Modifications of Quantum Computation and Adaptive Queries to PP

Probleemstelling

Het onderzoek richt zich op de fundamentele vraag hoe de computationele kracht van kwantumcomputing (BQP) verandert wanneer we "metaphysische" of niet-standaard operaties toestaan die de wetten van de standaard kwantummechanica (zoals het niet-kollapsen van golffuncties of het kopiëren van toestanden) schenden. Specifiek willen de auteurs de ruimte tussen de complexiteitsklassen PP (Probabilistic Polynomial time met een kleine kans op fouten) en PSPACE beter begrijpen.

Eerdere werken hebben aangetoond dat PostBQP (BQP met postselectie) gelijk is aan PP. De auteurs onderzoeken of andere, gerelateerde modificaties van BQP leiden tot nieuwe klassen die strikt tussen PP en PSPACE liggen, of juist gelijk zijn aan bestaande klassen zoals BPPPP (BPP met toegang tot een PP-orakel) of PPP (PP met toegang tot een PP-orakel). Een tweede belangrijke vraag is hoe adaptiviteit (het aanpassen van de berekening op basis van tussentijdse metingen) de rekenkracht beïnvloedt en hoe deze modellen zich verhouden tot klassieke versus kwantumtoegang tot orakels.

Methodologie

De auteurs introduceren en analyseren twee nieuwe complexiteitsklassen en bestuderen hun eigenschappen via de volgende methoden:

1. Definitie van Nieuwe Modellen:

   • CorrBQP: Een modificatie van BQP die "gecorreleerde metingen" toestaat. Hierbij worden meerdere registers gemeten zodat ze dezelfde uitkomst hebben, waarbij de waarschijnlijkheidsverdeling wordt bepaald door een "leider-register". Dit is een niet-unitaire operatie die de golffunctie op een specifieke manier projecteert.
   • MajBQP: Een modificatie van BQP die een "kwantume meerderheidspoort" (quantum majority gate) toestaat. Deze poort collapseert een qubit naar $|0\rangle$ of $|1\rangle$ afhankelijk van welke uitkomst de hoogste waarschijnlijkheid heeft ($|\alpha|^2 \geq |\beta|^2$).
   • Adaptieve Varianten: De auteurs onderscheiden tussen modellen zonder tussentijdse metingen (MajBQP) en modellen die tussentijdse metingen toestaan (AdMajBQP).

2. Complexiteitsanalyse en Orakel-Relaties:

   • Ze bewijzen inbeddingen (inclusions) en gelijkheden tussen deze nieuwe klassen en klassieke/kwantum-orakelklassen (zoals PP, BPPPP, PPP).
   • Ze analyseren het concept van self-lowness: Is de klasse $C$ gelijk aan $C^C$ (d.w.z. kan een machine in klasse $C$ een orakel voor $C$ simuleren zonder extra kracht te winnen)? Ze onderzoeken dit voor zowel klassieke als kwantumtoegang tot het orakel.
   • Ze gebruiken query-complexiteit technieken, waaronder het uitbreiden van de adversary lower-bound methode (tegenstander-methode) naar adaptieve modellen.

3. Rationale Bomen (Rational Trees):

   • Ze definiëren een nieuwe maatstaf, de rationele boomgraad (rational tree degree, trdeg), om de query-complexiteit van adaptieve postselectie (AdPostBQP) te karakteriseren. Dit is een generalisatie van de bestaande "rationele graad" (rdeg) die gebruikt wordt voor PostBQP.

4. Adaptieve PDQP:

   • Ze definiëren AdPDQP, een adaptieve versie van PDQP (PostBQP met niet-kollapsende metingen), en passen de adversary-methode toe om ondergrenzen voor zoekproblemen en pariteit te bewijzen.

Belangrijkste Bijdragen en Resultaten

1. Karakterisering van Rekenkracht (Resultaat 1):
De auteurs tonen exact aan dat de nieuwe modellen gelijk zijn aan bestaande klassen met orakeltoegang:

• CorrBQP = AdMajBQP = BPPPP
  • Dit betekent dat het vermogen om gecorreleerde metingen uit te voeren of adaptieve meerderheidsmetingen te gebruiken, precies overeenkomt met de kracht van een BPP-machine met toegang tot een PP-orakel.
• MajBQP = PPP
  • Het vermogen om een register te collapse naar de meest waarschijnlijke uitkomst (zonder adaptiviteit) is gelijk aan PPP.
