Algoritmul Deutsch-Jozsa în calculul cuantic

Aici oferim o demonstrație că computerele cuantice pot fi mai rapide decât computerele clasice prin construirea explicită a unei probleme.

Enunțul problemei

Fie f(x) o funcție necunoscută care operează pe un singur qubit. Pot exista doar patru funcții diferite care să satisfacă această cerință, iar cele patru funcții diferite sunt prezentate în Tabelul 9.1.

f1	f2	f3	f4
f1(0) = 0	f2(0) = 0	f3(0) = 1	f4(0) = 1
f1(1) = 0	f2(1) = 1	f3(1) = 0	f4(1) = 1

Tabelul 9.1 Există doar patru funcții posibile pentru un singur qubit

O funcție se numește constantă dacă produce întotdeauna același rezultat pentru toate valorile lui x. O funcție se numește echilibrată dacă produce 1 pentru jumătate din toate valorile posibile ale lui x și 0 pentru cealaltă jumătate. Întrebarea adresată computerului este următoarea:

„Este funcția f(x) o funcție constantă sau o funcție echilibrată?”

Pentru acest caz cu un singur qubit, răspunsul la întrebare se face verificând dacă f(0) = f(1). De asemenea, în acest caz cu un singur qubit se dovedește că există doar funcții constante și echilibrate. Cu toate acestea, în sistemele cu mai mulți qubit, există funcții care nu sunt nici constante, nici echilibrate. În scenariul cu mai mulți qubiti, este important ca în enunțul problemei funcția dată computerului cuantic să fie fie constantă, fie echilibrată, și nu altceva.

Întrebarea 2 Care dintre funcțiile din Tabelul 9.1 sunt constante și care sunt echilibrate?

Funcțiile f și f4 sunt constante, în timp ce f2 și f3 sunt echilibrate.

Întrebarea 3 Dacă rulați algoritmul clasic și vedeți că f(0) = 1, puteți spune dacă funcția este constantă sau echilibrată?

Nu, ar putea fi fie funcția echilibrată f3, fie funcția constantă f4. Un computer clasic ar trebui să evalueze atât f(0), cât și f(1) pentru a determina răspunsul. Cum poate un computer cuantic să determine răspunsul cu o singură măsurătoare în loc de două?

Înțelegere conceptuală

Înainte de a parcurge în detaliu algoritmul Deutsch-Jozsa, va fi util să înțelegem o soluție schițată a problemei, pe care o vom demonstra folosind interferometrul Mach-Zehnder. Încă o dată, superpoziția și interferența vor fi proprietățile cheie de utilizat. Configurația experimentală de desen este prezentată în Fig. 9.3. În simularea QuVis, vom modela funcțiile plasând bucăți de sticlă în casetele albastre. Scopul este de a ilustra cum este posibil să clasificăm f(x) fie ca fiind constantă, fie echilibrată, efectuând o singură măsurare. Iată cum poate fi implementat algoritmul:

Fig. 9.3 Interferometrul Mach-Zehnder modificat pentru a implementa versiunea desenată a algoritmului Deutsch-Jozsa. Implementările funcției sunt prezentate în Fig. 9.5.

1. Cele două intrări x = 0 și x = 1 sunt reprezentate de cele două căi posibile ale fotonilor, așa cum se arată în Fig. 9.4. Un foton care urmează calea galbenă este x = 0, în timp ce un foton care urmează calea roșie este x = 1. Prin urmare, divizorul de fascicul 1 creează o superpoziție de 0 și 1, deoarece fotonul urmează ambele căi. Datorită orientării divizorului de fascicul, calea transmisă roșie nu va avea nicio defazare, în timp ce calea reflectată galbenă va avea o defazare de n.

Fig. 9.4 Intrările funcției sunt fotoni pe două căi diferite. Un foton care urmează calea galbenă este x = 0, în timp ce un foton care urmează calea roșie este x = 1.

2. Fiecare dintre cele patru funcții din Tabelul 9.1 poate fi modelată printr-o configurație experimentală diferită, așa cum se arată în Fig. 9.5. De exemplu, dacă am dori să testăm f₁, am plasa o bucată de sticlă de-a lungul căii roșii, dar nimic de-a lungul căii galbene. Un foton care trece prin sticlă va experimenta o defazare suplimentară de n. Motivul pentru care aceasta este doar o demonstrație desenată este că defazoarele nu implementează de fapt funcția, așa cum vom vedea în secțiunea următoare.

