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 dont understand it all. Because it turns out the discovery has astonishing consequences for their own disciplines.
In 1936, Alan Turing showed that the Halting Problem algorithmically deciding whether a computer program halts or loops forever cannot be solved. Modern computer science was born. Its success made the impression that soon all practical problems would yield to the tremendous power of the computer.
But it soon became apparent that, while some problems can be solved algorithmically, the actual computation will last long after our Sun will have engulfed the computer performing the computation. Figuring out how to solve a problem algorithmically was not enough. It was vital to classify solutions by efficiency. Complexity theory classifies problems according to how hard it is to solve them. The hardness of a problem is measured in terms of how long the computation lasts.
RE stands for problems that can be solved by a computer. It is the zoo. Lets have a look at some subclasses.
The class P consists of problems which a known algorithm can solve quickly (technically, in polynomial time). For instance, multiplying two numbers belongs to P since long multiplication is an efficient algorithm to solve the problem. The problem of finding the prime factors of a number is not known to be in P; the problem can certainly be solved by a computer but no known algorithm can do so efficiently. A related problem, deciding if a given number is a prime, was in similar limbo until 2004 when an efficient algorithm showed that this problem is in P.
Another complexity class is NP. Imagine a maze. Is there a way out of this maze? is a yes/no question. If the answer is yes, then there is a simple way to convince us: simply give us the directions, well follow them, and well find the exit. If the answer is no, however, wed have to traverse the entire maze without ever finding a way out to be convinced.
Such yes/no problems for which, if the answer is yes, we can efficiently demonstrate that, belong to NP. Any solution to a problem serves to convince us of the answer, and so P is contained in NP. Surprisingly, a million dollar question is whether P=NP. Nobody knows.
The classes described so far represent problems faced by a normal computer. But computers are fundamentally changing quantum computers are being developed. But if a new type of computer comes along and claims to solve one of our problems, how can we trust it is correct?
Imagine an interaction between two entities, an interrogator and a prover. In a police interrogation, the prover may be a suspect attempting to prove their innocence. The interrogator must decide whether the prover is sufficiently convincing. There is an imbalance; knowledge-wise the interrogator is in an inferior position.
In complexity theory, the interrogator is the person, with limited computational power, trying to solve the problem. The prover is the new computer, which is assumed to have immense computational power. An interactive proof system is a protocol that the interrogator can use in order to determine, at least with high probability, whether the prover should be believed. By analogy, these are crimes that the police may not be able to solve, but at least innocents can convince the police of their innocence. This is the class IP.
If multiple provers can be interrogated, and the provers are not allowed to coordinate their answers (as is typically the case when the police interrogates multiple suspects), then we get to the class MIP. Such interrogations, via cross examining the provers responses, provide the interrogator with greater power, so MIP contains IP.
Quantum communication is a new form of communication carried out with qubits. Entanglement a quantum feature in which qubits are spookishly entangled, even if separated makes quantum communication fundamentally different to ordinary communication. 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.
In the 1970s, Alain Connes formulated what became known as the Connes Embedding Problem. Grossly simplified, this asked whether infinite matrices can be approximated by finite matrices. This new paper has now proved this isnt possible an important finding for pure mathematicians.
In 1993, meanwhile, Boris Tsirelson pinpointed a problem in physics now known as Tsirelsons Problem. This was about two different mathematical formalisms of a single situation in quantum mechanics to date an incredibly successful theory that explains the subatomic world. Being two different descriptions of the same phenomenon it was to be expected that the two formalisms were mathematically equivalent.
But the new paper now shows that they arent. Exactly how they can both still yield the same results and both describe the same physical reality is unknown, but it is why physicists are also suddenly taking an interest.
Time will tell what other unanswered scientific questions will yield to the study of complexity. Undoubtedly, MIP* = RE is a great leap forward.
The rest is here:
- New History of the Physics Department by Raj Gupta and Paul Sharrah Published - University of Arkansas Newswire - March 3rd, 2021
- New research indicates the whole universe could be a giant neural network - The Next Web - March 3rd, 2021
- Roivant Grows Computational Drug Discovery Engine with Acquisition of Silicon Therapeutics - Business Wire - March 3rd, 2021
- Physics - The Tiniest Superfluid Circuit in Nature - Physics - February 27th, 2021
- Can god be disproved using the laws of physics? An expert explains how it depends on perspective - Scroll.in - February 27th, 2021
- How philosophy blends physics with the idea of free will - Big Think - February 27th, 2021
- Exclusive! Ashwin Sanghi on his dream to cast Sushant Singh Rajput in 'Keepers Of The Kalachakra' series: He was like an excited child when it came to... - February 27th, 2021
- SD Times Open-Source Project of the Week: PennyLane - SDTimes.com - February 27th, 2021
- Google Teams With D-Wave in Massive Quantum Computing Leap, Cracking Simulation Problem - The Daily Hodl - February 27th, 2021
- Tech Talk: Universe or multiverse? | Free - Ashland Daily Press - February 27th, 2021
- Physicists Show a Speed Limit Also Applies in the Quantum World - SciTechDaily - February 25th, 2021
- Can the laws of Physics help settle the debate over the existence of God? - Firstpost - February 25th, 2021
- OU appoints three to rank of Distinguished Professor - 2021 - Office of the Provost - News - OU Magazine - News at OU - February 25th, 2021
- Mid-Atlantic Quantum Alliance Expands Impact and Reach with Addition of 10 New Partners - PR Web - February 25th, 2021
- Everything you need to know about quantum physics (almost ... - February 22nd, 2021
- Quantum mechanics - Wikipedia - February 22nd, 2021
- Six Things Everyone Should Know About Quantum Physics - February 22nd, 2021
- A new Approach Could Tease out the Connection Between Gravity and Quantum Mechanics - Universe Today - February 22nd, 2021
- And So It Begins Quantum Physicists Create a New Universe With Its Own Rules - The Daily Galaxy --Great Discoveries Channel - February 22nd, 2021
- IBM adds 10 historically Black colleges and universities to quantum computing center - TechRepublic - February 22nd, 2021
- Physicists Need to Be More Careful with How They Name Things - Scientific American - February 22nd, 2021
- Can the laws of physics disprove God? - The Conversation UK - February 22nd, 2021
- Planet Earth Report The Quantum Century to Events That Could Have Ended Humanity - The Daily Galaxy --Great Discoveries Channel - February 22nd, 2021
- A New Measurement of Quantum Space-Time Has Found Nothing Going On - ScienceAlert - February 22nd, 2021
- With a $50,000 Grant, Black Quantum Futurism Will Continue to Disrupt Space and Time - GalleristNY - February 22nd, 2021
- Gravity May Play a Tiny But Important Role in The Microworld of Particle Physics - ScienceAlert - February 22nd, 2021
- IBM Adds Future Developer And Software Details To Its Quantum Roadmap - Forbes - February 22nd, 2021
- Physics - A Superconducting Qubit that Protects Itself - Physics - February 22nd, 2021
- Black Quantum Futurism receives the Knight Foundations new art and technology fellowship - WHYY - February 22nd, 2021
- What science tells us about the quantum origin of the universe - Sunday Vision - February 22nd, 2021
- Quantum Mechanics, Free Will and the Game of Life - Scientific American - February 14th, 2021
- Quantum Theory Proposes That Cause and Effect Can Go In Loops - Universe Today - February 14th, 2021
- The search for dark matter gets a speed boost from quantum technology - The Conversation US - February 14th, 2021
- Microsofts Big Win in Quantum Computing Was an Error After All - WIRED - February 14th, 2021
- Kangaroo Court: Quantum Computing Thinking on the Future - JD Supra - February 14th, 2021
- New EU Consortium shaping the future of Quantum Computing USA - PRNewswire - February 14th, 2021
- 2020 Quantum Communications in Space Research Report: Quantum Communications are Expected to Solve the Problem of Secure communications First on... - February 14th, 2021
- Mutually unbiased bases and symmetric informationally complete measurements in Bell experiments - Science Advances - February 14th, 2021
- Yale Quantum Institute Co-sponsored Event - Alternative Realities for the Living - Quantum Physics & Fiction - Yale News - February 14th, 2021
- Dont Tell Einstein, but Black Holes Might Have Hair - WIRED - February 14th, 2021
- A Magnetic Twist to Graphene Could Offer a Dramatic Increase in Processing Speeds Compared to Electronics - SciTechDaily - February 14th, 2021
- The Interplay between Quantum Theory And Artificial Intelligence - Analytics India Magazine - February 14th, 2021
- In Violation of Einstein, Black Holes Might Have 'Hair' - Quanta Magazine - February 14th, 2021
- Dr. William Audeh - The Gazette - February 10th, 2021
- Quantum Physics | Rakuten Viki - February 6th, 2021
- Switching Nanolight On and Off | Columbia News - Columbia University - February 6th, 2021
- Scientists narrow down the 'weight' of dark matter trillions of trillions of times - Livescience.com - February 6th, 2021
- The Super Bowl: What is time? - SB Nation - February 6th, 2021
- 'Friends' Star Matthew Perry Dated Julia Roberts By Wooing Her With Quantum Physics and Funny Jokes - Showbiz Cheat Sheet - February 6th, 2021
- A world-first method to enable quantum optical circuits that use photons - Tech Explorist - February 6th, 2021
- Quantum Physics Story Helgoland to Be Adapted by Fremantles The Apartment, CAM Film (EXCLUSIVE) - Variety - February 2nd, 2021
- Quantum physics and romance collide in the streaming production of Constellations - Chicago Reader - February 2nd, 2021
- 'A Glitch in the Matrix' Director Was Skeptical About Simulation Theory Until He Started Doing Research - IndieWire - February 2nd, 2021
- Record-Breaking Source for Single Photons Developed That Can Produce Billions of Quantum Particles per Second - SciTechDaily - February 2nd, 2021
- Can public clouds fix the developer experience in the HPC domain? - Forbes - February 2nd, 2021
- 29 Scientists Came Together in the "Most Intelligent Photo" Ever Taken - My Modern Met - February 2nd, 2021
- Silence your stoner friends with this video of a room entirely constructed out of mirrors - The A.V. Club - February 2nd, 2021
- Valuable contributor to society - The Tribune India - February 2nd, 2021
- Copperizing the Complexity of Superconductivity - Newswise - February 2nd, 2021
- A Zoom with a view: Wintersession offers a virtual journey from the kitchen to Hollywood - Princeton University - February 2nd, 2021
- IBMs top executive says, quantum computers will never reign supreme over classical ones - The Hindu - January 29th, 2021
- How quantum is it? U of T physicist Aaron Goldberg may have the answer - News@UofT - January 29th, 2021
- Wormholes May Be Lurking in the Universe Here Are Proposed Ways of Finding Them - SciTechDaily - January 29th, 2021
- The Convergence of Internet of Things and Quantum Computing - BBN Times - January 29th, 2021
- Who You Really Are And Why It Matters | Practical Ethics - Practical Ethics - January 29th, 2021
- The relativity principle of physics in technology - The National - January 29th, 2021
- If Wormholes Are Lurking in Our Universe, This Is How We Could Find Them - ScienceAlert - January 17th, 2021
- New quantum particle may have been accidentally discovered - New Atlas - January 13th, 2021
- Exploring the unanswered questions of our universe with quantum technologies - University of Birmingham - January 13th, 2021
- Wormholes may be lurking in the universe and new studies are proposing ways of finding them - The Conversation UK - January 13th, 2021
- Surprising Discovery of Unexpected Quantum Behavior in Insulators Suggests Existence of Entirely New Type of Particle - SciTechDaily - January 13th, 2021
- New quantum technology projects to solve mysteries of the universe - Open Access Government - January 13th, 2021
- University of Sheffield to lead multi-million pound project which could open up a new frontier in physics - University of Sheffield News - January 13th, 2021
- The Greatest: Four Legends Gather in One Night in Miami - Memphis Flyer - January 13th, 2021
- Raytheon UK part of team transforming the Royal Navy's technology, training and learning solutions - PRNewswire - January 13th, 2021
- Optical selection and sorting of nanoparticles according to quantum mechanical properties - Science Advances - January 13th, 2021
- Birds Have a Mysterious 'Quantum Sense'. For The First Time, Scientists Saw It in Action - ScienceAlert - January 9th, 2021
- The unhackable computers that could revolutionize the future - CNN - January 9th, 2021
- How understanding light has led to a hundred years of bright ideas - The Economist - January 9th, 2021
- Quantum Nanodevice Can Be Both a Heat Engine and Refrigerator at the Same Time - SciTechDaily - January 9th, 2021