Calculatoare cuantice. Calculatoare cuantice Calculul intervalelor de timp emise procesului

Astăzi aș dori să încep să public o serie de note despre acest subiect arzător, despre care a fost publicată recent noua mea carte, și anume o introducere în înțelegerea modelului computațional cuantic. Îi mulțumesc bunului meu prieten și coleg Alexander pentru oportunitatea de a posta postări de invitați pe acest subiect pe blogul său.

Am încercat să fac această scurtă notă cât se poate de simplă din punct de vedere al înțelegerii pentru cititorul neinstruit care, totuși, ar dori să înțeleagă ce este calculul cuantic. Cu toate acestea, cititorul trebuie să aibă o înțelegere de bază a informaticii. Ei bine, nici o educație matematică generală nu s-ar potrivi :). Nu există formule în articol, totul este explicat în cuvinte. Cu toate acestea, toți îmi puteți pune întrebări în comentarii și voi încerca să vă explic cât de bine pot.

Ce este calculul cuantic?

Să începem cu faptul că calculul cuantic este o temă nouă, foarte la modă, care se dezvoltă vertiginos în mai multe direcții (în timp ce la noi, ca orice știință fundamentală, rămâne în paragină și este lăsată în seama câțiva oameni de știință care stau în picioare). turnurile lor de fildeș). Și acum vorbesc deja despre apariția primelor calculatoare cuantice (D-Wave, dar acesta nu este un computer cuantic universal), noi algoritmi cuantici sunt publicati în fiecare an, sunt create limbaje de programare cuantică, geniul umbră al International Business Machines din laboratoarele secrete subterane produce calcule cuantice pe zeci de qubiți.

Ce este? Calculul cuantic este un model de calcul care diferă de modelele Turing și von Neumann și este de așteptat să fie mai eficient pentru unele sarcini. Cel puțin, au fost găsite probleme pentru care modelul de calcul cuantic dă complexitate polinomială, în timp ce pentru modelul de calcul clasic nu sunt cunoscuți algoritmi care să aibă o complexitate mai mică decât cea exponențială (dar, pe de altă parte, nu a fost încă dovedit). că astfel de algoritmi nu există).

Cum poate fi aceasta? E simplu. Modelul de calcul cuantic se bazează pe mai multe reguli simple transformări ale informațiilor de intrare care asigură paralelizarea masivă a proceselor de calcul. Cu alte cuvinte, puteți evalua valoarea unei funcții pentru toate argumentele sale în același timp (și acesta va fi un singur apel de funcție). Acest lucru se realizează prin pregătirea specială a parametrilor de intrare și un tip special de funcție.

Lighter Prots învață că toate acestea sunt manipulare sintactică cu simboluri matematice, în spatele căreia, de fapt, nu există niciun sens. Există un sistem formal cu reguli de transformare a intrărilor în ieșiri, iar acest sistem permite, prin aplicarea consecventă a acestor reguli, obținerea rezultatelor din datele de intrare. Toate acestea se rezumă în cele din urmă la înmulțirea unei matrice și a unui vector. Da da da. Întregul model de calcul cuantic se bazează pe o operație simplă - înmulțirea unei matrice cu un vector, rezultând un alt vector ca rezultat.

Luminarul Halikaarn, în schimb, învață că există un proces fizic obiectiv care efectuează operația specificată și numai a cărui existență determină posibilitatea paralelizării masive a calculelor funcției. Faptul că percepem acest lucru ca înmulțirea unei matrice cu un vector este doar modul nostru de a reflecta imperfect realitatea obiectivă în mintea noastră.

În laboratorul nostru științific, numit după luminarii Prots și Halikaarn, combinăm aceste două abordări și spunem că modelul de calcul cuantic este o abstractizare matematică care reflectă un proces obiectiv. În special, numerele din vectori și matrici sunt complexe, deși acest lucru nu crește deloc puterea de calcul a modelului (ar fi la fel de puternic cu numerele reale), dar s-au ales numere complexe deoarece s-a constatat un proces fizic obiectiv care efectuează astfel de transformări, așa cum le descrie modelul și în care sunt utilizate numere complexe. Acest proces se numește evoluția unitară a unui sistem cuantic.

Modelul de calcul cuantic se bazează pe conceptul de qubit. Acest lucru este în esență același cu un bit în teoria clasică a informațiilor, dar un qubit poate lua mai multe valori în același timp. Ei spun că un qubit se află într-o suprapunere a stărilor sale, adică valoarea unui qubit este o combinație liniară a stărilor sale de bază, iar coeficienții stărilor de bază sunt exact numere complexe. Stările de bază sunt valorile 0 și 1, cunoscute din teoria clasică a informațiilor (în calculul cuantic ele sunt de obicei notate |0> și |1>).

Nu este încă foarte clar care este trucul. Și iată trucul. Suprapunerea unui qubit se scrie ca A|0> + B|1>, unde A și B sunt numere complexe, singura constrângere pentru care este aceea că suma pătratelor modulelor lor trebuie să fie întotdeauna egală cu 1. Ce dacă luăm în considerare doi qubiți? Doi biți pot avea 4 valori posibile: 00, 01, 10 și 11. Este rezonabil să presupunem că cei doi qubiți reprezintă o suprapunere a patru valori de bază: A|00> + B|01> + C|10> + D| 11>. Asa si este. Cei trei qubiți sunt o suprapunere a opt valori de bază. Cu alte cuvinte, un registru cuantic de N qubiți stochează simultan 2N numere complexe. Ei bine, din punct de vedere matematic, acesta este un vector 2N-dimensional într-un spațiu cu valori complexe. Aceasta este ceea ce atinge puterea exponențială a modelului de calcul cuantic.

Urmează o funcție care se aplică datelor de intrare. Deoarece intrarea este acum o suprapunere a tuturor valorilor posibile ale argumentului de intrare, funcția trebuie convertită pentru a accepta o astfel de suprapunere și a o procesa. Și aici totul este mai mult sau mai puțin simplu. În cadrul modelului de calcul cuantic, fiecare funcție este o matrice supusă unei singure constrângeri: trebuie să fie hermitiană. Aceasta înseamnă că atunci când această matrice este înmulțită cu conjugatul ei hermitian, ar trebui să se obțină matricea de identitate. Matricea conjugată Hermitiană se obține prin transpunerea matricei originale și înlocuirea tuturor elementelor acesteia cu conjugatele lor complexe. Această limitare rezultă din limitarea menționată anterior asupra registrului cuantic. Faptul este că, dacă o astfel de matrice este înmulțită cu vectorul unui registru cuantic, rezultatul este un nou registru cuantic, suma pătratelor modulelor de coeficienți cu valori complexe pentru stările cuantice ale cărora este întotdeauna egală. la 1.

Se arată că orice funcție poate fi transformată într-un mod special într-o astfel de matrice. De asemenea, afișat. că orice matrice hermitiană poate fi exprimată prin produsul tensor al unui set mic de matrici de bază reprezentând operații logice de bază. Totul aici este aproximativ la fel ca în modelul clasic de calcul. Acesta este un subiect mai complex, care depășește scopul acestui articol de recenzie. Adică, acum principalul lucru de înțeles este că orice funcție poate fi exprimată ca o matrice adecvată pentru utilizare în modelul de calcul cuantic.

Ce se întâmplă în continuare? Aici avem un vector de intrare, care este o suprapunere a diferitelor opțiuni pentru valorile parametrului de intrare al funcției. Există o funcție sub forma unei matrice hermitiene. Algoritmul cuantic este o multiplicare matrice-vector. Rezultatul este un nou vector. Ce fel de prostie este asta?

Cert este că în modelul de calcul cuantic există o altă operație numită măsurare. Putem măsura un vector și obține o anumită valoare de qubit din acesta. Adică, suprapunerea se prăbușește într-o anumită valoare. Și probabilitatea de a obține una sau alta valoare este egală cu pătratul modulului coeficientului cu valori complexe. Și acum este clar de ce suma pătratelor ar trebui să fie egală cu 1, deoarece măsurarea va produce întotdeauna o anumită valoare și, prin urmare, suma probabilităților de obținere a acestora este egală cu unu.

Deci ce se întâmplă? Având N qubiți, puteți procesa simultan 2N numere complexe. Și vectorul de ieșire va conține rezultatele procesării tuturor acestor numere simultan. Aceasta este puterea modelului de calcul cuantic. Dar puteți obține o singură valoare și poate fi diferită de fiecare dată, în funcție de distribuția probabilității. Aceasta este o limitare a modelului de calcul cuantic.

Esența algoritmului cuantic este următoarea. Este creată o suprapunere la fel de probabilă a tuturor valorilor posibile ale parametrului de intrare. Această suprapunere este alimentată la intrarea funcției. În plus, pe baza rezultatelor execuției sale, se trage o concluzie despre proprietățile acestei funcții. Cert este că nu putem obține toate rezultatele, dar putem trage complet concluzii despre proprietățile funcției. Și secțiunea următoare va arăta câteva exemple.

În marea majoritate a surselor de calcul cuantic, cititorul va găsi descrieri ale mai multor algoritmi, care, de fapt, sunt utilizați de obicei pentru a demonstra puterea modelului de calcul. Aici ne vom uita, de asemenea, pe scurt și superficial, la astfel de algoritmi (doi dintre ei, care demonstrează diferite principii de bază ale calculului cuantic). Ei bine, pentru o cunoaștere detaliată cu ei, mă refer din nou la noua mea carte.

algoritmul lui Deutsch

Acesta este primul algoritm care a fost dezvoltat pentru a demonstra esența și eficacitatea calculului cuantic. Problema pe care o rezolvă acest algoritm este complet separată de realitate, dar poate fi folosită pentru a arăta principiul de bază care stă la baza modelului.

Deci, să existe o funcție care primește un bit ca intrare și returnează un bit ca ieșire. Sincer, ar putea fi doar 4 astfel de funcții.Două dintre ele sunt constante, adică una returnează întotdeauna 0, iar cealaltă returnează întotdeauna 1. Celelalte două sunt echilibrate, adică returnează 0 și 1 în număr egal de cazuri. Întrebare: cum puteți determina într-un apel la această funcție dacă este constantă sau echilibrată?

Evident, acest lucru nu se poate face în modelul clasic de calcul. Trebuie să apelați funcția de două ori și să comparați rezultatele. Dar în modelul de calcul cuantic acest lucru se poate face, deoarece funcția va fi apelată o singură dată. Să vedem…

După cum a fost deja scris, vom pregăti o suprapunere la fel de probabilă a tuturor valorilor posibile ale parametrului de intrare al funcției. Deoarece avem un qubit la intrare, suprapunerea lui cu probabilitate egală este pregătită folosind o aplicație a porții Hadamard (aceasta este o funcție specială care pregătește suprapoziții cu probabilitate egală:). Apoi, se aplică din nou poarta Hadamard, care funcționează în așa fel încât, dacă o suprapunere cu probabilitate egală este alimentată la intrarea sa, o convertește înapoi în stările |0> sau |1>, în funcție de faza superpoziției cu probabilitate egală. este in. După aceasta, se măsoară qubitul, iar dacă este egal cu |0>, atunci funcția în cauză este constantă, iar dacă |1>, atunci este echilibrată.

