The Signal
Shmueli collega l’ordine causale indefinito alla computazione oltre BQP
L’articolo di Omri Shmueli esamina se le operazioni quantistiche prive di un ordine causale fisso possano risolvere problemi al di fuori della normale computazione quantistica in tempo polinomiale. Presenta un metodo in tempo polinomiale pe
Quantum.world Team · Scritto con l’IA · verificato ·
«Supponendo che per l’orientamento a pozzo unico non esista un algoritmo quantistico in tempo polinomiale, il nostro risultato mostra che l’ordine causale indefinito può fornire una potenza computazionale oltre BQP nel formalismo delle matrici di processo, pur preservando l’unitarietà.»
Omri Shmueli, autore di «What Can Be Computed with Indefinite Causal Structure?»
Il risultato di Shmueli su BQP dipende da un’ipotesi di complessità
L’articolo di Omri Shmueli, inviato ad arXiv il 29 ottobre, sostiene che le computazioni basate su una struttura causale indefinita possono andare oltre BQP, una classe standard di problemi risolvibili da un computer quantistico in tempo polinomiale. L’affermazione è condizionata, non è una dimostrazione incondizionata dell’esistenza di un simile vantaggio computazionale: dipende dal fatto che per l’orientamento a pozzo unico non esista un algoritmo quantistico in tempo polinomiale.
L’articolo studia le matrici di processo, un quadro matematico per collegare operazioni quantistiche senza prescrivere un ordine causale globale fisso. Nel modello, un circuito quantistico di dimensioni polinomiali descrive una matrice di processo e un algoritmo riceve accesso al canale generato da tale descrizione. L’articolo considera la dimensione del circuito generatore come costo computazionale.
Questa convenzione sul costo è importante. Il risultato stabilisce che cosa si può calcolare avendo accesso ai canali generati dal modello; non dimostra che un laboratorio possa costruire un dispositivo capace di fornire tali canali per problemi arbitrari.
Due risultati, con restrizioni diverse
Shmueli presenta due risultati principali. Nel contesto più ampio, la computazione di processo in tempo polinomiale può risolvere ogni problema in NP, la classe le cui soluzioni proposte possono essere verificate in tempo polinomiale. I processi costruiti sono purificabili e generano canali unitari, ma i circuiti generatori non sono essi stessi unitari, quindi quei processi non sono puri.
Il secondo risultato impone il requisito più stringente di processi puri, i cui circuiti generatori sono unitari. In questo contesto, l’articolo fornisce un algoritmo in tempo polinomiale per l’orientamento a pozzo unico, o USO. Un’istanza assegna direzioni agli spigoli di un cubo booleano a n dimensioni, in modo che ogni faccia abbia esattamente un pozzo; il compito consiste nel trovare il pozzo dell’intero cubo.
Secondo l’articolo, l’algoritmo usa una volta il canale generato e riesce con probabilità uno. La costruzione di Shmueli inverte in modo coerente una funzione derivata dalle direzioni degli spigoli, quindi ottiene il pozzo globale applicando tale inversa alla stringa composta interamente da zeri. L’articolo osserva che gli algoritmi quantistici più efficienti noti per USO richiedono un tempo 2Ω(n), ma il divario non dimostra di per sé che non esista un algoritmo quantistico in tempo polinomiale.
Le matrici di processo non sono i normali collegamenti di un circuito
In un normale circuito quantistico, l’ordine delle operazioni dei gate è specificato dal circuito. Le matrici di processo descrivono invece come le operazioni quantistiche locali possano essere correlate senza fissare un ordine globale, richiedendo al contempo che la trasformazione risultante rimanga un canale quantistico valido per ogni scelta delle operazioni locali. Questa condizione mira a mantenere la normale meccanica quantistica a livello locale, anche quando la struttura causale globale non è fissa.
L’articolo distingue i processi puri da quelli purificabili. Un processo puro preserva l’evoluzione unitaria quando le operazioni locali sono unitarie, anche quando agiscono su registri ausiliari; un processo purificabile può essere ottenuto da un processo puro più ampio preparando input aggiuntivi e scartando output aggiuntivi. Il risultato di Shmueli su NP soddisfa la seconda condizione, mentre quello su USO è formulato usando processi puri.
Questa distinzione incide sulla misura in cui i risultati possono essere considerati una proposta fisica. Shmueli scrive che la realizzazione fisica efficiente per istanze arbitrarie di USO rimane una questione aperta. L’articolo avverte inoltre che una descrizione concisa del circuito non garantisce una facile implementazione fisica: nelle costruzioni basate sul teletrasporto con postselezione, le probabilità di successo possono essere esponenzialmente piccole anche quando il canale risultante è unitario.
La questione aperta è se USO appartenga a BQP
Il confronto centrale è quindi condizionato. Se per USO non esiste un algoritmo quantistico in tempo polinomiale, il risultato di Shmueli sui processi puri offre una via alla computazione oltre BQP nel modello delle matrici di processo. Se un normale algoritmo quantistico può risolvere USO in tempo polinomiale, quel particolare risultato non dimostrerebbe la separazione sostenuta.
Il risultato su NP è distinto: si applica a una classe più ampia di processi purificabili ma non puri e non dimostra che i circuiti quantistici standard possano risolvere in modo efficiente i problemi NP. Nessuno dei due risultati è una dimostrazione sperimentale del fatto che la struttura causale indefinita fornisca questa potenza computazionale. Il risultato concreto dell’articolo è un algoritmo matematico per trovare il pozzo unico di un cubo booleano orientato, la cui implicazione riguardo al superamento di BQP dipende dalla complessità quantistica ancora irrisolta di tale compito.