Computer quantistico e calcolo quantistico. Concetti e principi di base del calcolo quantistico

13.07.2020

Di tanto in tanto vediamo una raffica di notizie sull'informatica quantistica. C'è molta attenzione su questo argomento, con un'azienda che afferma di avere un algoritmo di crittografia di cui avrai bisogno presto, poiché i computer quantistici rendono inutili gli algoritmi di crittografia moderni.

Per una persona curiosa, tali affermazioni sollevano domande. Cos'è il Quantum Computing (Figura 1)? È vero? In caso affermativo, come funziona? E in che modo questo si collega alla crittografia? Poi vengono fuori altre domande personali. Il quantum computing può cambiare le mie pratiche di progettazione? Devo studiare questo materiale?

Anche nel rendering degli artisti, gli elementi computazionali quantistici sono diversi da qualsiasi cosa nel mondo dell'hardware digitale.

Figura 1 - Visualizzazione di elementi di calcolo quantistico

Si scopre che queste non sono domande molto facili da studiare. La letteratura pertinente appartiene principalmente a uno dei due generi. Il primo è destinato a un pubblico più ampio e vede la meccanica quantistica come un inferno: oscura, forse pericolosa e completamente incomprensibile. Dopo aver letto tale letteratura, è piuttosto difficile trarre conclusioni.

Il secondo genere è completamente diverso, ma altrettanto "utile", scritto da esperti per impressionare altri esperti. Questo genere è caratterizzato dall'uso di termini come la macchina di Turing, il nome di Richard Feynman, lo spazio di Hilbert e la trasformazione di Hadamard, tutto quanto sopra e circa altre 75 parole, seguito da una confusione di equazioni con una terminologia sconosciuta e inspiegabile. Naturalmente, ricordate tutti bene cosa significa | 0\u003e!

Tre universi paralleli

Uno dei motivi per cui questo argomento è così complesso è che il calcolo quantistico abbraccia tre discipline con terminologia e interessi molto diversi. Tutto è iniziato con i fisici teorici. Già nel 1980, il fisico Paul Benioff ( Paolo Benioff) dell'Argonne National Laboratory ha descritto come alcuni effetti della meccanica quantistica possono essere utilizzati per implementare una macchina di Turing. Due anni dopo, anche il famoso fisico Richard Feynman ha sollevato la questione di un computer che utilizza il comportamento quantistico.

Ma l'idea è stata ripresa da un gruppo completamente diverso: informatici e matematici. Prendendo dalla fisica le idee di base del bit quantistico (qubit) e delle trasformazioni unitarie reversibili (che hanno chiamato porte quantistiche o quentili), gli informatici hanno studiato quali calcoli potrebbero essere eseguiti se ci fossero qubit ideali e porte quantistiche. Hanno trovato casi in cui tali presunti computer potrebbero essere molto più veloci dei computer digitali convenzionali.

Questo risultato ha spinto i fisici sperimentali - il terzo gruppo - a iniziare i tentativi di creare dispositivi fisici che potessero approssimare qubit ideali e porte quantistiche. È stato uno studio lungo e ad alta intensità di risorse che deve ancora dimostrare che un computer quantistico nella vita reale è fisicamente possibile. Ma questa possibilità è estremamente incoraggiante.

Alcune spiegazioni

Allora cos'è questo computer immaginario che ci interessa? Chiariamo prima alcuni malintesi. Un computer quantistico non è un normale computer che simula fenomeni di meccanica quantistica. Inoltre non è un normale computer digitale, costruito da alcuni transistor (l'era della fine della legge di Moore), così piccoli da immagazzinare o scambiare singoli quanti di energia.

Invece, i computer quantistici sono macchine basate su comportamenti unici descritti dalla meccanica quantistica che sono completamente diversi dal comportamento dei sistemi classici. Una di queste differenze è la capacità di una particella o di un gruppo di particelle in qualche modo di essere solo in due stati di base quantistici discreti - chiamiamoli 0 e 1. Qui faremo a meno delle parentesi divertenti (la notazione usata nella teoria quantistica - aggiunta dal traduttore) Esempi di questo tipo sono elettrone, polarizzazione del fotone o carica del punto quantico.

In secondo luogo, il calcolo quantistico dipende dalla proprietà della sovrapposizione: la capacità controintuitiva di una particella di trovarsi in una combinazione di entrambi gli stati di base 0 e 1 contemporaneamente, fino a quando non viene effettuata una misurazione. Non appena misuri un tale stato, diventa 0 o 1 e tutte le altre informazioni scompaiono. La meccanica quantistica descrive correttamente tale stato combinato come la somma di due stati fondamentali, ciascuno dei quali è moltiplicato per un coefficiente complesso. Il valore totale di questi coefficienti è sempre 1. Tale stato può essere rappresentato come un vettore unitario che parte dall'origine e termina da qualche parte su una sfera chiamata sfera di Bloch, che è mostrata nella Figura 2. Il punto chiave qui è che il quadrato (modulo - aggiunto traduttore) del coefficiente complesso per lo stato di base 0 rappresenta la probabilità che la misura rileverà un qubit nello stato di base 0, analogamente per lo stato di base 1. E quando effettui una misurazione, otterrai sempre esattamente lo stato 0 o esattamente lo stato 1.

Figura 2 - Sfera di Bloch - uno dei modi per visualizzare una sovrapposizione quantistica in un qubit

Questa (proprietà di sovrapposizione - aggiunta dal traduttore) è importante perché consente al qubit di trovarsi negli stati 0 e 1 contemporaneamente. Di conseguenza, un registro costituito da n qubit può "contenere" simultaneamente tutti i possibili numeri binari lunghi n bit. Ciò consente a un computer quantistico di eseguire una singola operazione non solo su un numero intero di n bit, ma su tutti i possibili numeri interi di n bit contemporaneamente: un parallelismo molto significativo all'aumentare di n.

Terzo, il calcolo quantistico dipende dalla capacità della porta quantistica di modificare questi coefficienti, e quindi dalla probabilità di misurare un numero particolare, in modo prevedibile. Se si inizia con uno stato in cui tutti i coefficienti in tutti i qubit sono uguali e quindi si misurano tutti i qubit in un registro, è altrettanto probabile che si trovi una stringa di bit compresa tra una stringa di tutti zeri e una stringa di tutti uno, inclusi. Ma eseguendo questo stato iniziale attraverso una sequenza accuratamente scelta di porte quantistiche, il computer quantistico può modificare questi coefficienti in modo che lo stato che è più probabile che misuri in uscita sia il risultato di un calcolo, ad esempio, è molto probabile che misuri i bit di un numero che è un quadrato esatto.

Computer su carta

Ma cosa c'entra tutto questo con l'informatica reale? Per rispondere a questa domanda, dobbiamo spostare la nostra attenzione dai fisici teorici agli informatici e ai matematici. Per ottenere risultati pratici, dobbiamo essere in grado di tradurre il registro dei qubit in una certa sovrapposizione di stati. Abbiamo bisogno di porte quantistiche, forse cavi e qualche tipo di dispositivo di output.

Tutto questo è facile per gli specialisti di computer: possono semplicemente presumere che queste idee siano già state implementate nella vita reale. Tuttavia, dovranno fare concessioni alla meccanica quantistica. Per non violare le leggi della fisica quantistica, gli informatici devono richiedere che le porte quantistiche siano reversibili: puoi mettere il risultato sull'output e ottenere i valori di input corretti all'ingresso. E insistono sul fatto che le porte quantistiche sono trasformazioni unitarie. Secondo l'algebra della matrice, ciò significa che quando passi lo stato di un qubit attraverso una porta quantistica, lo stato che ottieni sarà 0 o 1 quando misurato e la somma delle probabilità dei quadrati (moduli - aggiunti dal traduttore) di questi coefficienti rimarrà uguale unità.

Si noti che queste porte quantistiche, anche in teoria, sono molto diverse dalle normali porte logiche. Ad esempio, la maggior parte delle funzioni booleane non è reversibile. È impossibile emettere dati di input da una porta NAND a meno che l'output non sia 0. E, naturalmente, le porte funzionano solo con uno e zero (stati 1 e 0), mentre le porte quantistiche funzionano ruotando un vettore all'interno di una sfera di Bloch ... In effetti, non c'è niente in comune tra loro tranne che per il nome.

