2
$\begingroup$

Taking hidden variables to mean an underlying dynamics characterised by some hidden variable $\lambda$, which characterises a definite state of a system at any given time, whilst reproducing the statistical predictions of a quantum mechanics. Since such a model is, by construction, classical does that necessarily mean problems that are soluble by a quantum computer in polynomial time would, in practice, have a large complexity should Hidden-Variables be true as it cannot take advantage of superposition and interference? For example should a large scale quantum computer be developed, tasked, using Shor's algorithm, with factorising large primes actually find the problem as difficult as a classical computer?

$\endgroup$
  • $\begingroup$ If QM is correct, then if there are hidden variables, the hidden variable theory has to be non-local. All the weirdness of QM will still be there, regardless of the hidden variables, because QM will remain unmodified. Now, if QM is inaccurate, then the story will be different. $\endgroup$ – user126422 May 9 '17 at 12:37
  • $\begingroup$ I agree that a valid hidden variable theory would have to reproduce the observed quantum weirdness. But, take for example n entangled Qubits this corresponds to a state characterised by 2^n complex numbers, surely an algorithm designed to take advantage of interference due to superposition, would in practice have on the order 2^n more calculations to do if in actuality hidden variables were specifying a single state for the Qbits? $\endgroup$ – HiddenVariable May 9 '17 at 15:51
2
$\begingroup$

It depends what you define as a computation. It will certainly not work as Turing machine (or a modern computer), because a Turing machine is local, in the same way that a cellular automata. If you define a cellular automaton with nonlocal rules, then it will be much faster than a turing machine, in the sense that many NP problems will become polynomial in time. I do not think the speed up is specific to QM, but to many other non-local rules too.

For instance, you can define quantum cellular automata that do have an exponential speed up. But even if they claim to have local rules, the computation is nonlocal: because of the conservation of the total probability for each time step, information of the global array spread out over generally nonlocal distances must be conveyed for each time step to each local site via the normalization procedure (see here).

I do not have knowledge of non-local cellular automata that could have more power than a Turing machine (not just a speedup), but I would not be surprised if somebody finds one (well, perhaps there is some theorem that does not allow it). Other extensions of Turing machines, local but that can run on ordinal time do have super Turing power.

I wonder if a cellular automata based on Newtonian mechanics could result in exponential speedups due to the fact that Newtonian mechanics is nonlocal (my guess is no, but I hope somebody here knows better).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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