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:
Major quantum computational breakthrough is shaking up physics and maths - The Conversation UK
- The neutrino's quantum fuzziness is beginning to come into focus - Science News Magazine - May 23rd, 2024 [May 23rd, 2024]
- Unlocking the Quantum Code: International Team Cracks a Long-Standing Physics Problem - SciTechDaily - May 23rd, 2024 [May 23rd, 2024]
- Quantum tunnel: Scientists study particles that move faster than light - Interesting Engineering - May 23rd, 2024 [May 23rd, 2024]
- Quantum to cosmos: Why scale is vital to our understanding of reality - New Scientist - May 23rd, 2024 [May 23rd, 2024]
- A new theory of quantum gravity could explain the biggest puzzle in cosmology, study suggests - Livescience.com - May 23rd, 2024 [May 23rd, 2024]
- Helping qubits stay in sync - Newswise - May 23rd, 2024 [May 23rd, 2024]
- Breaking Light Speed: The Quantum Tunneling Enigma - SciTechDaily - May 23rd, 2024 [May 23rd, 2024]
- Quantum tunnels allow particles to break the light-speed barrier - Earth.com - May 23rd, 2024 [May 23rd, 2024]
- Cloud Computing under the Cover of Quantum - Physics - May 23rd, 2024 [May 23rd, 2024]
- Coherently excited superresolution using intensity product of phase-controlled quantum erasers via polarization-basis ... - Nature.com - May 23rd, 2024 [May 23rd, 2024]
- Quantum biology: New clues on how life might make use of weird physics - New Scientist - May 23rd, 2024 [May 23rd, 2024]
- Chinas father of quantum named Royal Society fellow as US targets sector - South China Morning Post - May 23rd, 2024 [May 23rd, 2024]
- Scientists move atoms so close together it may change quantum physics forever - - Study Finds - May 23rd, 2024 [May 23rd, 2024]
- "Impossible" quantum effects seen when squishing atoms together - Earth.com - May 23rd, 2024 [May 23rd, 2024]
- Beyond Hydrogen: Discovery of Tiny New Atom Tauonium With Massive Implications - SciTechDaily - May 23rd, 2024 [May 23rd, 2024]
- Quantum Coherence: Harvard Scientists Uncover Hidden Order in Chemical Chaos - SciTechDaily - May 23rd, 2024 [May 23rd, 2024]
- Netflixs 3 Body Problem: The science explained by an astrophysicist - Vox.com - March 24th, 2024 [March 24th, 2024]
- Entanglement entropies of nuclear systems gro - EurekAlert - March 24th, 2024 [March 24th, 2024]
- The Quest for a Theory of Everything Scientists Put Einstein to the Test - SciTechDaily - March 24th, 2024 [March 24th, 2024]
- Vibrating atoms are seen 'tuning' the energy of a single electron - Earth.com - March 24th, 2024 [March 24th, 2024]
- Innovator Spotlight: Joseph Maciejko | The Quad - University of Alberta - March 24th, 2024 [March 24th, 2024]
- A Breakthrough in the Control of Quantum Phenomena at Room Temperature Has Been Achieved, Researchers Say - The Debrief - February 16th, 2024 [February 16th, 2024]
- The End of the Quantum Ice Age: Room Temperature Breakthrough - SciTechDaily - February 16th, 2024 [February 16th, 2024]
- Quantum computer outperformed by new traditional computing - Earth.com - February 16th, 2024 [February 16th, 2024]
- URI program to help STEM professionals pivot into quantum information science careers - The University of Rhode Island - February 16th, 2024 [February 16th, 2024]
- Quantum realm controlled at room temperature for the first time - Earth.com - February 16th, 2024 [February 16th, 2024]
- Quantum Breakthrough: New Method Preserves Information Against All Odds - SciTechDaily - February 16th, 2024 [February 16th, 2024]
- Quantum computers get new design that makes them more "useful" - Earth.com - February 16th, 2024 [February 16th, 2024]
- Beyond Classical Physics: Scientists Discover New State of Matter With Chiral Properties - SciTechDaily - February 16th, 2024 [February 16th, 2024]
- Quantum research sheds light on the mystery of high-temperature superconductivity - Tech Explorist - February 16th, 2024 [February 16th, 2024]
- Unlocking the Mysteries of Quantum Many-Body Systems: A Look at Quantum Simulators and Universal Scaling ... - Medriva - February 16th, 2024 [February 16th, 2024]
- Functioning quantum internet makes giant stride closer to reality - Earth.com - February 13th, 2024 [February 13th, 2024]
- Exploring New Futures in Space: A Revolutionary Integration of Neuroscience, Quantum Physics, and Space Exploration - SETI Institute - February 13th, 2024 [February 13th, 2024]
- Uncovering the Quantum Plateau: Significance and Implications | Nature Physics - Medriva - February 13th, 2024 [February 13th, 2024]
- The State of the Art in Quantum Computing - Medium - February 13th, 2024 [February 13th, 2024]
- Beyond the Visible Universe: New Research Reveals How Gravity Influences the Quantum Realm - SciTechDaily - February 13th, 2024 [February 13th, 2024]
- Leader of IBM's Quantum Safe Team to speak at URI - University of Rhode Island - September 23rd, 2023 [September 23rd, 2023]
- University Assistant Predoctoral, Physics job with UNIVERSITY OF ... - Times Higher Education - September 23rd, 2023 [September 23rd, 2023]
- Zentropy A New Theory That Could Transform Material Science - SciTechDaily - September 23rd, 2023 [September 23rd, 2023]
- Researchers Studying the Quantum Realm Observe Alice in ... - The Debrief - September 23rd, 2023 [September 23rd, 2023]
- Augusta University graduate starts business in the artificial ... - Jagwire Augusta - September 23rd, 2023 [September 23rd, 2023]
- Quantum Echoes: A Revolutionary Method to Store Information as Sound Waves - SciTechDaily - August 14th, 2023 [August 14th, 2023]
- 'Quantum superchemistry' observed for the 1st time ever - Space.com - August 14th, 2023 [August 14th, 2023]
- Quantum Avalanche A Phenomenon That May Revolutionize Microelectronics and Supercomputing - SciTechDaily - August 14th, 2023 [August 14th, 2023]
- Applications of quantum mechanics at the beach - Symmetry magazine - August 14th, 2023 [August 14th, 2023]
- Book Review: On the Origin of Time Stephen Hawking's Final Theory - Moose Jaw Today - August 14th, 2023 [August 14th, 2023]
- Harnessing Quantum Technologies: The Next Big Leap in Global ... - Fagen wasanni - August 14th, 2023 [August 14th, 2023]
- The quantum avalanche - At the Vienna University of Technology, it ... - Chemie.de - August 14th, 2023 [August 14th, 2023]
- Semiconductors: The Linchpin of AI in Quantum Computing - Fagen wasanni - August 14th, 2023 [August 14th, 2023]
- The Promising Collaboration Between AI and Quantum Computing - Fagen wasanni - August 14th, 2023 [August 14th, 2023]
- String theory physicist changed quantum field theory - USC Dornsife College of Letters, Arts and Sciences - August 14th, 2023 [August 14th, 2023]
- QUANTUM SUPERCOMPUTERS. The words Quantum and ... - Medium - August 14th, 2023 [August 14th, 2023]
- Fourteen MIT School of Science professors receive tenure for 2022 ... - MIT News - August 14th, 2023 [August 14th, 2023]
- The Fascinating World of Quantum Integrated Circuits: The Next Big ... - Fagen wasanni - August 14th, 2023 [August 14th, 2023]
- Conclusive Evidence for Modified Gravity: Collapse of Newton's and ... - SciTechDaily - August 14th, 2023 [August 14th, 2023]
- Physicists Open New Path to an Exotic Form of Superconductivity - SciTechDaily - August 14th, 2023 [August 14th, 2023]
- The Principle of Least Action Now Exists in the Quantum Realm - Popular Mechanics - June 10th, 2023 [June 10th, 2023]
- Quantum materials: Electron spin measured for the first time - EurekAlert - June 10th, 2023 [June 10th, 2023]
- Life in a hologram | MIT News | Massachusetts Institute of Technology - MIT News - June 10th, 2023 [June 10th, 2023]
- If Black Holes Evaporate, Everything Evaporates - Universe Today - June 10th, 2023 [June 10th, 2023]
- Clever Ant-Man Easter Egg Links The Movie to the Real World's ... - Startefacts - June 10th, 2023 [June 10th, 2023]
- Quantum Cryptography: The Cutting Edge of Secure Communication - CityLife - June 10th, 2023 [June 10th, 2023]
- This 17-year-old works to make quantum mainstream - Indiatimes.com - June 10th, 2023 [June 10th, 2023]
- The multiverse is doomed and even Spider-Man and The Flash can't save it - Yahoo Entertainment - June 10th, 2023 [June 10th, 2023]
- Physics of Time Travel: A Scientific Perspective - Mirage News - June 10th, 2023 [June 10th, 2023]
- Quantum Spin Liquids: The Future of Superconductors - EnergyPortal.eu - June 10th, 2023 [June 10th, 2023]
- Interview: Three Books That Make Tess Gunty Angry - The New York Times - June 10th, 2023 [June 10th, 2023]
- Events Calendar School of Mathematics and Statistics Colloquium ... - Carleton University - June 10th, 2023 [June 10th, 2023]
- Graphene and Quantum Computing: A Match Made in Heaven - CityLife - June 10th, 2023 [June 10th, 2023]
- A Quantum Computer Simulation Has Reversed Time And Physics May Never Be The Same - Twisted Sifter - June 2nd, 2023 [June 2nd, 2023]
- Realizing the Einstein-Podolsky-Rosen Paradox for Atomic Clouds - Physics - June 2nd, 2023 [June 2nd, 2023]
- The US and UK team up to advance quantum information science - Fermi National Accelerator Laboratory - June 2nd, 2023 [June 2nd, 2023]
- How plants can perform feats of quantum mechanics - Big Think - June 2nd, 2023 [June 2nd, 2023]
- Physicists Make Matter out of Light to Find Quantum Singularities - Scientific American - June 2nd, 2023 [June 2nd, 2023]
- Eventually everything will evaporate, not only black holes - Science Daily - June 2nd, 2023 [June 2nd, 2023]
- Julius-Maximillians-Universitt Wrzburg Researchers Use ... - HPCwire - June 2nd, 2023 [June 2nd, 2023]
- TNTs The Lazarus Project Uses Suspense Trapping to Ask Smart ... - Roger Ebert - June 2nd, 2023 [June 2nd, 2023]
- Quantum Exponential: building a cutting edge quantum technology ... - The Armchair Trader - June 2nd, 2023 [June 2nd, 2023]
- IMDEA Software and IMDEA Networks work to deploy in the ... - EurekAlert - June 2nd, 2023 [June 2nd, 2023]
- Ian Hacking, Eminent Philosopher of Science and Much Else, Dies ... - The New York Times - June 2nd, 2023 [June 2nd, 2023]