In the 't Hooft threads, the exponential explosion is mentioned several times.
No one seems to like it. But it is an integral part of the standard formalism.
It seems to arise from the tensor product rule for Hilbert spaces.
Is there any known alternative that avoids this "explosion"?
Is there a theorem that shows it is unavoidable?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Comment to question(v1): For the benefit of future readers, perhaps you should link to the pertinent 't Hooft threads that you mention. $\endgroup$– Qmechanic ♦Aug 20, 2012 at 18:51
-
$\begingroup$ physics.stackexchange.com/questions/34217/… is the main reference $\endgroup$– Jim GraberAug 21, 2012 at 19:51
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
7
The "theorem" is not quite a theorem, but close. The main result was discovered by Peter Shor and is explained by Shor in one of the answers. Quantum systems of size N bits can for sure solve a few nontrivial search problems that are strongly believed to be unsolvable by classical methods without trying exponentially many possibilities, requiring order $2^N$ parallel trials. It is therefore certainly (in the physical, not mathematical, sense) unavoidable to do exponential computation to simulate full quantum mechanics, since otherwise there would be a uniform classical solution to all the problems quantum computers can solve, and this is exceedingly unlikely, even in the unlikely case that all of these are solvable by a complicated separate clever classical probabilistic algorithm.
The best example, since it is familiar, is factoring large integers. Classically, you try out a bunch of factors until you find one (you can't fail, since there is a recently discovered polynomial time algorithm which tells you whether a factor exists). Factoring is heavily studied, because it is important in cryptography, and the best algorithm are exponential in a fractional power of the length of the number. If there is a good algorithm for factoring, it is likely to be extremely complicated, and such a complicated algorithm will surely have nothing to do with the quantum algorithm, which is relatively simple compared to any hypothetical classical algorithm (although finding the quantum algorithm was already a great stroke of genius).
If you have a method of simulating quantum mechanics without the exponential explosion, you automatically find a good algorithm for factoring, and other related problems solvable by what is now known as the quantum Fourier transform. This is extraordinarily implausible, but it is not quite a theorem.
The problem with proving that factoring is unsolvable in polynomial time is that it would automatically prove P!=NP, which is one of the most hopelessly difficult mathematical conjectures. So don't hold your breath for a quick proof. Since factoring is in NP, if you prove factoring is not in P, then you prove P!=NP.
THe class of problems efficiently solvable by quantum computers includes problems that are not even in NP, that is, that are not solvable by a potentially infinitely parallel computer. So while proving factoring is hard requires proving P!=NP, to prove quantum computing is hard would not require quite so much, it would only imply that PSPACE is bigger than P.
The preceding means that any reasonably small classical substructure to quantum mechanics is forced to make an experimentally testable prediction which is different from usual quantum mechanics, namely that quantum computers will fail at a certain not too large number of qubits.
-
4$\begingroup$ Actually, arguably the best example was discovered by Simon before me. (Simon's algorithm for Simon's problem.) And it wouldn't prove P != NP if you proved that classical computers can't simulate quantum computers efficiently. It would prove P != PSPACE, which would be nearly as surprising to computational complexity theorists. $\endgroup$ Aug 18, 2012 at 22:31
-
1$\begingroup$ If you prove that simulating a quantum computer is not in P, you will know that P != BQP and, as BQP is included in PSPACE, you will also know that P != PSPACE. But BQP is not believed to be included in NP. $\endgroup$– mmcAug 19, 2012 at 14:01
-
1$\begingroup$ @RonMaimon In other words, you are not excluding P=NP if you prove that a quantum computer can't be simulated efficiently because, with the present state of knowledge, even a polynomial time SAT solver won't allow us to simulate a quantum computer in polynomial time. $\endgroup$– mmcAug 19, 2012 at 14:06
-
1$\begingroup$ @RonMaimon No, Peter is right here. You are obviously right in that proving that factoring is outside P implies P != NP. But proving that BQP is outside P only shows that Shor's algorithm cannot be simulated in a classical computer using polynomial time. It doesn't prove that factoring is outside P. $\endgroup$– mmcAug 19, 2012 at 18:54
-
1$\begingroup$ Oh I see, the comment I made is wrong (although not the answer)! I should have said "if you prove you can simulate a quantum computer efficiently, you prove factoring is in P", it's false to say "if you prove you can't simulate a quantum computer efficiently then you prove P!=NP", what is true is "if you prove you can't simulate a quantum computer efficienly, you prove P!=PSPACE", because there might logically be unrelated algorithms that solve all the NP problems in P. I am sorry, the nonstandard ideas that P=NP are so silly to my brain, I didn't even consider these options are realistic. $\endgroup$ Aug 19, 2012 at 20:46
