arXiv:1304.7516

Quantum Circuits for GCD Computation with $O(n \log n)$ Depth and O(n) Ancillae

Mehdi Saeedi, Igor L. Markov

Published Apr 28, 2013• 2 citations

Abstract

GCD computations and variants of the Euclidean algorithm enjoy broad uses in both classical and quantum algorithms. In this paper, we propose quantum circuits for GCD computation with $O(n \log n)$ depth with O(n) ancillae. Prior circuit construction needs $O(n^2)$ running time with O(n) ancillae. The proposed construction is based on the binary GCD algorithm and it benefits from log-depth circuits for 1-bit shift, comparison/subtraction, and managing ancillae. The worst-case gate count remains $O(n^2)$, as in traditional circuits.

DOI: 10.48550/arxiv.1304.7516

Related papers

Asymptotically Optimal Quantum Circuits for Comparators and Incrementers

Vivien Vandaele

quant-pharXiv:2603.12917Mar 16, 20260 citations

Nearly optimal quantum circuits for Boolean oracles

Junhong Nie, Wei Zi

quant-pharXiv:2607.28402Jul 31, 20260 citations

A quantum algorithm for greatest common divisor problem

Wen Wang, Xu Jiang, Liangzhu Mu +1 more

arXiv:1707.06430Jul 20, 20172 citations

Ancilla-free optimal quantum adder

Junhong Nie, Jialiang Tang, Xiaoming Sun +1 more

quant-pharXiv:2610.34446Oct 27, 20260 citations

Asymptotic improvements to quantum circuits via qutrits

Pranav Gokhale, Jonathan M. Baker, Casey Duckering +3 more

arXiv:1905.10481Proceedings - International Symposium on Computer Architecture/ProceedingsJun 14, 2019120 citations

Polylogarithmic-depth controlled-NOT gates without ancilla qubits

Baptiste Claudon, Julien Zylberman, César Feniou +3 more

arXiv:2312.13206Nature CommunicationsJul 13, 202419 citations

arXiv:1304.7516

Quantum Circuits for GCD Computation with $O(n \log n)$ Depth and O(n) AncillaeQuantum Circuits for GCD Computation with $O(n \log n)$ Depth and O(n) Ancillae

Mehdi Saeedi, Igor L. Markov

Published Apr 28, 2013• 2 citations

arXiv HTML PDF

Abstract

GCD computations and variants of the Euclidean algorithm enjoy broad uses in both classical and quantum algorithms. In this paper, we propose quantum circuits for GCD computation with

O(n \log n)

depth with O(n) ancillae. Prior circuit construction needs

O(n^2)

running time with O(n) ancillae. The proposed construction is based on the binary GCD algorithm and it benefits from log-depth circuits for 1-bit shift, comparison/subtraction, and managing ancillae. The worst-case gate count remains

O(n^2)

, as in traditional circuits.

DOI: 10.48550/arxiv.1304.7516

Related papers

Asymptotically Optimal Quantum Circuits for Comparators and Incrementers

Vivien Vandaele

We present quantum circuits for comparison and increment operations that achieve an asymptotically optimal gate count of $Θ(n)$ and depth of $Θ(\log n)$ over the Clifford+Toffoli gate set, while using a provably minimal number of qubits. We extend these results to classical-quantum comparators, yielding an improved classical-quantum adder with an optimal qubit count. Given the ubiquity of these operations as algorithmic building blocks, our constructions translate directly into reduced circuit complexity for many quantum algorithms. As a notable example, they can be used to improve a space-efficient circuit for Shor's factoring algorithm, reducing circuit depth from $\mathcal{O}(n^3)$ to $\mathcal{O}(n^2 \log^2 n)$ without increasing either the qubit count or the asymptotic gate complexity. Underpinning these results is a general theorem demonstrating how to trade ancilla qubits for control qubits with low overhead in both depth and gate count, providing a broadly applicable tool for quantum circuit design.We present quantum circuits for comparison and increment operations that achieve an asymptotically optimal gate count of $Θ(n)$ and depth of $Θ(\log n)$ over the Clifford+Toffoli gate set, while using a provably minimal number of qubits. We extend these results to classical-quantum comparators, yielding an improved classical-quantum adder with an optimal qubit count. Given the ubiquity of these operations as algorithmic building blocks, our constructions translate directly into reduced circuit complexity for many quantum algorithms. As a notable example, they can be used to improve a space-efficient circuit for Shor's factoring algorithm, reducing circuit depth from $\mathcal{O}(n^3)$ to $\mathcal{O}(n^2 \log^2 n)$ without increasing either the qubit count or the asymptotic gate complexity. Underpinning these results is a general theorem demonstrating how to trade ancilla qubits for control qubits with low overhead in both depth and gate count, providing a broadly applicable tool for quantum circuit design.

