An approximate Fourier transform useful in quantum factoring

By Don Coppersmith. 2002

580 citations recorded by the source corpus.

We define an approximate version of the Fourier transform on $2^L$ elements, which is computationally attractive in a certain setting, and which may find application to the problem of factoring integers with a quantum computer as is currently under investigation by Peter Shor. (1994 IBM Internal Report)

View Paper: https://www.semanticscholar.org/paper/ea79fa165ea3689863231b12cecd399104052f4a

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Qudits and High-Dimensional Quantum Computing (2020, background): “Qudit QFT offers superior approximations where the magnitude of the error decreases exponentially with d and the smaller error bounds are smaller [165]; which outperforms the binary case [34].”
Dynamics of Loschmidt echoes and fidelity decay (2006, methodology): “We concentrate on the Quantum Fourier Transformation algorithm (QFT) [262,263] and shall consider its stability against static random perturbations.”
Quantum annealing for industry applications: introduction and review (2021, unknown): “In some cases this can even result in exponentially faster algorithms, such as Shor’s algorithm for factoring [163] and the quantum Fourier transform algorithm [39].”
Q#: Enabling Scalable Quantum Computing and Development with a High-level DSL (2018, methodology): “This particular snippet defines a top-level operation that applies the Approximate Quantum Fourier Transform (AQFT) to a quantum register, see also [4, 17] for more background on this operation.”
Polynomial-time quantum algorithm for the simulation of chemical dynamics (2008, methodology): “For addition, we adopt Draper’s quantum addition algorithm [1], which is based on the quantum Fourier transform (QFT), and requires only32m 2 controlled rotations.”
How to perform the most accurate possible phase measurements (2009, methodology): “The inverse QFT can be implemented by using the simplification of [24] which requires only local measurements and control.”
Information and computation: Classical and quantum aspects (2001, background): “Altogether this implies that the size of quantum circuit for Shor’s algorithm is order O(K(2)) regardless of the SWAP gates for the final reversion (Coppersmith, 1994).”
Automated optimization of large quantum circuits with continuous parameters (2017, unknown): “It is well known that one can perform a highly accurate approximate QFT by omitting gates with very small rotation angles.(21) We choose to omit rotations by angles at most π/2(13) since evidence suggests that using this approximate QFT in the factoring algorithm gives an approach with small failure”
Circuit for Shor's algorithm using 2n+3 qubits (2002, background): “In fact, it has been shown [8] that by keeping all gates Rk with k ≤ kmax, the approximate QFT differs from the QFT by a multiplicative factor e where |ǫ| ≤ 2πn2max .”
Quantum computing with trapped ions (2008, background): “It is designed to find the periodicity of a quantum state (Shor, 1994; Coppersmith, 1994; Ekert and Jozsa, 1996; Nielsen and Chuang, 2000).”