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)?
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.
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.
