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.