Circuits

W informatyce circuits są modelami obliczeniowymi, w których informacja jest przenoszona przez przewody w sieci gates, reprezentujących operacje na informacji przenoszonej przez te przewody. Quantum circuits to konkretny model obliczeń oparty na tym ogólniejszym pojęciu.

Choć słowo „circuit" często kojarzy się z okrężną ścieżką, okrężne ścieżki nie są dozwolone w modelach obliczeniowych opartych na circuits, które są najczęściej badane. Innymi słowy, zazwyczaj rozważamy acyclic circuits (acykliczne), gdy myślimy o circuits jako modelach obliczeniowych. Quantum circuits podążają za tym wzorcem — quantum circuit reprezentuje skończoną sekwencję operacji, która nie może zawierać pętli sprzężenia zwrotnego.

Boolean circuits

Oto przykład (klasycznego) Boolean circuit, w którym przewody przenoszą wartości binarne, a gates reprezentują operacje logiki Boolean:

Przepływ informacji wzdłuż przewodów przebiega od lewej do prawej: przewody po lewej stronie rysunku, oznaczone $\mathsf{X}$ i $\mathsf{Y}$, to bity wejściowe, które można ustawić na dowolną wybraną wartość binarną, a przewód po prawej stronie to wyjście. Pośrednie przewody przyjmują wartości wyznaczone przez gates, które są obliczane od lewej do prawej.

Gates to: AND gates (oznaczone $\wedge$), OR gates (oznaczone $\vee$) i NOT gates (oznaczone $\neg$). Funkcje obliczane przez te gates są prawdopodobnie znane wielu czytelnikom, ale poniżej przedstawione są w postaci tablic wartości:

$$\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}$$

Dwa małe, wypełnione kółka na przewodach tuż po prawej stronie nazw $\mathsf{X}$ i $\mathsf{Y}$ reprezentują operacje fan-out, które po prostu tworzą kopię wartości przenoszonej przez przewód, na którym się pojawiają, umożliwiając jej podanie na wejście wielu gates. Operacje fan-out nie zawsze są uznawane za gates w klasycznym ujęciu — czasem traktuje się je jako „darmowe" w pewnym sensie. Kiedy jednak Boolean circuits są przekształcane w równoważne quantum circuits, musimy jawnie klasyfikować operacje fan-out jako gates, aby je prawidłowo obsłużyć i uwzględnić.

Oto ten sam circuit przedstawiony w stylu popularniejszym w elektrotechnice, który używa konwencjonalnych symboli dla gates AND, OR i NOT:

Nie będziemy dalej używać tego stylu ani tych konkretnych symboli gates, natomiast będziemy używać innych symboli do reprezentowania gates w quantum circuits — wyjaśnimy je, gdy się z nimi spotkamy.

Konkretny circuit w tym przykładzie oblicza exclusive-OR (w skrócie XOR), oznaczany symbolem $\oplus$:

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

Na następnym diagramie rozważamy tylko jeden wybór wejść: $\mathsf{X}=0$ i $\mathsf{Y}=1.$ Każdy przewód jest oznaczony wartością, którą przenosi, dzięki czemu możesz śledzić poszczególne operacje. Wartość wyjściowa wynosi w tym przypadku $1$, co jest poprawną wartością dla XOR: $0 \oplus 1 = 1.$

Pozostałe trzy możliwe ustawienia wejść można sprawdzić w podobny sposób.

Inne typy układów

Jak wspomniano powyżej, pojęcie układu w informatyce jest bardzo ogólne. Analizuje się na przykład układy, których przewody przenoszą wartości inne niż $0$ i $1$, a także układy z bramkami reprezentującymi różne operacje.

W układach arytmetycznych przewody mogą przenosić wartości całkowite, a bramki reprezentują operacje arytmetyczne, takie jak dodawanie i mnożenie. Poniższy rysunek przedstawia układ arytmetyczny, który przyjmuje dwie zmienne wartości wejściowe ($x$ i $y$) oraz trzecie wejście ustawione na wartość $1.$ Wartości przenoszone przez przewody, jako funkcje wartości $x$ i $y,$ są pokazane na rysunku.

Możemy też rozważać układy uwzględniające losowość, np. takie, w których bramki reprezentują operacje probabilistyczne.

Quantum circuits

W modelu Quantum circuit przewody reprezentują qubit/kubity, a bramki — operacje na tych qubit/kubitach. Na razie skupimy się na operacjach, które poznaliśmy do tej pory, a mianowicie na operacjach unitary i pomiarach w bazie standardowej. W miarę poznawania innych rodzajów operacji kwantowych i pomiarów będziemy mogli odpowiednio rozszerzać nasz model.

Oto prosty przykład Quantum circuit:

