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:
- Quantum Time Twist Offers a Way to Create Schrdinger's Clock - Scientific American - October 25th, 2020
- Quantum Tunnels Show How Particles Can Break the Speed of Light - Quanta Magazine - October 25th, 2020
- The Importance of Funding Quantum Physics, Even in a Pandemic - Inside Philanthropy - October 25th, 2020
- Quantum Physics and Early Death | Dan Peterson - Patheos - October 25th, 2020
- A New Timekeeping Theory Reconciles Einstein's Relativity and Quantum Clocks - Science Times - October 25th, 2020
- Archer Materials well-aligned with strategic direction of the US in quantum computing - Proactive Investors Australia - October 25th, 2020
- Could Schrdingers cat exist in real life? We propose an experiment to find out - Scroll.in - October 25th, 2020
- Every Thing You Need to Know About Quantum Computers - Analytics Insight - October 25th, 2020
- Physicists clock the fastest possible speed of sound - Live Science - October 25th, 2020
- Post-doctoral Fellow, Department of Physics job with THE UNIVERSITY OF HONG KONG | 230760 - Times Higher Education (THE) - October 25th, 2020
- Diamonds Are a Quantum Scientist's Best Friend: Discovery May Revolutionize the High-Tech Industry - SciTechDaily - October 25th, 2020
- Sumit Das to Deliver 2019-20 A&S Distinguished Professor Lecture on 'Deconstructing Space-Time' - UKNow - October 25th, 2020
- Column: A new era of electric vehicles could be on the way - Gainesville Times - October 25th, 2020
- The TRP turf - The Times of India Blog - October 25th, 2020
- Beyond Homo Sapiens A Slightly Different Roll of the Darwinian Dice (Weekend Feature) - The Daily Galaxy --Great Discoveries Channel - October 25th, 2020
- Quantum and classical computers handle time differently. What does that mean for AI? - The Next Web - September 18th, 2020
- The Fate of Schrdinger's Cat Probably Isn't in The Hands of Gravity, Experiment Finds - ScienceAlert - September 18th, 2020
- Hybrid lightmatter particles offer tantalising new way to control chemistry - Chemistry World - September 18th, 2020
- Scientists Have Shown There's No 'Butterfly Effect' in the Quantum World - VICE - August 19th, 2020
- How Physics Erases The Beginning Of The Universe - Forbes - August 19th, 2020
- Does the Butterfly Effect Exist? Maybe, But Not in the Quantum Realm - Discover Magazine - August 19th, 2020
- Dismantling disciplinary boundaries and decolonizing young India: Decoding the National Educational Policy (20 - The Times of India Blog - August 19th, 2020
- The spread of 'stranger than we can think' - Yahoo Lifestyle - August 19th, 2020
- Raytheon Technologies invests in new transformational STEM high school - PRNewswire - August 19th, 2020
- The Wheel of Time and the Storytelling Problem in the Concept of a Binary - tor.com - August 19th, 2020
- Physicists witness time crystals interacting for the first time ever - New Atlas - August 19th, 2020
- Quantum mechanics is immune to the butterfly effect - The Economist - August 17th, 2020
- Physicists watch quantum particles tunnel through solid barriers. Here's what they found. - Space.com - August 17th, 2020
- The science of marketing: taking inspiration from quantum physics - The Drum - August 17th, 2020
- Here's why we need to build a quantum security coalition - World Economic Forum - August 17th, 2020
- The Spread of 'Stranger Than We Can Think' - SFGate - August 17th, 2020
- Nuh Gedik and Pablo Jarillo-Herrero are 2020 Moore Experimental Investigators in Quantum Materials - MIT News - August 17th, 2020
- Students in the news | Announcements - Indiana Gazette - August 17th, 2020
- Indian American Engineer Develops Parachute That Helped Curiosity Land on Mars - India West - August 17th, 2020
- How Quantum Mechanics will Change the Tech Industry - Unite.AI - July 21st, 2020
- Money & Markets: After the virus, make sure you've read the inflationary playbook - E&T Magazine - July 21st, 2020
- Bruce Lee: Inside the mind of the martial arts icon - CNN - July 21st, 2020
- Read Before Pontificating on Quantum Technology - War on the Rocks - July 13th, 2020
- The universe's clock might have bigger ticks than we imagine - Livescience.com - July 13th, 2020
- Testing Einstein's theory of relativity | OUPblog - OUPblog - July 13th, 2020
- Scientists Say This Is the Smallest Unit of Time That Could Exist - lintelligencer - July 13th, 2020
- Study: The Period of the Universe's Clock - lintelligencer - July 13th, 2020
- Book review: From Infinity to Man: The Fundamental Ideas of Kabbalah - The Jerusalem Post - July 8th, 2020
- Book review: Travels with Sushi in the Land of the Mind - The Jerusalem Post - July 8th, 2020
- WATCH: Follow along as this drag queen connects the dots between quantum physics and queer identity - Queerty - July 8th, 2020
- Raytheon Technologies to release second quarter results on July 28, 2020 - PRNewswire - July 8th, 2020
- A Brighter Tomorrow > News > USC Dornsife - USC Dornsife College of Letters, Arts and Sciences - July 8th, 2020
- The logic of the impossible: Moses our rabbi - The Jerusalem Post - July 8th, 2020
- Professor tackles one more mystery about quantum mechanics and times flow - GeekWire - July 5th, 2020
- Quantum fluctuations can jiggle objects on the human scale - MIT News - July 5th, 2020
- Want to Know the Speed of a Complex Nuclear Reaction? - Popular Mechanics - July 5th, 2020
- Try to consciously change the world it might just work - Sentinel & Enterprise - July 5th, 2020
- The Death of Fashion Shows? Not So Fast. | Tim's Take | BoF - The Business of Fashion - July 5th, 2020
- U of T and Hebrew University of Jerusalem launch research and innovation partnership - News@UofT - July 5th, 2020
- Max Planck Created Quantum Theory and Laid a New Foundation for Physics - Interesting Engineering - June 21st, 2020
- Do we need a 'Quantum Generation'? | TheHill - The Hill - June 21st, 2020
- 'Everything was centered around Sara, he was lost': Abhishek Kapoor on Sushant Singh Rajput after 'Kedarnath' - DNA India - June 21st, 2020
- RHOBH: What's with Denise Richards Husband Aaron Phypers? - Screen Rant - June 21st, 2020
- Restructuring cybersecurity with the power of quantum - TechRadar - June 21st, 2020
- In the atmosphere of Mars, a green glow offers scientists hints for future visits - NBCNews.com - June 21st, 2020
- Nano-motor of just 16 atoms runs at the boundary of quantum physics - New Atlas - June 20th, 2020
- Physics - The Period of the Universe's Clock - Physics - June 20th, 2020
- Why Gravity Is Not Like the Other Forces - Quanta Magazine - June 20th, 2020
- Toronto-based Association Quantum appoints Northern Hive PR - Business Up North - June 20th, 2020
- Physicists have proposed a new theory for Bose-Einstein condensates - Tech Explorist - June 20th, 2020
- Intricate Beauty, Quasiperiodic Structures, and the Cascade to Criticality - SciTechDaily - June 20th, 2020
- AI And The Parallel Universe - AI Daily - June 20th, 2020
- The stories a muon could tell - Symmetry magazine - June 20th, 2020
- Physicists Have Reversed Time on The Smallest Scale Using a Quantum Computer - ScienceAlert - June 13th, 2020
- Duckworth on Education: The Feynman Technique - EMSWorld - June 13th, 2020
- Sussex Uni physicist creates the fifth state of matter whilst working from home - The Tab - June 13th, 2020
- Beware of 'Theories of Everything' - Scientific American - June 13th, 2020
- Francesca Vidotto: The Quantum Properties of Space-Time - JSTOR Daily - June 1st, 2020
- What Is the Many-Worlds Theory of Quantum Mechanics? - The Wire - June 1st, 2020
- MIT Student Probing Reality Through Physics, Philosophy and Writing - SciTechDaily - June 1st, 2020
- An Indian Origin Physicist Created the Fifth State of Matter from Her Living Room - News18 - June 1st, 2020
- Science and the humanities in the time of pandemic: better together - The Irish Times - June 1st, 2020
- Quantum Physicist Invents Code to Achieve the Impossible - Interesting Engineering - May 24th, 2020
- What does the Tenet title mean? Quantum mechanics and Einsteins theory - Explica - May 24th, 2020
- Covid 19 Pandemic: Quantum Computing Technologies Market 2020, Share, Growth, Trends And Forecast To 2025 - 3rd Watch News - May 24th, 2020