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 (7)

• Quantum algorithm for solving linear systems of equations
• The Future of Quantum Computing with Superconducting Qubits
• Quantum computing for finance
• Is there evidence for exponential quantum advantage in quantum chemistry?
• Linear-depth quantum circuits for multiqubit controlled gates
• 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