PaperlayerView exact revision on arXiv

Source-linked AI summary

Approximate Quantum Fourier Transform with $O(n \log(n))$ T gates

Yunseong Nam, Yuan Su, Dmitri Maslov

arXiv:1803.04933v2quant-phcs.ET

TL;DR

The standard fully coherent fault-tolerant AQFT has T-count O(n log^2(n)). This paper uses measurements, feedforward, and a reusable special state for phase-gradient transformations to obtain O(n log(n)) T-count and report practical savings.

  • Problem

    The standard fault-tolerant implementation of fully coherent AQFT has T-count O(n log^2(n)), despite the QFT's use in algorithms including factoring and phase estimation.

    Source: §I · pp. 1–2

  • Method

    The construction uses measurements and feedforward and reuses a special quantum state to induce phase-gradient transformations in grouped controlled rotations.

    Source: §I · p. 2, §II · p. 3

  • Results

    O(n log(n)) T-count reduces the dependence on n from O(n log^2(n)) and moves the approximation-error dependence from the leading term into a lower-order additive term.

    Source: §V · p. 5, §VI · p. 5

  • Takeaways & Limitations

    The authors report practical T-count improvements by factors of 10 to 12 for n values expected in practical quantum-computer applications.

    Source: §VI · p. 5

Abstract

from arXiv · show

The ability to implement the Quantum Fourier Transform (QFT) efficiently on a quantum computer facilitates the advantages offered by a variety of fundamental quantum algorithms, such as those for integer factoring, computing discrete logarithm over Abelian groups, solving systems of linear equations, and phase estimation, to name a few. The standard fault-tolerant implementation of an $n$-qubit unitary QFT approximates the desired transformation by removing small-angle controlled rotations and synthesizing the remaining ones into Clifford+T gates, incurring the T-count complexity of $O(n \log^2(n))$. In this paper, we show how to obtain approximate QFT with the T-count of $O(n \log(n))$. Our approach relies on quantum circuits with measurements and feedforward, and on reusing a special quantum state that induces the phase gradient transformation. We report asymptotic analysis as well as concrete circuits, demonstrating significant advantages in both theory and practice.

I. INTRODUCTION

The QFT supports applications including factoring, discrete logarithms, and phase estimation. For fully coherent AQFT, the standard fault-tolerant approach has T-count O(n log^2(n)), while this paper targets O(n log(n)).

I. INTRODUCTION

  • The QFT supports factoring and discrete logarithms, phase estimation, quantum simulation, and other algorithms.The introduction describes QFT as extracting periodicity encoded in a quantum state's amplitudes.Source: §I · p. 1
  • Approximate QFT removes rotations below a threshold; prior work reports factoring 2048-digit numbers with about 5.3 · 10^4 controlled rotations at expected accuracy ≳99.992%.The passage also cites studies of AQFT robustness, approximation under errors, restricted architectures, and hardware-aware implementations.Source: §I · p. 1
  • The standard fully coherent fault-tolerant AQFT uses O(n log^2(n)) T gates, whereas this paper targets O(n log(n)), an O(log(n)) improvement.The introduction distinguishes this general case from the semiclassical AQFT, for which O(n log(n)) was already known.Source: §I · p. 2
  • The paper's implementation uses measurements and feedforward, and aims to retain practical advantages despite added circuit complexity.The motivation for reducing T count is that T gates are more costly than Clifford gates in fault-tolerant computation.Source: §I · pp. 1–2

II. MAIN RESULT

The construction groups AQFT controlled rotations into layers and maps them to phase-gradient transformations. A reusable special state and a b-bit adder implement those transformations within the fault-tolerant circuit.

II. MAIN RESULT

  • The AQFT uses O(nb) controlled-za gates with a values from 1/2 through 1/2^b, where b = ⌈log n⌉.The controlled-rotation sets are separated by Hadamard gates.Source: §II · p. 2
  • Each controlled-za rotation is mapped from a controlled operation to an uncontrolled z power using a measurement/feedforward construction.The construction combines Kitaev’s trick [2], Jones’s Toffoli-measurement construction [29], a relative-phase Toffoli gate, and circuit simplifications.Source: §II · pp. 2–3
  • The uncontrolled z rotations are grouped into a phase-gradient layer, implementable with a b-bit adder at cost 4b + O(1) T gates.The phase-gradient transformation was coined in [31], and its induction by an addition circuit was first reported in.Source: §II · p. 3, Figure 3 · p. 3
  • The state |ψb+1⟩ can be reused to induce phase-gradient transformations in all n−1 sets of controlled rotations.The full circuit schematic includes preparation of this special state.Source: §II · p. 3
  • For the za gate, the repeat-until-success circuit succeeds when the second qubit is measured as 0; otherwise, a z error occurs and can be reversed at zero cost in T-gate count.The expected repetitions until success are 2L/|rz|^2; compared with the simpler algorithm [35, 36], the RUS approach improves the T-gate count about 2.5-fold [33].Source: §II · p. 3