Ce se întâmplă? După cum am menționat deja, atunci când măsurăm nu putem obține toate valorile unei funcții. Dar putem trage anumite concluzii despre proprietățile sale. Problema lui Deutsch se întreabă despre o proprietate a unei funcții. Și această proprietate este foarte simplă. La urma urmei, cum merge? Dacă funcția este constantă, atunci adăugarea modulo 2 a tuturor valorilor sale de ieșire dă întotdeauna 0. Dacă funcția este echilibrată, atunci adăugarea modulo 2 a tuturor valorilor sale de ieșire dă întotdeauna 1. Acesta este exact rezultatul pe care l-am obținut ca rezultat al executării algoritmului Deutsch. Nu știm exact ce valoare a returnat funcția dintr-o suprapunere la fel de probabilă a tuturor valorilor de intrare. Știm doar că aceasta este și o suprapunere a rezultatelor și dacă acum transformăm această suprapunere într-un mod special, atunci se vor trage concluzii clare despre proprietatea funcției.

Ceva de genul.

Algoritmul lui Grover

Un alt algoritm, care arată un câștig pătratic în comparație cu modelul clasic de calcul, rezolvă o problemă care este mai aproape de realitate. Acesta este algoritmul lui Grover sau, așa cum îl numește Love Grover însuși, algoritmul pentru găsirea unui ac într-un car de fân. Acest algoritm se bazează pe un alt principiu care stă la baza calculului cuantic, și anume amplificare.

Am menționat deja o anumită fază pe care o poate avea o stare cuantică într-un qubit. Nu există nicio fază ca atare în modelul clasic; este ceva nou în cadrul calculului cuantic. Faza poate fi înțeleasă ca semnul coeficientului unei stări cuantice în suprapunere. Algoritmul lui Grover se bazează pe faptul că o funcție special pregătită schimbă faza stării |1>.

Algoritmul lui Grover rezolvă problema inversă. Dacă aveți un set neordonat de date în care trebuie să găsiți un element care îndeplinește criteriul de căutare, algoritmul lui Grover vă va ajuta să faceți acest lucru mai eficient decât simpla forță brută. Dacă enumerarea simplă rezolvă problema în apelurile de funcție O(N), atunci algoritmul lui Grover găsește efectiv un element dat în apelurile de funcție O(√N).

Algoritmul lui Grover constă din următorii pași:

1. Inițializarea stării inițiale. Din nou, este pregătită o suprapunere cu probabilitate egală a tuturor qubiților de intrare.

2. Aplicarea iterației Grover. Această iterație constă în aplicarea secvențială a funcției de căutare (determină criteriul de căutare pentru element) și o poartă de difuzie specială. Poarta de difuzie modifică coeficienții stărilor cuantice, rotindu-i în jurul mediei. Aceasta produce o amplificare, adică o creștere a amplitudinii valorii dorite. Trucul este că este necesar să se aplice iterația de un anumit număr de ori (√2 n), altfel algoritmul va returna rezultate greșite.

3. Măsurare. După măsurarea registrului cuantic de intrare, este probabil să se obțină rezultatul dorit. Dacă este necesar să creșteți fiabilitatea răspunsului, atunci algoritmul este rulat de mai multe ori și se calculează probabilitatea cumulativă a răspunsului corect.

Lucrul interesant la acest algoritm este că vă permite să rezolvați o problemă arbitrară (de exemplu, oricare din clasa NP-completă), oferind, deși nu exponențial, dar o creștere semnificativă a eficienței în comparație cu modelul clasic de calcul. Un articol viitor va arăta cum se poate face acest lucru.

Cu toate acestea, nu se mai poate spune că oamenii de știință continuă să stea în turnul lor de fildeș. În ciuda faptului că mulți algoritmi cuantici sunt dezvoltați pentru unele probleme ciudate și de neînțeles asemănătoare Mathan (de exemplu, determinarea ordinii unui ideal al unui inel finit), au fost deja dezvoltați o serie de algoritmi cuantici care rezolvă probleme foarte aplicate. În primul rând, acestea sunt sarcini din domeniul criptografiei (compromiterea diferitelor sisteme și protocoale criptografice). Urmează problemele matematice tipice pe grafice și matrice, iar astfel de probleme au o gamă foarte largă de aplicații. Ei bine, există o serie de algoritmi de aproximare și emulare care folosesc componenta analogică a modelului de calcul cuantic.

Cu doar cinci ani în urmă, doar specialiștii din domeniul fizicii cuantice știau despre calculatoarele cuantice. Cu toate acestea, în anul trecut Numărul publicațiilor pe Internet și în publicațiile de specialitate dedicate calculului cuantic a crescut exponențial. Subiectul calculului cuantic a devenit popular și a generat multe opinii diferite, care nu corespund întotdeauna realității.
În acest articol vom încerca să vorbim cât mai clar despre ce este un computer cuantic și în ce stadiu se află evoluțiile moderne din acest domeniu.

Capacități limitate ale computerelor moderne

Despre computerele cuantice și despre calculul cuantic se vorbește adesea ca o alternativă la tehnologiile cu siliciu pentru crearea de microprocesoare, ceea ce, în general, nu este în întregime adevărat. De fapt, de ce trebuie să căutăm o alternativă la tehnologia computerizată modernă? După cum arată întreaga istorie a industriei computerelor, puterea de calcul a procesoarelor crește exponențial. Nicio altă industrie nu se dezvoltă într-un ritm atât de rapid. De regulă, când vorbesc despre rata de creștere a puterii de calcul a procesoarelor, ei amintesc de așa-numita lege a lui Gordon Moore, derivată în aprilie 1965, adică la doar șase ani de la inventarea primului circuit integrat (IC) .

La solicitarea revistei Electronics, Gordon Moore a scris un articol dedicat aniversării a 35 de ani de la publicație. El a făcut o predicție despre cum se vor dezvolta dispozitivele semiconductoare în următorii zece ani. După ce a analizat ritmul de dezvoltare a dispozitivelor semiconductoare și a factorilor economici în ultimii șase ani, adică din 1959, Gordon Moore a sugerat că până în 1975 numărul de tranzistori dintr-un circuit integrat va fi de 65 de mii.

De fapt, conform prognozei lui Moore, numărul de tranzistori dintr-un singur cip era de așteptat să crească de peste o mie de ori în zece ani. În același timp, asta însemna că în fiecare an numărul de tranzistori dintr-un cip trebuia să se dubleze.

Ulterior, s-au făcut ajustări la legea lui Moore (pentru a o corela cu realitatea), dar sensul nu s-a schimbat: numărul de tranzistori din microcircuite crește exponențial. Desigur, creșterea densității tranzistorilor pe un cip este posibilă numai prin reducerea dimensiunii tranzistorilor înșiși. În acest sens, o întrebare relevantă este: în ce măsură poate fi redusă dimensiunea tranzistoarelor? Deja acum, dimensiunile elementelor individuale de tranzistor din procesoare sunt comparabile cu cele atomice; de ​​exemplu, lățimea stratului de dioxid care separă dielectricul de poartă de canalul de transfer al sarcinii este de doar câteva zeci de straturi atomice. Este clar că există o limită pur fizică care face imposibilă reducerea în continuare a dimensiunii tranzistorilor. Chiar dacă presupunem că în viitor vor avea o geometrie și o arhitectură puțin diferite, teoretic este imposibil să se creeze un tranzistor sau un element similar cu o dimensiune mai mică de 10 -8 cm (diametrul unui atom de hidrogen) și o funcționare. frecvență mai mare de 10 15 Hz (frecvența tranzițiilor atomice). Prin urmare, fie că ne place sau nu, este inevitabil ziua în care Legea lui Moore va trebui să fie arhivată (cu excepția cazului în care, desigur, este corectată încă o dată).

Oportunități limitate creșterea puterii de calcul a procesoarelor prin reducerea dimensiunii tranzistorilor este doar unul dintre blocajele procesoarelor clasice cu siliciu.

După cum vom vedea mai târziu, calculatoarele cuantice nu reprezintă în niciun caz o încercare de a rezolva problema miniaturizării elementelor de bază ale procesoarelor.

Rezolvarea problemei miniaturizării tranzistoarelor, căutarea de noi materiale pentru crearea elementului de bază a microelectronicii, căutarea de noi principii fizice pentru dispozitive cu dimensiuni caracteristice comparabile cu lungimea de undă De Broglie, care are o valoare de aproximativ 20 nm - aceste probleme au fost pe ordinea de zi de aproape două decenii. Ca rezultat al soluției lor, a fost dezvoltată nanotehnologia. O problemă serioasă cu care se confruntă în timpul tranziției către domeniul dispozitivelor nanoelectronice este reducerea disipării de energie în timpul operațiilor de calcul. Ideea posibilității operațiunilor „reversibile logic” care nu sunt însoțite de disiparea energiei a fost exprimată pentru prima dată de R. Landauer în 1961. Un pas semnificativ în rezolvarea acestei probleme a fost făcut în 1982 de Charles Bennett, care a demonstrat teoretic că un computer digital universal poate fi construit pe porți reversibile logic și termodinamic în așa fel încât energia să fie disipată doar datorită proceselor periferice ireversibile de introducere a informațiilor. în mașină (pregătirea stării inițiale) și, în consecință, ieșirea din aceasta (citirea rezultatului). Supapele universale reversibile tipice includ supapele Fredkin și Toffoli.

O altă problemă cu computerele clasice constă în arhitectura von Neumann însăși și în logica binară a tuturor procesoarelor moderne. Toate computerele, de la motorul analitic al lui Charles Babbage la supercalculatoarele moderne, se bazează pe aceleași principii (arhitectura von Neumann) care au fost dezvoltate în anii 40 ai secolului trecut.

Orice computer la nivel de software operează cu biți (variabile care iau valoarea 0 sau 1). Folosind porți logice, se efectuează operații logice pe biți, ceea ce vă permite să obțineți o anumită stare finală la ieșire. Schimbarea stării variabilelor se face folosind un program care definește o secvență de operații, fiecare dintre ele utilizând un număr mic de biți.

Procesoarele tradiționale execută programe secvenţial. În ciuda existenței unor sisteme multiprocesoare, procesoare multi-core și diverse tehnologii care vizează creșterea nivelului de paralelism, toate calculatoarele construite pe baza arhitecturii von Neumann sunt dispozitive cu un mod secvenţial de execuție a instrucțiunilor. Toate procesoarele moderne implementează următorul algoritm pentru procesarea comenzilor și datelor: preluarea comenzilor și a datelor din memorie și executarea instrucțiunilor pe datele selectate. Acest ciclu se repetă de multe ori și cu o viteză extraordinară.

Cu toate acestea, arhitectura von Neumann limitează capacitatea de a crește puterea de calcul a computerelor moderne. Un exemplu tipic de sarcină care depășește capacitățile PC-urilor moderne este descompunerea unui număr întreg în factori primi (un factor prim este un factor care este divizibil cu el însuși și 1 fără rest).

Dacă doriți să factorizați un număr în factori primi X, având n caractere în notație binară, atunci modalitatea evidentă de a rezolva această problemă este să încercați să o împărțiți secvențial în numere de la 2 la. Pentru a face acest lucru, va trebui să parcurgeți 2 opțiuni n/2. De exemplu, dacă luați în considerare un număr care are 100.000 de caractere (în notație binară), atunci va trebui să parcurgeți 3x10 15.051 opțiuni. Dacă presupunem că este necesar un ciclu de procesor pentru o căutare, atunci la o viteză de 3 GHz, va dura timp pentru a depăși vârsta planetei noastre pentru a căuta prin toate numerele. Există, totuși, un algoritm inteligent care rezolvă aceeași problemă în exp( n 1/3) pași, dar chiar și în acest caz, niciun supercomputer modern nu poate face față sarcinii de factorizare a unui număr cu un milion de cifre.

