Efficient Simulation of Quantum Mechanics Collapses the Polynomial Hierarchy

by Scott Aaronson.

Oded's comments

In find the warm-up result, which refers to exact simulation and has a much simpler proof, almost as appealing as the main result. Here I refer to the fact that the probabilty distribution to be simulated involve only probabilities that have a short representation as binary fractions.

The original abstract

We give a new type of evidence that quantum mechanics is hard to simulate classically---evidence that is more complexity-theoretic in character than Shor's famous factoring algorithm. Specifically we show the following: Suppose there's a BPP machine that, given any quantum circuit C, approximately samples (with constant error in variation distance) from the probability distribution over C's possible outputs. Then P^sharpP = BPP^NP, and in particular the polynomial hierarchy collapses. The proof uses a quantum algorithm that simulates a system of n identical, non-interacting bosonic particles. We exploit an old observation: that the amplitude for n non-interacting bosons to evolve to a particular state is given by the squared permanent of an n-by-n matrix, a sharpP-complete function. Therefore, one might hope that the ability to classically sample the bosons' final distribution would put sharpP in the polynomial hierarchy. However, pushing this implication through requires some further ideas from complexity theory, including the random self-reducibility of the permanent, noisy interpolation of polynomials, and approximate counting in BPP^NP. We also need to upper-bound the probability that two or more bosons will occupy the same state (unlike fermions, bosons are not subject to the Pauli exclusion principle, and can "pile on top of each other"). Our result can be strengthened in two ways. First, even if every distribution samplable in BQP can be approximately sampled in BPP^PH, we still get that P^sharpP = PH and PH collapses. This provides a new sort of evidence that quantum computers have capabilities outside the entire polynomial hierarchy. Second, we can prove a version of our result for relational problems (problems where the output is an n-bit string, and there could be many valid outputs), rather than sampling problems. What remains unknown is a result for decision problems (e.g., "if P=BQP then PH collapses").

Back to list of Oded's choices.