MIP ^* =RE är inget stavfel. Det är en banbrytande upptäckt och den medryckande titeln på en ny artikel inom kvantkomplexitetsteori. Komplexitetsteorin är en djurpark av "komplexitetsklasser" - samlingar av beräkningsproblem - varav MIP ^* och RE är bara två.

Den 165 sidor långa uppsatsen visar att dessa två klasser är desamma. Det kan tyckas vara en obetydlig detalj i en abstrakt teori utan någon verklig tillämpning. Men fysiker och matematiker strömmar för att besöka djurparken, även om de förmodligen inte förstår allt. För det visar sig att upptäckten får häpnadsväckande konsekvenser för deras egna discipliner.

1936, Alan Turing visade att stoppproblemet – att algoritmiskt bestämma om ett datorprogram stannar eller går i loop för alltid – inte kan lösas. Modern datavetenskap föddes. Dess framgång gjorde intrycket att alla praktiska problem snart skulle ge efter för datorns enorma kraft.

Men det visade sig snart att medan vissa problem kan lösas algoritmiskt, den faktiska beräkningen kommer att pågå långt efter att vår sol kommer att ha uppslukat datorn som utför beräkningen. Att ta reda på hur man löser ett problem algoritmiskt räckte inte. Det var viktigt att klassificera lösningar efter effektivitet. Komplexitetsteorin klassificerar problem efter hur svårt det är att lösa dem. Hårdheten av ett problem mäts i termer av hur länge beräkningen pågår.

RE står för problem som kan lösas av en dator. Det är djurparken. Låt oss ta en titt på några underklasser.

Klassen P består av problem som en känd algoritm kan lösa snabbt (tekniskt, i polynomtid). Till exempel, att multiplicera två tal hör till P eftersom lång multiplikation är en effektiv algoritm för att lösa problemet. Problemet med att hitta primtalsfaktorerna för ett tal är inte känt för att vara i P; problemet kan säkert lösas av en dator men ingen känd algoritm kan göra det effektivt. Ett relaterat problem, bestämma om ett givet tal är ett primtal, var i liknande limbo fram till 2004 då en effektiv algoritm visade att detta problem finns i P.

En annan komplexitetsklass är NP. Föreställ dig en labyrint. "Finns det en väg ut ur denna labyrint?" är en ja/nej fråga. Om svaret är ja, då finns det ett enkelt sätt att övertyga oss:ge oss bara anvisningarna, vi följer dem, och vi hittar utgången. Om svaret är nej, dock, vi skulle behöva korsa hela labyrinten utan att någonsin hitta en väg ut för att bli övertygade.

Sådana ja/nej-problem för vilka, om svaret är ja, vi kan effektivt visa att, tillhör NP. Varje lösning på ett problem tjänar till att övertyga oss om svaret, och så finns P i NP. Förvånande, en miljon dollar fråga är om P=NP. Ingen vet.

Lita på maskiner

Klasserna som beskrivits hittills representerar problem som en vanlig dator står inför. Men datorer förändras i grunden – kvantdatorer utvecklas. Men om en ny typ av dator kommer och påstår sig lösa ett av våra problem, hur kan vi lita på att det är korrekt?

Föreställ dig en interaktion mellan två enheter, en förhörsledare och en bevisare. I ett polisförhör, bevisaren kan vara en misstänkt som försöker bevisa sin oskuld. Förhörsledaren måste ta ställning till om bevisaren är tillräckligt övertygande. Det finns en obalans; kunskapsmässigt är förhörsledaren i en underlägsen position.

I komplexitetsteorin, förhörsledaren är personen, med begränsad beräkningskraft, försöker lösa problemet. Beviset är den nya datorn, som antas ha en enorm beräkningskraft. Ett interaktivt bevissystem är ett protokoll som förhörsledaren kan använda för att fastställa, åtminstone med stor sannolikhet, om bevisaren ska tros. I analogi, det här är brott som polisen kanske inte kan lösa, men åtminstone oskyldiga kan övertyga polisen om sin oskuld. Detta är klassens IP.

Om flera bevisare kan förhöras, och bevisarna får inte samordna sina svar (som vanligtvis är fallet när polisen förhör flera misstänkta), sedan kommer vi till klassen MIP. Sådana förhör, genom att korsförhöra provarnas svar, ge förhörsledaren större makt, så MIP innehåller IP.

Kvantkommunikation är en ny form av kommunikation som utförs med qubits. Entanglement – ​​en kvantfunktion där qubits är spöklikt intrasslade, även om den är åtskild – gör kvantkommunikationen fundamentalt annorlunda än vanlig kommunikation. Att tillåta MIP-provarna att dela en intrasslad qubit leder till klassen MIP ^*.

Det verkar uppenbart att kommunikation mellan bevisarna kan bara hjälpa dem att samordna lögner snarare än att hjälpa förhörsledaren att upptäcka sanningen. Av den anledningen, ingen förväntade sig att mer kommunikation skulle göra beräkningsproblem mer tillförlitliga och lösbara. Förvånande, vi vet nu att MIP ^* =RE. Det betyder att kvantkommunikation beter sig helt annorlunda än normal kommunikation.

Långtgående konsekvenser

På 1970-talet Alain Connes formulerade vad som blev känt som Connes Embedding Problem. Grovt förenklat, detta frågade om oändliga matriser kan approximeras av finita matriser. Detta nya papper har nu visat att detta inte är möjligt - ett viktigt fynd för rena matematiker.

1993, under tiden, Boris Tsirelson pekade på ett problem i fysiken som nu kallas Tsirelsons problem. Det här handlade om två olika matematiska formalismer för en enskild situation inom kvantmekaniken – hittills en otroligt framgångsrik teori som förklarar den subatomära världen. Eftersom det är två olika beskrivningar av samma fenomen var det att förvänta sig att de två formalismerna var matematiskt likvärdiga.

Men den nya tidningen visar nu att de inte är det. Exakt hur de båda fortfarande kan ge samma resultat och båda beskriver samma fysiska verklighet är okänt, men det är därför som fysiker också plötsligt intresserar sig.

Tiden kommer att utvisa vad andra obesvarade vetenskapliga frågor kommer att ge för studiet av komplexitet. Otvivelaktigt, MIP ^* =RE är ett stort steg framåt.

Den här artikeln är återpublicerad från The Conversation under en Creative Commons-licens. Läs originalartikeln.