⚛️ quantum physics

High performance Boson Sampling simulation via data-flow engines

In dit werk wordt een op FPGA's gebaseerde Boson Sampling-simulatie gepresenteerd die door generalisatie van de BB/FG-permanenteformule en gebruikmaking van n-ary Gray code-ordening tot 40 fotonen in een 60-modus interferometer kan simuleren met een snelheid van ongeveer 80 seconden per sample.

Oorspronkelijke auteurs: Gregory Morse, Tomasz Rybotycki, Ágoston Kaposi, Zoltán Kolarovszki, Uroš Stojčić, Tamás Kozsik, Oskar Mencer, Michał Oszmaniec, Zoltán Zimborás, Péter Rakyta

Gepubliceerd 2026-04-13

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Gregory Morse, Tomasz Rybotycki, Ágoston Kaposi, Zoltán Kolarovszki, Uroš Stojčić, Tamás Kozsik, Oskar Mencer, Michał Oszmaniec, Zoltán Zimborás, Péter Rakyta

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

De Grote Uitdaging: Het "Quantum Raadsel"

Stel je voor dat je een enorm ingewikkeld legpuzzel hebt. In de wereld van de kwantumcomputers proberen wetenschappers een specifieke puzzel op te lossen die ze Boson Sampling noemen. Dit is een taak waarbij deeltjes (fotonen, oftewel lichtdeeltjes) door een complex netwerk van spiegels en straalverdelers worden gestuurd. Het doel is om te voorspellen waar deze deeltjes uiteindelijk uitkomen.

Het probleem? Voor een gewone computer (zoals je laptop of de krachtigste supercomputer ter wereld) is dit raadsel bijna onoplosbaar. De tijd die nodig is om de uitkomst te berekenen, groeit exponentieel naarmate je meer deeltjes toevoegt. Het is alsof je elke keer dat je één stukje aan je legpuzzel toevoegt, het aantal mogelijke oplossingen verdubbelt, en dan nog eens verdubbelt. Bij 40 deeltjes is het aantal mogelijke routes zo groot dat het de leeftijd van het heelal zou overschrijden om ze allemaal één voor één uit te rekenen.

Om te bewijzen dat een kwantumcomputer echt "superieur" is, moeten we dit raadsel eerst oplossen met een gewone computer om te zien of het experiment klopt. Maar hoe doe je dat als het te moeilijk is?

De Oplossing: Een Nieuwe Wiskundige Truc

De auteurs van dit paper hebben een slimme nieuwe manier bedacht om dit raadsel sneller op te lossen. Ze gebruiken een wiskundige formule (de BB/FG-formule) die als een rekenmachine voor kansen werkt.

Stel je voor dat je een enorme lijst met opties hebt om te tellen. De oude manier was om elke optie één voor één af te vinken. De auteurs hebben echter ontdekt dat je slim kunt "haken" in de lijst. Ze gebruiken een techniek die Gray-code heet.

De Analogie: Stel je voor dat je een combinatieslot hebt. De oude manier was om elke cijfercombinatie van 0000 tot 9999 te proberen. De Gray-code methode is alsof je het slot zo draait dat je bij elke stap slechts één cijfer verandert. Hierdoor hoef je niet alles opnieuw te berekenen; je past alleen het kleine verschil toe. Dit bespaart enorm veel tijd.

Bovendien hebben ze ontdekt dat in dit experiment vaak meerdere deeltjes op dezelfde plek terechtkomen (een "botsing"). In de oude wiskunde telde je die dan apart. De auteurs hebben een meervoudige Gray-code (n-ary) bedacht die deze botsingen direct herkent en samenvoegt. Het is alsof je in plaats van 100 losse mensen te tellen, direct een groep van 10 mensen als één blok telt. Dit maakt de berekening veel sneller.

De Motor: De Data-Flow Engine (FPGA)

