In che modo il calcolo quantico cambierà la programmazione? [chiuso]

Quando ho esaminato questo aspetto qualche tempo fa, era chiaro che gli algoritmi quantistici, sebbene non particolarmente veloci, permettessero un parallelismo esponenzialmente massiccio. Quindi brilleranno nei casi che riguardano la ricerca in spazi che non sono pratici con hardware sequenziale, anche con hardware sequenziale massicciamente parallelo.

Una proprietà degli algoritmi quantistici è che devono essere reversibili . Qualsiasi algoritmo dato può essere tradotto in uno che è reversibile, aggiungendo ad esso abbastanza record per consentirne il funzionamento all'indietro.

Un'altra proprietà è che ottenere una risposta da un algoritmo quantistico è un affare da colpire, poiché ciò che si ottiene alla fine di un calcolo è costituito da più risposte, ognuna con una propria probabilità. Deve essere eseguito in modo tale che la risposta desiderata abbia un'alta probabilità. Ciò potrebbe comportare l'esecuzione dell'algoritmo in avanti e all'indietro più volte.

Controlla Algoritmo di ricerca di Grover .

INSERITO per mostrare l'operazione fondamentale dell'algoritmo di Grover. Supponiamo che ci sia un problema di ricerca. Le risposte possibili sono 0, 1, 2 e 3, ma la risposta destra è 2. Quindi il computer quantico viene inserito in una sovrapposizione di tutti e quattro gli stati e passa attraverso una sequenza di passaggi per vedi quale è corretta, e inverte la sua ampiezza, come i punti neri e le frecce qui sotto:

Puoi vedere che la freccia 2 è stata invertita all'interno della macchina, ma non c'è modo di dirlo all'esterno, perché solo le probabilità sono visibili all'esterno, che sono ampiezze al quadrato e quando sono al quadrato sono tutte uguale.

Tuttavia, le ampiezze hanno una media, indicata dalla linea rossa, e il computer può essere fatto per passare attraverso una sequenza di passaggi che inverte ogni ampiezza della media . Quando ciò è fatto, le ampiezze e le probabilità trasferiscono allo stato 2, la risposta giusta ! Quindi, se la macchina viene osservata, lo stato 2 si illumina.

Non è proprio così semplice. Generalmente occorrono più cicli della macchina, avanti e indietro, invertendo alla fine di ogni ciclo, per massimizzare la probabilità della risposta corretta. Inoltre, si deve fare attenzione a non farlo più di quel numero di volte, perché può altrettanto facilmente invertire se stesso.

Quindi perché dicono che i computer quantistici sono così veloci ? Perché ogni volta che raddoppi il numero di qubit, devi quadrare il parallelismo, ma non hai quadrato il tempo, quindi alla fine vince.

Non è divertente?

Ero personalmente interessato a come questo potesse essere applicato alla verifica della correttezza del software. Ora testiamo il software lanciando una serie di input di test e (per essere troppo semplici) vedendo se colpisce un Assert. In un computer quantistico potrebbe essere possibile eseguirlo in parallelo contro un insieme di input molto più denso e vedere se qualcuno di questi casi ha colpito un Assert.

Come se l'input dell'algoritmo fosse di 128 byte, o 1024 bit, ci sono 2 ^ 1024 o 10 ^ 308 possibili ingressi diversi. Non c'è modo di testare molti input su un computer convenzionale, ma un computer quantico potrebbe provarli tutti in parallelo.

What would a C like language look like if it was designed for qubits? Would types change?

Sarebbe così drasticamente diverso da essere incomprensibile come C.

Il problema principale (a quanto ho capito) è che l'informatica quantistica non funziona in un modo imperativo "fai questo, poi quello, poi quest'altra cosa". Cercare di forzare la capacità di C di farlo nel "processore" del computer quantistico sarà, se non impossibile, selvaggiamente inefficiente.

Gli algoritmi di programmazione per i computer quantistici (di nuovo, a quanto li capisco) tendono ad essere più vicini alla mappa dello stile di programmazione funzionale / riduzione, poiché il calcolo quantico consente a tutti i candidati nella parte "ridotta" di esistere contemporaneamente e "cadere" del computer quando osservato.

Si noti che esistono alcuni algoritmi esistenti per i computer quantistici, anche se i dispositivi non esistono per eseguirli. Algoritmo di Simon per esempio.

Per fare l'uso più efficace possibile di un computer quantistico, è necessario essere in grado di gestire input e output che sono stati di un registro quantistico, per il quale non esiste realmente un analogo classico. Parlando da alcuni anni di esperienza nel campo dell'informazione quantistica, devo avvertirti che nessuno ha davvero una buona intuizione per questo al di là della matematica astratta delle algebre C *, e mi viene detto che anche questa intuizione risulta inadeguata se inizi a pensare alla teoria della relatività.

La classe di problemi che è risolvibile in modo efficiente su un computer quantistico è nota come BQP, per il polinomio quantistico limitato. Questa è la versione quantistica di BPP e puoi trovare ulteriori informazioni in questo documento: link

Mi è stato detto solo ieri sera da un ricercatore di algoritmi quantistici che c'è un problema molto importante che è completo con BQP: risolvere un sistema lineare di equazioni N. Classicamente, questo è risolvibile in passi O (N) con eliminazione gaussiana. L'algoritmo Harrow-Hassidim-Lloyd ( link ) lo risolve in polylog (N), a condizione che tu sia disposto ad accettare una risposta che la soluzione codificata come uno stato quantico. Se vuoi sfruttare appieno un computer quantistico, sembra quindi necessario avere un tipo corrispondente allo stato di un registro quantistico.

Anche se in questo momento sono un po 'al di fuori della mia particolare competenza, rischierei di indovinare che saresti in grado di programmare un computer quantico finché avessi accesso a un tipo corrispondente agli stati magici. Questo è un concetto difficile, però, che richiede un po 'di studio sull'argomento.

Sappiate che siamo da molto tempo dall'avere un linguaggio di programmazione quantistica, perché siamo ad uno stadio molto primitivo della ricerca di calcolo quantico. Chiedere una C quantistica adesso sarebbe come andare ad Alan Turing e chiedergli di progettare Python. Non abbiamo ancora ottenuto la versione quantistica del tubo del vuoto!