## Major quantum computational breakthrough is shaking up physics and maths – The Conversation UK

Posted: August 14, 2020 at 11:51 pm

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.

See more here:

Major quantum computational breakthrough is shaking up physics and maths - The Conversation UK

- Newly Invented Device Controls Thousands of Qubits - Unite.AI - February 9th, 2021
- Universities are Building the Future of Quantum Internet - EdTech Magazine: Focus on Higher Education - February 9th, 2021
- A Swiss company claims it used quantum computers to find weakness in encryption - HT Tech - February 9th, 2021
- Microsoft Scientists Build Chip That Can Handle Thousands Of Qubits - Analytics India Magazine - February 9th, 2021
- The draft bill of the 17th Amendment Ordinance of the AWV (Foreign Trade and Payments Ordinance) - a first analysis - Lexology - February 9th, 2021
- BMW takes first steps into the quantum computing revolution - CNET - January 29th, 2021
- IBMs top executive says, quantum computers will never reign supreme over classical ones - The Hindu - January 29th, 2021
- A fridge thats colder than outer space could take quantum computing to new heights - TechRadar - January 29th, 2021
- article image Caltech and NTT developing the world's fastest quantum computer - Digital Journal - January 29th, 2021
- A Quantum Leap Is Coming: Ones, Zeros And Everything In Between - Transmission & Distribution World - January 29th, 2021
- The Convergence of Internet of Things and Quantum Computing - BBN Times - January 29th, 2021
- NTT Research Collaboration with Caltech to Develop World's Fastest Coherent Ising Machine - HPCwire - January 29th, 2021
- Analysis: Opportunities and Restraint of the Quantum Computing Market KSU | The Sentinel Newspaper - KSU | The Sentinel Newspaper - January 29th, 2021
- Light-Induced Twisting of Weyl Nodes Switches on Giant Electron Current Useful for Spintronics and Quantum Computing - SciTechDaily - January 29th, 2021
- Physicists Study How Our Universe Might Have Bubbled Up in the Multiverse - Quanta Magazine - January 29th, 2021
- IBM, Apple and Accenture join MIT cross-industry climate change-tackling consortium - ComputerWeekly.com - January 29th, 2021
- Worldwide High Performance Computing Industry to 2026 - The Market is Driven Largely by Simulations, Engineering and Design Solutions - PRNewswire - January 29th, 2021
- Biden needs an innovation agenda - Milford Daily News - January 29th, 2021
- Ten Technologies To Watch In 2021 - Forbes - January 29th, 2021
- 3 tech trends that COVID-19 will accelerate in 2021 - VentureBeat - January 29th, 2021
- Beam me up: long-distance quantum teleportation has happened for the first time ever - SYFY WIRE - December 26th, 2020
- Quanta's Year in Math and Computer Science (2020) - Quanta Magazine - December 26th, 2020
- What the Hell Is Quantum Chess? | IE - Interesting Engineering - December 26th, 2020
- The Interview Issue: Eisgruber is trying to reshape the meaning of a Princeton education even as his school, and higher ed as a whole, grapples with... - December 26th, 2020
- Satoshis Bitcoin Fortune Will Be Easiest Batch for Quantum Computers to Hack, Says Andreas Antonopoulos - The Daily Hodl - December 26th, 2020
- Europe Is on Its Way To Quantum Leadership, IQM Raises 39 M in Series A Funding - Embedded Computing Design - November 30th, 2020
- How Scientists Have Learned To Work With the Quantum World - Walter Bradley Center for Natural and Artificial Intelligence - November 30th, 2020
- Archer Materials makes strong progress in shifting focus to Advanced Materials Business and technology - Proactive Investors USA & Canada - November 30th, 2020
- 01 Communique to Present at the Benzinga Global Small Cap Conference on December 8 - IT News Online - November 30th, 2020
- What is Quantum Computing, and How does it Help Us? - Analytics Insight - October 11th, 2020
- 4 Reasons Why Now Is the Best Time to Start With Quantum Computing - Medium - October 11th, 2020
- Race for quantum supremacy gathers momentum with several companies joining bandwagon, says GlobalData - Quantaneo, the Quantum Computing Source - October 11th, 2020
- Quantum computing: Photon startup lights up the future of computers and cryptography - ZDNet - October 8th, 2020
- Canadian quantum computing firms partner to spread the technology - IT World Canada - October 8th, 2020
- Google's Billion Dollar News, Commercial Quantum Computers And More In This Week's Top News - Analytics India Magazine - October 8th, 2020
- SC20 Invited Speakers Tackle Challenges for the Earth, Its Inhabitants, and Our Security Using 'More Than HPC' - HPCwire - October 8th, 2020
- A new claimant for "most powerful quantum computer" - Axios - October 3rd, 2020
- ESAs -Week: Digital Twin Earth, Quantum Computing and AI Take Center Stage - SciTechDaily - October 3rd, 2020
- Schrdingers Web offers a sneak peek at the quantum internet - Science News - October 3rd, 2020
- Global QC Market Projected to Grow to More Than $800 million by 2024 - HPCwire - October 3rd, 2020
- Berkeley Lab Technologies Honored With 7 R&D 100 Awards - Lawrence Berkeley National Laboratory - October 3rd, 2020
- oneAPI Academic Center of Excellence Established at the Heidelberg University Computing Center (URZ) - HPCwire - October 3rd, 2020
- Baidu offers quantum computing from the cloud - VentureBeat - September 26th, 2020
- IBM Partners With HBCUs to Diversify Quantum Computing Workforce - Diverse: Issues in Higher Education - September 26th, 2020
- IBM, Alphabet and well-funded startups in the race for quantum supremacy - IT Brief Australia - September 26th, 2020
- IBM plans to build a 1121 qubit system. What does this technology mean? - The Hindu - September 26th, 2020
- Inaugural OSA Quantum 2.0 Conference Featured Talks on Emerging Technologies - Novus Light Technologies Today - September 26th, 2020
- Could Quantum Computing Progress Be Halted by Background Radiation? - Singularity Hub - September 1st, 2020
- Fermilab to lead $115 million National Quantum Information Science Research Center to build revolutionary quantum computer with Rigetti Computing,... - September 1st, 2020
- The future of artificial intelligence and quantum computing - Military & Aerospace Electronics - September 1st, 2020
- Researchers Found Another Impediment for Quantum Computers to Overcome - Dual Dove - September 1st, 2020
- Quantum Cryptography Market Research Analysis Including Growth Factors, Types And Application By Regions From 2024 - Kentucky Journal 24 - September 1st, 2020
- Q-NEXT collaboration awarded National Quantum Initiative funding - University of Wisconsin-Madison - September 1st, 2020
- This Equation Calculates The Chances We Live In A Computer Simulation - Discover Magazine - September 1st, 2020
- I confess, I'm scared of the next generation of supercomputers - TechRadar - September 1st, 2020
- Honeywell Wants To Show What Quantum Computing Can Do For The World - Forbes - August 14th, 2020
- Quantum Computing for the Next Generation of Computer Scientists and Researchers - Campus Technology - August 14th, 2020
- Quantum mechanics is immune to the butterfly effect - The Economist - August 14th, 2020
- IEEE International Conference on Quantum Computing and Engineering (QCE20) Transitions to All-Virtual Event - PRNewswire - August 14th, 2020
- 6 new degrees approved, including graduate degrees in biostatistics and quantum information science: News at IU - IU Newsroom - August 14th, 2020
- The race to building a fully functional quantum stack - TechCrunch - August 14th, 2020
- Toshiba Exits PC Business 35 Years of IBM Compatible PCs - Electropages - August 14th, 2020
- IBM Z mainframes revived by Red Hat, AI and security - TechTarget - August 14th, 2020
- Quantum computing will (eventually) help us discover vaccines in days - VentureBeat - May 17th, 2020
- Quantum computing analytics: Put this on your IT roadmap - TechRepublic - May 17th, 2020
- Video: The Future of Quantum Computing with IBM - insideHPC - May 17th, 2020
- Registration Open for Inaugural IEEE International Conference on Quantum Computing and Engineering - HPCwire - May 17th, 2020
- Light, fantastic: the path ahead for faster, smaller computer processors - News - The University of Sydney - May 17th, 2020
- VTT to acquire Finland's first quantum computer seeking to bolster Finland's and Europe's competitiveness - Quantaneo, the Quantum Computing Source - May 12th, 2020
- IonQ CEO Peter Chapman on how quantum computing will change the future of AI - VentureBeat - May 12th, 2020
- David Graves to Head New Research at PPPL for Plasma Applications in Industry and Quantum Information Science - HPCwire - May 12th, 2020
- Recent Research Answers the Future of Quantum Machine Learning on COVID-19 - Analytics Insight - May 12th, 2020
- Kerry Emanuel, David Sabatini, and Peter Shor receive BBVA Frontiers of Knowledge awards - MIT News - May 12th, 2020
- Between God and Science in the Surreal Silicon Valley of Devs - The Nation - May 12th, 2020
- Online course trains students in the bizarre world of quantum computing - Livescience.com - May 2nd, 2020
- Devs: Here's the real science behind the quantum computing TV show - New Scientist News - May 2nd, 2020
- New Princeton study takes superconductivity to the edge - Princeton University - May 2nd, 2020
- Quantum computer chips demonstrated at the highest temperatures ever - New Scientist News - April 16th, 2020
- Calling On AI And Quantum Computing To Fight The Coronavirus - Forbes - April 16th, 2020
- COVID-19: Quantum computing could someday find cures for coronaviruses and other diseases - TechRepublic - April 16th, 2020