4
$\begingroup$

Let me quote from the section 9.3 of Classical and Quantum Computation 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?

Improve this question
$\endgroup$
10
  • 7
    $\begingroup$ Because we don't know the laws of physics for certain? $\endgroup$
    – Peter Shor
    Nov 16, 2013 at 14:04
  • 1
    $\begingroup$ 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 and accompanying blog post. $\endgroup$
    – Artem Kaznatcheev ♦
    Nov 16, 2013 at 22:38
  • 3
    $\begingroup$ We will never be able to know for sure whether we have the right laws of physics, or just very good approximations. $\endgroup$
    – Peter Shor
    Nov 17, 2013 at 0:40
  • 1
    $\begingroup$ @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). $\endgroup$
    – Peter Shor
    Nov 17, 2013 at 11:42
  • 1
    $\begingroup$ @PeterShor Your comments make a good answer. $\endgroup$
    – Mohammad Al-Turkistany
    Nov 17, 2013 at 15:55

2 Answers 2

Reset to default
6
$\begingroup$

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 papers 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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ In that case I would like to know the ground of 'high confidence' mentioned by the authors. $\endgroup$
    – Omar Shehab
    Nov 19, 2013 at 4:22
0
$\begingroup$

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 @Peter Shor pointed 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?

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ They do give an exact computational model for a quantum computer, and this quote comes from the chapter in which they give it. $\endgroup$
    – Peter Shor
    Nov 18, 2013 at 20:57

Your Answer

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

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