Novel constructions for the fault-tolerant Toffoli gate

Abstract

We present two new constructions for the Toffoli gate which substantially reduce resource costs in fault-tolerant quantum computing. The first contribution is a Toffoli gate requiring Clifford operations plus only four $T=\exp (i\pi {\sigma }^z/8)$ gates, whereas conventional circuits require seven $T$ gates. An extension of this result is that adding $n$ control inputs to a controlled gate requires $4n$ $T$ gates, whereas the best prior result was $8n$. The second contribution is a quantum circuit for the Toffoli gate which can detect a single ${\sigma }^z$ error occurring with probability $p$ in any one of eight $T$ gates required to produce the Toffoli. By post-selecting circuits that did not detect an error, the posterior error probability is suppressed to lowest order from $4p$ (or $7p$, without the first contribution) to $28p^2$ for this enhanced construction. In fault-tolerant quantum computing, this construction can reduce the overhead for producing logical Toffoli gates by an order of magnitude.

5 pages, 4 figures

References in corpus (19)

• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Elementary gates for quantum computation
• Surface codes: Towards practical large-scale quantum computation
• Quantum Teleportation is a Universal Computational Primitive
• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Reliable Quantum Computers
• Topological fault-tolerance in cluster state quantum computation
• A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits
• High threshold universal quantum computation on the surface code
• Magic state distillation with low overhead
• Methodology for quantum logic gate constructions
• Quantum circuits of T-depth one
• Layered architecture for quantum computing
• Fast Quantum Modular Exponentiation
• Simulating chemistry efficiently on fault-tolerant quantum computers
• Multilevel distillation of magic states for quantum computing
• A bridge to lower overhead quantum computation
• Resource Requirements for Fault-Tolerant Quantum Simulation: The Transverse Ising Model Ground State
• Distilling one-qubit magic states into Toffoli states

Cited by in corpus (108)

