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?
Asked
Active
Viewed 545 times
8
Jim Graber
- 5,817
1 Answers
3
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.