• Verwante Klassen: Ze tonen aan dat andere bekende "metaphysische" modellen, zoals CBQP (kopiëren van toestanden), RwBQP (rewindable computation) en AdPostBQP (adaptieve postselectie), allemaal gelijk zijn aan BPPPP.

2. Self-Lowness en de Counting Hierarchy (Resultaat 2):

• Klassieke toegang: CorrBQP en MajBQP zijn self-low met betrekking tot klassieke query's (d.w.z. $CorrBQP^{CorrBQP_{classical}} = CorrBQP$). Dit is een opmerkelijk verschil met PostBQP, waarvan bekend is dat dit niet self-low is.
• Kwantum toegang: Als CorrBQP self-low zou zijn onder kwantum query's (toegang tot het orakel in superpositie), dan zou de Counting Hierarchy (CH) ineenstorten tot BPPPP. Dit suggereert dat deze modellen een fundamenteel verschil maken tussen klassieke en kwantumtoegang tot orakels.

3. Query Complexiteit en Rationale Bomen (Resultaat 3):

• Ze introduceren trdeg (rational tree degree) als een ondergrens voor de query-complexiteit van AdPostBQP.
• Ze tonen aan dat in het geval van nul fouten (zero-error), trdeg gelijk is aan rdeg, maar bij constante fouten ze gescheiden kunnen worden. Dit biedt een nieuw hulpmiddel om de scheiding tussen BPPPP en PSPACE te onderzoeken.

4. Orakel-Scheidingen (Resultaat 4):

• Ze bewijzen dat er een orakel $O$ bestaat waarvoor BQP$^O$ niet bevat is in PostBQP$^O_{classical}$ (PostBQP beperkt tot klassieke query's).
• Dit weerlegt de hypothese dat PostBQP altijd gelijk is aan PP, zelfs als we de toegang tot het orakel beperken tot klassieke queries. Het benadrukt dat volledige kwantumtoegang tot een orakel essentieel is voor de gelijkheid PP = PostBQP.

5. Adaptiviteit in PDQP (Resultaat 5):

• Ze passen de adversary-methode toe op AdPDQP.
• Verrassend resultaat: In tegenstelling tot adaptieve postselectie (AdPostBQP), die pariteit efficiënt kan oplossen, biedt adaptiviteit in PDQP geen significant voordeel voor zoekproblemen of pariteit.
• De ondergrenzen blijven: $\Omega(n^{1/4})$ voor ongestructureerde zoekopdracht en $\Omega(n^{1/2})$ voor pariteit. Dit betekent dat AdPDQP niet sterker is dan PDQP voor deze problemen, ondanks de mogelijkheid om de berekening aan te passen aan niet-kollapsende metingen.

Betekenis en Impact

1. Verduidelijking van de Complexiteitslandschap: Het werk plaatst diverse "metaphysische" kwantummodellen exact in het complexiteitslandschap. Het toont aan dat veel van deze krachtige modificaties (kopiëren, rewinden, gecorreleerde metingen) niet leiden tot PSPACE, maar juist in de buurt van BPPPP en PPP blijven.
2. Klassiek vs. Kwantum Orakeltoegang: De resultaten benadrukken een fundamenteel onderscheid in de complexiteitstheorie: modellen die self-low zijn voor klassieke query's, hoeven dat niet te zijn voor kwantum query's. Dit heeft implicaties voor het begrijpen van de Counting Hierarchy en de mogelijke ineenstorting daarvan.
3. Nieuwe Technieken: De introductie van "rationele bomen" en de uitbreiding van de adversary-methode naar adaptieve niet-kollapsende metingen biedt nieuwe wiskundige hulpmiddelen voor het bewijzen van ondergrenzen in kwantumquery-complexiteit.
4. Adaptiviteit is niet altijd krachtig: Het resultaat dat adaptiviteit in PDQP geen extra kracht biedt voor zoek- en pariteitsproblemen, contrasteert sterk met de situatie bij postselectie. Dit suggereert dat de aard van de "metaphysische" operatie cruciaal is voor het effect van adaptiviteit.

Kortom, dit artikel biedt een rigoureuze analyse van hoe afwijkingen van de standaard kwantummechanica de rekenkracht beïnvloeden, en levert sterke bewijzen dat de meeste van deze afwijkingen de klassen binnen een specifiek bereik (tussen PP en PSPACE) houden, met subtiele maar belangrijke verschillen afhankelijk van het type orakeltoegang en adaptiviteit.