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). Niedzianie się niczego 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ą: