Unitary complexity in polynomial space

In de wereld van de informatica bestaat er een fundamentele kloof tussen wat een machine snel kan doen en wat het kan doen als het een enorme hoeveelheid geheugen krijgt. Decennialang hebben computerwetenschappers deze gebieden in kaart gebracht door categorieën te creëren voor problemen die gemakkelijk op te lossen zijn, problemen die moeilijk op te lossen zijn, en problemen die binnen een redelijke tijdstip onmogelijk lijken op te lossen. Een centrale vraag in dit veld is of het vermogen om meer geheugen te gebruiken een computer in staat stelt om problemen op te lossen die strikt buiten het bereik liggen van een computer met beperkte tijd. Hoewel we sterke vermoedens hebben over de antwoorden, blijven veel van deze vragen onbewezen.

Parallel aan deze klassieke wereld bestaat het domein van de quantumcomputing, waar machines gebruikmaken van de vreemde eigenschappen van subatomaire deeltjes om informatie te verwerken. Hier zijn de regels anders. Een quantumcomputer draait niet alleen bits aan of uit; hij manipuleert complexe golven van waarschijnlijkheid. Dit stelt hem in staat om bepaalde taken uit te voeren die een klassieke computer een eeuwigheid zouden kosten. Er heeft echter een diep mysterie voortgeduurd: berust de kracht van quantumcomputing op een compleet nieuw soort moeilijkheidsgraad, of is het in het geheim gewoon een zeer efficiënte versie van klassieke computing in vermomming? Specifiek hebben onderzoekers zich afgevraagd of elke mogelijke operatie die een quantumcomputer kan uitvoeren, kan worden afgebroken tot een reeks stappen die een klassieke computer uiteindelijk zou kunnen ontcijferen, indien voorzien van de juiste hints. Als het antwoord ja is, dan is de unieke kracht van quantumcryptografie misschien een illusie. Als het antwoord nee is, dan bezitten quantumcomputers een fundamentele kracht die klassieke machines nooit kunnen evenaren.

Twee onderzoekers, William Kretschmer en Ewin Tang, hebben onlangs een belangrijke stap gezet naar het oplossen van deze onzekerheid. Ze hebben het mysterie niet volledig opgelost, maar ze hebben een krachtige logische brug gebouwd die het bestaan van veilige quantumcryptografie verbindt met enkele van de oudste, meest hardnekkige onopgeloste problemen in de klassieke computerwetenschap. Hun werk suggereert dat als veilige quantumcryptografie in de echte wereld bestaat, dan ofwel een van de twee waar moet zijn: ofwel er is een fundamentele limiet aan hoe goed we quantumoperaties naar klassieke instructies kunnen vertalen, ofwel een specifieke, decennia-oude vraag over de kracht van klassieke computers moet een verrassend antwoord hebben.

Om hun prestatie te begrijpen, moet men eerst de aard van de taak begrijpen die zij analyseren. Stel je een quantumcomputer voor als een apparaat dat een complex, multidimensionaal object kan roteren op een manier die perfect omkeerbaar is. Het "unitary synthesis problem" vraagt of we, voor elke dergelijke rotatie, een set klassieke instructies kunnen vinden die een standaardcomputer zou kunnen volgen om die rotatie na te bootsen. Als we dit altijd zouden kunnen doen, zou dit betekenen dat de quantumwereld in zekere zin slechts een zeer ingewikkelde versie van de klassieke wereld is. De onderzoekers concentreerden zich op een specifieke klasse van deze rotaties: die welke een quantumcomputer kan uitvoeren met een redelijke hoeveelheid geheugen. Ze vroegen zich af of deze specifieke rotaties altijd gesynthetiseerd konden worden door een klassieke computer met de hulp van een oracle, wat essentieel een magische zwarte doos is die instantaan specifieke vragen kan beantwoorden.

De auteurs begonnen met het aanpakken van een praktische hindernis: hoe definieer je deze quantumtaken precies. Eerdere pogingen om deze te categoriseren hadden geleid tot verwarrende resultaten, deels omdat ze toestonden dat er "garbage" (afval) achterbleef tijdens de berekening. In quantumcomputing, wanneer een machine een berekening uitvoert, laat deze vaak extra data achter die niet langer nodig is, maar die niet simpelweg verwijderd kan worden zonder het resultaat te verstoren. Sommige definities stond dit rommelige, afvalrijke proces toe, terwijl andere een perfect schoon proces vereisten. Kretschmer en Tang toonden aan dat dit onderscheid er niet toe doet voor taken die grote hoeveelheden geheugen inhouden. Ze bewezen dat elk rommelig, afvalrijk quantumproces kan worden omgezet in een schoon, afvalvrij proces zonder de fundamentele moeilijkheidsgraad van de taak te veranderen. Dit was een cruciale stap, aangezien het hen in staat stelde om deze complexe quantumoperaties met een niveau van wiskundige helderheid te behandelen dat eerder ontbrak.

