Bucket-brigade QRAM: hoe een kwantumcomputer straks efficiënt in het geheugen zoekt
Stel je een enorme bibliotheek voor met miljoenen boeken, en je wilt niet één boek opzoeken, maar tegelijkertijd een beetje van elk boek lezen — een soort mengsel van alle informatie tegelijk. Dat is ongeveer wat een kwantumcomputer nodig heeft wanneer hij klassieke data, zoals een database of een lijst met getallen, wil inladen in een "superpositie": een toestand waarin een kwantumbit (qubit) niet gewoon 0 of 1 is, maar een beetje van beide tegelijk. Bucket-brigade QRAM is een ontwerp voor het geheugen dat dat mogelijk moet maken, op een manier die minder gevoelig is voor storingen dan de voor de hand liggende aanpak.
De naam verwijst naar een ouderwetse "emmerbrigade": bij een brand gaven mensen vroeger emmers water door van hand tot hand, in een lange rij, in plaats van dat iedereen tegelijk naar de rivier rende. Bij bucket-brigade QRAM werkt het geheugen ook als een estafette: een adres wordt stap voor stap doorgegeven langs een pad van schakelaars, tot het bij precies de juiste geheugencel aankomt, terwijl de rest van het geheugen grotendeels met rust wordt gelaten. Dat blijkt cruciaal, omdat kwantumbits extreem gevoelig zijn voor verstoringen uit hun omgeving.
Wat is het precies?
Klassiek RAM-geheugen (Random Access Memory, het werkgeheugen van elke computer) werkt met een adresboom: op basis van een binair adres wordt via een reeks vertakkingen de weg gewezen naar één specifieke geheugencel. Een kwantumversie van RAM moet hetzelfde kunnen, maar dan met een adres dat in superpositie staat — dus met een adres dat tegelijk "naar cel 3" én "naar cel 7" én naar nog veel meer cellen "wijst". Het resultaat moet zijn dat de uitvoer een superpositie wordt van de inhoud van al die cellen, netjes gekoppeld aan het bijbehorende adres.
De simpelste manier om dit te bouwen, een zogeheten fanout-architectuur, activeert bij elke zoekopdracht in principe alle schakelaars in de hele boom tegelijk. Bij een geheugen met N cellen betekent dat dat er ordegrootte N onderdelen actief moeten zijn en foutloos moeten samenwerken. Omdat elke qubit een kleine kans heeft om door ruis te worden verstoord (decoherentie, het geleidelijk wegvallen van de kwantumeigenschappen door contact met de omgeving), stapelen die kleine foutkansen zich op. Bij grote geheugens wordt de kans op minstens één fout dan al snel bijna zeker.
Bucket-brigade QRAM lost dit anders op. Elke vertakking in de adresboom bevat een klein "routeer-qubit" dat drie toestanden kan aannemen: wacht, stuur-links of stuur-rechts. Aan het begin staan alle routeer-qubits in de wachtstand. Het adres wordt qubit voor qubit, laag voor laag, de boom in gestuurd. Bij elke laag wordt slechts het ene routeer-qubit dat al "wakker" is gemaakt, gebruikt om te bepalen of het volgende deel van het adres naar links of naar rechts gaat. Het gevolg is dat voor elke individuele zoekopdracht maar één pad door de boom daadwerkelijk actief is — van de wortel tot aan één geheugencel — terwijl alle andere vertakkingen in de wachtstand blijven staan en dus veel minder blootstaan aan ruis.
Omdat een boom met N geheugencellen een diepte heeft van ongeveer log₂(N) lagen (bij een miljoen cellen is dat ongeveer twintig lagen), hoeven er bij elke zoekopdracht maar zo'n log(N) onderdelen actief te zijn, in plaats van N onderdelen. Dat is voor grote geheugens een enorm verschil in hoeveel er tegelijk foutloos moet werken.
Wat wil men ermee bereiken?
Veel kwantumalgoritmes die op papier een enorme snelheidswinst beloven, gaan ervan uit dat er een efficiënte manier bestaat om klassieke gegevens in kwantumvorm te laden. Denk aan het zoeken in ongesorteerde databases (het beroemde Grover-algoritme), het oplossen van grote stelsels lineaire vergelijkingen (het HHL-algoritme, vernoemd naar Harrow, Hassidim en Lloyd) en verschillende vormen van kwantum-machinelearning, waarbij patronen in grote datasets worden gezocht. Al deze algoritmes hebben in de praktijk een QRAM-achtige component nodig om data in te laden zonder dat die inlaadstap zelf alle winst weer tenietdoet.
Het doel van bucket-brigade QRAM is dus niet zozeer een nieuwe rekenkracht op zich, maar het wegnemen van een bottleneck: een geheugentoegang die snel genoeg en betrouwbaar genoeg is om de beloofde versnellingen van andere algoritmes daadwerkelijk te kunnen benutten. Zonder een werkbare vorm van QRAM blijven veel van die algoritmes vooral theoretische exercities.
Voorbeelden uit de praktijk
Het concept werd in 2008 geïntroduceerd door de natuurkundigen Vittorio Giovannetti, Seth Lloyd en Lorenzo Maccone, in een paper getiteld "Architectures for a quantum random access memory", gepubliceerd in Physical Review A. Zij lieten wiskundig zien dat de bucket-brigade-aanpak in theorie veel minder gevoelig is voor bepaalde soorten fouten dan de fanout-aanpak.
Rond 2015 publiceerden onderzoekers verbonden aan het Institute for Quantum Computing in Waterloo (Canada), onder wie Srinivasan Arunachalam, Vlad Gheorghiu, Tomas Jochym-O'Connor en Michele Mosca, een kritische analyse getiteld "On the robustness of bucket brigade quantum RAM". Zij toonden aan dat de oorspronkelijke robuustheidsclaims genuanceerder liggen: bij bepaalde soorten ruis is bucket-brigade QRAM inderdaad veel beter bestand tegen fouten, maar niet tegen alle soorten fouten, en de precieze voordelen hangen sterk af van de aannames over het foutmodel.
Ook informaticus Scott Aaronson leverde rond diezelfde periode invloedrijke kritiek, onder meer in een veelgeciteerd essay waarin hij waarschuwde dat het "kleine lettertje" van QRAM-voorstellen vaak wordt overgeslagen: praktische kwantumfoutcorrectie kan de kosten van geheugentoegang alsnog flink opdrijven, ook bij bucket-brigade-ontwerpen.
Op de hardwarekant deed een onderzoeksgroep rond Steven Girvin en Liang Jiang aan Yale University rond 2019-2021 voorstellen en kleinschalige experimenten voor een "hardware-efficiënte" bucket-brigade QRAM, gebouwd met supergeleidende circuits gekoppeld aan microgolf- of akoestische resonatoren (bosonische kwantumgeheugens). Het idee daarbij was om routeer-qubits te vervangen door goedkopere, robuustere bouwstenen dan volwaardige logische qubits, om de weg naar een werkend, schaalbaar apparaat te verkorten.
Hoe ver is de techniek?
Bucket-brigade QRAM bevindt zich grotendeels nog in de theoretische en vroege experimentele fase. Er bestaan kleinschalige proof-of-concept-demonstraties met een handvol qubits en een paar lagen adresboom, maar een groot, foutbestendig geheugen met duizenden of miljoenen cellen is er nog niet, en de weg daarnaartoe is niet triviaal.
Een belangrijk obstakel is dat de "wachtstand" van routeer-qubits in de praktijk niet volledig foutvrij is: ook inactieve qubits ondervinden decoherentie over tijd, en hoe langer een berekening duurt, hoe meer dat een rol gaat spelen. Daarnaast blijft er discussie binnen de onderzoeksgemeenschap over hoeveel praktisch voordeel bucket-brigade QRAM oplevert zodra je rekening houdt met de overhead van kwantumfoutcorrectie, de techniek waarmee kwantumcomputers fouten in individuele qubits detecteren en herstellen door informatie over veel fysieke qubits te verspreiden. Sommige analyses suggereren dat dit voordeel bij realistische foutenpercentages kleiner uitvalt dan aanvankelijk gehoopt.
Kortom: het idee is theoretisch goed onderbouwd en experimenteel deels bevestigd op kleine schaal, maar niemand kan momenteel met zekerheid zeggen wanneer, of zelfs of, bucket-brigade QRAM op de schaal komt die nodig is voor de kwantumalgoritmes die er oorspronkelijk voor bedoeld waren. Dat maakt het een actief onderzoeksveld met veel open vragen, eerder dan een rijpe technologie.
Wie werken eraan?
Het onderzoek naar bucket-brigade QRAM is voornamelijk academisch van aard. Het Massachusetts Institute of Technology (MIT), waar Seth Lloyd als hoogleraar werkt, geldt als een van de bakermatten van het concept. Het Institute for Quantum Computing aan de University of Waterloo in Canada heeft met zijn analyses van foutgevoeligheid een belangrijke bijdrage geleverd aan het scherper krijgen van de beperkingen van het ontwerp.
Op het gebied van fysieke implementatie is de groep rond Liang Jiang en Steven Girvin aan Yale University een van de weinige teams die concrete hardwarevoorstellen hebben gedaan en getest, gebruikmakend van de supergeleidende-circuittechnologie waarin Yale al decennialang gespecialiseerd is. Grote commerciële kwantumcomputerbedrijven zoals IBM, Google en IonQ tonen interesse in QRAM-achtige concepten omdat ze relevant zijn voor toekomstige toepassingen in kwantum-machinelearning en optimalisatie, maar geen van hen heeft een bucket-brigade QRAM-chip als apart product of hoofdproject aangekondigd; het blijft vooral universitair, gefinancierd door onder meer Amerikaanse (NSF, DARPA), Canadese en Europese onderzoeksbeurzen.