Fig. 9.5 Cele patru funcții diferite din Tabelul 9.1 implementate experimental prin patru configurații diferite. În acest desen, am notat funcția care modifică bitul printr-o poartă X, însă în realitate, așa cum este descris în Ec. (9.2), sunt necesari doi qubiți pentru a implementa aceste funcții.

Întrebarea 4 Dacă se testează f₁, care este faza căii galbene la atingerea celui de-al doilea divizor de fascicul? Fotonul căii roșii?

Calea galbenă a fost defazată de Divizorul de Fascicul 1 și nu a fost afectată de caseta albastră de funcții f(0). Calea roșie nu a fost afectată de Divizorul de Fascicul 1 și a fost defazată de caseta albastră de funcții f(1). Prin urmare, ambele au o defazare de n.

3. Al doilea divizor de fascicul creează interferența necesară pentru a se asigura că măsurarea are loc doar într-un singur detector. În funcție de detectorul măsurat, funcția este interpretată ca fiind constantă sau echilibrată.

Întrebarea 5 Pentru configurația experimentală /1, care este faza fotonului căii galbene la Detectorul 1? Fotonul roșu de la Detectorul 1?

La Detectorul 1, fotonii galben și roșu au ambele o defazare de n.

Întrebarea 6 Pentru configurația experimentală /1, care este faza fotonului galben de la Detectorul 2? Fotonul roșu de la Detectorul 2?

La Detectorul 2, fotonul galben de la Detectorul are o defazare de n, în timp ce fotonul roșu de la Detectorul are o defazare de 2n.

4. Măsurați care detector este activat.

Întrebarea 7 Pentru configurația experimentală f₁, care detector(i) se declanșează și cu ce probabilitate?

Detectorul 1 experimentează interferențe constructive, în timp ce Detectorul 2 experimentează interferențe distructive. Prin urmare, doar Detectorul 1 se activează pentru f₁, care este o funcție constantă. Care detector(i) se declanșează pentru f₂, f₃ și f₄?

După parcurgerea exercițiilor, ar trebui să vedeți că, datorită suprapunerii și interferenței, este necesară o singură măsurare cuantică în această imagine de desen a problemei Deutsch-Jozsa. Algoritmul general este prezentat în secțiunea următoare.

Algoritmul cuantic

Înainte de a descrie soluția cuantică completă, trebuie să configurăm câteva instrumente utile. De exemplu, în literatura de specialitate privind calculul cuantic, este obișnuit să se utilizeze instrumentul matematic numit aritmetică modulară. Pentru acest algoritm, nu va trebui să înțelegem aritmetica modulară mai mult decât notația de bază. În calculul cuantic, aritmetica modulară cu „mod 2” este definită ca fiind f(0) ⊕ f(1) = 0 dacă f(0) + f(1) = 0, 2, 4, 6, … . Cu toate acestea, f(0) ⊕ f(1) = 1 dacă f(0) + f(1) = 1, 3, 5, … . Observați că cercul cu un plus în interior ⊕ denotă această operație aritmetică modulară „mod 2”. Operația ⊕ generează restul împărțirii unui număr x la numărul 2. De exemplu, dacă f(0) = 0 și f(1) = 1, atunci f(0) ⊕ f(1) = 1, în timp ce dacă f(0) = 1 și f(1) = 1, atunci f(0) ⊕ f(1) = 0.

De asemenea, vom avea nevoie de un al doilea qubit pentru acest algoritm și vom vedea în curând de ce. În lumea calculului cuantic, funcția f(x) este implementată prin

|x⟩|y⟩ →^f |x⟩|y ⊕ f(x)⟩.   (9.2)

De exemplu, să presupunem că f(0) = 1, atunci |0⟩|1⟩ →^f |0⟩|1 ⊕ f(0)⟩ = |0⟩|0⟩. Deși implementarea funcțiilor ca în Ec. (9.2) pare ciudată, acest lucru este necesar pentru a se asigura că operația funcției este unitară. Circuitul care implementează algoritmul Deutsch-Jozsa este prezentat în Fig. 9.6. Vom oferi acum o prezentare generală a algoritmului și a circuitului.

Fig. 9.6 Circuitul cuantic pentru algoritmul Deutsch-Jozsa pe un qubit. Funcția generică f(x) este reprezentată de caseta cu f în interior, iar etichetele de sub/deasupra liniilor indică modul în care este implementată funcția.

