Classical problem becomes undecidable in a quantum setting

Classical problem becomes undecidable in a quantum setting

To arrive at this conclusion, the physicists turned to a well-known computational problem called the halting problem, which was introduced by Alan Turing in 1936. The problem is to determine whether a program that receives an input will eventually finish running, i.e., “halt,” or whether the program will continue running forever. Turing showed that no single algorithm exists that can solve this problem for all possible inputs, so the problem is undecidable. Among the implications of the halting problem, it is related to Godel’s famous incompleteness theorem in mathematics.

In the current study, the physicists have shown that, if the quantum measurement problem dealing with impossible outputs could always be solved by some algorithm, then an algorithm must also exist that could solve every instance of the halting problem – which Turing showed is not possible.

When using a classical measurement device, the physicists show that they can always find an algorithm that can answer whether or not any outputs with zero probability exist. So in a classical context, the problem is decidable.

However, when using a quantum measurement device, the physicists show that there cannot be an algorithm that always provides the correct answer, and so the problem becomes undecidable. The scientists explain that the undecidability arises from interference in the quantum device, implying that, at least in this scenario, undecidability appears to be a genuine quantum property.

We are able to show that very natural, reasonable questions about quantum measurement are, intriguingly, undecidable,” Eisert told Phys.org. “At the same time, the corresponding classical problem is decidable.”

As a testament to how differently things work in the quantum and classical regimes, physicists have found that a problem that is easily solved in a classical context cannot be solved at all in a quantum context. The physicists think that the same situation applies to many other similar problems, which could have implications for quantum computing applications and quantum many-body models, which describe microscopic systems.