Methods for Reducing Ancilla-Overhead in Block Encodings

Quantumcomputers beloven problemen op te lossen die klassieke machines millennia zouden kosten om te voltooien, maar ze zijn berucht fragiel. Om complexe berekeningen uit te voeren, vertrouwen deze machines op een techniek genaamd block encoding, waarmee ze wiskundige operaties kunnen representeren die niet perfect omkeerbaar zijn, een noodzaak voor realistische toepassingen zoals het simuleren van chemische reacties of het oplossen van differentiaalvergelijkingen. Denk bij een block encoding aan een manier om een complexe, niet-omkeerbare berekening te verbergen binnen een groter, omkeerbaar kwantumproces door gebruik te maken van extra hulpbits, bekend als ancillae. Deze hulpbits fungeren als een tijdelijke werkruimte, waardoor de quantumcomputer gegevens kan manipuleren zonder de fundamentele wetten van de kwantummechanica te schenden. Echter, naarmate algoritmen complexer worden, vereisen ze steeds meer van deze hulpbits. Omdat de huidige quantumhardware beperkt is in hoeveel qubits het kan bevatten, creëert deze vraag naar extra ruimte een ernstige flessenhals, die onderzoekers er vaak toe dwingt te kiezen tussen het uitvoeren van een berekening of het volledig uitgeput raken van het geheugen.

Een team onderzoekers van de University of California, Berkeley, en het Alfréd Rényi Instituut voor Wiskunde in Hongarije heeft twee nieuwe methoden ontwikkeld om het aantal benodigde hulpbits voor block encodings drastisch te verminderen. Hun werk benadert het probleem vanuit twee verschillende invalshoeken, waarbij een afweging wordt geboden tussen ruimte en tijd in het eerste geval, en tussen ruimte en nauwkeurigheid in het tweede geval. De eerste methode introduceert een manier om de werkruimte op te schonen nadat een berekening is voltooid. In veel quantumalgoritmen blijven de hulpbits, zodra een block encoding is gebruikt, in een rommelige, verstrengelde staat achter die niet hergebruikt kan worden. De onderzoekers bedachten een protocol dat bijna al deze hulpbits coherent terugzet naar een schone nultoestand, waardoor ze vrijkomen voor gebruik in latere delen van het algoritme. Dit proces is niet onmiddellijk; het vereist extra computationele stappen, wat effectief extra tijd ruilt voor de waardevolle hulpbron van extra ruimte. Het resultaat is een systeem dat dezelfde complexe operaties kan uitvoeren met slechts één hulpbit, ongeacht hoeveel er oorspronkelijk nodig waren, mits de berekening niet perfect precies is maar wel dicht genoeg bij de werkelijkheid voor praktisch gebruik.

Het tweede deel van hun werk pakt de specifieke uitdaging aan van het met elkaar vermenigvuldigen van vele block encodings, een veelvoorkomende vereiste bij het simuleren van hoe fysieke systemen zich in de loop van de tijd ontwikkelen. Traditioneel vereiste het vermenigvuldigen van een groot aantal van deze encodings een aantal hulpbits dat logaritmisch groeide met het aantal operaties, een vraag die snel de beschikbare hardware overstijgt. De onderzoekers bewezen dat voor exacte, perfecte vermenigvuldiging, deze logaritmische vereiste een harde limiet is die niet omzeild kan worden. Ze toonden echter aan dat als men bereid is een kleine, gecontroleerde fout te accepteren, deze limiet doorbroken kan worden. Ze introduceerden een nieuwe gadget die deze vermenigvuldigingen uitvoert met een constante, kleine hoeveelheid hulpbits, ongeacht hoeveel operaties er achter elkaar worden geschakeld. De fout die door deze compressie wordt geïntroduceerd is extreem klein en neemt snel af naarmate het aantal hulpbits iets wordt verhoogd. Deze aanpak is bijzonder effectief voor simulaties waarbij de individuele stappen al zeer dicht bij het doen van niets zijn, een veelvoorkomend scenario in natuurkundige simulaties waarbij kleine tijdstappen worden gebruikt om geleidelijke veranderingen te volgen.

Om ervoor te zorgen dat deze gecomprimeerde berekeningen nog steeds bruikbaar zijn, hebben de onderzoekers ook gedemonstreerd hoe ze een techniek genaamd oblivious amplitude amplification kunnen gebruiken. Deze methode werkt als een filter die de waarschijnlijkheid van het slagen van de berekening versterkt, waardoor een proces dat vaak zou kunnen falen effectief wordt omgezet in een proces dat bijna altijd slaagt, zelfs wanneer de gecomprimeerde, benaderde methode wordt gebruikt. De bevindingen suggereren dat door zorgvuldig de afweging tussen precisie en hulpbrongebruik te beheren, quantumalgoritmen veel efficiënter kunnen worden gemaakt. Dit is niet slechts een theoretische oefening; de methoden zijn direct toepasbaar op het simuleren van Hamiltonian dynamics, wat beschrijft hoe energie door een systeem beweegt, en het oplossen van quantumdifferentiaalvergelijkingen, die essentieel zijn voor het modelleren van alles van vloeistofdynamica tot chemische reacties. Door de ancilla-overhead te verminderen, zouden deze technieken huidige en nabije quantumcomputers in staat kunnen stellen om problemen aan te pakken die voorheen onbereikbaar waren vanwege een gebrek aan beschikbaar geheugen.