Correlations decide a shallow-circuit advantage

In de race om te bewijzen dat kwantumcomputers dingen kunnen doen die gewone machines niet kunnen, worden wetenschappers geconfronteerd met een bijzonder probleem: hoe het resultaat te verifiëren zonder de machine zelf te vertrouwen. Stel je een apparaat voor dat beweert een specifieke, complexe reeks willekeurige getallen te genereren. Een klassieke computer, hoe krachtig ook, zou dat patroon kunnen vervalsen als het de mogelijkheid krijgt om de output te bekijken en de strategie aan te passen. De uitdaging is om een test te vinden die een klassieke computer niet kan passeren, zelfs niet als deze de resultaten ziet, mits de klassieke computer beperkt is in hoeveel informatie het kan vasthouden en hoe snel het deze kan verwerken. Dit is de grens van "sampling advantage", waarbij het doel niet alleen is om aan te tonen dat een kwantummachine werkt, maar om te bewijzen dat de output van die machine fundamenteel onmogelijk is voor een beperkte klasse klassieke computers om na te bootsen. De belangen zijn groot, want zonder een betrouwbare, aannamevrije test blijft de claim van kwantumsuperioriteit een kwestie van geloof in plaats van een feit.

Een team van onderzoekers heeft nu zo'n test gebouwd, die niet rust op het meten van hoe ver een resultaat afstaat van het ideaal, maar op het controleren van de verborgen relaties tussen de bits in de output. Hun werk richt zich op een specifiek type kwantumcircuit dat zeer snel draait, gebruikmakend van een speciale verstrengelde toestand van 43 qubits als bron. Deze toestand is als een enkele, gesynchroniseerde schakelaar die al zijn onderdelen tegelijkertijd omzet. De kwantummachine gebruikt dit om een reeks bits te produceren, waarbij de laatste bit een label is dat wordt berekend op basis van de rest. De onderzoekers ontwierpen een verificatieprotocol dat een simpele vraag stelt: komt het label overeen met de berekening? Als de machine eerlijk is, zal het label bijna elke keer overeenkomen. Als een klassieke computer probeert af te wijken, zal deze uiteindelijk falen, maar de onderzoekers moesten precies uitzoeken hoe ze hem konden betrappen.

Het team ontdekte dat de sleutel tot het betrappen van een afwijker ligt in de correlaties tussen de bits, en niet alleen in de algemene afstand tot het doel. Ze bewezen dat elke klassieke computer die beperkt is in zijn complexiteit, ofwel het label te vaak foutief zal geven, ofwel er niet in zal slagen een willekeurig ogende reeks bits te produceren. Dit inzicht leidde tot een tweeledige test. Het eerste deel telt simpelweg hoe vaak het label fout is. Als de foutmarge te hoog is, wordt de machine onmiddellijk afgewezen. Dit deel van de test is wiskundig bewezen optimaal en werkt voor elke machine die probeert af te wijken, ongeacht hoe deze is gebouwd. Het is een robuuste, onvoorwaardelijke controle die slechts een polynomiaal aantal monsters vereist om betrouwbaar te zijn.

Echter, een slimme afwijker zou kunnen proberen het label elke keer goed te krijgen, terwijl de geproduceerde reeks nog steeds niet echt willekeurig is. Om dit te vangen, ontwikkelden de onderzoekers een tweede laag controles, een set van vijf verschillende "deuren" waar de output doorheen moet gaan. Vier van deze deuren kijken naar algemene eigenschappen van de reeks, zoals of de bits gelijkmatig verdeeld zijn of of de reeks een bepaalde wiskundige rang heeft. De onderzoekers toonden door rigoureuze constructie aan dat een klassieke computer deze vier deuren kon passeren terwijl hij nog steeds een vervalsing was. Ze bouwden een specifiek voorbeeld van een klassieke machine die alle vier de controles bedroog, waarmee ze bewezen dat deze standaardtests op zichzelf onvoldoende waren.

De doorbraak kwam met de vijfde deur, die kijkt naar iets subtielers: de specifieke, gekwantiseerde correlaties tussen paren bits. In tegenstelling tot de andere controles, die naar de reeks als geheel kijken, onderzoekt deze deur hoe individuele bits zich tot elkaar verhouden op een manier die uniek is voor de klasse van eenvoudige klassieke circuits. Ze bewezen dat elke machine die beperkt is tot het lezen van slechts een paar willekeurige zaden om zijn output te genereren, deze correlaties moet hebben in specifieke, discrete waarden. Een echt willekeurige reeks, of een gegenereerd door een kwantummachine, zou deze specifieke waarden niet hebben. Door op deze correlaties te controleren, creëerden de onderzoekers een test die de afwijker vangt die de andere vier deuren misten.

Het artikel bevestigt dat deze gecombineerde test werkt voor een breed scala aan klassieke machines, specifiek die waarbij elke outputbit slechts afhangt van een klein aantal willekeurige inputs. De onderzoekers gebruikten een computer-bewijsassistent om elke stap van hun wiskundige argumenten te verifiëren, om te verzekeren dat de logica zonder hiaten standhoudt. Ze hebben ook aangetoond dat de test solide is tegen een specifieke, brede klasse van klassieke samplers die bekend staan als "bounded pinned-residue" samplers. Voor deze machines is de test niet alleen effectief, maar ook wiskundig gegarandeerd te werken.

Er is nog één puzzelstukje dat onopgelost blijft. De onderzoekers identificeerden een smalle, theoretische kloof waar een zeer complexe klassieke machine nog steeds door de mazen van het net zou kunnen glippen. Deze kloof betreft een machine die ver van het doel afstaat maar zijn willekeur op een manier verspreidt die moeilijk te detecteren is met een beperkt aantal monsters. Hoewel ze deze kloof nog niet hebben gedicht, hebben ze het probleem teruggebracht tot een precieze, goed gedefinieerde vraag. Ze hebben aangetoond dat als deze kloof gedicht kan worden, de test compleet en aannamevrij zal zijn voor alle klassieke machines van dit type.

De fysieke vereiste voor deze test is verrassend bescheiden. Het kwantumapparaat moet een 43-qubit verstrengelde toestand voorbereiden met een fidelity van ongeveer 0,99, wat betekent dat het 99% van de tijd correct is. Dit is een uitdagend maar haalbaar doel voor de huidige technologie, en de voorbereiding van deze toestand, en niet het uitlezen van de output, is de kritieke hulpbron. De test zelf is puur klassiek; het vereist alleen het uitlezen van de door de machine geproduceerde bits en het controleren ervan aan de hand van de regels.

Dit werk vormt een belangrijke stap voorwaarts in de verificatie van kwantumvoordeel. Het beweegt het veld weg van het vertrouwen op onbewezen aannames of complexe apparaatmodellen en naar een test die geworteld is in de fundamentele beperkingen van klassieke berekeningen. Door te bewijzen dat vier natuurlijke controles onvoldoende zijn en een vijfde te bieden die wel werkt, hebben de onderzoekers een duidelijk pad gebaand om te certificeren dat een kwantumcomputer iets doet wat een klassieke computer niet kan. Het resterende openstaande probleem is een kwestie van wiskundige verfijning, niet van een fundamentele barrière, en het kader dat zij hebben opgebouwd biedt de instrumenten om het op te lossen. Het resultaat is een verificatieprotocol dat zo dicht bij een definitief bewijs staat als de wetenschap momenteel kan bieden, waarbij het vertrouwt op de structuur van de data zelf om de aard van de machine te onthullen die het heeft voortgebracht.