Major quantum computational breakthrough is shaking up physics and maths

Sep 21, 2020 | Location West County

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.

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. Let's 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, we'll follow them, and we'll find the exit. If the answer is no, however, we'd 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.

Trust in machines

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 , the interrogator is the person, with limited computational power, trying to solve the problem. The prover is the new , 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  is a new form of communication carried out with qubitsEntanglement – a quantum feature in which qubits are spookishly entangled, even if separated—makes  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.

Far-reaching implications

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 isn't possible—an important finding for pure mathematicians.

In 1993, meanwhile, Boris Tsirelson pinpointed a problem in physics now known as Tsirelson's 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 aren't. 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.

 

 

 

 

 

 

Locations near
ME
Ashburn 0.93 mi
43330 Junction Plaza
#160
Ashburn, VA 20147
Sterling 4.07 mi
44 Pidgeon Hill Drive
#100
Sterling, VA 20165
Leesburg 5.69 mi
521 E Market St
#B
Leesburg, VA 20176
Herndon 7.66 mi
2465 Centreville Road
#J2
Herndon, VA 20171
Stone Ridge 7.88 mi
42020 Village Center Plaza
#100
Stone Ridge, VA 20105
Reston 8.62 mi
1424 North Point Village Center
Reston, VA 20194
Purcellville 12.72 mi
1020 E Main St
Ste L
Purcellville, VA 20132
North Potomac 13.58 mi
12150 Darnestown Rd
Gaithersburg, MD 20878
Centreville 14.52 mi
5959 Centreville Crest Ln
Centreville, VA 20121
Fairfax 14.67 mi
11891 Grand Commons Ave
Fairfax, VA 22030
Potomac 14.98 mi
10232 River Road
#B
Potomac, MD 20854
Germantown MD 15.03 mi
12800 Middlebrook Road
Germantown, MD 20874
Tysons 15.45 mi
328 Maple Ave E
#A
Vienna, VA 22180
Haymarket 17.87 mi
15125 Washington St
Haymarket, VA 20169
Rockville 18.19 mi
20 Courthouse Square
#106
Rockville, MD 20850
Mclean 18.23 mi
1320 Old Chain Bridge Road
Suite #190
McLean, VA 22101
Gaithersburg 18.71 mi
9132 Rothbury Drive
Gaithersburg, MD 20886
North Bethesda 20.42 mi
5268 Nicholson Ln
#N
Kensington, MD 20895
Falls Church 20.59 mi
6674 Arlington Blvd
Falls Church, VA 22042
Manassas 20.65 mi
9722 Liberia Ave
Manassas, VA 20110
Bristow 20.71 mi
12705 Braemar Village Pz
Bristow, VA 20136
Burke 20.82 mi
9411 Old Burke Lake Rd
#C
Burke, VA 22015
Bethesda 21.3 mi
4918 Fairmont Ave
Bethesda, MD 20814
Annandale 21.64 mi
7000 Columbia Pike
Annandale, VA 22003
Damascus 22.77 mi
9815 Main St
Damascus, MD 20872
Arlington, VA 23.29 mi
4801 1st St N
Arlington, VA 22203
Cathedral Heights 23.51 mi
3706 Macomb St NW
Washington, D.C., DC 20016
Olney 23.96 mi
18157 Village Center Dr
Olney, MD 20832
Downtown Silver Spring 24.94 mi
1133 East West Highway
Silver Spring, MD 20910
Lorton 25.06 mi
9027 Silverbrook Rd
#A
Fairfax Station, VA 22039
West Washington 25.69 mi

Washington, DC 20009
Alexandria City 25.7 mi
4605 Duke Street
Alexandria, VA 22304
Lake Ridge 26.5 mi
12473 Dillingham Square
Lake Ridge, VA 22192
Frederick North 26.7 mi
905 W. 7th Street
Frederick, MD 21701
Northern Silver Spring 26.75 mi
732 Cloverly Street
Silver Spring, MD 20905
Alexandria 27.17 mi
6483 Old Beulah Street
Alexandria, VA 22315
Warrenton 27.42 mi
512 Fletcher Drive
Warrenton, VA 20186
Mount Airy 28.24 mi
411 E Ridgeville Blvd
Mt Airy, MD 21771
Capitol Hill DC 28.48 mi
621 Pennsylvania Ave SE
1st-floor unit
Washington, DC 20003
Dale City 28.99 mi
5512 Staples Mill Plaza
Dale City, VA 22193
Mount Vernon 29.66 mi
7696 H Richmond Hwy
Alexandria, VA 22306
Beltsville 30.89 mi
10914 Baltimore Ave
#B
Beltsville, MD 20705
Clarksville 31.56 mi
12250 Clarksville Pike
#D
Clarksville, MD 21029
Laurel 35.02 mi
10095 Washington Blvd N
#136
Laurel, MD 20723
Woodmore 35.27 mi
9101 Woodmore Centre Drive
Lanham, MD 20706
Glenn Dale 35.83 mi
10559 Greenbelt Rd
Lanham, MD 20706
Sykesville 36.57 mi
1207 Liberty Rd.
#D-104
Sykesville, MD 21784
Ellicott City 37.11 mi
3290 Pine Orchard Lane
#B
Ellicott City, MD 21042
Winchester 37.62 mi
2512 S Pleasant Valley Rd
Winchester, VA 22601
Columbia 38.19 mi
8827 Centre Park Drive
#F
Columbia, MD 21045
Stafford 39.58 mi
263 Garrisonville Road
#104
Stafford, VA 22554
Bowie 41.26 mi
15231 Hall Rd
Bowie, MD 20721
Waldorf 42.24 mi
3022 Festival Way
Waldorf, MD 20601
Crofton 42.6 mi
1153 Route 3 North
#120
Crofton, MD 21054
Owings Mills 44.15 mi
9433 Common Brook Rd #100
Owings Mills, MD 21117
Pikesville 46.84 mi
1433 Reisterstown Rd
Pikesville, MD 21208
Dunkirk 49.92 mi
10735 Town Center Blvd
#7
Dunkirk, MD 20754