Major quantum computational breakthrough is shaking up physics and maths
theconversation.com
theconversation.com
I'm also puzzled by the use of the word "convince" in there. Is it possible for such a quantum oracle to lie?
There are some white mice on Magrathea who hold the IP on this.
IP: The class of decision problems for which a "yes" answer can be verified by an interactive proof. Here a probabilistic polynomial-time verifier sends messages back and forth with an all-powerful prover. There are some additional stipulations about the probability with which the verifier must accept or reject the prover’s claim.
MIP* is like IP but (a) you can have multiple provers and (b) the provers can share arbitrarily many entangled qubits.
MIP* = RE
One way to look at this is to think of MIP* as a subset of RE and then RE as a subset of MIP. RE being contained within MIP* isn’t very surprising - if it’s already in RE, then just clone a bunch of entangled copies of the “regular” Turing machine that already verifies “yes” answers in finite time and you’ve got your no-op MIP* version of the same thing. The hard part here (and where all the details that make the proof such an impressive achievement come in) is how to ensure the verifier doesn’t have to just trust the provers, for any general problem in RE, while still only running in polynomial time to achieve a certain level of probability of correctness.
MIP* \in RE is weird though.
Any decision problem where a verifier can polynomially verify a “yes” answer given info from multiple entangled provers must also be a problem where there exists a “regular” Turing machine that can verify a “yes” answer in finite time.
What’s surprising is that the “collusion” of multiple entangled provers never presents the verifier with something they can polynomially verify such that some other “regular” Turing machine couldn’t.
You don’t “get more” or “get extra” out of their being multiple provers that can “work together” in a sense. It turns out to be no different than the class of problems where a “yes” answer was already easy (finite time) to verify.
One careful point to note is that the only place in this where polynomial time comes into play is the process of the verifier validating a “yes” answer from the provers in MIP.
The process of the provers themselves may not be polynomial (though, for “yes” answers it is clear it must be finite).
RE problems are not necessarily efficiently verifiable. For example the Halting Problem itself is in RE.
The finite verifier for a “yes” answer is to run for the finite amount of time it takes to halt for that example. The MIP interactive proof could be running several of those in parallel and just ignore any entanglement and ask each one “have you halted?” They will all wait around for the finite amount of time it takes to halt and then say “yes” and the verifier can just check they all said yes (O(n) where n is number of provers). But again the trick is how to modify that algorithm so the verifier doesn’t just have to believe the provers, and the authors of the proof give that explicitly for the Halting Problem on page 154 of the paper.
Side note: it’s really hard writing prose with a term that needs an asterisk on HN - apologies for weird italics and “MIP” when it should be “MIP*”.
This is a little misleading. The set of TMs that halt is in RE. But the halting problem requires you to construct the complement of this set, and that is not in RE.
"In computability theory and computational complexity theory, RE (recursively enumerable) is the class of decision problems for which a 'yes' answer can be verified by a Turing machine in a finite amount of time."
But the halting problem requires you to produce a YES OR NO answer within a finite time. That's the whole point.
> “ Examples of RE-complete problems: > Halting problem: Whether a program given a finite input finishes running or will run forever.”
Huh? That is indeed the halting problem. More formally "given some turing machine H and an input x, decide whether H halts on x." But it is of course trivially semi-decidable.
>determining whether a program halts or does not halt
That is equivalent to the formulation mentioned above, since if we had a decider W for the halting problem then H(x) halts iff W(H, x) accepts and halts, and H(x) does not halt iff W(H, x) rejects and halts.
I think your confusion stems from the fact that if we had a decider for the halting problem, then the halting problem would be in R. But the fact that the halting problem is undecidable (i.e. not in R) means it is in RE but not co-RE.
Unfortunately, it is too late for me to go back and edit my erroneous comment.
<Φ| they would not provide any speedup for most everyday computations.
<Φ| For many everyday computations where they provide speedup they provide only quadratic speedup (see Grover's algorithm)
<Φ| They can't interact with the environment when they are doing calculations.
They can help out with pretty neat stuff and could make for an awesome special purpose co-processor, but they'll be cloud-only for quite a while.
It would probably be an add-on, kind of like a GPU (if we massively solve all the engineering problems), but only for people working on problems that need it. Sort of like how GPUs are a thing now, but most web servers dont have one because they are useless for your typical web server.