Polylogarithmic-depth controlled-NOT gates without ancilla qubits

Area of Science:

• Quantum Computing
• Quantum Information Science
• Algorithm Optimization

Background:

• Controlled operations, specifically n-control-NOT gates (Cⁿ(X)), are essential components in quantum algorithms.
• Efficiently decomposing Cⁿ(X) gates into fundamental single-qubit and CNOT gates is a significant challenge in quantum circuit design.

Purpose of the Study:

• To introduce novel Cⁿ(X) gate decomposition circuits that outperform existing methods.
• To provide efficient circuit decompositions applicable in both asymptotic and non-asymptotic quantum computing regimes.

Main Methods:

• Developed three distinct decomposition strategies for Cⁿ(X) gates.
• One exact decomposition utilizes a single ancilla qubit, achieving a circuit depth of $$.
• An approximate decomposition requires no ancilla qubits, with a circuit depth of $$.
• An adjustable-depth exact decomposition is presented, where depth decreases with available ancilla qubits (m≤n) as $$.

Main Results:

• The proposed Cⁿ(X) circuits demonstrate superior performance compared to previous decomposition techniques.
• Achieved exponential speedups in circuit complexity for controlled operations.
• The decompositions are effective in both asymptotic and non-asymptotic scenarios.

Conclusions:

• The developed Cⁿ(X) decomposition methods offer significant improvements for quantum circuit construction.
• These advancements are expected to enhance the efficiency of numerous quantum algorithms across diverse fields.
• Potential impact on fault-tolerant quantum computing, quantum chemistry, physics, finance, and quantum machine learning.