Circuits

În informatică, circuitele sunt modele de calcul în care informațiile sunt transportate prin fire printr-o rețea de porți (gates), care reprezintă operații asupra informațiilor purtate de fire. Quantum circuits sunt un model specific de calcul bazat pe acest concept mai general.

Deși cuvântul „circuit" se referă adesea la o cale circulară, căile circulare nu sunt de fapt permise în modelele de calcul de tip circuit studiate cel mai frecvent. Cu alte cuvinte, considerăm de obicei circuite aciclice atunci când ne gândim la circuite ca modele de calcul. Quantum circuits urmează acest tipar; un quantum circuit reprezintă o secvență finită de operații care nu poate conține bucle de feedback.

Circuite booleene

Iată un exemplu de circuit boolean (clasic), în care firele transportă valori binare, iar porțile (gates) reprezintă operații de logică booleană:

Fluxul de informații de-a lungul firelor se desfășoară de la stânga la dreapta: firele din partea stângă a figurii, notate $\mathsf{X}$ și $\mathsf{Y}$, sunt biți de intrare, fiecare putând fi setat la orice valoare binară dorim, iar firul din partea dreaptă este ieșirea. Firele intermediare iau valorile determinate de porți (gates), care sunt evaluate de la stânga la dreapta.

Porțile (gates) sunt porți AND (notate $\wedge$), porți OR (notate $\vee$) și porți NOT (notate $\neg$). Funcțiile calculate de aceste porți vor fi probabil familiare multor cititori, dar iată-le reprezentate prin tabele de valori:

$$\begin{array}{c} \begin{array}{c|c} a & \neg a\\ \hline 0 & 1\\ 1 & 0\\ \end{array}\\ \\ \\ \end{array} \qquad\quad \begin{array}{c|c} ab & a \wedge b\\ \hline 00 & 0\\ 01 & 0\\ 10 & 0\\ 11 & 1 \end{array} \qquad\quad \begin{array}{c|c} ab & a \vee b\\ \hline 00 & 0\\ 01 & 1\\ 10 & 1\\ 11 & 1 \end{array}$$

Cele două mici cercuri pline de pe fire, chiar în dreapta numelor $\mathsf{X}$ și $\mathsf{Y}$, reprezintă operații de fan-out, care creează pur și simplu o copie a valorii purtate pe firul pe care apar, permițând ca această valoare să fie introdusă în mai multe porți (gates). Operațiile de fan-out nu sunt întotdeauna considerate porți (gates) în contextul clasic; uneori sunt tratate ca și cum ar fi „gratuite" într-un anumit sens. Când circuitele booleene sunt convertite în quantum circuits echivalente, trebuie însă să clasificăm operațiile de fan-out explicit drept porți (gates) pentru a le gestiona și contabiliza corect. Iată același Circuit ilustrat într-un stil mai comun în ingineria electrică, care folosește simboluri convenționale pentru porțile AND, OR și NOT:

Nu vom folosi acest stil sau aceste simboluri particulare de Gate în continuare, dar vom folosi simboluri diferite pentru a reprezenta Gate-uri în circuite cuantice, pe care le vom explica pe măsură ce le întâlnim.

Circuitul particular din acest exemplu calculează sau-exclusiv (sau XOR pe scurt), notat cu simbolul $\oplus$:

$$\begin{array}{c|c} ab & a \oplus b\\ \hline 00 & 0\\ 01 & 1\\ 10 & 1\\ 11 & 0 \end{array}$$

În diagrama următoare considerăm o singură alegere pentru intrări: $\mathsf{X}=0$ și $\mathsf{Y}=1.$ Fiecare fir este etichetat cu valoarea pe care o transportă, astfel încât poți urmări operațiile. Valoarea de ieșire este $1$ în acest caz, ceea ce este valoarea corectă pentru XOR: $0 \oplus 1 = 1.$

Celelalte trei configurații posibile ale intrărilor pot fi verificate într-un mod similar.

Alte tipuri de circuite

Așa cum s-a sugerat mai sus, noțiunea de Circuit în informatică este foarte generală. De exemplu, sunt uneori analizate circuite ale căror fire transportă valori diferite de $0$ și $1$, la fel ca și Gate-urile care reprezintă alegeri diferite de operații.