Gli informatici hanno scoperto che un insieme molto piccolo di porte quantistiche è sufficiente per emulare una macchina di Turing: solo un insieme di porte quantistiche a un ingresso e una porta quantistica a due ingressi. L'esempio più comunemente usato di una porta quantistica a due ingressi è un "NOT controllato" (CNOT). Questa funzione reversibile ribalta lo stato del vettore del qubit o lo lascia invariato, a seconda dello stato del secondo qubit. È più simile a un'analogia quantistica con OR esclusivo.

Possibili vantaggi

Non abbiamo ancora risposto alla domanda su come tutto ciò possa essere utilizzato. La risposta è che se colleghi un numero sufficiente di porte quantistiche insieme in modo appropriato e se puoi preparare qubit di input per rappresentare tutti i numeri possibili nel tuo dominio di input, allora all'uscita dell'array di porte quantistiche, puoi teoricamente misurare i bit che rappresentano valori di qualche funzione utile.

Facciamo un esempio. Nel 1994, il matematico Peter Shor, presso i Bell Labs, ha sviluppato un algoritmo per la fattorizzazione di numeri molto grandi utilizzando subroutine quantistiche. Questa fattorizzazione è un problema vitale nella matematica applicata, perché non esiste una soluzione analitica: l'unico modo è provare ed errore, e puoi solo rendere l'algoritmo più veloce scegliendo i numeri di prova appropriati in un modo più sottile. Di conseguenza, quando si imposta un numero di input molto grande, la quantità di tentativi ed errori diventa schiacciante. Non è un caso che questa sia la base di algoritmi crittografici come RSA. I codici RSA e a curva ellittica sono difficili da decifrare, soprattutto perché è così difficile fattorizzare numeri enormi.

L'algoritmo di Shor ha combinato alcuni calcoli tradizionali con due funzioni quantistiche che velocizzano direttamente l'algoritmo in termini di tentativi ed errori, infatti, iterando contemporaneamente su tutti i numeri possibili, una dimostrazione dell'algoritmo è mostrata nella Figura 3. Una di queste funzioni quantistiche esegue esponenziazione modulare, e l'altra implementa una versione quantistica della trasformata veloce di Fourier (FFT). Per ragioni che solo un matematico potrebbe amare, se introducessimo un insieme di n qubit, preparati in modo che insieme rappresentino tutti i possibili numeri binari fino alla lunghezza n, allora nelle porte quantistiche i vari stati in sovrapposizione si annullano a vicenda - come l'interferenza di due raggi di luce coerenti - e ci rimane una certa struttura di stati nel registro di uscita.

Figura 3 - L'algoritmo di Shor dipende dalle routine quantistiche per l'esponenziazione modulare e le operazioni FFT. (immagine per gentile concessione di Tyson Williams)

Questa procedura non fornisce un fattore primo: è solo un passaggio intermedio che consente di calcolare un possibile fattore primo. Questo calcolo viene eseguito misurando i qubit - nota che qui siamo nel regno della possibilità, ma non dell'accuratezza, di misurare lo stato più probabile di ogni qubit - e quindi, per assicurarti che il risultato sia corretto, devi fare molti calcoli normali su un normale processore (CPU).

Tutto ciò può sembrare irrimediabilmente difficile e impraticabile. Ma la capacità dell'esponenziazione quantistica e della FFT quantistica di lavorare simultaneamente con tutte le potenze possibili di 2 per trovare il fattore primo più grande rende l'algoritmo di Shor più veloce dei calcoli convenzionali per grandi numeri, anche quando si usano routine quantistiche teoriche piuttosto lente.

L'algoritmo di Shor è un esempio lampante informatica quantisticaperché è diverso dall'elaborazione convenzionale ed è potenzialmente estremamente importante. Ma lui non è solo. Il National Institute of Standards and Technology (NIST) degli Stati Uniti mantiene un'ampia libreria di algoritmi di calcolo quantistico presso il suo Quantum Algorithm Zoo, all'indirizzo math.nist.gov/quantum/zoo/.

Questi algoritmi sono solo esercizi matematici? È ancora troppo presto per dirlo. Ma in pratica, i ricercatori hanno creato calcolatori quantistici da laboratorio con più qubit funzionanti. Queste macchine hanno suddiviso con successo 15 in fattori primi (fatto per la prima volta da IBM nel 2001), risultando in 3 e 5, e l'attuale record mondiale è 21 (fatto da un team congiunto di diversi istituti nel 2012). Quindi, per piccoli numeri, l'idea funziona. L'idoneità di questo approccio per grandi numeri potrà essere testata in futuro solo su macchine con un gran numero di qubit. E questo porta la domanda a un livello pratico.

Percorso di implementazione

Per creare dispositivi di calcolo quantistico funzionanti, è necessario passare attraverso una serie di fasi di implementazione. Dobbiamo costruire qubit funzionanti, non solo cinque, ma migliaia. Dobbiamo organizzare una struttura di porte quantistiche e l'equivalente di fili, a meno che non riusciamo a far sì che le porte agiscano direttamente sullo stato nel registro quantistico di input. Queste sono tutte attività complesse e la pianificazione per la loro soluzione è imprevedibile.

Purtroppo i problemi sono legati non tanto alla novità dei problemi quanto alle leggi della meccanica quantistica e della fisica classica. Forse il più importante e il meno familiare di questi si chiama decoerenza. Il ruolo di un qubit è di mantenere un oggetto fisico - ad esempio, uno ione, un pacchetto di fotoni o un elettrone - in posizione in modo che possiamo agire su di esso e infine misurare una quantità quantizzata come carica o spin. Perché questa quantità si comporti in modo quantistico piuttosto che classico, dobbiamo essere in grado di restringere il suo stato a una sovrapposizione di due stati di base puri, che abbiamo chiamato 0 e 1.

Ma la natura dei sistemi quantistici è tale da legarli alle cose che li circondano, aumentando notevolmente il numero di possibili stati di base. I fisici chiamano questo sfocamento degli stati puri decoerenza. Un'analogia può essere un raggio laser coerente in una fibra, disperso da disomogeneità del materiale e spalmato dalla sovrapposizione di due modalità in una luce completamente incoerente. L'obiettivo della creazione di un qubit fisico è prevenire la decoerenza il più a lungo possibile.

In pratica, ciò significa che anche un singolo qubit è un sofisticato strumento di laboratorio, possibilmente utilizzando laser o radiotrasmettitori ad alta frequenza, campi elettrici e magnetici controllati con precisione, dimensioni precise, materiali speciali e possibilmente raffreddamento criogenico. Il suo utilizzo è, infatti, una complessa procedura sperimentale. Anche con tutti questi sforzi, oggi questo "il più a lungo possibile" si misura in decine di microsecondi. Pertanto, hai pochissimo tempo per eseguire il calcolo quantistico prima che i tuoi qubit perdano la loro consistenza. Cioè, prima che le informazioni scompaiano.

Oggi, queste restrizioni precludono la possibilità di grandi registri quantistici o di eseguire calcoli che richiedono più di pochi microsecondi. Tuttavia, la ricerca è attualmente in corso nella microelettronica per creare array molto più grandi di qubit e porte quantistiche.

Tuttavia, questo lavoro in sé è alquanto incoerente, perché non c'è ancora certezza su quale fenomeno fisico utilizzare per memorizzare gli stati quantistici. Esistono progetti di qubit che quantizzano la polarizzazione dei fotoni, la carica degli elettroni catturati dai punti quantici, lo spin netto degli ioni super raffreddati in una trappola, la carica in un dispositivo chiamato transmon e alcuni altri approcci.

Il tipo di qubit che scegli determinerà naturalmente l'implementazione delle porte quantistiche. Ad esempio, è possibile utilizzare l'interazione di impulsi radio con spin interni nelle molecole nella trappola o l'interazione di divisori di fascio con modalità fotoniche nelle guide d'onda. È ovvio che l'essenza della questione risiede profondamente nel campo della fisica sperimentale. E, come detto, l'implementazione di qubit o porte quantistiche richiede l'utilizzo di un gran numero di apparecchiature diverse, dalla logica digitale ai laser o radiotrasmettitori, antenne e refrigeratori criogenici.