Problema factorizării unui număr în factori primi aparține clasei de probleme despre care se spune că nu sunt rezolvate în timp polinomial (problema NP-completă - Polinomial nedeterministă-timp complet). Astfel de probleme sunt incluse în clasa problemelor necalculabile în sensul că nu pot fi rezolvate pe calculatoare clasice într-un polinom de timp în funcție de numărul de biți n, reprezentând sarcina. Dacă vorbim despre factorizarea unui număr în factori primi, atunci pe măsură ce numărul de biți crește, timpul necesar pentru rezolvarea problemei crește exponențial, nu polinom.

Privind în viitor, observăm că calculul cuantic este asociat cu perspectivele de rezolvare a problemelor NP-complete în timp polinomial.

Fizica cuantică

Desigur, fizica cuantică este strâns legată de ceea ce se numește baza elementară a computerelor moderne. Cu toate acestea, când vorbim despre un computer cuantic, este pur și simplu imposibil să eviți menționarea unor termeni specifici ai fizicii cuantice. Înțelegem că nu toată lumea a studiat legendarul volum al treilea din „Fizica teoretică” de L.D. Landau și E.M. Lifshitz, iar pentru multe concepte precum funcția de undă și ecuația Schrödinger sunt ceva din lumea cealaltă. În ceea ce privește aparatul matematic specific al mecanicii cuantice, acestea sunt formule solide și cuvinte obscure. Prin urmare, vom încerca să aderăm la un nivel general accesibil de prezentare, evitând, dacă este posibil, analiza tensorială și alte specificități ale mecanicii cuantice.

Pentru marea majoritate a oamenilor, mecanica cuantică este dincolo de înțelegere. Ideea nu este atât în ​​aparatul matematic complex, cât în ​​faptul că legile mecanicii cuantice sunt ilogice și nu au o asociere subconștientă - sunt imposibil de imaginat. Cu toate acestea, analiza ilogicității mecanicii cuantice și nașterea paradoxală a logicii armonioase din această ilogicitate este lotul filosofilor; vom atinge aspectele mecanicii cuantice doar în măsura necesară pentru a înțelege esența calculului cuantic.

Istoria fizicii cuantice a început pe 14 decembrie 1900. În această zi, fizicianul german și viitorul laureat al Premiului Nobel Max Planck a raportat la o reuniune a Societății de Fizică din Berlin despre descoperirea fundamentală a proprietăților cuantice ale radiației termice. Așa a apărut în fizică conceptul de cuantum de energie și, printre alte constante fundamentale, constanta lui Planck.

Descoperirea lui Planck și teoria efectului fotoelectric a lui Albert Einstein, care a apărut apoi în 1905, precum și crearea în 1913 a primei teorii cuantice a spectrelor atomice de către Niels Bohr au stimulat crearea și dezvoltarea rapidă ulterioară a teoriei cuantice și a studiilor experimentale cuantice. fenomene.

Deja în 1926, Erwin Schrödinger și-a formulat celebra ecuație de undă, iar Enrico Fermi și Paul Dirac au obținut o distribuție statistică cuantică pentru gazul de electroni, ținând cont de umplerea stărilor cuantice individuale.

În 1928, Felix Bloch a analizat problema mecanică cuantică a mișcării unui electron într-un câmp periodic extern al unei rețele cristaline și a arătat că spectrul de energie electronică dintr-un solid cristalin are o structură de bandă. De fapt, acesta a fost începutul unei noi direcții în fizică - teoria stării solide.

Întregul secol al XX-lea este o perioadă de dezvoltare intensivă a fizicii cuantice și a tuturor acelor ramuri ale fizicii pentru care teoria cuantică a devenit precursoare.

Apariția calculului cuantic

Ideea de a utiliza calculul cuantic a fost exprimată pentru prima dată de matematicianul sovietic Yu.I. Manin în 1980 în celebra sa monografie „Computable and Incomputable”. Este adevărat, interesul pentru opera sa a apărut abia doi ani mai târziu, în 1982, după publicarea unui articol pe aceeași temă de către fizicianul teoretician american, laureatul Nobel Richard Feynman. El a observat că anumite operații mecanice cuantice nu pot fi transferate exact pe un computer clasic. Această observație l-a determinat să creadă că astfel de calcule ar putea fi mai eficiente dacă sunt efectuate folosind operații cuantice.

Luați în considerare, de exemplu, problema mecanică cuantică a schimbării stării unui sistem cuantic format din n se învârte într-o anumită perioadă de timp. Fără să ne adâncim în detaliile aparatului matematic al teoriei cuantice, observăm că stare generală sisteme de la n spinii sunt descriși de un vector în spațiu complex 2n-dimensional, iar schimbarea stării sale este descrisă de o matrice unitară de dimensiunea 2nx2n. Dacă perioada de timp luată în considerare este foarte scurtă, atunci matricea este structurată foarte simplu și fiecare dintre elementele sale este ușor de calculat, cunoscând interacțiunea dintre rotiri. Dacă trebuie să cunoașteți schimbarea stării sistemului pe o perioadă lungă de timp, atunci trebuie să înmulțiți astfel de matrici, iar acest lucru necesită un număr exponențial de mare de operații. Din nou ne confruntăm cu o problemă PN-completă, nerezolvabilă în timp polinomial pe calculatoarele clasice. În prezent, nu există nicio modalitate de a simplifica acest calcul și este probabil ca modelarea mecanicii cuantice să fie o problemă matematică complexă exponențial. Dar dacă computerele clasice nu sunt capabile să rezolve probleme cuantice, atunci poate că ar fi indicat să folosim sistemul cuantic în sine în acest scop? Și dacă acest lucru este într-adevăr posibil, sistemele cuantice sunt potrivite pentru rezolvarea altor probleme de calcul? Întrebări similare au fost luate în considerare de Feynman și Manin.

Deja în 1985, David Deutsch a propus un model matematic specific al unei mașini cuantice.

Cu toate acestea, până la mijlocul anilor 90, domeniul calculului cuantic s-a dezvoltat destul de lent. Implementarea practică a calculatoarelor cuantice s-a dovedit a fi foarte dificilă. Mai mult, în comunitate stiintifica au fost pesimiști cu privire la capacitatea operațiilor cuantice de a accelera soluționarea anumitor probleme de calcul. Acest lucru a continuat până în 1994, când matematicianul american Peter Shor a propus un algoritm de descompunere pentru un computer cuantic. n-numar cifra in factori primi intr-un polinom de timp in functie de n(algoritm de factorizare cuantică). Algoritmul de factorizare cuantică a lui Shor a devenit unul dintre principalii factori care au condus la dezvoltarea intensivă a metodelor de calcul cuantic și apariția unor algoritmi care permit rezolvarea unor probleme NP.

Firește, se pune întrebarea: de ce, de fapt, algoritmul de factorizare cuantică propus de Shor a dus la astfel de consecințe? Faptul este că problema descompunerii unui număr în factori primi este direct legată de criptografie, în special de popularele sisteme de criptare RSA. Fiind capabil să factorizeze un număr în factori primi în timp polinomial, un computer cuantic ar putea teoretic să decripteze mesajele codificate folosind mulți algoritmi criptografici populari, cum ar fi RSA. Până acum, acest algoritm a fost considerat relativ fiabil, deoarece o modalitate eficientă de factorizare a numerelor în factori primi pentru un computer clasic este în prezent necunoscută. Shor a venit cu un algoritm cuantic care vă permite să factorizați n-numar digital pt n 3 (log n) k pași ( k=const). Desigur, implementarea practică a unui astfel de algoritm ar putea avea consecințe mai mult negative decât pozitive, deoarece a făcut posibilă selectarea cheilor pentru criptare, falsificarea semnăturilor electronice etc. Cu toate acestea, implementarea practică a unui computer cuantic real este încă departe și, prin urmare, în următorii zece ani nu există nicio teamă că codurile pot fi sparte folosind calculatoarele cuantice.

Ideea de calcul cuantic

Deci dupa descriere scurta istoria calculului cuantic, putem trece la considerarea însăși esența ei. Ideea (dar nu și implementarea sa) de calcul cuantic este destul de simplă și interesantă. Dar chiar și pentru o înțelegere superficială a acesteia, este necesar să ne familiarizați cu unele concepte specifice ale fizicii cuantice.

Înainte de a lua în considerare conceptele cuantice generalizate ale vectorului de stare și ale principiului de suprapunere, să luăm în considerare un exemplu simplu de foton polarizat. Un foton polarizat este un exemplu de sistem cuantic cu două niveluri. Starea de polarizare a unui foton poate fi specificată de un vector de stare care determină direcția de polarizare. Polarizarea unui foton poate fi îndreptată în sus sau în jos, deci se vorbește despre două stări principale, sau de bază, care sunt notate cu |1 și |0.

Aceste notații (notații sutien/pisica) au fost introduse de Dirac și au o definiție strict matematică (vectori de stare de bază), care determină regulile de lucru cu ele, totuși, pentru a nu pătrunde în jungla matematică, nu le vom lua în considerare. subtilități în detaliu.

Revenind la fotonul polarizat, observăm că, după cum arată baza, am putea alege nu numai orizontală și verticală, ci și orice direcție de polarizare reciproc ortogonală. Sensul stărilor de bază este că orice polarizare arbitrară poate fi exprimată ca o combinație liniară de stări de bază, adică a|1+b|0. Deoarece ne interesează doar direcția de polarizare (mărimea polarizării nu este importantă), vectorul de stare poate fi considerat unitate, adică |a| 2 +|b| 2 = 1.

Acum să generalizăm exemplul cu polarizarea fotonului la orice sistem cuantic cu două niveluri.

Să presupunem că avem un sistem cuantic arbitrar cu două niveluri, care este caracterizat de stări ortogonale de bază |1 și |0. Conform legilor (postulatelor) mecanicii cuantice (principiul suprapunerii), stările posibile ale unui sistem cuantic vor fi și suprapoziții y = a|1+b|0, unde a și b sunt numere complexe numite amplitudini. Rețineți că nu există un analog al stării de suprapunere în fizica clasică.

Unul dintre postulatele fundamentale ale mecanicii cuantice afirmă că, pentru a măsura starea unui sistem cuantic, acesta trebuie distrus. Adică, orice proces de măsurare din fizica cuantică încalcă starea inițială a sistemului și o transferă într-o stare nouă. Nu este atât de ușor de înțeles această afirmație și, prin urmare, să ne oprim asupra ei mai detaliat.

În general, conceptul de măsurare în fizica cuantică joacă un rol deosebit și nu trebuie considerat ca o măsurătoare în sensul clasic. O măsurare a unui sistem cuantic are loc ori de câte ori acesta intră în interacțiune cu un obiect „clasic”, adică un obiect care respectă legile fizicii clasice. Ca urmare a unei astfel de interacțiuni, starea sistemului cuantic se schimbă, iar natura și amploarea acestei schimbări depind de starea sistemului cuantic și, prin urmare, poate servi ca caracteristică cantitativă a acestuia.

În acest sens, un obiect clasic este de obicei numit dispozitiv, iar despre procesul său de interacțiune cu un sistem cuantic se vorbește despre o măsurătoare. Trebuie subliniat că aceasta nu înseamnă deloc procesul de măsurare la care participă observatorul. Prin măsurare în fizica cuantică înțelegem orice proces de interacțiune între obiectele clasice și cuantice care are loc în plus față de și independent de orice observator. Clarificarea rolului măsurării în fizica cuantică îi aparține lui Niels Bohr.

