Technische Samenvatting: Over de Hardheid van Benaderende Kwantumcircuit-lidmaatschap en Optimalisatie

1. Probleemdefinitie

Het artikel onderzoekt de computationele complexiteit van twee fundamentele problemen in de kwantumcircuittheorie: Benaderend Lidmaatschap (Approximate Membership) en Benaderende Optimalisatie (Approximate Optimization).

• Benaderend Lidmaatschap ($\text{ApproxMember}$): Gegeven een kwantumcircuit $C$ over een poortenset $G$, een verzameling unitairheden $S$, een afstandmetriek $m$, en een tolerantie $\epsilon$, bepaal of er een unitariteit $U \in S$ bestaat zodanig dat de afstand $d_m(C, U) \le \epsilon$.
  • Een speciaal geval is Benaderende Identiteit ($\text{ApproxId}$), waarbij $S = \{I\}$.
  • Het artikel beschouwt drie specifieke verzamelingen voor $S$:
    1. $S = \{I\}$ (Identiteit).
    2. $S \subseteq S_{\text{Cliff}}$ (Unitairheden implementeerbaar door Clifford-circuits).
    3. $S \subseteq S_{\text{GP}}$ (Generalized Permutation matrices, d.w.z. unitairheden die geen superpositie creëren).
• Benaderende Optimalisatie ($\text{ApproxOpt}$): Gegeven een circuit $C$, een kostenfunctie $f$, en een budget $k$, bepaal of er een equivalent circuit $C'$ bestaat zodanig dat $d_m(C, C') \le \epsilon$ en $f(C') \le k$. De kostenfunctie $f$ wordt gekenmerkt door haar "vrije verzameling" $S_f = \{U_{C'} \mid f(C') = 0\}$.

De studie richt zich op promise-vrije inputs, in tegenstelling tot eerder werk van Janzing, Wocjan en Beth (2005), dat QMA-volledigheid vaststelde voor het "niet-identiteit check"-probleem onder een belofte (promise) dat het circuit ofwel dicht bij of ver van de identiteit is. Dit werk verwijdert die belofte en vraagt of het probleem hard blijft wanneer de afstand van het invoercircuit tot de doelverzameling onbekend is.

De auteurs analyseren drie standaardmetrieken voor het meten van de afstand tussen unitarheden:

1. Sine-metriek: Gebaseerd op de trace, vangt gemiddelde verschillen op ($d_{\text{Sine}}$).
2. Spectrale metriek: Gebaseerd op de operatornorm, vangt worst-case verschillen op ($d_{\text{sp}}$).
3. Operator-metriek: De global-phase-invariante versie van de spectrale metriek ($d_{\text{op}}$).

2. Methodologie

De auteurs vestigen de hardheid door de complexiteitsklasse PP (Probabilistic Polynomial time) te reduceren naar het benaderende lidmaatschapsprobleem. De kern van hun methodologie omvat de volgende stappen:

1. Bronprobleem: Zij maken gebruik van AtMostSat, een PP-hard probleem dat vraagt of een propositionele formule $\phi$ door ten hoogste een fractie $\beta$ van zijn toewijzingen wordt voldaan. Zij introduceren een promise-versie, PromiseAtMostSat, waarbij de fractie voldaan toewijzingen beloofd wordt maximaal $\kappa$ te zijn.
2. Promise-naar-Benadering Reductie: Zij bewijzen dat PromiseApproxId (het controleren of een circuit $\epsilon$-dicht bij de identiteit is onder de belofte dat het $\tau$-dicht bij de identiteit is) PP-hard is. Dit wordt bereikt door Clifford+T-circuits $C$ te construeren uit formules $\phi$ zodanig dat de afstand $d_m(I, C)$ een strikt toenemende functie $g(\gamma(\phi))$ is van de voldane fractie $\gamma(\phi)$.
   • Voor de Sine-metriek construeren zij een circuit dat een gecontroleerde-XOR operatie implementeert ($|x\rangle|b\rangle \mapsto |x\rangle|b \oplus \phi(x)\rangle$).
   • Voor de Spectrale en Operator-metrieken maken zij gebruik van de Grover-iteratie om circuits te construeren met eigenhoeken afhankelijk van $\gamma(\phi)$. Voor de operator-metriek gebruiken zij tensorproducten van deze circuits om de booglengte van eigenhoeken op de eenheidscirkel te controleren.
3. Het Verwijderen van de Belofte (Promise):
   • Geval $S = \{I\}$: De hardheid van de promise-versie impliceert direct de hardheid van de promise-vrije versie voor de specifieke bereiken van $\epsilon$.
   • Geval $S \subseteq S_{\text{Cliff}}$: Zij maken gebruik van een driehoeksongelijkheid-argument (Lemma 6). Zij tonen aan dat voor een voldoende kleine $\epsilon$ (specifiek $\epsilon < \sqrt{2}/4$), als een circuit $C$ beloofd dicht bij $I$ te zijn, de enige elementen in $S_{\text{Cliff}}$ die $\epsilon$-dicht bij $C$ kunnen zijn, de elementen zijn die een afstand 0 van $I$ hebben (d.w.z. $I$ zelf). Dit berust op het ondergrenzen van de minimale niet-nul afstand tussen $I$ en elke andere Clifford-unitariteit.
   • Geval $S \subseteq S_{\text{GP}}$: Zij construeren specifieke circuits waarbij de afstand tot de verzameling van generalized permutation matrices exact gelijk is aan de afstand tot de identiteit voor een kleine $\gamma(\phi)$, wat een directe reductie van het promise-probleem mogelijk maakt. Deze reductie is specifiek van toepassing wanneer de identiteit $I$ in de verzameling $S$ is opgenomen (d.w.z. $I \in S \subseteq S_{\text{GP}}$).

3. Belangrijkste Bijdragen en Resultaten

Hoofdstelling (Theorem 1)

Het artikel bewijst dat ApproxMember PP-hard is voor een breed scala aan parameters, mits de poortenset $G$ Clifford+T exact kan implementeren. De hardheid geldt voor:

• Verzamelingen $S$: $S=\{I\}$, $I \in S \subseteq S_{\text{Cliff}}$, en $I \in S \subseteq S_{\text{GP}}$.
• Metrieken: Sine, Spectrale en Operator-metrieken.
• Tolerantie $\epsilon$:
  • Voor $S=\{I\}$ en trace-gebaseerde (Sine) metrieken: PP-hard voor alle $0 < \epsilon < 1$ (de volledige diameter).
  • Voor $S=\{I\}$ en Spectrale/Operator-metrieken: PP-hard voor alle $0 < \epsilon < 2$.
  • Voor $I \in S \subseteq S_{\text{Cliff}}$: PP-hard voor $0 < \epsilon < \sqrt{2}/4 \approx 0.3536$.
  • Voor $I \in S \subseteq S_{\text{GP}}$: PP-hard voor $0 < \epsilon < 1$ (Sine) en $0 < \epsilon < \sqrt{2}$ (Spectraal/Operator).

Corolarium 1 (Optimalisatie Hardheid)

De resultaten impliceren direct dat ApproxOpt PP-hard is voor het minimaliseren van de totale gate-diepte/aantal, de niet-Clifford gate-diepte/aantal, en de superpositie gate-diepte/aantal, binnen de overeenkomstige $\epsilon$-bereiken.

Specifieke Technische Bevindingen

1. Hardheid voor Klassiek-Reversibele Poorten: Zelfs wanneer de poortenset $G$ enkel uit klassiek-reversibele poorten bestaat (bijv. X, CNOT, Toffoli) die geen superpositie kunnen creëren, blijft het ApproxId probleem onder de Sine-metriek PP-hard voor alle $0 < \epsilon < 1$.
2. Robuustheid: De hardheidsresultaten generaliseren naar elke afstandmetriek afgeleid van de Sine, Spectrale of Operator-metrieken via een strikt toenemende functie. Bovendien blijven de problemen PP-hard zelfs als het doel is om de minimale kosten binnen een bepaalde factor te benaderen (constant of niet), aangezien de hardheid standhoudt wanneer de optimale kosten 0 zijn.
3. Vergelijking met Voorgaand Werk: Dit artikel versterkt het resultaat van Janzing, Wocjan en Beth (2005). Waar hun resultaat QMA-volledigheid toonde voor het promise-probleem van de niet-identiteit check, toont dit werk aan dat het promise-vrije probleem PP-hard is (een klasse die als strikt moeilijker dan QMA wordt beschouwd) voor een breder scala aan metrieken en verzamelingen $S$.

4. Betekenis en Claims

De auteurs claimen dat hun resultaten aantonen dat benaderende kwantumcircuit-optimalisatie fundamenteel moeilijker is over promise-vrije inputs vergeleken met de QMA-volledigheid van de promise-gebaseerde niet-identiteit check.

• Resource Onafhankelijkheid: De hardheid blijft bestaan ongeacht de beschikbare kwantum-resources (elke poort, niet-Clifford poorten, of superpositie).
• Metriek Onafhankelijkheid: De hardheid houdt stand voor diverse afstandmetrieken (trace-gebaseerd, spectraal en operator).
• Praktische Implicaties: Aangezien standaard hardware-poortensets (zoals Clifford+T) aan de voorwaarden voldoen, zijn deze hardheidsresultaten direct van toepassing op real-world kwantumcompilatie en optimalisatietaken. De resultaten geven aan dat het vinden van een ongeveer equivalent circuit met minimale kosten (bijv. minimale T-count of diepte) computationeel onuitvoerbaar is voor klassieke computers, zelfs als men benaderingsfouten toestaat, tenzij de fouttolerantie triviaal groot is (groter dan de diameter van de metriekruimte).

Het artikel concludeert door te wijzen op openstaande problemen met betrekking tot de complexiteit voor grotere waarden van $\epsilon$ (specifiek $\epsilon \ge \sqrt{2}/4$ voor Clifford-verzamelingen en $\epsilon \ge \sqrt{2}$ voor permutatie-verzamelingen) en het vinden van bijbehorende bovengrenzen, hoewel het vermeldt dat voor algebraïsche poortensets en de Sine-metriek bij $\epsilon = \sqrt{2}/2$, het probleem PP-compleet is.