Lower bounds on non-local computation from controllable correlation

Titel: Ondergrenzen voor niet-lokale berekening afgeleid van controleerbare correlatie

Auteurs: Richard Cleve (University of Waterloo) en Alex May (Perimeter Institute for Theoretical Physics)

1. Probleemstelling

Niet-lokale kwantumberekening (Non-Local Quantum Computation, NLQC) is een protocol waarbij twee partijen, Alice en Bob, een unitaire transformatie $U_{AB}$ op hun respectieve kwantumsystemen uitvoeren zonder deze systemen fysiek samen te brengen. In plaats daarvan delen ze verstrengeling (entanglement), voeren lokale operaties uit, wisselen één ronde van simultane communicatie uit, en voeren vervolgens weer lokale operaties uit.

De centrale vraag in dit domein is: wat is de minimale kost aan verstrengeling die nodig is om een specifieke unitaire transformatie $U_{AB}$ te implementeren via een NLQC-protocol?

• Huidige staat van de kunst: Hoewel er bovenste grenzen (upper bounds) zijn voor de verstrengelingskosten (bijvoorbeeld via Clifford+T-decompositie of teleportatie), zijn er zeer weinig scherpe ondergrenzen (lower bounds). Bestaande technieken zijn vaak beperkt tot specifieke gevallen (zoals $f$-routing) of vereisen strenge aannames. Het bewijzen van ondergrenzen voor eenvoudige, veelvoorkomende twee-qubit poorten (zoals CNOT) bleef tot nu toe een open probleem.
• Relevantie: Het begrijpen van deze kosten is cruciaal voor kwantumpositie-verificatie, kwantumgravitatie, complexiteitstheorie en cryptografie.

2. Methodologie

De auteurs introduceren twee nieuwe, gerelateerde technieken om ondergrenzen voor de verstrengelingskosten te bepalen. Beide methoden zijn gebaseerd op het idee van het "controleren" van de toestand van een referentiesysteem ($Q$) en een input-systeem ($A$) door de input op een controle-wire ($B$) te variëren.

Het basisopzet (zie Figuur 3 in het artikel) is als volgt:

1. Alice en Bob delen een hulpbronverstrengeling $\Psi_{LR}$.
2. Het systeem $A$ wordt voorbereid in een toestand die gecorreleerd is met een referentiesysteem $Q$ (toestand $P_{QA}$).
3. De unitaire $U_{AB}$ wordt toegepast.
4. De auteurs analyseren hoe de correlatie of verstrengeling tussen $Q$ en $A$ verandert afhankelijk van de keuze van de input op $B$.

De twee technieken zijn:

A. Controleerbare Correlatie (Controllable Correlation - CC)

• Concept: Men kijkt naar de wederzijdse informatie (mutual information) $I(Q:A)$ na de toepassing van $U_{AB}$.
• Definitie: Een unitaire $U_{AB}$ heeft $(\lambda_1, \lambda_2)$-controleerbare correlatie als er een starttoestand $P_{QA}$ en twee inputs voor $B$ ($\phi_1, \phi_2$) bestaan zodanig dat:
  • $\lambda_1 = \max I(Q:A)$ (bij input $\phi_1$)
  • $\lambda_2 = \min I(Q:A)$ (bij input $\phi_2$)
• Resultaat: Als $\lambda_1 > \lambda_2$, impliceert dit dat de verstrengeling in de hulpbron $\Psi_{LR}$ minimaal $(\lambda_1 - \lambda_2)/2$ moet bedragen.
• Voordeel: Deze methode is breed toepasbaar en werkt voor willekeurige unitaire operaties.

B. Controleerbare Verstrengeling (Controllable Entanglement - CE)

• Concept: Deze methode is specifieker en richt zich op de verstrengeling van vorming (entanglement of formation, $E_f$).
• Definitie: Men begint met een maximaal verstrekte toestand tussen $Q$ en $A$ ($\Psi^+_{QA}$).
  • $\lambda_1$: De maximale $E_f(Q:A)$ die kan worden bereikt met een input $\phi_1$ op $B$.
  • $\lambda_2$: De minimale trace-afstand van de toestand $Q:A$ (bij input $\phi_2$) tot de verzameling van scheidbare (separable) toestanden.
• Resultaat: Als $\lambda_1$ groot is en $\lambda_2$ klein (bijvoorbeeld 0), dan is de ondergrens voor de verstrengelingskosten ongeveer $\lambda_1$.
• Voordeel: Deze methode kan leiden tot scherpere (tighter) ondergrenzen dan de CC-methode, maar is moeilijker te evalueren en werkt niet voor alle poorten.

3. Belangrijkste Bijdragen en Resultaten

