Efficient classical simulation of the approximate quantum Fourier transform

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 (2)

• Classical simulation versus universality in measurement based quantum computation
• Classical simulation of limited-width cluster-state quantum computation

Cited by in corpus (3)

• The quantum FFT can be classically simulated
• Classical simulability and the significance of modular exponentiation in Shor's algorithm
• A new approach to characterize qubit channels