MIP ^* =RE is geen typfout. 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 computationele problemen - waarvan MIP ^* en RE zijn maar twee.

De 165 pagina's tellende paper laat zien dat deze twee klassen hetzelfde zijn. Dat lijkt misschien een onbeduidend detail in een abstracte theorie zonder enige toepassing in de echte wereld. Maar natuurkundigen en wiskundigen komen massaal naar de dierentuin, ook al begrijpen ze het waarschijnlijk niet allemaal. Want de vondst blijkt verbazingwekkende gevolgen te hebben voor hun eigen disciplines.

1936, Alan Turing toonde aan dat het stopprobleem - algoritmisch beslissen of een computerprogramma stopt of voor altijd in een lus blijft - niet kan worden opgelost. De moderne informatica was geboren. Het succes wekte de indruk dat alle praktische problemen spoedig zouden wijken voor de enorme kracht van de computer.

Maar al snel bleek dat hoewel sommige problemen algoritmisch kunnen worden opgelost, de eigenlijke berekening duurt lang nadat onze zon de computer die de berekening uitvoert, heeft overspoeld. Uitzoeken hoe een probleem algoritmisch op te lossen was niet genoeg. Het was essentieel om oplossingen te classificeren op 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, in polynomiale tijd). Bijvoorbeeld, twee getallen vermenigvuldigen hoort bij P, omdat 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 enkel bekend algoritme kan dit efficiënt doen. Een gerelateerd probleem, beslissen of een bepaald getal een priemgetal is, bevond zich tot 2004 in een soortgelijk 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 zullen ze volgen, en we zullen de uitgang vinden. Als het antwoord nee is, echter, we zouden 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, kunnen we efficiënt aantonen dat, behoren tot NP. Elke oplossing voor een probleem dient om ons te overtuigen van het antwoord, en dus zit P in NP. Verrassend genoeg, een miljoen dollar vraag is of P=NP. Niemand weet het.

Vertrouw op machines

De klassen die tot nu toe zijn beschreven, vertegenwoordigen problemen waarmee een normale computer wordt geconfronteerd. Maar computers zijn fundamenteel aan het veranderen:er worden kwantumcomputers ontwikkeld. Maar als er een nieuw type computer komt en beweert een van onze problemen op te lossen, hoe kunnen we erop vertrouwen dat het klopt?

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

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

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

Quantumcommunicatie is een nieuwe vorm van communicatie die wordt uitgevoerd met qubits. Verstrengeling - een kwantumfunctie waarin qubits spookachtig verstrengeld zijn, zelfs als ze gescheiden zijn, maakt kwantumcommunicatie fundamenteel anders dan gewone communicatie. Toestaan ​​dat de provers van MIP een verstrengelde qubit delen, leidt tot de klasse MIP ^*.

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

Vergaande implicaties

In de jaren zeventig, Alain Connes formuleerde wat bekend werd als het Connes Embedding Problem. sterk vereenvoudigd, dit vroeg 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, In de tussentijd, Boris Tsirelson ontdekte een probleem in de natuurkunde dat nu bekend staat als het probleem van Tsirelson. 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. Hoe ze allebei nog steeds dezelfde resultaten kunnen opleveren en beide dezelfde fysieke realiteit beschrijven, is onbekend, maar daarom krijgen natuurkundigen ook ineens belangstelling.

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

Dit artikel is opnieuw gepubliceerd vanuit The Conversation onder een Creative Commons-licentie. Lees het originele artikel.