The quantum FFT can be classically simulated

Abstract

In this note we describe a simple and intriguing observation: the quantum Fourier transform (QFT) over $Z_q$, which is considered the most ``quantum'' part of Shor's algorithm, can in fact be simulated efficiently by classical computers. More precisely, we observe that the QFT can be performed by a circuit of poly-logarithmic path-width, if the circuit is allowed to apply not only unitary gates but also general linear gates. Recalling the results of Markov and Shi [MaSh] and Jozsa [Jo] which provided classical simulations of such circuits in time exponential in the tree-width, this implies the result stated in the title. Classical simulations of the FFT are of course meaningless when applied to classical input strings on which their result is already known; Our observation might be interesting only in the context in which the QFT is used as a subroutine and applied to more interesting superpositions. We discuss the reasons why this idea seems to fail to provide an efficient classical simulation of the entire factoring algorithm. In the course of proving our observation, we provide two alternative proofs of the results of [MaSh,Jo] which we use. One proof is very similar in spirit to that of [MaSh] but is more visual, and is based on a graph parameter which we call the ``bubble width'', tightly related to the path- and tree-width. The other proof is based on connections to the Jones polynomial; It is very short, if one is willing to rely on several known results.

12 pages, 3 figures. Added reference to similar results achieved independently by Yoran and Short (quant-ph/0611241)

References in corpus (7)

• Efficient classical simulation of slightly entangled quantum computations
• Simulating quantum computation by contracting tensor networks
• Classical simulation of noninteracting-fermion quantum circuits
• The BQP-hardness of approximating the Jones Polynomial
• Efficient classical simulation of the approximate quantum Fourier transform
• On the simulation of quantum circuits
• A Polynomial Quantum Algorithm for Approximating the Jones Polynomial

Cited by in corpus (17)

• Simulating quantum computation by contracting tensor networks
• qHiPSTER: The Quantum High Performance Software Testing Environment
• Quantum-centric Supercomputing for Materials Science: A Perspective on Challenges and Future Directions
• Trading inverses for an irrep in the Solovay-Kitaev theorem
• Quantum interference as a resource for quantum speedup
• Certainty and Uncertainty in Quantum Information Processing
• A tree tensor network approach to simulating Shor's algorithm
• Quantum-assisted biomolecular modelling
• Simulating Quantum Circuits with Sparse Output Distributions
• Effective Physical Processes and Active Information in Quantum Computing
• De-quantisation of the Quantum Fourier Transform
• Normalizer Circuits and Quantum Computation
• The Quantum Frontier
• Quantum Speedup and Categorical Distributivity
• Carving-width and contraction trees for tensor networks
• Classical simulation of qubit by a new hardware design and its applications
• Monoidal Width: Capturing Rank Width