Deci, pentru a măsura un sistem cuantic, este necesar să se acționeze cumva asupra lui cu un obiect clasic, după care starea sa inițială va fi perturbată. În plus, se poate argumenta că, în urma măsurării, sistemul cuantic va fi transferat la una dintre stările sale de bază. De exemplu, pentru a măsura un sistem cuantic cu două niveluri, este necesar cel puțin un obiect clasic cu două nivele, adică un obiect clasic care poate lua două valori posibile: 0 și 1. În timpul procesului de măsurare, starea cuantiei sistemul va fi transformat într-unul dintre vectorii de bază, iar dacă obiectul clasic ia o valoare egală cu 0, atunci obiectul cuantic este transformat în starea |0, iar dacă obiectul clasic ia o valoare egală cu 1, atunci obiectul cuantic se transformă în starea |1.

Astfel, deși un sistem cuantic cu două niveluri poate fi într-un număr infinit de stări de suprapunere, ca rezultat al măsurării, este nevoie doar de una dintre cele două stări de bază posibile. Modulul de amplitudine la pătrat |a| 2 determină probabilitatea detectării (măsurării) a sistemului în starea de bază |1, iar pătratul modulului de amplitudine |b| 2 - în starea de bază |0.

Cu toate acestea, să revenim la exemplul nostru cu un foton polarizat. Pentru a măsura starea unui foton (polarizarea acestuia), avem nevoie de un dispozitiv clasic cu o bază clasică (1,0). Atunci starea de polarizare a fotonului a|1+b|0 va fi definită ca 1 (polarizare orizontală) cu probabilitate |a| 2 și ca 0 (polarizare verticală) cu probabilitatea |b| 2.

Deoarece măsurarea unui sistem cuantic îl duce la una dintre stările de bază și, prin urmare, distruge suprapunerea (de exemplu, în timpul măsurării se obține o valoare egală cu |1), aceasta înseamnă că în urma măsurării sistemul cuantic pleacă. într-o nouă stare cuantică și la următoarea măsurătoare obținem valoarea |1 cu 100% probabilitate.

Vectorul de stare al unui sistem cuantic cu două niveluri se mai numește și funcție de undă a stărilor cuantice y ale sistemului cu două niveluri sau, în interpretarea calculului cuantic, un qubit (bit cuantic, qubit). Spre deosebire de un bit clasic, care poate lua doar două valori logice, un qubit este un obiect cuantic, iar numărul stărilor sale determinat de suprapunere este nelimitat. Cu toate acestea, subliniem încă o dată că rezultatul măsurării unui qubit ne duce întotdeauna la una dintre cele două valori posibile.

Acum luați în considerare un sistem de doi qubiți. Măsurarea fiecăruia dintre ele poate da o valoare clasică a obiectului de 0 sau 1. Prin urmare, un sistem de doi qubiți are patru stări clasice: 00, 01, 10 și 11. Analog cu acestea sunt stările cuantice de bază: |00, |01, |10 și |11. Vectorul de stare cuantică corespunzător este scris ca A|00+b|01+ c|10+ d|11, unde | A| 2 - probabilitatea în timpul măsurării de a obține valoarea 00, | b| 2 - probabilitatea obținerii valorii 01 etc.

În general, dacă un sistem cuantic este format din L qubiți, atunci are 2 L posibile stări clasice, fiecare dintre acestea putând fi măsurată cu o anumită probabilitate. Funcția de stare a unui astfel de sistem cuantic se va scrie astfel:

