Source-linked AI summary
Factoring using 2n+2 qubits with Toffoli based modular multiplication
Thomas Häner, Martin Roetteler, Krysta M. Svore
TL;DR
The paper addresses space-efficient implementations of Shor’s algorithm that avoid rotation-synthesis overhead and support circuit testing. It uses Toffoli-based modular multiplication built from a dirty-ancilla constant-adder, achieving 2n+2 qubits with O(n^3) depth and O(n^3 log(n)) gate count.
Problem
Space-optimized Shor implementations still face rotation-synthesis overhead and challenges in testing logical and hardware circuits.
Method
The paper constructs a purely Toffoli-based modular multiplication circuit from an in-place constant-adder using borrowed dirty ancilla qubits.
Results
The implementation uses 2n+2 qubits, with circuit depth O(n^3), overall gate count O(n^3 log(n)), and Toffoli count TShor(n) = 64n^3 log2 n + O(n^3).
Takeaways & Limitations
Avoiding rotation synthesis enables classical simulation, testing, and localization of faults in the logical circuit and quantum hardware implementation.
Takeaways & Limitations
Fault localization requires an initial sample set that triggers every fault, and reducing the circuit size to O(n^3) without more qubits remains open.
Abstract
from arXiv · showhide
We describe an implementation of Shor's quantum algorithm to factor n-bit integers using only 2n+2 qubits. In contrast to previous space-optimized implementations, ours features a purely Toffoli based modular multiplication circuit. The circuit depth and the overall gate count are in O(n^3) and O(n^3 log(n)), respectively. We thus achieve the same space and time costs as Takahashi et al., while using a purely classical modular multiplication circuit. As a consequence, our approach evades most of the cost overheads originating from rotation synthesis and enables testing and localization of faults in both, the logical level circuit and an actual quantum hardware implementation. Our new (in-place) constant-adder, which is used to construct the modular multiplication circuit, uses only dirty ancilla qubits and features a circuit size and depth in O(n log(n)) and O(n), respectively.
1 Introduction
The paper targets a space-efficient implementation of Shor’s algorithm using 2n+2 qubits while replacing Fourier-based modular multiplication with Toffoli-based arithmetic. Its constant-adder uses borrowed dirty ancillas, supporting efficient construction, testing, and fault localization.
- Motivation and contribution: 2n+2 qubits are sufficient for the space-optimized implementation of Shor’s algorithm described by the paper.This matches the lowest-qubit implementation discussed for factoring n-bit integers.
- Motivation and contribution: The implementation replaces Fourier-based modular multiplication with a Toffoli-based circuit to avoid most single-qubit rotation-synthesis overheads.Toffoli networks can be efficiently simulated, debugged, and decomposed exactly into Clifford and T gates.
- Arithmetic construction: The constant-adder maps |a⟩ to |a + c⟩ for an arbitrary n-bit input while ignoring the final carry.It is used as the basic arithmetic component for constructing modular multiplication.
- Arithmetic construction: Dirty ancillas provide scratch space even when initially arbitrary or entangled, and the circuits return them to their original states.This borrowing strategy is the paper’s main technical innovation for reducing qubit requirements.
- Arithmetic construction: The adder requires O(n log n) Toffoli gates and has depth O(n), while repeated conditional modular additions implement the modular multiplication.The modular exponentiation mapping uses 2n conditional modular multiplications, each decomposed into n doubly controlled modular additions.
2 Toffoli based in-place addition
The paper constructs a Toffoli-based in-place constant adder using borrowed dirty ancillae, restoring them to their initial states while retaining the result bit. Recursive carry and incrementer constructions provide O(n log n) size and O(n) depth, with parallelization reducing depth using available dirty qubits.
- Carry construction: Borrowed dirty qubits store carry information through toggling and are restored, while the highest result bit remains computed.The carry construction uses toggles because dirty ancilla states cannot be directly determined or measured.
- Carry construction: For c = 11 = 1011_2, gates controlled by the zero bit c_2 are removed, and an optimization eliminates g_0.The example applies the constant-dependent gate selection and removes one borrowed qubit.
- Serial implementation: The recursive adder combines a CARRY operation on x_L with an incrementer on x_H, achieving O(n log n) size using one clean ancilla in the basic construction.The carry from the low bits is written into the ancilla and then handled by incrementing the high bits.
- Serial implementation: With a dirty ancilla, the incrementer is run twice with a conditional inversion so the unknown ancilla state is left unchanged.At the lowest recursion level, one-bit additions reduce to NOT gates when the corresponding constant bit is one.
- Serial implementation: The serial implementation reuses borrowed ancillae and has a recursively derived Toffoli count, while controlled addition requires controlling only the final CNOT gates.The construction explicitly accounts for carry and incrementer costs in the recursion.
- Parallel / Lower-depth version: Parallel carry computation uses borrowed qubits from the x-register, reducing the addition depth to O(n) during modular multiplication.The modular-multiplication layout makes n qubits of the x-register available as dirty ancillae.
3 Modular multiplication
The modular multiplier is built from modular additions selected by the bits of the multiplier, using a comparator-based modular-adder construction and an uncompute procedure to maintain the qubit budget.
- Modular multiplication: Repeated addition and shift decomposes modular multiplication into modular additions of (a2^i) mod N conditioned on multiplier bits x_i.The binary expansion x_{n-1}, ..., x_0 determines which modular additions are applied.
- Register uncomputation: The uncompute method swaps the two registers and applies a subtraction-based modular multiplication using the inverse a^-1 modulo N.This removes the computed result while preserving the constant total register count.
- Modular addition: The modular adder compares b with N − a, then conditionally adds a or a − N and resets the comparison indicator.The comparison can be implemented with the paper’s carry circuit, and controlled modular addition requires controlling the comparator’s final CNOT gates.
- Register uncomputation: The complete modular-addition construction requires 2n + 1 qubits: two n-qubit registers and one additional qubit.This is the register cost stated for the modular addition procedure.
4 Implementation and simulation results
The implementation realizes controlled modular multiplication for Shor’s algorithm with Toffoli-based constructions, and simulations confirm the expected Toffoli-count scaling. The resulting full algorithm has an overall Toffoli count of 64n^3 log2 n + O(n^3).
- The controlled modular multiplier implements modular exponentiation through modular multiplications by constants conditioned on the bits x_i.The constants are ã_i = a^2^i mod N, and the multiplication uses repeated controlled modular additions.
- The construction adds controls to comparator gates rather than conditioning the innermost adders, using idle garbage qubits to implement multi-controlled operations.There are n idle qubits available during controlled addition or subtraction.
- The circuits were implemented in LIQUi|⟩ and simulated for inputs of up to 8,192-bit numbers.The simulator was extended to support large-scale reversible Toffoli-circuit simulations.
- The modular-multiplier Toffoli scaling agrees with the expected form, with each compute or uncompute circuit using n doubly controlled modular additions.The modular addition uses two controlled adders with T_add(n) = 8n log2 n + O(n).
- 64n^3 log2 n + O(n^3) is the overall Toffoli count for a complete run of Shor’s algorithm.This follows because 2n modular multiplications are required.
5 Advantages of Toffoli circuits
Toffoli-based networks avoid the synthesis overhead associated with approximate-QFT rotations and support direct testing and fault localization. Their computational-basis behavior makes debugging possible in ways that QFT-based addition does not support.
- 5.1 Single-qubit rotation gate synthesis: Rotation synthesis introduces Θ(log 1/ε) gate growth, where ε is the target synthesis precision.This overhead applies when arbitrary rotations are decomposed into a discrete universal gate set.
- 5.1 Single-qubit rotation gate synthesis: Previous space-efficient circuits have overall gate count Θ(n^3 log2 n) and depth Θ(n^3 log n) because approximate-QFT angles require synthesis.The approximation cutoff produces small Fourier angles whose precision drives the synthesis cost.
- 5.1 Single-qubit rotation gate synthesis: Toffoli networks avoid synthesis overhead, leaving the proposed circuit with gate count Θ(n^3 log n) and depth Θ(n^3).Toffoli gates decompose exactly into Clifford and T gates, while semi-classical inverse-QFT rotations do not change the asymptotic scaling.
- 5.2 Design for testability: Toffoli networks can be debugged on quantum hardware and faults localized by binary search when the initial basis-state sample triggers every fault.The method covers missing-gate faults and computational-basis errors such as bit flips.
- 5.2 Design for testability: QFT-based addition does not permit the same debugging approach because intermediate states may be superpositions of exponentially many basis states.The contrast concerns hardware-level testing and fault localization of the logical network.
6 Summary and Outlook
The paper presents a 2n + 2-qubit Shor implementation built from a Toffoli-based in-place adder using dirty ancillas. It identifies a linear-time constant-adder without Θ(n) clean ancillas as an open direction for reducing circuit size.
- The implementation uses 2n + 2 qubits, has size O(n^3 log n), and has depth O(n^3).Its modular multiplication circuit consists only of Toffoli and Clifford gates.
- The constant-adder performs O(n log n) operations using between 1 and n dirty ancillas borrowed from idle parts of the computation.Borrowed ancillas may start in arbitrary states but are returned to those states after use.
- A linear-time constant-adder without Θ(n) clean ancillas could reduce the circuit size to O(n^3) without increasing the total qubit count to 3n + 2.The paper presents this as an open problem rather than a achieved result.