12
$\begingroup$

JBV suggested I turn some comments into a question, so here goes.

Another question [1] asks about applications of QM computing. One answer [2] was "efficiently simulating quantum mechanics". Apparently this idea dates all the way back to Feynman's early writing on subject; although I dont have a reference. So:

Question. What is the proof that a quantum computer can efficiently simulate an arbitrary quantum mechanical system?

On one level this seems basic. However, this does not seem to be trivial for following reason: most quantum computing literature seems to reduce to operations on gates acting on two particles or other small subsystems. (Yes, Toffoli gates act on 3 inputs, but anyway are often reduced to two-qubit CNOT gates.)

There is surely no question, due to Turing completeness, that a quantum computer can simulate arbitrary classical or even quantum physics (although maybe there are some naysayers there due to the uncertainty principle etcetera — I would be curious to hear about that too). But it seems to me that to simulate arbitary quantum physics efficiently one at least needs a way to simulate arbitrary n-way interactions in mostly/nearly 2-way gates.

One could argue that we can build arbitary n-way gates, but the clear evidence after many years of experimental research is that even just 2-way gates are extremely hard to build, and that n-way gates would surely be much harder. (There are some 3-way quantum experiments, e.g. 3 particle bell inequalities, but they are difficult to build.)

[1] Real world applications of quantum computing (except for security)

[2] https://cstheory.stackexchange.com/a/10241/248

Improve this question
$\endgroup$
1
  • $\begingroup$ further thoughts, the general idea of QM computer equivalence with QM physics simulation apparently originated with Feynman, who seemed to take it as a given or assumption [who was more a brilliant physicist than a computer scientist]... eg in the paper & lecture, Simulating Physics with Computers, 1982 $\endgroup$
    – vzn
    Commented Nov 18, 2013 at 23:52

1 Answer 1

Reset to default
16
$\begingroup$

Why do you think simulating quantum physics means that you have to efficiently implement arbitrary quantum $n$-way interactions? If that's your requirement, quantum computers cannot do it efficiently.

You can write down an $n$-way unitary gate which implements an arbitrary $n$-bit-input $n$-bit-output function. This would let us solve an arbitrary problem on $n$ bits in one step. It is common sense that we can't find quantum systems in "real life" that will let us do this.

Of course, in actual quantum physics, quantum dynamics is Hamiltonian and not just unitary, but there are still roughly $2^n$ parameters in an arbitrary $n$-way Hamiltonian, and doing this using 2-qubit gates (which have a constant number of parameters each) will require an exponential number of gates. Furthermore, I am fairly sure that the ability to implement arbitrary $n$-way Hamiltonians would still let you construct arbitrary binary functions on $O(n)$ bits.

So the requirement you pose for quantum computers to efficiently simulate arbitrary $n$-way interactions is much too strict. What you need is that quantum computers can efficiently simulate the $n$-way interactions that actually arise in quantum physics. Quantum computers are able to efficiently simulate $k$-local Hamiltonian dynamics for constant $k$, which may be enough to simulate interactions that arise in real quantum physics.

If you can suggest any $n$-way interactions that arise in quantum physics that appear difficult for a quantum computer to simulate efficiently, this would be a truly exciting development. However, I don't know of any current suggestions for such interactions.

Whether quantum computers can efficiently simulate quantum field theory is still an open question, but progress is currently being made on it.

Improve this answer
$\endgroup$
6
  • $\begingroup$ isnt that a typo in 1st line "should"=>"shouldnt". and note Im focusing on the tighter issue of efficiency, not mere equivalence. accept that QM computers are Turing complete. since you say this is all fairly straightfwd, how about the simple case of simulating an n-particle quantum system where no particles are isolated from each other? how is that done with qubits? $\endgroup$
    – vzn
    Commented Feb 24, 2012 at 21:22
  • 6
    $\begingroup$ I was talking about efficiency. To efficiently simulate an $n$-particle quantum system where no particles are isolated from each other, you have to look at the Hamiltonian. If there are only pairwise interactions between the particles, then you use Trotterization; this only gives you a polynomial hit in efficiency, and you're fine. If not, then you have to analyze the structure of the Hamiltonian carefully. The point I'm making is (1) you can't simulate an arbitrary Hamiltonian efficiently and (2) physical Hamiltonians are not arbitrary. $\endgroup$
    – Peter Shor
    Commented Feb 25, 2012 at 2:14
  • 1
    $\begingroup$ will take your word for it but my main pt-- is this discussed anywhere in the literature? seem all those caveats could easily fill up a paper at least. you seem to be asserting that likely all physical hamiltonians are efficiently simulatable via qubits, but that needs to be fleshed out somehow mathematically. & I think its sufficiently nontrivial that authorities should not glibly state that efficient QM simulation of all arbitrary QM setups is intrinsically feasible. maybe environmental influences eg applied electrical or magnetic field configurations could complicate the hamiltonian. $\endgroup$
    – vzn
    Commented Feb 25, 2012 at 3:03
  • 5
    $\begingroup$ I believe I've seen it discussed somewhere, but I don't remember where. Saying which Hamiltonians can be implemented physically is a tricky question ... since the dynamics of nature all originates in quantum field theory, showing that QFT can be simulated efficiently with a quantum computer might answer this question, but (1) we're still a really long from proving this and (2) this might be something like saying we can simulate turbulence by using the underlying atomic dynamics. In some sense, it might be true, but it's clearly the wrong way to do it. $\endgroup$
    – Peter Shor
    Commented Feb 27, 2012 at 0:16
  • $\begingroup$ I guess the question also depends on does QFT have a natural bit-model associated with it different than the qubit model and stronger? For example going from bits to qubits where your replacing the state (a bit) with a wave function (a qubit with probability amplitudes). I wonder if the path integral formulation "suggests" a natural QFT-bit analogue. $\endgroup$
    – Sidharth Ghoshal
    Commented Oct 18, 2022 at 16:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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