unde | n- stări cuantice de bază (de exemplu, starea |001101 și | cn| 2 - probabilitatea de a fi în starea de bază | n.

Pentru a schimba starea de suprapunere a unui sistem cuantic, este necesar să se implementeze o influență externă selectivă asupra fiecărui qubit. Din punct de vedere matematic, o astfel de transformare este reprezentată de matrici unitare de mărime 2 L x2 L. Ca rezultat, se va obține o nouă stare de suprapunere cuantică.

Structura unui computer cuantic

Transformarea pe care am considerat-o a stării de suprapunere a unui sistem cuantic format din L qubits este în esență un model de computer cuantic. Luați în considerare, de exemplu, un exemplu mai simplu de implementare a calculului cuantic. Să presupunem că avem un sistem de L qubits, fiecare dintre care este ideal izolat de lumea exterioară. În fiecare moment de timp, putem alege arbitrar doi qubiți și acționăm asupra lor cu o matrice unitară de dimensiunea 4x4. Secvența unor astfel de influențe este un fel de program pentru un computer cuantic.

Pentru a utiliza un circuit cuantic pentru calcul, trebuie să fiți capabil să introduceți date de intrare, să efectuați calculul și să citiți rezultatul. De aceea schema circuitului orice calculator cuantic (a se vedea figura) trebuie să includă următoarele blocuri funcționale: un registru cuantic pentru introducerea datelor, un procesor cuantic pentru conversia datelor și un dispozitiv pentru citirea datelor.

Un registru cuantic este o colecție de un anumit număr L qubiți Înainte de a introduce informații în computer, toți qubiții registrului cuantic trebuie aduși la stările de bază |0. Această operație se numește pregătire sau inițializare. În continuare, anumiți qubiți (nu toți) sunt supuși unei influențe externe selective (de exemplu, folosind impulsuri ale unui câmp electromagnetic extern controlat de un computer clasic), care modifică valoarea qubiților, adică trec de la starea |0 la stare |1. În acest caz, starea întregului registru cuantic va intra într-o suprapunere a stărilor de bază | n s, adică starea registrului cuantic la momentul inițial de timp va fi determinată de funcția:

Este clar că această stare de suprapunere poate fi folosită pentru reprezentarea binară a unui număr n.

Într-un procesor cuantic, datele de intrare sunt supuse unei secvențe de operații logice cuantice, care, din punct de vedere matematic, sunt descrise printr-o transformare unitară care acționează asupra stării întregului registru. Ca rezultat, după un anumit număr de cicluri de procesor cuantic, starea cuantică inițială a sistemului devine o nouă suprapunere a formei:

Vorbind despre procesorul cuantic, trebuie să facem o notă importantă. Se pare că pentru a construi orice calcul, sunt suficiente doar două operații booleene logice de bază. Folosind operații cuantice de bază, este posibil să se imite funcționarea porților logice obișnuite din care sunt făcute computerele. Deoarece legile fizicii cuantice la nivel microscopic sunt liniare și reversibile, dispozitivele logice cuantice corespunzătoare care efectuează operații cu stările cuantice ale qubiților individuali (porți cuantice) se dovedesc a fi reversibile din punct de vedere logic și termodinamic. Porțile cuantice sunt similare cu porțile clasice reversibile corespunzătoare, dar, spre deosebire de acestea, sunt capabile să efectueze operații unitare asupra suprapunerilor de stări. Implementarea operațiilor logice unitare pe qubiți se presupune a fi efectuată folosind influențe externe adecvate controlate de calculatoarele clasice.

Structura schematică a unui computer cuantic

După implementarea transformărilor într-un computer cuantic, noua funcție de suprapunere este rezultatul calculelor într-un procesor cuantic. Mai rămâne doar să numărăm valorile obținute, pentru care se măsoară valoarea sistemului cuantic. Ca rezultat, se formează o succesiune de zerouri și unu și, datorită naturii probabilistice a măsurătorilor, poate fi orice. Astfel, un computer cuantic poate da orice răspuns cu o oarecare probabilitate. În acest caz, o schemă de calcul cuantic este considerată corectă dacă răspunsul corect este obținut cu o probabilitate suficient de apropiată de unitate. Repetând calculele de mai multe ori și alegând răspunsul care apare cel mai des, puteți reduce probabilitatea de eroare la o cantitate arbitrar mică.

Pentru a înțelege modul în care computerele clasice și cuantice diferă în funcționarea lor, să ne amintim ce stochează în memorie un computer clasic. L biți care se modifică în timpul fiecărui ciclu de procesor. Într-un computer cuantic, memoria (registrul de stare) stochează valori L qubiti, cu toate acestea, sistemul cuantic este într-o stare care este o suprapunere a întregii baze 2 L stări, iar o schimbare a stării cuantice a sistemului produsă de un procesor cuantic afectează toate cele 2 L stări de bază simultan. În consecință, într-un computer cuantic, puterea de calcul este obținută prin implementarea calculelor paralele și, teoretic, un computer cuantic poate funcționa exponențial mai rapid decât un circuit clasic.

Se crede că pentru a implementa un computer cuantic la scară largă, superioară ca performanță oricărui computer clasic, indiferent de principiile fizice pe care funcționează, trebuie îndeplinite următoarele cerințe de bază:

• un sistem fizic care este un computer cuantic la scară largă trebuie să conţină un număr suficient de mare L>103 qubiți clar vizibili pentru efectuarea de operații cuantice relevante;
• este necesar să se asigure suprimarea maximă a efectelor de distrugere a suprapunerii stărilor cuantice cauzate de interacțiunea unui sistem de qubiți cu mediu inconjurator, în urma căruia poate deveni imposibilă executarea algoritmilor cuantici. Timpul de distrugere a unei suprapuneri de stări cuantice (timp de decoerență) trebuie să fie de cel puțin 104 ori mai mare decât timpul necesar pentru a efectua operații cuantice de bază (timp de ciclu). Pentru a face acest lucru, sistemul qubit trebuie să fie cuplat destul de lejer la mediul său;
• este necesar să se asigure măsurarea cu fiabilitate suficient de mare a stării sistemului cuantic la ieșire. Măsurarea stării cuantice finale este una dintre principalele provocări ale calculului cuantic.

Aplicații practice ale calculatoarelor cuantice

Pentru aplicație practică Până acum, nu a fost creat niciun computer cuantic care să satisfacă toate condițiile de mai sus. Cu toate acestea, în multe țări dezvoltate, se acordă o atenție deosebită dezvoltării computerelor cuantice și se investesc zeci de milioane de dolari anual în astfel de programe.

În prezent, cel mai mare computer cuantic este format din doar șapte qubiți. Acest lucru este suficient pentru a implementa algoritmul lui Shor și pentru a factoriza numărul 15 în factori primi de 3 și 5.

Dacă vorbim despre posibile modele de calculatoare cuantice, atunci, în principiu, sunt destul de multe. Primul computer cuantic care a fost creat în practică a fost un spectrometru de rezonanță magnetică nucleară pulsată (RMN) de înaltă rezoluție, deși, desigur, nu a fost considerat un computer cuantic. Abia când a apărut conceptul de computer cuantic, oamenii de știință și-au dat seama că un spectrometru RMN era o variantă a unui computer cuantic.

Într-un spectrometru RMN, spinurile nucleelor ​​moleculei studiate formează qubiți. Fiecare nucleu are propria frecvență de rezonanță într-un anumit câmp magnetic. Când un nucleu este expus unui puls la frecvența sa de rezonanță, acesta începe să evolueze, în timp ce nucleele rămase nu experimentează niciun impact. Pentru a forța un alt nucleu să evolueze, trebuie să luați o frecvență de rezonanță diferită și să îi dați un impuls. Astfel, acțiunea pulsată asupra nucleelor ​​la o frecvență de rezonanță reprezintă un efect selectiv asupra qubiților. Mai mult, molecula are o legătură directă între spini, deci este o pregătire ideală pentru un computer cuantic, iar spectrometrul în sine este un procesor cuantic.

Primele experimente asupra spinurilor nucleare a doi atomi de hidrogen în moleculele de 2,3-dibromotiofen SCH:(CBr) 2:CH și pe trei spini nucleari - unul în atomul de hidrogen H și doi în izotopii carbonului 13 C în moleculele de tricloretilenă CCl 2:CHCl - au fost puse în scenă în 1997 la Oxford (Marea Britanie).

În cazul utilizării unui spectrometru RMN, este important ca pentru a influența selectiv spinurile nucleare ale unei molecule, este necesar ca aceștia să difere semnificativ în ceea ce privește frecvențele de rezonanță. Ulterior, operațiunile cuantice au fost efectuate într-un spectrometru RMN cu numărul de qubiți 3, 5, 6 și 7.

Principalul avantaj al unui spectrometru RMN este că poate folosi un număr mare de molecule identice. Mai mult, fiecare moleculă (mai precis, nucleele atomilor din care constă) este un sistem cuantic. Secvențele de impulsuri de radiofrecvență, acționând ca anumite porți logice cuantice, efectuează transformări unitare ale stărilor spinilor nucleari corespunzători simultan pentru toate moleculele. Adică, influența selectivă asupra unui qubit individual este înlocuită de accesul simultan la qubiții corespunzători din toate moleculele unui ansamblu mare. Un astfel de computer se numește computer cuantic de ansamblu. Astfel de computere pot funcționa la temperatura camerei, iar timpul de decoerență al stărilor cuantice ale spinurilor nucleare este de câteva secunde.

În domeniul RMN al calculatoarelor cuantice pe lichide organice, cel mai mare progres a fost realizat până în prezent. Acestea se datorează în principal tehnicii de spectroscopie RMN pulsată bine dezvoltată, care permite efectuarea diferitelor operații pe suprapuneri coerente ale stărilor de spin nuclear și posibilității de a utiliza în acest scop spectrometre RMN standard care funcționează la temperatura camerei.

Principala limitare a calculatoarelor cuantice RMN este dificultatea inițializării stării inițiale într-un registru cuantic. Cert este că într-un ansamblu mare de molecule starea inițială a qubiților este diferită, ceea ce complică aducerea sistemului la starea inițială.

O altă limitare a calculatoarelor cuantice RMN se datorează faptului că semnalul măsurat la ieșirea sistemului scade exponențial odată cu creșterea numărului de qubiți. L. În plus, numărul de qubiți nucleari dintr-o singură moleculă cu frecvențe de rezonanță foarte variate este limitat. Acest lucru duce la faptul că calculatoarele cuantice RMN nu pot avea mai mult de zece qubiți. Acestea ar trebui considerate doar ca prototipuri ale viitoarelor calculatoare cuantice, utile pentru testarea principiilor calculului cuantic și testarea algoritmilor cuantici.

O altă versiune a unui computer cuantic se bazează pe utilizarea capcanelor de ioni, când rolul qubiților este nivelul energetic al ionilor captați de capcanele de ioni, care sunt creați în vid printr-o anumită configurație a câmpului electric în condiții de răcire cu laser. la temperaturi foarte scăzute. Primul prototip al unui computer cuantic bazat pe acest principiu a fost propus în 1995. Avantajul acestei abordări este că este relativ simplu să controlezi individual qubiții individuali. Principalele dezavantaje ale computerelor cuantice de acest tip sunt necesitatea de a crea temperaturi ultra-scăzute, de a asigura stabilitatea stării ionilor din lanț și numărul limitat posibil de qubiți - nu mai mult de 40.

Sunt posibile și alte scheme pentru calculatoare cuantice, a căror dezvoltare este în prezent în curs. Cu toate acestea, vor mai trece cel puțin încă zece ani până când adevăratele computere cuantice vor fi create în sfârșit.

Din cauza boom-ului general al blockchain-ului și a tot felul de date mari, un alt subiect promițător a scăzut din topul știrilor din tehnologie - calculul cuantic. Și ei, apropo, sunt capabili să revoluționeze mai multe domenii IT deodată, începând cu notoriul blockchain și terminând cu securitatea informațiilor. În următoarele două articole, Sberbank și Sberbank Technologies vă vor spune de ce calculul cuantic este grozav și ce fac ei acum.

Calcule clasice: AND, OR, NOT

Pentru a înțelege calculul cuantic, ar trebui mai întâi să perfecționați calculul clasic. Aici unitatea de informație procesată este puțin. Fiecare bit poate fi în doar una dintre cele două stări posibile - 0 sau 1. Un registru de N biți poate conține una dintre cele 2 N combinații posibile de stări și este reprezentat ca o secvență a acestora.

Pentru procesarea și transformarea informațiilor, se folosesc operații pe biți care provin din algebra booleană. Operațiile de bază sunt NOT pe un bit și AND și SAU pe doi biți. Operațiile cu biți sunt descrise prin tabele de adevăr. Ele arată corespondența argumentelor de intrare cu valoarea rezultată.

Un algoritm de calcul clasic este un set de operații secvențiale pe biți. Cel mai convenabil este să o reproduci grafic, sub forma unei diagrame a elementelor funcționale (SFE), unde fiecare operațiune are propria denumire. Iată un exemplu de SFE pentru verificarea echivalenței a doi biți.

Calcul cuantic. Baza fizică

Acum să trecem la subiect nou. Calculul cuantic este o alternativă la algoritmii clasici bazați pe procesele fizicii cuantice. Afirmă că fără interacțiune cu alte particule (adică până în momentul măsurării), electronul nu are coordonate clare în orbita atomului, ci este situat simultan în toate punctele orbitei. Regiunea în care se află electronul se numește nor de electroni. În celebrul experiment cu dublă fante, un electron trece prin ambele fante simultan, interferând cu el însuși. Numai în timpul măsurării această incertitudine se prăbușește și coordonatele electronilor devin clare.

Natura probabilistică a măsurătorilor inerente în calculul cuantic stă la baza multor algoritmi - de exemplu, căutarea într-o bază de date nestructurată. Algoritmii de acest tip măresc pas cu pas amplitudinea rezultatului corect, permițând obținerea acestuia la ieșire cu probabilitate maximă.

Qubits

În calculul cuantic, proprietățile fizice ale obiectelor cuantice sunt implementate în așa-numiții qubiți (q-biți). Un bit clasic poate fi doar într-o stare – 0 sau 1. Înainte de măsurare, un qubit poate fi în ambele stări simultan, deci este de obicei notat prin expresia a|0⟩ + b|1⟩, unde A și B sunt complexe. numere care satisfac condiția |A | 2 +|B| 2 =1. Măsurarea unui qubit „prăbușește” instantaneu starea sa într-una dintre cele de bază – 0 sau 1. În acest caz, „norul” se prăbușește într-un punct, starea inițială este distrusă și toate informațiile despre acesta se pierd iremediabil.

O aplicație a acestei proprietăți este pisica lui Schrödinger ca un adevărat generator de numere aleatorii. Qubitul este introdus într-o stare în care rezultatul măsurării poate fi 1 sau 0 cu probabilitate egală. Această condiție este descrisă după cum urmează:

Calcul cuantic și clasic. Prima runda

Să începem cu elementele de bază. Există un set de date inițiale pentru calcule, reprezentate în format binar prin vectori de lungime N.

În calculele clasice, doar una dintre cele 2 n opțiuni de date este încărcată în memoria computerului și valoarea funcției este calculată pentru această opțiune. Ca urmare, numai unu din 2 n seturi de date posibile.

Toate cele 2n combinații de date sursă sunt reprezentate simultan în memoria unui computer cuantic. Transformările sunt aplicate tuturor acestor combinații simultan. Ca rezultat, într-o singură operație calculăm funcția pentru toți 2n opțiuni posibile set de date (măsurarea va oferi o singură soluție, dar mai multe despre asta mai târziu).

Atât calculul clasic cât și cel cuantic folosesc transformări logice - porti. În calculul clasic, valorile de intrare și de ieșire sunt stocate în biți diferiți, ceea ce înseamnă că în porți numărul de intrări poate diferi de numărul de ieșiri:

Să luăm în considerare o problemă reală. Trebuie să stabilim dacă doi biți sunt echivalenti.

Dacă în timpul calculelor clasice obținem unul la ieșire, atunci ele sunt echivalente, altfel nu:

Acum să ne imaginăm această problemă folosind calculul cuantic. În ele, toate porțile de transformare au același număr de ieșiri ca și intrări. Acest lucru se datorează faptului că rezultatul transformării nu este o valoare nouă, ci o schimbare a stării celor actuale.

În exemplu, comparăm valorile primului și celui de-al doilea qubit. Rezultatul va fi în qubit-ul zero - qubit-ul steag. Acest algoritm este aplicabil numai stărilor de bază - 0 sau 1. Aceasta este ordinea transformărilor cuantice.

1. Influențăm steagul qubit cu poarta „Nu”, setând-o la 1.
2. Folosim de două ori poarta „Controlled Not” de doi qubiți. Această poartă inversează valoarea qubitului de pavilion numai dacă al doilea qubit implicat în transformare este în starea 1.
3. Măsurăm qubitul zero. Dacă rezultatul este 1, atunci atât primul cât și cel de-al doilea qubit sunt fie în starea 1 (qubit-ul flag și-a schimbat valoarea de două ori), fie în starea 0 (qubit-ul flag a rămas în starea 1). În caz contrar, qubiții sunt în stări diferite.

Nivelul următor. Porți Pauli cuantice cu un singur qubit

Să încercăm să comparăm calculul clasic și cel cuantic în probleme mai serioase. Pentru aceasta avem nevoie de puțin mai multe cunoștințe teoretice.

În calculul cuantic, informațiile procesate sunt codificate în biți cuantici - numiți qubiți. În cel mai simplu caz, un qubit, ca un bit clasic, poate fi în una dintre cele două stări de bază: |0⟩ (notație scurtă pentru vectorul 1|0⟩ + 0|1⟩) și |1⟩ (pentru vectorul 0) |0⟩ + 1 |1⟩). Un registru cuantic este un produs tensor al vectorilor qubit. În cel mai simplu caz, când fiecare qubit se află într-una din stările de bază, registrul cuantic este echivalent cu cel clasic. Un registru de doi qubiți în starea |0> poate fi scris după cum urmează:

(1|0⟩ + 0|1⟩)*(1|0⟩ + 0|1⟩) = 1|00⟩ + 0|01⟩ + 0|10⟩ + 0|11⟩ = |00⟩.

Pentru a procesa și transforma informațiile în algoritmi cuantici, sunt folosite așa-numitele porți cuantice. Ele sunt reprezentate sub forma unei matrice. Pentru a obține rezultatul aplicării porții, trebuie să înmulțim vectorul care caracterizează qubit-ul cu matricea porții. Prima coordonată a vectorului este multiplicatorul înainte de |0⟩, a doua coordonată este multiplicatorul înainte de |1⟩. Matricele porților principale cu un singur qubit arată astfel:

Iată un exemplu de utilizare a porții Not:

X * |0⟩ = X * (1|0⟩ + 0|1⟩) = 0|0⟩ + 1|1⟩ = |1⟩

Factorii din fața stărilor de bază se numesc amplitudini și sunt numere complexe. Modulul unui număr complex este egal cu rădăcina sumei pătratelor părților reale și imaginare. Pătratul mărimii amplitudinii în fața stării de bază este egal cu probabilitatea de a obține această stare de bază la măsurarea unui qubit, deci suma pătratelor mărimii amplitudinilor este întotdeauna egală cu 1. Am putea folosi matrici arbitrare pentru transformări peste qubiți, dar datorită faptului că vectorul normă (lungimea) trebuie să fie întotdeauna egal cu 1 (suma probabilităților tuturor rezultatelor este întotdeauna egală cu 1), transformarea noastră trebuie să păstreze norma vectorului . Aceasta înseamnă că transformarea trebuie să fie unitară, iar matricea corespunzătoare trebuie să fie unitară. Reamintim că transformarea unitară este inversabilă și UU † =I.