L'implementazione di un qubit dipende anche da come viene misurato lo stato del qubit. Potrebbe essere necessario un fotometro o un bolometro supersensibile, un ponte di resistenza o qualche altro dispositivo incredibilmente sensibile per misurare i qubit e riportare lo stato di sovrapposizione alla linea di base. Inoltre, questo processo di misurazione dello stato di un qubit presenta un altro problema non familiare al calcolo tradizionale: ottenere la risposta sbagliata.

Dubbio

Esistono due tipi principali di problemi con l'estrazione dello stato di base da un qubit. Primo, stai misurando una sovrapposizione quantistica, non una quantità classica. Supponendo che il qubit rimanga coerente, otterrai l'uno o l'altro degli stati base, ma non puoi essere sicuro in anticipo quale otterrai: puoi solo essere sicuro che la probabilità di ottenere un certo stato sarà un quadrato (modulo - aggiunto dal traduttore) il coefficiente di questo stato nella sovrapposizione. Se si misura cento volte un qubit esattamente nello stesso stato, si ottiene una distribuzione di zeri e uno che converge ai quadrati (moduli) dei coefficienti.

Quindi non sai se la linea di base che hai misurato in qualche tentativo è davvero la più probabile. Dopo aver letto il registro di output quantistico misurando i bit, impostandoli così tutti sui loro stati di base, hai tre opzioni. Potresti dubitare di avere la risposta corretta e continuare. Puoi controllare con i calcoli tradizionali, così come l'algoritmo di Shor, per vedere se il numero che hai contato è davvero la decisione giusta... In alternativa, puoi ripetere il calcolo un gran numero di volte, in sequenza o in parallelo, e ottenere il risultato più comune. È inoltre possibile organizzare i calcoli in modo che la risposta sia una distribuzione di probabilità di base anziché un numero binario specifico. In questo caso è necessaria anche la ripetizione.

Questo è vero anche per un computer quantistico teoricamente perfetto. Ma c'è un altro problema con l'effettiva implementazione: il buon vecchio rumore classico. Anche se tutto va bene, non c'è decoerenza dei qubit e il calcolo è progettato per fornire una risposta con una probabilità molto alta, stai ancora osservando i qubit, cercando di misurare quantità fisiche molto, molto piccole. Il rumore è ancora presente. Ancora una volta, l'unica soluzione è rilevare l'errore attraverso ulteriori calcoli o eseguire il calcolo così tante volte da essere pronto ad accettare qualsiasi incertezza rimanente come risultato. Il concetto di una risposta corretta garantita è estraneo all'essenza stessa del calcolo quantistico.

Se tutto ciò non dipinge un quadro roseo del futuro dell'informatica quantistica, allora dovrebbe essere preso molto sul serio. La ricerca della scelta migliore per l'implementazione dei qubit è in corso, sebbene la risposta possa dipendere dall'algoritmo. Gli specialisti di microelettronica stanno lavorando per miniaturizzare i componenti quantistici basati su nuovi materiali e strutture che consentirebbero la creazione di array molto grandi di dispositivi di calcolo quantistico e che potrebbero essere prodotti in serie come chip nei processori tradizionali. Gli informatici sviluppano prototipi di assemblatori e compilatori in grado di trasformare un algoritmo nella disposizione di registri quantistici e porte quantistiche in una particolare tecnologia.

Ne vale la pena? Ecco un fatto. Shore ha calcolato che un umile computer ibrido, cioè quantistico più convenzionale, può decifrare il potente algoritmo di crittografia RSA più velocemente di quanto un computer convenzionale possa crittografarlo. Risultati simili sono stati ottenuti per problemi come l'ordinamento e il disfacimento di altri problemi matematici complessi simili. Quindi ci sono abbastanza promesse in questo settore perché i ricercatori mantengano il loro entusiasmo. Ma sarebbe bello vedere tutto questo mentre ancora vivo.

Richard Feynman ha osservato che alcuni processi quantistici meccanici non possono essere modellati efficacemente su un computer classico. Questa osservazione ha portato all'affermazione più generale che i processi quantistici sono più efficienti dei processi classici per l'esecuzione di calcoli. Questa ipotesi è stata confermata da Peter Shor, che ha sviluppato un algoritmo quantistico per scomporre gli interi in fattori primi in tempo polinomiale.

Nei sistemi quantistici, lo spazio di calcolo cresce in modo esponenziale con la dimensione del sistema, il che rende possibile il parallelismo esponenziale. Questo parallelismo può portare a algoritmi quantistici che sono esponenzialmente più veloci di quelli classici.

Non è stato fino alla metà degli anni '90 che la teoria dei computer quantistici e dell'informatica quantistica è stata stabilita come un nuovo campo della scienza. Apparentemente, il matematico ungherese I. von Neumann fu il primo a richiamare l'attenzione sulla possibilità di sviluppare la logica quantistica. Tuttavia, a quel tempo, non solo i computer quantistici, ma anche quelli ordinari, classici, non erano ancora stati creati. E con l'avvento di quest'ultimo, i principali sforzi degli scienziati si sono rivelati principalmente volti a trovare e sviluppare nuovi elementi per loro (transistor e quindi circuiti integrati), e non a creare dispositivi informatici fondamentalmente diversi.

Negli anni '60, il fisico americano R. Landauer cercò di attirare l'attenzione sul fatto che il calcolo è sempre una sorta di processo fisico, il che significa che è impossibile comprendere i limiti delle nostre capacità computazionali senza specificare a quale implementazione fisica corrispondono. Sfortunatamente, a quel tempo, tra gli scienziati, la visione prevalente del calcolo come una sorta di procedura logica astratta, che dovrebbe essere studiata dai matematici, non dai fisici.

Con la proliferazione dei computer, gli scienziati quantistici sono giunti alla conclusione che era praticamente impossibile calcolare direttamente lo stato di un sistema in evoluzione costituito da poche dozzine di particelle interagenti, ad esempio la molecola di metano CH 4. Ciò è spiegato dal fatto che per una descrizione completa di un sistema complesso, è necessario mantenere nella memoria del computer un numero di variabili esponenzialmente grande (per il numero di particelle), le cosiddette ampiezze quantistiche. Si è creata una situazione paradossale: conoscendo l'equazione dell'evoluzione, conoscendo con sufficiente precisione tutti i potenziali di interazione delle particelle tra loro e lo stato iniziale del sistema, è praticamente impossibile calcolarne il futuro, anche se il sistema consiste di soli 30 elettroni in un potenziale pozzo, e c'è un supercomputer con memoria ad accesso casuale , il cui numero di bit è uguale al numero di atomi nella regione visibile dell'Universo. Allo stesso tempo, per studiare la dinamica di un tale sistema, si può semplicemente impostare un esperimento con 30 elettroni, ponendoli in un dato potenziale e stato iniziale. Questo, in particolare, è stato disegnato dal matematico russo Yu I. Manin, che ha sottolineato nel 1980 la necessità di sviluppare una teoria dei dispositivi di calcolo quantistico. Negli anni '80 lo stesso problema fu studiato dal fisico americano P. Benev, che dimostrò chiaramente che un sistema quantistico può eseguire calcoli, così come dallo scienziato inglese D. Deutsch, che teoricamente sviluppò un computer quantistico universale superiore all'analogo classico.

R. Feynman ha attirato grande attenzione sul problema dello sviluppo di computer quantistici. Grazie al suo autorevole appeal, il numero di specialisti che hanno prestato attenzione all'informatica quantistica è aumentato molte volte.

Tuttavia per molto tempo non è stato chiaro se l'ipotetica potenza di calcolo di un computer quantistico potesse essere utilizzata per velocizzare la risoluzione di problemi pratici. Nel 1994, il matematico americano P. Shore ha proposto un algoritmo quantistico che consente la fattorizzazione rapida di grandi numeri. Rispetto ai migliori metodi classici conosciuti fino ad oggi, l'algoritmo quantistico di Shor fornisce un'accelerazione multipla dei calcoli e più lungo è il numero fattorizzato, maggiore è il guadagno di velocità. Nel caso dell'algoritmo classico, un aumento del numero fattorizzato porta ad un aumento esponenziale delle risorse richieste. Ad esempio, la scomposizione in fattori di un numero di 500 cifre richiede 100 milioni di volte più iterazioni di un numero di 250 cifre. Per l'algoritmo di Shor, la quantità di risorse richieste cresce solo in modo polinomiale: un numero di 500 cifre richiede solo 8 volte più passaggi di un numero di 250 cifre.