quant-pharXiv:2603.12917Mar 16, 20260 citations

Nearly optimal quantum circuits for Boolean oracles

Junhong Nie, Wei Zi

Quantum oracle of Boolean functions is one of the central bridges between classical and quantum algorithms, but the study focusing at quantum circuit optimization of such oracle is yet closed. In this paper, we propose nearly optimal tradeoffs among circuit size, circuit depth and ancilla count, for quantum oracles of three kinds of Boolean functions: general total Boolean functions with output size $b$ : with $1\le m\leΘ\left(\frac{2^n}{n}\right)$ ancilla, size $\mathcal{O}\left(\frac{b2^n}{\log(n+m)}\right)$ , depth $\mathcal{O}\left(\frac{b2^n}{n+m}\right)$ ; partial Boolean functions of effective support size $d$ and output size $b$ : with $Θ\left(\log d\right)\le m\le Θ\left(d\right)$ ancilla, size $\mathcal{O}\left(n\log d+bd\right)$ , depth $\mathcal{O}\left(\frac{n\log n\log d}{n+m}+\log n+\frac{d(\log d+b\log m)}{m}\right)$ ; sparse Boolean functions of true input size $d$ : with $Θ\left(\log n+\log d\right)\le m\leΘ\left(\frac{nd}{\log d}\right)$ ancilla, size $\mathcal{O}\left(n^2\log d+\frac{nd}{\log(\log d+m/n)}\right)$ , depth $\mathcal{O}\left(\frac{n^2\log n\log d}{n+m}+\log n+\frac{nd}{m}\right)$ . All the size and depth bounds are asymptotically optimal up to logarithmic factors in the corresponding ancilla count regions. We hope these results find applications in scenarios where classical procedures are needed to be embedded into quantum circuits, such as QROM implementation and quantum algorithm design.Quantum oracle of Boolean functions is one of the central bridges between classical and quantum algorithms, but the study focusing at quantum circuit optimization of such oracle is yet closed. In this paper, we propose nearly optimal tradeoffs among circuit size, circuit depth and ancilla count, for quantum oracles of three kinds of Boolean functions: general total Boolean functions with output size $b$: with $1\le m\leΘ\left(\frac{2^n}{n}\right)$ ancilla, size $\mathcal{O}\left(\frac{b2^n}{\log(n+m)}\right)$, depth $\mathcal{O}\left(\frac{b2^n}{n+m}\right)$; partial Boolean functions of effective support size $d$ and output size $b$: with $Θ\left(\log d\right)\le m\le Θ\left(d\right)$ ancilla, size $\mathcal{O}\left(n\log d+bd\right)$, depth $\mathcal{O}\left(\frac{n\log n\log d}{n+m}+\log n+\frac{d(\log d+b\log m)}{m}\right)$; sparse Boolean functions of true input size $d$: with $Θ\left(\log n+\log d\right)\le m\leΘ\left(\frac{nd}{\log d}\right)$ ancilla, size $\mathcal{O}\left(n^2\log d+\frac{nd}{\log(\log d+m/n)}\right)$, depth $\mathcal{O}\left(\frac{n^2\log n\log d}{n+m}+\log n+\frac{nd}{m}\right)$. All the size and depth bounds are asymptotically optimal up to logarithmic factors in the corresponding ancilla count regions. We hope these results find applications in scenarios where classical procedures are needed to be embedded into quantum circuits, such as QROM implementation and quantum algorithm design.

quant-pharXiv:2607.28402Jul 31, 20260 citations

A quantum algorithm for greatest common divisor problem

Wen Wang, Xu Jiang, Liangzhu Mu +1 more