Pentru a lucra mai clar cu qubiții, aceștia sunt reprezentați ca vectori pe sfera Bloch. În această interpretare, porțile cu un singur qubit reprezintă rotația vectorului qubit în jurul uneia dintre axe. De exemplu, poarta Not(X) rotește vectorul qubit cu Pi în raport cu axa X. Astfel, starea |0>, reprezentată printr-un vector îndreptat drept în sus, intră în starea |1> îndreptată direct în jos. Starea qubitului pe sfera Bloch este determinată de formula cos(θ/2)|0⟩+e iϕ sin(θ/2)|1⟩

Porți cuantice de doi qubiți

Pentru a construi algoritmi, doar porțile cu un singur qubit nu sunt suficiente pentru noi. Sunt necesare porți care efectuează transformări în funcție de anumite condiții. Principalul astfel de instrument este poarta de doi qubiți CNOT. Această poartă este aplicată la doi qubit și inversează al doilea qubit numai dacă primul qubit este în starea |1⟩. Matricea porții CNOT arată astfel:

Iată un exemplu de aplicație:

CNOT *|10⟩ = CNOT * (0|00⟩ + 0|01⟩ + 1|10⟩ + 0|11⟩) = 0|00⟩ + 0|01⟩ + 1|11⟩ + 0|10⟩ = |11⟩

Utilizarea unei porți CNOT este echivalentă cu efectuarea unei operații XOR clasice și scrierea rezultatului în al doilea qubit. Într-adevăr, dacă ne uităm la tabelul de adevăr al operatorilor XOR și CNOT, vom vedea corespondența:

XOR			CNOT
0	0	0	00	00
0	1	1	01	01
1	0	1	10	11
1	1	0	11	10

Poarta CNOT are o proprietate interesantă - după aplicarea ei, qubiții se încurcă sau se desfășoară, în funcție de starea inițială. Acest lucru va fi arătat în articolul următor, în secțiunea despre paralelismul cuantic.

Construcția algoritmului - implementare clasică și cuantică

Cu un arsenal complet de porți cuantice, putem începe să dezvoltăm algoritmi cuantici. Într-o reprezentare grafică, qubiții sunt reprezentați prin linii drepte - „șiruri” pe care sunt suprapuse porți. Porțile Pauli cu un singur qubit sunt desemnate prin pătrate obișnuite, în interiorul cărora este reprezentată axa de rotație. Poarta CNOT pare puțin mai complicată:

Exemplu de utilizare a porții CNOT:

Una dintre cele mai importante acțiuni ale algoritmului este măsurarea rezultatului obținut. Măsurarea este de obicei indicată printr-o scară de arc cu o săgeată și o desemnare cu privire la axa care se face măsurarea.

Deci, să încercăm să construim un algoritm clasic și cuantic care adaugă 3 la argument.

Însumarea numerelor obișnuite într-o coloană implică efectuarea a două acțiuni pe fiecare cifră - suma cifrelor cifrei în sine și suma rezultatului cu un transfer din operația anterioară, dacă a existat un astfel de transfer.

În reprezentarea binară a numerelor, operația de însumare va consta din aceleași acțiuni. Iată codul în python:

Arg = #set the argument result = #inițializați rezultatul carry1 = arg & 0x1 #add with 0b11, astfel încât transportul de la bitul low va apărea dacă argumentul are low bit = 1 result = arg ^ 0x1 #add the low bits purta2 = purta1 | arg #add cu 0b11, astfel încât transferul de la bitul înalt va apărea dacă argumentul are bitul înalt = 1 sau a existat o transportare din rezultatul bitului scăzut = arg ^ 0x1 #adăugați rezultatul biților înalți ^= carry1 #aplicați carry din rezultatul bitului scăzut ^= carry2 #aplicați carry de la cea mai semnificativă imprimare de biți (rezultat)
Acum să încercăm să dezvoltăm un program similar pentru un computer cuantic:

În această schemă, primii doi qubiți sunt argumentul, următorii doi sunt transferurile, iar restul de 3 sunt rezultatul. Așa funcționează algoritmul.

1. Primul pas către barieră este să setați argumentul în aceeași stare ca în cazul clasic - 0b11.
2. Folosind operatorul CNOT, calculăm valoarea primului carry - rezultatul operației arg & 1 este egal cu unu numai atunci când arg este egal cu 1, caz în care inversăm al doilea qubit.
3. Următoarele 2 porți implementează adăugarea celor mai puțin semnificativi biți - transferăm qubitul 4 în starea |1⟩ și scriem rezultatul XOR în el.
4. Dreptunghiul mare reprezintă poarta CCNOT, o prelungire a porții CNOT. Această poartă are doi qubiți de control, iar al treilea este inversat numai dacă primii doi sunt în starea |1. Combinația dintre 2 porți CNOT și o poartă CCNOT ne oferă rezultatul operației clasice carry2 = carry1 | arg. Primele 2 porți transportă la una dacă una dintre ele este 1, iar poarta CCNOT se ocupă de cazul când ambele sunt egale cu unul.
5. Adăugăm cei mai mari qubiți și qubiții de transfer.

Concluzii intermediare

Rulând ambele exemple, obținem același rezultat. Pe un computer cuantic, acest lucru va dura mai mult, deoarece compilarea suplimentară în codul de asamblare cuantică trebuie efectuată și trimisă în cloud pentru execuție. Utilizarea calculului cuantic ar avea sens dacă viteza de realizare a operațiilor lor elementare - porțile - ar fi de multe ori mai mică decât în ​​modelul clasic.

Măsurătorile experților arată că execuția unei porți durează aproximativ 1 nanosecundă. Deci, algoritmii pentru un computer cuantic nu ar trebui să îi copieze pe cei clasici, ci să folosească la maximum proprietățile unice ale mecanicii cuantice. În articolul următor ne vom uita la una dintre principalele astfel de proprietăți - paralelismul cuantic - și vom vorbi despre optimizarea cuantică în general. Apoi vom identifica cele mai potrivite domenii pentru calculul cuantic și vom descrie aplicațiile acestora.

Pe baza materialelor

Richard Feynman a observat că anumite procese mecanice cuantice nu pot fi simulate eficient pe un computer clasic. Această observație a condus la afirmația mai generală că procesele cuantice sunt mai eficiente decât cele clasice pentru efectuarea calculelor. Această ipoteză a fost confirmată de Peter Shor, care a dezvoltat un algoritm cuantic pentru factorizarea numerelor întregi în factori primi în timp polinomial.

În sistemele cuantice, spațiul de calcul crește exponențial odată cu dimensiunea sistemului, ceea ce face posibil paralelismul exponențial. Acest paralelism poate duce la algoritmi cuantici care sunt exponențial mai rapizi decât cei clasici.

Abia la mijlocul anilor 1990, teoria calculatoarelor cuantice și a calculului cuantic s-a stabilit ca un nou domeniu al științei. Aparent, matematicianul maghiar J. von Neumann a fost primul care a atras atenția asupra posibilității dezvoltării logicii cuantice. Cu toate acestea, la acel moment, nu fuseseră încă create computere cuantice, ci și obișnuite, clasice. Și odată cu apariția acestuia din urmă, principalele eforturi ale oamenilor de știință au vizat în primul rând căutarea și dezvoltarea de noi elemente pentru ei (tranzistoare și apoi circuite integrate), și nu crearea de dispozitive de calcul fundamental diferite.

În anii 1960, fizicianul american R. Landauer a încercat să atragă atenția asupra faptului că calculele sunt întotdeauna un anumit proces fizic, ceea ce înseamnă că este imposibil să înțelegem limitele capacităților noastre de calcul fără a specifica ce implementare fizică îi corespund. Din păcate, la acea vreme, opinia dominantă în rândul oamenilor de știință era că calculul era un fel de procedură logică abstractă care ar trebui studiată de matematicieni, nu de fizicieni.

Pe măsură ce computerele au devenit mai răspândite, oamenii de știință cuantici au ajuns la concluzia că era practic imposibil să se calculeze în mod direct starea unui sistem în evoluție format din doar câteva zeci de particule care interacționează, cum ar fi o moleculă de metan CH4. Acest lucru se explică prin faptul că, pentru a descrie pe deplin un sistem complex, este necesar să se păstreze în memoria computerului un număr exponențial de mare (din punct de vedere al numărului de particule) de variabile, așa-numitele amplitudini cuantice. A apărut o situație paradoxală: cunoscând ecuația evoluției, cunoscând cu suficientă acuratețe toate potențialele de interacțiune ale particulelor între ele și starea inițială a sistemului, este aproape imposibil să-i calculăm viitorul, chiar dacă sistemul este format doar din 30 de electroni într-un puț de potențial și este disponibil un supercalculator cu RAM, al cărui număr de biți este egal cu numărul de atomi din regiunea vizibilă a Universului. În același timp, pentru a studia dinamica unui astfel de sistem, puteți pur și simplu efectua un experiment cu 30 de electroni, plasându-i într-un anumit potențial și stare inițială. Acest lucru, în special, a fost remarcat de matematicianul rus Yu. I. Manin, care în 1980 a subliniat necesitatea dezvoltării unei teorii a dispozitivelor de calcul cuantic. În anii 1980, aceeași problemă a fost studiată de fizicianul american P. Benev, care a arătat clar că un sistem cuantic poate efectua calcule, precum și de savantul englez D. Deutsch, care a dezvoltat teoretic un computer cuantic universal care este superior acestuia. omologul clasic.

R. Feynman a atras multă atenție asupra problemei dezvoltării computerelor cuantice. Datorită apelului său de autoritate, numărul specialiștilor care au acordat atenție calculului cuantic a crescut de multe ori.

Cu toate acestea, pentru o lungă perioadă de timp, a rămas neclar dacă puterea de calcul ipotetică a unui computer cuantic ar putea fi folosită pentru a accelera soluționarea problemelor practice. În 1994, matematicianul american P. Shore a propus un algoritm cuantic care permite factorizarea rapidă a numerelor mari. În comparație cu cea mai bună metodă clasică cunoscută astăzi, algoritmul cuantic al lui Shor oferă o accelerare multiplă a calculelor și, cu cât numărul factorizat este mai lung, cu atât câștigul de viteză este mai mare. În cazul algoritmului clasic, o creștere a numărului factorizat duce la o creștere exponențială a resurselor necesare. De exemplu, factorizarea unui număr de 500 de cifre necesită de 100 de milioane de ori mai multe iterații decât un număr de 250 de cifre. Pentru algoritmul lui Shor, cantitatea de resurse necesare crește doar polinom - un număr de 500 de cifre necesită doar de 8 ori mai mulți pași decât un număr de 250 de cifre.

Se dovedește că folosind legile mecanicii cuantice, este posibil să se construiască calculatoare pentru care problema factorizării (și multe altele!) nu va fi dificilă. Se estimează că un computer cuantic cu doar aproximativ 10 mii de biți cuantici de memorie poate transforma un număr de 1000 de cifre în factori primi în doar câteva ore! Algoritmul de factorizare rapidă este, de exemplu, de mare interes practic pentru diverse agenții de informații care au acumulat bănci de mesaje necriptate.

