Random-Oracle Unitary Synthesis is Impossible

In de kwantumwereld staat de fundamentele natuurkunde toe dat er een bijna oneindige variëteit aan transformaties bestaat. Stel je een machine voor die een stukje informatie kan nemen en het kan vervormen tot elke gewenste vorm, hoe complex of vreemd ook. Deze transformaties, bekend als unitair, zijn de bouwstenen van quantumcomputing. Echter, alleen omdat de natuur een transformatie toestaat, betekent dit niet dat een computer deze ook kan bouwen. Er bestaat een enorme kloof tussen de unitair die gemakkelijk te construeren zijn en de transformaties die met de huidige technologie effectief onmogelijk te creëren zijn. Decennialang hebben wetenschappers zich afgevraagd of deze kloof echt is of dat het slechts een gat in ons begrip is. Specifiek vroegen zij zich af of elke moeilijke quantumtransformatie gebouwd kon worden door simpelweg te weten hoe men een specifieke, moeilijke klassieke functie berekent. Als het antwoord ja was, zou dit betekenen dat de moeilijkste problemen in quantumcomputing net zo moeilijk zijn als de moeilijkste problemen in klassieke computing, waardoor de twee werelden nauw met elkaar verbonden zijn. Als het antwoord nee was, zou dit suggereren dat de kwantummechanica geheimen bevat die de klassieke logica niet kan ontsluiten, wat potentieel een geheel nieuwe theorie van complexiteit vereist.

Een team van onderzoekers heeft deze vraag nu onderzocht door de regels van het spel licht te veranderen. In plaats van te vragen of een computer een specifieke transformatie kan bouwen met behulp van een specifieke, ingewikkelde functie, vroegen zij of een computer een volledig willekeurige, onvoorspelbare transformatie kon bouwen met behulp van een willekeurige, structuurloze functie. Deze verschuiving stelde hen in staat om de grenzen te testen van wat mogelijk is wanneer de invoerdata geen verborgen patronen heeft om te exploiteren. Hun bevindingen zijn definitief: het is onmogelijk om efficiënt een werkelijk willekeurige quantumtransformatie te synthetiseren met behruik van slechts een willekeurige functie. Ze bewezen dat geen enkel algoritme, hoe slim ook, een gewenste quantumtoestand kan creëren als het steunt op een functie die willekeurig is gekozen, zonder dat het een astronomisch groot aantal vragen moet stellen. Dit resultaat beslecht een langlopend debat door aan te tonen dat het vermogen om complexe quantumtoestanden te bouwen volledig afhangt van de structuur van de verstrekte informatie. Zonder die structuur blijft de taak buiten bereik.

De onderzoekers verkenden ook een gerelateerd concept dat wordt gebruikt in de kwantumcryptografie: pseudowillekeurige unitair. Dit zijn quantumtransformaties die willekeurig lijken voor iedereen die de geheime sleutel niet kent die gebruikt is om ze te creëren, ook al zijn ze gebouwd door een eenvoudig, efficiënt proces. Jarenlang waren de beste bekende methoden voor het creëren van deze "nep" willekeurige transformaties beperkt; ze konden alleen een waarnemer misleiden die een relatief klein aantal vragen stelde. De onderzoekers wilden weten of deze limiet een tijdelijke technische hindernis was of een fundamentele natuurwet. Ze construeerden een nieuwe methode die deze transformaties succesvol creëert op een manier die veilig blijft tegen een waarnemer die een veel groter aantal vragen stelt, specifweg tot een aantal dat proportioneel is aan de totale omvang van het systeem. Dit is een significante verbetering ten opzichte van eerdere methoden, die slechts een aantal vragen konden afhandelen dat proportioneel was aan de wortel van de systeemomvang.

Hun werk onthulde echter ook een hard plafond. Hoewel ze de beveiliging van deze nep willekeurige transformaties veel verder konden pushen dan voorheen, bewezen ze dat het onmogelijk is om het helemaal tot het theoretische maximum te drijven zonder het proces inefficiënt te maken. Ze demonstreerden dat als een methode efficiënt moet zijn in termen van het aantal stappen dat het neemt, deze niet beveiligd kan blijven tegen een waarnemer die een zeer groot aantal vragen stelt. Dit creëert een precieze grens: je kunt een methode hebben die efficiënt is en beveiligd tegen een gemiddeld aantal vragen, of je kunt een methode hebben die beveiligd is tegen een enorm aantal vragen, maar je kunt niet beide tegelijkertijd hebben. Deze bevinding suggereert dat de huidige beperkingen in de kwantumcryptografie niet slechts een kwestie zijn van wachten op betere algoritmen; ze zijn waarschijnlijk een fundamentele beperking van het universum.

De studie richtte zich ook op de bredere vraag of we ooit een universele machine kunnen bouwen die elke quantumtransformatie kan synthetiseren, gegeven de juiste klassieke instructies. Door aan te tonen dat willekeurige invoer geen willekeurige uitvoer produceert, leverden de onderzoekers sterk bewijs dat de structuur van de invoer essentieel is. Het is niet genoeg om een krachtige computer en een willekeurige functie te hebben; de functie zelf moet zorgvuldig worden ontworpen om de computer naar het gewenste resultaat te leiden. Dit impliceert dat de moeilijkheid van het creëren van bepaalde quantumtoestanden niet alleen een kwestie is van rekenkracht, maar inherent is aan de aard van de informatie die nodig is om hen te beschrijven. Het werk sluit effectief de deur op de gedachte dat een eenvoudige, willekeurige oracle zou kunnen dienen als een universele sleutel om alle quantummogelijkheden te ontsluiten.

Uiteindelijk schetst het artikel een beeld van een quantumlandschap waar efficiëntie en willekeur in spanning met elkaar staan. De onderzoekers toonden aan dat we weliswaar zeer overtuigende imitaties van willekeur kunnen creëren, maar dat er een harde limiet is aan hoe goed die imitaties kunnen zijn als we het proces snel willen houden. Ze toonden ook aan dat de hoop om een eenvoudige, willekeurige functie te gebruiken om elke quantumtransformatie te bouwen, ongegrond is. De resultaten bieden niet alleen een nieuw algoritme of een nieuwe beperking; ze herdefiniëren de grenzen van wat mogelijk is in de kwantumwereld. Ze vertellen ons dat de complexiteit van de kwantumwereld geen illusie is die kan worden omzeild met een slim trucje, maar een reëel kenmerk dat specifieke, gestructureerde informatie vereist om doorheen te navigeren. Voor hen die de toekomst van de kwantumtechnologie bouwen, betekent dit dat de weg vooruit niet alleen meer kracht vereist, maar ook meer precisie in het ontwerp. Het universum, zo lijkt het, eist dat we precies weten wat we vragen voordat het ons het antwoord geeft.