Entangle Quantum Entangled Machines Can Verify Solutions Up to Halting Problem Hardness Level

A major new proof has combined Albert Einsteins Quantum Physics with Alan Turing’s Computing Theories.

The new proof shows that quantum entangled machines can be used to verify solutions to problems that are as complicated and hard as the halting problem. Turing showed that Halting problem cannot be solved but we can use entangled systems to help to verify solutions to problems where we cannot prove the complete solutions.

Entangled Quantum Computers Will Have Value in Solving Problems Beyond Classical Computers

Quantum computers that use entangled quantum bits or qubits will be capable verify answers to an incredibly vast set of problems. The correspondence between entanglement and computing was previously not proven and it was a surprise to most researchers.

They looked at the limits of computing using entanglement.

They settled two major problems:
* Tsirelson’s problem in physics, about how to mathematically model entanglement
* and a related problem in pure mathematics called the Connes embedding conjecture.

Halting and Turing

Turing proved that the halting problem is undecidable. There are problems where you will not know beforehand if you can solve them. You just have to run a program and try. But you will also not know if you should keep letting it run after using large amounts of resources.

Checking Results of Major Complicated Problems

Every big complicated problem has two major parts
* How hard is it to solve?
* How hard is it to verify that an answer is correct?

How do we check results of hard problems?

A powerful computer, the prover, proposes a solution to a problem.
Another less powerful computer, the verifier, asks the prover questions to determine whether the answer is correct.

In 1988 it was shown that using two provers with independent solutions is better for checking answers. You can cross-check and look for inconsistencies and get to a true or false determination of the answers in a shorter time.

In the early 2000s, computer scientists asked — How does it change the range of problems you can verify if you interrogate two provers that share entangled particles? ie can quantum effects help with hard problems?

Most assumed that entanglement worked against verification. Two suspects would have an easier time telling a consistent lie if they had some means of coordinating their answers.

Recently, scientists have realized that the opposite is true. Entangled particles helps to verify a much larger class of problems than you can without entanglement.

Entanglement makes it possible for the provers to come up with the questions themselves.

Computer scientists didn’t know the full range of problems that can be verified using entanglement. Until now.

The new proof shows interrogating entangled provers makes it possible to verify answers to unsolvable problems, including the halting problem.

You ask two entangled provers whether a problem will halt.

The entangled provers generate questions and win based on the coordination between their answers.

If the program does in fact halt, the provers should be able to win 100% of the time.
If it doesn’t halt, the provers should only win by chance — 50% of the time.

The new paper proves that the class of problems that can be verified through interactions with entangled quantum provers, a class called MIP*, is exactly equal to the class of problems that are no harder than the halting problem, a class called RE. The title of the paper states it succinctly: “MIP* = RE.”

By showing the two complexity classes are equal, the computer scientists proved that Tsirelson’s problem is false amd the Connes embedding conjecture is also false.

Here is the 165 paper with the proof Arxiv – MIP∗ = RE

This also seems to mean that true quantum entangled quantum computers will be able to answer fundamental problems that are beyond classical computers.

Wikipedia has an entry on Interactive Proof Systems.

SOURCES- Quanta Magazine, Arxiv
Written by Brian Wang, Nextbigfuture.com

9 thoughts on “Entangle Quantum Entangled Machines Can Verify Solutions Up to Halting Problem Hardness Level”

  1. No, the theorem doesn’t say a quantum computer is an oracle. It just says that if you already have some oracles, then entanglement can be used to convince you that the oracles aren’t lying.

    But since we can’t build oracles, this method for preventing lies isn’t useful in practice. It’s just a cool math result.

  2. I expect there to be some sort of transformation you can apply to your problem in order for it to match a finite class of problems which can then be submitted to the oracle for proof or disproof. Then it becomes a question of writing the translator which will look both inside and outside a lot like a compiler.

  3. Turing machine and Quantum physics in same paper. Every numberphile: Quantum computer solves halting problem! Clue: it’s unsolvable.

  4. I figure it’s all about (1) programability and (2) general applicability. Defining the problem and converting it into some kind of executable request and then making sense of the ‘output’. Having a general use software interface to a general usage ‘quantum’ hardware ‘solver’. This seems to be a way off. Having to assemble a system for each problem – is that scalable, manufacturable, and widely distributable? — or will there be a centralized ‘solver’ for which you have to make a request and enter the queue — like the punch card systems in a few universities over 75 years ago? I sense a slow roll-out to very limited access for a long time.

  5. Big deal if true. That makes quantum computers of this kind the equivalent of oracle machines, which were by definition thought not to exist.

    But as with any ground breaking work, let’s wait for the refutations and comments.

Comments are closed.