Source-linked AI summary
Shor's algorithm on a nearest-neighbor machine
Samuel A. Kutin
TL;DR
Nearest-neighbor implementations of Shor’s algorithm require efficient exponentiation under linear connectivity. The paper develops nested-add circuits using approximate modular multiplication and compares a transform-adder design with a reversible-classical alternative. The main design achieves linear width and quadratic depth, while the alternative avoids small controlled rotations at O(n^2 log n) depth.
Problem
Nearest-neighbor Shor circuits previously required either O(n^3) depth or superlinear width, while transform adders may require costly small controlled rotations.
Source: §1 · p. 1Method
Results
Takeaways & Limitations
The paper provides two nearest-neighbor implementation paths for Shor’s algorithm, trading lower asymptotic depth against avoidance of small controlled rotations.
Source: §1 · p. 1The analysis assumes unit cost for adjacent interactions, and the authors do not know which circuit version will ultimately be cheaper to implement.
Source: §1 · p. 1
Abstract
from arXiv · showhide
We give a new ``nested adds'' circuit for implementing Shor's algorithm in linear width and quadratic depth on a nearest-neighbor machine. Our circuit combines Draper's transform adder with approximation ideas of Zalka. The transform adder requires small controlled rotations. We also give another version, with slightly larger depth, using only reversible classical gates. We do not know which version will ultimately be cheaper to implement.
1 Introduction
The paper introduces a nearest-neighbor exponentiation circuit for Shor’s algorithm that achieves linear width and quadratic depth, improving on prior nearest-neighbor constructions. It combines an approximate multiplier based on Zalka’s idea with a practical alternative that avoids small controlled rotations at greater depth.
1 Introduction
- O(n) width and O(n^2) depth replace prior nearest-neighbor exponentiation costs of either O(n^3) depth or superlinear width.The construction combines with a nearest-neighbor QFT to yield a Shor factorization circuit.Source: §1 · p. 1
- Earlier nearest-neighbor work modified Beauregard’s transform-adder circuit without changing its dominant size or depth terms, while general-architecture depth-reduction techniques often do not transfer.The prior circuit used 2n + O(1) qubits but had cubic depth dominated by Θ(n^2) transform-adder applications.Source: §1 · p. 1
- An approximate controlled modular multiplier has linear width and linear depth by organizing O(n) additions around only a constant number of large QFTs.This applies Zalka’s approximation idea and yields the paper’s main exponentiation construction.Source: §1 · p. 1
- The transform-adder construction assumes unit cost for adjacent interactions, but its small controlled rotations may be expensive in practice.Van Meter questioned the practical usefulness of transform adders under error-correction requirements.Source: §1 · p. 1
- A reversible-classical version avoids small rotations but increases depth to O(n^2 log n), matching Van Meter’s asymptotic depth while retaining linear width.The paper notes that it is unknown which implementation will ultimately be cheaper.Source: §1 · p. 1
- Zalka [Zal06] independently identified framing multiple additions with one QFT but did not develop the details or nearest-neighbor application.The paper applies the related approximation idea to construct its multiplier.Source: §1 · p. 1
2 Preliminaries
The preliminaries reduce nearest-neighbor modular multiplication to controlled additions, then combine Zalka’s approximation, Draper’s transform adder, and pseudo-Toffoli-based data movement.
2.1 Approximate Modular Multiplication
- With high probability, the approximate quotient q̂ equals q after using only ℓ0 = O(log n) high bits of each xi.The quotient estimate is computed in depth O(log^2 n).Source: §2.1 · p. 2
- The resulting controlled modular multiplication costs about n controlled additions, with quotient computation, correction, and erasure contributing lower-order terms.The correction subtracts q̂m through O(log^2 n)-depth controlled additions.Source: §2.1 · p. 2
2.2 The Transform Adder
- The transform adder adds v to u by independently applying controlled phase rotations in the Fourier basis, followed by an inverse QFT.The encoded state |φ(u)⟩ is unentangled, and each bit receives a Z-rotation determined by v.Source: §2.2 · p. 3
- The circuit reduces the number of QFTs in modular exponentiation from Θ(n^2) for a naive design to O(n).Nearest-neighbor QFT implementations use swaps after controlled rotations, and the circuit may approximate the QFT by omitting small rotations.Source: §2.2 · p. 3
2.3 Pseudo-Toffolis and Controlled Swaps
- Pseudo-Toffoli cascades reduce depth from 2k to k, but introduce a phase change on |011⟩ that is acceptable only under stated conditions.The phase side effect is harmless when the computation is later undone or the affected input is forbidden.Source: §2.3 · pp. 3–4
- When one register is initialized to zero, a controlled swap can be implemented with a pseudo-Toffoli cascade of depth 2n + 2 without phase shifts.The known-zero targets prevent the phase-changing case.Source: §2.3 · p. 4, Figure 3 · p. 4
3 Nested Adds
The “nested adds” construction combines transform-addition and approximation to build nearest-neighbor modular multiplication and exponentiation with linear width and quadratic depth.
3 Nested Adds
- The main construction achieves nearest-neighbor exponentiation with width O(n) and depth O(n^2), extending the nested-adds multiplier into Shor’s algorithm.Source: §3 · p. 4
3.1 Nested Controlled Addition
- The repeated controlled adder nests QFT operations with controlled swaps and rotations, reducing its depth to 6n −4.Assuming constant initial data allows the initial QFT to be replaced by one time-slice, reducing depth further to 4n −1.Source: §3.1 · pp. 4–5
3.2 Nested Controlled Modular Addition
- The modular-adder circuit computes an approximate quotient, subtracts multiples of m, and returns the modular result with width 2n + ℓ+ O(1).Its quotient-processing depth is determined by summing QFT and movement costs over the quotient bits.Source: §3.2 · pp. 5–6
3.3 Controlled Modular Multiplication
- The controlled in-place modular multiplier preserves b when c = 0 and produces ab in B when c = 1, with depth 5n^2 + O(n log n).Overlapping the red and blue portions reduces the second-order depth term from 8(2ℓ−log2 n) log2 n to 6(2ℓ−log2 n) log2 n.Source: §3.3 · p. 6
3.4 Exponentiation
- Overlapping controlled swaps between rounds reduces each exponentiation round to 9n + O(log^2 n), yielding total depth 10n^3 + O(n^2 log n).The exponentiation repeatedly applies the modular multiplier while alternating the circuit orientation.Source: §3.4 · p. 8
3.5 Error Analysis
- Choosing ℓ0 = 2 log2 n + O(1) controls the approximation error under the random-addend analysis, while randomizing z addresses concerns about that assumption.The additional nonmodular subtraction of z requires t = log2 n + O(1), increasing ℓ0 to 3 log2 n + O(1) and ℓ to 4 log2 n + O(1).Source: §3.5 · p. 8
4 A Classical Version
This section develops a reversible classical approximate exponentiation circuit that avoids QFTs and achieves nearest-neighbor depth O(n^2 log n), with size O(n^3).
4 A Classical Version
- O(n^2 log n) depth is achieved by a reversible classical approximate exponentiation circuit with O(n^3) size.The exact depth constant depends on block parameters ℓ and t and on the ripple-carry implementation.Source: §4 · p. 9
- The construction retains repeated multiplication and addition, using nested controlled additions to obtain amortized depth O(log n) per addition on nearest-neighbor hardware.Controlled addition cannot be performed in sublinear depth on this architecture, motivating the nested organization.Source: §4 · p. 9
- The classical variant partitions registers into t-bit blocks with t = O(log n), performs parallel block additions, and tracks high bits to propagate carries between blocks.Correctness requires that no carry propagate through an entire block and that the recorded high bits be correct.Source: §4 · p. 9
- Ripple-carry adders implement the block operations, requiring 2k extra bits for high bits and scratch, while the Takahashi–Kunihiro adder is unusable on nearest-neighbor machines.Pseudo-Toffoli gates can reduce depth while preserving correction of the relevant phase errors.Source: §4 · p. 9
- Its modular-multiplication error analysis gives probability O(n^3 2^-t) that some high bit is wrong, so t = O(log n) reduces this probability to a small constant.The circuit performs O(n^3) controlled additions of size t.Source: §4 · p. 9
5 General Architectures
For general architectures, the nested-adds multiplier can be simplified by parallel swaps, removing mesh operations, and approximating QFTs, yielding explicit depth, width, and size bounds.
5 General Architectures
- Controlled swaps can be reduced to logarithmic depth by fanning the control bit into an empty n-bit register and performing n swaps in parallel.The control is then fanned back in.Source: §5 · p. 10
- Removing mesh and register-swap operations reduces depth by about n and size by about 2n^2.These operations are unnecessary without the nearest-neighbor restriction.Source: §5 · p. 10
- Approximating the QFT reduces each transform's size from about n^2/2 to O(n log n) without improving depth.The depth remains unchanged under this approximation.Source: §5 · p. 10
- 12n^2 + 60n log_2^2 n + O(n log n) is the resulting exponentiation depth after choosing ℓ = 3 log_2 n + O(1).The corresponding width is 3n + 6 log_2 n + O(1), and the size is 4n^3 + O(n^2 log n).Source: §5 · p. 10
- The general-architecture multiplier has depth 6n + 6(2ℓ − log_2 n) log_2 n + O(log n), width 3n + 2ℓ + 1, and size 2n^2 + O(n log n).These bounds follow after parallelizing controlled swaps, removing mesh operations, and approximating QFTs.Source: §5 · p. 10