Quantum Eigenvalue Transformations for Arbitrary Matrices

Titel: Quantum Eigenvalue Transformations for Arbitrary Matrices

Auteurs: Xabier Gutiérrez, Lorenzo Laneve en Mikel Sanz.

---

1. Het Probleem

Bestaande methoden voor quantum algoritme-ontwerp, zoals Quantum Signal Processing (QSP) en Quantum Singular Value Transformation (QSVT), bieden een krachtig raamwerk voor het implementeren van polynomen van matrices. Echter, deze technieken hebben fundamentele beperkingen:

• QSP kan alleen polynomen toepassen op de eigenwaarden van een unitaire matrix.
• QSVT kan alleen polynomen toepassen op de singuliere waarden van een blokk-gecodeerde matrix.
• Het gat: Voor een willekeurige, niet-Hermitische matrix (die niet noodzakelijk diagonaliseerbaar is), kunnen deze methoden niet direct worden gebruikt om een polynoomtransformatie op de eigenwaarden uit te voeren. In het bijzonder geldt dat een polynoom van een matrix $P(A)$ niet gelijk is aan de transformatie van de singuliere waarden van $A$, tenzij $A$ Hermitisch is.

Bestaande alternatieven, zoals de "Linear Combination of Unitaries" (LCU) methode, hebben nadelen zoals een hoge qubit-overhead, complex circuitontwerp en het probleem van "subnormalisatie" (waarbij de succeskans klein wordt).

2. Methodologie

De auteurs introduceren een nieuwe aanpak om QSP uit te breiden naar willekeurige vierkante matrices door een specifiek type blokk-encoding te creëren dat de eigenschappen van de matrixkrachten behoudt.

A. n-Reguliere Blokk-encoding

De kern van de methode is de definitie van een n-regular block encoding.

• Een unitaire operator $U$ is een $(a, \epsilon)$-blokk-encoding van een matrix $A$ als het linkerbovenblok van $U$ gelijk is aan $A$ (binnen een fout $\epsilon$).
• $U$ wordt n-regular genoemd als $U^k$ een blokk-encoding is van $A^k$ voor alle $0 \le k \le n$.
• Waarom is dit nodig? Normaal gesproken encodeert $U^k$ niet $A^k$ omdat "vuile" toestanden (garbage states) uit de blokk-encoding terugkeren naar de succesvolle subruimte bij herhaalde toepassing. Een n-regular encoding voorkomt dit.

B. Regularisatie door "Dumping Branches" (Takken afstoten)

De auteurs presenteren een constructie om elke blokk-encoding om te zetten in een n-regular versie:

• Ze voegen een extra register van $b = \lceil \log_2 n \rceil$ qubits toe.
• Ze gebruiken een quantum incrementer ($Q_n$) die dit register verhoogt met 1, maar alleen als de oorspronkelijke ancilla-qubits niet in de $|0\rangle$-toestand zijn.
• Principe: Als de blokk-encoding faalt (d.w.z. de ancilla's gaan naar een niet-nul toestand), wordt het incrementer-register verhoogd. Hierdoor kunnen deze "gefaalde" takken niet terugkeren naar de $|0\rangle$-toestand van het incrementer-register, waardoor ze de hoofd-tak (waar $A$ correct wordt toegepast) niet vervuilen bij opeenvolgende machtswaarden.
• Dit vereist slechts $O(\log n)$ extra qubits en $O(\text{poly}(\log n))$ extra operaties.

C. Toepassing van GQSP

Zodra een n-regular blokk-encoding $U$ van $A$ is verkregen, kan standaard Generalized Quantum Signal Processing (GQSP) worden toegepast.

• Omdat $U^k$ correct $A^k$ encodeert, zal het toepassen van een polynoom $P(z)$ op de unitaire $U$ leiden tot een blokk-encoding van $P(A)$.
• Dit werkt zelfs voor niet-diagonaliseerbare matrices, waarbij de transformatie in feite op de Jordan-blokken van de matrix wordt toegepast.

3. Belangrijkste Bijdragen

1. Concept van n-regulariteit: De introductie van een nieuwe eigenschap voor blokk-encodings die het mogelijk maakt om QSP toe te passen op de eigenwaarden van willekeurige matrices.
2. Efficiënte Constructie: Een bewijs dat elke blokk-encoding kan worden omgezet in een n-regular encoding met slechts $O(\log n)$ extra qubits en operaties, wat een aanzienlijke verbetering is ten opzichte van LCU-methoden.
3. Algemene Eigenwaarde-transformatie: Een algoritme (Theorema 6) dat een blokk-encoding van $P(A)$ genereert voor een willekeurige $n \times n$ matrix $A$ en polynoom $P$, zonder dat $A$ diagonaliseerbaar hoeft te zijn.
4. Toepassingsvoorbeelden:
   • Verschoven Inverse: Benadering van $(cI - A)^{-1}$ via een Taylor-reeks, wat natuurlijker is dan contour-integratie methoden.
   • Matrix Exponentiële: Implementatie van $e^A$ met minder kopieën van $A$ dan bestaande methoden voor lineaire differentiaalvergelijkingen.

4. Resultaten en Complexiteit

• Qubit Overhead: $O(\log n)$ extra qubits.
• Circuit Diepte: $O(n \log n)$ elementaire operaties.
• Aanroepen: $n$ keer het gebruik van de oorspronkelijke blokk-encoding van $A$.
• Foutanalyse: De fout in de blokk-encoding van $P(A)$ wordt begrensd door $\sqrt{n^3/3}\epsilon$ (afhankelijk van de graad van het polynoom en de initiële fout $\epsilon$).
• Convergentie: Voor functies die analytisch zijn op een schijf met straal $R > 1$, is het aantal vereiste kopieën van $A$ $O(\log(1/\epsilon))$ om een precisie $\epsilon$ te bereiken.

5. Betekenis en Toekomstperspectief

Dit werk sluit een belangrijke kloof in het quantum algoritmisch ontwerp:

• Unificatie: Het breidt het QSP/QSVT-raamwerk uit van alleen unitaire of Hermitische matrices naar willekeurige niet-Hermitische matrices.
• Toepassingen: Het opent de deur voor efficiëntere simulaties van:
  • Algemene inhomogene differentiaalvergelijkingen.
  • Niet-unitaire dynamica (bijv. dissipatieve systemen, open quantum systemen).
  • Carleman-linearisatie voor niet-lineaire systemen.
• Efficiëntie: De methode vermijdt de hoge kosten van LCU-technieken en biedt een systematische, "black-box" manier om matrixfuncties toe te passen zonder de eigenstates expliciet te hoeven berekenen.

De auteurs merken op dat de huidige methode beperkt is tot functies die analytisch zijn op de eenheidsschijf, maar dat er potentie is voor verbeteringen in de implementatie van de incrementer (bijv. via Fibonacci-LSR) en voor het uitbreiden naar annulus-gebieden.