PaperlayerView exact revision on arXiv

Source-linked AI summary

Fast parallel circuits for the quantum Fourier transform

Richard Cleve, John Watrous

arXiv:quant-ph/0006004v1quant-ph

TL;DR

Perfect-accuracy quantum gates seem physically implausible, making approximate QFT computation especially relevant. The paper constructs circuits with new approximation-depth bounds and applies them to factoring. The bounds are asymptotically optimal for a reasonable range of error values, and factoring lies in ZPP^BQNC.

  • Problem

    Perfect-accuracy quantum gates seem physically implausible, so approximate QFT computation is especially relevant.

    Source: §1 · p. 3

  • Method

    The paper constructs logarithmic-space-uniform quantum circuits approximating the QFT modulo 2^n.

    Source: §1 · p. 3

  • Results

    Approximate QFT depth is O(log n + log log(1/ε)), asymptotically optimal for a reasonable range of ε, and factoring is in ZPP^BQNC.

    Source: §1 · pp. 3–4

  • Takeaways & Limitations

    Factoring can use a polynomial-size, polylogarithmic-depth quantum circuit within the ZPP^BQNC framework.

    Source: §1 · p. 4

    The stated circuit convention assumes logarithmic-space uniformity; repeated doubling has O(log k log n) depth, too large for the paper’s purposes.

    Source: §1 · p. 3, §3.2 · p. 8

Abstract

from arXiv · show

We give new bounds on the circuit complexity of the quantum Fourier transform (QFT). We give an upper bound of O(log n + log log (1/epsilon)) on the circuit depth for computing an approximation of the QFT with respect to the modulus 2^n with error bounded by epsilon. Thus, even for exponentially small error, our circuits have depth O(log n). The best previous depth bound was O(n), even for approximations with constant error. Moreover, our circuits have size O(n log (n/epsilon)). We also give an upper bound of O(n (log n)^2 log log n) on the circuit size of the exact QFT modulo 2^n, for which the best previous bound was O(n^2). As an application of the above depth bound, we show that Shor's factoring algorithm may be based on quantum circuits with depth only O(log n) and polynomial-size, in combination with classical polynomial-time pre- and post-processing. In the language of computational complexity, this implies that factoring is in the complexity class ZPP^BQNC, where BQNC is the class of problems computable with bounded-error probability by quantum circuits with poly-logarithmic depth and polynomial size. Finally, we prove an Omega(log n) lower bound on the depth complexity of approximations of the QFT with constant error. This implies that the above upper bound is asymptotically optimal (for a reasonable range of values of epsilon).

1 Introduction and summary of results

The paper gives new depth and size bounds for approximate and exact QFT circuits, then applies the depth result to factoring and proves a lower bound for QFT approximations. It also explains why approximation and low circuit depth matter in quantum computing.

1 Introduction and summary of results

  • The QFT is central to Shor’s factoring and discrete-logarithm algorithms and also appears in extensions of Grover’s search technique.Source: §1 · p. 1
  • Approximation is emphasized because perfect-accuracy quantum gates seem physically implausible, although exact QFT computation remains mathematically interesting.Source: §1 · p. 3
  • O(log n + log log(1/ε)) depth and O(n log(n/ε)) size suffice to approximate the QFT modulo 2^n; earlier circuits had depth O(n).The approximation error is measured by Euclidean distance between the resulting states, and the circuit family is assumed logarithmic-space uniform.Source: §1 · p. 3
  • Theorem 1 defines precision ε as a bound on Euclidean distance for every pure input state, allowing the approximating operation to use ancilla qubits.The circuit family is assumed logarithmic-space uniformly generated unless otherwise stated.Source: §1 · p. 3
  • The approximation proof follows Kitaev’s approach, with efficiency improvements and a new parallel method for multiprecision phase estimation.The paper says depth is relevant because it corresponds informally to the time coherence must be preserved, and parallelization may help circuits operate in shorter-coherence systems.Source: §1 · p. 3
  • O(n(log n)^2 log log n) gates suffice for the exact QFT modulo 2^n, improving on the known O(n^2) size bound.The construction combines a nonstandard recursive description of the QFT with asymptotically fast multiplication.Source: §1 · pp. 2–3
  • Factoring n-bit integers can use an O(log n)-depth, polynomial-size quantum stage between polynomial-size classical pre- and post-processing stages.The paper states that this places factoring in ZPP^BQNC.Source: §1 · pp. 1, 4
  • Depth at least log n is required for one- and two-qubit circuits approximating the QFT with precision 1/10 or smaller, making the upper bound asymptotically optimal for a reasonable range of ε.The paper contrasts this with a related problem whose depth drops from log n to O(log log n) under approximation.Source: §1 · p. 4

