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

Efficient Quantum Circuit Decompositions via Intermediate Qudits

Jonathan M. Baker, Casey Duckering, Frederic T. Chong

Many quantum algorithms make use of ancilla, additional qubits used to store temporary information during computation, to reduce the total execution time. Quantum computers will be resource-constrained for years to come so reducing ancilla requirements is crucial. In this work, we give a method to generate ancilia out of idle qubits by placing some in higher-value states, called qudits. We show how to take a circuit with many O(n) ancilla and design an ancilla-free circuit with the same asymptotic depth. Using this, we give a circuit construction for an in-place adder and a constant adder both with O(log n) depth using temporary qudits and no ancilla.Many quantum algorithms make use of ancilla, additional qubits used to store temporary information during computation, to reduce the total execution time. Quantum computers will be resource-constrained for years to come so reducing ancilla requirements is crucial. In this work, we give a method to generate ancilia out of idle qubits by placing some in higher-value states, called qudits. We show how to take a circuit with many O(n) ancilla and design an ancilla-free circuit with the same asymptotic depth. Using this, we give a circuit construction for an in-place adder and a constant adder both with O(log n) depth using temporary qudits and no ancilla.

arXiv:2002.10592IEEE International Symposium on Multiple-Valued Logic (ISMVL)Nov 1, 202019 citations

Improved Quantum Circuits via Intermediate Qutrits

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

Quantum computation is traditionally expressed in terms of quantum bits, or qubits. In this work, we instead consider three-level qu trits . Past work with qutrits has demonstrated only constant factor improvements, owing to the log 2 (3) binary-to-ternary compression factor. We present a novel technique, intermediate qutrits, to achieve sublinear depth decompositions of the Generalized Toffoli and other arithmetic circuits using no additional ancilla—a significant improvement over linear depth for the best qubit-only equivalents. For example, our Generalized Toffoli construction features a 70× improvement in two-qudit gate count over a qubit-only decomposition. This results in circuit cost reductions for important algorithms like quantum neurons, Grover search, and even Shor’s algorithm. Using a previously developed simulator with near-term noise models, we demonstrate for these models over 90% mean reliability (fidelity) for the Toffoli construction, versus under 30% for the qubit-only baseline. For our other constructions, such as the Incrementer, the A + B adder and the +K adder, we demonstrate the power of intermediate qutrits in producing asymptotic depth improvements with no additional ancilla. Together, these results suggest qutrits offer a promising path toward scaling quantum computation.Quantum computation is traditionally expressed in terms of quantum bits, or qubits. In this work, we instead consider three-level qu trits . Past work with qutrits has demonstrated only constant factor improvements, owing to the log 2 (3) binary-to-ternary compression factor. We present a novel technique, intermediate qutrits, to achieve sublinear depth decompositions of the Generalized Toffoli and other arithmetic circuits using no additional ancilla—a significant improvement over linear depth for the best qubit-only equivalents. For example, our Generalized Toffoli construction features a 70× improvement in two-qudit gate count over a qubit-only decomposition. This results in circuit cost reductions for important algorithms like quantum neurons, Grover search, and even Shor’s algorithm. Using a previously developed simulator with near-term noise models, we demonstrate for these models over 90% mean reliability (fidelity) for the Toffoli construction, versus under 30% for the qubit-only baseline. For our other constructions, such as the Incrementer, the A + B adder and the +K adder, we demonstrate the power of intermediate qutrits in producing asymptotic depth improvements with no additional ancilla. Together, these results suggest qutrits offer a promising path toward scaling quantum computation.

ACM Transactions on Quantum ComputingOct 29, 202017 citations

Quantum adder circuits

Hafiz Md. Hasan Babu

Institute of Physics eBooksMay 1, 20200 citations

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.