Si scopre che usando le leggi della meccanica quantistica, è possibile costruire computer per i quali il problema della fattorizzazione (e molti altri!) Non sarà difficile. Si stima che un computer quantistico con solo circa 10.000 bit quantistici di memoria sia in grado di scomporre un numero di 1000 cifre in fattori primi in poche ore! L'algoritmo di fattorizzazione rapida è, ad esempio, di grande interesse pratico per vari servizi speciali che hanno accumulato banche di messaggi non crittografati.

Nel 1997 L. Grover ha proposto un algoritmo di ricerca veloce quantistica in un database non ordinato. (Un esempio di tale database è un elenco telefonico, in cui i nomi degli abbonati sono disposti non in ordine alfabetico, ma in modo arbitrario.) Il compito di cercare, scegliere l'elemento ottimale tra numerose opzioni è molto comune nei problemi economici, militari, di ingegneria e nei giochi per computer. L'algoritmo di Grover consente non solo di accelerare il processo di ricerca, ma anche di raddoppiare approssimativamente il numero di parametri presi in considerazione nella scelta dell'ottimo.

La vera creazione di computer quantistici è ostacolata da un grave problema: errori o interferenze. Il fatto è che lo stesso livello di rumore rovina il processo di calcolo quantistico in modo molto più intenso rispetto al calcolo classico. I modi per risolvere questo problema sono stati delineati nel 1995 da P. Shor, che ha sviluppato uno schema per codificare gli stati quantistici e correggere gli errori in essi.

Il tempo necessario per eseguire determinati calcoli può essere ridotto utilizzando processori paralleli. Per ottenere una diminuzione esponenziale del tempo è necessario un aumento esponenziale del numero di processori, e quindi della quantità di spazio fisico. In un sistema quantistico, per una diminuzione esponenziale nel tempo, è richiesto solo un aumento lineare del volume dello spazio fisico richiesto. Questo fenomeno è direttamente correlato al parallelismo quantistico (Deutsch e Josha 1992).

C'è un'altra caratteristica importante. Mentre il sistema quantistico esegue calcoli, l'accesso ai risultati è limitato. Il processo di accesso ai risultati è un processo di misurazione che perturba lo stato quantistico distorcendolo. Può sembrare che la situazione qui sia persino peggiore rispetto ai calcoli classici. Si scopre che possiamo contare solo il risultato di uno dei processi paralleli e, poiché la misurazione è probabilistica, non possiamo nemmeno scegliere il risultato di quale processo riceveremo.

Ma negli ultimi anni, le persone hanno scoperto modi non standard per risolvere abilmente il problema di misurazione al fine di sfruttare il parallelismo quantistico. Manipolazioni di questo tipo non hanno analoghi nella teoria classica e richiedono l'uso di tecniche di programmazione non convenzionali. Una di queste tecniche consiste nel manipolare lo stato quantistico in modo che la proprietà comune di tutti i valori risultanti, come la simmetria o il periodo di una funzione, possa essere letta. Una tecnica simile viene utilizzata nell'algoritmo di fattorizzazione di Shor. In un altro approccio, gli stati quantistici vengono trasformati in modo da aumentare la probabilità di leggere il risultato del calcolo che ci interessa. Questa tecnica viene utilizzata nell'algoritmo di ricerca di Grover

Il contenuto del concetto di "parallelismo quantistico" può essere divulgato come segue: "I dati nel processo di calcolo sono informazioni quantistiche, che alla fine del processo vengono convertite in informazioni classiche misurando lo stato finale del registro quantistico. Il guadagno negli algoritmi quantistici è ottenuto grazie al fatto che quando viene applicata una singola operazione quantistica, un gran numero di coefficienti di sovrapposizione di stati quantistici, che in forma virtuale contengono informazioni classiche, vengono trasformati simultaneamente ".

Entanglement quantistico, chiamato anche "sovrapposizione quantistica", di solito significa: "Immagina un atomo che potrebbe decadere radioattivamente entro un certo periodo di tempo. Oppure no. Possiamo aspettarci che questo atomo ne abbia solo due stati possibili: "Decadimento" e "non decadimento", / ... / ma nella meccanica quantistica, un atomo può avere un certo stato unificato - "decadimento - non decadimento", cioè né l'uno né l'altro, ma come se fosse tra. Questo stato è chiamato "sovrapposizione".

Le caratteristiche di base dei computer quantistici in teoria consentono loro di superare alcune delle limitazioni che sorgono quando i computer classici funzionano.

Teoria

Qubits

L'idea del calcolo quantistico, espressa per la prima volta da Yu.I. Manin e R. Feynman, è che un sistema quantistico di L gli elementi quantistici a due livelli (qubit) hanno 2 L di stati linearmente indipendenti, e quindi, a causa del principio di sovrapposizione quantistica, 2 L -spazio degli stati di Hilbert -dimensionale. Un'operazione nel calcolo quantistico corrisponde a una rotazione in questo spazio. Quindi, un dispositivo di calcolo quantistico di dimensioni L un qubit può essere eseguito in parallelo 2 L operazioni.

Supponiamo che ci sia un qubit. In questo caso, dopo la misurazione, nella cosiddetta forma classica, il risultato sarà 0 o 1. In realtà, un qubit è un oggetto quantistico e quindi, a causa del principio di indeterminazione, possono esserci sia 0 che 1 con una certa probabilità. Se un qubit è 0 (o 1) con probabilità del 100%, il suo stato è indicato dal simbolo | 0\u003e (o | 1\u003e) - nella notazione di Dirac. | 0\u003e e | 1\u003e sono linee di base. Nel caso generale, lo stato quantistico di un qubit è compreso tra quelli di base ed è scritto nella forma, dove | un| ² e | b| ² - probabilità di misurare rispettivamente 0 o 1; ; | un|² + | b| ² \u003d 1. Inoltre, subito dopo la misurazione, il qubit passa allo stato quantistico di base, simile al risultato classico.

C'è un qubit in uno stato quantistico In questo caso, la probabilità da ottenere durante la misurazione In questo caso, durante la misurazione, abbiamo ottenuto 0 con il 64% di probabilità. Quindi il qubit salta in un nuovo stato quantistico 1 * | 0\u003e + 0 * | 1\u003e \u003d | 0\u003e, cioè, la prossima volta che misuriamo questo qubit, otterremo 0 con il 100% di probabilità. Ciò è dovuto al fatto che il vettore di stato di Dirac non dipende dal tempo, cioè è scomposto nella somma dei vettori di stati base con coefficienti indipendenti dal tempo.

Diamo due esempi dalla meccanica quantistica per la spiegazione: 1) un fotone è in uno stato di sovrapposizione di due polarizzazioni; la misura una volta per tutte fa collassare lo stato del fotone in uno con una certa polarizzazione; 2) l'atomo radioattivo ha una certa emivita; la misurazione può rivelare che non si è ancora disintegrato, ma ciò non significa che non si disintegrerà mai.

Passiamo a un sistema di due qubit. La misurazione di ciascuno di essi può dare 0 o 1. Pertanto, il sistema ha 4 stati classici: 00, 01, 10 e 11. Stati quantistici di base simili: | 00\u003e, | 01\u003e, | 10\u003e e | 11\u003e. E infine, lo stato quantistico generale del sistema è. Adesso | un| ² - la probabilità di misurare 00, ecc. Notare che | un|²+| b|²+| c|²+| d| ² \u003d 1 come probabilità totale.

In generale, i sistemi da L ha 2 qubit L stati classici (00000 ... (L-zero), ... 00001 (L-digit), ..., 11111 ... (L-one)), ciascuno dei quali può essere misurato con probabilità dello 0-100%.

Pertanto, un'operazione su un gruppo di qubit influenza tutti i valori che può assumere, a differenza del bit classico. Ciò fornisce un parallelismo computazionale senza precedenti.

Calcolo

Uno schema di calcolo semplificato su un computer quantistico si presenta così: viene preso un sistema di qubit, su cui viene registrato lo stato iniziale. Quindi lo stato del sistema o dei suoi sottosistemi viene modificato mediante operazioni quantistiche di base. Alla fine, il valore viene misurato e questo è il risultato del computer.

