<p>This question is similar to the "Computability Theory". This theory studies the problem of "What problems can be computed by a computing machine?"! Well! We need a model for that machine!</p>

<p>This is exactly the case here, from my point of view if I am correct. They did not consider a computational model for quantum computer or maybe they believe, as Prof @Peter Shor pointed out, they do not know all the quantum laws.</p>

<p>To sum it up, the question here is that are all quantum systems computable by a quantum computer?</p>

CC BY-SA 3.0
2013-11-18T20:57:19.663Z
They do give an exact computational model for a quantum computer, and this quote comes from the chapter in which they give it.
Peter Shor 
CC BY-SA 3.0
2013-11-16T18:05:54.600Z
2013-11-16T18:05:54.600Z
Ali Shakiba
<p>We will never be able to <em>prove</em> this statement, because we can never be able to know for sure whether we have the exact laws of physics, or just a very good approximation to them. Even if we had a satisfactory theory of everything which we could use to make good predictions about every experimentally measurable physical system, there would be no way to tell whether it was correct or a very good approximation.</p>

<p>Having said that, we are still quite far from even coming close to a proof of this statement. For example, we can't even prove that the Standard Model is simulable by a quantum computer. Jordan, Lee, and Preskill have <a href="http://arxiv.org/abs/1111.3633">two</a> <a href="http://arxiv.org/abs/1112.4833">papers</a> showing how to use a quantum computer to simulate a quantum field theory which is much simpler than the Standard Model. This turns out to be harder than it might at first appear. </p>

CC BY-SA 3.0
2013-11-19T04:22:04.127Z
In that case I would like to know the ground of 'high confidence' mentioned by the authors.
Omar Shehab
CC BY-SA 3.0
2013-11-18T20:33:53.877Z
2013-11-18T20:53:39.650Z
2013-11-18T20:53:39.650Z
Peter Shor 
<p>Let me quote from the section 9.3 of <a href="http://rads.stackoverflow.com/amzn/click/0821832298" rel="nofollow">Classical and Quantum Computation</a> by Kitaev, Shen and Vyalyi. </p>

<blockquote>
  <p>With high confidence, we may claim that every physical quantum system
  can be efficiently simulated on a quantum computer, but we can never
  prove this statement.</p>
</blockquote>

<p>Why can't we ever prove this statement?</p>

