Unitary RQL Equals RQL

Kwantumcomputers worden vaak voorgesteld als machines die vele mogelijkheden tegelijkertijd vasthouden, waarbij ze een uitgestrekt landschap van uitkomsten simultaan verkennen. Om deze kracht te benutten, moet een computer in staat zijn om onderweg de voortgang te controleren, paden die nergens toe leiden te verwerpen en middelen te concentreren op de paden die veelbelovend lijken. In de taal van de kwantumfysica wordt dit controleproces een meting genoemd. Het is de handeling van het kijken naar een stuk informatie, wat het systeem dwingt een definitieve staat te kiezen en de computer in staat stelt de rest weg te gooien. Decennialang heeft een fundamentele vraag rondgehangen in het onderzoek naar hoeveel geheugen deze machines nodig hebben: als een computer wordt toegestaan om tijdens een berekening de voortgang te bekijken en informatie weg te gooien, wordt hij dan krachtiger dan een computer die gedwongen is te wachten tot het allerlaatste moment om te kijken?

Het antwoord hangt sterk af van de regels van het spel. Als de computer fouten aan beide kanten mag maken — soms "ja" zeggen wanneer het "nee" zou moeten zijn, en vice versa — wisten onderzoekers al dat het vermogen om tussentijds te meten geen echt voordeel oplevert. Een machine die tot het einde wacht, kan alles doen wat een machine die vroeg meet kan doen, mits beide een kleine foutmarge toestaan. Echter, een striktere versie van de regels verandert het beeld. In dit striktere scenario is de computer verboden om ooit een specifieke soort fout te maken: hij mag nooit "ja" zeggen als het antwoord eigenlijk "nee" is. Hij kan nog steeds fouten maken aan de andere kant, maar de kost van een vals positief resultaat is nul. Voor dit geval van eenzijdige fouten was het onbekend of het vermogen om vroeg te meten en informatie weg te gooien enige extra kracht bood. De vraag was of een machine die nooit onjuist mag zijn over een "nee"-antwoord, gedwongen kon worden om tot het einde te wachten zonder het vermogen om problemen efficiënt op te lossen te verliezen.

Een onderzoeker heeft deze vraag nu beantwoord door te bewijzen dat het vermogen om vroeg te meten ook in dit strikte scenario geen voordeel biedt. Hij toonde aan dat elke kwantumcomputer die met beperkt geheugen werkt, geen valse "ja"-oproepen doet en wordt toegestaan om tussentijds te meten, perfect gesimuleerd kan worden door een machine die nooit meet tot de allerlaatste stap. De twee soorten machines zijn, wat betreft wat ze kunnen oplossen, exact hetzelfde. De onderzoeker suggereerde dit niet alleen; hij leverde een rigoureus wiskundig bewijs dat een specifieke methode construeert voor het omzetten van de vroeg-metende machine naar een wachtende machine. Dit resultaat is van toepassing op een breed scala aan standaard kwantum bouwstenen, inclus\nuit de bouwstenen die vandaag de dag in de meest voorkomende ontwerpen voor kwantumcomputers worden gebruikt.

De kern van de ontdekking ligt in de manier waarop de onderzoeker omging met de informatie die normaal gesproken zou worden weggegooid. In een standaardberekening, wanneer een machine een bit meet en een nul ziet, kan het de machine deels van het systeem dat een één toonde laten weggooien. Als de machine niet wordt toegestaan om vroeg te meten, moet hij dat weggegooide deel in leven houden, wat meestal extra geheugen vereist. De onderzoeker vond een manier om de weggegooide informatie in leven te houden zonder extra geheugen te gebruiken, door de gehele geschiedenis van de berekening als één enkel, verenigd object te behandelen. Hij ontwikkelde een techniek die effectief de omvang van de beschrijving van het systeem verdubbelt, niet door meer fysiek geheugen toe te voegen, maar door de manier waarop de informatie wordt opgeslagen te reorganiseren.

Stel je een berekening voor als een lange keten van gebeurtenissen. In de oude manier van denken, als de computer naar een schakel in de keten kijkt en besluit deze af te snijden, is dat deel van de keten voor altijd weg. De nieuwe methode houdt de afgesneden schakel eraan vast, maar op een manier dat deze de uiteindelijke uitkomst niet kan beïnvloeden, tenzij de hele keten had moeten slagen. De onderzoeker bereikte dit door een speciale "referentie"-staat te creëren die het gemiddelde gedrag van het systeem bijhoudt. Hij gebruikte deze referentie om het gewicht van de verschillende delen van de berekening gaandeweg aan te passen. Deze aanpassing zorgde ervoor dat als de oorspronkelijke machine een probleem zou hebben afgewezen, de nieuwe machine het ook met absolute zekerheid zou afwijzen, waardoor de garantie van nul fouten behouden bleef. Tegelijkertijd zorgde de methode ervoor dat als de oorspronkelijke machine een probleem zou hebben geaccepteerd, de nieuwe machine nog steeds een goede kans zou hebben om het te accepteren, zelfs hoewel hij gedwongen werd om alle weggegooide informatie in leven te houden.

