Equivalence of non-local computation tasks beyond Clifford operations

Sintesi Tecnica: Equivalenza di Compiti di Computazione Non Locale Oltre le Operazioni di Clifford

Definizione del Problema
La computazione quantistica non locale (NLQC) indaga come due parti spazialmente separate, Alice e Bob, possano implementare un canale quantistico congiunto su sistemi distribuiti utilizzando un singolo round simultaneo di comunicazione quantistica e entanglement condiviso. Sebbene sia noto che qualsiasi canale quantistico possa essere implementato tramite NLQC, il costo delle risorse — specificamente la quantità di entanglement pre-condiviso richiesto — varia significativamente tra i diversi compiti.

Una motivazione primaria per lo studio della NLQC è la sua applicazione alla Verifica della Posizione Quantistica (QPV). In una QPV, un prover tenta di convincere dei verifier della propria posizione fisica. Un prover che imbroglia, situato altrove, deve simulare le operazioni locali oneste del prover utilizzando la NLQC. La sicurezza di uno schema di QPV si basa sulla difficoltà del compito NLQC: se un prover che imbroglia richiede una quantità di entanglement esponenzialmente grande per simulare il compito, lo schema è considerato sicuro.

Il problema centrale affrontato in questo lavoro è la mancanza di una comprensione unificata della difficoltà relativa di diversi compiti di NLQC. Sebbene il compito di "f-routing" (instradamento controllato classicamente di un sistema quantistico) sia stato ampiamente studiato, non è chiaro se altri plausibili protocolli QPV — in particolare quelli che coinvolgono misurazioni quantistiche controllate o unitarie oltre il semplice routing — offrano una sicurezza migliorata. Gli autori mirano a determinare se questi compiti, apparentemente distinti, siano riducibili l'uno all'altro, stabilendo così se condividano lo stesso costo di entanglement asintotico.

Metodologia
Gli autori utilizzano un framework di riduzioni tra famiglie di compiti NLQC, analogamente alle riduzioni nella teoria della complessità computazionale. Definiscono due tipi di riduzioni:

1. Riduzione dello Stato di Risorsa: Un compito $G$ si riduce a un compito $F$ se $G$ può essere implementato utilizzando un piccolo numero di copie dello stato di risorsa richiesto per $F$.
2. Riduzione per Oracolo: Un compito $G$ si riduce a un compito $F$ se $G$ può essere implementato utilizzando un piccolo numero di chiamate a un oracolo black-box che implementa $F$, più operazioni locali e una piccola quantità di risorse condivise aggiuntive.

Il documento si concentra sui compiti f-controlled 2→2, dove l'operazione eseguita dipende dal valore di una funzione booleana $f(x, y)$ data ad Alice ($x$) e Bob ($y$). I sistemi di input sono tipicamente di dimensione costante (O(1) qubit), mentre gli input classici possono essere grandi ($n$ bit).

L'approccio tecnico prevede:

• Teletrasporto di Gate e Computazione Quantistica Basata su Misura (MBQC): Gli autori utilizzano gadget ispirati al teletrasporto di gate e alla MBQC non adattiva per costruire protocolli che trasformano un compito NLQC in un altro.
• Caratterizzazione e Manipolazione degli Angoli: Per le misurazioni a singolo qubit, gli autori caratterizzano i compiti tramite angoli di rotazione sulla sfera di Bloch. Sviluppano tecniche per aggiungere, dividere e approssimare questi angoli utilizzando combinazioni di protocolli più semplici (ad esempio, combinando protocolli $f$-measure con angoli $\theta_1$ e $\theta_2$ per simulare $\theta_1 + \theta_2$).
• Teletrasporto Basato su Porte (Port-Based Teleportation): Utilizzato negli appendici per dimostrare che la distribuzione spaziale degli input quantistici (se sul lato di Alice, sul lato di Bob o suddivisi) non altera significativamente la difficoltà del compito, a condizione che la dimensione dell'input sia costante.

Contributi Chiave e Risultati

