Pseudoentanglement in constant depth: How trivial states can have non-trivial entanglement structure

Sintesi Tecnica: Pseudoentanglement in Profondità Costante

Definizione del Problema
Lo studio dell'entanglement è centrale per l'informazione quantistica, eppure stimare l'entropia di entanglement di uno stato quantistico è generalmente computazionalmente difficile, anche per i computer quantistici. Ciò motiva il concetto di pseudoentanglement: famiglie di stati quantistici in cui la struttura dell'entanglement è computazionalmente indistinguibile da stati con diversa entropia di entanglement, nonostante gli stati stessi siano preparabili in modo efficiente.

Una questione aperta critica riguarda la relazione tra pseudoentanglement e pseudocasualità. Mentre gli stati pseudocasuali (PRS) e le unitarie (PRU) richiedono che il circuito di preparazione sia nascosto (o che la profondità del circuito sia sufficiente a impedire l'apprendimento efficiente), risultati recenti indicano che i circuiti quantistici a profondità costante e fan-in limitato ($QNC^0$) sono apprendibili efficientemente da un numero polinomiale di campioni. Questa apprendibilità esclude l'esistenza di stati pseudocasuali in $QNC^0$. Tuttavia, rimane incerto se stati pseudoentangled possano essere preparati da tali circuiti così superficiali e geometricamente locali. In particolare, possono gli stati "triviali" (quelli preparabili da circuiti a profondità costante) esibire strutture di entanglement che siano computazionalmente difficili da stimare?

Metodologia
Il lavoro costruisce una famiglia di circuiti quantistici a profondità costante e località 2D che generano stati pseudoentangled. La costruzione si basa su tre componenti tecniche principali:

1. Assunzione Crittografica: La difficoltà del problema Dense-Sparse Learning Parity with Noise (Dense-Sparse LPN), introdotto da Dao e Jain [DJ25]. Questa assunzione fornisce una coppia di mappe lineari, $F_{low}$ e $F_{high}$, che sono computazionalmente indistinguibili ma possiedono proprietà di entropia differenti su input sparsi. Nello specifico, $F_{high}$ è iniettiva su input sparsi (generando alta entropia), mentre $F_{low}$ è molti-a-uno (generando bassa entropia).
2. Codifica Randomizzata a Fan-in Limitato: Il contributo tecnico centrale è una nuova codifica randomizzata perfetta per mappe lineari dense $x \mapsto Mx$. A differenza di precedenti codifiche che richiedevano porte di fan-out illimitate, questa costruzione utilizza solo fan-in e fan-out limitati (nello specifico, fan-in/fan-out $\le 3$).
   • La codifica introduce maschere casuali uniformi $r$ e $s$.
   • Produce bit $w$ e $z$ tali che un decoder deterministico possa recuperare $Mx$.
   • Fondamentalmente, l'entropia dell'output codificato è esattamente $H(Mx)$ più un termine fisso dipendente dalla maschera e indipendente dalla matrice $M$. Ciò preserva il gap di entropia tra i due rami "low" e "high" della mappa lineare sottostante.
   • La codifica è implementata tramite una griglia 2D di plaquette di dimensione costante usando solo porte CNOT tra vicini, garantendo che il circuito sia 2D-locale e a profondità costante.
3. Preparazione dello Stato: Gli autori preparano una sovrapposizione coerente dei bit di input (campionati da una distribuzione di Bernoulli sparsa) e delle maschere casuali. Applicano il circuito di codifica randomizzata in modo coerente. Tracciando via i registri di input e di maschera, si ottiene una matrice densità diagonale sui registri di output la cui entropia di Shannon è uguale all'entropia della codifica randomizzata. Grazie alla proprietà di preservazione dell'entropia, l'entropia di entanglement attraverso il taglio input-output riflette il gap di entropia delle mappe lineari sottostanti.

Contributi Chiave e Risultati

• Teorema 1.1 (Pseudoentanglement a Profondità Costante): Assumendo l'intrattabilità del Dense-Sparse LPN per avversari con tempo quantistico polinomiale (QPT), esiste una distribuzione campionabile efficientemente su tuple $(C_{low}, C_{high}, W)$, dove $C_{low}$ e $C_{high}$ sono circuiti a profondità costante e 2D-locali. Gli stati in uscita $|\psi_{low}\rangle$ e $|\psi_{high}\rangle$ presentano un gap di entropia di entanglement additivo di $\omega(\log n)$ attraverso un fissato taglio $W$, eppure le descrizioni dei circuiti sono computazionalmente indistinguibili.

  • Significato: Questo dimostra che l'pseudoentanglement è possibile nel regime $QNC^0$, mentre la pseudocasualità non lo è. Gli stati sono pseudoentangled a "chiave pubblica": i loro circuiti di preparazione sono pubblici e superficiali, eppure la loro struttura di entanglement è nascosta.

• Teorema 1.2 (Codifica Randomizzata): Il documento fornisce una prova formale della codifica randomizzata a fan-in e fan-out limitati per mappe lineari dense. Questa codifica preserva l'esatta entropia della mappa lineare fino a una costante additiva ed è di interesse indipendente per la crittografia a bassa profondità (ad esempio, per costruire hash collision-resistant da assunzioni di codice casuale).

• Teorema 1.3 (Difficoltà dell'Hamiltoniana 2D): Coniugando i proiettori locali con i circuiti pseudoentangled, gli autori costruiscono una famiglia di Hamiltoniane 2D locali con un gap spettrale costante (gap = 1). Gli stati fondamentali unici di queste Hamiltoniane ereditano il gap di entanglement, rendendo il compito di apprendere l'entropia di entanglement attraverso un fissato taglio computazionalmente difficile per un osservatore quantistico.

• Teorema 1.4 (Difficoltà dell'Hamiltoniana 1D): Utilizzando una costruzione a stati di storia (history-state) di Feynman–Kitaev 1D con padding, gli autori estendono il risultato a Hamiltoniane locali 1D. Queste Hamiltoniane hanno un gap spettrale inverso-polinomiale. Gli stati fondamentali unici mantengono il gap di entanglement (fino a una piccola perdita additiva), stabilendo l'esistenza di una difficoltà per i sistemi 1D basata su un'assunzione crittografica post-quantum basata su codici.

Significato e Rivendicazioni
Il documento sostiene di aver stabilito una netta separazione tra pseudocasualità e pseudoentanglement nel regime dei circuiti superficiali. Sebbene i circuiti a profondità costante non possano generare stati pseudocasuali (a causa della loro apprendibilità efficiente), essi possono generare stati pseudoentangled.

• Natura a Chiave Pubblica: A differenza degli stati pseudocasuali, che richiedono che il circuito di preparazione sia segreto, questi stati pseudoentangled sono generati da circuiti pubblici. Ciò consente di inquadrare i risultati di durezza nel modello di complessità computazionale (l'input è una descrizione classica di un circuito/Hamiltoniana) piuttosto che nel modello di complessità di campionamento.
• Sicurezza Post-Quantum: La difficoltà si basa sul Dense-Sparse LPN, un'assunzione basata su codici ritenuta sicura contro avversari quantistici, in contrasto con risultati precedenti (ad esempio, [BZZ24]) che si basavano sulla fattorizzazione (che è quantisticamente trattabile).
• Limitazioni: Gli autori notano esplicitamente alcune limitazioni. Il "taglio nascosto" è fisso e non geometrico (determinato dalla struttura del circuito piuttosto che da una regione spaziale connessa), il che significa che il risultato non affronta direttamente i tagli geometrici rilevanti per le distinzioni tra legge dell'area (area-law) e legge del volume (volume-law) nella gravità quantistica. Inoltre, la costruzione è specifica per l'entropia di von Neumann (Shannon); estendere il risultato ad altre entropie di Rényi non è garantito dall'attuale analisi delle funzioni con perdita (lossy-function analysis).

In sintesi, il lavoro dimostra che stati "triviali" (a profondità costante e locali) possono possedere strutture di entanglement computazionalmente nascoste, a patto di accettare plausibili assunzioni crittografiche post-quantum.