Computații clasice pe calculatoare cuantice

Vom îndrepta acum atenția spre implementarea algoritmilor clasici pe calculatoare cuantice. Vom vedea că orice computație care poate fi efectuată cu un circuit Boolean clasic poate fi efectuată și de un circuit cuantic cu un cost computațional asimptotic similar. Mai mult, acest lucru se poate face într-un mod „curat", care va fi descris în curând, și care reprezintă o cerință importantă pentru folosirea acestor computații ca subrutine în cadrul unor computații cuantice mai mari.

Simularea circuitelor Boolean cu circuite cuantice

Circuitele Boolean sunt compuse din porți AND, OR, NOT și FANOUT. Pentru a simula circuitele Boolean cu circuite cuantice, vom începe prin a arăta cum poate fi simulată fiecare dintre aceste patru porți cu porți cuantice. Odată rezolvat acest lucru, conversia unui circuit Boolean dat într-un circuit cuantic este o simplă chestiune de simulare a câte unei porți pe rând. Va fi nevoie doar de porți NOT, porți controlled-NOT și porți Toffoli, care sunt toate operații deterministe, dar și unitare.

Porți Toffoli

Porțile Toffoli pot fi descrise alternativ ca porți controlled-controlled-NOT, a căror acțiune asupra stărilor bazei standard este prezentată în figura de mai jos.

Ținând cont că folosim convenția de ordonare a Qiskit, unde qubiții sunt ordonați în ordinea crescătoare a semnificației de sus în jos, reprezentarea matriceală a acestei porți este următoarea.

$$\begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \end{pmatrix}$$

Un alt mod de a gândi porțile Toffoli este că ele sunt în esență porți de interogare pentru funcția AND, în sensul că urmează tiparul văzut în lecția anterioară pentru implementările unitare ale porților de interogare ale unor funcții arbitrare cu intrări și ieșiri de tipul șiruri binare.

Porțile Toffoli nu sunt incluse în setul implicit de porți discutat mai devreme în lecție, dar este posibil să construiești o poartă Toffoli din porțile $H,$ $T,$ $T^{\dagger}$ și CNOT după cum urmează.

Simularea porților Boolean cu porți Toffoli, controlled-NOT și NOT

O singură poartă Toffoli, folosită împreună cu câteva porți NOT, poate implementa o poartă AND și una OR, iar porțile FANOUT pot fi implementate cu ușurință folosind porți controlled-NOT, după cum sugerează diagramele de mai jos.

În toate trei cazurile, qubiții asupra cărora acționează porțile AND, OR și FANOUT intră din stânga ca intrări, iar pentru fiecare este necesar și câte un qubit de spațiu de lucru inițializat la starea zero. Acești qubiți de spațiu de lucru apar în interiorul casetelor care reprezintă implementările porților pentru a sugera că sunt noi și, prin urmare, fac parte din costul acestor implementări.

Pentru porțile AND și OR mai rămân și doi qubiți, pe lângă qubitul de ieșire. De exemplu, în interiorul casetei din diagramă care reprezintă simularea unei porți AND, primii doi qubiți rămân în stările $\vert a\rangle$ și $\vert b\rangle.$ Acești qubiți sunt ilustrați ca rămânând în interiorul casetelor deoarece nu mai sunt necesari și nu fac parte din ieșire. Pot fi ignorați deocamdată, deși vom reveni la ei în curând.

Singura poartă Boolean rămasă, poarta NOT, este inclusă în setul nostru implicit de porți cuantice, deci nu avem nevoie de o simulare pentru aceasta.

Simularea gate cu gate a circuitelor Boolean

Să presupunem acum că avem un circuit Boolean obișnuit numit $C,$ compus din porți AND, OR, NOT și FANOUT, cu $n$ biți de intrare și $m$ biți de ieșire. Fie $t = \operatorname{size}(C)$ numărul de porți din $C$ și să numim $f$ funcția calculată de $C$, care are forma

$$f:\Sigma^n\rightarrow\Sigma^m$$

