(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.”

**Explore further:**
Too much entanglement can render quantum computers useless

**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

## 210

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

## Torbjorn_Larsson_OM

@ 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

## vacuum-mechanics

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

Fascinating.

## antialias_physorg

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

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

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

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

http://arxiv.org/abs/1111.3965

## Claudius

## tgoldman

## ubavontuba

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

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

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

"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

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.