Polylogarithmic-depth controlled-NOT gates without ancilla qubits.
basic_science · Level V
Where this comes from
- Record sourced from PubMed, PMID 39003276.
- Also identified by DOI 10.1038/s41467-024-50065-x and PMC identifier 11246449.
- Licence recorded as CC BY.
- The licence permits redistribution, so the abstract is shown in full and the full text is available from the publisher.
Abstract
Controlled operations are fundamental building blocks of quantum algorithms. Decomposing n-control-NOT gates (C<sup>n</sup>(X)) into arbitrary single-qubit and CNOT gates, is a crucial but non-trivial task. This study introduces C<sup>n</sup>(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 <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>Θ</mi> <mrow><mo>(</mo> <mrow><mi>log</mi> <msup> <mrow><mrow><mo>(</mo> <mrow><mi>n</mi></mrow> <mo>)</mo></mrow> </mrow> <mrow><mn>3</mn></mrow> </msup> </mrow> <mo>)</mo></mrow> </math> , an approximating one without ancilla qubits with a circuit depth <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>O</mi> <mrow><mo>(</mo> <mrow><mi>log</mi> <msup> <mrow><mrow><mo>(</mo> <mrow><mi>n</mi></mrow> <mo>)</mo></mrow> </mrow> <mrow><mn>3</mn></mrow> </msup> <mi>log</mi> <mrow><mo>(</mo> <mrow><mn>1</mn> <mo>/</mo> <mi>ϵ</mi></mrow> <mo>)</mo></mrow> </mrow> <mo>)</mo></mrow> </math> and an exact one with an adjustable-depth circuit which decreases with the number m≤n of ancilla qubits available as <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>O</mi> <mrow><mo>(</mo> <mrow><mi>log</mi> <msup> <mrow><mrow><mo>(</mo> <mrow><mi>n</mi> <mo>/</mo> <mrow><mo>⌊</mo> <mrow><mi>m</mi> <mo>/</mo> <mn>2</mn></mrow> <mo>⌋</mo></mrow> </mrow> <mo>)</mo></mrow> </mrow> <mrow><mn>3</mn></mrow> </msup> <mo>+</mo> <mi>log</mi> <mrow><mo>(</mo> <mrow><mrow><mo>⌊</mo> <mrow><mi>m</mi> <mo>/</mo> <mn>2</mn></mrow> <mo>⌋</mo></mrow> </mrow> <mo>)</mo></mrow> </mrow> <mo>)</mo></mrow> </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.