Procedura Deutsch-Jozsa:

1. Ca prim pas al algoritmului prezentat în Fig. 9.6, obțineți doi qubiti și puneți-i într-o stare de produs |0⟩|1⟩. În experimentul Mach-Zehnder modificat de mai sus, a fost afișat doar primul qubit din Fig. 9.6. Al doilea qubit a fost ascuns în casetele albastre ale funcțiilor.
2. Operați asupra fiecărui qubit cu poarta Hadamard. Urmând regulile porții Hadamard, starea cu doi qubiti este acum

½ (|0⟩ + |1⟩)(|0⟩ – |1⟩).   (9.3)

În desenul Mach-Zehnder din Fig. 9.3, divizorul de fascicul 1 efectuează prima poartă Hadamard pe primul qubit din Fig. 9.6.

3. Aplicați funcția f(x) folosind regula din Ec. (9.2) stării din Ec. (9.3). După efectuarea aritmeticii, starea cu doi qubiti poate fi organizată ca

½ (|0⟩(|0 ⊕ f(0)⟩ – ⟩(|1 ⊕ f(0)⟩) + |1⟩(|0 ⊕ f(1)⟩ – |1 ⊕ f(1))).   (9.4)

Pentru a obține o imagine mai clară a efectului lui f(x) asupra stării, este util să observăm că dacă f(0) = 0 atunci |0 ⊕ f(0)⟩ – ⟩(|1 ⊕ f(0)⟩ = |0⟩ – |1⟩. În plus, dacă f(0) = 1, atunci |0 ⊕ f(0)⟩ – ⟩(|1 ⊕ f(0)⟩ = -|0⟩ + |1⟩. Putem combina aceste două formulări scriind |0 ⊕ f(0)⟩ – ⟩(|1 ⊕ f(0)⟩ = (-1)^f(0)(|0⟩ – |1⟩). O formulă similară este necesară și pentru cazul f(1), pe care o lăsăm ca exercițiu pentru cititor. Aplicând această formulă la ecuația (9.4), rezultă

½ ((-1)^f(0)|0⟩(|0⟩ – |1⟩) + (-1)^f(1)|1⟩(|0⟩ – |1⟩))   (9.5)

= (-1)^f(0) 1/2 (|0⟩ + (-1)^(f(0)+f(1))|1⟩)(|0⟩ – |1⟩).   (9.6)

În desenul lui Mach-Zehnder din Fig. 9.3, interacțiunea dintre cei doi qubiti a fost modelată prin trecerea fotonului prin casetele albastre ale funcțiilor.

4. Acum eliminăm al doilea qubit. Păstrăm doar primul qubit și ne asigurăm că este normalizat corect. Primul qubit este

1/√2 (|0⟩ + (-1)^(f(0)+f(1))|1⟩).   (9.7)

Motivul pentru care avem nevoie de al doilea qubit este pentru a efectua operațiile de poartă și a colecta termenii similari, ceea ce asigură funcționarea algoritmului. Acest al doilea qubit se numește qubit ancilla deoarece nu este măsurat. Acest lucru este prezentat în circuitul din Fig. 9.6 ca lipsa operatorului de măsurare din a doua linie de qubit.

5. Aplicați o poartă Hadamard stării qubitului din Ec. (9.7) pentru a obține

½ (1 + (-1)^(f(0)+f(1)))|0⟩ + (1 – (-1)^(f(0)+f(1)))|1⟩.   (9.8)

În desenul Mach-Zehnder din Fig. 9.3, a doua operație a porții Hadamard a fost implementată de Divizorul de flux 2.

6. Măsurați qubitul. Dacă f(x) este constant, atunci starea din Ec. (9.8) se reduce la |0⟩, în timp ce dacă f(x) este echilibrat, atunci starea se reduce la |1⟩. În desenul Mach-Zehnder din Fig. 9.3, detectorul a măsurat starea finală a fotonului.

După cum arată acest algoritm, o singură măsurare a lui |0⟩ sau |1⟩ arată dacă funcția este constantă sau echilibrată. Impresionant, acest algoritm se extinde direct la funcții care acceptă orice număr de intrări. Acest lucru este impresionant deoarece o singură măsurare vă poate spune dacă o funcție de orice dimensiune este constantă sau echilibrată. Pentru ca un computer clasic să îndeplinească aceeași sarcină, ar trebui să măsoare fiecare dintre intrări, ceea ce este exponențial mai lent.

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