În circuitele aritmetice, de pildă, firele pot transporta valori întregi, în timp ce Gate-urile reprezintă operații aritmetice, cum ar fi adunarea și înmulțirea. Figura următoare reprezintă un Circuit aritmetic care primește două valori variabile de intrare ($x$ și $y$) precum și o a treia intrare setată la valoarea $1.$ Valorile transportate de fire, ca funcții ale valorilor $x$ și $y,$ sunt prezentate în figură.

Putem considera, de asemenea, circuite care încorporează aleatorul, cum ar fi cele în care Gate-urile reprezintă operații probabilistice.

Circuite cuantice

În modelul Circuit cuantic, firele reprezintă Qubiți, iar Gate-urile reprezintă operații asupra acestor Qubiți. Ne vom concentra deocamdată pe operațiile pe care le-am întâlnit până acum, și anume operații unitare și măsurători în baza standard. Pe măsură ce învățăm despre alte tipuri de operații cuantice și măsurători, putem extinde modelul în mod corespunzător.

Iată un exemplu simplu de Circuit cuantic:

În acest Circuit avem un singur Qubit numit $\mathsf{X},$ reprezentat prin linia orizontală, și o secvență de Gate-uri reprezentând operații unitare asupra acestui Qubit. La fel ca în exemplele de mai sus, fluxul de informații merge de la stânga la dreapta — astfel, prima operație efectuată este o operație Hadamard, a doua este o operație $S$, a treia este o altă operație Hadamard, iar ultima operație este o operație $T$. Aplicând întregul Circuit se aplică astfel compoziția acestor operații, $T H S H,$ asupra Qubitului $\mathsf{X}.$

Uneori poate fi dorit să indicăm explicit stările de intrare sau ieșire ale circuitelor. De exemplu, dacă aplicăm operația $T H S H$ asupra stării $\vert 0\rangle,$ obținem starea $\frac{1+i}{2}\vert 0\rangle + \frac{1}{\sqrt{2}} \vert 1 \rangle.$ Aceasta poate fi indicată astfel:

Circuitele cuantice pornesc adesea cu toți Qubiții inițializați la $\vert 0\rangle,$ așa cum avem în acest caz, dar există și situații în care Qubiții de intrare sunt inițial setați la stări diferite. Iată un alt exemplu de Circuit cuantic, de această dată cu doi Qubiți:

Ca întotdeauna, Gate-ul etichetat $H$ se referă la o operație Hadamard, în timp ce al doilea Gate este o operație NOT controlat: cercul plin reprezintă Qubit-ul de control, iar cercul care seamănă cu simbolul $\oplus$ denotă Qubit-ul țintă.

Înainte de a examina acest Circuit mai în detaliu și de a explica ce face, este imperativ să clarificăm mai întâi cum sunt ordonați Qubiții în circuitele cuantice. Aceasta se leagă de convenția pe care Qiskit o folosește pentru denumirea și ordonarea sistemelor, menționată pe scurt în lecția anterioară.

Convenția Qiskit de ordonare a qubiților în circuite

În Qiskit, qubit-ul din vârful unui Circuit are indexul $0$ și corespunde poziției din dreapta unui tuplu de qubiți (sau dintr-un șir, produs cartezian sau produs tensorial corespunzător acestui tuplu); qubit-ul al doilea de sus are indexul $1$ și corespunde poziției a doua din dreapta a tuplului, și tot așa. Qubit-ul din josul diagramei, care are cel mai mare index, corespunde prin urmare poziției din stânga a tuplului. În special, denumirile implicite ale qubiților dintr-un Circuit cu $n$ qubiți în Qiskit sunt reprezentate prin $n$-tuplul $(\mathsf{q_{n-1}},\ldots,\mathsf{q_{0}}),$ unde $\mathsf{q_{0}}$ este qubit-ul din vârf, iar $\mathsf{q_{n-1}}$ este qubit-ul din jos în diagramele de Circuit cuantic.

Această convenție este inversul unei convenții mai comune de ordonare a qubiților în circuite și reprezintă o sursă frecventă de confuzie. Mai multe informații despre această convenție de ordonare se găsesc pe pagina de documentație Bit-ordering in Qiskit.