W tym układzie mamy jeden qubit o nazwie $\mathsf{X},$ reprezentowany przez poziomą linię, oraz ciąg bramek reprezentujących operacje unitary na tym qubit/kubicie. Podobnie jak w powyższych przykładach, informacja płynie od lewej do prawej — pierwszą wykonywaną operacją jest operacja Hadamard, drugą jest operacja $S$, trzecią kolejna operacja Hadamard, a ostatnią operacja $T$. Zastosowanie całego układu odpowiada więc złożeniu tych operacji, $T H S H,$ na qubit $\mathsf{X}.$

Czasem możemy chcieć jawnie wskazać stany wejściowe lub wyjściowe układów. Na przykład, jeśli zastosujemy operację $T H S H$ do stanu $\vert 0\rangle,$ otrzymamy stan $\frac{1+i}{2}\vert 0\rangle + \frac{1}{\sqrt{2}} \vert 1 \rangle.$ Można to przedstawić następująco:

Quantum circuits często zaczynają się z wszystkimi qubit/kubitami zainicjalizowanymi do $\vert 0\rangle,$ tak jak w tym przypadku, ale zdarzają się też sytuacje, w których wejściowe qubit/kubity są początkowo ustawione w różnych stanach. Oto kolejny przykład Quantum circuit, tym razem z dwoma qubit/kubitami:

Jak zawsze, bramka oznaczona $H$ odnosi się do operacji Hadamard, natomiast druga bramka to operacja controlled-NOT: wypełnione kółko reprezentuje qubit sterujący (control qubit), a kółko przypominające symbol $\oplus$ oznacza qubit docelowy (target qubit).

Zanim dokładniej przeanalizujemy ten układ i wyjaśnimy, co robi, musimy najpierw wyjaśnić, jak qubit/kubity są porządkowane w Quantum circuits. Wiąże się to z konwencją, którą Qiskit stosuje do nazewnictwa i porządkowania systemów, wspomnianą pokrótce w poprzedniej lekcji.

Qiskit's qubit ordering convention for circuits

W Qiskit najwyższy kubit w diagramie obwodu ma indeks $0$ i odpowiada prawej pozycji w krotce kubitów (lub w ciągu, iloczynie kartezjańskim lub iloczynie tensorycznym odpowiadającym tej krotce), drugi od góry kubit ma indeks $1$ i odpowiada pozycji drugiej od prawej w krotce i tak dalej. Najniższy kubit, mający najwyższy indeks, odpowiada zatem lewej pozycji w krotce. W szczególności domyślne nazwy Qiskit dla kubitów w obwodzie $n$-kubitowym są reprezentowane przez $n$-krotkę $(\mathsf{q_{n-1}},\ldots,\mathsf{q_{0}}),$ gdzie $\mathsf{q_{0}}$ to kubit na górze, a $\mathsf{q_{n-1}}$ na dole w diagramach obwodów kwantowych.

Należy zauważyć, że jest to odwrócenie bardziej powszechnej konwencji porządkowania kubitów w obwodach i jest częstym źródłem nieporozumień. Więcej informacji na temat tej konwencji porządkowania można znaleźć na stronie dokumentacji Kolejność bitów w Qiskit.

Choć czasem odchodzimy od konkretnych domyślnych nazw $\mathsf{q_{0}},\ldots,\mathsf{q_{n-1}}$ używanych przez Qiskit dla qubit/kubitów, zawsze będziemy stosować opisaną powyżej konwencję porządkowania przy interpretacji diagramów układów w tym kursie. Zatem nasza interpretacja powyższego układu jest taka, że opisuje on operację na parze qubit/kubitów $(\mathsf{X},\mathsf{Y}).$ Jeśli wejściem do układu jest stan kwantowy $\vert\psi\rangle \otimes \vert\phi\rangle,$ oznacza to na przykład, że dolny qubit $\mathsf{X}$ zaczyna w stanie $\vert\psi\rangle$, a górny qubit $\mathsf{Y}$ zaczyna w stanie $\vert\phi\rangle.$

Aby zrozumieć, co robi układ, możemy przejść od lewej do prawej przez jego operacje.

1. Pierwsza operacja to operacja Hadamard na $\mathsf{Y}$:

   

   Gdy stosujemy bramkę do jednego qubit/kubita w ten sposób, na pozostałych qubit/kubitach nie dzieje się nic (w tym przypadku to tylko jeden inny qubit). To, że nic się nie dzieje, jest równoważne wykonaniu operacji identyczności. Przerywany prostokąt na powyższym rysunku reprezentuje zatem tę operację:

   $$\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}.$$

   Zwróć uwagę, że macierz identyczności jest po lewej stronie iloczynu tensorowego, a $H$ po prawej, co jest spójne z konwencją porządkowania Qiskit.

