Een grote doorbraak op het gebied van kwantumcomputers schudt natuurkunde en wiskunde door elkaar.

Niemand had verwacht dat meer communicatie de rekenproblemen betrouwbaarder zou maken.

MIP * = RE is geen typefout. Het is een baanbrekende ontdekking en de pakkende titel van een recent artikel op het gebied van kwantumcomplexiteitstheorie. Complexiteitstheorie is een dierentuin van “complexiteitsklassen” – verzamelingen van rekenproblemen – waarvan MIP * en RE er slechts twee zijn.

Het 165 pagina’s tellende artikel laat zien dat deze twee klassen hetzelfde zijn. Dat lijkt misschien een onbeduidend detail in een abstracte theorie zonder enige echte toepassing. Maar natuurkundigen en wiskundigen komen massaal naar de dierentuin, ook al begrijpen ze het waarschijnlijk niet allemaal. Omdat het blijkt dat de ontdekking verbazingwekkende gevolgen heeft voor hun eigen disciplines.

In 1936 toonde Alan Turing aan dat het Halting-probleem – algoritmisch beslissen of een computerprogramma voor altijd stopt of lussen – niet kan worden opgelost. De moderne informatica was geboren. Het succes ervan wekte de indruk dat binnenkort alle praktische problemen zouden wijken voor de enorme kracht van de computer.

Maar het werd al snel duidelijk dat, hoewel sommige problemen algoritmisch kunnen worden opgelost, de feitelijke berekening zal duren lang nadat onze zon de computer die de berekening uitvoert heeft overspoeld. Uitzoeken hoe een probleem algoritmisch kon worden opgelost, was niet voldoende. Het was essentieel om oplossingen te classificeren op basis van efficiëntie. Complexiteitstheorie classificeert problemen op basis van hoe moeilijk het is om ze op te lossen. De hardheid van een probleem wordt gemeten in termen van hoe lang de berekening duurt.

RE staat voor problemen die door een computer kunnen worden opgelost. Het is de dierentuin. Laten we eens kijken naar enkele subklassen.

De klasse P bestaat uit problemen die een bekend algoritme snel kan oplossen (technisch gezien in polynoomtijd). Het vermenigvuldigen van twee getallen behoort bijvoorbeeld tot P, aangezien lange vermenigvuldiging een efficiënt algoritme is om het probleem op te lossen. Het probleem van het vinden van de priemfactoren van een getal is niet bekend in P; het probleem kan zeker door een computer worden opgelost, maar geen bekend algoritme kan dat efficiënt doen. Een gerelateerd probleem, beslissen of een bepaald getal een priemgetal is, bevond zich tot 2004 in een vergelijkbare limbo toen een efficiënt algoritme aantoonde dat dit probleem zich in P.

Een andere complexiteitsklasse is NP. Stel je een doolhof voor. “Is er een uitweg uit dit doolhof?” is een ja / nee-vraag. Als het antwoord ja is, dan is er een eenvoudige manier om ons te overtuigen: geef ons gewoon de aanwijzingen, we volgen ze en we vinden de uitgang. Als het antwoord nee is, zouden we het hele doolhof moeten doorkruisen zonder ooit een uitweg te vinden om overtuigd te worden.

Dergelijke ja / nee-problemen waarvoor, als het antwoord ja is, we dat efficiënt kunnen aantonen, behoren tot NP. Elke oplossing voor een probleem dient om ons te overtuigen van het antwoord, en daarom zit P in NP. Verrassend genoeg is een vraag van een miljoen dollar of P = NP. Niemand weet het.

Vertrouw op machines

De tot dusver beschreven klassen vertegenwoordigen problemen waarmee een normale computer te maken heeft. Maar computers veranderen fundamenteel – er worden kwantumcomputers ontwikkeld. Maar als er een nieuw type computer komt en beweert een van onze problemen op te lossen, hoe kunnen we dan vertrouwen dat het correct is?