Risulta che due operazioni di base sono sufficienti per costruire qualsiasi calcolo. Il sistema quantistico fornisce un risultato corretto solo con una certa probabilità. Ma a causa di un piccolo aumento delle operazioni nell'algoritmo, la probabilità di ottenere il risultato corretto può essere avvicinata all'unità quanto desiderato.

Le operazioni quantistiche di base possono essere utilizzate per simulare il funzionamento delle normali porte logiche di cui sono fatti i normali computer. Pertanto, un computer quantistico risolverà qualsiasi problema risolto ora e quasi nello stesso tempo. Di conseguenza, il nuovo schema di calcolo non sarà più debole di quello attuale.

Perché un computer quantistico è migliore di uno classico? La maggior parte dei computer moderni funziona allo stesso modo: n bit di memoria memorizzano lo stato e ogni volta che l'orologio viene modificato dal processore. Nel caso quantistico, un sistema di n qubit è in uno stato che è una sovrapposizione di tutti gli stati di base, quindi il cambiamento nel sistema riguarda tutti 2 n stati di base allo stesso tempo. In teoria, il nuovo schema può funzionare molto (esponenzialmente) più velocemente di quello classico. In pratica, l'algoritmo di ricerca del database (quantistico) di Grover mostra un guadagno di potenza quadratico rispetto agli algoritmi classici. Finora non esistono in natura.

Algoritmi

È stato dimostrato che non tutti gli algoritmi sono in grado di eseguire una "accelerazione quantistica".

Teletrasporto quantistico

L'algoritmo di teletrasporto implementa il trasferimento esatto dello stato di un qubit (o sistema) a un altro. Lo schema più semplice utilizza 4 qubit: una sorgente, un ricevitore e due ausiliari. Si noti che come risultato dell'operazione dell'algoritmo, lo stato iniziale della sorgente verrà distrutto: questo è un esempio dell'azione di un generale il principio dell'impossibilità di clonazione - è impossibile creare una copia esatta di uno stato quantistico senza distruggere l'originale. In effetti, è abbastanza facile creare gli stessi stati sui qubit. Ad esempio, dopo aver misurato 3 qubit, trasferiremo ciascuno di essi negli stati base (0 o 1) e almeno due di essi coincideranno. Impossibile copiare arbitrario stato, e il teletrasporto è un sostituto per questa operazione.

Il teletrasporto consente di trasferire lo stato quantistico del sistema utilizzando i canali di comunicazione classici convenzionali. Pertanto, è possibile, in particolare, ottenere uno stato vincolato di un sistema costituito da sottosistemi remoti su una lunga distanza.

Applicazioni dei computer quantistici

Specificità dell'applicazione

Potrebbe sembrare che un computer quantistico sia una specie di macchina informatica analogica. Ma non è così: in sostanza si tratta di un dispositivo digitale, ma di natura analogica.

I principali problemi associati alla creazione e all'uso dei computer quantistici:

è necessario garantire un'elevata precisione delle misurazioni;
influenze esterne possono distruggere il sistema quantistico o introdurvi distorsioni.

Applicazioni di crittografia

Grazie all'enorme velocità della scomposizione in fattori primi, un computer quantistico può decrittografare i messaggi crittografati utilizzando il popolare algoritmo crittografico asimmetrico, aprendo nuove possibilità nel campo della trasmissione dei messaggi. Prototipi di sistemi di questo tipo sono in fase di sviluppo.

Implementazione

La società canadese D-Wave ha annunciato nel febbraio 2007 di aver creato un campione di un computer quantistico composto da 16 qubit (il dispositivo si chiamava Orion). Tuttavia, le informazioni su questo dispositivo non soddisfacevano i severi requisiti di accurate relazioni scientifiche; la notizia non ha ricevuto riconoscimenti scientifici. Inoltre, gli ulteriori piani dell'azienda (per creare un computer a 1024 qubit nel prossimo futuro) hanno suscitato scetticismo tra i membri della comunità di esperti.

Nel novembre 2007, la stessa azienda D-Wave ha dimostrato il lavoro di un campione di un computer a 28 qubit online in una conferenza sui supercomputer. La dimostrazione ha anche generato un certo scetticismo.

Nel dicembre 2008 la società ha organizzato il progetto Distributed Computing [email protected](UNdiabatico QUantum UNlgorithms), che testa algoritmi che ottimizzano i calcoli su computer quantistici superconduttori adiabatici D-Wave.

Guarda anche

Appunti

Letteratura

Kilin S.Ya. Quanta e informazione / Progressi in ottica. - 2001. - Vol. 42. - P. 1-90.
Kilin S. Ya. Informazioni quantistiche / progressi nelle scienze fisiche. - 1999. - T. 169. - C. 507-527.
Pro e contro del quantum computing. Ed. Sadovnichy V.A.
Computer quantistico e calcolo quantistico. Ed. Sadovnichy V.A.
Valiev K.A., Kokin A.A. Computer quantistici: speranze e realtà. Mosca, Izhevsk: dinamiche regolari e caotiche, 2004.320 p. ISBN 5-93972-024-2

Collegamenti

Computer quantistico e sua base elementare semiconduttrice
Kitaev, A., Shen, A., Sluggish, M. Informatica classica e quantistica
QWiki e Quantiki - Risorse Wiki per l'informatica quantistica
Il linguaggio di programmazione QCL per computer quantistici
Corso "Problemi moderni di informatica teorica" \u200b\u200b(lezioni sul calcolo quantistico: introduzione, codifica superdensa, teletrasporto quantistico, algoritmi di Simon e Shor)
InFuture.ru: Il futuro dei computer quantistici è nell'informatica ternaria
Valiev K. A. "Computer quantistici e calcolo quantistico" Phys. 175 3 (2005)

Wikimedia Foundation. 2010.

Effetto dimensione quantistica
Effetti dimensionali quantistici

Scopri cos'è "Quantum computing" in altri dizionari:

Computer quantistici - 3 qubit di un registro quantistico contro 3 bit di un computer quantistico convenzionale è un ipotetico dispositivo di calcolo che, eseguendo algoritmi quantistici, utilizza in modo significativo effetti quantomeccanici, come ... ... Wikipedia

TEORIE QUANTISTICHE TOPOLOGICHE DEI CAMPI - meccanica quantistica. o teorie quantistiche dei campi, tutte funzioni di correlazione in cui non dipendono dalla scelta di coordinate e metriche sia nello spazio di tempo che in altri spazi coinvolti nella definizione della teoria. Questo ti permette di usare ... ... Enciclopedia fisica

Computer quantistico - 3 qubit di un registro quantistico contro 3 bit di un dispositivo di calcolo quantistico convenzionale basato sulla meccanica quantistica. Un computer quantistico è fondamentalmente diverso dai computer classici basati su ... Wikipedia

