Stort kvanteberegningsgennembrud ryster fysik og matematik

MIP ^* =RE er ikke en stavefejl. Det er en banebrydende opdagelse og den iørefaldende titel på et nyligt papir inden for kvantekompleksitetsteori. Kompleksitetsteori er en zoologisk have af "kompleksitetsklasser" - samlinger af beregningsproblemer - heraf MIP ^* og RE er kun to.

Det 165 sider lange papir viser, at disse to klasser er de samme. Det kan virke som en ubetydelig detalje i en abstrakt teori uden virkelige anvendelser. Men fysikere og matematikere strømmer til for at besøge zoologisk have, selvom de nok ikke forstår det hele. Fordi det viser sig, at opdagelsen har forbløffende konsekvenser for deres egne discipliner.

I 1936, Alan Turing viste, at Halting Problem - algoritmisk at afgøre, om et computerprogram stopper eller sløjfer for evigt - ikke kan løses. Moderne datalogi blev født. Dens succes gjorde indtryk af, at alle praktiske problemer snart ville give efter for computerens enorme kraft.

Men det viste sig hurtigt, at mens nogle problemer kan løses algoritmisk, den faktiske beregning vil vare længe efter, at vores sol vil have opslugt computeren, der udfører beregningen. Det var ikke nok at finde ud af, hvordan man løser et problem algoritmisk. Det var afgørende at klassificere løsninger efter effektivitet. Kompleksitetsteori klassificerer problemer efter, hvor svært det er at løse dem. Et problems hårdhed måles i forhold til, hvor længe beregningen varer.

RE står for problemer, der kan løses af en computer. Det er zoologisk have. Lad os se på nogle underklasser.

Klassen P består af problemer, som en kendt algoritme hurtigt kan løse (teknisk set i polynomisk tid). For eksempel, multiplikation af to tal tilhører P, da lang multiplikation er en effektiv algoritme til at løse problemet. Problemet med at finde hovedfaktorerne for et tal vides ikke at være i P; problemet kan bestemt løses af en computer, men ingen kendt algoritme kan gøre det effektivt. Et beslægtet problem, beslutter, om et givet tal er et primtal, var i lignende limbo indtil 2004, da en effektiv algoritme viste, at dette problem er i P.

En anden kompleksitetsklasse er NP. Forestil dig en labyrint. "Er der en vej ud af denne labyrint?" er et ja/nej spørgsmål. Hvis svaret er ja, så er der en enkel måde at overbevise os på:giv os bare anvisningerne, vi følger dem, og vi finder udgangen. Hvis svaret er nej, imidlertid, vi skulle krydse hele labyrinten uden nogensinde at finde en vej ud for at blive overbevist.

Sådanne ja/nej -problemer, som hvis svaret er ja, vi kan effektivt demonstrere, at tilhører NP. Enhver løsning på et problem tjener til at overbevise os om svaret, og så er P indeholdt i NP. Overraskende, et spørgsmål om en million dollar er, om P =NP. Ingen ved.

Tillid til maskiner

De hidtil beskrevne klasser repræsenterer problemer, som en normal computer står over for. Men computere ændrer sig grundlæggende - kvantecomputere udvikles. Men hvis der kommer en ny type computer og hævder at løse et af vores problemer, hvordan kan vi stole på at det er korrekt?

Forestil dig en interaktion mellem to enheder, en forhør og en beviser. I et politiafhør, beviseren kan være en mistænkt, der forsøger at bevise deres uskyld. Afhøreren skal beslutte, om beviseren er tilstrækkeligt overbevisende. Der er en ubalance; vidensmæssigt er forhørslederen i en ringere position.

I kompleksitetsteorien, forhørslederen er personen, med begrænset regnekraft forsøger at løse problemet. Beviset er den nye computer, som antages at have en enorm beregningskraft. Et interaktivt bevissystem er en protokol, som forhørslederen kan bruge til at bestemme, i hvert fald med stor sandsynlighed, om beviseren skal troes. I analogi, det er forbrydelser, som politiet muligvis ikke kan løse, men i det mindste kan uskyldige overbevise politiet om deres uskyld. Dette er klasse IP.

Hvis flere bevisere kan afhøres, og beviserne må ikke koordinere deres svar (som det typisk er, når politiet forhører flere mistænkte), så kommer vi til klassen MIP. Sådanne afhøringer, via krydsundersøgelse af bevisernes svar, give forhørslederen større magt, så MIP indeholder IP.

Kvantekommunikation er en ny kommunikationsform, der udføres med qubits. Forvikling - en kvantefunktion, hvor qubits er uhyggeligt sammenfiltrede, selvom den er adskilt - gør kvantekommunikation fundamentalt anderledes end almindelig kommunikation. At tillade MIP -beviserne at dele en sammenfiltret qubit fører til klassen MIP ^*.

Det virker indlysende, at kommunikation mellem beviserne kan kun hjælpe med at koordinere løgne frem for at hjælpe forhørslederen med at opdage sandheden. Af den grund, ingen forventede, at mere kommunikation ville gøre beregningsproblemer mere pålidelige og løselige. Overraskende, vi kender nu den MIP ^* =RE. Det betyder, at kvantekommunikation opfører sig vildt anderledes end normal kommunikation.

Vidtrækkende konsekvenser

I 1970'erne, Alain Connes formulerede det, der blev kendt som Connes Embedding Problem. Groft forenklet, dette spurgte, om uendelige matricer kan tilnærmes med endelige matricer. Dette nye papir har nu bevist, at dette ikke er muligt - et vigtigt fund for rene matematikere.

I 1993, imens, Boris Tsirelson pegede på et problem i fysikken, der nu er kendt som Tsirelsons problem. Dette handlede om to forskellige matematiske formalismer om en enkelt situation i kvantemekanikken - til dato en utrolig vellykket teori, der forklarer den subatomære verden. Da det var to forskellige beskrivelser af det samme fænomen, kunne det forventes, at de to formalismer var matematisk ækvivalente.

Men det nye papir viser nu, at de ikke er det. Præcis hvordan de begge stadig kan give de samme resultater og begge beskriver den samme fysiske virkelighed er ukendt, men det er derfor, fysikere også pludselig interesserer sig.

Tiden vil vise, hvad andre ubesvarede videnskabelige spørgsmål vil give til undersøgelsen af ​​kompleksitet. Utvivlsomt, MIP ^* =RE er et stort spring fremad.

Denne artikel er genudgivet fra The Conversation under en Creative Commons -licens. Læs den originale artikel.