We present a quantum algorithm solving the greatest common divisor (GCD) problem. This quantum algorithm possesses similar computational complexity with classical algorithms, such as the well-known Euclidean algorithm for GCD. This algorithm is an application of the quantum algorithms for the hidden subgroup problems, the same as Shor factoring algorithm. Explicit quantum circuits realized by quantum gates for this quantum algorithm are provided. We also give a computer simulation of this quantum algorithm and present the expected outcomes for the corresponding quantum circuit.We present a quantum algorithm solving the greatest common divisor (GCD) problem. This quantum algorithm possesses similar computational complexity with classical algorithms, such as the well-known Euclidean algorithm for GCD. This algorithm is an application of the quantum algorithms for the hidden subgroup problems, the same as Shor factoring algorithm. Explicit quantum circuits realized by quantum gates for this quantum algorithm are provided. We also give a computer simulation of this quantum algorithm and present the expected outcomes for the corresponding quantum circuit.

arXiv:1707.06430Jul 20, 20172 citations

Ancilla-free optimal quantum adder

Junhong Nie, Jialiang Tang, Xiaoming Sun +1 more

We construct an exact $n$ -bit quantum adder with $O(n)$ gates and $O(\log n)$ depth that requires no ancillary qubits. The circuit uses only $X$ , CNOT, and Toffoli gates under all-to-all connectivity and is classically reversible. Our construction accelerates the controlled ladder underlying addition. Grouping the data into blocks and use existing control qubits as conditional workspace gives a recursive construction with $O(n\log\log n)$ gates and $O(\log n)$ depth. We then coordinate inter-block propagation via two short-path forest operations to cut the per-block workspace requirement, yielding a nonrecursive implementation with $O(n)$ gates. Both the gate count and circuit depth are asymptotically optimal.We construct an exact $n$-bit quantum adder with $O(n)$ gates and $O(\log n)$ depth that requires no ancillary qubits. The circuit uses only $X$, CNOT, and Toffoli gates under all-to-all connectivity and is classically reversible. Our construction accelerates the controlled ladder underlying addition. Grouping the data into blocks and use existing control qubits as conditional workspace gives a recursive construction with $O(n\log\log n)$ gates and $O(\log n)$ depth. We then coordinate inter-block propagation via two short-path forest operations to cut the per-block workspace requirement, yielding a nonrecursive implementation with $O(n)$ gates. Both the gate count and circuit depth are asymptotically optimal.

quant-pharXiv:2610.34446Oct 27, 20260 citations

Asymptotic improvements to quantum circuits via qutrits

Pranav Gokhale, Jonathan M. Baker, Casey Duckering +3 more

Quantum computation is traditionally expressed in terms of quantum bits, or qubits. In this work, we instead consider three-level qutrits. Past work with qutrits has demonstrated only constant factor improvements, owing to the log2(3) binary-to-ternary compression factor. We present a novel technique using qutrits to achieve a logarithmic depth (runtime) decomposition of the Generalized Toffoli gate using no ancilla-a significant improvement over linear depth for the best qubit-only equivalent. Our circuit construction also features a 70x improvement in two-qudit gate count over the qubit-only equivalent decomposition. This results in circuit cost reductions for important algorithms like quantum neurons and Grover search. We develop an open-source circuit simulator for qutrits, along with realistic near-term noise models which account for the cost of operating qutrits. Simulation results for these noise models indicate over 90% mean reliability (fidelity) for our circuit construction, versus under 30% for the qubit-only baseline. These results suggest that qutrits offer a promising path towards scaling quantum computation.Quantum computation is traditionally expressed in terms of quantum bits, or qubits. In this work, we instead consider three-level qutrits. Past work with qutrits has demonstrated only constant factor improvements, owing to the log2(3) binary-to-ternary compression factor. We present a novel technique using qutrits to achieve a logarithmic depth (runtime) decomposition of the Generalized Toffoli gate using no ancilla-a significant improvement over linear depth for the best qubit-only equivalent. Our circuit construction also features a 70x improvement in two-qudit gate count over the qubit-only equivalent decomposition. This results in circuit cost reductions for important algorithms like quantum neurons and Grover search. We develop an open-source circuit simulator for qutrits, along with realistic near-term noise models which account for the cost of operating qutrits. Simulation results for these noise models indicate over 90% mean reliability (fidelity) for our circuit construction, versus under 30% for the qubit-only baseline. These results suggest that qutrits offer a promising path towards scaling quantum computation.

arXiv:1905.10481Proceedings - International Symposium on Computer Architecture/ProceedingsJun 14, 2019120 citations

Polylogarithmic-depth controlled-NOT gates without ancilla qubits

