4
$\begingroup$

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.

$\endgroup$
8
  • 3
    $\begingroup$ Did Feynman gave a formal proof for that? Can you cite it? $\endgroup$
    – CuriousOne
    Commented Apr 27, 2016 at 20:21
  • $\begingroup$ The only thing I can find is a transcription of a key note he gave, where he suggests it: Simulating physics with computers, Richard Feynman. He does not give a formal proof I think. I take it there haven't been any formal proofs since? $\endgroup$
    – lmartens
    Commented Apr 27, 2016 at 20:34
  • 3
    $\begingroup$ It is well known that simulating quantum models is not necessarily hard, e.g. stabilizer quantum mechanics, Gaussian continuous-variable quantum mechanics, or one-dimensional spin systems satisfying an area law, can all be simulated with polynomial overhead. (I suppose Feynman was not aware of these examples when he made his famous proposal.) Computer scientists have various reasons to believe that there should exist quantum simulations which are hard (i.e. not in $P$), but there is still no proof. $\endgroup$ Commented Apr 27, 2016 at 20:56
  • $\begingroup$ @MarkMitchison: Are you saying that there is no known example of a quantum system that is not in P or that there is no known proof that a non-naive algorithm can not be in P? I am never certain about what these statements mean. $\endgroup$
    – CuriousOne
    Commented Apr 27, 2016 at 21:03
  • 1
    $\begingroup$ @CuriousOne Basically, any quantum mechanical problem can be simulated classically using a polynomial amount of memory (basically, using a path integral), a class known as PSPACE. It is not known whether PSPACE is strictly larger than P. So if you could prove for a quantum problem that it is outside P, you would have also solved a long-standing open problem in complexity theory. $\endgroup$ Commented Apr 28, 2016 at 10:25

1 Answer 1

7
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Does BQP $\subset$ PSPACE have a longer story? Would love to read it if so $\endgroup$
    – Luke Miles
    Commented Apr 11 at 21:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.