Quantcast
  • Register
PhysicsOverflow is a next-generation academic platform for physicists and astronomers, including a community peer review system and a postgraduate-level discussion forum analogous to MathOverflow.

Welcome to PhysicsOverflow! PhysicsOverflow is an open platform for community peer review and graduate-level Physics discussion.

Please help promote PhysicsOverflow ads elsewhere if you like it.

News

PO is now at the Physics Department of Bielefeld University!

New printer friendly PO pages!

Migration to Bielefeld University was successful!

Please vote for this year's PhysicsOverflow ads!

Please do help out in categorising submissions. Submit a paper to PhysicsOverflow!

... see more

Tools for paper authors

Submit paper
Claim Paper Authorship

Tools for SE users

Search User
Reclaim SE Account
Request Account Merger
Nativise imported posts
Claim post (deleted users)
Import SE post

Users whose questions have been imported from Physics Stack Exchange, Theoretical Physics Stack Exchange, or any other Stack Exchange site are kindly requested to reclaim their account and not to register as a new user.

Public \(\beta\) tools

Report a bug with a feature
Request a new functionality
404 page design
Send feedback

Attributions

(propose a free ad)

Site Statistics

205 submissions , 163 unreviewed
5,047 questions , 2,200 unanswered
5,345 answers , 22,709 comments
1,470 users with positive rep
816 active unimported users
More ...

  Shor's algorithm and Bohmian Mechanics

+ 4 like - 0 dislike
1495 views

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
asked Aug 20, 2012 in Theoretical Physics by user7348 (20 points) [ no revision ]
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

2 Answers

+ 6 like - 0 dislike

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
answered Aug 21, 2012 by ScottAaronson (795 points) [ no revision ]
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
+ 1 like - 0 dislike

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
answered Aug 21, 2012 by akhmeteli (40 points) [ no revision ]

Your answer

Please use answers only to (at least partly) answer questions. To comment, discuss, or ask for clarification, leave a comment instead.
To mask links under text, please type your text, highlight it, and click the "link" button. You can then enter your link URL.
Please consult the FAQ for as to how to format your post.
This is the answer box; if you want to write a comment instead, please use the 'add comment' button.
Live preview (may slow down editor)   Preview
Your name to display (optional):
Privacy: Your email address will only be used for sending these notifications.
Anti-spam verification:
If you are a human please identify the position of the character covered by the symbol $\varnothing$ in the following word:
p$\hbar$ysicsO$\varnothing$erflow
Then drag the red bullet below over the corresponding character of our banner. When you drop it there, the bullet changes to green (on slow internet connections after a few seconds).
Please complete the anti-spam verification




user contributions licensed under cc by-sa 3.0 with attribution required

Your rights
...