I solutori di algebra lineare classica possono implementare algoritmi quantistici con accelerazioni simili?
Un algoritmo quantistico inizia con un registro di qubit in uno stato iniziale, un operatore unitario (l'algoritmo) manipola lo stato di quei qubit, quindi lo stato dei qubit viene letto (o almeno alcune informazioni sullo stato su un singolo esecuzione dell'algoritmo).
Mi sembra che un computer quantistico risponda alla domanda degli atti unitari sullo stato quantistico. Questa è "solo" una questione di algebra lineare. Mi colpisce, quindi, che i computer quantistici possano essere visti come calcolatori di algebra lineare.
Perché allora abbiamo bisogno della meccanica quantistica? Non possiamo trovare un sistema classico che implementa operazioni di algebra lineare e usarlo per implementare gli algoritmi che sono stati progettati per i computer quantistici? Ovviamente i computer digitali classici non saranno sufficienti, queste macchine si basano sull'elaborazione binaria delle informazioni piuttosto che sulla manipolazione di vettori in uno spazio ad alta dimensione.
Domanda: Ci sono candidati per risolutori di algebra lineare classica (computer analogici classici) che potrebbero implementare gli algoritmi del "computer quantistico" mentre godono di una velocità simile rispetto ai computer classici digitali?
Domanda 2: Forse sto semplificando eccessivamente riducendo un computer quantistico a un semplice risolutore di algebra lineare. È questo il caso? Quale complessità sto sorvolando?
Risposte
La complessità su cui stai sorvolando è che nel caso generale devi archiviare $2^n$ ampiezze complesse per rappresentare anche un $n$sistema qubit classico. Pertanto, per un computer quantistico di diciamo 1000 qubit è necessario memorizzare$2^{1000}$ampiezze complesse. Anche se usi un atomo per ampiezza per farlo, rimarrai comunque a corto di atomi nell'universo osservabile.
Per quanto ne so, quanto sopra è l'argomento generale. Tuttavia, potrebbero esserci ancora modi per rappresentare determinati algoritmi quantistici in un modo trattabile in modo classico utilizzando alcune informazioni intelligenti per risparmiare sulle esigenze di rappresentazione dell'algoritmo, andando così al di sotto del$2^n$Requisiti. Ma è probabile che questo sia specifico del problema e improbabile che funzioni nel caso generale.
Secondo l'affermazione della domanda relativa al calcolo digitale rispetto a quello analogico, ci sono altri thread su questo sito che hanno chiesto informazioni su proposte simili. Vedi, ad esempio, qui e qui . Tra le altre cose, i sistemi analogici classici non possono impegnarsi in entanglement; quindi riformulare un computer quantistico come un computer analogico non porterà alla stessa accelerazione osservata.
Tuttavia, oltre alla risposta di @Attila Kun ci sono problemi specifici nell'algebra lineare / apprendimento automatico che hanno avuto algoritmi quantistici veloci ma sono stati rifusi come algoritmi classici con velocità simili.
Ad esempio, il problema di raccomandazione utilizzato da Netflix / Amazon / ecc. ha un algoritmo veloce su un computer quantistico. Questo algoritmo ha mostrato un miglioramento esponenziale rispetto all'algoritmo classico (allora) più noto.
Tuttavia, nel tentativo di dimostrare che l'algoritmo quantistico era veramente superiore, E. Tang ha mostrato che esisteva davvero un "sistema classico che implementa operazioni di algebra lineare e lo usa per implementare gli algoritmi che sono stati progettati per computer quantistici".
Il lavoro di Tang ha dato il via a un programma di dequantizzazione , ovvero di riprogettare algoritmi quantistici veloci in algebra lineare / apprendimento automatico come algoritmi classici veloci. Un articolo di Quanta Magazine descrive il problema e l'approccio di Tang.
Quali problemi sono suscettibili di questa dequantizzazione è un'area attiva di ricerca, come discute in questo thread . Ciò può dipendere dal rango delle matrici considerate.