Suppose I want to write a classical software simulator of a quantum circuit with $N$ qubits.  When it comes time to simulate the quantum Fourier transform I can evaluate all $2^N$ states to determine the probability amplitudes, and then perform a Fast-Fourier Transform on the probability amplitudes in time $o(N 2^N)$.  Finally in $o(2^N)$ time I can generate a scan of the partial sums of the probabilities of all the result states.  Then I can choose a random number in the range $[0,1]$ and use it to do a binary search of the partial sums.This results in a simulator that, each time is run outputs a single $N$ bit binary number with the probability distribution predicted by theory.Can I do better?  Of course I can't do exponentially better in general, but perhaps I could reduce the time to simulate a single experiment to $o(2^N)$?I can do significantly better under some circumstances.  For example, Gilbert, Guha, Indyk, Muthukrishnan, and Strauss, Near-Optimal Sparse Fourier Representations via Sampling, ACM Symp Theory Comp, STOC-44:152-161, 2002, seems to indicate that if there are only $B$ frequencies (or if the $B$ frequencies make up most of the power of the signal) then there is a randomized algorithm that will recover all of them (and their amplitudes) in time, space and number of samples polynomial in $B$ and $N$.I guess I'm hoping for something like that, but only to get one frequency, and to have some guarantee that the probability of getting a particular frequency will be proportional to the amplitude of its coefficient.
(Slightly) faster simulation of quantum Fourier transform
randomized algorithms;quantum computing;fourier transform