1. Equivalenza dei Protocolli f-Measure a Singolo Qubit:
   Gli autori dimostrano che tutti i protocolli non triviali di $f$-measure a singolo qubit (dove la base di misurazione è scelta tra due basi arbitrarie $U$ e $V$ in base a $f(x,y)$) sono equivalenti sotto riduzioni di oracolo O(1).

   • Nello specifico, qualsiasi $f$-measure($U, V$) può essere ridotto al caso canonico $f$-measure($I, H$) (misurazione nelle basi computazionale o di Hadamard).
   • Ciò implica che nessun protocollo di misurazione proiettiva a singolo qubit offre un vantaggio di sicurezza rispetto al caso più semplice, poiché tutti ereditano lo stesso limite superiore di entanglement sub-esponenziale noto per l'f-routing.

2. Riduzione delle Operazioni Unitari di Clifford Controllate:
   Il documento dimostra che le unitari di Clifford f-controllate e le misurazioni in basi correlate a Clifford possono essere ridotte a $f$-measure($I, H$).

   • Stabilendo un'equivalenza tra $f$-measure($I, H$) e $f$-Bell measurement (misurazione nella base di Bell), gli autori mostrano che le operazioni di Clifford controllate possono essere implementate tramite strategie di teletrasporto di gate utilizzando oracoli $f$-Bell.
   • Questo estende la classe di compiti riducibili all'f-routing, confermando che anche le operazioni di Clifford controllate multi-qubit non richiedono intrinsecamente più entanglement rispetto al compito fondamentale di routing.

3. Estensione alle Unitari Diagonali Controllate:
   Un risultato significativo è la riduzione delle unitari controllate da f del tipo $U = C_1 D C_0$, dove $C_0, C_1$ sono circuiti di Clifford e $D$ è un'unitaria diagonale arbitraria.

   • Gli autori mostrano che $f$-unitary($I, U$) può essere ridotto per oracolo a $f$-measure($I, H$) con un overhead di O($n_Q$) (dove $n_Q$ è il numero di qubit).
   • Ciò è sorprendente perché $D$ può avere un'alta T-depth, rendendo $U$ altamente non-Clifford. Eppure, il costo di implementazione rimane legato al compito $f$-measure basato su Clifford più semplice.
   • La costruzione si basa su "gadget di iniezione di rotazione Z" che relazionano le rotazioni X controllate a singolo qubit (implementabili tramite $f$-measure) alle rotazioni Z multi-qubit controllate tramite gate CZ.

Significato e Rivendicazioni
Il documento sostiene che il panorama dei protocolli QPV realizzabili è più vincolato di quanto precedentemente pensato. Stabilendo una ricca struttura di riduzioni, gli autori dimostrano che:

• Limitazioni di Sicurezza: Molti schemi QPV proposti che coinvolgono misurazioni controllate a singolo qubit, operazioni di Clifford e persino certe unitari non-Clifford diagonali non offrono una sicurezza migliorata rispetto al compito base di $f$-routing. Tutti condividono la stessa scalabilità asintotica per il costo di entanglement (sub-esponenziale rispetto alla dimensione dell'input classico).
• Difficoltà Unificata: La difficoltà relativa di questi compiti è unificata; se esiste un attacco sub-esponenziale per l'f-routing, esso si estende a queste classi più ampie di compiti tramite le riduzioni stabilite.
• Avanzamento delle Tecniche: Il lavoro introduce nuove strategie per la NLQC, come specifici gadget di teletrasporto di gate e tecniche di divisione degli angoli, che possono essere di interesse indipendente per la costruzione di limiti superiori sui costi di entanglement per altri compiti di NLQC.

Gli autori rimangono modesti riguardo all'ambito di questi risultati, notando che, sebbene coprano una vasta classe di protocolli "fattibili" (grande input classico, piccolo input quantistico), rimane una questione aperta se due strati di gate diagonali o altre strutture unitarie più complesse possano fornire livelli di sicurezza più elevati che eludano queste riduzioni. I risultati non pretendono di provare limiti inferiori super-lineari, ma piuttosto chiariscono che molte estensioni intuitive dell'f-routing non sfuggono ai limiti superiori noti.