Polylogarithmic-depth controlled-NOT gates without ancilla qubits

Abstract

Controlled operations are fundamental building blocks of quantum algorithms. Decomposing $n$-control-NOT gates ($C^n(X)$) into arbitrary single-qubit and CNOT gates, is a crucial but non-trivial task. This study introduces $C^n(X)$ circuits outperforming previous methods in the asymptotic and non-asymptotic regimes. Three distinct decompositions are presented: an exact one using one borrowed ancilla with a circuit depth $\Theta \left(\log (n{)}^3\right)$, an approximating one without ancilla qubits with a circuit depth $\mathcal{O}\left(\log (n{)}^3\log (1/\epsilon )\right)$ and an exact one with an adjustable-depth circuit which decreases with the number $m\le n$ of ancilla qubits available as $O(log(2n/m{)}^3+log(m/2))$. The resulting exponential speedup is likely to have a substantial impact on fault-tolerant quantum computing by improving the complexities of countless quantum algorithms with applications ranging from quantum chemistry to physics, finance and quantum machine learning.

References in corpus (21)

• Quantum algorithm for solving linear systems of equations
• Quantum Simulation
• Hamiltonian Simulation by Qubitization
• Quantum algorithms for quantum chemistry and quantum materials science
• Roads towards fault-tolerant universal quantum computation
• A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits
• The Future of Quantum Computing with Superconducting Qubits
• Even more efficient quantum computations of chemistry through tensor hypercontraction
• Quantum computing for finance
• Is there evidence for exponential quantum advantage in quantum chemistry?
• Quantum Circuits for Isometries
• Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization
• High-precision quantum algorithms for partial differential equations
• Reliably assessing the electronic structure of cytochrome P450 on today's classical computers and tomorrow's quantum computers
• Deterministic Preparation of Dicke States
• Approximate Quantum Fourier Transform with $O(n\log (n))$ T gates
• Linear-Depth Quantum Circuits for n-qubit Toffoli gates with no Ancilla
• Linear-depth quantum circuits for multiqubit controlled gates
• Double sparse quantum state preparation
• Sparse Quantum State Preparation for Strongly Correlated Systems
• Decomposing Quantum Generalized Toffoli with an Arbitrary Number of Ancilla

Cited by in corpus (9)

• Quantum algorithm for the advection-diffusion equation and the Koopman-von Neumann approach to nonlinear dynamical systems
• Rise of conditionally clean ancillae for efficient quantum circuit constructions
• Encoding of linear kinetic plasma problems in quantum circuits via data compression
• Modular quantum signal processing in many variables
• Variational Quantum Algorithm for Constrained Combinatorial Optimization Problems
• Variational Quantum Subspace Construction via Symmetry-Preserving Cost Functions
• Shallow quantum circuit for generating extremely low-entangled approximate state designs
• Benincasa-Dowker-Glaser causal set actions by quantum counting
• An efficient explicit implementation of a near-optimal quantum algorithm for simulating linear dissipative differential equations