Asymmetric Linear-Combination-of-Unitaries Realization of Quantum Convolution via Modular Adders

Probleemstelling

Het artikel adresseert de uitdaging om discrete circulaire convolutie (een fundamentele lineaire operator in signaalverwerking) efficiënt en fysisch realiseerbaar te implementeren op kwantumhardware.

• Beperkingen: Eerdere "no-go" argumenten (zoals die van Lomont) verbieden directe bilineaire vermenigvuldiging van amplitude's als fysieke kwantumoperatie.
• Huidige aanpak: Bestaande methoden, zoals die van Zhou en Wang (circulante matrices) en Castelazo et al. (groepconvolutie), benaderen het probleem vanuit verschillende hoeken (aritmatisch vs. representatietheoretisch), maar missen vaak een expliciete, circuit-niveau verbinding die de complexe coëfficiënten van de kernel behoudt zonder fase-informatie te verliezen.
• Specifiek probleem: Bij het gebruik van standaard symmetrische LCU (Linear Combination of Unitaries) benaderingen, waarbij dezelfde voorbereidingsunitary ($PREP_b$) aan beide kanten wordt gebruikt, worden de complexe coëfficiënten $b_i$ van de kernel vervangen door hun kwadraten $|b_i|^2$. Hierdoor gaan de cruciale fase-informatie en teken van de kernel verloren.

Methodologie

De auteurs stellen een nieuwe, asymmetrische LCU-benadering voor die modulariteit en bewaring van complexe amplitudes combineert.

1. Asymmetrische LCU Formulering:

   • In plaats van een symmetrische overlap te gebruiken, gebruiken de auteurs een asymmetrische post-selectie.
   • De kernel-toestand $|b\rangle$ wordt als input-ancilla ingevoerd (via $PREP_b$).
   • De post-selectie-toestand is een vaste, uniforme toestand $|u\rangle$ (via $PREP_u$).
   • De kernoperatie is een gecontroleerde shift die wordt geïmplementeerd als modulaire optelling ($ADD_N$) op de berekeningsbasis.
   • Resultaat: Deze asymmetrie zorgt ervoor dat de complexe coëfficiënten $b_i$ zelf behouden blijven in de gepost-selekteerde blokk, in plaats van alleen de gewichten $|b_i|^2$. Dit elimineert de noodzaak voor een kernel-afhankelijke inverse voorbereiding ($PREP_b^\dagger$) binnen de convolutiesubroutine, mits de kernel-toestand al beschikbaar is.

2. Symmetrisatie via Reflectie-matrix ($J_n$):

   • De auteurs introduceren een reversie-matrix $J_n = X^{\otimes n}$ (bitwise NOT).
   • Ze definiëren een gespiegelde shift-operator: $\tilde{L}_{i,n} = L_{i,n} J_n$.
   • Hierdoor wordt de convolutie-operator herschreven als $H_n(b) = \sum b_i \tilde{L}_{i,n}$.
   • Cruciaal voordeel: Voor reëelwaardige kernels is deze operator $H_n(b)$ Hermitisch. Dit maakt de operator direct compatibel met geavanceerde kwantumtechnieken zoals Quantum Singular Value Transformation (QSVT) en QSP, zonder de noodzaak voor een verdubbelde register (Hermitische dilatie) of het oplossen van normale vergelijkingen.

3. Circuit Constructie:

   • De auteurs presenteren een recursieve structuur voor de geselecteerde blokken ($SELECT_{\tilde{L}}$).
   • Ze tonen aan dat deze recursieve structuur exact equivalent is aan standaard ripple-carry adders en QFT-gebaseerde adders, maar biedt een transparanere operator-structuur.
   • Er wordt een geoptimaliseerde bitwise compilatie gepresenteerd die de gate-kosten aanzienlijk verlaagt ten opzichte van de directe recursieve implementatie.

Belangrijkste Bijdragen

1. Expliciete Asymmetrische LCU Formulering: Het artikel maakt de brug tussen modulaire optelling en circulaire convolutie expliciet. Het benadrukt dat het gebruik van een vaste post-selectie-toestand ($|u\rangle$) en een ingevoerde kernel-toestand ($|b\rangle$) essentieel is om de complexe fases van de kernel te behouden.
2. Hermitische Operator-pijplijn: Door de introductie van de reversie-matrix $J_n$, wordt een familie van convolutie-operatoren gedefinieerd die voor reële kernels Hermitisch zijn. Dit biedt een directe interface voor QSVT voor inverse problemen (zoals deconvolutie), waarbij de voorwaardegetal-kwadratering (die optreedt bij normale vergelijkingen) wordt vermeden.
3. Recursieve Structuur en Geoptimaliseerde Compilatie: De auteurs leveren een structureel inzicht in de operator-algebra van convolutie en koppelen dit aan een exact equivalente, geoptimaliseerde bitwise implementatie. Dit biedt een schaalbare route voor circuit-synthese.

Resultaten en Complexiteitsanalyse

• Complexiteit:
  • De directe recursieve constructie heeft een complexiteit van $O(n^3)$ in macro-blokken en $O(n^4)$ in primitieve CNOT-gates (waarbij $n = \log_2 N$).
  • De geoptimaliseerde bitwise compilatie (gebaseerd op carry-propagatie) verlaagt dit tot $O(n^2)$ in macro-blokken en $O(n^3)$ in CNOT-gates.
  • Dit is polylogaritmisch in de datagrootte $N$, wat vergelijkbaar is met de beste bestaande modulaire adders, maar met een scherpere operator-oriëntatie.
• Input Modellen:
  • In het coherente kwantum-toestandsmodel (waarbij data en kernel al als kwantumtoestanden beschikbaar zijn) is de convolutie-subroutine extreem efficiënt, omdat er geen extra kosten zijn voor het laden van de kernel ($PREP_b^\dagger$ is niet nodig).
  • In het klassieke vector-model domineert de kosten voor het laden van de data ($T_{load}$), maar de convolutie-blok zelf blijft polylogaritmisch.
• Foutkans: De succeskans van de post-selectie wordt bepaald door de norm van de convolutie-output, wat standaard is voor LCU-methoden, maar kan worden versterkt via amplitude-versterking.

Betekenis en Toepassing

Dit werk is significant omdat het:

1. Een unificerend kader biedt: Het verbindt circulaire matrix-implementaties en groep-convolutie-frameworks onder één circuit-niveau statement (modulaire optelling).
2. Hermitische Eigenschappen Benut: Het biedt een natuurlijke route voor het toepassen van QSVT op convolutie-operatoren, wat essentieel is voor deconvolutie en inverse filtering in kwantum signaalverwerking (bijv. kwantumsensoren of simulaties).
3. Efficiëntie in Coherente Pipelines: Het is bij uitstek geschikt voor scenario's waar convolutie een tussenstap is in een grotere kwantum-algoritme-pijplijn (bijv. kwantum-ML of kwantum-chemie), waar de kernel-toestand al coherent is gegenereerd. In deze setting vermijdt het de overhead van het herhaaldelijk voorbereiden en ongedaan maken van de kernel-toestand.

Kortom, het artikel levert een fundamentele verbetering in de theoretische formulering en praktische implementatie van kwantumconvolutie, met name door het benadrukken van asymmetrie voor fasebehoud en het creëren van een Hermitische structuur voor geavanceerde spectrale transformaties.