Baptiste Claudon, Julien Zylberman, César Feniou +3 more

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 $\Theta (\log {(n)}^{3})$ Θ ( log ( n ) 3 ) , an approximating one without ancilla qubits with a circuit depth ${{{{{{{\mathcal{O}}}}}}}}(\log {(n)}^{3}\log (1/\epsilon ))$ O ( log ( n ) 3 log ( 1 / ϵ ) ) 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 ))$ 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.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 $$\Theta (\log {(n)}^{3})$$ Θ ( log ( n ) 3 ) , an approximating one without ancilla qubits with a circuit depth $${{{{{{{\mathcal{O}}}}}}}}(\log {(n)}^{3}\log (1/\epsilon ))$$ O ( log ( n ) 3 log ( 1 / ϵ ) ) 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 ))$$ 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.

arXiv:2312.13206Nature CommunicationsJul 13, 202419 citations

Quantum Circuits for GCD Computation with

O(n \log n)

Depth and O(n) Ancillae

GCD computations and variants of the Euclidean algorithm enjoy broad uses in both classical and quantum algorithms. In this paper, we propose quantum circuits for GCD computation with

O(n \log n)

depth with O(n) ancillae. Prior circuit construction needs

O(n^2)

O(n^2)

, as in traditional circuits.

We present quantum circuits for comparison and increment operations that achieve an asymptotically optimal gate count of

Θ(n)

and depth of

Θ(\log n)

over the Clifford+Toffoli gate set, while using a provably minimal number of qubits. We extend these results to classical-quantum comparators, yielding an improved classical-quantum adder with an optimal qubit count. Given the ubiquity of these operations as algorithmic building blocks, our constructions translate directly into reduced circuit complexity for many quantum algorithms. As a notable example, they can be used to improve a space-efficient circuit for Shor's factoring algorithm, reducing circuit depth from

\mathcal{O}(n^3)

\mathcal{O}(n^2 \log^2 n)

without increasing either the qubit count or the asymptotic gate complexity. Underpinning these results is a general theorem demonstrating how to trade ancilla qubits for control qubits with low overhead in both depth and gate count, providing a broadly applicable tool for quantum circuit design.

b

: with

1\le m\leΘ\left(\frac{2^n}{n}\right)

ancilla, size

\mathcal{O}\left(\frac{b2^n}{\log(n+m)}\right)

, depth

\mathcal{O}\left(\frac{b2^n}{n+m}\right)

; partial Boolean functions of effective support size

d

and output size

b

: with

Θ\left(\log d\right)\le m\le Θ\left(d\right)

ancilla, size

\mathcal{O}\left(n\log d+bd\right)

, depth

\mathcal{O}\left(\frac{n\log n\log d}{n+m}+\log n+\frac{d(\log d+b\log m)}{m}\right)

; sparse Boolean functions of true input size

d

: with

Θ\left(\log n+\log d\right)\le m\leΘ\left(\frac{nd}{\log d}\right)

ancilla, size

\mathcal{O}\left(n^2\log d+\frac{nd}{\log(\log d+m/n)}\right)

, depth

\mathcal{O}\left(\frac{n^2\log n\log d}{n+m}+\log n+\frac{nd}{m}\right)

. All the size and depth bounds are asymptotically optimal up to logarithmic factors in the corresponding ancilla count regions. We hope these results find applications in scenarios where classical procedures are needed to be embedded into quantum circuits, such as QROM implementation and quantum algorithm design.

We construct an exact

n

-bit quantum adder with

O(n)

gates and

O(\log n)

depth that requires no ancillary qubits. The circuit uses only

X

, CNOT, and Toffoli gates under all-to-all connectivity and is classically reversible. Our construction accelerates the controlled ladder underlying addition. Grouping the data into blocks and use existing control qubits as conditional workspace gives a recursive construction with

O(n\log\log n)

gates and

O(\log n)

depth. We then coordinate inter-block propagation via two short-path forest operations to cut the per-block workspace requirement, yielding a nonrecursive implementation with

O(n)

gates. Both the gate count and circuit depth are asymptotically optimal.

\Theta (\log {(n)}^{3})

Θ ( log ( n ) 3 ) , an approximating one without ancilla qubits with a circuit depth

{{{{{{{\mathcal{O}}}}}}}}(\log {(n)}^{3}\log (1/\epsilon ))

O ( log ( n ) 3 log ( 1 / ϵ ) ) 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 ))

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.