Het bewijs behelst een slimme truc om om te gaan met het feit dat het bijhouden van alle informatie de betrokken getallen gewoon te groot maakt om te beheren. De onderzoeker introduceerde een systeem van gewichten die elkaar af cancelen naarmate de berekening vordert. Hij voegde een klein beetje willekeurige ruis toe aan het systeem bij elke stap, wat contra-intuïtief klinkt, maar het voorkomt er feitelijk voor dat de getallen instabiel worden. Deze ruis stelt hen in staat om de verschillende delen van de berekening te schalen zodat ze beheersbaar blijven. Ze toonden vervolgens aan dat het deel van de berekening dat overeenkomt met de "weggegooide" informatie kan worden gesimuleerd met standaard kwantum-gates, mits deze gates exacte wiskundige inversen hebben. Aan deze vereiste wordt voldaan door de standaard sets gates die in de meeste kwantumonderzoek worden gebruikt.

De onderzoeker onderzocht ook of dit resultaat standhoudt voor verschillende soorten kwantum-gates, inclusief die met complexere wiskundige eigenschappen. Hij vond dat zolang de gates behoren tot een specifieke familie van getallen bekend als CM-velden, het resultaat standhoudt. Deze familie omvat de standaard gates die in de meeste kwantumalgoritmen worden gebruikt, evenals enkele meer exotische varianten. Dit betekent dat de bevinding niet beperkt is tot één enkel, nauw ontwerp, maar van toepassing is op een brede klasse van potentiële kwantumcomputers. Het bewijs strekt zich ook uit tot een gerelateerd scenario waarbij een verifieerder een getuige controleert, een opstelling die vaak wordt gebruikt in de cryptografie en complexiteitstheorie. In dit geval toonden zij aan dat een verifieerder die een correct antwoord met perfecte zekerheid moet accepteren, ook kan worden omgezet in een machine die wacht tot het einde om te meten, zonder die perfecte zekerheid te verliezen.

Dit werk lost een langlopend open probleem in de theorie van de kwantumcomputing op. Het bevestigt dat de kracht van kwantumcomputers met beperkt geheugen niet voortkomt uit het vermogen om hun voortgang te bekijken en informatie weg te gooien. In plaats daarvan komt de kracht voort uit de onderliggende kwantummechanica zelf. Het vermogen om vroeg te meten is een gemak, geen noodzaak, voor machines die strikt correct moeten zijn over negatieve antwoorden. De constructie van de onderzoeker biedt een blauwdruk voor hoe een dergelijke machine gebouwd zou kunnen worden, waarbij wordt aangetoond dat het extra geheugen dat gewoonlijk wordt gedacht te worden voor deze conversie, eigenlijk niet nodig is. Het resultaat versterkt ons begrip van de fundamentele grenzen van kwantumcomputatie en suggereert dat de meest efficiënte kwantumalgoritmen misschien helemaal niet afhankelijk hoeven te zijn van tussenliggende metingen.

De implicaties van deze bevinding zijn primair theoretisch en helpen het landschap in kaart te brengen van wat kwantumcomputers wel en niet kunnen doen. Het verheldert de relatie tussen verschillende modellen van berekening en neemt een mogelijke bron van verwarring weg over waar het kwantumvoordeel vandaan komt. Door te bewijzen dat de twee modellen equivalent zijn, heeft de onderzoeker de gereedschapskist voor het analyseren van kwantumalgoritmen vereenvoudigd. Toekomstig werk kan zich nu richten op de eigenschappen van het wachtende model, in de wetenschap dat elk resultaat dat daar wordt gevonden, evenredig geldt voor het meer flexibele meetmodel. Het artikel beweert geen fysieke machine te hebben gebouwd die deze methode gebruikt, noch suggereert het onmiddellijke veranderingen in hoe kwantumcomputers momenteel worden ontworpen. In plaats daarvan biedt het een solide wiskundige basis die garandeert dat de theoretische grenzen van deze machines goed begrepen zijn. Het bewijs is compleet en rigoureus, waardoor er geen ruimte is voor twijfel over de gelijkwaardigheid van deze twee manieren om een kwantumcalculatie uit te voeren onder de gespecificeerde beperkingen.