Unknown

Dataset Information

0

Polylogarithmic-depth controlled-NOT gates without ancilla qubits.


ABSTRACT: Controlled operations are fundamental building blocks of quantum algorithms. Decomposing n-control-NOT gates (Cn(X)) into arbitrary single-qubit and CNOT gates, is a crucial but non-trivial task. This study introduces Cn(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 Θ(log(n)3) , an approximating one without ancilla qubits with a circuit depth O(log(n)3log(1/ϵ)) and an exact one with an adjustable-depth circuit which decreases with the number m≤n of ancilla qubits available as O(log(n/⌊m/2⌋)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.

SUBMITTER: Claudon B 

PROVIDER: S-EPMC11246449 | biostudies-literature | 2024 Jul

REPOSITORIES: biostudies-literature

altmetric image

Publications

Polylogarithmic-depth controlled-NOT gates without ancilla qubits.

Claudon Baptiste B   Zylberman Julien J   Feniou César C   Debbasch Fabrice F   Peruzzo Alberto A   Piquemal Jean-Philip JP  

Nature communications 20240713 1


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 Θ ( log ( n ) 3 ) , an approximating one without ancilla  ...[more]

Similar Datasets

| S-EPMC7442480 | biostudies-literature
| S-EPMC3856813 | biostudies-literature
| S-EPMC10948820 | biostudies-literature
| S-EPMC11522314 | biostudies-literature
| S-EPMC3482629 | biostudies-other
| S-EPMC11372149 | biostudies-literature
| S-EPMC6089953 | biostudies-literature
| S-EPMC4848482 | biostudies-literature
| S-EPMC3644086 | biostudies-other
| S-EPMC4406124 | biostudies-literature