The power of constant-depth quantum circuits of unbounded size

Sintesi Tecnica: Il Potere dei Circuiti Quantistici a Profondità Costante di Dimensione Illimitata

Enunciato del Problema
Il saggio investiga il potere computazionale dei circuiti quantistici quando le restrizioni sulla dimensione del circuito e sullo spazio ancillare vengono rimosse. Nella complessità classica, la classe $AC^0$ (circuiti a profondità costante con porte AND/OR a fan-in illimitato) non può calcolare la parità. Tuttavia, se la restrizione della dimensione polinomiale viene sollevata, ogni funzione booleana può essere calcolata in profondità costante tramite costruzioni DNF (Forma Normale Disgiuntiva). Gli autori si chiedono se un fenomeno simile valga per i circuiti quantistici costruiti con arbitrarie porte a singolo qubit e porte Toffoli generalizzate ($QAC^0$). Nello specifico, ogni operazione unitaria può essere implementata esattamente in profondità costante se la dimensione del circuito e il numero di qubit ancillari sono illimitati?

Gli autori inquadrano questa indagine attraverso quattro compiti via via più generali:

1. Calcolare l'appartenenza a qualsiasi insieme $L \subseteq \{0, 1\}^n$.
2. Implementare qualsiasi permutazione degli stati della base computazionale.
3. Preparare qualsiasi stato puro.
4. Implementare qualsiasi unitaria arbitraria su ogni stato di input.

Metodologia
Gli autori impiegano una combinazione di costruzioni di circuiti classici reversibili, tecniche classiche probabilistiche adattate al dominio quantistico e protocolli di teletrasporto quantistico.

• Costruzioni Classiche Reversibili: Gli autori stabiliscono prima che arbitrarie permutazioni di stringhe di bit possono essere implementate in profondità costante utilizzando porte Toffoli e fanout. Ciò è ottenuto tramite uno schema di "codifica indicatrice": l'input viene mappato in un vettore indicatore a $2^n$ dimensioni (dove esattamente un elemento è 1), manipolato, e poi decodificato nuovamente nella stringa originale. Questo permette l'evaluazione parallela di tutte le possibili stringhe di input.
• Adattamento Probabilistico al Quantistico: Per preparare distribuzioni di probabilità arbitrarie e stati puri, gli autori adattano una costruzione classica probabilistica. Ciò comporta il campionamento indipendente di bit per codificare una distribuzione basata sulla posizione del primo '1'. Nel contesto quantistico, ciò viene reso coerente applicando rotazioni inverse ai qubit che seguono il primo '1' per riportarli allo stato $|0\rangle$ senza distruggere la sovrapposizione.
• Estensioni del Set di Porte: Sebbene il set di porte primario includa porte a singolo qubit e porte Toffoli generalizzate, gli autori utilizzano le porte fanout come strumento concettuale. Citano i risultati di Grier, Morris e Wu [GMW26] e Rosenthal [Ros20] per mostrare che il fanout può essere implementato esattamente in profondità costante usando solo il set di porte primario, sebbene con un potenziale aumento della dimensione del circuito verso limiti doppiamente esponenziali.
• Riduzioni per le Unitarie: Per l'implementazione di unitarie arbitrarie, gli autori non forniscono una costruzione diretta. Invece, offrono diverse formulazioni equivalenti e riduzioni. Queste includono la riduzione dell'implementazione di unitarie a:
  • Clonazione di vettori di una base ortonormale specificata.
  • Permutazione di liste di vettori di base.
  • Decodifica di etichette di base.
  • Implementazione di unitarie con somme di riga e colonna unitarie (tramite la forma normale di Idel-Wolf).
  • Implementazione di involuzioni unitarie traceless (usando un qubit pulito aggiuntivo).
• Teletrasporto Basato su Porte (PBT): Per avvicinarsi all'implementazione di unitarie arbitrarie senza correzioni unitarie dipendenti dalla specifica porta, gli autori utilizzano il Teletrasporto Basato su Porte (PBT). Costruiscono un circuito unitario che esegue il PBT utilizzando stati massimamente entangled (o stati Choi dell'unitaria target) e una misura congiunta, seguiti dalla selezione della porta.

Contributi Chiave e Risultati

