State Synthesis with an NP oracle

In de kwantumwereld wordt informatie niet opgeslagen als eenvoudige nullen en enen, maar als delicate, schitterende golven van waarschijnlijkheid. Om een bruikbare kwantumcomputer te bouwen, moeten wetenschappers leren hoe ze deze golven in specifieke vormen kunnen boetseren, een proces dat bekend staat als staatvoorbereiding (state preparation). Stel je voor dat je probeert een uniek, complex beeldhouwwerk van licht te maken; de uitdaging is dat de instructies voor dit beeldhouwwerk ongelooflijk moeilijk op te schrijven kunnen zijn, wat een niveau van berekening vereist dat voor elke machine onmogelijk lijkt om snel uit te voeren. Jarenlang hebben onderzoekers zich afgevraagd of de moeilijkheid van het creëren van deze kwantumtoestanden verbonden is aan de moeilijkheid van het oplossen van bepaalde klassieke puzzels. Als een computer een specifiek type moeilijke puzzel kan oplossen, kan hij dan ook direct de overeenkomstige kwantumtoestand oproepen? Deze vraag bevindt zich op het snijvlak van twee enorme gebieden: de studie naar hoe moeilijk problemen zijn om op te lossen, en de studie naar hoe kwantummachines de realiteit manipuleren.

Een nieuw artikel van Aniruddha Sen van de University of Texas at Austin biedt een verrassend antwoord op deze vraag. Het onderzoek toont aan dat een kwantumcomputer, als deze toegang heeft tot een specifiek type probleemoplossende helper, elke gewenste kwantumtoestand met extreme precisie in een redelijke tijd kan creëren. De helper die in dit scenario wordt gebruikt, is een "NP-orakel", een theoretisch hulpmiddel dat onmiddellijk kan verifiëren of een voorgestelde oplossing voor een complexe puzzel correct is. Vóór dit werk vereiste de beste bekende methode een veel krachtigere, en naar verluidt meer abstracte, soort helper genaamd een "PP-orakel". Sens algoritme laat zien dat de zwakkere NP-helper eigenlijk voldoende is, mits de computer ook een blik kan werpen op de ruwe getallen die de kwantumtoestand definiëren die hij probeert te bouwen. Deze bevinding suggereert dat het vermogen om oplossingen te verifiëren bijna even krachtig is als het vermogen om ze op te lossen wanneer het gaat om het genereren van kwantummaterie.

De kern van de prestatie ligt in de manier waarop het algoritme de toestand opbouwt. Traditioneel is het creëren van een complexe kwantumtoestand als het construeren van een gebouw verdieping voor verdieping, waarbij elke nieuwe laag afhankelijk is van het exacte gewicht van de verdiepingen eronder. Om dit te doen, moet een computer meestal de som van een enorm aantal mogelijkheden berekenen, een taak die doorgaans een zwaarbelast PP-orakel vereist. Sens aanpak gebruikt echter een slim tweetrapsstrategie. Eerst gebruikt het de NP-orakel om een ruwe, benaderde versie van de toestand te verkrijgen. Dit is niet perfect, maar het is goed genoeg om als fundament te dienen. Vervolgens voert het algoritme een tweede passage uit, waarbij dezelfde NP-orakel wordt gebruikt om het verschil te controleren tussen deze ruwe benadering en de werkelijke doeltoestand. Door de twee te vergelijken, kan de computer de fouten isoleren en corrigeren.

Om deze correctie werkbaar te maken, maakt het algoritme gebruik van een techniek genaamd kwantum-rejection sampling. In dit proces creëert de computer een superpositie waarin de juiste delen van de toestand licht worden versterkt en de onjuiste delen worden onderdrukt. Het is vergelijkbaar met een zeef die de juiste zandkorrels doorlaat terwijl de verkeerde tegenhoudt, maar het gebeurt in de kwantumwereld waar de "zeef" een wiskundige rotatie van waarschijnlijkheidsgolven is. Zodra de fouten zijn weggefilterd, zorgt een laatste stap, genaamd amplitude amplification, ervoor dat de waarschijnlijkheid van de juiste uitkomst wordt vergroot totdat deze bijna zeker is. Het resultaat is een kwantumtoestand die de doeltoestand met een precisie evenaart die zo hoog is dat de kans op een fout kleiner is dan één op een biljard biljard.

Het artikel behandelt ook de grenzen van deze kracht. Sen levert sterk bewijs dat het NP-orakel de zwakst mogelijke helper is die deze taak efficiënt kan volbrengen. Het onderzoek toont aan dat als de computer beperkt zou zijn tot het gebruik van een standaard "P-orakel", dat eenvoudige problemen kan oplossen, hij een exponentieel groot aantal vragen zou moeten stellen om de klus te klaren. Dit impliceert dat de sprong van eenvoudige problemen naar NP-problemen de kritieke drempel is voor efficiënte kwantumtoestandcreatie. De auteur bewijst dit door aan te tonen dat elk algoritme dat een zwakker orakel gebruikt, zou falen om een fundamenteel zoekprobleem binnen een redelijke tijd op te lossen, wat de mogelijkheid uitsluit om eenvoudigere hulpmiddelen voor deze specifieke kwantumtaak te gebruiken.

Buiten de mechanica van het algoritme heeft het werk aanzienlijke implicaties voor het bredere veld van de kwantumcomplexiteit. Het suggereert dat de moeilijke taak van het voorbereiden van een kwantumtoestand, vaak gezien als een zoektocht naar een verborgen getuige (witness), kan worden teruggebracht tot de eenvoudigere taak van het berekenen van de getallen die die toestand beschrijven. Dit verbindt de kwantumwereld van QMA, een complexiteitsklasse voor kwantumbewijzen, met de klassieke wereld van NP. De bevindingen openen ook de deur naar een grotere vraag: als we met een NP-orakel elke toestand kunnen creëren, kunnen we dan ook elke kwantumoperatie, of unitair, met hetzelfde hulpmiddel bouwen? Hoewel het artikel dit grotere puzzelstuk niet oplost, legt het een duidelijk pad vooruit, waarbij suggereert dat dezelfde technieken van toepassing kunnen zijn op het algemenere probleem van kwantum unitair synthese.

Het onderzoek vormt een verfijning van ons begrip van wat kwantumcomputers kunnen bereiken met beperkte middelen. Door aan te tonen dat een relatief bescheiden orakel genoeg is om elke kwantumtoestand te genereren, verkleint het artikel de kloof tussen theoretische mogelijkheid en praktische implementatie. Het bevestigt dat de barrière voor het creëren van complexe kwantumtoestanden geen onoverkomelijke muur van rekenkracht is, maar een specifere vorm van logische verificatie die goed binnen het bereik van bekende complexiteitsklassen valt. Terwijl het veld beweegt naar het bouwen van werkelijke kwantummachines, is weten hoeveel hulp er precies nodig is om deze lichttoestanden te boetseren een essentieel onderdeel van de engineeringpuzzel.