Low-overhead constructions for the fault-tolerant Toffoli gate

2013/02/20 by Cody Jones · 19 citations
Computer Science · Engineering · #Quantum Computing Algorithms and Architecture #Radiation Effects in Electronics #Advancements in Semiconductor Devices and Circuit Design

paper · doi:10.1103/physreva.87.022328

Abstract

We present two 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\ensuremathπ\ensuremathσ^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 \ensuremathσ^z error occurring with probability p in any one of eight T gates required to produce the Toffoli gate. By postselecting 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² 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.

Citations

• Universal quantum computation with ideal Clifford gates and noisy ancillas
• Elementary gates for quantum computation
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer

Cited by

• Offloading Quantum Computation by Superposition Masking
• Logic Synthesis for Quantum Computing
• Space-Time Tradeoffs of Pauli-Based Computation in Distributed qLDPC Architectures
• Fault-Tolerant Resource Comparison of Qudit and Qubit Encodings for Diagonal Quadratic Operators
• Computing 256-bit Elliptic Curve Logarithm in 9 Hours with 126133 Cat Qubits
• Stab-QRAM: An All-Clifford Quantum Random Access Memory for Special Data
• Distributed Quantum Error Correction with Permutation-Invariant Approximate Codes
• Effective Compression of Quantum Braided Circuits Aided by ZX-Calculus
• Resource optimization for fault-tolerant quantum computing
• Solving reaction dynamics with quantum computing algorithms
• Transversal AND in Quantum Codes
• Optimized quantum algorithms for simulating the Schwinger effect
• Recursive algorithm for constructing antisymmetric fermionic states in first quantization mapping
• Practical Fidelity Limits of Toffoli Gates in Superconducting Quantum Processors
• Unitary Synthesis with AlphaZero via Dynamic Circuits
• Application of resource theory based on free Clifford+kT computation to early fault-tolerant quantum computing
• Resource-Efficient Synthesis of Sparse Quantum States
• A simpler Gaussian state-preparation
• T-count Optimized Quantum Circuits for Bilinear Interpolation

Related

• Logic Synthesis for Fault-Tolerant Quantum Computers
• Synthesizing Toffoli-optimal quantum circuits for arbitrary multi-qubit unitaries
• Fault-tolerance of ancilla preparation for logical Toffoli gate of a family of Calderbank-Shor-Steane codes
• Multi-qubit Toffoli with exponentially fewer T gates
• Quantum circuit for multi-qubit Toffoli gate with optimal resource