Complexiteitswetenschap helpt uit te leggen welke problemen een computer kan oplossen. Phatcharapon / Shutterstock

Stel je een interactie voor tussen twee entiteiten, een ondervrager en een bewijzer. Bij een verhoor door de politie kan de bewijzer een verdachte zijn die zijn onschuld probeert te bewijzen. De ondervrager moet beslissen of de prover voldoende overtuigend is. Er is een onbalans; qua kennis bevindt de ondervrager zich in een ondergeschikte positie.

In de complexiteitstheorie is de ondervrager de persoon met beperkte rekenkracht die het probleem probeert op te lossen. De bewijzer is de nieuwe computer, waarvan wordt aangenomen dat deze een enorme rekenkracht heeft. Een interactief bewijssysteem is een protocol dat de ondervrager kan gebruiken om, althans met grote waarschijnlijkheid, te bepalen of de bewijzer moet worden geloofd. Naar analogie zijn dit misdrijven die de politie misschien niet kan oplossen, maar onschuldigen kunnen de politie tenminste van hun onschuld overtuigen. Dit is de klasse IP.

Als meerdere proefpersonen kunnen worden ondervraagd, en de proefpersonen mogen hun antwoorden niet coördineren (zoals meestal het geval is wanneer de politie meerdere verdachten ondervraagt), dan komen we bij de MIP van de klas. Dergelijke ondervragingen, door middel van kruisonderzoek van de antwoorden van de proefpersonen, geven de ondervrager meer macht, dus MIP bevat IP.

Quantumcommunicatie is een nieuwe vorm van communicatie die wordt uitgevoerd met qubits. Verstrengeling – een kwantumfunctie waarbij qubits op een spookachtige manier verstrikt zijn, zelfs als ze gescheiden zijn – maakt kwantumcommunicatie fundamenteel anders dan gewone communicatie. Door de bewijzen van MIP toe te staan een verstrengelde qubit te delen, leidt dit tot de klasse MIP *.

Het lijkt duidelijk dat communicatie tussen de proefpersonen alleen kan dienen om de proefpersonen te helpen bij het coördineren van leugens in plaats van de ondervrager te helpen de waarheid te ontdekken. Om die reden had niemand verwacht dat het toestaan van meer communicatie computationele problemen betrouwbaarder en oplosbaarder zou maken. Verrassend genoeg weten we nu dat MIP * = RE. Dit betekent dat kwantumcommunicatie zich heel anders gedraagt dan normale communicatie.

Verregaande implicaties

In de jaren zeventig formuleerde Alain Connes wat bekend werd als het Connes Embedding Problem. Sterk vereenvoudigd, vroeg dit zich af of oneindige matrices kunnen worden benaderd door eindige matrices. Dit nieuwe artikel heeft nu bewezen dat dit niet mogelijk is – een belangrijke bevinding voor zuivere wiskundigen.

In 1993 wees Boris Tsirelson ondertussen op een probleem in de natuurkunde dat nu bekend staat als Tsirelson’s Problem. Dit ging over twee verschillende wiskundige formalismen van een enkele situatie in de kwantummechanica – tot op heden een ongelooflijk succesvolle theorie die de subatomaire wereld verklaart. Omdat het twee verschillende beschrijvingen van hetzelfde fenomeen waren, was het te verwachten dat de twee formalismen wiskundig equivalent waren.

Maar de nieuwe krant laat nu zien dat ze dat niet zijn. Precies hoe ze allebei nog steeds dezelfde resultaten kunnen opleveren en beide dezelfde fysieke realiteit beschrijven, is niet bekend, maar het is de reden waarom natuurkundigen plotseling ook geïnteresseerd zijn.

De tijd zal leren wat andere onbeantwoorde wetenschappelijke vragen zullen opleveren voor de studie van complexiteit. MIP * = RE is ongetwijfeld een grote sprong voorwaarts.


— Lees op

The Conversation.com

Een artikel van:

Ittay Weiss


Geef een reactie