III. DETAILS OF THE IMPLEMENTATION

The implementation further optimizes controlled-p and controlled-t gates through direct circuits and gate cancellation. It also modifies phase-gradient operations to handle the remaining rotations in each layer.

III. DETAILS OF THE IMPLEMENTATION

  • Implementing controlled-p directly costs two CNOT gates and three T gates, including inverses.The construction also works when all Z-axis gates are replaced by their complex conjugates.Source: §III · p. 3, Figure 5 · p. 4
  • In the AQFT implementation, the neighboring controlled-t and controlled-p gate pair requires 7 T gates (5+3+3−2−2), with reductions from cancellations between adjacent T and T† gates.The controlled-z3/4 gate is implemented directly and costs 5 T gates.Source: §III · p. 3
  • The circuit schematic distinguishes operations before each adder, the adder itself, and operations through the in-circuit measurements.The special state is prepared for the full implementation, and the operations before each adder include Hadamards and relative-phase Toffoli gates.Source: Figure 4 · p. 4, §III · p. 4
  • For the remaining rotations, the partial gradient applies a phase to |k⟩ using |ψd+1,b+1⟩ when k < 2^(b−d).The truncated state omits its first d+1 qubits; with d = 2, one T gate is applied for each gradient operation.Source: §III · p. 4

IV. COMPARISONS TO PRIOR WORK

The comparison reports substantial T-count savings for the improved AQFT, while also accounting for its qubit and CNOT costs. It compares the construction with prior controlled-rotation and automated circuits under stated synthesis settings.

IV. COMPARISONS TO PRIOR WORK

  • The improved circuit’s T-count is fairly accurately approximated by 8n(b−1).The stated previous construction uses n+1 qubits.Source: §IV · p. 4
  • For n≤4096 and b=13, the improved construction uses a 10^-5 error target per z_a gate approximation, with total synthesis error below 1.1 × 10^-4.The corresponding previous construction uses a gate-synthesis error budget of about 10^-5/n per rotation.Source: §IV · p. 4
  • The resource comparison includes the improved implementation, circuits using a prior controlled-z_a construction, and an automatically optimized AQFT; both prior implementations use Gridsynth to synthesize z_a gates.The table reports qubit, CNOT, and T counts for AQFT circuits with b=13.Source: §IV · pp. 4–5, Table I · p. 5
  • For AQFT4096 at b=13, the implementation saves T-count by as much as a factor of 12; slight increases in nq and CNOT-gate counts are completely offset by T-count savings in the fault-tolerant regime.Source: §IV · p. 5

V. COMPLEXITY ANALYSIS

The complexity analysis gives a T-count for the AQFT construction and bounds its approximation error. In the stated effective-error regime, the count is O(n log n).

V. COMPLEXITY ANALYSIS

  • The AQFT T-count is 8n(b−1) + O(b log(b/ε)), with the additive term covering preparation of a special state using O(b) synthesized rotations.Each of roughly nb controlled-z_a gates uses four T gates for mapping and four more in the adder, with stated exceptions for two rotations.Source: §V · p. 5
  • For b=O(log(n/ε)), the ideal AQFT approximation has spectral-norm error O(ε), and combining AQFT and Clifford+T synthesis errors keeps total error O(ε).The circuit differs from the ideal AQFT only in preparation of the special state.Source: §V · p. 5
  • In the stated effective-error regime, the ε dependence can be dropped, yielding the claimed O(n log n) T-count.The passage identifies that regime as ε ≻ n/2^n.Source: §V · p. 5

VI. CONCLUSION

The conclusion reports a T-count improvement from O(n log^2(n)) to O(n log(n)), with the dependence on ε moved from the leading term to a lower-order additive term. It also reports practical T-count reductions of 10 to 12 times for application-scale n.

VI. CONCLUSION

  • O(n log^2(n)) to O(n log(n)): the construction reduces the T-count's dependence on n and moves ε dependence from the leading term to a lower-order additive term.The conclusion says the construction becomes more efficient relative to prior work as the desired approximation error decreases.Source: §VI · p. 5
  • 10 to 12 times: the implementation reduces T-count for n values expected in practical quantum-computing applications.The conclusion attributes the practical gains partly to constant-factor improvements not captured by the asymptotics.Source: §VI · p. 5
Loading 1803.04933v2…