A Polylogarithmic-Depth Quantum Multiplier

Deze paper presenteert een kwantumalgoritme voor het vermenigvuldigen van twee $n$-bit gehele getallen met een circuitdiepte en $T$-diepte van $O(\log^2 n)$, wat de laagste $T$-diepte tot nu toe is voor dit probleem in het Clifford + $T$-model en zo de praktische haalbaarheid van grootschalige fouttolerante kwantumalgoritmen verbetert.

De kern

Stel je voor dat je een enorme bibliotheek hebt met twee specifieke boeken: Boek X en Boek Y. Je wilt weten hoeveel pagina's er samen in zitten als je ze op een heel specifieke manier combineert. In de wereld van computers heet dit "vermenigvuldigen".

Op een normale computer is dit een simpele rekensom. Maar op een kwantumcomputer (een computer die werkt met de vreemde regels van de deeltjeswereld) is dit een enorme uitdaging. Het is alsof je probeert twee boeken te vermenigvuldigen terwijl je in een kamer staat waar de muren continu bewegen en waar je maar heel weinig ruimte hebt om te werken.

Deze paper, geschreven door Fred Sun en Anton Borissov, introduceert een nieuwe manier om deze "kwantum-vermenigvuldiging" te doen. Ze noemen het een kwantum-vermenigvuldiger met een diepte van slechts een paar lagen.

Hier is de uitleg in simpele taal, met een paar creatieve vergelijkingen:

1. Het Probleem: De "Galactische" Rekenmachine

Vroeger waren de beste kwantum-vermenigvuldigers als een gigantische, trage fabriek.

• Ze hadden weliswaar weinig ruimte nodig (weinig "hulpqubits"), maar ze duurden eeuwen om klaar te zijn.
• Of ze waren als een snelle raceauto, maar dan eentje die zo veel brandstof (hulpqubits) verbruikt dat je er nooit genoeg van hebt.
• Een andere methode (de Schönhage-Strassen-algoritme) was als een raket die alleen werkt als je al een heel groot sterrenstelsel hebt (voor heel grote getallen). Voor normale maten was het te duur en te complex.

Het grote probleem in de kwantumwereld is de "T-depth". Denk hierbij aan de tijd die het kost om een specifieke, moeilijke stap te doen (een "T-gate"). Als deze stap te lang duurt, valt de hele kwantumcomputer uit elkaar door ruis. De auteurs zeggen: "We moeten die tijd drastisch verkorten, zelfs als we daarvoor meer ruimte (qubits) nodig hebben."

2. De Oplossing: De "Parallellisatie-Parade"

De auteurs hebben een nieuwe strategie bedacht die lijkt op het organiseren van een massale, perfect gecoördineerde parade.

In plaats van één persoon die stap voor stap alles doet (wat lang duurt), gebruiken ze een boomstructuur met duizenden mensen die tegelijkertijd werken.

Stap 1: De Klonen (Fast Copy)
Stel je voor dat je één origineel recept hebt (getal X) en één lijst met ingrediënten (getal Y).
In plaats van één keer te koken, maken ze n kopieën van het recept en de ingrediënten.

• Hoe doen ze dit zo snel? Ze gebruiken een "teleportatie-methode" (CNOT-gates) die in één keer alle kopieën maakt, net zoals een fotokopieermachine die in één seconde 100 pagina's kopieert in plaats van één voor één. Dit kost ze wel veel papier (hulpqubits), maar het gaat supersnel.

Stap 2: De Deeltjes (Partial Products)
Nu hebben ze duizenden kopieën. Ze laten elke kopie van het recept (Y) samenwerken met de bijbehorende kopie van de ingrediënten (X).

• Dit is als het laten maken van duizenden kleine broodjes tegelijk. Omdat ze allemaal apart werken, gebeurt dit in één oogopslag.
• Ze krijgen hierdoor duizenden "deeltjes" (partiele producten).

Stap 3: De Boom (Parallel Adder Tree)
Nu moeten ze al die duizenden broodjes optellen tot één groot feestmaal.

• Oude methoden deden dit rijtje voor rijtje (A + B, dan + C, dan + D...). Dat duurt lang.
• Deze nieuwe methode doet het als een piramide.
  • Ronde 1: 1000 mensen tellen 2 broodjes bij elkaar op.
  • Ronde 2: 500 mensen tellen de resultaten van ronde 1 bij elkaar op.
  • Ronde 3: 250 mensen...
• Omdat ze in een piramide werken, halveren ze het aantal stappen elke ronde. In plaats van 1000 stappen, doen ze het in ongeveer 10 stappen (logaritmisch).

3. Het Magische Trucje: De "Geestelijke Ruimte"