CC BY-SA 3.0
2013-11-16T14:04:15.217Z
Because we don't know the laws of physics for certain?
Peter Shor 
CC BY-SA 3.0
2013-11-16T22:38:40.550Z
This is no different hat the problem with the Church-Turing thesis more generally (just focusing on quantum systems and making the simulations efficient). For an overview why the looser statement still can't be proven see [this discussion](http://cstheory.stackexchange.com/q/88/1037) and [accompanying blog post](http://nanoexplanations.wordpress.com/2011/07/04/a-mathematical-proof-of-the-church-turing-thesis/).
Artem Kaznatcheev
CC BY-SA 3.0
2013-11-16T22:48:51.723Z
@PeterShor, do you mean all our theories are approximations to some extent?
Omar Shehab
CC BY-SA 3.0
2013-11-17T00:40:36.673Z
We will ***never*** be able to know for sure whether we have the right laws of physics, or just very good approximations.
Peter Shor 
CC BY-SA 3.0
2013-11-17T07:14:21.983Z
@PeterShor, can we at least say that any physical phenomena is just a combination of more than zero local unitary transformations as defined in quantum mechanics?
Omar Shehab
CC BY-SA 3.0
2013-11-17T11:42:43.080Z
@Omar: the universe isn't local unitary transformations; it's quantum field theory (and it's not even that, because we don't know how to write gravity as a quantum field theory; string theory isn't quantum field theory).
Peter Shor 
CC BY-SA 3.0
2013-11-17T15:55:55.407Z
@PeterShor Your comments make a good answer.
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-11-17T15:58:50.317Z
@Mohammad: I'm a little uncertain about making it an answer, because I don't know for sure that's what they meant without seeing the statement in the original context.
Peter Shor 
CC BY-SA 3.0
2013-11-18T20:55:20.640Z
@Mohammad: I looked up the original context of this statement in Kitaev, Shen, and Vyalyi, and although there's not that much context, it seems to me that my comments indeed reflect what they meant. So I'm adding an answer.
Peter Shor 
CC BY-SA 3.0
2013-11-18T21:04:19.563Z
nearly same as this question [what is the proof that qm computers can efficiently simulate arbitrary qm systems](http://cstheory.stackexchange.com/questions/10368/what-is-the-proof-that-quantum-computers-can-efficiently-simulate-arbitrary-quan)
vzn
<quantum-computing><turing-machines><quantum-information><physics><qma>
Simulation of every physical quantum system on quantum computer
Omar Shehab
# Simulation of every physical quantum system on quantum computer

(Asked by: username_0 on 2013-11-16)

Let me quote from the section 9.3 of [Classical and Quantum Computation](http://rads.stackoverflow.com/amzn/click/0821832298) by Kitaev, Shen and Vyalyi.

> With high confidence, we may claim that every physical quantum system
> can be efficiently simulated on a quantum computer, but we can never
> prove this statement.

Why can't we ever prove this statement?

**Tags:** quantum-computing, turing-machines, quantum-information, physics, qma

> **Comments:**
> **username_1**: Because we don't know the laws of physics for certain?  
> **username_2**: This is no different hat the problem with the Church-Turing thesis more generally (just focusing on quantum systems and making the simulations efficient). For an overview why the looser statement still can't be proven see [this discussion](http://cstheory.stackexchange.com/q/88/1037) and [accompanying blog post](http://nanoexplanations.wordpress.com/2011/07/04/a-mathematical-proof-of-the-church-turing-thesis/).  
> **username_0**: @PeterShor, do you mean all our theories are approximations to some extent?  
> **username_1**: We will ***never*** be able to know for sure whether we have the right laws of physics, or just very good approximations.  
> **username_0**: @PeterShor, can we at least say that any physical phenomena is just a combination of more than zero local unitary transformations as defined in quantum mechanics?  
> **username_1**: @Omar: the universe isn't local unitary transformations; it's quantum field theory (and it's not even that, because we don't know how to write gravity as a quantum field theory; string theory isn't quantum field theory).  
> **username_3**: @PeterShor Your comments make a good answer.  
> **username_1**: @Mohammad: I'm a little uncertain about making it an answer, because I don't know for sure that's what they meant without seeing the statement in the original context.  
> **username_1**: @Mohammad: I looked up the original context of this statement in Kitaev, Shen, and Vyalyi, and although there's not that much context, it seems to me that my comments indeed reflect what they meant. So I'm adding an answer.  
> **username_4**: nearly same as this question [what is the proof that qm computers can efficiently simulate arbitrary qm systems](http://cstheory.stackexchange.com/questions/10368/what-is-the-proof-that-quantum-computers-can-efficiently-simulate-arbitrary-quan)  

---

## 2 answers

### Answer by username_1 on 2013-11-18. Score: 6 | Accepted answer

We will never be able to *prove* this statement, because we can never be able to know for sure whether we have the exact laws of physics, or just a very good approximation to them. Even if we had a satisfactory theory of everything which we could use to make good predictions about every experimentally measurable physical system, there would be no way to tell whether it was correct or a very good approximation.

Having said that, we are still quite far from even coming close to a proof of this statement. For example, we can't even prove that the Standard Model is simulable by a quantum computer. Jordan, Lee, and Preskill have [two](http://arxiv.org/abs/1111.3633) [papers](http://arxiv.org/abs/1112.4833) showing how to use a quantum computer to simulate a quantum field theory which is much simpler than the Standard Model. This turns out to be harder than it might at first appear.

> **Comments:**
> **username_0**: In that case I would like to know the ground of 'high confidence' mentioned by the authors.  

---

### Answer by username_5 on 2013-11-16. Score: 0

This question is similar to the "Computability Theory". This theory studies the problem of "What problems can be computed by a computing machine?"! Well! We need a model for that machine!

This is exactly the case here, from my point of view if I am correct. They did not consider a computational model for quantum computer or maybe they believe, as Prof @username_1pointed out, they do not know all the quantum laws.

To sum it up, the question here is that are all quantum systems computable by a quantum computer?

> **Comments:**
> **username_1**: They do give an exact computational model for a quantum computer, and this quote comes from the chapter in which they give it.  

---