Deși uneori ne abatem de la denumirile implicite $\mathsf{q_{0}},\ldots,\mathsf{q_{n-1}}$ folosite de Qiskit pentru qubiți, vom urma întotdeauna convenția de ordonare descrisă mai sus când interpretăm diagrame de Circuit pe parcursul acestui curs. Prin urmare, interpretarea noastră a Circuit-ului de mai sus este că acesta descrie o operație pe o pereche de qubiți $(\mathsf{X},\mathsf{Y}).$ Dacă intrarea în Circuit este o stare cuantică $\vert\psi\rangle \otimes \vert\phi\rangle,$ de exemplu, asta înseamnă că qubit-ul de jos $\mathsf{X}$ pornește din starea $\vert\psi\rangle,$ iar qubit-ul de sus $\mathsf{Y}$ pornește din starea $\vert\phi\rangle.$

Pentru a înțelege ce face Circuit-ul, putem parcurge operațiile sale de la stânga la dreapta.

1. Prima operație este operația Hadamard pe $\mathsf{Y}$:

   

   Când se aplică un Gate pe un singur qubit în acest mod, ceilalți qubiți nu sunt afectați (în acest caz există un singur alt qubit). Faptul că nu se întâmplă nimic este echivalent cu efectuarea operației identitate. Dreptunghiul punctat din figura de mai sus reprezintă astfel această operație:

   $$\mathbb{I}\otimes H = \begin{pmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} & 0 & 0\\[2mm] \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} & 0 & 0\\[2mm] 0 & 0 & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}}\\[2mm] 0 & 0 & \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \end{pmatrix}.$$

   Observă că matricea identitate se află în stânga produsului tensorial, iar $H$ în dreapta, ceea ce este consistent cu convenția de ordonare a lui Qiskit.

2. A doua operație este operația controlled-NOT, unde $\mathsf{Y}$ este qubit-ul de control, iar $\mathsf{X}$ este qubit-ul țintă:

   

   Acțiunea Gate-ului controlled-NOT asupra stărilor din baza standard este următoarea:

   

   Ținând cont că ordonăm qubiții ca $(\mathsf{X}, \mathsf{Y}),$ cu $\mathsf{X}$ în jos și $\mathsf{Y}$ în sus în Circuit-ul nostru, reprezentarea matriceală a Gate-ului controlled-NOT este aceasta:

   $$\begin{pmatrix} 1 & 0 & 0 & 0\\[2mm] 0 & 0 & 0 & 1\\[2mm] 0 & 0 & 1 & 0\\[2mm] 0 & 1 & 0 & 0 \end{pmatrix}.$$

Operația unitară implementată de întregul Circuit, căreia îi vom da numele $U,$ este compoziția operațiilor:

$$U = \begin{pmatrix} 1 & 0 & 0 & 0\\[2mm] 0 & 0 & 0 & 1\\[2mm] 0 & 0 & 1 & 0\\[2mm] 0 & 1 & 0 & 0 \end{pmatrix} \begin{pmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} & 0 & 0\\[2mm] \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} & 0 & 0\\[2mm] 0 & 0 & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}}\\[2mm] 0 & 0 & \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \end{pmatrix} = \begin{pmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} & 0 & 0\\[2mm] 0 & 0 & \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}}\\[2mm] 0 & 0 & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}}\\[2mm] \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} & 0 & 0 \end{pmatrix}.$$

În particular, amintindu-ne notația pentru stările Bell,

$$\begin{aligned} \vert \phi^+ \rangle & = \frac{1}{\sqrt{2}} \vert 0 0 \rangle + \frac{1}{\sqrt{2}} \vert 1 1 \rangle \\[2mm] \vert \phi^- \rangle & = \frac{1}{\sqrt{2}} \vert 0 0 \rangle - \frac{1}{\sqrt{2}} \vert 1 1 \rangle \\[2mm] \vert \psi^+ \rangle & = \frac{1}{\sqrt{2}} \vert 0 1 \rangle + \frac{1}{\sqrt{2}} \vert 1 0 \rangle \\[2mm] \vert \psi^- \rangle & = \frac{1}{\sqrt{2}} \vert 0 1 \rangle - \frac{1}{\sqrt{2}} \vert 1 0 \rangle, \end{aligned}$$