1. Costruzioni a Profondità Costante Esatte per Compiti Specifici:

   • Permutazioni: Arbitrarie permutazioni degli stati della base computazionale possono essere implementate in profondità costante (profondità $\le 20$) utilizzando $O(n2^n)$ porte e qubit ancillari.
   • Unitarie Diagonali: Arbitrarie unitarie diagonali possono essere implementate in profondità costante (profondità 7) calcolando gli indicatori, applicando le fasi in parallelo e scomputando.
   • Preparazione dello Stato: Arbitrari stati puri possono essere preparati in profondità costante (profondità $\le 37$) utilizzando $O(4^n)$ qubit e $O(n2^n)$ porte. Tutti i qubit ancillari sono riportati a zero.
   • Implementazione del Fanout: Il fanout può essere implementato esattamente in profondità costante usando solo porte a singolo qubit e Toffoli generalizzate, sebbene ciò possa richiedere una dimensione doppiamente esponenziale.

2. Riduzioni per Unitarie Arbitrarie:
   Il saggio dimostra che implementare unitarie arbitrarie in profondità costante è equivalente a implementare una serie di operazioni specifiche (ad esempio, clonare vettori di base, decodificare etichette o implementare involuzioni traceless). Ciò inquadra il problema aperto dell'implementazione di unitarie arbitrarie in un insieme di sfide strutturali equivalenti.

3. Misure Adattive e Teletrasporto di Porte:
   Gli autori mostrano che, se sono consentite misure intermedie adattive, qualsiasi porta al livello $\ell$ della gerarchia di Clifford può essere implementata con profondità $O(\ell)$. Inoltre, l'implementazione di unitarie arbitrarie si riduce all'implementazione di involuzioni unitarie traceless in questo modello adattivo.

4. Approssimazione tramite Teletrasporto Basato su Porte (PBT):
   Gli autori costruiscono un circuito unitario per il Port-Based Teleportation (PBT) per una dimensione di input $d$ e $M \ge d^2 - 1$ porte.

   • Profondità: La profondità del circuito è $O(\sqrt{d})$, ed è indipendente dal numero di porte $M$.
   • Fedeltà: La fedeltà di entanglement è limitata da $F_e \ge (1 - \frac{d^2-1}{2M})^2$.
   • Accuratezza vs Profondità: Per qualsiasi dimensione di input $d$ fissata, l'approssimazione può essere resa arbitrariamente accurata aumentando $M$ senza aumentare la profondità del circuito. Tuttavia, la dipendenza dalla dimensione di input $d$ rimane; resta aperto il quesito se sia possibile ottenere un limite di profondità indipendente da $d$.
   • Implementazione: Il circuito utilizza solo porte a singolo qubit e Toffoli generalizzate e non richiede misure intermedie.

Significato e Rivendicazioni
Il saggio stabilisce che la rimozione delle restrizioni su dimensione e spazio ancillare permette ai circuiti quantistici a profondità costante di eseguire compiti generalmente impossibili nei modelli a dimensione polinomiale a profondità costante, come la preparazione di stati arbitrari e la permutazione degli stati di base. Ciò collega direttamente la preparazione dello stato quantistico alla computazione classica reversibile e alla preparazione di distribuzioni di probabilità.

Tuttavia, il saggio mantiene una posizione modesta riguardo all'implementazione di unitarie arbitrarie. Sebbene fornisca costruzioni esatte a profondità costante per permutazioni, unitarie diagonali e preparazione di stati, l'implementazione di unitarie generali rimane un problema aperto. Gli autori forniscono caratterizzazioni equivalenti di questo problema ma non lo risolvono.

Il contributo principale riguardante le unitarie generali è la costruzione PBT. Gli autori dimostrano che per qualsiasi dimensione di input fissata, le unitarie arbitrarie possono essere approssimate con precisione arbitraria senza aumentare la profondità del circuito aumentando il numero di porte. Tuttavia, la profondità di questa costruzione scala come $O(\sqrt{d})$ rispetto alla dimensione dell'input $d$. Gli autori dichiarano esplicitamente che se la dipendenza da $d$ possa essere rimossa (ovvero, ottenere un limite di profondità indipendente da $d$) rimane una questione aperta. Il lavoro evidenzia che la difficoltà fondamentale nell'implementazione di unitarie a profondità costante non risiede nel produrre un output arbitrario da un input fisso, ma nel prescrivere l'azione su ogni stato di input simultaneamente preservando l'unitarietà.