Shallow unitary decompositions of quantum Fredkin and Toffoli gates for connectivity-aware equivalent circuit averaging
arXiv:2305.18128 · doi:10.1063/5.0187026
Abstract
The controlled-SWAP and controlled-controlled-NOT gates are at the heart of the original proposal of reversible classical computation by Fredkin and Toffoli. Their widespread use in quantum computation, both in the implementation of classical logic subroutines of quantum algorithms and in quantum schemes with no direct classical counterparts, has made it imperative early on to pursue their efficient decomposition in terms of the lower-level gate sets native to different physical platforms. Here, we add to this body of literature by providing several logically equivalent circuits for the Toffoli and Fredkin gates under all-to-all and linear qubit connectivity, the latter with two different routings for control and target qubits. Besides achieving the lowest CNOT counts in the literature for all these configurations, we also demonstrate the remarkable effectiveness of the obtained decompositions at mitigating coherent errors on near-term quantum computers via equivalent circuit averaging. We first quantify the performance of the method in silico with a coherent-noise model before validating it experimentally on a superconducting quantum processor. In addition, we consider the case where the three qubits on which the Toffoli or Fredkin gates act nontrivially are not adjacent, proposing a novel scheme to reorder them that saves one CNOT for every SWAP. This scheme also finds use in the shallow implementation of long-range CNOTs. Our results highlight the importance of considering different entangling gate structures and connectivity constraints when designing efficient quantum circuits.
arXiv commentMain text: 12 pages, 8 figures. Appendix: 4 sections, 5 figures. OpenQASM files are available in the referenced, publicly accessible online repository
References in corpus (65)
- Quantum Computing in the NISQ era and beyond
- Elementary gates for quantum computation
- Surface codes: Towards practical large-scale quantum computation
- QuTiP: An open-source Python framework for the dynamics of open quantum systems
- Circuit Quantum Electrodynamics
- Quantum computational chemistry
- Silicon Quantum Electronics
- Quantum fingerprinting
- Quantum Networks for Elementary Arithmetic Operations
- Quantum Error Correction for Beginners
- Synthesis of Quantum Logic Circuits
- Realization of Three-Qubit Quantum Error Correction with Superconducting Circuits
- A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits
- Noise tailoring for scalable quantum computation via randomized compiling
- Quantum computations without definite causal structure
- Quantum Simulation of Electronic Structure with Linear Depth and Connectivity
- Direct estimations of linear and non-linear functionals of a quantum state
- Universal Quantum Estimator
- Implementation of a Toffoli Gate with Superconducting Circuits
- Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity
- Efficient Toffoli Gates Using Qudits
- An Artificial Neuron Implemented on an Actual Quantum Processor
- Quantum circuits of T-depth one
- Arbitrarily accurate composite pulses
- Novel constructions for the fault-tolerant Toffoli gate
- On the advantages of using relative phase Toffolis with an application to multiple control Toffoli optimization
- Graph-theoretic Simplification of Quantum Circuits with the ZX-calculus
- A divide-and-conquer algorithm for quantum state preparation
- Quantum circuits for strongly correlated quantum systems
- Quantum algorithms to simulate many-body physics of correlated fermions
- A quantum Fredkin gate
- Suppression of crosstalk in superconducting qubits using dynamical decoupling
- The non-local content of quantum operations
- Reducing unitary and spectator errors in cross resonance with optimized rotary echoes
- Quantum computers as universal quantum simulators: state-of-art and perspectives
- A Simple Proof that Toffoli and Hadamard are Quantum Universal
- High-Fidelity Single-Shot Toffoli Gate via Quantum Control
- PyZX: Large Scale Automated Diagrammatic Reasoning
- Efficient error models for fault-tolerant architectures and the Pauli twirling approximation
- Linear optics quantum Toffoli and Fredkin gates
- High-fidelity three-qubit iToffoli gate for fixed-frequency superconducting qubits
- Asymptotic Improvements to Quantum Circuits via Qutrits
- Both Toffoli and Controlled-NOT need little help to do universal quantum computation
- Fusing multiple W states simultaneously with a Fredkin gate
- There and back again: A circuit extraction tale
- Single-step implementation of high fidelity -bit Toffoli gate
- Quantum circuits for measuring weak values, Kirkwood--Dirac quasiprobability distributions, and state spectra
- Coherence in logical quantum channels
- Realization of efficient quantum gates with a superconducting qubit-qutrit circuit
- Mitigating Coherent Noise Using Pauli Conjugation
- Methods for linear optical quantum Fredkin gate
- Shorter gate sequences for quantum computing by mixing unitaries
- Quantum computation with indefinite causal structures
- How weak values emerge in joint measurements on cloned quantum systems
- Optimal synthesis of the Fredkin gate in a multilevel system
- Dynamics of quantum causal structures
- Efficient construction of three- and four-qubit quantum gates by global entangling gates
- Preparing Valence-Bond-Solid states on noisy intermediate-scale quantum computers
- Efficient variational synthesis of quantum circuits with coherent multi-start optimization
- Subdivided Phase Oracle for NISQ Search Algorithms
- Orchestrated Trios: Compiling for Efficient Communication in Quantum Programs with 3-Qubit Gates
- Gutzwiller wave function on a digital quantum computer
- Simpler semidefinite programs for completely bounded norms
- Hardware-Conscious Optimization of the Quantum Toffoli Gate
- Testing complementarity on a transmon quantum processor
Cited by in corpus (11)
- A Toffoli Gate Decomposition via Echoed Cross-Resonance Gates
- Direct Implementation of High-Fidelity Three-Qubit Gates for Superconducting Processor with Tunable Couplers
- MIRAGE: Quantum Circuit Decomposition and Routing Collaborative Design using Mirror Gates
- Inductive Construction of Variational Quantum Circuit for Constrained Combinatorial Optimization
- Accurate and Honest Approximation of Correlated Qubit Noise
- An Efficient Decomposition of the Carleman Linearized Burgers' Equation
- All You Need is pi: Quantum Computing with Hermitian Gates
- An Error Mitigated Non-Orthogonal Quantum Eigensolver via Shadow Tomography
- Certifying entanglement dimensionality by -reduction moments
- Jenga-Krotov algorithm: Efficient compilation of multi-qubit gates for exchange-only qubits
- Resource Constraint Estimation of In-Quantum Implementated Mini-AES