SoylentNews is people
SoylentNews
from the just-when-you-thought-you-knew-how-things-worked dept.
Major quantum computational breakthrough is shaking up physics and maths:
MIP* = RE is not a typo. It is a groundbreaking discovery and the catchy title of a recent paper in the field of quantum complexity theory. Complexity theory is a zoo of "complexity classes" – collections of computational problems – of which MIP* and RE are but two.
The 165-page paper shows that these two classes are the same. That may seem like an insignificant detail in an abstract theory without any real-world application. But physicists and mathematicians are flocking to visit the zoo, even though they probably don't understand it all. Because it turns out the discovery has astonishing consequences for their own disciplines.
[...] RE stands for problems that can be solved by a computer. It is the zoo. Let's have a look at some subclasses.
[...] Allowing the provers of MIP to share an entangled qubit leads to the class MIP*.
It seems obvious that communication between the provers can only serve to help the provers coordinate lies rather than assist the interrogator in discovering truth. For that reason, nobody expected that allowing more communication would make computational problems more reliable and solvable. Surprisingly, we now know that MIP* = RE. This means that quantum communication behaves wildly differently to normal communication.
IP = Interactive Polynomial time solvable using an interactive proof.
MIP = Multiple Interactive Provers that are not allowed to communicate between each other.
RE = Recursively Enumerable.
[Edited to add a definition for RE and to correct the definition of IP. - Ed]
(Score: 1) by anubi on Saturday August 22 2020, @05:47PM
I sure miss the older simpler times when a "proof" was not much more than physical evidence I had not forgotten to put film in the camera before I took the photo.
"Prove all things; hold fast that which is good." [KJV: I Thessalonians 5:21]
(Score: 3, Funny) by fustakrakich on Saturday August 22 2020, @06:24PM (5 children)
Are we delving into "million monkeys" territory here?
La politica e i criminali sono la stessa cosa..
(Score: 2) by RamiK on Saturday August 22 2020, @07:05PM (4 children)
Don't forget the Beowulf clusters..
compiling...
(Score: 1) by fustakrakich on Saturday August 22 2020, @07:17PM
Well, with all the chatter, it certainly won't be very Zen...
Maybe if they modulate the amplitude of the noise, they can transmit a useful signal
La politica e i criminali sono la stessa cosa..
(Score: 3, Funny) by mhajicek on Sunday August 23 2020, @04:58AM (2 children)
Imagine a Beowulf cluster of monkeys!
The spacelike surfaces of time foliations can have a cusp at the surface of discontinuity. - P. Hajicek
(Score: 2) by RamiK on Sunday August 23 2020, @07:22AM (1 child)
Quantum monkeys they all banned me COVID19...
compiling...
(Score: 2) by RamiK on Sunday August 23 2020, @07:25AM
Quantum monkeys < sea monkeys < monkeys < humans < quantum monkeys
So there you have it, at the quantum scale, solutions prove you!
p.s. normally I'd save this "quality" material for comp&math conferences but
they all banned meCOVID19...p.p.s. repost since last submit got chewed and spit by the html parser due to the less-than symbols...
compiling...
(Score: 5, Interesting) by bzipitidoo on Saturday August 22 2020, @07:23PM (2 children)
I have studied but not kept up with Complexity Theory, and am not familiar with MIP* and RE. The Wikipedia article on Complexity Theory doesn't mention those classes. Sounds like RE contains PSPACE.
I find a maze a useful analogy for these problems. If you know which turn to take at every intersection, you can solve a maze very quickly. Or, if you have an army of travelers, enough to try all the passages simultaneously, that works too, for quickly finding the solution. Without those things, a maze could take an impractically long time to solve. This is the essence of the class of NP hard (NP or harder) problems. That's the basic idea behind such things as combination locks.
The million dollar question of whether P=NP I like to think is asking whether there are shortcuts that can help a wanderer in a maze pick the branch that leads to an answer. For instance, if the maze is 2D, and the start and finish are openings in the outer wall, and while within the maze, the traveler can somehow know they have reached an outer wall, and know which side of their passage the exit is on, they can dismiss all the passages on the opposite side, which on average should be half the passages. Similarly with any loop. All the passages inside the loop can be dismissed. Whether there are enough such things for any NP problem is the question. I think not. If I could prove it, I'd be a millionaire.
(Score: 2) by Barenflimski on Saturday August 22 2020, @07:43PM
Outside of P=NP, I don't have a clue about what you're talking about. I modded that interesting because it sounds like the words you wrote should be together and it was mostly new to me.
Thanks for this!
(Score: 2, Interesting) by Anonymous Coward on Sunday August 23 2020, @08:03AM
RE stands for recursively enumerable, it's the set of all computable functions and encompasses every other complexity class. MIP* is new to me so I may be wrong about this but here's my understanding of it.
One of the definitions of NP is that a decision problem in NP is verifiable in polynomial time, in your maze example it may take a long time to find a path through through the maze but if someone gives you a path it's easy to check whether it's correct (just follow it and see if it leads you out).
Some problems could be a lot harder to check than that though, in a sense these are harder still than NP as even if you're given the answer there's no easy way to verify it's correct. A solution to this is to come up with some heuristics that you can have the algorithm output along with the answer and these help reassure you the answer is valid, from my understanding thats IP.
MIP is an extension of this where you use multiple methods of finding a solution and cross check the results against each other which gives you more power than checking everything yourself. Of course you want these 2 systems to be independent otherwise an error in one could spread to the other and mess up your cross checking.
This seems to be saying that in the quantum world you actually get more power by allowing the different methods to share information, in fact you get so much more power that the set of problems that you can verify is equal to all functions that can be computed (MIP* = RE).
The reason this is so big is that it proves that if something can be computed *at all* then it's also possible to verify the solution is correct with less work than it took to prove it.
(Score: 3, Insightful) by ledow on Saturday August 22 2020, @09:42PM (1 child)
I studied computer science.
And that summary sucks.
(Score: 0) by Anonymous Coward on Sunday August 23 2020, @02:00AM
I did not study CS, and came here for this comment, thankyou, even if i am still none the wiser.
Suppose all will be well, if i can better read homeapathy articles on pirutebay, without the man imuning my rightts wecan all move forward.