Exponential lower bounds on the fermionic Gaussian rank of magic states and the bosonic coherent state rank of Fock states

In de zoektocht naar het begrijpen van hoe het universum werkt op zijn kleinste schaal, hebben natuurkundigen lang vertrouwd op een krachtige truc: als een systeem eenvoudig genoeg is, kunnen we het gedrag ervan berekenen met een standaardcomputer. Decennialang kon een specifieke klasse kwantumsystemen—die bestaan uit deeltjes die strikte regels van uitsluiting en symmetrie volgen, bekend als fermionen—efficiënt worden gesimuleerd. Deze systemen, die vaak worden beschreven als "vrij" of "Gaussiaans", gedragen zich op een voorspelbare, ordelijke manier die klassieke machines zonder moeite kunnen aan kunnen. Echter, om een werkelijk krachtige kwantumcomputer te bouwen, moeten wetenschappers een speciaal ingrediënt introduceren dat deze orde doorbreekt. Ze noemen deze ingrediënten "magic states" (magische toestanden). Dit zijn zeer complexe kwantumconfiguraties die, wanneer ze aan de eenvoudige systemen worden toegevoegd, het vermogen ontgrendelen om berekeningen uit te voeren die onmogelijk zijn voor klassieke computers bij te houden. De centrale vraag voor onderzoekers is geweest: hoeveel extra werk moet een klassieke computer precies verrichten om deze magische toestanden te simuleren? Het antwoord ligt in een getal dat de "rang" wordt genoemd, wat in essentie telt hoeveel eenvoudige, ordelijke stukjes nodig zijn om één enkele complexe, magische eenheid te bouren.

Jarenlang wisten wetenschappers dat dit getal groot moest zijn, maar konden ze niet bewijzen hoe groot precies. Ze wisten dat het snel groeide naarmate je meer magische toestanden toevoegde, maar de beste wiskundige bewijzen toonden slechts aan dat het met een trage, kwadratische snelheid groeide, terwijl de meest basale simulaties suggereerden dat het exponentieel zou kunnen groeien. Deze kloof liet een enorme onzekerheid achter in het vakgebied. Als het aantal traag groeide, zou het mogelijk zijn om deze krachtige kwantumcomputers uiteindelijk toch op gewone machines te simuleren. Als het exponentieel groeide, bevestigde dit dat kwantumcomputers een duidelijk en superieur type machine zouden blijven. In een recente studie heeft Oliver Reardon-Smith van het Centrum voor Theoretische Natuurkunde van de Poolse Academie van Wetenschappen deze kloof eindelijk verkleind voor een specifieke, cruciale soort magische toestand. Door een nieuwe wiskundige methode te ontwikkelen, bewees de onderzoeker dat het aantal eenvoudige stukjes dat nodig is om deze complexe toestanden te bouwen niet alleen snel groeit; het explodeert exponentieel, met een ondergrens van ongeveer 1,4 tot de macht van het aantal kopieën. Hoewel het artikel opmerkt dat er een grote kloof blijft bestaan tussen deze nieuwe ondergrens en de bekende bovengrens van 2 tot de macht van het aantal kopieën, en dat de exacte waarde van de rang binnen dit gebied volledig onbekend is voor meer dan twee kopieën, versterkt dit resultaat het bewijs voor exponentiële complexiteit aanzienlijk.

De studie richt zich op een specifieke vier-deeltjesconfiguratie, een toestand die fungeert als een fundamentele bouwsteen voor kwantumlogica, in staat om de posities van deeltjes te verwisselen. De onderzoeker stelde een eenvoudige vraag: als je twee van deze toestanden neemt en ze combineert, hoeveel eenvoudige, ordelijke toestanden moet je dan toevoegen om het resultaat te recreëren? Eerdere methoden konden niet uitsluiten dat een klein aantal eenvoudige toestanden voldoende zou zijn. Het werk van Reardon-Smith laat zien dat dit onmogelijk is. Voor slechts twee kopieën van de toestand toont het bewijs aan dat je minstens vier eenvoudige toestanden nodig hebt om het te reconstrueren. Wanneer men dit opschaalt naar veel kopieën, verdubbelt de vereiste niet simpelweg; het vermenigvuldigt met een factor van ongeveer 1,4 voor elke nieuwe kopie die wordt toegevoegd. Dit betekent dat naarmate je meer magische toestanden toevoegt, de computationele inspanning die nodig is om ze op een klassieke computer te simuleren, de hoogte in schiet, wat bevestigt dat deze systemen inderdaad onhandelbaar zijn voor klassieke machines, althans binnen de bewezen ondergrenzen.

