Conseguenze di$MIP^\ast=RE$Per quanto riguarda gli algoritmi quantistici
La prova (in attesa di revisione tra pari) di$MIP^\ast=RE$in questa pre-stampa è stato salutato come un significativo passo avanti. Il significato di questo risultato è affrontato da Henry Yuen (uno degli autori) in questo post sul blog . Scott Aaronson elenca anche alcune delle principali implicazioni in questo post sul blog .
Per un gioco non locale ($G$), definiscono il massimo delle probabilità di successo per strategie di prodotti tensoriali non relativistici come$\omega^\ast(G)$, e il massimo delle probabilità di successo per una strategia di operatore di pendolarismo relativistico (QFT) as$\omega^{co}(G)$. Poiché il QM non relativistico è un caso speciale di QFT, è chiaro che una strategia ottimale basata sull'operatore di pendolarismo è valida almeno quanto una strategia ottimale basata sul prodotto tensoriale,$\omega^\ast(G) \le \omega^{co}(G)$.
La mia comprensione del post di Yuen è una conseguenza di$MIP^\ast=RE$è che esistono giochi non locali per i quali$\omega^\ast(G) < \omega^{co}(G)$. Nello specifico, dice
Ci deve essere un gioco$G$, quindi, per cui il valore del quanto è diverso dal valore dell'operatore di pendolarismo. Ma questo implica che il problema di Tsirelson ha una risposta negativa, e quindi la congettura di incorporamento di Connes è falsa.
Capisco che ciò significhi che esiste una classe di problemi per i quali gli algoritmi che utilizzano tecniche di QFT (operatori di pendolarismo) hanno probabilità di successo più elevate rispetto agli algoritmi che utilizzano tecniche di QM non relativistica (prodotti tensoriali, formalismo del circuito quantistico).
La prima parte della mia domanda è, supponendo che questa prova valga :
- Fa$MIP^\ast=RE$implica che esiste una serie di problemi che possono essere risolti in modo più efficiente impiegando il formalismo matematico di QFT (operatori di pendolarismo) piuttosto che il formalismo QM non relativistico (circuiti quantistici convenzionali)?
A meno che non stia interpretando male, questo sembra derivare direttamente dalle dichiarazioni di Yuen. Se è così, è possibile che esista una serie di giochi non locali per i quali$\omega^\ast(G) < 0.5$e$\omega^{co}(G) > 0.5$? In particolare, la seconda parte della mia domanda è:
- Fa$MIP^\ast=RE$implica che esiste (o potrebbe esserci) un insieme di problemi che possono essere risolti utilizzando operatori di pendolarismo che non possono essere risolti utilizzando circuiti quantistici, o questa possibilità è preclusa dall'universalità del modello del circuito quantistico?
EDIT: Henry Yuen ha creato un MIP* Wiki per coloro che sono interessati a comprendere meglio questa classe di complessità o il$MIP^\ast = RE$risultato.
Risposte
Non so se il risultato MIP* = RE, e in particolare l'affermazione che esiste un gioco non locale$G$dove$\omega^*(G) \neq \omega^{co}(G)$, ha implicazioni algoritmiche per i computer quantistici. Ci sono un paio di cose da dire qui.
Il risultato MIP* = RE riguarda quali problemi computazionali possono essere verificati utilizzando giochi non locali, in contrasto con ciò che può essere risolto da giochi non locali (non sono sicuro di cosa significherebbe, comunque!). La distinzione tra verificare e risolvere è dovuta a quanto segue: in un gioco non locale, assumiamo che Alice e Bob conoscano magicamente la risposta al problema (quindi assumiamo che possano risolvere istantaneamente qualsiasi problema computazionale). La loro sfida non è risolverlo, ma dimostrarloa un verificatore classico polinomiale conoscono la risposta. Il solo fatto di conoscere la risposta a qualcosa non significa che sei in grado di convincere qualcun altro della risposta. Il fatto che Alice e Bob possano utilizzare le correlazioni dal framework del prodotto tensoriale o dal framework dell'operatore di pendolarismo influisce su ciò che sono in grado di dimostrare al verificatore. MIP* = RE mostra che, con le correlazioni del prodotto tensoriale, Alice e Bob possono dimostrare di sapere che una macchina di Turing alla fine si ferma. Questo è qualcosa che non può essere fatto se Alice e Bob condividono correlazioni tra operatori di pendolarismo; pertanto il modello dell'operatore pendolare differisce dal modello del prodotto tensoriale.
La seconda cosa che volevo menzionare è, separatamente, è una domanda interessante se si possa definire un modello di calcolo quantistico che parli di operatori di pendolarismo e sistemi a dimensione infinita. Sembra che Cleve, et al. abbiano provato a trovare un modello per questo, qualcosa che chiamano il modello del circuito C*:https://arxiv.org/pdf/1811.12575.pdf. Potresti trovarlo interessante.