L. Fedichkin, PhD in Fisica e Matematica (Istituto di Fisica e Tecnologia dell'Accademia Russa delle Scienze.

Usando le leggi della meccanica quantistica, puoi creare un tipo di computer fondamentalmente nuovo che ti permetterà di risolvere alcuni problemi che sono inaccessibili anche ai più potenti supercomputer moderni. La velocità di molti calcoli complessi salirà alle stelle; i messaggi inviati sulle linee di comunicazione quantistica non possono essere né intercettati né copiati. I prototipi di questi computer quantistici del futuro sono già stati creati.

Matematico e fisico americano di origine ungherese Johann von Neumann (1903-1957).

Il fisico teorico americano Richard Phillips Feynman (1918-1988).

Il matematico americano Peter Shor, esperto nel campo dell'informatica quantistica. Proposta di un algoritmo quantistico per la fattorizzazione rapida di grandi numeri.

Quantum bit, o qubit. Gli stati e corrispondono, ad esempio, alla direzione dello spin del nucleo atomico verso l'alto o verso il basso.

Il registro quantistico è una stringa di bit quantistici. Le porte quantistiche a uno o due qubit eseguono operazioni logiche sui qubit.

INTRODUZIONE O POCO SULLA PROTEZIONE DELLE INFORMAZIONI

Quale software pensi abbia il maggior numero di licenze vendute al mondo? Non oserò insistere sul fatto di conoscere la risposta corretta, ma sicuramente ne conosco una sbagliata: questa nonqualsiasi versione di Microsoft Windows. Il sistema operativo più comune è superato da un modesto prodotto di RSA Data Security, Inc. - un programma che implementa l'algoritmo di crittografia a chiave pubblica RSA, dal nome dei suoi autori: i matematici americani Rivest, Shamir e Adelman.

Il fatto è che RSA è integrato nella maggior parte dei sistemi operativi venduti, così come in molte altre applicazioni utilizzate in vari dispositivi, dalle smart card ai telefoni cellulari. In particolare, è disponibile anche in Microsoft Windows, il che significa che è più ampio di questo popolare sistema operativo. Per trovare tracce di RSA, ad esempio, nel browser Internet Explorer (un programma per la visualizzazione di pagine www su Internet), è sufficiente aprire il menu Aiuto, entrare nel sottomenu Informazioni su Internet Explorer e visualizzare un elenco di prodotti di altre società. Un altro browser comune, Netscape Navigator, utilizza anche l'algoritmo RSA. In generale, è difficile trovare una nota azienda high-tech che non acquisterà una licenza per questo programma. Oggi RSA Data Security, Inc. ha già venduto oltre 450 milioni (!) di licenze.

Perché RSA è così importante?

Immagina di dover scambiare rapidamente un messaggio con una persona lontana. Grazie allo sviluppo di Internet, un tale scambio è diventato disponibile per la maggior parte delle persone oggi: è sufficiente disporre di un computer con un modem o una scheda di rete. Naturalmente, quando si scambiano informazioni sulla rete, si desidera mantenere segreti i propri messaggi agli estranei. Tuttavia, è impossibile proteggere completamente una linea di comunicazione estesa dalle intercettazioni. Ciò significa che quando si inviano messaggi, devono essere crittografati e durante la ricezione devono essere decrittografati. Ma come potete concordare tu e il tuo interlocutore quale chiave utilizzerai? Se invii la chiave al cifrario sulla stessa riga, un malintenzionato che ascolta di nascosto può facilmente intercettarlo. È possibile, ovviamente, trasmettere la chiave tramite un'altra linea di comunicazione, ad esempio, inviarla tramite telegramma. Ma questo metodo è solitamente scomodo e, inoltre, non sempre affidabile: è possibile intercettare anche un'altra linea. È positivo se tu e il tuo destinatario sapevate in anticipo che avreste scambiato le crittografie e quindi trasferite le chiavi a vicenda in anticipo. Ma cosa succede se, ad esempio, si desidera inviare un'offerta riservata a un potenziale partner commerciale o acquistare un prodotto che ti piace con una carta di credito in un nuovo negozio online?

Negli anni '70 furono proposti sistemi di crittografia per risolvere questo problema, utilizzando due tipi di chiavi per lo stesso messaggio: aperta (che non richiede segretezza) e chiusa (altamente segreta). La chiave pubblica viene utilizzata per crittografare il messaggio e la chiave privata viene utilizzata per decrittografarlo. Invii al tuo corrispondente una chiave pubblica e lui crittografa il suo messaggio con essa. Tutto ciò che un utente malintenzionato che intercetta la chiave pubblica può fare è crittografare la sua lettera e inoltrarla a qualcuno. Ma non sarà in grado di decifrare la corrispondenza. Conoscendo la chiave privata (inizialmente è memorizzata con te), puoi leggere facilmente il messaggio a te indirizzato. Per crittografare i messaggi di risposta, utilizzerai la chiave pubblica inviata dal tuo corrispondente (e lui tiene per sé la chiave privata corrispondente).

Questo è esattamente il tipo di schema crittografico utilizzato in RSA, il metodo di crittografia a chiave pubblica più comune. Inoltre, per creare una coppia di chiavi pubbliche e private, viene utilizzata la seguente importante ipotesi. Se ci sono due grandi (che richiedono più di cento cifre decimali per la loro notazione) semplice numeri M e K, quindi trovare il loro prodotto N \u003d MK non sarà difficile (per questo non è nemmeno necessario avere un computer: sufficientemente preciso e uomo paziente può moltiplicare tali numeri con carta e penna). Ma per risolvere il problema inverso, cioè conoscere un grande numero N, scomporlo in fattori primi M e K (i cosiddetti problema di fattorizzazione) - quasi impossibile! È con questo problema che un malintenzionato che decide di "crackare" l'algoritmo RSA e leggere le informazioni crittografate con esso si troverà ad affrontare: per scoprire la chiave privata, conoscendo quella pubblica, dovrai calcolare M o K.

Per verificare la validità dell'ipotesi sulla complessità pratica della fattorizzazione di grandi numeri, erano e sono tuttora tenuti concorsi speciali. La scomposizione di solo un numero di 155 cifre (512 bit) è considerata un record. I calcoli sono stati eseguiti in parallelo su molti computer per sette mesi nel 1999. Se questa attività fosse eseguita su un moderno personal computer, ci vorrebbero circa 35 anni di tempo per il computer! I calcoli mostrano che utilizzando anche migliaia di moderne workstation e i migliori algoritmi computazionali conosciuti oggi, un numero di 250 cifre può essere scomposto in circa 800 mila anni e un numero di 1000 cifre - in 10 25 (!) Anni. (Per confronto, l'età dell'universo è ~ 10-10 anni.)

Pertanto, algoritmi crittografici come RSA, operanti con chiavi sufficientemente lunghe, sono stati considerati completamente affidabili e sono stati utilizzati in molte applicazioni. E tutto andava bene fino ad allora ... fino all'arrivo dei computer quantistici.

COME TUTTO È INIZIATO?

Non è stato fino alla metà degli anni '90 che la teoria dei computer quantistici e dell'informatica quantistica è stata stabilita come un nuovo campo della scienza. Come spesso accade con le grandi idee, è difficile scegliere uno scopritore. Apparentemente, il matematico ungherese I. von Neumann fu il primo a richiamare l'attenzione sulla possibilità di sviluppare la logica quantistica. Tuttavia, a quel tempo, non solo i computer quantistici, ma anche quelli ordinari, classici, non erano ancora stati creati. E con l'avvento di quest'ultimo, i principali sforzi degli scienziati si sono rivelati diretti principalmente verso la ricerca e lo sviluppo di nuovi elementi per loro (transistor e quindi circuiti integrati), e non verso la creazione di dispositivi di elaborazione fondamentalmente diversi.

Negli anni '60, il fisico americano R. Landauer, che lavorava presso la società IBM, cercò di attirare l'attenzione del mondo scientifico sul fatto che il calcolo è sempre una sorta di processo fisico, il che significa che è impossibile comprendere i limiti delle nostre capacità computazionali senza specificare quale implementazione fisica siano. corrispondere. Sfortunatamente, a quel tempo, tra gli scienziati, la visione prevalente del calcolo come una sorta di procedura logica astratta, che dovrebbe essere studiata dai matematici, non dai fisici.

Con la proliferazione dei computer, gli scienziati quantistici giunsero alla conclusione che era praticamente impossibile calcolare direttamente lo stato di un sistema in evoluzione costituito da poche dozzine di particelle interagenti, come una molecola di metano (CH 4). Ciò è spiegato dal fatto che per una descrizione completa di un sistema complesso, è necessario mantenere nella memoria del computer un numero di variabili esponenzialmente grande (per il numero di particelle), le cosiddette ampiezze quantistiche. Si è creata una situazione paradossale: conoscendo l'equazione dell'evoluzione, conoscendo con sufficiente accuratezza tutti i potenziali di interazione delle particelle tra loro e lo stato iniziale del sistema, è praticamente impossibile calcolarne il futuro, anche se il sistema consiste di soli 30 elettroni in un pozzo potenziale, e c'è un supercomputer con memoria ad accesso casuale , il cui numero di bit è uguale al numero di atomi nella regione visibile dell'Universo (!). E allo stesso tempo, per studiare la dinamica di un tale sistema, puoi semplicemente impostare un esperimento con 30 elettroni, posizionandoli in un dato potenziale e stato iniziale. Questo, in particolare, è stato disegnato dal matematico russo Yu I. Manin, che ha sottolineato nel 1980 la necessità di sviluppare una teoria dei dispositivi di calcolo quantistico. Negli anni '80 lo stesso problema fu studiato dal fisico americano P. Benev, che dimostrò chiaramente che un sistema quantistico può eseguire calcoli, così come dallo scienziato inglese D. Deutsch, che teoricamente sviluppò un computer quantistico universale superiore all'analogo classico.

Il premio Nobel per la fisica R. Feynman, ben noto ai lettori abituali di Science and Life, ha attirato molta attenzione sul problema dello sviluppo dei computer quantistici. Grazie al suo autorevole appeal, il numero di specialisti che hanno prestato attenzione all'informatica quantistica è aumentato molte volte.

Tuttavia per molto tempo non è stato chiaro se l'ipotetica potenza di calcolo di un computer quantistico potesse essere utilizzata per velocizzare la risoluzione di problemi pratici. Ma nel 1994, P. Shor, un matematico americano e impiegato di Lucent Technologies (USA), sbalordì il mondo scientifico proponendo un algoritmo quantistico che consente una rapida fattorizzazione di grandi numeri (l'importanza di questo problema era già stata discussa nell'introduzione). Rispetto ai migliori metodi classici conosciuti fino ad oggi, l'algoritmo quantistico di Shor fornisce un'accelerazione multipla dei calcoli e più lungo è il numero fattorizzato, maggiore è il guadagno di velocità. L'algoritmo di fattorizzazione rapida è di grande interesse pratico per vari servizi speciali che hanno accumulato banche di messaggi non crittografati.

Nel 1996, il collega di Shor alla Lucent Technologies, L. Grover, ha proposto un algoritmo di ricerca veloce quantistica in un database non ordinato. (Un esempio di tale database è un elenco telefonico, in cui i nomi degli abbonati sono disposti non in ordine alfabetico, ma in modo arbitrario.) Il compito di cercare, scegliere l'elemento ottimale tra numerose opzioni è molto comune nei problemi economici, militari, di ingegneria e nei giochi per computer. L'algoritmo di Grover consente non solo di accelerare il processo di ricerca, ma anche di raddoppiare approssimativamente il numero di parametri presi in considerazione nella scelta dell'ottimo.

La vera creazione di computer quantistici è stata ostacolata essenzialmente dall'unico problema serio: errori o interferenze. Il fatto è che lo stesso livello di rumore rovina il processo di calcolo quantistico in modo molto più intenso rispetto al calcolo classico. I modi per risolvere questo problema sono stati delineati nel 1995 da P. Shor, che ha sviluppato uno schema per codificare gli stati quantistici e correggere gli errori in essi. Sfortunatamente, l'argomento della correzione degli errori nei computer quantistici è tanto importante quanto difficile da trattare in questo articolo.

DISPOSITIVO DI UN COMPUTER QUANTISTICO

Prima di raccontare come funziona un computer quantistico, ricordiamo le caratteristiche principali dei sistemi quantistici (vedi anche "Science and Life" n. 8, 1998; n. 12, 2000).

Per comprendere le leggi del mondo quantistico, non si dovrebbe fare affidamento direttamente sull'esperienza quotidiana. Nel solito modo (nel senso quotidiano), le particelle quantistiche si comportano solo se le "sbirciamo" costantemente o, più strettamente parlando, misuriamo costantemente lo stato in cui si trovano. Ma non appena "voltiamo le spalle" (smettiamo di osservare), le particelle quantistiche passano immediatamente da uno stato completamente definito a diverse ipostasi diverse. Cioè, un elettrone (o qualsiasi altro oggetto quantistico) sarà parzialmente posizionato in un punto, parzialmente in un altro, parzialmente in un terzo, ecc. Questo non significa che sia diviso in fette, come un'arancia. Quindi sarebbe possibile isolare in modo affidabile una parte dell'elettrone e misurare la sua carica o massa. Ma l'esperienza mostra che dopo la misurazione l'elettrone risulta sempre "sano e salvo" in un unico punto, nonostante il fatto che prima fosse riuscito a visitare quasi ovunque contemporaneamente. Viene chiamato un tale stato di un elettrone, quando si trova in più punti nello spazio contemporaneamente sovrapposizione di stati quantistici e sono solitamente descritte dalla funzione d'onda introdotta nel 1926 dal fisico tedesco E. Schrödinger. La grandezza del valore della funzione d'onda in qualsiasi punto, al quadrato, determina la probabilità di trovare una particella in questo punto in un dato momento. Dopo aver misurato la posizione della particella, la sua funzione d'onda si contrae (collassa) fino al punto in cui è stata rilevata la particella, quindi inizia a diffondersi di nuovo. La proprietà delle particelle quantistiche di essere simultaneamente in molti stati, chiamata parallelismo quantistico , utilizzato con successo nel calcolo quantistico.

Bit quantistico

La cella principale di un computer quantistico è un bit quantistico o, in breve, qubit(q-bit). È una particella quantistica con due stati di base, indicati con 0 e 1 o, come è consuetudine nella meccanica quantistica, e. Due valori di un qubit possono corrispondere, ad esempio, gli stati fondamentali ed eccitati di un atomo, direzioni su e giù dello spin di un nucleo atomico, direzione della corrente in un anello superconduttore, due possibili posizioni di un elettrone in un semiconduttore, ecc.

Registro quantistico

Il registro quantistico funziona quasi come quello classico. Questa è una stringa di bit quantistici, su cui è possibile eseguire operazioni logiche a uno e due bit (simile all'uso di NOT, 2AND-NOT, ecc. In un registro classico).

Gli stati di base del registro quantistico formato da L qubit includono, come in quello classico, tutte le possibili sequenze di zeri e uno di lunghezza L. Possono esserci 2 L diverse combinazioni in totale. Possono essere considerati come scrivere numeri in forma binaria da 0 a 2 L -1 e indicati. Tuttavia, questi stati di base non esauriscono tutti i possibili valori del registro quantistico (a differenza di quello classico), poiché esistono anche stati di sovrapposizione specificati da ampiezze complesse legate dalla condizione di normalizzazione. La maggior parte dei possibili valori del registro quantistico (ad eccezione di quelli di base) semplicemente non hanno un analogo classico. Gli stati del registro classico sono solo un'ombra pietosa della ricchezza di stati in un computer quantistico.

Immagina che un'influenza esterna venga eseguita sul registro, ad esempio, gli impulsi elettrici vengono applicati a una parte dello spazio o vengono diretti i raggi laser. Se è un registro classico, un impulso, che può essere visto come un'operazione di calcolo, cambierà le variabili L. Se si tratta di un registro quantistico, lo stesso impulso può trasformarsi simultaneamente in variabili. Pertanto, un registro quantistico è, in linea di principio, in grado di elaborare le informazioni una volta più velocemente della sua controparte classica. Da ciò è immediatamente chiaro che i piccoli registri quantistici (L.<20) могут служить лишь для демонстрации отдельных узлов и принципов работы квантового компьютера, но не принесут большой практической пользы, так как не сумеют обогнать современные ЭВМ, а стоить будут заведомо дороже. В действительности квантовое ускорение обычно значительно меньше, чем приведенная грубая оценка сверху (это связано со сложностью получения большого количества амплитуд и считывания результата), поэтому практически полезный квантовый компьютер должен содержать тысячи кубитов. Но, с другой стороны, понятно, что для достижения действительного ускорения вычислений нет необходимости собирать миллионы квантовых битов. Компьютер с памятью, измеряемой всего лишь в килокубитах, будет в некоторых задачах несоизмеримо быстрее, чем классический суперкомпьютер с терабайтами памяти.

Va notato, tuttavia, che esiste una classe di problemi per i quali gli algoritmi quantistici non forniscono un'accelerazione significativa rispetto a quelli classici. Uno dei primi a dimostrarlo è stato il matematico russo Yu. Ozhigov, che ha costruito una serie di esempi di algoritmi che in linea di principio non possono essere accelerati da un singolo orologio su un computer quantistico.

Tuttavia, non c'è dubbio che i computer che funzionano secondo le leggi della meccanica quantistica sono una tappa nuova e decisiva nell'evoluzione dei sistemi informatici. Resta solo da costruirli.

I COMPUTER QUANTICI OGGI

Oggi esistono prototipi di computer quantistici. È vero, finora è stato sperimentalmente possibile raccogliere solo piccoli registri costituiti solo da pochi bit quantistici. Ad esempio, recentemente un gruppo guidato dal fisico americano I. Chang (IBM) ha annunciato l'assemblaggio di un computer quantistico a 5 bit. Questo è senza dubbio un grande successo. Sfortunatamente, i sistemi quantistici esistenti non sono ancora in grado di fornire calcoli affidabili, poiché non sono sufficientemente controllabili o molto sensibili al rumore. Tuttavia, non ci sono restrizioni fisiche alla costruzione di un computer quantistico efficace, è solo necessario superare le difficoltà tecnologiche.

Sono disponibili diverse idee e suggerimenti su come creare bit quantistici affidabili e facilmente controllabili.

I. Chang sviluppa l'idea di utilizzare gli spin dei nuclei di alcune molecole organiche come qubit.

Ricercatore russo M. V. Feigelman che lavora presso l'Istituto di Fisica Teorica. LD Landau RAS, suggerisce di assemblare registri quantistici da anelli superconduttori in miniatura. Ogni anello agisce come un qubit e gli stati 0 e 1 corrispondono alla direzione della corrente elettrica nell'anello, in senso orario e antiorario. Tali qubit possono essere commutati utilizzando un campo magnetico.

All'Istituto fisico-tecnologico dell'Accademia delle scienze russa, un gruppo guidato dall'accademico K. A. Valiev ha proposto due opzioni per posizionare i qubit nelle strutture dei semiconduttori. Nel primo caso, il ruolo di un qubit è svolto da un elettrone in un sistema di due pozzi di potenziale creati da una tensione applicata a mini-elettrodi sulla superficie del semiconduttore. Gli stati 0 e 1 sono le posizioni di un elettrone in uno di questi pozzetti. Il qubit viene commutato modificando la tensione su uno degli elettrodi. In un'altra versione, il qubit è il nucleo di un atomo di fosforo inserito in un certo punto nel semiconduttore. Gli stati 0 e 1 sono le direzioni dello spin nucleare lungo o contro il campo magnetico esterno. Il controllo viene effettuato utilizzando l'azione combinata di impulsi magnetici della frequenza di risonanza e impulsi di tensione.

Pertanto, la ricerca viene portata avanti attivamente e si può presumere che in un futuro molto prossimo, tra dieci anni, verrà creato un computer quantistico efficace.

UNO SGUARDO AL FUTURO

Pertanto, è del tutto possibile che in futuro i computer quantistici vengano prodotti utilizzando metodi tradizionali della tecnologia microelettronica e contengano molti elettrodi di controllo, simili a un moderno microprocessore. Al fine di ridurre il livello di rumore, fondamentale per il normale funzionamento di un computer quantistico, i primi modelli dovranno molto probabilmente essere raffreddati con elio liquido. È probabile che i primi computer quantistici siano dispositivi ingombranti e costosi che non possono stare su una scrivania e sono stati mantenuti da un ampio staff di programmatori di sistema e regolatori hardware in camice bianco. In primo luogo, solo le agenzie governative avranno accesso a loro, quindi le ricche organizzazioni commerciali. Ma l'era dei computer convenzionali è iniziata più o meno allo stesso modo.

E che ne sarà dei computer classici? Moriranno? Difficilmente. Sia i computer classici che quelli quantistici hanno le proprie aree di applicazione. Anche se, con ogni probabilità, il rapporto sul mercato si sposterà gradualmente verso quest'ultimo.

L'introduzione dei computer quantistici non porterà alla soluzione di problemi classici fondamentalmente irrisolvibili, ma accelererà solo alcuni calcoli. Inoltre, diventerà possibile la comunicazione quantistica: la trasmissione di qubit a distanza, che porterà all'emergere di una sorta di Internet quantistico. La comunicazione quantistica fornirà una connessione protetta (dalle leggi della meccanica quantistica) dalle intercettazioni di tutti gli uni con gli altri. Le tue informazioni memorizzate nei database quantistici saranno più protette dalla copia di quanto non lo siano ora. Le aziende che producono programmi per computer quantistici saranno in grado di proteggerli da qualsiasi copia, comprese quelle illegali.

Per una comprensione più approfondita di questo argomento, è possibile leggere l'articolo di revisione di E. Riffel, V. Polak "Fundamentals of Quantum Computing" pubblicato sulla rivista "Quantum Computers and Quantum Computing" pubblicato in Russia (n. 1, 2000). (A proposito, questa è la prima e finora l'unica rivista al mondo dedicata al calcolo quantistico. Ulteriori informazioni a riguardo possono essere trovate su Internet all'indirizzo http://rcd.ru/qc.). Dopo aver imparato questo lavoro, sarai in grado di leggere articoli scientifici sull'informatica quantistica.

Per la lettura del libro di A. Kitaev, A. Shen, M. Vyaly "Classical and Quantum Computing" sarà richiesto un addestramento matematico un po 'più preliminare (Mosca: MTsNMO-CheRo, 1999).

Un certo numero di aspetti fondamentali della meccanica quantistica, essenziali per l'informatica quantistica, sono analizzati nel libro di V.V.Belokurov, O.D. Timofeevskaya, O. A. Khrustalev "Il teletrasporto quantistico è un miracolo ordinario" (Izhevsk: RKhD, 2000).

La casa editrice RKhD si prepara a pubblicare, sotto forma di un libro separato, una traduzione della recensione di A. Steen dedicata ai computer quantistici.

La seguente letteratura sarà utile non solo cognitivamente, ma anche storicamente:

1) Yu. I. Manin. Calcolabile e non calcolabile.

M .: Sov. radio, 1980.

2) I. von Neumann. Fondamenti matematici della meccanica quantistica.

