AQ-Stacker: An Adaptive Quantum Matrix Multiplication Algorithm with Scaling via Parallel Hadamard Stacking

Titel: AQ-Stacker: Een Adaptief Quantum-Matrixvermenigvuldigingsalgoritme met Schaling via Parallelle Hadamard-Stacking

Auteur: Vladimir Silva (North Carolina State University)
Datum: 6 april 2026 (voorlopige preprint)

---

1. Het Probleem

Matrixvermenigvuldiging (MatMul) vormt de computationele ruggengraat van moderne machine learning, wetenschappelijke simulaties en data-analyse. Hoewel klassieke algoritmen zijn geëvolueerd van $O(N^3)$ naar $O(N^{2.37})$ (Coppersmith-Winograd), blijft de kwadratische vloer een bottleneck voor grote datasets.

Bestaande quantum-algoritmen voor lineaire algebra (zoals HHL) bieden theoretisch sub-kwadratische schaling, maar lijden vaak onder:

• Zeer diepe circuits die niet haalbaar zijn voor huidige hardware (NISQ-era).
• Rigidere hardware-eisen die ze "galactisch" maken (theoretisch correct, maar praktisch onbereikbaar).
• Gebrek aan flexibiliteit om zich aan te passen aan de beschikbare qubit-breedte van de processor.

Er is dus behoefte aan een hybride quantum-klassiek algoritme dat zowel numeriek stabiel is als schaalbaar op zowel huidige als toekomstige hardware.

---

2. Methodologie

AQ-Stacker is een hybride algoritme dat matrixvermenigvuldiging decomposeert in drie fasen, gebruikmakend van de Hadamard-test als fundamentele bouwsteen en Quantum Random Access Memory (QRAM) voor data-invoer.

A. Wiskundige Mapping

Klassieke vectoren $\vec{x}$ en $\vec{w}$ worden gemapt naar genormaliseerde quantum-toestanden $|\psi\rangle$ en $|\phi\rangle$. Het klassieke inproduct $\vec{x} \cdot \vec{w}$ wordt gerelateerd aan het quantum-inproduct $\langle\psi|\phi\rangle$ vermenigvuldigd met de product van hun Euclidische normen:
$$\vec{x} \cdot \vec{w} = \langle\psi|\phi\rangle \cdot \|\vec{x}\| \cdot \|\vec{w}\|$$
De normen worden klassiek berekend en opgeslagen als metadata, terwijl de quantum-circuits zich richten op het schatten van de overlap.

B. De Hadamard-test Primitief

De kern van de berekening is de Hadamard-test om het reële deel van de overlap $\langle\phi|\psi\rangle$ te schatten:

1. Een ancilla-qubit wordt in superpositie gebracht.
2. Een gecontroleerde unitaire operatie ($U^\dagger V$) wordt toegepast.
3. Na een tweede Hadamard-gate wordt de ancilla gemeten. De kans op $|0\rangle$ is gerelateerd aan het inproduct: $P(0) = \frac{1}{2}(1 + \text{Re}\langle\phi|\psi\rangle)$.

C. De "Adaptive Stacking" Framework

Het innovatieve aspect is de dynamische herschikking van de uitvoering op basis van beschikbare qubits:

• Fase 1 (Classical/QRAM): Voorbereiding van metadata (normen) en generatie van $N^2$ Hadamard-test-objecten. De klassieke overhead is $O(N^2)$.
• Fase 2 (Quantum Execution): De circuits worden uitgevoerd op een QPU. Het algoritme kan schakelen tussen:
  • Sequentiële Horizontale Stacking: Voor beperkte hardware (NISQ).
  • Massale Verticale Parallelisme: Waar $K$ tests parallel worden uitgevoerd.
  • Dit verlaagt de quantum-tijdcomplexiteit van $O(N^3)$ naar $O(N^2/K \cdot \log N)$, en theoretisch tot $O(\log N)$ bij volledige parallelisatie.
• Fase 3 (Reconstructie): De meetresultaten worden gecombineerd met de vooraf berekende normen om de matrixelementen $C_{ij}$ te reconstrueren.

---

3. Belangrijkste Bijdragen

1. Adaptieve Architectuur: In tegenstelling tot statische quantum-algoritmen, past AQ-Stacker zijn uitvoeringspatroon aan aan de qubit-breedte van de target processor. Dit maakt een naadloze overgang mogelijk van NISQ-apparaten naar fouttolerante systemen.
2. Tijdscomplexiteit Schaling:
   • Horizontaal (sequentieel): $O(N^3)$.
   • Verticaal (volledig parallel): Theoretisch $O(N^2)$ (beperkt door klassieke I/O) of $O(\log N)$ in pure quantum-diepte.
3. QRAM Input Model: Door QRAM aan te nemen voor $O(\log N)$ state preparation, wordt de data-ladingsoverhead ontkoppeld van de rekenlogica, wat essentieel is voor de theoretische prestaties.
4. Entropie Dividend: De auteurs ontdekten dat quantum-toestanden met hoge entropie (typisch voor neurale netwerken) een lagere variantie (shot noise) vertonen dan theoretisch verwacht. Dit betekent dat minder metingen nodig zijn voor hoge precisie in ML-taken.

---

4. Resultaten

De auteurs hebben het algoritme gevalideerd via simulaties op twee datasets: IRIS en MNIST.

• MNIST Prestaties:
  • AQ-Stacker bereikte 96,0% - 97,0% nauwkeurigheid op het MNIST-dataset (handgeschreven cijfers).
  • Dit is slechts een minimale achterstand ten opzichte van de klassieke baseline (97,4%) en een enorme verbetering ten opzichte van Variational Quantum Circuits (VQC), die slechts 6,0% haalde op dezelfde dataset (door dimensiereductie).
• Stabiliteit: Het algoritme behield numerieke stabiliteit ondanks de statistische ruis inherent aan de Hadamard-test (met $S=16384$ shots).
• Vergelijking: AQ-Stacker overtreft VQC-modellen aanzienlijk in schaalbaarheid en nauwkeurigheid voor hoog-dimensionale data.

---

5. Betekenis en Toekomstperspectief

AQ-Stacker biedt een haalbare weg naar super-klassieke efficiëntie in lineaire algebra voor machine learning.

• Praktische Toepasbaarheid: Het is niet alleen een theoretisch concept; het werkt met de beperkingen van huidige en nabije toekomstige hardware door adaptiviteit.
• Verschil met VQC: In plaats van het trainen van parametrische circuits (zoals bij VQC), versnelt AQ-Stacker de onderliggende lineaire algebra-primitieven. Dit blijkt effectiever voor hoog-dimensionale problemen.
• Toekomstige Richtingen:
  • Evaluatie op ruizige hardware (NISQ).
  • Schaling naar complexere datasets (CIFAR-10, ImageNet).
  • Integratie met Transformer-architecturen (LLMs), waarbij de $O(N^2)$ self-attention mechanismen kunnen worden versneld.
  • Ontwikkeling van hardware-specifieke compilers voor dynamische circuit-"herstacking".

Conclusie: AQ-Stacker bewijst dat quantum-versnelde matrixvermenigvuldiging een realistische kandidaat is voor de volgende generatie Quantum Machine Learning, mits de focus ligt op het versnellen van lineaire algebra-primitieven in plaats van puur variatieve benaderingen.