Nu hebben ze de slimme formule, maar ze hebben ook een motor nodig om die formule razendsnel af te draaien. Normale computers (CPU's) zijn als multitaskers: ze kunnen veel dingen doen, maar ze doen het één voor één, heel snel wisselend.

De auteurs hebben hun formule echter gebouwd op speciale chips genaamd FPGA's (Field Programmable Gate Arrays).

De Analogie: Stel je voor dat een CPU een chef is in een keuken die alle gerechten zelf moet bereiden, van het snijden van groenten tot het bakken. Hij is slim, maar hij kan maar één ding tegelijk doen.
Een FPGA is als een speciaal ontworpen productielijn in een fabriek. Zodra de machine is ingesteld (geprogrammeerd), stroomt het voedsel (de data) door een reeks stations. Terwijl station A het eerste stukje groente snijdt, snijdt station B het tweede stukje, en station C het derde. Alles gebeurt tegelijkertijd, in een continue stroom.

De auteurs hebben deze productielijn zo ontworpen dat hij speciaal is voor het tellen van deze kansen. Ze gebruiken geen ingewikkelde zwevende komma's (zoals bij gewone rekenmachines), maar werken met vaste getallen (fixed-point), wat voor deze chips veel sneller en efficiënter is.

De Resultaten: Een Wereldrecord

Wat hebben ze bereikt?

Snelheid: Met hun nieuwe methode en de speciale chips konden ze een simulatie uitvoeren met 40 fotonen in een systeem van 60 kanalen.
Tijd: Het duurde ongeveer 80 seconden om één enkel resultaat (één "sample") te genereren.
Vergelijking: Voorheen zou dit op een supercomputer dagen of weken hebben geduurd. Ze hebben bewezen dat hun systeem werkt en dat het de theoretische limieten van wat mogelijk is, haalt.

Ze hebben ook getest met "verlies" (waarbij sommige lichtdeeltjes onderweg verdwijnen, zoals in echte experimenten). Ook daar werkte hun systeem uitstekend, hoewel het dan iets langer duurde (ongeveer 360 seconden per sample).

Waarom is dit belangrijk?

Dit onderzoek is als het bouwen van een snellere en slimmere landkaart voor een gebied dat tot nu toe onbegaanbaar leek.

Het bewijst dat we kwantumexperimenten kunnen verifiëren met klassieke computers, zolang we maar slim genoeg zijn in onze wiskunde en hardware.
Het biedt een standaardmaatstaf (een soort "benchmark") om te zien hoe goed verschillende computersystemen zijn in het simuleren van kwantumgedrag.
Het laat zien dat speciale hardware (zoals FPGA's) een enorme kracht kan zijn in de strijd om te begrijpen hoe de kwantumwereld werkt.

Kortom: Ze hebben een ingewikkeld wiskundig raadsel opgelost door een slimme volgorde te vinden (Gray-code) en het te laten draaien op een machine die is ontworpen als een onophoudelijke stroom, in plaats van een trage, stap-voor-stap rekenmachine. Hierdoor kunnen we nu zien hoe kwantumcomputers werken, zelfs als we ze nog niet volledig hebben gebouwd.

Probleemstelling

Boson Sampling (BS) is een van de meest veelbelovende algoritmen om "quantum supremacy" (kwantumoverwicht) aan te tonen, waarbij ononderscheidbare fotonen door een lineair optisch interferometer worden gestuurd. Het simuleren van dit proces op klassieke hardware is extreem rekenintensief omdat de waarschijnlijkheid van een uitkomst evenredig is met het permanent van een complexe matrix. Het berekenen van een permanent is een #P-volledig probleem, wat betekent dat de rekentijd exponentieel groeit met het aantal fotonen ( $n$ ).

Bestaande klassieke methoden, zoals de Ryser-formule of de Balasubramanian-Bax-Franklin-Glynn (BB/FG) formule, hebben een complexiteit van $O(n \cdot 2^n)$ of $O(n^2 \cdot 2^n)$ . Voor grotere systemen (bijv. >20 fotonen) worden deze berekeningen onuitvoerbaar op conventionele CPU's, wat de validatie van echte kwantumexperimenten bemoeilijkt. Daarnaast introduceert het simuleren van verlies (photon loss) en meervoudige bezetting van modi (collisions) extra complexiteit en vereist het hoge numerieke nauwkeurigheid om fouten te minimaliseren.

Methodologie

De auteurs ontwikkelen een nieuwe, schaalbare aanpak die twee hoofdbanen combineert: een wiskundige optimalisatie van het permanent-berekeningsalgoritme en een hardware-implementatie op FPGA's (Field Programmable Gate Arrays) via Data-Flow Engines (DFE).

1. Wiskundige Optimalisatie (n-ary Gray Code):

Generalisatie van BB/FG: De auteurs generaliseren de BB/FG-formule om rekening te houden met rij-multipliciteiten in de invoermatrix. Dit komt overeen met situaties waar meerdere fotonen dezelfde uitgangsmodus bezetten (collisions).
n-ary Gray Code: In plaats van de traditionele binaire Gray code, gebruiken ze een n-ary Gray code (ook wel Guan-code genoemd). Hierbij verandert in elke iteratie slechts één "cijfer" van de code, wat overeenkomt met het aantal fotonen in een specifieke modus.
Complexiteitsreductie: Door deze ordening kunnen tussentijdse sommen worden hergebruikt. De complexiteit wordt gereduceerd tot $O(n \cdot 2^{M^*})$ , waarbij $M^*$ afhangt van de multipliciteiten. Dit is een aanzienlijke versnelling ten opzichte van de standaard $O(n \cdot 2^n)$ wanneer er veel collisions zijn.

2. Hardware Implementatie (Data-Flow Engines):

FPGA Architectuur: Het algoritme is geïmplementeerd op Xilinx Alveo U250 FPGA-chips met behulp van het Maxeler Data-Flow-programmeermodel. In tegenstelling tot traditionele CPU/GPU-parallelle verwerking, stroomt data continu door hardware-kernen (kernels) die logische transformaties uitvoeren per klokcyclus.
Vaste punt rekenen (Fixed-Point): Om de beperkte middelen van FPGA's efficiënt te benutten en hoge snelheid te bereiken, gebruiken ze vaste punt-getallen (fixed-point) in plaats van zwevende komma (floating-point). De bitbreedte wordt dynamisch opgevoerd van 64 bit (invoer) naar 128 bit of meer voor de eindresultaten om numerieke nauwkeurigheid te behouden.
Parallelle Verwerking: De invoermatrix wordt opgesplitst in blokken die parallel worden verwerkt door vier concurrente "kolom-som" kernels. De resultaten worden vervolgens via een boom-structuur (tree reduction) vermenigvuldigd en opgeteld.
Batch-verwerking: Om de overhead van het uploaden van data naar de FPGA (via PCIe) te minimaliseren, worden meerdere matrices in één enkele uitvoering verwerkt.

Belangrijkste Bijdragen

Nieuw Algoritme: De eerste implementatie van een BB/FG-formule die gebruikmaakt van n-ary Gray code om rij-multipliciteiten (fotonen-collisions) direct in de complexiteit te verwerken.
FPGA-Data-Flow Engine: Een hoogpresterende, FPGA-gebaseerde engine voor het exact berekenen van permanenten, die schaalbaar is tot 40 fotonen zonder herconfiguratie van de FPGA.
Numerieke Nauwkeurigheid: Het aantonen dat de vaste punt-implementatie op FPGA's vergelijkbare nauwkeurigheid biedt als uitgebreide precisie (extended precision) zwevende komma-berekeningen op CPU's, zelfs voor matrices tot $40 \times 40$ .
Validatie van Kwantumexperimenten: Het leveren van een tool om Boson Sampling-experimenten te valideren door samples te trekken uit een 60-moden interferometer, wat essentieel is om te bewijzen dat een kwantumcomputer echt "kwantumgedrag" vertoont en niet door klassieke heuristieken kan worden nagebootst.

Resultaten

Snelheid: Met 4 FPGA-chips kon het systeem samples trekken uit een 60-moden interferometer met 40 input-fotonen met een gemiddelde snelheid van ongeveer 80 seconden per sample (zonder verlies).
Vergelijking met CPU: De DFE-implementatie is aanzienlijk sneller dan de beste CPU-implementaties (zoals de BB/FG in de Piquasso Boost bibliotheek en TheWalrus). Voor 40 fotonen is de DFE ongeveer 27,9 tot 35,4 keer sneller dan de langzame "long double" CPU-implementaties, en behoudt tegelijkertijd een hogere nauwkeurigheid dan de snellere "double precision" CPU-versies.
Verlies-simulatie: Bij het simuleren van verlies (bijv. 30% of 50%), waarbij het aantal modi verdubbelt, neemt de tijd toe tot ongeveer 360 seconden per sample, wat nog steeds haalbaar is voor validatiedoeleinden.
Theoretische Overeenstemming: De prestaties volgen nauwkeurig de theoretische voorspelling van Clifford & Clifford, waarbij een enkele parameter ( $T_0$ ) de prestaties van de simulator karakteriseert.
Vergelijking met Experiment: De simulator kon een experimentele setup (60 modi, 20 fotonen, 14 gedetecteerd) simuleren in ~0,8 ms per sample, terwijl het fysieke experiment (Wang et al.) 26 uur nodig had voor 150 geldige samples.

Betekenis

Deze studie is van groot belang voor het veld van de kwantuminformatie:

Validatie: Het biedt een krachtige methode om de resultaten van echte "quantum supremacy"-experimenten te verifiëren. Zonder snelle klassieke simulaties is het moeilijk om te bewijzen dat een kwantumdevice een probleem oplost dat klassiek onoplosbaar is.
Schaalbaarheid: Het toont aan dat FPGA's, door middel van data-flow architectuur, een zeer efficiënt alternatief zijn voor supercomputers bij specifieke kwantumsimulaties, vooral bij het hanteren van complexe wiskundige structuren zoals permanenten.
Toekomstige Ontwikkeling: De techniek kan worden toegepast op zowel ideale als verlies-gevoelige Boson Sampling experimenten en vormt een basis voor verdere optimalisaties, zoals het gebruik van benaderingsmethoden (MF-approximatie) voor nog grotere systemen.

Kortom, de auteurs hebben een brug geslagen tussen geavanceerde wiskundige optimalisatie en gespecialiseerde hardware, waardoor klassieke simulatie van complexe kwantumsystemen aanzienlijk sneller en nauwkeuriger wordt.