pentru $\Sigma = \{0,1\}.$

Acum să ne gândim la ce se întâmplă când parcurgem pe rând porțile AND, OR și FANOUT ale lui $C,$ înlocuind fiecare cu simularea corespunzătoare descrisă mai sus, inclusiv adăugând qubiții de spațiu de lucru necesari. Să numim circuitul rezultat $R$ și să ordonăm qubiții lui $R$ astfel încât cei $n$ biți de intrare ai lui $C$ să corespundă primilor $n$ qubiți ai lui $R$, iar qubiții de spațiu de lucru să fie la sfârșit.

Aici, $k$ este numărul de qubiți de spațiu de lucru necesari — câte unul pentru fiecare poartă AND, OR și FANOUT din $C$ — și $g$ este o funcție de forma $g:\Sigma^n \rightarrow \Sigma^{n+k-m}$ care descrie stările qubiților rămași creați de simulările de porți după ce $R$ este rulat. În figură, qubiții corespunzători ieșirii $f(x)$ se află sus, iar qubiții rămași care stochează $g(x)$ se află jos. Putem forța acest lucru dacă dorim, prin rearanjarea qubiților cu porți SWAP, care pot fi implementate cu trei porți controlled-NOT astfel:

Cum vom vedea în secțiunea următoare, nu este cu adevărat esențial să rearanjăm qubiții de ieșire în acest mod, dar este suficient de simplu de făcut dacă alegem să o facem.

Funcția $g$ care descrie stările clasice ale qubiților rămași este determinată de circuitul $C,$ dar de fapt nu trebuie să ne îngrijorăm prea mult în privința ei; nu ne interesează în mod specific în ce stare se află acești qubiți când computația se termină. Litera $g$ vine după $f,$ deci este un nume rezonabil pentru această funcție din acel motiv, dar există un motiv mai bun de a alege numele $g$ — este prescurtarea pentru gunoi (engl. garbage).

Curățarea gunoiului

Dacă singurul nostru interes este evaluarea funcției $f$ calculată de un circuit Boolean $C$ cu un circuit cuantic, nu trebuie să mergem mai departe decât simularea gate cu gate tocmai descrisă. Aceasta înseamnă că, pe lângă ieșirea funcției, vom mai avea o grămadă de gunoi rămas.

Totuși, asta nu este suficient dacă vrem să efectuăm computații clasice ca subrutine în cadrul unor computații cuantice mai mari, deoarece acei qubiți de gunoi vor cauza probleme. Fenomenul de interferență este extrem de important pentru algoritmii cuantici, iar qubiții de gunoi pot distruge tiparele de interferență necesare pentru ca algoritmii cuantici să funcționeze.

Din fericire, curățarea gunoiului, ca să spunem așa, nu este dificilă. Cheia este să folosim faptul că, deoarece $R$ este un circuit cuantic, îl putem rula în sens invers, înlocuind pur și simplu fiecare poartă cu inversa sa și aplicându-le în ordine inversă, obținând astfel un circuit cuantic pentru operația $R^{\dagger}.$ Porțile Toffoli, porțile CNOT și porțile NOT sunt de fapt propriile lor inverse, deci rularea lui $R$ în sens invers este cu adevărat doar o chestiune de aplicare a porților în ordine inversă — dar mai general, orice circuit cuantic poate fi inversat după cum tocmai am descris.

Mai concret, ce putem face este să adăugăm $m$ qubiți în plus (amintind că funcția $f$ are $m$ biți de ieșire), să folosim porți CNOT pentru a copia ieșirea lui $R$ pe acești qubiți și să inversăm $R$ pentru a curăța gunoiul. Figura de mai jos ilustrează circuitul rezultat și descrie acțiunea sa asupra stărilor bazei standard.

Dacă punem o casetă în jurul întregului circuit și îl numim $Q$, arată astfel:

Dat fiind că $C$ are $t$ porți, circuitul $Q$ va avea $O(t)$ porți.

