Algoritmi cuantici vs clasici

Fenomene importante ale mecanicii cuantice, cum ar fi superpoziția și măsurarea (prin experimentele Stern-Gerlach și Mach-Zehnder). Deși computerele cuantice pot, în principiu, să încalce protocoalele clasice de criptare, ele pot fi folosite și pentru a crea noi canale de comunicare sigure. În plus, putem aplica porți logice cuantice la qubiti pentru a efectua calcule cuantice. Prin inseparabilitate, teleportăm informațiile dintr-un qubit necunoscut către un alt qubit. Aceasta este o realizare destul de substanțială.

Un aspect fundamental al calculului cuantic este reprezentat de algoritmii cuantici. Simplu spus, având în vedere o sarcină pe care dorim să o îndeplinească computerul cuantic, un algoritm cuantic este modul în care computerul cuantic îndeplinește această sarcină pe niște qubiti de intrare. Un exemplu tipic de algoritm pe un computer clasic este algoritmul de căutare, de exemplu, căutarea într-o bază de date pentru a găsi un prieten din lista de prieteni. De fapt, computerele cuantice pot implementa, de asemenea, algoritmi de căutare. Algoritmul lui Grover, unul dintre cei mai cunoscuți doi algoritmi de calcul cuantic (celălalt fiind algoritmul lui Shor, despre care am aflat în Capitolul 5), folosește inseparabilitatea pentru a căuta într-o bază de date mai rapid decât orice computer clasic. Deși studierea algoritmului lui Grover este în afara domeniului de aplicare al acestui curs, vom studia algoritmul Deutsch-Jozsa, care arată cum computerele cuantice pot efectua calcule mai rapid decât computerele clasice. După studierea acestui algoritm, veți avea o bază pentru a învăța algoritmi mai complicați.

Puterea calculului cuantic

Principalul avantaj pe care îl au computerele cuantice față de computerele clasice este paralelismul. Deoarece qubiții pot fi într-o suprapunere de stări, un computer cuantic poate efectua o operație simultan pe toate stările. Să presupunem că vrem să știm rezultatul aplicării unei funcții f(x) unui număr x. Două calcule clasice sunt necesare pentru a găsi rezultatul pentru x = 0 și pentru x = 1, în timp ce un computer cuantic poate evalua ambele răspunsuri în paralel, așa cum se arată în Fig. 9.1.

Fig. 9.1 Un calculator clasic execută două operații pentru a opera asupra a două informații. Un calculator cuantic cu un qubit poate opera asupra a două informații clasice simultan.

Dacă am dori să calculăm f(x) pentru x = 2 (reprezentat ca 10 în binar) și x = 3 (reprezentat ca 11), ar trebui să adăugăm un al doilea qubit. Computerul cuantic de doi qubiți poate apoi evalua toate cele patru posibilități simultan, așa cum se arată în Fig. 9.2.

Fig. 9.2 Un calculator clasic execută patru operații pentru a opera cu patru informații. Un calculator cuantic cu doi qubiți poate opera simultan cu patru informații clasice.

Întrebarea 1 Câte informații poate procesa în paralel un computer cuantic de trei qubiți? Scrieți toate stările.

Stările posibile sunt

|000⟩, |001⟩, |010⟩, |100⟩, |011⟩, |110⟩, |101⟩, |111⟩ → 8 informații.   (9.1)

Adăugarea unui qubit la un computer cuantic îi dublează puterea de procesare! Pentru un computer clasic, trebuie să dublați numărul de fire din procesor pentru a obține dublu puterea de procesare[1]. Cu toate acestea, cu un computer cuantic, trebuie doar să adăugați un singur qubit pentru a dubla puterea de procesare! În plus, un sistem de n-qubiți poate efectua anumite 2ⁿ operații simultan!

