Classical problem becomes undecidable in a quantum setting

(Phys.org) -- 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.

The physicists, Jens Eisert and Christian Gogolin from the Free University of Berlin in Germany, along with Markus P. Müller from the Perimeter Institute for Theoretical Physics in Waterloo, Ontario, Canada, have published their study in a recent issue of Physical Review Letters.

“We present a novel twist present in quantum mechanics, absent in its classical counterpart: 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.”

The problem in question involves a measurement device that generates any one of multiple outputs depending on the outcome of the measurement. The output state is then fed back into the device as the input, leading to a new output, and the process repeats. The question is whether there exist any finite sequences of measurement outcomes that never occur.

“The problem as such is simple - merely asking whether certain outcomes can occur in quantum measurements,” Eisert said.

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.

“In a way, one can say that it is undecidable whether certain processes are allowed by quantum mechanics or not; quite a puzzling situation,” Eisert said.

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.

Besides being an interesting example of the complexity of the quantum world, the results could be expanded to show that problems in other areas are undecidable, as well. For example, a similar mathematical description applies to the quantum wires used in measurement-based quantum computing devices, suggesting that no algorithm can identify sequences of measurement outcomes that will never occur. Undecidability may also occur frequently in many-body problems. In these cases, knowing that certain problems are undecidable could give physicists a new perspective of these problems.

“We establish a novel link between quantum physics and computer science: Some problems are not only computationally hard to decide (such as finding ground states of glassy quantum many-body models can be QMA-hard), it is absolutely impossible to decide, with all computational power available and all available running time in the world, as a matter of principle!” Eisert said. “A computer trying to do this would simply run on and on and on. This surprising fact highlights a novel facet of quantum mechanics that was previously unknown. Also, it shows that not only academic problems on Turing machines in computer science can be undecidable, but in fact, natural, physical and intuitive ones as well.”

In the future, the physicists plan to explore the possibility of using undecidability as a “proof tool” for validating ideas.

“It all could amount to a powerful new proof tool,” Eisert said. “Say, if one could find the intriguing result that it is undecidable whether a state is distillable or not, one would have solved the long-standing problem on the existence of NPT bound entanglement [a problem that has implications for quantum information theory] in a very indirect way.

“There is a lot of exciting work to be done. Then, we may understand a bit more clearly what this really says about quantum mechanics as a physical theory and what this says about nature as such.”

Copyright 2012 Phys.org
All rights reserved. This material may not be published, broadcast, rewritten or redistributed in whole or part without the express written permission of PhysOrg.com.