Het grootste probleem bij zo'n parade is: waar doe je al die mensen neer? Je hebt veel ruimte nodig.
De auteurs gebruiken een slimme truc: Hun "geestelijke ruimte" (hulpqubits) is tijdelijk.

1. Ze maken de kopieën (gebruiken ruimte).
2. Ze doen de berekening (gebruiken ruimte).
3. De truc: Zodra ze een stap klaar hebben, "wissen" ze de kopieën direct weer (uncompute).
   • Het is alsof je een kamer vol bouwwerken bouwt, de foto's maakt, en de gebouwen direct weer afbreekt om de ruimte vrij te maken voor de volgende ronde.
   • Hierdoor hoeven ze niet alle ruimte tegelijk te hebben, maar kunnen ze dezelfde ruimte hergebruiken.

4. Waarom is dit zo belangrijk?

In de wereld van fouttolerante kwantumcomputers (computers die niet snel fouten maken) is de tijd (diepte) belangrijker dan het aantal onderdelen.

• Vroeger: Een vermenigvuldiging duurde zo lang (O(n²)) dat de kwantumcomputer al "vergeten" was wat hij aan het doen was voordat hij klaar was.
• Nu: Met deze nieuwe methode duurt het maar een fractie van de tijd (O(log² n)). Het is alsof je van een wandeling naar de maan (en terug) gaat, naar een snelle treinreis.

Samenvatting in één zin

De auteurs hebben een manier bedacht om kwantumgetallen te vermenigvuldigen door duizenden kopieën tegelijk te maken en ze in een snelle piramide te laten optellen, waardoor de rekentijd drastisch omlaag gaat, zelfs als we daarvoor een tijdelijk grotere "werkruimte" nodig hebben.