Mosca: Nauka, 1964.

3) R. Feynman. Simulazione della fisica su computer // Computer quantistico e calcolo quantistico:

Sab. in 2 volumi - Izhevsk: RKhD, 1999. Vol.2, p. 96-123.

4) R. Feynman. Computer meccanici quantistici

// Ibid, p. 123.-156.

Vedi il problema sullo stesso argomento

Il motivo per cui questa simulazione è importante è che i computer digitali classici hanno poco a che fare con gli stati multi-referenziali; in molti casi, i metodi classici di calcolo, non solo quantitativamente ma anche qualitativamente, non sono in grado di descrivere la struttura elettronica delle molecole.

Un problema importante che è stato risolto di recente era trovare modi in cui un computer quantistico potesse eseguire calcoli in modo efficiente e con l'accuratezza chimica richiesta per il mondo reale. Il programma è stato eseguito su un processore IBM a 20 qubit.

Perché la chimica è entrata nel campo di tale interesse? La chimica è una delle applicazioni commerciali più redditizie per una serie di motivi. Gli scienziati si aspettano di trovare materiali più efficienti dal punto di vista energetico che possono essere utilizzati nelle batterie o nei pannelli solari. Ci sono anche vantaggi ambientali: circa il due per cento dell'energia mondiale viene spesa in fertilizzanti, che sono orribilmente inefficienti e possono essere migliorati attraverso sofisticate analisi chimiche.