Met deze definities op hun plaats, pakten ze de kernvraag aan. Ze demonstreerden dat voor elke quantumoperatie die uitgevoerd kan worden met polynomiale ruimte (een beheersbare hoeveelheid geheugen), er slechts twee mogelijkheden zijn. Ofwel de operatie is zo complex dat geen enkele klassieke computer, ongeacht hoe slim of hoeveel hulp hij ook krijgt van een oracle, deze efficiënt kan synthetiseren. Ofwel de operatie is helemaal niet zo moeilijk; deze kan efficiënt worden gesynthetiseerd als de klassieke computer de mogelijkheid heeft om vragen te stellen over een specif kind van een moeilijk probleem dat bekend staat als een NEXP search problem. Deze tweede categorie is een zeer hoge lat in de klassieke complexiteitstheorie, en vertegenwoordigt problemen die exponentieel moeilijker zijn dan de moeilijkste problemen die we momenteel kennen.

De implicaties van deze bevinding zijn diepgaand, met name voor de toekomst van de cryptografie. Quantumcryptografie rust op het idee dat bepaalde taken, zoals het creëren van een veilige commitment scheme (een manier om een geheim in een digitale doos te vergrendelen zodat het niet kan worden gewijzigd of ingezien), onmogelijk zijn voor een tegenstander om te breken. Als veilige quantumcommitments bestaan, dicteert de logica van de onderzoekers dat we ons in een zeer specifieke situatie bevinden. Ofwel het unitary synthesis problem heeft een negatief antwoord, wat betekent dat er quantumoperaties zijn die fundamenteel buiten het bereik liggen van klassieke synthese, ofwel een grote klassieke complexiteitsvraag moet worden opgelost. Specifiek zou het impliceren dat een klasse van problemen genaamd BPP (problemen die snel oplosbaar zijn met toeval) niet gelijk is aan NEXP (problemen die oplosbaar zijn met exponentiële tijd en niet-determinisme). Dit is een vraag die al meer dan veertig jaar onbeantwoord blijft.

In simpelere termen betoogt het artikel dat het bewijzen van het bestaan van veilige quantumcryptografie niet alleen een kwestie is van het bouwen van betere quantumapparaten. Het is onlosmakelijk verbonden met de diepste theoretische limieten van de klassieke informatica. Als we onvoorwaardelijk zouden kunnen bewijzen dat quantumcommitments veilig zijn, zouden we tegelijkertijd gedwongen worden een van de twee enorme, decennia-oude raadsels in de computerwetenschap te beantwoorden. We zouden ofwel moeten accepteren dat quantumoperaties fundamenteel moeilijker te simuleren zijn dan we dachten, of we zouden moeten bewijzen dat een specifiek, ongelooflijk krachtig type klassieke berekening strikt meer in staat is dan een standaard gerandomiseerde berekening.

Het werk werpt ook licht op de relatie tussen de quantum- en klassieke kracht in een algemenere zin. De auteurs toonden aan dat als we aannemen dat het unitary synthesis problem een positief antwoord heeft (dat alles gesynthetiseerd kan worden), de kracht van quantumcomputers met grote geheugens nauw wordt beperkt door de kracht van klassieke computers die NEXP search problems oplossen. Dit suggereert dat de "magie" van quantumcomputing, indien aanwezig, geen vrij zwevend fenomeen is, maar diep geworteld is in de structuur van de klassieke complexiteit. Als quantumcomputers iets echt nieuws kunnen doen, is dat omdat ze toegang krijgen tot een laag van moeilijkheid die klassieke computers niet kunnen bereiken, zelfs niet met de beste mogelijke afkortingen.

Uiteindelijk vertelt dit onderzoek ons niet of quantumcryptografie veilig is of of het unitary synthesis problem oplosbaar is. In plaats daarvan brengt het het terrein in kaart tussen deze twee mogelijkheden. Het onthult dat de weg naar het bewijzen van de veiligheid van quantumsystemen wordt geblokkeerd door dezelfde muren die klassieke complexiteitstheoretici al een halve eeuw van hun moeilijkste problemen houden. Het artikel suggereert dat we niet simpelweg onze weg naar een bewijs kunnen bouwen; we moeten eerst de fundamentele limieten van de berekenbaarheid zelf begrijpen. Door de definities te verhelderen en deze rigoureuze verbindingen vast te leggen, hebben Kretschmer en Tang een duidelijker zicht op het landschap geboden, waarbij zij laten zien dat het lot van de quantumcryptografie en het lot van de klassieke complexiteitstheorie op een manier aan elkaar verbonden zijn die voorheen niet begrepen werd.