Dit maakt het mogelijk om in de toekomst veel complexere dingen te doen met kwantumcomputers, zoals het kraken van codes (Shor's algoritme) of het simuleren van nieuwe medicijnen, omdat de basisrekenmachine nu eindelijk snel genoeg is.

Technische samenvatting

Titel: Een Polylogaritmische Diepte Quantum Multiplier

Auteurs: Fred Sun en Anton Borissov (softwareQ inc. en University of Waterloo)
Datum: 14 april 2026

---

1. Het Probleem

Quantum-rekenkunde is een fundamentele bouwsteen voor veel geavanceerde quantumalgoritmen, zoals Shor's factorisatiealgoritme (modulaire exponentiatie), Hamilton-simulaties en het HHL-algoritme voor lineaire systemen. Hoewel er reeds quantumcircuits zijn voor gehele getallenvermenigvuldiging, vormen deze vaak een knelpunt in termen van circuitdiepte en specifiek T-diepte (het aantal lagen van niet-Clifford T-gates).

In fouttolerante quantumcomputing is de T-diepte een kritieke maatstaf voor de uitvoeringstijd, omdat T-gates de grootste overhead veroorzaken. Bestaande methoden hebben vaak een kwadratische T-diepte ($O(n^2)$) of vereisen onpraktisch grote inputgroottes om asymptotisch betere methoden (zoals Sch¨onhage–Strassen) bruikbaar te maken. Er is behoefte aan een algoritme dat de diepte minimaliseert, zelfs ten koste van een groter aantal qubits, om de praktische haalbaarheid van grootschalige quantumcomputing te verbeteren.

2. Methodologie

De auteurs presenteren een modulair quantumalgoritme dat twee $n$-bit gehele getallen vermenigvuldigt met een totale circuitdiepte en T-diepte van $O(\log^2 n)$. Het algoritme maakt gebruik van het Clifford + T-model en wisselt een kwadratisch aantal hulpqubits (ancilla's) en T-gates in voor een drastische reductie in diepte.

De kern van de methode bestaat uit drie hoofdsubmodules:

A. Snelle Kopiëren (Fast Copying)

Om parallelisme te maximaliseren, worden $n$ kopieën gemaakt van de invoerregisters $|x\rangle$ en $|y\rangle$.

• Methode: Een boomstructuur van CNOT-gates wordt gebruikt om in $O(\log n)$ diepte $n$ kopieën te genereren.
• Kosten: Vereist $O(n^2)$ ancilla-qubits, maar de diepte is slechts logaritmisch.

B. Partiële Producten (Partial Products)

Het vermenigvuldigen van $x$ en $y$ wordt opgebroken in partiële producten $y_i \cdot x$.

• Methode: Met behulp van de gegenereerde kopieën worden $n$ partiële producten parallel berekend. Dit gebeurt via "conditionele kopie" (controlled copying) waarbij Toffoli-gates worden gebruikt.
• Parallelisme: Omdat alle Toffoli-gates op disjuncte qubitsets werken, heeft deze stap slechts een Toffoli-diepte van 1, ondanks het gebruik van $n$ Toffoli-gates.

C. Parallelle Optelling (Parallel Adder Tree)

De partiële producten moeten worden opgeteld, waarbij rekening wordt gehouden met de verschuivingen (factoren van $2^k$).

• Boomstructuur: De optelling wordt uitgevoerd in een binair boompatroon, waarbij paren van partiële sommen in elke laag worden opgeteld. Dit reduceert het aantal optelstappen van $O(n)$ naar $O(\log n)$.
• Gemodificeerde QCLA: De auteurs gebruiken een aangepaste versie van Draper's Quantum Carry Lookahead Adder (QCLA). In plaats van volledige optelling met nullen, worden drie fasen onderscheiden:
  1. Suffix kopiëren: De minst significante bits worden direct overgenomen.
  2. Overlappende som: De overige bits worden opgeteld met een QCLA.
  3. Carry-propagatie: De carry wordt verwerkt met de meest significante bits van het volgende getal.
• Uncomputation: Om de ancilla-qubits schoon te houden (nodig voor fouttolerantie), wordt het circuit na het berekenen van de eindresultaten "ongedaan gemaakt" (uncomputed). Dit gebeurt efficiënt door tegelijkertijd nieuwe lagen te berekenen en eerdere lagen ongedaan te maken, waardoor de diepte-toename minimaal blijft.

3. Belangrijkste Bijdragen

1. Record T-diepte: Het algoritme bereikt een T-diepte van $O(\log^2 n)$, wat de laagste bekende T-diepte is voor vermenigvuldiging in het Clifford+T-model.
2. Concrete Kostenanalyse: In tegenstelling tot veel theoretische werken die alleen asymptotische notaties gebruiken, bieden de auteurs een concrete, niet-asymptotische analyse met strakke bovengrenzen voor het aantal gates, Toffoli-gates, diepte en qubits.
3. Efficiënte Hulpqubit-beheer: Hoewel het algoritme $O(n^2)$ ancilla-qubits vereist, wordt er een slimme strategie ontwikkeld om deze qubits her te gebruiken tussen de verschillende lagen van de adder-boom, zodat het totale aantal benodigde qubits strikt onder de $2n^2$ blijft (plus de invoerregisters).
4. Praktische Toepasbaarheid: De auteurs tonen aan dat hun methode praktische constante factoren heeft, in tegenstelling tot andere snelle methoden (zoals Sch¨onhage–Strassen) die alleen voor extreem grote $n$ ($n \ge 2^{40}$) rendabel zijn.

4. Resultaten en Resource Costs

De paper presenteert een gedetailleerde vergelijking met bestaande methoden (Shift-and-Add, Karatsuba, Toom-Cook, Sch¨onhage–Strassen).

Samenvatting van de resources voor $n$-bit vermenigvuldiging:

Resource	Auteurs' Algoritme	Shift-and-Add (Schoolbook)	Sch¨onhage–Strassen
T-diepte	$O(\log^2 n)$	$O(n^2)$	$O(\log^2 n)$ (maar grote constante)
T-count	$O(n^2)$	$O(n^2)$	$O(n \log n \log \log n)$
Ancilla Qubits	$O(n^2)$	$O(n)$	$O(n \log n \log \log n)$
Totale Gate Count	$O(n^2)$	$O(n^2)$	$O(n \log n \log \log n)$

Concrete bovenlimieten (voor het totale algoritme):

• Diepte: $3 \log_2^2 n + 17 \log n + 20$
• Toffoli-diepte: $3 \log_2^2 n + 7 \log n + 14$
• Toffoli-aantal: $12n^2 - n \log n$
• Totaal aantal Gates: $26n^2 + 2n \log n$
• Ancilla Qubits: $3n^2$ (inclusief invoerregisters en tussenresultaten).

5. Significantie

Deze bijdrage is van groot belang voor de ontwikkeling van grootschalige, fouttolerante quantumcomputers.

• Versnelling van Algoritmen: Door de T-diepte van vermenigvuldiging (een kernonderdeel van Shor's algoritme) te reduceren tot polylogaritmisch, wordt de totale uitvoeringstijd van cryptografische en numerieke algoritmen aanzienlijk verkort.
• Trade-off Optimalisatie: Het werk toont aan dat het accepteren van een kwadratisch aantal qubits (wat binnen bereik ligt voor toekomstige grote quantumprocessors) een enorme winst oplevert in de uitvoeringstijd (diepte), wat de huidige beperkende factor is.
• Modulariteit: Het ontwerp is modulair en gebaseerd op standaard primitieven, wat het eenvoudig maakt om te integreren in grotere quantumsoftware-stacks en hardware-ontwerpen.

Kortom, Sun en Borissov bieden een praktische, hoog-efficiënte oplossing voor quantumvermenigvuldiging die de balans tussen qubit-omvang en uitvoeringstijd verschuift naar een meer haalbare richting voor toekomstige hardware.