Major Breakthrough In Quantum Computing Shows That MIP* = RE (arxiv.org) 28
Slashdot reader JoshuaZ writes:
In a major breakthrough in quantum computing it was shown that MIP* equals RE. MIP* is the set of problems that can be efficiently demonstrated to a classical computer interacting with multiple quantum computers with any amount of shared entanglement between the quantum computers. RE is the set of problems which are recursive; this is essentially all problems which can be computed.
This result comes through years of deep development of understanding interactive protocols, where one entity, a verifier, has much less computing power than another set of entities, provers, who wish to convince the verifier of the truth of a claim. In 1990, a major result was that a classical computer with a polynomial amount of time could be convince of any claim in PSPACE by interacting with an arbitrarily powerful classical computer. Here PSPACE is the set of problems solvable by a classical computer with a polynomial amount of space. Subsequent results showed that if one allowed a verifier able to interact with multiple provers, the verifier could be convinced of a solution of any problem in NEXPTIME, a class conjectured to be much larger than PSPACE. For a while, it was believed that in the quantum case, the set of problems might actually be smaller, since multiple quantum computers might be able to use their shared entangled qubits to "cheat" the verifier. However, this has turned out not just to not be the case, but the exact opposite: MIP* is not only large, it is about as large as a computable class can naturally be.
This result while a very big deal from a theoretical standpoint is unlikely to have any immediate applications since it supposes quantum computers with arbitrarily large amounts of computational power and infinite amounts of entanglement.
The paper in question is a 165 tour de force which includes incidentally showing that the The Connes embedding conjecture, a 50 year old major conjecture from the theory of operator algebras, is false.
In a major breakthrough in quantum computing it was shown that MIP* equals RE. MIP* is the set of problems that can be efficiently demonstrated to a classical computer interacting with multiple quantum computers with any amount of shared entanglement between the quantum computers. RE is the set of problems which are recursive; this is essentially all problems which can be computed.
This result comes through years of deep development of understanding interactive protocols, where one entity, a verifier, has much less computing power than another set of entities, provers, who wish to convince the verifier of the truth of a claim. In 1990, a major result was that a classical computer with a polynomial amount of time could be convince of any claim in PSPACE by interacting with an arbitrarily powerful classical computer. Here PSPACE is the set of problems solvable by a classical computer with a polynomial amount of space. Subsequent results showed that if one allowed a verifier able to interact with multiple provers, the verifier could be convinced of a solution of any problem in NEXPTIME, a class conjectured to be much larger than PSPACE. For a while, it was believed that in the quantum case, the set of problems might actually be smaller, since multiple quantum computers might be able to use their shared entangled qubits to "cheat" the verifier. However, this has turned out not just to not be the case, but the exact opposite: MIP* is not only large, it is about as large as a computable class can naturally be.
This result while a very big deal from a theoretical standpoint is unlikely to have any immediate applications since it supposes quantum computers with arbitrarily large amounts of computational power and infinite amounts of entanglement.
The paper in question is a 165 tour de force which includes incidentally showing that the The Connes embedding conjecture, a 50 year old major conjecture from the theory of operator algebras, is false.
Re: Achtung, Computer Scientists!!! (Score:3, Insightful)
Part of the sentence missing? (Score:2)
sounds to me like "I just the whole thing?"...
What does "can be demonstrated to a computer" mean here?
Re: (Score:3)
Re: (Score:3)
It means the classical computer is acting as a verifier of a solution's proof, as described later in the summary. Don't feel bad, though; the whole summary is written terribly in terms of conveying what the supposed breakthrough means to anyone who is not familiar with theoretical research in computational complexity.
Re: (Score:3)
The whole summary is written terribly, period.
Re: Part of the sentence missing? (Score:2)
Maybe that terrible period's terrible author's on a terrible period, period,,,?
Re: (Score:1)
the whole summary is written terribly in terms of conveying what the supposed breakthrough means to anyone who is not familiar with theoretical research
You mean it was copied from Wikipedia?
Nah, contains too much concrete information. (Score:2)
Wikipedia has the policy of never ever specifically stating what it is in the first paragraph of the article. ;)
(And then starting with a chapter about the etymology and that huge one where somebody barfed out formulas with obscure symbols and words nobody ever heard of. Once, I tried to show it to a buddy, by reading it out loud. Accidentially summoned Cthulhu.)
Re: (Score:2)
The author had to pay by the word - so he dropped a number of them to fit into his budget.
Great! (Score:5, Funny)
I totally understand what they mean and am also excited by the result. The math thing which I totally understand and is what I've been saying all along. Great job on the thing which I grasp entirely and am not just saying that so people don't think I'm dumb.
Re: Great! (Score:2)
Dude, that's not how you do it. You just give a slight smile and nod comprehendingly and people assume you understand
Re: Great! (Score:3)
Re: (Score:2)
The math thing which I totally understand and is what I've been saying all along. Great job on the thing which I grasp entirely and am not just saying that so people don't think I'm dumb.
But isn’t this paper proof you don’t need to do the math? Feasibly verifying a provided answer is all you would ever need. I’m... Stunned! ... We have now simultaneously proven, lol, that, actually lol, we don’t need to show all our work if we can just show its true ... and ... vindication that college professors were full of crap every time they marked you off points for just answering correctly and not showing all your work.
I’m gonna take a break to write a strongly wor
A Million Instructions Per Wildcard = One Regular (Score:2)
Theoretical = dick (Score:2)
Sounds like another "possible" theory.
The following assumes the existence of negative mass/energy.
If this negative mass/energy matter exists, then creating both a supermassive black hole and the negative mass/energy counterpart to it, while then connecting them, should allow for a traversible wormhole.
Easy, peasie, right?
I really wish these people would honestly start their art
Here is why it's important (Score:5, Informative)
Here is why showing that these two classes are equivalent is important. It's not about the definition - nobody thinks there could be infinitely powerful quantum computers. Each class contains many problems. They can each be converted one into the other, much like division can be converted to multiplication (of the inverse) and multiplication can be converted to repeated addition. That means the problems are equally "hard".
If you prove that ANY problem is harder than X, you've proved that ALL problems in the class are that hard. Such a thing would be useful for cryptography / security for example. It would also be important for further math research - no need to look for better solutions after it's been proved that they don't exist.
By proving that the classes are equal, that means anything proved about how hard any problem in any class is, also applies to all problems in both classes.
So for example if you prove that a particular RE is NOT in this class, that means it'll never be solved by quantum computers - because it can't even be solved by an infinitely powerful one.
Re: (Score:2)
Sure, it is just a math thing. It has absolutely nothing to do with any sort of computer, including a quantum computer.
If you suppose a certain set of math operators, then all the stuff can be calculated with them instead of using all the real math that is used to "prove" it.
It is basically a really really big algebra mathpeen.
There is no useful machine with those operators, though. That would be necessary for it to have anything to do with "computers."
A true "working" paper! (Score:4, Funny)
Wow. This paper "works" for me on multiple levels.
First, it's not afraid to start at the basics. The gist of it can be understood with little more than Wikipedia, and the references include some thorough text books and accessible papers.
Second, the writing "works". The style and language is not just accessible, but also friendly in tone. It is an inviting piece of writing.
Third, the proof "works". Both as exposition and process. Even if you have no interest in MIP* and RE, this proof is a model that deserves to be understood at a structural level. It is so lucid that, even though I'm still far from understanding the details, its form and flow have affected how I think about such things. It's that rare kind of proof/exposition that lets me "think along" with it, making me feel like my brain is working better than normal.
I'm also amazed there are only 3 pages of references. That alone makes deeper study more practical. Should I ever decide to do so...
Like I said: Wow.
Re: (Score:2)
Mistake in the summary (Score:5, Informative)
RE is not the set of problems which are recursive, it's the set of problems that are recursively enumerable.
As anyone who paid attention in theory of computation classes, vaguely remembered there was a difference, and looked it up on Wikipedia can tell you, R is a proper subset of RE. Recursive languages are decidable (i.e. there is a Turing machine that always halts and says "in" or "out") and RE problems are semi-decidable (i.e. there is a TM that always halts if it's "in" but may not halt if it's "out").
Informally, RE means we can computationally find a solution if it exists, but not always tell if it doesn't exist.
Re: (Score:2)
Re: (Score:2)
A few notes (Score:3)
For people looking to know if this will impact you (Score:3)
No, this result will not impact your everyday life. MIP* relies on access to all-powerful "oracle" computers that are assumed to be able to compute the correct answer by magic. This is just saying that if we did have these impossible to build computers, we would be able to build an architecture (using 2+ all-powerful computers and 1 classical computer) that would be practical regardless of quantum uncertainty, and would be able to solve anything in RE (which is basically everything, as other commenters have noted).
MIP is a thought experiment where you have two or more all-powerful computers that are unreliable, and another reliable normal computer that is working to verify what the unreliable computers said. It turns out that you need 2 unreliable computers because a smart enough single malicious unreliable computer can fake out your verifying computer (and this is pretty realistic considering they have infinite computing power at their disposal), but two unreliable computers acting independently are not able to do so. MIP* actually makes it harder on the verifier by allowing the unreliable computers to be quantum entangled with each other, so their answers could be correlated. Lastly, the verifier can interrogate the two unreliable computers as many times as it needs, up to a polynomial limit of interrogations (otherwise you might end up taking exponential time in interrogations, making it impractical).
But yeah, this isn't directly useful because we can't build all-powerful computers.
That said, this is some very impressive math, especially since they solved an open problem in the process, and you never know when it or something derived from it could turn out useful (a similar result for MIP ended up proving that not all NP problems could be approximated).
Additionally, this result increases the optimism that we will be able to deal with quantum uncertainty in real quantum computers dealing with realistic problems, but we can't be sure yet.