Dacă ignorăm cei $k$ qubiți suplimentari de spațiu de lucru, avem un circuit $Q$ care funcționează exact ca o poartă de interogare pentru funcția $f.$ Dacă vrem pur și simplu să calculăm funcția $f$ pe un șir $x,$ putem seta $y = 0^m$ și valoarea rezultată $f(x)$ va apărea pe ultimii $m$ qubiți — sau putem alimenta o stare diferită în ultimii $m$ qubiți dacă dorim (poate pentru a utiliza un phase kickback, ca în algoritmul lui Deutsch sau al lui Deutsch-Jozsa).

Aceasta înseamnă că pentru orice algoritm de interogare, dacă avem un circuit Boolean care calculează funcția de intrare, putem înlocui fiecare poartă de interogare cu o implementare ca circuit a acesteia, și algoritmul de interogare va funcționa corect.

Rețineți că qubiții de spațiu de lucru sunt necesari pentru ca acest proces să funcționeze, dar sunt readuși la stările lor inițiale odată ce circuitul combinat este executat. Asta permite ca acești qubiți să fie folosiți din nou ca qubiți de spațiu de lucru în alte scopuri. Există și strategii cunoscute pentru a reduce numărul de qubiți de spațiu de lucru necesari (care vin cu un cost de mărire a circuitelor), dar nu vom discuta acele strategii aici.

Implementarea funcțiilor inversabile

Construcția tocmai descrisă ne permite să simulăm orice circuit Boolean cu un circuit cuantic fără gunoi. Dacă $C$ este un circuit Boolean care implementează o funcție $f:\Sigma^n \rightarrow \Sigma^m,$ atunci obținem un circuit cuantic $Q$ care operează astfel pe stările bazei standard.

$$Q \bigl( \vert y \rangle \vert 0^k \rangle \vert x\rangle\bigr) = \vert y \oplus f(x) \rangle \vert 0^k \rangle \vert x\rangle$$

Numărul $k$ indică câți qubiți de spațiu de lucru sunt necesari în total. Asta este suficient pentru scopurile acestui curs, dar este posibil să duci această metodologie cu un pas mai departe când funcția $f$ în sine este inversabilă.

Mai precis, să presupunem că funcția $f$ are forma $f:\Sigma^n \rightarrow \Sigma^n$ și că există o funcție $f^{-1}$ astfel încât $f^{-1}(f(x)) = x$ pentru orice $x\in\Sigma^n$ (care este în mod necesar unică atunci când există). Aceasta înseamnă că operația care transformă $\vert x \rangle$ în $\vert f(x) \rangle$ pentru orice $x\in\Sigma^n$ este unitară, deci am putea spera să construim un circuit cuantic care implementează operația unitară definită de

$$U \vert x \rangle = \vert f(x) \rangle$$

pentru orice $x\in\Sigma^n.$

Pentru a fi clar, faptul că aceasta este o operație unitară depinde de $f$ a fi inversabilă — nu este unitară când $f$ nu este inversabilă. Ignorând qubiții de spațiu de lucru, $U$ este diferit de operația pe care o implementează circuitul $Q$ deoarece nu păstrăm o copie a intrării și nu aplicăm XOR cu un șir arbitrar, ci înlocuim $x$ cu $f(x).$

Întrebarea este: când $f$ este inversabilă, putem face asta?

Răspunsul este da, cu condiția să avem voie să folosim qubiți de spațiu de lucru și, pe lângă un circuit Boolean care calculează $f,$ să avem și unul care calculează $f^{-1}.$ Deci, aceasta nu este o scurtătură pentru inversarea computațională a funcțiilor când nu știm deja cum să facem asta! Diagrama de mai jos ilustrează cum se poate realiza prin compunerea a două circuite cuantice, $Q_f$ și $Q_{f^{-1}},$ obținute individual pentru funcțiile $f$ și $f^{-1}$ prin metoda descrisă mai sus, împreună cu $n$ porți swap, luând $k$ ca maximul numărului de qubiți de spațiu de lucru necesari de $Q_f$ și $Q_{f^{-1}}.$