What is the proof that quantum computers can efficiently simulate arbitrary quantum mechanical systems? 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 &mdash; 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
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.