# If quantum mechanics is ultimately deterministic, would Shor's factorization algorithm still work for large integers?

Victor Stenger argues that the apparent randomness in quantum mechanics is a result of the randomness in the macroscopic detectors (similar to the randomness in the laws of thermodynamics) and is not something that is inherent to quantum mechanics (this is my interpretation of Stenger). This would imply that QM is ultimately deterministic. See http://www.colorado.edu/philosophy/vstenger/Timeless/08-timeless.pdf

If this is true, then would Shor's factorization algorithm still work for large integers? More generally, how would scalable quantum computing be affected?

• I don't think so. Shor himself provided the argument in another thread that determinism implies $2^n$ states are necessary for a system of order $n$.
– Nick
Commented Sep 2, 2012 at 19:45
• Can you point to the thread? Commented Sep 2, 2012 at 20:23
• physics.stackexchange.com/a/34402/960
– Nick
Commented Sep 2, 2012 at 20:24
• Thank you Nick. That's good, but I'd like to see more detail in an answer. Hopefully, someone will provide more detail. Commented Sep 2, 2012 at 20:37
• Commented Dec 30, 2012 at 19:21

Victor Stenger's stuff is vague unquantitative musings with no significant value, about back and forth in time particle paths and such things. It isn't important to this question, and it isn't important for anything at all.

If quantum mechanics is deterministic underneath, and the number of variables is reasonably bounded, for example a number of bits less than the area of the cosmological horizon in Planck units, about $10^{138}$, then the the exponentially growing search ability of a quantum computer will crap out. The point at which factoring necessarily fails can be easily estimated from the number of independent multiplications performed in Shor's algorithm. To do $10^N$ multiplications in superposition at once, you need $10^N$ classical states (it's actually NlogN in the exponent, but same difference), so when N is larger than around 130, so around 130 digit numbers, you exceed this bound.

Since the entire universe can't be expending all it's effort on your dinky quantum computer, the actual bound will be closer to 100 digits, on the same the order of the numbers used for cryptography today.

To be on the absolute safe side, perhaps nature realizes something about the multiplications and reduces the operations accordingly, you should have N to some power less than 1 in the exponent, because of redundancies, and you should have N to some power less than 1 in the exponent. This power cannot be as small as 1/2, because the best classical algorithm scales exponentially in a higher exponent than this, and nature isn't as clever as mathematicians trying hard to do factoring. So you get a firm bound at around 10,000 digits, and a quantum computer factoring larger numbers than this is definite evidence that quantum mechanics is exponentially large.

If you don't say there is a limit to the amount of classical computation in the deterministic model, if you allow exponentially large deterministic descriptions, you can mimic quantum mechanics exactly using Bohmian mechanics. You make a lattice description of some field theory, you make a wavefunction for the fields, and you have definite field values that wander around according to the Bohmian quantum force law. This type of thing can't be ruled out experimentally, but the description is not unique, it is different depending on which fields you choose to make Bohmian, and in which time-slicing you define the quantum-force dynamics, so it is certainly not the right description. Bohmian mechanics might as well be quantum mechanics, which is why Bohm's theory is more often called an interpretation of quantum mechanics rather than a new theory.

There is no point in asking whether it's deterministic underneath if Shor's algorithm works, the determinism in this case would be the universe simulating quantum mechanics and fooling us into thinking it's correct. In this case, you might as well believe quantum mechanics is exact with no substructure.

So the only options, modulo philosophy, are that quantum mechanics fails to factor 10,000 digit numbers, or that it succeeds and is exact. This a wonderful experimental distillation of the hidden-variable question, and for those that have full confidence that quantum computers will work, this definitively excludes hidden variable theories. This is Shor's answer to this question: Why do people categorically dismiss some simple quantum models? .

• from where does it come the estimation of $10^{130}$ classical bits for what is encoded by our cosmological horizon? Commented Sep 2, 2012 at 21:45
• @lurscher: That's the age of the universe in Planck times squared. Commented Sep 2, 2012 at 22:21
• what is the relationship between area of cosmological horizon and age of the universe? Commented Sep 3, 2012 at 3:52
• @user56771: The radius of the universe and it's age are the same up to factors of order unity, calculable from the r-form of the FRW metric. I don't extrapolate as cosmologists often misleadingly do, but whether you do or don't, all these considerations would only change the order-unity factor, not the order of magnitude. Commented Sep 3, 2012 at 5:51
• @CraigFeinstein: It is not "well written" because the number of ideas per sentence is too low to waste time reading it, and it is not important because the new ideas, which are hardly there, are all wrong. Commented Sep 3, 2012 at 17:42