În 1997, L. Grover a propus un algoritm cuantic pentru căutarea rapidă într-o bază de date neordonată. (Un exemplu de astfel de baze de date este o carte telefonică în care numele abonaților nu sunt aranjate alfabetic, ci într-o manieră arbitrară.) Sarcina de căutare, selectare a elementului optim dintre numeroasele opțiuni este foarte des întâlnită în domeniul economic, militar, probleme de inginerie și în jocurile pe calculator. Algoritmul lui Grover permite nu numai să accelereze procesul de căutare, ci și să dubleze aproximativ numărul de parametri luați în considerare la alegerea optimului.

Crearea reală a calculatoarelor cuantice este îngreunată de o problemă serioasă - erori sau interferențe. Faptul este că același nivel de interferență strică procesul de calcul cuantic mult mai intens decât calculul clasic. P. Shor a schițat modalități de a rezolva această problemă în 1995, dezvoltând o schemă pentru codificarea stărilor cuantice și corectarea erorilor din acestea.

Timpul necesar pentru efectuarea anumitor calcule poate fi redus prin utilizarea procesoarelor paralele. Pentru a obține o reducere exponențială a timpului, numărul de procesoare și, prin urmare, cantitatea de spațiu fizic, trebuie crescut exponențial. Într-un sistem cuantic, pentru a reduce timpul exponențial, tot ceea ce este necesar este o creștere liniară a volumului spațiului fizic necesar. Acest fenomen este direct legat de paralelismul cuantic (Deutsch și Josha, 1992).

Mai este altul caracteristică importantă. În timp ce sistemul cuantic efectuează calcule, accesul la rezultate este limitat. Procesul de accesare a rezultatelor este un proces de măsurare care perturbă starea cuantică, distorsionând-o. Poate părea că situația de aici este și mai rea decât în ​​cazul calculelor clasice. Rezultă că putem număra doar rezultatul executării unuia dintre procesele paralele și, deoarece măsurarea este probabilistică, nici nu putem alege ce rezultat al procesului vom primi.

Dar în ultimii câțiva ani, oamenii au descoperit modalități creative de a rezolva în mod inteligent problema de măsurare pentru a profita de paralelismul cuantic. Manipulațiile de acest fel nu au analogi în teoria clasică și necesită utilizarea unor tehnici de programare neconvenționale. O astfel de tehnică este de a manipula o stare cuantică astfel încât să poată fi citită o proprietate comună a tuturor valorilor rezultate, cum ar fi simetria sau perioada unei funcții. O tehnică similară este utilizată în algoritmul de factorizare al lui Shor. Într-o altă abordare, stările cuantice sunt transformate în așa fel încât să crească probabilitatea de a citi rezultatul computațional care ne interesează. Această tehnică este folosită în algoritmul de căutare al lui Grover

Din când în când vedem o serie de știri despre calculul cuantic. Acest subiect atrage multă atenție, o companie susținând că are algoritmul de criptare de care veți avea nevoie în curând, deoarece computerele cuantice fac inutili algoritmii de criptare actuali.

Pentru o persoană curios, astfel de afirmații ridică întrebări. Ce este calculul cuantic (Figura 1)? E real? Dacă da, cum funcționează? Și cum se leagă asta cu criptografia? Apoi apar mai multe întrebări personale. Ar putea calcularea cuantică să schimbe modul în care proiectez? Ar trebui să studiez acest material?

Chiar și în redările artiștilor, elementele de calcul cuantic nu seamănă cu nimic din lumea hardware digitală.

Figura 1 – Vizualizarea elementelor de calcul cuantic

Se pare că acestea nu sunt întrebări foarte simple de studiat. Literatura relevantă se încadrează în principal într-unul dintre cele două genuri. Prima este destinată unui public general și tratează mecanica cuantică ca pe un iad: întunecată, posibil periculoasă și complet de neînțeles. După ce citești o astfel de literatură, este destul de dificil să tragi concluzii.

Al doilea gen este complet diferit, dar la fel de „util”, scris de experți pentru a impresiona pe alți experți. Acest gen se caracterizează prin folosirea unor termeni precum mașina Turing, numele lui Richard Feynman, spațiul Hilbert și transformarea Hadamard, toate cele de mai sus și încă aproximativ 75 de cuvinte, urmate de o încurcătură de ecuații cu terminologie necunoscută și inexplicabilă. Desigur, vă amintiți cu toții bine ce înseamnă |0>!

Trei universuri paralele

Unul dintre motivele pentru care acest subiect este atât de complex este că calculul cuantic se întinde pe trei discipline cu terminologie și interese foarte diferite. Totul a început cu fizicienii teoreticieni. În 1980, fizicianul Paul Benioff ( Paul Benioff) de la Laboratorul Național Argonne a descris modul în care unele efecte mecanice cuantice ar putea fi utilizate pentru a implementa o mașină Turing. Doi ani mai târziu, celebrul fizician Richard Feynman a pus și el problema unui computer care folosește comportamentul cuantic.

Dar ideea a fost preluată de un grup complet diferit: informaticieni și matematicieni. Luând din fizică ideile de bază ale bitului cuantic (qubit) și transformărilor unitare reversibile (pe care le-au numit porți cuantice sau cuantile), oamenii de știință în computer au studiat ce calcule ar putea fi efectuate dacă ar exista qubiții și porțile cuantice ideale. Ei au găsit cazuri în care astfel de presupuse calculatoare ar putea fi mult mai rapide decât computerele digitale convenționale.

Acest rezultat i-a determinat pe fizicienii experimentali - un al treilea grup - să înceapă eforturile de a crea dispozitive fizice care ar putea aproxima qubiții ideali și porțile cuantice. Acestea au fost studii lungi, care consumau multe resurse, care încă nu au demonstrat că un computer cuantic cu adevărat funcțional este posibil din punct de vedere fizic. Dar această posibilitate este extrem de încurajatoare.

Câteva precizări

Deci, ce este acest computer imaginar care ne interesează? Să lămurim mai întâi unele neînțelegeri. Un computer cuantic nu este un computer obișnuit care simulează fenomene mecanice cuantice. Nici acesta nu este un computer digital obișnuit, construit din niște tranzistori (de la sfârșitul Legii lui Moore) atât de mic încât să stocheze sau să schimbe cuante individuale de energie.