Separat de problema puterii de procesare este un concept cunoscut sub numele de memorie. Într-un computer clasic, pe un laptop standard pe 64 de biți, fiecare număr poate fi reprezentat în reprezentarea binară pe 64 de biți (o extensie simplă a reprezentării binare pe 8 biți despre care ați aflat deja). Dacă doriți patru numere pe o mașină pe 64 de biți în același timp, atunci trebuie să aveți 4 x 64 = 256 biți de memorie pe hard disk pentru a le stoca. Pe un computer clasic pe 64 de biți, pentru M numere diferite, aveți nevoie de M x 64 biți de memorie; adică, biții necesari pentru memorie sunt liniari în funcție de numărul de numere necesare. Cu toate acestea, pe un computer cuantic de n qubiți, pot exista 2ⁿ coeficienți diferiți ai stării cuantice care ar putea, în principiu, să rețină numerele și, prin urmare, pot fi utilizați ca memorie; adică, qubiții necesari pentru memorie sunt logaritmici în funcție de numărul de numere dorite.

Deoarece computerele clasice sunt foarte avansate și au o putere de procesare mare și terabyți de memorie, computerele clasice pot simula computere cuantice mici. Întrucât adăugarea unui singur qubit ar dubla memoria necesară, cel mai mare supercomputer din SUA[2] ar putea simula doar un computer cuantic de 46 de qubiți. Începând cu 2018, Google are un computer cuantic cu un cip cuantic (numit Bristlecone) care are 72 de qubiți.

Limitări

Deși paralelismul sună uimitor în teorie, nu este imediat util în sine. Un calcul cuantic poate calcula o suprapunere a celor 2ⁿ numere, însă este necesară efectuarea unei măsurători pentru a extrage informații din computerul cuantic. O singură măsurătoare va afișa doar unul dintre aceste răspunsuri și ulterior va restrânge suprapunerea într-o stare de bază. Gândiți-vă la asta ca și cum cele 2ⁿ numere ar fi toate pe un blocnotes secret pe care nu îl putem vedea, iar natura vă arată câte o pagină aleatorie pe rând, apoi arde blocnotesul. Ar trebui să rulați computerul cuantic de cel puțin 2ⁿ ori pentru a obține toate numerele, anulând astfel orice avantaj față de computerele clasice. Ca exemplu în acest sens, computerul cuantic pe doi qubiți poate calcula suprapunerea a|f(00)⟩ + b|f(01)⟩ + c|f(10)⟩ + d|f(11)⟩, dar măsurarea acestei stări va avea ca rezultat f(00), f(01), f(10), SAU f(11). Dacă aveți ghinion, din cauza caracterului aleatoriu al fizicii cuantice, ați putea repeta calculul de patru ori și tot nu veți vedea toate posibilitățile.

Prin urmare, computerele cuantice sunt practice doar pentru anumite tipuri de probleme. Deoarece computerele cuantice sunt construite pe principii ale fizicii cuantice, ne așteptăm intuitiv ca acestea să fie cele mai potrivite pentru simularea directă a fenomenelor cuantice. În general, aceste tipuri de probleme caută corelații între diferite rezultate. Din acest motiv, este în general acceptat faptul că computerele cuantice nu vor înlocui computerele clasice, dar vor putea efectua diferite calcule pe care computerele clasice pur și simplu nu le pot face. Vom studia o problemă exemplu pe care computerul cuantic o poate rezolva mai eficient decât un computer clasic.

Note

[1] Se observă că computerele clasice își dublează puterea de procesare aproximativ la fiecare 18 luni. Aceasta este cunoscută sub numele de legea lui Moore.

[2] Titan de la Laboratorul Oak Ridge din 2018.

Sursa: Ciaran Hughes, Joshua Isaacson, Anastasia Perry, Ranbel F. Sun, Jessica Turner (2021) Quantum Computing for the Quantum Curious, Springer Cham, https://doi.org/10.1007/978-3-030-61601-4, licența CC BY 4.0. Traducere și adaptare: Nicolae Sfetcu