2. Druga operacja to operacja controlled-NOT, gdzie $\mathsf{Y}$ jest kontrolą, a $\mathsf{X}$ jest celem:

   

   Działanie bramki controlled-NOT na stanach bazy standardowej jest następujące:

   

   Biorąc pod uwagę, że porządkujemy qubit/kubity jako $(\mathsf{X}, \mathsf{Y}),$ gdzie $\mathsf{X}$ jest na dole, a $\mathsf{Y}$ na górze układu, reprezentacja macierzowa bramki controlled-NOT wygląda następująco:

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

Operacja unitary zaimplementowana przez cały układ, którą nazwiemy $U,$ jest złożeniem operacji:

$$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}.$$

Przypominając sobie notację stanów Bella,

$$\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}$$

stwierdzamy, że

$$\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}$$

Ten układ daje nam zatem sposób na utworzenie stanu $\vert\phi^+\rangle,$ jeśli uruchomimy go na dwóch qubit/kubitach zainicjalizowanych do $\vert 00\rangle.$ Ogólniej, dostarcza nam sposób konwersji bazy standardowej do bazy Bella. (Warto zauważyć, że choć nie jest to istotne dla tego przykładu, czynnik fazowy $-1$ przy ostatnim stanie, $-\vert \psi^-\rangle,$ można by wyeliminować, wprowadzając małą modyfikację układu. Moglibyśmy na przykład dodać bramkę controlled-$Z$ na początku, która jest podobna do bramki controlled-NOT z tą różnicą, że operacja $Z$ jest stosowana do qubit/kubita docelowego zamiast operacji NOT, gdy kontrola jest ustawiona na $1.$ Alternatywnie, moglibyśmy dodać bramkę swap na końcu. Każdy z tych wyborów eliminuje znak minus, nie wpływając na działanie układu na pozostałe trzy stany bazy standardowej.)

Ogólnie Quantum circuits mogą zawierać dowolną liczbę przewodów qubit/kubitowych. Możemy też uwzględniać przewody klasycznych bitów, oznaczane podwójnymi liniami, jak w tym przykładzie:

Mamy tu bramkę Hadamard i bramkę controlled-NOT na dwóch qubit/kubitach $\mathsf{X}$ i $\mathsf{Y},$ tak jak w poprzednim przykładzie. Mamy też dwa klasyczne bity, $\mathsf{A}$ i $\mathsf{B},$ oraz dwie bramki pomiarowe. Bramki pomiarowe reprezentują pomiary w bazie standardowej: Qubit/kubity są zmieniane w swoje stany po pomiarze, a wyniki pomiarów są nadpisywane na klasyczne bity, na które wskazują strzałki.

Często wygodnie jest przedstawiać pomiar jako bramkę, która przyjmuje qubit jako wejście i zwraca klasyczny bit (zamiast zwracać qubit w jego stanie po pomiarze i zapisywać wynik do osobnego klasycznego bitu). Oznacza to, że zmierzony qubit został odrzucony i można go bezpiecznie zignorować, przy czym jego stan zmienił się w $\vert 0\rangle$ lub $\vert 1\rangle$ w zależności od wyniku pomiaru.

Na przykład poniższy diagram układu reprezentuje ten sam proces co poprzedni diagram, ale z pominięciem $\mathsf{X}$ i $\mathsf{Y}$ po ich zmierzeniu:

W miarę postępu kursu zobaczymy więcej przykładów Quantum circuits, które są zazwyczaj bardziej skomplikowane niż proste przykłady powyżej. Oto kilka przykładów symboli używanych do oznaczania bramek często pojawiających się w diagramach układów:

• Bramki jednokubitowe są zazwyczaj pokazane jako kwadraty z literą wskazującą, o jaką operację chodzi, jak poniżej:

  

  Bramki NOT (lub równoważnie bramki $X$) są też czasem oznaczane kółkiem wokół znaku plus:

  

• Bramki swap są oznaczane następująco:

  

• Bramki sterowane (controlled-gates), czyli bramki opisujące operacje controlled-unitary, są oznaczane wypełnionym kółkiem (wskazującym kontrolę) połączonym pionową linią z wykonywaną operacją. Na przykład bramki controlled-NOT, controlled-controlled-NOT (czyli Toffoli) i controlled-swap (Fredkin) są oznaczane w następujący sposób:

  

• Dowolne operacje unitary na wielu qubit/kubitach można traktować jako bramki. Są one przedstawiane jako prostokąty opisane nazwą operacji unitary. Oto na przykład przedstawienie (nieokreślonej) operacji unitary $U$ jako bramki wraz z jej wersją sterowaną: