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?

$\endgroup$
  • 7
    $\begingroup$ Because we don't know the laws of physics for certain? $\endgroup$ – Peter Shor Nov 16 '13 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 '13 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 '13 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 '13 at 11:42
  • 1
    $\begingroup$ @PeterShor Your comments make a good answer. $\endgroup$ – Mohammad Al-Turkistany Nov 17 '13 at 15:55
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.

$\endgroup$
  • $\begingroup$ In that case I would like to know the ground of 'high confidence' mentioned by the authors. $\endgroup$ – Omar Shehab Nov 19 '13 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?

$\endgroup$
  • 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 '13 at 20:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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