Efficient classical simulation of the approximate quantum Fourier transform

We present a method for classically simulating quantum circuits based on the tensor contraction model of Markov and Shi (e-print arXiv:quant-ph/0511069). Using this method we are able to classically simulate the approximate quantum Fourier transform in polynomial time. Moreover, our approach allow 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.

Figure 1

A simple example circuit, and the associated graph and tensors.

Figure 2

The general structure of the circuit calculating the approximate quantum Fourier transform, showing a measurement of ∣0⟩ on the first output qubit. Each box corresponds to a ladder circuit, with internal gates as shown in Fig. 3.

Figure 3

The gates composing a ladder circuit, consisting of a Hadamard gate and then $m-1$ controlled rotation gates. Note that the last few ladder circuits are actually slightly smaller, although they have the same form.