Source-linked AI summary
Quantum Addition Circuits and Unbounded Fan-Out
Yasuhiro Takahashi, Seiichiro Tani, Noboru Kunihiro
TL;DR
The paper addresses how to construct quantum adders with improved depth, size, and ancillary-qubit complexity, especially when qubit count is constrained. It develops ripple-carry and carry-lookahead constructions, with modified versions using short unbounded fan-out gates. The resulting circuits include O(log n)-depth and O(log*n)-depth adders with O(n) size and sublinear ancillary qubits, and are applied to Shor’s discrete logarithm algorithm.
Problem
The paper studies quantum addition circuits with better size, depth, and qubit complexity, treating qubit count as primary because realizing computers with many qubits seems difficult.
Method
The paper combines a no-ancilla ripple-carry adder with carry-lookahead and quantumized classical addition circuits, optionally using bounded-length unbounded fan-out gates.
Results
O(log n/log log n)-depth O(n)-size addition with o(n) ancillary qubits is achieved using unbounded fan-out gates of length O(log n).
Takeaways & Limitations
The constructions provide efficient quantum adders across different depth–ancilla trade-offs and support efficient circuits for Shor’s discrete logarithm algorithm.
Takeaways & Limitations
The paper leaves open whether an O(log n)-depth O(n)-size adder with O(1) ancillary qubits can be constructed.
Abstract
from arXiv · showhide
We first show how to construct an O(n)-depth O(n)-size quantum circuit for addition of two n-bit binary numbers with no ancillary qubits. The exact size is 7n-6, which is smaller than that of any other quantum circuit ever constructed for addition with no ancillary qubits. Using the circuit, we then propose a method for constructing an O(d(n))-depth O(n)-size quantum circuit for addition with O(n/d(n)) ancillary qubits for any d(n)=Ω(log n). If we are allowed to use unbounded fan-out gates with length O(n^c) for an arbitrary small positive constant c, we can modify the method and construct an O(e(n))-depth O(n)-size circuit with o(n) ancillary qubits for any e(n)=Ω(log* n). In particular, these methods yield efficient circuits with depth O(log n) and with depth O(log* n), respectively. We apply our circuits to constructing efficient quantum circuits for Shor's discrete logarithm algorithm.
1 Introduction
The paper addresses quantum addition circuits that balance depth, size, and qubit count, emphasizing qubit reduction as a practical concern. It presents a flexible construction spanning no-ancilla, logarithmic-depth, and sublogarithmic-depth regimes, and applies the circuits to Shor’s discrete logarithm algorithm.
- 1 Introduction: Qubit count is treated as a primary concern because realizing quantum computers with many qubits seems difficult.The paper contrasts qubit count with size and depth, which roughly correspond to memory and computation time, respectively.
- 1 Introduction: An O(n)-depth O(n)-size adder uses no ancillary qubits and has exact size 7n−6.The circuit is based on the ripple-carry approach and can be used directly on a linear nearest neighbor architecture.
- 1 Introduction: For any d(n) = Ω(log n), the method constructs an O(d(n))-depth O(n)-size adder with O(n/d(n)) ancillary qubits.Setting d(n) = log n gives O(log n) depth and O(n/log n) ancillary qubits; setting d(n) = n favors qubit efficiency.
- 1 Introduction: With unbounded fan-out gates of length O(n^ε), the modified method achieves O(e(n)) depth, O(n) size, and O(n log**n/e(n)) ancillary qubits for e(n) = Ω(log*n).For e(n) = log*n, this becomes O(log*n) depth with o(n) ancillary qubits.
- 1 Introduction: Fan-out gates of length O(log n) suffice for an O(log n/log log n)-depth O(n)-size circuit with o(n) ancillary qubits.The paper states that this sublogarithmic-depth circuit cannot be constructed using only bounded-qubit gates or classical bounded-fan-in and unbounded-fan-out gates.
- 1 Introduction: The addition circuits are used to construct efficient quantum circuits for Shor’s discrete logarithm algorithm over elliptic curves over GF(p).Replacing the addition component in Proos et al.’s circuit reduces ancillary qubits without asymptotically increasing original depth or size, and o(n) ancillas reduce depth asymptotically.
2 Circuit with Depth O(n)
The section develops a ripple-carry quantum adder that uses no ancillary qubits by storing carry information in existing input locations. Its six-step construction achieves linear depth and size, supports linear nearest-neighbor architectures, and improves on prior no-ancilla circuits in size.
- Ripple-Carry Approach: The circuit defines ADD_n for two n-bit inputs and computes carries sequentially with the ripple-carry approach.Carry c1 is computed from a0, b0, and c0, then each subsequent carry uses the preceding carry.
- Ripple-Carry Approach: The majority function is MAJ(a, b, c) = ab ⊕bc ⊕ca, and the sum bits satisfy s_i = a_i ⊕b_i ⊕c_i.The construction computes carry bits through MAJ and then derives each sum bit from the corresponding inputs and carry.
- Our Circuit: The method stores c_i in the qubit initially holding a_i and c_n in the qubit initially holding z, avoiding ancillary qubits.It divides the MAJ operation into CNOT and Toffoli parts so carry information can be propagated through existing locations.
- Our Circuit: The six-step circuit uses CNOT and Toffoli gates to transform input locations so A_i retains a_i, B_i stores s_i, and A_n stores z ⊕s_n.The construction applies CNOTs and Toffoli gates in a forward and reverse pattern to compute and uncompute the required intermediate information.
- Complexity Analysis: 7n−6 gates give the circuit exact linear size, while its depth is O(n) and it uses no ancillary qubits.The circuit’s gate counts are analyzed step by step, and the paper compares its size favorably with prior no-ancilla adders.
- Complexity Analysis: The circuit can be used directly on a linear nearest-neighbor architecture without increasing size or depth asymptotically.This applies when the input and output bits are arranged in an interleaved manner.
3 General Method
The method combines ripple-carry and carry-lookahead techniques by partitioning inputs into blocks, computing block generate/propagate information, propagating carries, and then producing the sum. This yields O(d(n))-depth, O(n)-size addition circuits using O(n/d(n)) ancillary qubits for d(n)=Ω(log n).
- Motivation: Ripple-carry reduces ancillary-qubit use but has large depth, whereas carry-lookahead reduces depth but requires many qubits.
- 3.1 Combination Method: The combination method divides each n-bit input into n/k blocks of length k and computes block generate and propagate values before carry propagation.
- 3.1 Combination Method: O(n/log n) ancillary qubits, O(log n) depth, and O(n) size are achieved by the previous combination method.
- 3.2 Our Method: The proposed circuit divides inputs into blocks of length d(n), uses CARRYlog d(n)+1, and achieves O(n/d(n)) ancillary qubits with O(d(n)) depth and O(n) size.
- 3.2 Our Method: The INITw and SUMw gates compute the intermediate generate, propagate, and sum-related values without ancillary qubits, each with O(w) depth and size.
4.1 Chandra et al.’s Classical Circuit
The classical circuit of Chandra et al. generalizes carry-lookahead using unbounded fan-in and fan-out, achieving constant depth with size O(m log* * m).
- Chandra et al.’s circuit generalizes carry-lookahead with unbounded fan-in AND/OR gates and classical unbounded fan-out gates.
- The circuit for two m-bit numbers has O(1) depth and O(m log* * m) size.
4.2 Simple Case
The paper transforms Chandra et al.’s classical circuit into a quantum carry-lookahead circuit using generalized Toffoli operations and bounded-length unbounded fan-out gates.
- The classical circuit is transformed into a quantum version by replacing unbounded fan-in operations with quantum T_t gates and using unbounded fan-out gates.
- The resulting GCLAm circuit uses O(m log* * m) ancillary qubits and size, with depth O(log*(m log* * m)).
- Using GCLAm as CARRY_l yields a whole circuit with O(n log* * n/e(n))=o(n) ancillary qubits, O(e(n)) depth, and O(n) size.
4.3 Reduction of the Length of an Unbounded Fan-Out Gate
The paper reduces the required fan-out length by recursively simulating long fan-out and T_t operations, preserving linear size while adjusting depth according to the available fan-out length.
- Long unbounded fan-out gates can be simulated without ancillary qubits using depth O(log t/log f(n)+1) and size O(t/f(n)+1).
- The modified T_t construction has depth O(log t/log f(n)+log* t) and O(t) size with O(t) ancillary qubits.
- With fan-out length f(n), the GCLAm circuit has depth O(log m/log f(n)+log*(m log* *m)) and O(m log* *m) size.
- Setting f(n)=n^ε gives O(e(n))-depth, O(n)-size addition with O(n log* *n/e(n))=o(n) ancillary qubits.
- For f(n)=log n, the construction achieves O(log n/log log n) depth, O(n) size, and O(n log* *n log log n/log n) ancillary qubits.
5 Application
The paper applies its addition circuits to Shor’s discrete logarithm algorithm for elliptic curves over GF(p), reducing qubit use while preserving asymptotic depth and size. Adding sublinear ancillary qubits enables further depth reductions with explicitly quantified resource bounds.
- Replacing Proos et al.’s ADD_n circuit eliminates its n ancillary qubits during addition, producing a circuit using about 4n qubits.
- The resulting circuit has asymptotically the same depth and size as Proos et al.’s original circuit, whose overall bounds are O(n^3).The precise ADD_n depth and size cannot be compared because Proos et al. do not specify them precisely.
- O(n/d(n)) ancillary qubits yield an O(n^2d(n))-depth O(n^3)-size discrete logarithm circuit using 4n + O(n/d(n)) qubits for d(n) = Ω(log n).
- With unbounded fan-out gates of length O(n^ε), o(n) ancillary qubits yield an O(n^2e(n))-depth O(n^3)-size circuit using 4n + o(n) qubits for e(n) = Ω(log* n).
6 Conclusions and Future Work
The paper concludes that its addition circuits achieve low size and ancillary-qubit use across several depth regimes, and applies them to efficient quantum circuits for Shor’s discrete logarithm algorithm. It identifies further open questions about simultaneously improving depth, size, ancillary qubits, and fan-out assumptions.
- The paper constructs an O(n)-depth O(n)-size circuit for ADD_n with no ancillary qubits and size smaller than any previously constructed such circuit.
- With unbounded fan-out gates of length O(n^ε), the method achieves O(log* n) depth, O(n) size, and o(n) ancillary qubits for ADD_n.
- The circuits are applied to constructing efficient quantum circuits for Shor’s discrete logarithm algorithm.
- Open challenges include O(log n)-depth O(n)-size ADD_n with O(1) ancillary qubits and O(1)-depth O(n)-size ADD_n with O(n) ancillary qubits using unbounded fan-out.