2 Definitions and notation

The section defines the QFT as mapping computational basis states to Fourier basis states and introduces related state and phase computations. It also fixes binary-state notation and the gates used in the paper’s circuits.

2 Definitions and notation

  • For an n-bit modulus m, x ∈ Zm is identified with its binary representation, and |x⟩ is called a computational basis state.When m = 2^n, a Fourier basis state |ψx⟩ can be factored as a product of states.Source: §2 · p. 5
  • The QFT maps each computational basis state |x⟩ to its Fourier basis state |ψx⟩.This is the paper’s definition of the QFT for x ∈ Zm.Source: §2 · p. 5
  • A QFS maps |x⟩|0⟩ to |x⟩|ψx⟩, while a QFP maps |ψx⟩|0⟩ to |ψx⟩|x⟩, retaining the input in each mapping.The QFT can be computed by composing a QFS with the inverse of a QFP.Source: §2 · p. 5
  • The circuits use Hadamard, phase shift, and controlled-phase shift gates, with the phase parameter drawn from values of the form x/2^n.The passage states that this gate set is universal and can compose any classical reversible circuit.Source: §2 · p. 5

3 New depth bounds for the QFT

For modulus 2^n, the construction parallelizes phase estimation by preparing and copying Fourier states, then estimating their phases. The phase-estimation mapping has size O(n log(n/ε)) and depth O(log n + log log(1/ε)).

3.1 Parallel Fourier state computation and estimation

  • Exact preparation of all Fourier-state components has size O(n^2) and depth O(log n), with repeated input-qubit copies enabling the controlled phase shifts to run in parallel.Each component circuit has depth O(log n) and size O(n).Source: §3.1 · p. 7
  • Approximate Fourier-state preparation keeps only k = O(log(n/ε)) significant phase shifts, with size O(n log(n/ε)) and depth O(log log(n/ε)).The cutoff is chosen so the combined approximation has error O(ε).Source: §3.1 · p. 7

3.2 Copying a Fourier state in parallel

  • An exact Fourier-state copy circuit uses O(kn) size and O(log(kn)) depth to produce k copies from one.Its prefix-addition construction uses pairwise representations and a parallel prefix circuit.Source: §3.2 · pp. 7, 9

3.3 Estimating the phase of a Fourier state in parallel

  • Using the parallel prefix method, all values x_j = A_{l_j}A_{l_{j-1}}…A_{l_1}[2,1], for j = 1,…,n, can be computed by one circuit of size O(n) and depth O(log n), with matrix multiplication modulo 2.Source: §3.3 · p. 12
  • The phase-estimation mapping uses O(n log(n/ε)) size and O(log n + log log(1/ε)) depth.It uses k ∈ O(log(n/ε)) Fourier-state copies and converts measurements into a unitary operation with error O(ε).Source: §3.3 · p. 12

4 New size bounds for the QFT

The exact QFT circuit replaces a quadratic collection of controlled-phase gates in the recursive construction with a more efficient multiplication-based implementation. The resulting circuit has size O(n(log n)^2 log log n), depth O(n), and width O(n).

4 New size bounds for the QFT

  • The improved recursive construction sets m = ⌊n/2⌋ and implements its phase-coupling step using integer multiplication and one-qubit phase shifts.The step maps |x⟩|y⟩ to a state with phase e^(2πi/2^n)x·y while preserving |x⟩|y⟩.Source: §4 · p. 13
  • The standard generalized recursion's Step 2 uses (n − m)m two-qubit gates, approximately n^2/4, while the multiplication circuit has size O(n log n log log n).The reversible multiplication circuit maps |x⟩|y⟩|0^n⟩ to |x⟩|y⟩|x · y⟩.Source: §4 · p. 13
  • The exact QFT modulo 2^n has size O(n(log n)^2 log log n), depth O(n), and width O(n).The size follows from the recurrence for the recursive construction.Source: §4 · p. 13

5 Factoring via logarithmic-depth quantum circuits

The paper rearranges Shor’s factoring algorithm so its quantum circuit has logarithmic depth, using classical preprocessing and post-processing. Classical preprocessing supplies powers that let the modular exponentiation portion be parallelized.

