Classical problem becomes undecidable in a quantum setting

Jul 09, 2012 by Lisa Zyga feature
In a decision problem with three possible outcomes, is there an empty port through which the particle will never fly? When using a quantum measurement device, the answer is undecidable; no algorithm exists that can always provide the correct answer. Image credit: J. Eisert, et al. ©2012 American Physical Society

(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 , 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 as a physical theory and what this says about nature as such.”

Explore further: Progress in the fight against quantum dissipation

More information: J. Eisert, M. P. Müller, and C. Gogolin. “Quantum measurement occurrence is undecidable.” PRL 108, 260501 (2012). DOI: 10.1103/PhysRevLett.108.260501

Update:

Previous papers on undecidability include the following:

Michael Wolf, Toby Cubitt, and David Perez-Garcia. "Are problems in Quantum Information Theory (un)decidable?" arXiv:1111.5425v1 [quant-ph] arxiv.org/abs/1111.5425

Vincent D. Blondel, Emmanuel Jeandel, Pascal Koiran, Natacha Portier. "Decidable and undecidable problems about quantum automata." arXiv:quant-ph/0304082v1 arxiv.org/abs/quant-ph/0304082

Journal reference: Physical Review Letters search and more info website

4.9 /5 (25 votes)

Related Stories

Too much entanglement can render quantum computers useless

May 25, 2009

(PhysOrg.com) -- "For certain tasks, quantum computers are more powerful than their classical counterparts. The task to be performed is the same for quantum or classical systems. However, the former ones can do it in a more ...

Recommended for you

Progress in the fight against quantum dissipation

20 hours ago

(Phys.org) —Scientists at Yale have confirmed a 50-year-old, previously untested theoretical prediction in physics and improved the energy storage time of a quantum switch by several orders of magnitude. ...

A quantum logic gate between light and matter

Apr 10, 2014

Scientists at Max Planck Institute of Quantum Optics, Garching, Germany, successfully process quantum information with a system comprising an optical photon and a trapped atom.

User comments : 18

Adjust slider to filter visible comments by rank

Display comments: newest first

210
1 / 5 (2) Jul 09, 2012
Ya know, this follows! I have always wondered how one could shoe-horn the Uber robust Quantum processing paradigm into the imminently more limited classical electronics realm of Human-User processing and utility?!?!
The quantum world is so very 'other-worldly'; and subject to none of the constraints of a digital world but comfortable with a 'fuzzy' one, or fuzzy-on-steroids one!

Your thoughts please?

word-to-ya-muthas
tadchem
5 / 5 (1) Jul 09, 2012
Quantum mechanics, I would like to introduce to you Herr Kurt Gödel.
Torbjorn_Larsson_OM
1 / 5 (1) Jul 09, 2012
Interesting. I can't remember if they found the landscape (the set of possible universes) of string theory NP hard of just estimated it was. They can't solve it explicitly in all cases anyway, but having to try and then give up after a reasonable time makes it even worse.

@ tadchem:

Undecidable models are known before I imagine, at least in practice: let a large enough physical realization of a Turing machine work a small enough undecidable problem. The news seems to be that QM and CM differ in nature. (Maybe not so much news either.)

Undecidability isn't a problem, inconsistency would be. If physics is algorithmic in nature, as quantum field theory suggest (can't be axiomatized), the first is expected and the latter would be surprising.
dirk_bruere
1 / 5 (1) Jul 09, 2012
Does the universe solve the three body problem?
vacuum-mechanics
1 / 5 (3) Jul 09, 2012
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.


By the way, talking about quantum mechanics, we know that it is the outcome of the character of particle wave duality nature. And to understand it a bit more clearly, what we should do may be try to find out what the mechanism of the particle wave duality is. May be this paper could give some idea.

http://www.vacuum...id=17=en
ubavontuba
1 / 5 (1) Jul 10, 2012
So, if we conduct an experiment in the macro scale, the outcomes can be calculated, but using the same experiment in the quantum scale, anything might happen?

Fascinating.

antialias_physorg
5 / 5 (1) Jul 10, 2012
So, if we conduct an experiment in the macro scale, the outcomes can be calculated

Even at the macroscale anything can happen. The probabilities just drop so rapidly that a value close to the expected (read: calculated) becomes exceedingly likely.

Take coinflips.
1 coinflip may come up heads with 50% chance. I.e. you get 100% heads half the time. This is a huge result but at a 50/50 chance not precalculable.

If you take 1000 coinflips then the chance of getting 100% heads is 1 over 2 to the power of 1000 (which is an astronomically small number. If you do this experiment once for every atom in the universe youre not even close to standing a chance of seeing such an outcome).
But getting within a close range of 500/500 for heads/tails is very likely (range from 505-495 heads - which is 1% spread - is almost 25% likely. Being within 10 percent is already 99.99% likely).

Macroscopic systems have MANY more than 1000 elements with binary outcomes.
tadchem
not rated yet Jul 10, 2012
Does the universe solve the three body problem?

