Polylogarithmic-depth controlled-NOT gates without ancilla qubits

Abstract

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 (\log {(n)}^{3})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>Θ</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mrow> <mml:mi>log</mml:mi> <mml:msup> <mml:mrow> <mml:mrow> <mml:mo>(</mml:mo> <mml:mrow> <mml:mi>n</mml:mi> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> <mml:mrow> <mml:mn>3</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> , an approximating one without ancilla qubits with a circuit depth $${{{{{{{\mathcal{O}}}}}}}}(\log {(n)}^{3}\log (1/\epsilon ))$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>O</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mrow> <mml:mi>log</mml:mi> <mml:msup> <mml:mrow> <mml:mrow> <mml:mo>(</mml:mo> <mml:mrow> <mml:mi>n</mml:mi> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> <mml:mrow> <mml:mn>3</mml:mn> </mml:mrow> </mml:msup> <mml:mi>log</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mi>ϵ</mml:mi> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> and an exact one with an adjustable-depth circuit which decreases with the number m ≤ n of ancilla qubits available as $${{{{{{{\mathcal{O}}}}}}}}(\log {(n/\lfloor m/2\rfloor )}^{3}+\log (\lfloor m/2\rfloor ))$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>O</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mrow> <mml:mi>log</mml:mi> <mml:msup> <mml:mrow> <mml:mrow> <mml:mo>(</mml:mo> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>/</mml:mo> <mml:mrow> <mml:mo>⌊</mml:mo> <mml:mrow> <mml:mi>m</mml:mi> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> <mml:mo>⌋</mml:mo> </mml:mrow> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> <mml:mrow> <mml:mn>3</mml:mn> </mml:mrow> </mml:msup> <mml:mo>+</mml:mo> <mml:mi>log</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mrow> <mml:mrow> <mml:mo>⌊</mml:mo> <mml:mrow> <mml:mi>m</mml:mi> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> <mml:mo>⌋</mml:mo> </mml:mrow> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . 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.

Topics & Concepts