5 Factoring via logarithmic-depth quantum circuits

  • Factoring can be arranged to use logarithmic-depth quantum circuits, but the method still requires polynomial-time classical preprocessing and post-processing.Those classical stages are not known to be parallelizable.Source: §5 · p. 13
  • The method parallelizes the quantum portion associated with modular exponentiation, then combines it with logarithmic-depth QFT circuits.Whether modular exponentiation can be parallelized without this classical preprocessing remains an open question addressed neither here nor by the paper’s result.Source: §5 · p. 13
  • Classical preprocessing computes powers of a modulo N, reducing quantum modular exponentiation to an iterated multiplication of the selected powers.The iterated product can be computed with O(log n) depth and size O(n^5(log n)^2) using the cited Boolean circuits.Source: §5 · p. 14

6 Lower bounds

The section proves an Ω(log n) depth lower bound for constant-error QFT approximations. Its argument uses the dependence of a high-order output qubit on all n input qubits.

6 Lower bounds

  • The same depth lower bound applies to quantum Fourier sampling because its output includes the Fourier state |ψx⟩.The passage states that this lower-bound proof applies to QFS computations as well as the QFT.Source: §6 · p. 15
  • A circuit approximating the inverse QFT to precision 1/10 needs depth at least log n, because its high-order output qubit must depend on every input qubit.A circuit of smaller depth leaves some input qubit outside that output qubit’s dependence, contradicting the required output behavior.Source: §6 · p. 15
  • Changing an input bit that a shallow circuit cannot affect yields states whose required high-order outputs are orthogonal, contradicting the circuit’s approximation guarantee.The proof compares Fourier states for z and z + 2^r, then uses a third state to bound the distance between the circuit outputs.Source: §6 · pp. 15–16
  • The lower-bound argument uses trace distance and a contradiction: the output states would have to be closer than the distance between orthogonal states permits.The proof concludes that the trace distance between |0⟩ and |1⟩ would be less than 1, which is impossible.Source: §6 · p. 16

7 Other moduli

This section discusses QFTs for non-power-of-two moduli, including an arbitrary-modulus approximation method and Shor’s mixed-radix method. The arbitrary-modulus method gives polylogarithmic depth, while the mixed-radix analysis yields worse size and/or depth bounds than the power-of-2 method.

7 Other moduli

  • The section also sketches parallelization of the QFT for arbitrary non-power-of-two moduli and Shor’s method for smooth moduli.Source: §7 · p. 16

7.1 Arbitrary moduli

  • For any modulus m, the arbitrary-modulus method gives an ε-approximate QFT with depth O(log n log log(1/ε)) and size polynomial in n + log(1/ε), where n = ⌈log m⌉.It uses a QFT modulo 2^k as a black box, with k = ⌊log m⌋ + O(1).Source: §7.1 · p. 17
  • The arbitrary-modulus construction creates and copies a Fourier state, applies inverse QFTs modulo 2^k, then takes the mode of rounded outcomes to recover x with high probability.The text says this works using a sufficiently large modulus m′ as a black box, without requiring m′ to be a power of 2.Source: §7.1 · p. 17
  • Some power-of-2 techniques, including three-two adders and approximating individual Fourier-basis qubits, do not seem to work for arbitrary moduli, yielding a slightly worse depth bound.The overall size bound increases as well, but remains polynomial.Source: §7.1 · p. 17

7.2 Shor’s “mixed-radix” QFT

  • Shor’s mixed-radix method factors m into pairwise relatively prime moduli, converts x to modular coordinates, performs independent QFTs, and converts back.The conversion operators can be parallelized to logarithmic depth when the component moduli are small.Source: §7.2 · p. 18
  • Using exact circuits of size m_j for the component QFTs gives linear depth; approximation approaches are available, but the mixed-radix method has worse size and/or depth bounds than the power-of-2 method.The discussed approximation options include Kitaev’s method and the arbitrary-modulus method.Source: §7.2 · p. 19

8 Conclusion

The conclusion identifies open questions about exact-QFT depth, optimizing the proposed circuits, and quantum parallel algorithms for problems not known to be classically parallelizable. It also notes that logarithmic-depth QFT raises the question of whether natural problems lie in BQNC but not NC or RNC.

8 Conclusion

  • The depth of an exact QFT remains open: the best known upper bound is linear in the number of input qubits, and the section asks whether logarithmic or polylogarithmic depth is possible.Source: §8 · p. 19
  • The authors expect significant circuit optimizations for interesting input sizes, including several hundred to a few thousand qubits.Their analyses focus on asymptotic bounds.Source: §8 · p. 19
  • The logarithmic-depth QFT motivates asking whether natural problems lie in BQNC but not NC or RNC, including gcd and modular arithmetic problems.The passage says polylogarithmic-depth, polynomial-size classical circuits are not known for the listed problems.Source: §8 · pp. 19–20
Loading quant-ph/0006004v1…