Yes, in a 1:1 scale physical model with real time.
If you are looking for a 'closed-form analytical' solution to the system of differential equations, then that is another problem. The orthogonal equations for a three-body system in 4-dimensional space-time are a beast to establish. There are not enough defineable conserved quantities (CoM, total momentum, angular momenta, total energy) to constrain all the degrees of freedom. The normal modes of motion are free to interact ("mix") in ways that are exquisitely sensitive to initial conditions (translation: 'chaotic').
tadchem
not rated yet Jul 10, 2012
Does the universe solve the three body problem?

Yes, in a 1:1 scale physical model with real time.
If you are looking for a 'closed-form analytical' solution to the system of differential equations, then that is another problem. The orthogonal equations for a three-body system in 4-dimensional space-time are a beast to establish. There are not enough defineable conserved quantities (CoM, total momentum, angular momenta, total energy) to constrain all the degrees of freedom. The normal modes of motion are free to interact ("mix") in ways that are exquisitely sensitive to initial conditions (translation: 'chaotic').
antialias_physorg
5 / 5 (1) Jul 10, 2012
Does the universe solve the three body problem?

The universe doesn't solve equations at all. If you want to look at it from a calculation point of view (which isn't correct, anyhow) it works in massive parallel on probabilty densities.

WE solve equations because your brains are evolved to (consciously) deal with one thing at a time. So we made up a tool which allows us to use exactly that facility to get a good approximation of what the universe does (math/physics).

Only with modern technology - which allows us to go more parallel with numeric simulations - do we start to approach what the universe 'does'.
ZachAdams
5 / 5 (2) Jul 10, 2012
The preprint version of the paper is available here:
http://arxiv.org/abs/1111.3965
Claudius
2.3 / 5 (3) Jul 10, 2012
It would be interesting if they had tried to solve this problem using a many-world's interpretation (i.e. David Deutsch's Multiverse) instead of assuming the Copenhagen interpretation is correct.
tgoldman
1 / 5 (2) Jul 10, 2012
Except that there is a flaw in Godel's argument and so also Turing: they apply only to countable sequences. The theorems do not apply to continua.
ubavontuba
1 / 5 (2) Jul 11, 2012
Even at the macroscale anything can happen. The probabilities just drop so rapidly that a value close to the expected (read: calculated) becomes exceedingly likely.
Yeah, I'm aware of the probabilities. In some ways I doubt this works on the macro scale at all, as we'd see some small item somewhere, sometime, all of a sudden "deciding" to be cold, or some such.

But then I lose my keys, search frantically for them, and then find them in plain sight where I'd swear I looked for them thoroughly already. "It's the quantum fluctuations." I'd tell you.

But seriously, I wonder if there is a demarcation, particularly in regards to spacetime, as recent experiments indicate spacetime is less granular than thought.

"space-time is smooth as Einstein predicted,"

http://www.nasa.g...ear.html
antialias_physorg
not rated yet Jul 11, 2012
as we'd see some small item somewhere, sometime, all of a sudden "deciding" to be cold, or some such.

The probabilities against this are just so enormous. And we'd have to measure it, too (it could happen - but if you don't see it you don't notice it).
The number of measurements you'd have to do to get even a one-in-a-universe-lifetime chance of recording such an event would be such that you'd have to convert a lot more than the entire universe's mass into recording apparatus.

Differential equations (and all of the exact calculations in physics) simply make use of that fact. They trim out all the improbables and just calculate the mean - because that is what happens in so many cases that we'll likely never see an exception - ever.

Now when you get to the microscale things look different. That's why we have quantum mechanics (we should use that on the macroscale, too. But the 'old' laws are god enough for that - and easier to use)
ubavontuba
1 / 5 (1) Jul 12, 2012
Now when you get to the microscale things look different. That's why we have quantum mechanics (we should use that on the macroscale, too. But the 'old' laws are god enough for that - and easier to use)
This brings us to the heart of what I was getting to. It looks like QM is a good descriptor for the tangible (mass/energy), but not the intangible (spacetime) even to the smallest scales.

I find that fascinating.

In short, mass/energy affects spacetime, and vice versa, but it appears they are distinct.

I wonder, which came first? LOL

Dr_Ron
not rated yet Jul 13, 2012
This article should be re-titled and repackaged as:
"Alan Turing's Halting Problem is rolled out to decide Classical vs. Quantum World Question."
Give him the credit he deserves. It is his year.
Tausch
1 / 5 (1) Jul 14, 2012
:)
Hut ab, Kurt. Postum. Grisha Perelman und Kurt Gödel sind meine Helden.

Der einer lebt noch. Der anderer nicht.
Beide gaben selblosen Beitäge ab - zum weiter Verständnis 'die Natur' - was nur aus der Sicht von Menchen sein können.

Einen anderen Wahl außerhalb der Sicht der Menschen/Dingen ist außerhalb unsere Vorstellungskraft und/oder Reichweite.

Einen Ansicht das als gut oder schlecht einzustufen ist - je nach persönlichen Einstellung.

More news stories

Robotics goes micro-scale

(Phys.org) —The development of light-driven 'micro-robots' that can autonomously investigate and manipulate the nano-scale environment in a microscope comes a step closer, thanks to new research from the ...

Net neutrality balancing act

Researchers in Italy, writing in the International Journal of Technology, Policy and Management have demonstrated that net neutrality benefits content creator and consumers without compromising provider innovation nor pr ...