Efficient classical simulation of the semi-classical Quantum Fourier Transform

Abstract

A number of elegant approaches have been developed for the identification of quantum circuits which can be efficiently simulated on a classical computer. Recently, these methods have been employed to demonstrate the classical simulability of the quantum Fourier transform (QFT). In this note, we show that one can demonstrate a number of simulability results for QFT circuits in a straightforward manner using Griffiths and Niu's semi-classical QFT construction [Phys. Rev. Lett. 76, 3228 (1996)]. We then discuss the consequences of these results in the context of Shor's factorisation algorithm.

4 pages, 2 figures. Comments welcome

References in corpus (9)

• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Efficient classical simulation of slightly entangled quantum computations
• Persistent entanglement in arrays of interacting particles
• On the role of entanglement in quantum computational speed-up
• A class of ansatz wave functions for 1D spin systems and their relation to DMRG
• Semiclassical Fourier Transform for Quantum Computation
• Quantum Algorithms: Entanglement Enhanced Information Processing
• Ground state approximation for strongly interacting systems in arbitrary dimension
• Classical simulation of limited-width cluster-state quantum computation

Cited by in corpus (25)

• Quantum walks: a comprehensive review
• Generalization in quantum machine learning from few training data
• Roadmap on Spin-Wave Computing
• Using Quantum Computers for Quantum Simulation
• Equivalence between contextuality and negativity of the Wigner function for qudits
• Quantum Fourier Transform Has Small Entanglement
• Neural-network states for the classical simulation of quantum computing
• Exact NMR simulation of protein-size spin systems using tensor train formalism
• Solving search problems by strongly simulating quantum circuits
• Quantum-assisted biomolecular modelling
• Classical simulability and the significance of modular exponentiation in Shor's algorithm
• Quantum algorithms for scientific computing
• Simulating Quantum Circuits with Sparse Output Distributions
• De-quantisation of the Quantum Fourier Transform
• Quantum self-learning Monte Carlo with quantum Fourier transform sampler
• Interference versus success probability in quantum algorithms with imperfections
• Quantum computation mediated by ancillary qudits and spin coherent states
• Understanding the Quantum Computational Speed-up via De-quantisation
• Normalizer Circuits and Quantum Computation
• Direct interpolative construction of the discrete Fourier transform as a matrix product operator
• Cooling ultracold bosons in optical lattices by spectral transform
• Classical simulations of Abelian-group normalizer circuits with intermediate measurements
• Simulations of Shor's Algorithm using Matrix Product States
• Classical Simulation of Quantum Adiabatic Algorithms using Mathematica on GPUs
• Symmetry-Accelerated Classical Simulation of Clifford-Dominated Circuits