Physics – Quantum Physics
Scientific paper
2009-11-09
Quant. Inf. Comp. 11, 9-10 pp. 784-812 (2011)
Physics
Quantum Physics
26 pages, updated references
Scientific paper
We investigate the boundary between classical and quantum computational power. This work consists of two parts. First we develop new classical simulation algorithms that are centered on sampling methods. Using these techniques we generate new classes of classically simulatable quantum circuits where standard techniques relying on the exact computation of measurement probabilities fail to provide efficient simulations. For example, we show how various concatenations of matchgate, Toffoli, Clifford, bounded-depth, Fourier transform and other circuits are classically simulatable. We also prove that sparse quantum circuits as well as circuits composed of CNOT and exp[iaX] gates can be simulated classically. In a second part, we apply our results to the simulation of quantum algorithms. It is shown that a recent quantum algorithm, concerned with the estimation of Potts model partition functions, can be simulated efficiently classically. Finally, we show that the exponential speed-ups of Simon's and Shor's algorithms crucially depend on the very last stage in these algorithms, dealing with the classical postprocessing of the measurement outcomes. Specifically, we prove that both algorithms would be classically simulatable if the function classically computed in this step had a sufficiently peaked Fourier spectrum.
No associations
LandOfFree
Simulating quantum computers with probabilistic methods does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Simulating quantum computers with probabilistic methods, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Simulating quantum computers with probabilistic methods will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-659907