În schimb, calculatoarele cuantice sunt mașini bazate pe un comportament unic descris de mecanica cuantică care este complet diferit de comportamentul sistemelor clasice. Una dintre aceste diferențe este capacitatea unei particule sau a unui grup de particule, într-o anumită privință, de a fi în doar două stări de bază cuantice discrete - să le numim 0 și 1. Ne vom lipsi aici de paranteze amuzante (notații adoptate în teoria cuantică - adăugate de Exemple de acest fel pot fi electronii de spin, polarizarea fotonului sau încărcarea cu puncte cuantice.

În al doilea rând, calculul cuantic depinde de proprietatea suprapunerii - capacitatea contraintuitivă a unei particule de a fi într-o combinație a ambelor stări de bază 0 și 1 în același timp, până când se face o măsurătoare. Odată ce măsurați o astfel de stare, aceasta se transformă într-un 0 sau 1 și toate celelalte informații dispar. Mecanica cuantică descrie corect o astfel de stare combinată ca suma a două stări de bază, fiecare dintre ele înmulțită cu un factor complex. Valoarea totală a acestor coeficienți este întotdeauna egală cu 1. Această stare poate fi reprezentată ca vector unitar, începând de la origine și terminând undeva pe o sferă numită sfera Bloch, care este prezentată în Figura 2. Punctul cheie aici este că pătratul coeficientului complex pentru starea de bază 0 reprezintă probabilitatea ca rezultatul măsurării, qubitul va fi detectat în starea de bază 0, în mod similar pentru starea de bază 1. Și când faceți o măsurătoare, veți obține întotdeauna fie exact starea 0, fie exact starea 1.

Figura 2 – Sfera Bloch – una dintre modalitățile de a vizualiza suprapunerea cuantică într-un qubit

Aceasta (proprietatea de suprapunere - adăugată de traducător) este importantă deoarece permite qubitului să fie în ambele stări 0 și 1 în același timp. Prin urmare, un registru format din n qubiți poate „conține” simultan toate numerele binare posibile cu lungimea de n biți. Acest lucru permite unui computer cuantic să efectueze o singură operație nu doar pe un număr întreg de n biți, ci și pe toate numerele întregi posibile de n biți simultan - paralelism foarte semnificativ pe măsură ce n crește.

În al treilea rând, calculul cuantic depinde de capacitatea unei porți cuantice de a schimba acești coeficienți și, prin urmare, de probabilitatea de a măsura orice număr dat, într-un mod previzibil. Dacă începeți cu o stare în care toți coeficienții din toți qubiții sunt egali și apoi măsurați toți qubiții dintr-un registru, este la fel de probabil să găsiți orice șir de biți între un șir cu toate zerourile și un șir cu toate cele, inclusiv. Dar prin rularea acestei stări inițiale printr-o secvență aleasă cu grijă de porți cuantice, un computer cuantic poate modifica acești coeficienți, astfel încât starea pe care este cel mai probabil să o măsurați ca rezultat este rezultatul unor calcule, de exemplu, este foarte probabil să măsurați biții unui număr care este un pătrat perfect.

Computer pe hârtie

Dar ce legătură au toate acestea cu computerul real? Pentru a răspunde la această întrebare, trebuie să ne îndreptăm atenția de la fizicienii teoreticieni la informaticieni și matematicienii. Pentru a obține rezultate practice, trebuie să putem mapa registrul qubit într-o suprapunere specifică de stări. Avem nevoie de porți cuantice, eventual fire și un fel de dispozitive de ieșire.

Toate acestea sunt ușor pentru informaticieni - ei pot pur și simplu presupune că aceste idei au fost deja implementate în viața reală. Cu toate acestea, ei vor trebui să facă concesii mecanicii cuantice. Pentru a evita încălcarea legile fizicii cuantice, oamenii de știință trebuie să solicite ca porțile cuantice să fie reversibile - puteți pune rezultatul la ieșire și puteți obține valorile corecte de intrare la intrare. Și insistă că porțile cuantice trebuie să fie transformări unitare. Conform algebrei matriceale, aceasta înseamnă că atunci când treceți o stare de qubit printr-o poartă cuantică, starea rezultată va fi fie 0, fie 1 atunci când este măsurată, iar suma probabilităților pătratelor acestor coeficienți va rămâne o unitate egală.

Rețineți că aceste porți cuantice, chiar și în teorie, sunt foarte diferite de porțile logice obișnuite. De exemplu, majoritatea funcțiilor booleene nu sunt inversabile. Nu există nicio modalitate de a scoate intrarea de la o poartă NAND decât dacă ieșirea este 0. Și, desigur, porțile logice funcționează numai cu unu și zero (stările 1 și 0), în timp ce porțile cuantice funcționează prin rotirea unui vector în interiorul unei sfere Bloch. De fapt, nu există nimic în comun între ei, cu excepția numelui.

Oamenii de știință în informatică au descoperit că un set foarte mic de porți cuantice este suficient pentru a emula o mașină Turing - doar un set de porți cuantice cu o singură intrare și o poartă cuantică cu două intrări. Cel mai des folosit exemplu de poartă cuantică cu două intrări este „NU controlat” (CNOT). Această funcție reversibilă fie inversează starea vectorială a unui qubit, fie o lasă neschimbată, în funcție de starea celui de-al doilea qubit. Este mai mult ca o analogie XOR cuantică.

Beneficii posibile

Încă nu am răspuns la întrebarea cum pot fi folosite toate acestea. Răspunsul este că, dacă conectați suficiente porți cuantice împreună într-un mod adecvat și dacă puteți pregăti qubiți de intrare reprezentând toate numerele posibile din domeniul dvs. de date de intrare, atunci la ieșirea matricei de porți cuantice puteți, în teorie, măsura biți care reprezintă valorile unei funcții utile.

Să dăm un exemplu. În 1994, matematicianul Peter Shor, de la Bell Labs, a dezvoltat un algoritm pentru factorizarea numerelor foarte mari folosind rutine cuantice. Această factorizare este o problemă vitală în matematica aplicată, deoarece nu există o soluție analitică: singura cale este încercarea și eroarea și nu puteți face algoritmul decât prin alegerea mai abil a numerelor de încercare adecvate. În consecință, atunci când faceți numărul de intrare foarte mare, cantitatea de încercări și erori devine enormă. Nu este o coincidență că aceasta este baza algoritmilor de criptare precum RSA. Cifrurile RSA și curbe eliptice sunt greu de spart, mai ales pentru că este atât de dificil să factorizezi numere uriașe.

Algoritmul lui Shor a combinat unele calcule tradiționale cu două funcții cuantice care accelerează direct algoritmul în partea de încercare și eroare, încercând în esență toate numerele posibile în același timp, o demonstrație a algoritmului este dată în Figura 3. Una dintre aceste funcții cuantice realizează exponentiație modulară, iar celălalt realizează o versiune cuantică a transformării rapide Fourier (FFT). Din motive pe care doar un matematician le-ar putea iubi, dacă ar fi să introducem un set de n qubiți pregătiți astfel încât împreună să reprezinte toate numerele binare posibile până la lungimea n, atunci în porțile cuantice diferitele stări dintr-o suprapunere se anulează reciproc - ca interferența a două raze de lumină coerente - și ne rămâne cu o anumită structură de stări în registrul de ieșire.

Figura 3 – Algoritmul lui Shor depinde de rutinele cuantice pentru exponențiarea modulară și operațiile FFT. (Imaginea prin amabilitatea lui Tyson Williams)

Această procedură nu produce un factor prim - este doar un pas intermediar care permite calcularea unui posibil factor prim. Acest calcul se face prin măsurarea qubitilor - rețineți că ne aflăm în domeniul posibilității, dar nu al preciziei, de a măsura starea cea mai probabilă a fiecărui qubit - și apoi făcând o mulțime de calcule de rutină pe un procesor obișnuit (CPU) pentru a face sigur ca rezultatul este corect.

Toate acestea pot părea extrem de complicate și imposibile. Dar capacitatea exponențiării cuantice și a FFT cuantică de a lucra simultan cu toate puterile posibile de 2 pentru a găsi cel mai mare factor prim face ca algoritmul lui Shor să fie mai rapid decât calculele convenționale pentru numere mari, chiar și atunci când se utilizează rutine cuantice teoretice destul de lente.

Algoritmul lui Shor este un exemplu strălucitor de calcul cuantic, deoarece este atât diferit de calculul convențional, cât și potențial extrem de important. Dar el nu este singur. Institutul Național de Standarde și Tehnologie din SUA (NIST) menține o bibliotecă mare de algoritmi de calcul cuantic în Grădina Zoologică cu algoritmi cuantici, la math.nist.gov/quantum/zoo/.

Acești algoritmi sunt doar exerciții de matematică? E prea devreme pentru a spune cu siguranță. Dar, în practică, cercetătorii au creat de fapt calculatoare cuantice de laborator cu mai mulți qubiți de lucru. Aceste mașini au luat în considerare cu succes numărul 15 (făcut pentru prima dată la IBM în 2001), producând probabil 3 și 5, iar recordul mondial actual este de 21 (realizat de o echipă multi-instituțională în 2012). Deci, pentru un număr mic, ideea funcționează. Adecvarea acestei abordări pentru un număr mare poate fi testată în viitor numai pe mașini cu mai mulți qubiți. Și acest lucru aduce problema la un nivel practic.

Calea spre Realizare

Pentru a crea dispozitive funcționale de calcul cuantic, este necesar să parcurgeți o serie de etape de implementare. Trebuie să construim qubiți funcționali - nu doar cinci, ci mii. Trebuie să organizăm o structură de porți cuantice și echivalentul firelor - cu excepția cazului în care putem face ca porțile să acționeze direct asupra stării din registrul cuantic de intrare. Toate acestea sunt probleme complexe, iar calendarul pentru soluționarea lor este imprevizibil.

Din păcate, problemele sunt legate nu atât de noutatea problemelor, cât de legile mecanicii cuantice și ale fizicii clasice. Poate cea mai importantă și mai puțin familiară dintre acestea se numește decoerență. Rolul unui qubit este de a menține un obiect fizic, cum ar fi un ion, un pachet de fotoni sau un electron, astfel încât să îl putem influența și, în cele din urmă, să măsuram o cantitate cuantificată, cum ar fi sarcina sau spinul. Pentru ca această mărime să se comporte mai degrabă într-o manieră cuantică decât clasică, trebuie să putem restricționa starea ei la o suprapunere a două stări de bază pure, pe care le-am numit 0 și 1.

Dar natura sistemelor cuantice este de așa natură încât le leagă de lucrurile din jurul lor, crescând foarte mult numărul posibilelor stări subiacente. Fizicienii numesc această estompare a stărilor pure decoerență. O analogie ar putea fi un fascicul laser coerent într-un ghid de lumină, împrăștiat de neomogenități în material și împrăștiat din suprapunerea a două moduri în lumină complet incoerentă. Scopul creării unui qubit fizic este de a preveni decoerența cât mai mult timp posibil.

În practică, aceasta înseamnă că chiar și un singur qubit este un instrument complex de laborator, poate folosind lasere sau transmițătoare radio de înaltă frecvență, câmpuri electrice și magnetice controlate cu precizie, dimensiuni precise, materiale speciale și, eventual, răcire criogenică. Utilizarea sa este în esență o procedură experimentală complexă. Chiar și cu toate aceste eforturi, astăzi acest „cât mai lung posibil” se măsoară în zeci de microsecunde. Astfel, aveți foarte puțin timp pentru a efectua calcule cuantice înainte ca qubiții dvs. să-și piardă coerența. Adică înainte ca informația să dispară.

Astăzi, aceste limitări exclud posibilitatea unor registre cuantice mari sau calcule care necesită mai mult de câteva microsecunde. Cu toate acestea, cercetările sunt în curs de desfășurare în microelectronică pentru a crea rețele mult mai extinse de qubiți și porți cuantice.

Cu toate acestea, această lucrare în sine este oarecum disjunsă, deoarece nu este încă sigur ce fenomen fizic să folosească pentru a stoca stările cuantice. Există modele de qubit care cuantizează polarizarea fotonilor, sarcina electronilor prinși în puncte cuantice, spinul net al ionilor suprarăciți într-o capcană, încărcarea într-un dispozitiv numit transmon și alte câteva abordări.

Tipul de qubit pe care îl alegeți va determina în mod natural implementarea porții cuantice. De exemplu, puteți utiliza interacțiunea impulsurilor radio cu spinurile interne în molecule dintr-o capcană sau interacțiunea divizoarelor de fascicul cu moduri de fotoni în ghidurile de undă. Evident, esența materiei se află adânc în domeniul fizicii experimentale. Și, după cum am menționat deja, implementarea qubit-urilor sau porților cuantice necesită utilizarea unui număr mare de echipamente diferite, de la logica digitală la lasere sau transmițătoare radio, antene, până la răcitoare criogenice.

Implementarea unui qubit depinde, de asemenea, de modul în care este măsurată starea qubitului. Este posibil să aveți nevoie de un fotometru sau bolometru ultra-sensibil, o punte rezistivă sau un alt dispozitiv incredibil de sensibil pentru a măsura qubiții și a forța starea de suprapunere în starea fundamentală. Și, pe deasupra, acest proces de măsurare a stării unui qubit introduce o altă problemă necunoscută pentru calculul tradițional: obținerea unui răspuns greșit.

Îndoieli

Există două tipuri principale de probleme cu extragerea stării fundamentale dintr-un qubit. În primul rând, măsori o suprapunere cuantică, nu o mărime clasică. Presupunând că qubit-ul rămâne coerent, veți obține una sau alta dintre stările de bază, dar nu puteți fi sigur în prealabil pe care o veți obține: puteți fi sigur doar că probabilitatea de a obține o anumită stare va fi pătratul ( modulul – adăugat de traducător) al coeficientului acestei stări în suprapunere. Dacă măsurați un qubit în exact aceeași stare de o sută de ori, veți obține o distribuție de zerouri și unități care converge către pătratele coeficienților.

Deci nu știți dacă starea de referință pe care ați măsurat-o într-un studiu are de fapt cea mai mare probabilitate. Odată ce ați citit registrul de ieșire cuantică, măsurați biții, setându-i astfel pe toți la stările lor de bază, aveți trei opțiuni. S-ar putea să te îndoiești că ai răspunsul corect și să mergi mai departe. Puteți verifica cu calcule tradiționale, cum face algoritmul lui Shor, pentru a vedea dacă numărul pe care l-ați crezut că este de fapt soluția corectă. Sau, puteți repeta calculul de un număr mare de ori, secvențial sau în paralel și să luați rezultatul care apare cel mai frecvent. De asemenea, vă puteți organiza calculele astfel încât răspunsul să fie o distribuție de probabilitate a stărilor subiacente, mai degrabă decât un anumit număr binar. În acest caz, este necesară și repetarea.

Acest lucru este valabil chiar și pentru un computer cuantic perfect teoretic. Dar implementarea reală mai are o problemă: zgomot clasic vechi. Chiar dacă totul merge bine, nu există o decoerență a qubiților, iar calculul este conceput pentru a produce un răspuns cu o probabilitate foarte mare, tot observați qubiții în timp ce încercați să măsurați cantități fizice foarte, foarte mici. Zgomotul este încă acolo. Din nou, singura soluție este fie să detectați eroarea prin calcule suplimentare, fie să efectuați calculele de atâtea ori încât să fiți dispus să acceptați orice incertitudine rămasă ca rezultat. Conceptul de răspuns corect garantat este străin de însăși esența calculului cuantic.

Dacă toate acestea nu pictează pictura roz viitorul calculului cuantic, atunci acest lucru ar trebui luat foarte în serios. Căutarea este în curs cea mai buna alegere pentru a implementa qubiți, deși răspunsul poate depinde de algoritm. Oamenii de știință din microelectronică lucrează la miniaturizarea componentelor cuantice folosind noi materiale și structuri care ar permite crearea unor rețele foarte mari de dispozitive de calcul cuantic care ar putea fi produse în masă ca cipurile de procesoare tradiționale. Oamenii de știință în domeniul informaticii dezvoltă prototipuri de asamblare și compilatoare care pot traduce un algoritm în configurația registrelor cuantice și a porților cuantice într-o anumită tehnologie.

Merita? Iată un fapt. Shore a calculat că un computer hibrid modest – adică cuantic plus convențional – ar putea sparge puternicul algoritm de criptare RSA mai repede decât l-ar putea cripta un computer convențional. S-au găsit rezultate similare pentru probleme precum sortarea și descurcarea altor probleme complexe de matematică similare. Deci, există destule promisiuni în acest domeniu pentru a-i menține entuziasmați pe cercetători. Dar ar fi frumos să vezi toate astea încă în viață.