Shor's algorithm and Bohmian Mechanics

Question

Do quantum computer's tell us anything about the foundations of quantum theory? In particular Shor argued in the famous thread by 't Hooft

Why do people categorically dismiss some simple quantum models?

that quantum computation was at odds with 't Hooft's ideas.

Does quantum computation tell us anything new about hidden variables like Bohmian mechanics (which, at least so far, is 100% in agreement with everything we know about physics, contrary to what some people (e.g. Motl) claim)?

This post imported from StackExchange Physics at 2014-07-24 15:43 (UCT), posted by SE-user user7348

Comments

Previous Phys.SE posts on Bohmian mechanics: physics.stackexchange.com/q/7112/2451 and physics.stackexchange.com/q/31920/2451

This post imported from StackExchange Physics at 2014-07-24 15:43 (UCT), posted by SE-user Qmechanic

---

Bohm's theory reproduces quantum computation, this is why 'tHooft is as disgusted by it as by standard QM.

This post imported from StackExchange Physics at 2014-07-24 15:43 (UCT), posted by SE-user Ron Maimon

---

I didn't realize 't Hooft made a thread here. Is he the real deal? ;P Great, I'm off to read that one!

This post imported from StackExchange Physics at 2014-07-24 15:43 (UCT), posted by SE-user Raskolnikov

---

Every good physicist knows that the hidden-variable theories have been excluded for many decades and leading physicists such as the fathers of quantum mechanics knew that they were a wrong approach from the very first moment they were proposed by de Broglie in the late 1920s.

This post imported from StackExchange Physics at 2014-07-24 15:43 (UCT), posted by SE-user Luboš Motl

---

@ Motl, Absolute nonsense. The Bohmian predictions exactly reproduce quantum mechanics, and therefore are compatible with all known phenomena. If you think differently, I would like to see a paper demonstrating that a quantitative prediction from the Bohmian theory differs from what has been observed in the laboratory.

This post imported from StackExchange Physics at 2014-07-24 15:43 (UCT), posted by SE-user user7348

Answer 1

You might want to check out my paper Quantum Computing and Hidden Variables, where I showed that, in discrete hidden-variable theories sort of like Bohmian mechanics, computing the entire trajectory of a hidden variable is probably an intractable problem even for a "standard" quantum computer -- and would let us efficiently solve certain problems, like Graph Isomorphism, that are not known to have efficient quantum algorithms. (This result probably extends to Bohmian mechanics itself, but there are messy issues of formalization there.) What makes this surprising is that a quantum computer can easily sample any individual point in the hidden-variable trajectory (just simulate the system up until that point in time, then measure!). So the only source of difficulty lies in the correlations between the hidden-variable values at different times. In the same paper, I also showed that calculating a hidden-variable trajectory still probably wouldn't let you solve NP-complete problems in polynomial-time: all it would do is improve the square-root speedup of Grover's algorithm to a cube-root improvement! Thus, calculating hidden-variable trajectories provides one of the only examples I know of a computational problem that generalizes what a quantum computer can do, but only "slightly."

There seems to have been very little other work at the intersection of quantum computing and Bohmian mechanics. One reason for that is that Bohmian mechanics naturally lives in a continuous Hilbert space of particle positions, whereas quantum computing naturally lives in a finite-dimensional Hilbert space of qubits. A second reason is that, if you take a standard quantum algorithm (like Shor's algorithm) and try to look at the trajectory of a hidden variable while the algorithm is running, you get basically no additional insight. You'll just see the exponentially-large wavefunction "doing all the work," while the hidden variable bounces around as an almost comically irrelevant-looking fluff on top of it.

This post imported from StackExchange Physics at 2014-07-24 15:43 (UCT), posted by SE-user Scott Aaronson

Comments

The unexplored frontier of Bohmian mechanics is the "nomological" form, where you treat the pilot wave as a law of motion. That is, if you specialize to BM with a specific wavefunction, you can just eliminate the wavefunction from your ontology, and you're left with a local and a nonlocal potential for a "classical" system. No-one has seriously investigated this option - not as physics, and certainly not from a computational perspective.

This post imported from StackExchange Physics at 2014-07-24 15:43 (UCT), posted by SE-user Mitchell Porter

---

Needless to say, it would be interesting to understand exactly where the "quantum speedup" comes from, in a "theory" where there is no exponentially large state space. Instead it must somehow come from the complexity of the nonlocal interaction.

This post imported from StackExchange Physics at 2014-07-24 15:43 (UCT), posted by SE-user Mitchell Porter

---

Whoever downvoted this answer: may I ask why?

This post imported from StackExchange Physics at 2014-07-24 15:43 (UCT), posted by SE-user Scott Aaronson

Answer 2

Let me first mention a recent paper on quantum computing in the Bohm interpretation - http://arxiv.org/abs/1205.2563 , FWIW, though I cannot offer any comments on it right now, sorry.

Another thing. As nightlight noticed in his posts on hidden variables, there is an off-the-shelf mathematical trick (an extension of the Carleman linearization) that embeds a system of partial differential equations into a quantum field theory (see, e.g., my article in Int'l Journ. of Quantum Information ( akhmeteli.org/akh-prepr-ws-ijqi2.pdf ), the end of Section 3, and references there. There is also a substantially updated version at arxiv.org/abs/1111.4630).

nightlight also mentioned what that may mean for quantum computing. One can imagine a situation where Nature is described correctly by a quantum field theory (QFT), whereas actually only a limited subset of the entire set of states of the QFT is realized in Nature, the subset that is correctly described by a (classical) system of partial differential equations, so there are obvious limitations on how fast quantum computing can be. Of course this is highly hypothetical, but perhaps quite relevant to the question above on the relation between quantum computing and foundations of quantum theory.

This post imported from StackExchange Physics at 2014-07-24 15:43 (UCT), posted by SE-user akhmeteli