• Majorana Zero Modes and Topological Quantum Computation
• Roads towards fault-tolerant universal quantum computation
• Application of a resource theory for magic states to fault-tolerant quantum computing
• A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery
• Building a fault-tolerant quantum computer using concatenated cat codes
• Simulation of quantum circuits by low-rank stabilizer decompositions
• Halving the cost of quantum addition
• Quantum Computer Systems for Scientific Discovery
• Universal fault-tolerant quantum computation with only transversal gates and error correction
• Magic State Distillation: Not as Costly as You Think
• Chemical Basis of Trotter-Suzuki Errors in Quantum Chemistry Simulation
• Quantum computation with realistic magic state factories
• Focus beyond quadratic speedups for error-corrected quantum advantage
• Quantum Algorithms for Simulating the Lattice Schwinger Model
• Efficient synthesis of universal Repeat-Until-Success circuits
• Improved Techniques for Preparing Eigenstates of Fermionic Hamiltonians
• Efficient magic state factories with a catalyzed |CCZ> to 2|T> transformation
• Lower bounds on the non-Clifford resources for quantum computations
• Quantifying the magic of quantum channels
• Factoring with Qutrits: Shor's Algorithm on Ternary and Metaplectic Quantum Architectures
• Fault-Tolerant High Level Quantum Circuits: Form, Compilation and Description
• High-fidelity three-qubit iToffoli gate for fixed-frequency superconducting qubits
• Fault-tolerant resource estimate for quantum chemical simulations: Case study on Li-ion battery electrolyte molecules
• A unified framework for magic state distillation and multi-qubit gate-synthesis with reduced resource cost
• Approximate Quantum Fourier Transform with $O(n\log (n))$ T gates
• Universal quantum computing with twist-free and temporally encoded lattice surgery
• Quantum-centric Supercomputing for Materials Science: A Perspective on Challenges and Future Directions
• Extracting Success from IBM's 20-Qubit Machines Using Error-Aware Compilation
• Codes and Protocols for Distilling $T$, controlled-$S$, and Toffoli Gates
• Early fault-tolerant simulations of the Hubbard model
• Universal fault-tolerant gates on concatenated stabilizer codes
• Efficient Decomposition of Single-Qubit Gates into $V$ Basis Circuits
• Applying quantum algorithms to constraint satisfaction problems
• Surface code compilation via edge-disjoint paths
• Magic State Distillation with Low Space Overhead and Optimal Asymptotic Input Count
• Unifying gate-synthesis and magic state distillation
• General quantum algorithms for Hamiltonian simulation with applications to a non-Abelian lattice gauge theory
• Braiding Majorana zero modes using quantum dots
• Distilling one-qubit magic states into Toffoli states
• Simulating quantum circuits with ZX-calculus reduced stabiliser decompositions
• Hybridized Methods for Quantum Simulation in the Interaction Picture
• Constrained Optimization via Quantum Zeno Dynamics
• Lower bound for the T count via unitary stabilizer nullity
• The Impact of Hardware Specifications on Reaching Quantum Advantage in the Fault Tolerant Regime
• Floating Point Representations in Quantum Circuit Synthesis
• Quantifying Qubit Magic Resource with Gottesman-Kitaev-Preskill Encoding
• Quantum Resources Required to Block-Encode a Matrix of Classical Data
• Morphing quantum codes
• ZX-calculus for the working quantum computer scientist
• A polynomial time and space heuristic algorithm for T-count
• Techniques to Reduce $\pi /4$-Parity-Phase Circuits, Motivated by the ZX Calculus
• Composite Toffoli gate with two-round error detection
• Quantum Computation with Topological Codes: from qubit to topological fault-tolerance
• Repeat-Until-Success circuits with fixed-point oblivious amplitude amplification
• Effective Compression of Quantum Braided Circuits Aided by ZX-Calculus
• Shallow unitary decompositions of quantum Fredkin and Toffoli gates for connectivity-aware equivalent circuit averaging
• Magic State Distillation from Entangled States
• Synthesizing efficient circuits for Hamiltonian simulation
• End-to-end resource analysis for quantum interior point methods and portfolio optimization
• Error rates and resource overheads of encoded three-qubit gates
• Repeat-Until-Success: Non-deterministic decomposition of single-qubit unitaries
• State-injection schemes of quantum computation in Spekkens' toy theory
• Quantum Simulations of Chemistry in First Quantization with any Basis Set
• Fault-tolerant Preparation of Stabilizer States for Quantum CSS Codes by Classical Error-Correcting Codes
• Logic Synthesis for Quantum Computing
• A Regular Representation of Quantum Circuits
• Rise of conditionally clean ancillae for efficient quantum circuit constructions
• Synthesis of Arbitrary Quantum Circuits to Topological Assembly: Systematic, Online and Compact
• Option pricing under stochastic volatility on a quantum computer
• Quantum Computation of Eigenvalues within Target Intervals
• The phase/state duality in reversible circuit design
• Solving reaction dynamics with quantum computing algorithms
• Faster Born probability estimation via gate merging and frame optimisation
• Code switching revisited: Low-overhead magic state preparation using color codes
• Flexible layout of surface code computations using AutoCCZ states
• Quantum Computation of Electronic Structure with Projector Augmented-Wave Method and Plane Wave Basis Set
• QContext: Context-Aware Decomposition for Quantum Gates
• T-count and Qubit Optimized Quantum Circuit Designs of Carry Lookahead Adder
• Optimal and asymptotically optimal NCT reversible circuits by the gate types
• Quantum Simulation of the First-Quantized Pauli-Fierz Hamiltonian
• Measurement sequences for magic state distillation
• Lower T-count with faster algorithms
• T-count Optimized Quantum Circuits for Bilinear Interpolation
• A quantum random access memory (QRAM) using a polynomial encoding of binary strings
• Ladder Operator Block-Encoding
• Resource optimization for fault-tolerant quantum computing
• Applying Grover's algorithm to AES: quantum resource estimates
• Lowering the T-depth of Quantum Circuits By Reducing the Multiplicative Depth Of Logic Networks
• A Q# Implementation of a Quantum Lookup Table for Quantum Arithmetic Functions
• A CCCZ gate performed with 6 T gates
• Time versus Hardware: Reducing Qubit Counts with a (Surface Code) Data Bus
• Low Depth Phase Oracle Using a Parallel Piecewise Circuit
• Quantum resource estimates for computing binary elliptic curve discrete logarithms
• A Jordan-Wigner gadget that reduces T count by more than 6x for quantum chemistry applications
• Clifford operators in SU(N)1; N not odd prime
• Noise-Canceling Quantum Feedback: non-Hermitian Dynamics with Applications to State Preparation and Magic State Distillation
• Efficient simulation of logical magic state preparation protocols
• Quantum Theory from Principles, Quantum Software from Diagrams
• Classification and transformations of quantum circuit decompositions for permutation operations
• Benchmarking Quantum Simulation of Chemical Hamiltonians using the Sorted-List Encoding
• Quantum phase estimation with optimal confidence interval using three control qubits
• Measurement-Driven Adaptive Low-Overhead Implementation of Multi-Controlled Toffoli Gates
• Transversal AND in Quantum Codes
• A T-depth two Toffoli gate for 2D square lattice architectures
• Offloading Quantum Computation by Superposition Masking
• Polynomial-Time Classical Simulation of Hidden Shift Circuits via Confluent Rewriting of Symbolic Sums
• Hypergraph States in SU(N)1, N odd prime, Chern-Simons Theory
• Benincasa-Dowker-Glaser causal set actions by quantum counting