Infine, ci sono applicazioni di medicina personalizzata con la capacità di prevedere come i farmaci influenzeranno le persone in base alla loro genetica. A lungo termine, un'opportunità per sviluppare un farmaco per una persona specifica per il trattamento più efficace e la riduzione al minimo degli effetti collaterali

CQC e JSR Corp avevano due strategie che hanno consentito agli scienziati di compiere questa svolta. In primo luogo, hanno utilizzato il proprio compilatore CQC per trasformare in modo più efficiente un programma per computer in istruzioni per manipolare un qubit. Questa efficienza è particolarmente importante sulle moderne macchine a piccoli qubit, dove ogni qubit è importante e necessario e la velocità di esecuzione è fondamentale.

In secondo luogo, hanno utilizzato l'apprendimento automatico quantistico, uno speciale sottocampo dell'apprendimento automatico che utilizza ampiezze vettoriali anziché solo probabilità. Il metodo utilizzato di apprendimento automatico quantistico è stato sviluppato appositamente per computer quantistici a basso qubit, con scaricamento parziale utilizzando processori tradizionali.

Nei prossimi anni sono previsti miglioramenti quantistici sia nell'hardware che nel software. Man mano che i calcoli diventano più accurati, più industrie possono trarre vantaggio dalle applicazioni di calcolo quantistico, inclusa la chimica quantistica. Gartner prevede che entro quattro anni il 20% delle aziende disporrà di un budget per il calcolo quantistico. In dieci anni diventeranno parte integrante della tecnologia.