11

As far as I understand a Universal Quantum Simulator can simulate any quantum system and thus anything that exists in the universe. Also, a quantum computer can implement such a quantum simulator. Further, from what I've read, a quantum computer does not have the ability to compute something that is not computable by a classical Turing Machine, although it can perform certain computations much more efficiently.

However, I recently saw this: Classical problem becomes undecidable in a quantum setting. The actual paper: Quantum measurement occurrence is undecidable

I don't understand this, unfortunately, so I wanted to ask, does this mean that physics is not computable by a classical computer (Turing Machine)? What about by a quantum computer? Or is this article saying something different altogether?

Kitchi
  • 3,709
user21359
  • 113

1 Answers1

3

The article is saying something different altogether.

There is a difference between being able to run a program (Turing machine) and being able to decide whether that program evenutally finishes running. The latter is called a $\Pi_1$ decision problem.

A classical computer can run any given program, subject to resource limitations, but there is no general algorithm to decide whether a given program will ever finish.

The article has come up with a type of physical system and a decision problem for it. It solves the decision problem for the classical version of the system and proves that decision problem for the quantum version of the system is undecidable. This doesn't mean that a classical computer can't simulate the quantum version of the system. It means that, in general, it can't answer a certain question about what might eventually happen (and neither can a quantum computer answer the question).

Retarded Potential
  • 2,045