Complexity of quantum simulation Richard Feynman showed that Quantum simulation on a Turing machine will have an exponential slowdown. If that is so, does this put quantum simulation outside of P (complexity class)? I thought quantum simulation was polynomially possible on quantum computers, but there is still no proof that BQP is strictly bigger than P. So either quantum simulation has not been shown to lie outside of P, or it is not in BQP. I can't seem to find the answer.
 A: Feynman never showed that quantum simulation has an exponential cost. He probably mentioned that it seemed to be the case.
In complexity theory, it's surprisingly hard to prove lower bounds on the cost of solving a problem or to prove separations between complexity classes. The behavior of computer programs is wildly diverse, and eliminating all of them as candidates is pretty tricky. For example, complexity theorists trying to resolve P-vs-NP have proved lower bounds... on how hard the proof will be.
Classical vs quantum, i.e. BPP vs BQP, is one of the many examples of a complexity class pair in the "conjectured to be different, but no one knows how to prove it" bucket.
As an example of why this is tricky, suppose you conjectured that quantum computers have a space advantage over classical computers. That BQP $\not\subset$ PSPACE. You make all kinds of arguments about the number of amplitudes being exponentially large, etc, etc. Except we know that, actually, BQP $\subset$ PSPACE. You can compute a single output amplitude without using much space by iterating over all the possible paths contributing to it. Use that to iterate over the outputs, and return one probabilistically.
Proving there's nothing that does for time what path integrals did for space is hard.