obținem că

$$\begin{aligned} U \vert 00\rangle & = \vert \phi^+\rangle\\ U \vert 01\rangle & = \vert \phi^-\rangle\\ U \vert 10\rangle & = \vert \psi^+\rangle\\ U \vert 11\rangle & = -\vert \psi^-\rangle. \end{aligned}$$

Acest Circuit ne oferă astfel o modalitate de a crea starea $\vert\phi^+\rangle$ dacă îl rulăm pe doi qubiți inițializați în $\vert 00\rangle.$ Mai general, ne oferă o modalitate de a converti baza standard în baza Bell. (Observă că, deși nu este important pentru acest exemplu, factorul de fază $-1$ din ultima stare, $-\vert \psi^-\rangle,$ ar putea fi eliminat dacă am dori, printr-o mică adăugire la Circuit. De exemplu, am putea adăuga un Gate controlled-$Z$ la început, care este similar cu un Gate controlled-NOT, cu excepția că o operație $Z$ este aplicată Qubitului țintă în loc de o operație NOT atunci când controlul este setat la $1.$ Alternativ, am putea adăuga un swap gate la sfârșit. Oricare dintre aceste variante elimină semnul minus fără a afecta acțiunea Circuitului asupra celorlalte trei stări ale bazei standard.)

În general, circuitele cuantice pot conține oricâte fire de Qubit. Putem include și fire de bit clasic, indicate prin linii duble, ca în acest exemplu:

Aici avem un Gate Hadamard și un Gate controlled-NOT pe doi qubiți $\mathsf{X}$ și $\mathsf{Y},$ la fel ca în exemplul anterior. Avem de asemenea doi biți clasici, $\mathsf{A}$ și $\mathsf{B},$ precum și două gate-uri de măsurare. Gate-urile de măsurare reprezintă măsurători în baza standard: qubiții sunt transformați în stările lor post-măsurare, iar rezultatele măsurătorilor sunt suprascrise pe biții clasici spre care indică săgețile.

Este adesea convenabil să reprezentăm o măsurătoare ca un Gate care primește un Qubit ca intrare și produce un bit clasic la ieșire (spre deosebire de a scoate Qubit-ul în starea sa post-măsurare și a scrie rezultatul într-un bit clasic separat). Aceasta înseamnă că Qubit-ul măsurat a fost eliminat și poate fi ignorat în siguranță ulterior, starea sa schimbându-se în $\vert 0\rangle$ sau $\vert 1\rangle$ în funcție de rezultatul măsurătorii.

De exemplu, următoarea diagramă de Circuit reprezintă același proces ca cel din diagrama anterioară, dar în care renunțăm la $\mathsf{X}$ și $\mathsf{Y}$ după ce îi măsurăm:

Pe măsură ce cursul continuă, vom vedea mai multe exemple de circuite cuantice, care sunt de obicei mai complexe decât exemplele simple de mai sus. Iată câteva exemple de simboluri folosite pentru a denota gate-uri care apar frecvent în diagramele de Circuit:

• Gate-urile cu un singur Qubit sunt reprezentate în general ca pătrate cu o literă care indică operația respectivă, astfel:

  

  Gate-urile NOT (sau, echivalent, gate-urile $X$) sunt uneori reprezentate și printr-un cerc în jurul unui semn plus:

  

• Gate-urile swap sunt reprezentate astfel:

  

• Gate-urile controlate, adică gate-urile care descriu operații unitare controlate, sunt reprezentate printr-un cerc plin (indicând controlul) conectat printr-o linie verticală la operația controlată. De exemplu, gate-urile controlled-NOT, gate-urile controlled-controlled-NOT (sau Toffoli) și gate-urile controlled-swap (Fredkin) sunt reprezentate astfel:

  

• Operațiile unitare arbitrare pe mai mulți qubiți pot fi privite ca gate-uri. Acestea sunt reprezentate prin dreptunghiuri etichetate cu numele operației unitare. De exemplu, iată o reprezentare a unei operații unitare (nespecificate) $U$ ca Gate, împreună cu o versiune controlată a acestui Gate: