<p>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.</p>

<p>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. </p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>Whether quantum computers can efficiently simulate quantum field theory is still an open question, but progress is <a href="http://arxiv.org/abs/1111.3633">currently</a> being <a href="http://arxiv.org/abs/1112.4833">made</a> on it. </p>

CC BY-SA 3.0
2012-02-24T21:22:24.553Z
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?
vzn
CC BY-SA 3.0
2012-02-25T02:14:55.807Z
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.
Peter Shor 
CC BY-SA 3.0
2012-02-25T03:03:49.967Z
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.
vzn
CC BY-SA 3.0
2012-02-27T00:16:51.390Z
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.
Peter Shor 
CC BY-SA 4.0
2022-10-18T16:43:56.907Z
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.
Sidharth Ghoshal
CC BY-SA 4.0
2022-10-18T16:45:25.580Z
maybe instead of a wave function over bit vectors, we instead look at ordered sequences of bit-vectors (paths) and to each such path we assign a phase, and now we need to know what our operators are going to be on these paths (i dont think i have the right level of physics maturity to generalize this)
Sidharth Ghoshal
CC BY-SA 3.0
2012-02-24T20:44:22.630Z
2012-02-25T02:23:00.600Z
2012-02-25T02:23:00.600Z
Peter Shor 
<p>JBV suggested I turn some comments into a question, so here goes.</p>

<p>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: </p>

<blockquote>
  <p><strong>Question.</strong> What is the proof that a quantum computer can efficiently simulate an arbitrary quantum mechanical system?</p>
</blockquote>

<p>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.)</p>

<p>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 &mdash; I  would be curious to hear about that too). But it seems to me that to simulate arbitary quantum physics <em>efficiently</em> one at least needs a way to simulate arbitrary <em>n-way</em> interactions in mostly/nearly <em>2-way</em> gates.</p>

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

<p>[1] 
<a href="https://cstheory.stackexchange.com/questions/10141/real-world-applications-of-quantum-computing-except-for-security">Real world applications of quantum computing (except for security)</a></p>

<p>[2] <a href="https://cstheory.stackexchange.com/a/10241/248">https://cstheory.stackexchange.com/a/10241/248</a></p>

CC BY-SA 3.0
2013-11-18T23:52:31.187Z
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](http://link.springer.com/article/10.1007%2FBF02650179), 1982
vzn
<reference-request><quantum-computing><application-of-theory>
What is the proof that quantum computers can efficiently simulate arbitrary quantum mechanical systems?
vzn
# What is the proof that quantum computers can efficiently simulate arbitrary quantum mechanical systems?

(Asked by: username_0 on 2012-02-24)

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)](https://cstheory.stackexchange.com/questions/10141/real-world-applications-of-quantum-computing-except-for-security)

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

**Tags:** reference-request, quantum-computing, application-of-theory

> **Comments:**
> **username_0**: 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](http://link.springer.com/article/10.1007%2FBF02650179), 1982  

---

## 1 answers

### Answer by username_1 on 2012-02-24. Score: 16 | Accepted answer

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](http://arxiv.org/abs/1111.3633) being [made](http://arxiv.org/abs/1112.4833) on it.

> **Comments:**
> **username_0**: 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?  
> **username_1**: 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.  
> **username_0**: 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.  
> **username_1**: 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.  
> **username_2**: 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.  
> **username_2**: maybe instead of a wave function over bit vectors, we instead look at ordered sequences of bit-vectors (paths) and to each such path we assign a phase, and now we need to know what our operators are going to be on these paths (i dont think i have the right level of physics maturity to generalize this)  

---