Om tot deze conclusie te komen, maakte de onderzoeker gebruik van een techniek die werkt als een microscoop met hoge resolutie voor wiskundige structuren. In plaats van te proberen de complexe toestand vanaf nul op te bouwen, analyseert de methode de toestand door deze te projecteren in een andere wiskundige ruimte. Stel je voor dat je probeert de vorm van een complex 3D-object te begrijpen door naar de schaduw ervan te kijken; als de schaduw eenvoudig is, is het object misschien eenvoudig, maar als de schaduw ongelooflijk complex is, moet het object complex zijn. In dit geval construeerde de onderzoeker een specifieke matrix, een rooster van getallen die de toestand vertegenwoordigt, en bewees dat voor de magische toestanden dit rooster altijd vol zit met onafhankelijke informatie. In contrast hiermee is het rooster voor de eenvoudige, ordelijke toestanden altijd erg dun en repetitief. Door de "dikte" van deze rasters te vergelijken, toonde de onderzoeker aan dat hoe men de eenvoudige toestanden ook combineert, men nooit de dikte kan genereren die nodig is om de magische toestand te matchen, tenzij men een enorm aantal van hen gebruikt. Deze methode bood een onbreekbare ondergrens, waarmee werd bewezen dat de complexiteit inherent en onvermijdelijk is.

De bevindingen strekken zich uit voorbij de specifieke vier-deeltjes-toestand naar een bredere klasse van kwantumsystemen bestaande uit licht- en geluidsgolven, bekend als bosonen. In dit domein pakte de onderzoeker een langdurige gok aan over hoeveel eenvoudige golfpatronen nodig zijn om een specifieke, hoog geëxciteerde toestand van licht te creëren. De studie bevestigde dat het aantal benodigde patronen exact gelijk is aan het product van het aantal deeltjes in elke modus plus één. Dit resultaat beslecht een debat dat al lang in het veld hing, door aan te tonen dat de complexiteit van deze lichtgebaseerde toestanden wordt bepaald door de specifieke distributie van deeltjes over de modi. Verder keek de studie naar wat er gebeurt als de simulatie niet perfect is. In de echte wereld werken computers vaak met benaderingen, waarbij een kleine fout wordt geaccepteerd om tijd te besparen. De onderzoeker bewees dat zelfs als men een kleine foutmarge toestaat, het aantal eenvoudige toestanden dat nodig is, bijna net zo hoog blijft als het exacte aantal. De complexiteit verdwijnt niet alleen omdat men bereid is iets minder precies te zijn.

Dit werk is belangrijk omdat het een grote twijfel wegneemt over de kracht van kwantumcomputers. Voor een tijdje was er een hardnekkige hoop dat slimme wiskundige trucs het mogelijk zouden maken voor klassieke computers om deze magische toestanden efficiënt te simuleren, bijvoorbeeld door een manier te vinden om ze met minder stukjes te beschrijven dan verwacht. Deze studie sluit die deur voor de onderzochte specifieke toestanden, tenminste wat betreft de bewezen ondergrenzen. Het bevestigt dat de "magie" echt is en dat de computationele kosten voor het simuleren ervan ten minste exponentieel zijn, groeiend met een snelheid van ongeveer 1,4 per kopie. De resultaten suggereren dat naarmate kwantumcomputers opschalen, het toevoegen van meer van deze magische toestanden hen steeds moeilijker te imiteren zal maken voor klassieke machines, wat het voordeel van kwantumtechnologie veiligstelt. Hoewel het exacte aantal stukjes dat nodig is voor grotere systemen nog steeds een onderwerp is voor toekomstige verfijning, aangezien de kloof tussen de onder- en bovengrenzen nog steeds groot is, is de richting nu duidelijk: de complexiteit groeit met een snelheid die ervoor zorgt dat kwantumcomputers een uniek en krachtig instrument zullen blijven, ver buiten het bereik van klassieke simulatie.