De auteurs hebben numerieke optimalisaties uitgevoerd voor een groot aantal twee-qubit poorten en willekeurige unitaire operaties. De belangrijkste bevindingen zijn:

1. Nieuwe Ondergrenzen voor Bekende Poorten: Voor de eerste keer zijn er niet-triviale ondergrenzen bewezen voor veel standaard twee-qubit poorten, waaronder:

   • CNOT: De CE-methode levert een scherpe ondergrens van 1 EPR-paar op. Dit komt overeen met de bekende bovenste grens, waardoor de verstrengelingskosten voor CNOT volledig zijn opgelost.
   • DCNOT, Berkeley B, $\sqrt{SWAP}$, XX-interactie: Voor deze poorten zijn nieuwe ondergrenzen gevonden (bijv. 0.5 voor Berkeley B en XX, 0.30 voor $\sqrt{SWAP}$).
   • Random Unitaries: Voor Haar-willekeurige twee-qubit unitaire operaties tonen de technieken aan dat er bijna altijd een niet-triviale ondergrens bestaat (gemiddeld $\approx 0.23$ voor CC).

2. Parallelle Repetitie: Beide technieken hebben eigenschappen voor parallelle repetitie. Als een poort $G$ een ondergrens $\Delta$ heeft, dan heeft de parallelle uitvoering $G^{\otimes n}$ een ondergrens van minstens $n \cdot \Delta$. Dit is cruciaal voor toepassingen in complexiteitstheorie en cryptografie.

3. Robuustheid: De ondergrenzen gelden ook in een ruisomgeving (noisy setting), mits de implementatie dicht bij de ideale unitaire ligt.

4. Tabel met Resultaten:
   De paper presenteert een tabel met ondergrenzen voor diverse poorten (CNOT, iSWAP, Sycamore, Magic, etc.).

   • Opmerking: De SWAP-poort heeft een ondergrens van 0, wat correct is aangezien deze zonder verstrengeling kan worden geïmplementeerd (alleen via kwantumcommunicatie).
   • De CNOT-poort heeft een ondergrens van 1 (via CE), wat betekent dat er exact één EPR-paar nodig is.

4. Technische Details en Bewijsstrategie

• Continuïteit en Data Processing: De bewijzen maken gebruik van continuïteitsgrenzen voor wederzijdse informatie en verstrengeling van vorming (Fannes-type ongelijkheden) en de data-processing ongelijkheid.
• Causale Structuur: Een kernpunt in de bewijzen is dat de staat van het systeem $Q$ en de eerste helft van de hulpbron ($M_1$) niet kan afhangen van de input op $B$ vanwege de causale structuur van het circuit. Als de correlatie/verstrengeling tussen $Q$ en $A$ wel afhangt van de input op $B$, moet deze informatie "weg" zijn gegaan naar de tweede helft van de hulpbron ($R$), wat impliceert dat $R$ voldoende verstrengeling moet bevatten.
• Schumacher-compressie: Voor de CE-methode wordt een bewijsgevoerd dat gebruikmaakt van Schumacher-compressie. Als de verstrengelingskosten lager zouden zijn dan de berekende ondergrens, zou men de hulpbron kunnen comprimeren tot een kleinere dimensie, wat in strijd zou zijn met de noodzakelijke dimensie om de unitaire transformatie te simuleren.

5. Betekenis en Toekomstperspectief

• Fundamenteel Inzicht: Dit werk vult een groot gat in de literatuur door een systematische manier te bieden om verstrengelingskosten voor elke unitaire transformatie te evalueren, in plaats van alleen voor specifieke klassen.
• Toepassingen: De resultaten hebben directe implicaties voor:
  • Kwantumpositie-verificatie (QPV): Strakkere ondergrenzen leiden tot veiligere protocollen.
  • Kwantumgravitatie: Begrip van de entropie van verstrengeling in holografische modellen.
  • Cryptografie: Beperkingen op "uncloneable" secret sharing.
• Beperkingen: De huidige technieken zijn beperkt tot unitaire operaties. Het uitbreiden van deze methoden naar algemene kwantumkanalen (quantum channels) blijft een open probleem, aangezien kanalen verstrengeling kunnen "vernietigen" op een manier die deze specifieke ondergrenzen omzeilt.
• Observaties: Numerieke experimenten suggereren dat unitaire operaties met een verstrengelingskosten van nul een verzameling van maat nul vormen binnen de ruimte van alle twee-qubit unitaire operaties.

Conclusie: Cleve en May bieden met "controllable correlation" en "controllable entanglement" krachtige, nieuwe gereedschappen om de fundamentele kosten van niet-lokale kwantumberekening te kwantificeren, met als hoogtepunt het volledig oplossen van de verstrengelingskosten voor de CNOT-poort.