Efficient classical simulation of the approximate quantum Fourier transform
arXiv:quant-ph/0611241 · doi:10.1103/PhysRevA.76.042321
Abstract
We present a method for classically simulating quantum circuits based on the tensor contraction model of Markov and Shi (quant-ph/0511069). Using this method we are able to classically simulate the approximate quantum Fourier transform in polynomial time. Moreover, our approach allows us to formulate a condition for the composability of simulable quantum circuits. We use this condition to show that any circuit composed of a constant number of approximate quantum Fourier transform circuits and log-depth circuits with limited interaction range can also be efficiently simulated.
5 pages, 3 figures
References in corpus (3)
Cited by in corpus (25)
- Simulating quantum computation by contracting tensor networks
- Roadmap on Spin-Wave Computing
- Quantum-centric Supercomputing for Materials Science: A Perspective on Challenges and Future Directions
- Equivalence between contextuality and negativity of the Wigner function for qudits
- Quantum Fourier Transform Has Small Entanglement
- Multiscale space-time ansatz for correlation functions of quantum systems based on quantics tensor trains
- Scalable reconstruction of unitary processes and Hamiltonians
- The quantum FFT can be classically simulated
- A tree tensor network approach to simulating Shor's algorithm
- Solving search problems by strongly simulating quantum circuits
- Classical simulability and the significance of modular exponentiation in Shor's algorithm
- Simulating Quantum Circuits with Sparse Output Distributions
- Simulation of Quantum Computing on Classical Supercomputers
- Tensor network methods with graph enhancement
- Simulating the quantum Fourier transform, Grover's algorithm, and the quantum counting algorithm with limited entanglement using tensor-networks
- De-quantisation of the Quantum Fourier Transform
- Understanding the Quantum Computational Speed-up via De-quantisation
- Quantum computation mediated by ancillary qudits and spin coherent states
- On Shor's Factoring Algorithm with More Registers and the Problem to Certify Quantum Computers
- Normalizer Circuits and Quantum Computation
- Direct interpolative construction of the discrete Fourier transform as a matrix product operator
- Classical simulations of Abelian-group normalizer circuits with intermediate measurements
- A new approach to characterize qubit channels
- Entanglement, Flow and Classical Simulatability in Measurement Based Quantum Computation
- Classical simulation of qubit by a new hardware design and its applications