arXiv:2609.26591
A New Method For Manipulating Circuits, Application To Quantum Adders
William Schober, Scott Wesley
Abstract
We use a new technique for manipulating controlled quantum circuits to convert between two distinct types of quantum adders, one based on the Quantum Fourier Transform and the other based on the Ripple-Carry technique from classical reversible logic. This conversion takes the form of an explicit gate-level transpilation. We also present a new quantum adder with a natural interpretation as a kind of Carry-Lookahead adder that uses no ancillas.
AI Summary
The paper addresses how to transform a quantum Fourier transform (QFT) adder into a classical reversible ripple-carry adder by explicit circuit rewrites, rather than merely showing that both implement addition. It uses hierarchical quantum circuits, a previously introduced language with circuit powers and a control product that generalizes controlled unitaries. For in-place modular addition $\lvert a\rangle\lvert b\rangle\mapsto\lvert a\rangle\lvert a+b\bmod 2^n\rangle$, the construction connects the QFT-based circuit over Hadamards and controlled phase rotations to a specified seven-stage ripple-carry circuit over $\{X,\mathrm{CNOT},\mathrm{Toffoli}\}$. The QFT adder is first expressed recursively with a prefix and suffix. A sequence of $n$ merging steps reorganizes fractional circuit powers into carry-generating and carry-propagating controls; commuting the suffix through the remaining adder cancels the fractional powers. Further conjugation and gate-pushing identities recover the ripple-carry stages. Equivalence is established inductively for arbitrary register size. An intermediate circuit is interpreted as an ancilla-free carry-lookahead adder. It computes sum bits from most to least significant, using diagonal Hermitian controls that encode whether lower-order inputs generate a carry, without storing the intermediate carry bits. However, the stated straightforward compilation into classical reversible gates has exponential depth. No depth-efficient implementation or resource advantage for this intermediate construction is established; finding such an implementation remains an expectation rather than a result.
Central claim may not hold: The explicitly specified seven-stage ripple-carry circuit maps the two-bit input |01>|01> to |11>|00> rather than |01>|10>, contradicting its claimed implementation of addition and equivalence to the QFT adder.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- Typos and better exposition in section 3.1