Схеми

У комп'ютерних науках схеми — це моделі обчислень, в яких інформація переноситься дротами через мережу вентилів, що представляють операції над інформацією, яку несуть дроти. Квантові схеми — це конкретна модель обчислень, заснована на цьому більш загальному понятті.

Хоча слово "схема" часто означає замкнений шлях, у моделях обчислень, що найчастіше вивчаються, замкнені шляхи насправді не допускаються. Тобто, коли ми розглядаємо схеми як обчислювальні моделі, ми зазвичай розглядаємо ациклічні схеми. Квантові схеми слідують цьому принципу; квантова схема представляє скінченну послідовність операцій, що не може містити зворотних зв'язків.

Булеві схеми

Ось приклад (класичної) булевої схеми, де дроти несуть двійкові значення, а вентилі представляють операції булевої логіки:

Потік інформації вздовж дротів іде зліва направо: дроти з лівого боку схеми, позначені $\mathsf{X}$ та $\mathsf{Y},$ є вхідними бітами, яким можна надати будь-яке двійкове значення на наш вибір, а дріт з правого боку є виходом. Проміжні дроти набувають значень, визначених вентилями, які обчислюються зліва направо.

Вентилями є вентилі AND (позначені $\wedge$), OR (позначені $\vee$) та NOT (позначені $\neg$). Функції, що обчислюються цими вентилями, напевно знайомі багатьом читачам, але тут вони представлені таблицями значень:

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

Два маленькі суцільні кола на дротах одразу праворуч від імен $\mathsf{X}$ та $\mathsf{Y}$ представляють операції розгалуження (fan-out), які просто створюють копію будь-якого значення, що несе дріт, на якому вони з'являються, дозволяючи це значення подавати на кілька вентилів. Операції розгалуження не завжди розглядаються як вентилі в класичному контексті; іноді їх трактують так, ніби вони "безкоштовні" в певному сенсі. Однак коли булеві схеми перетворюються на еквівалентні квантові, ми дійсно повинні явно класифікувати операції розгалуження як вентилі, щоб правильно з ними поводитись і обліковувати їх.

Ось та ж схема, проілюстрована в стилі, поширенішому в електротехніці, де використовуються стандартні символи для вентилів AND, OR та NOT:

Надалі ми не використовуватимемо цей стиль або ці конкретні символи вентилів, але використовуватимемо різні символи для представлення вентилів у квантових схемах, які будемо пояснювати в міру їх появи.

Конкретна схема в цьому прикладі обчислює виключне АБО (або XOR скорочено), що позначається символом $\oplus$:

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

На наступній діаграмі ми розглядаємо лише один вибір для входів: $\mathsf{X}=0$ та $\mathsf{Y}=1.$ Кожен дріт позначений значенням, яке він несе, щоб ти міг(ла) стежити за операціями. Вихідне значення дорівнює $1$ у цьому випадку, що є правильним значенням для XOR: $0 \oplus 1 = 1.$

Інші три можливих налаштування входів можна перевірити аналогічним чином.

Інші типи схем

Як зазначалося вище, поняття схеми в комп'ютерних науках є дуже загальним. Наприклад, іноді аналізуються схеми, дроти яких несуть значення, відмінні від $0$ та $1,$ а також вентилі, що представляють різні вибори операцій.

В арифметичних схемах, наприклад, дроти можуть нести цілочисельні значення, тоді як вентилі представляють арифметичні операції, такі як додавання та множення. На наступній схемі зображена арифметична схема, яка приймає два змінні вхідних значення ($x$ та $y$), а також третій вхід, встановлений на значення $1.$ Значення, що несуть дроти, як функції від значень $x$ та $y,$ показані на схемі.

Ми також можемо розглядати схеми, що включають випадковість, наприклад ті, де вентилі представляють імовірнісні операції.

Квантові схеми

У моделі квантових схем дроти представляють кубіти, а вентилі — операції над цими кубітами. Наразі ми зосередимося на операціях, з якими вже зустрічались, а саме унітарних операціях та вимірюваннях у стандартному базисі. У міру вивчення інших видів квантових операцій та вимірювань ми зможемо відповідно розширити нашу модель.

Ось простий приклад квантової схеми:

У цій схемі ми маємо один кубіт на ім'я $\mathsf{X},$ представлений горизонтальною лінією, та послідовність вентилів, що представляють унітарні операції на цьому кубіті. Так само як і в прикладах вище, потік інформації йде зліва направо — тому перша виконувана операція — це операція Адамара, друга — операція $S$, третя — ще одна операція Адамара, а остання — операція $T$. Отже, виконання всієї схеми застосовує композицію цих операцій $T H S H$ до кубіта $\mathsf{X}.$

Іноді ми можемо хотіти явно вказати вхідні або вихідні стани схем. Наприклад, якщо ми застосуємо операцію $T H S H$ до стану $\vert 0\rangle,$ ми отримаємо стан $\frac{1+i}{2}\vert 0\rangle + \frac{1}{\sqrt{2}} \vert 1 \rangle.$ Це можна позначити так:

Квантові схеми часто починаються з усіма кубітами, ініціалізованими до $\vert 0\rangle,$ як у цьому випадку, але також бувають ситуації, коли вхідні кубіти спочатку встановлені в різні стани. Ось ще один приклад квантової схеми, цього разу з двома кубітами:

Як завжди, вентиль позначений $H$ відноситься до операції Адамара, тоді як другий вентиль — це операція керованого NOT: суцільне коло представляє керуючий кубіт, а коло, що нагадує символ $\oplus,$ позначає цільовий кубіт.

Перш ніж детальніше розглядати цю схему та пояснити, що вона робить, необхідно спочатку уточнити, як упорядковуються кубіти в квантових схемах. Це пов'язано з конвенцією, яку Qiskit використовує для іменування та впорядкування систем, яка була коротко згадана в попередньому уроці.

Конвенція впорядкування кубітів у Qiskit для схем

У Qiskit найвищий кубіт у діаграмі схеми має індекс $0$ і відповідає крайній правій позиції в кортежі кубітів (або в рядку, декартовому добутку або тензорному добутку, що відповідає цьому кортежу), другий зверху кубіт має індекс $1$ і відповідає позиції другій справа в кортежі, і так далі. Найнижчий кубіт, що має найбільший індекс, відповідає крайній лівій позиції в кортежі. Зокрема, імена за замовчуванням у Qiskit для кубітів у схемі з $n$ кубітами представлені $n$-кортежем $(\mathsf{q_{n-1}},\ldots,\mathsf{q_{0}}),$ де $\mathsf{q_{0}}$ — це кубіт зверху, а $\mathsf{q_{n-1}}$ — знизу в діаграмах квантових схем.

Зверни увагу, що це є інверсією більш поширеної конвенції впорядкування кубітів у схемах і є частим джерелом плутанини. Додаткову інформацію про цю конвенцію впорядкування можна знайти на сторінці документації Порядок бітів у Qiskit.

Хоча ми іноді відступаємо від конкретних імен за замовчуванням $\mathsf{q_{0}},\ldots,\mathsf{q_{n-1}},$ що використовуються Qiskit для кубітів, ми завжди дотримуватимемося конвенції впорядкування, описаної вище, при інтерпретації діаграм схем протягом усього курсу. Таким чином, наша інтерпретація наведеної схеми полягає в тому, що вона описує операцію на парі кубітів $(\mathsf{X},\mathsf{Y}).$ Якщо вхід схеми є квантовим станом $\vert\psi\rangle \otimes \vert\phi\rangle,$ наприклад, то це означає, що нижній кубіт $\mathsf{X}$ починається зі стану $\vert\psi\rangle,$ а верхній кубіт $\mathsf{Y}$ — зі стану $\vert\phi\rangle.$

Щоб зрозуміти, що робить схема, можна пройтися крізь її операції зліва направо.

1. Перша операція — це операція Адамара на $\mathsf{Y}$:

   

   При застосуванні вентиля до одного кубіта, як тут, з іншими кубітами нічого не відбувається (у цьому випадку — лише з одним іншим кубітом). Відсутність змін еквівалентна виконанню тотожної операції. Пунктирний прямокутник на малюнку вище представляє тому таку операцію:

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

   Зверни увагу, що матриця тотожності знаходиться ліворуч від тензорного добутку, а $H$ — праворуч, що відповідає конвенції впорядкування Qiskit.

2. Друга операція — це операція керованого NOT, де $\mathsf{Y}$ є керуючим, а $\mathsf{X}$ — цільовим:

   

   Дія вентиля керованого NOT на стани стандартного базису є такою:

   

   Враховуючи, що ми впорядковуємо кубіти як $(\mathsf{X}, \mathsf{Y}),$ де $\mathsf{X}$ знаходиться знизу, а $\mathsf{Y}$ — зверху нашої схеми, матричне представлення вентиля керованого NOT є таким:

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

Унітарна операція, реалізована всією схемою, якій ми надамо ім'я $U,$ є композицією операцій:

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

Зокрема, пригадуючи наш запис для станів Белла,

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

ми знаходимо, що

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

Ця схема таким чином дає нам спосіб створити стан $\vert\phi^+\rangle,$ якщо ми запустимо її на двох кубітах, ініціалізованих до $\vert 00\rangle.$ Загалом вона дає нам спосіб перетворити стандартний базис на базис Белла. (Зверни увагу, що хоча для цього прикладу це не важливо, фазовий множник $-1$ в останньому стані, $-\vert \psi^-\rangle,$ можна усунути, якщо потрібно, зробивши невелике доповнення до схеми. Наприклад, ми могли б додати вентиль керованого $Z$ на початку, який схожий на вентиль керованого NOT за винятком того, що операція $Z$ застосовується до цільового кубіта замість операції NOT, коли керуючий встановлений в $1.$ Або ж ми могли б додати вентиль swap в кінці. Будь-який з варіантів усуває мінус без впливу на дію схеми на трьох інших стандартних базисних станах.)

Загалом квантові схеми можуть містити будь-яку кількість дротів кубітів. Ми також можемо включати дроти класичних бітів, які позначаються подвійними лініями, як у цьому прикладі:

Тут у нас є вентиль Адамара та вентиль керованого NOT на двох кубітах $\mathsf{X}$ та $\mathsf{Y},$ так само як і в попередньому прикладі. Також є два класичні біти, $\mathsf{A}$ та $\mathsf{B},$ а також два вентилі вимірювання. Вентилі вимірювання представляють вимірювання в стандартному базисі: кубіти змінюються до своїх поствимірювальних станів, тоді як результати вимірювань перезаписуються на класичні біти, на які вказують стрілки.

Часто зручно зображувати вимірювання як вентиль, що приймає кубіт як вхід і видає класичний біт (на відміну від виведення кубіта в його поствимірювальному стані та запису результату в окремий класичний біт). Це означає, що виміряний кубіт відкинуто і надалі може бути безпечно проігнорований, його стан змінився на $\vert 0\rangle$ або $\vert 1\rangle$ залежно від результату вимірювання.

Наприклад, наступна діаграма схеми представляє той самий процес, що і попередня, але де ми не враховуємо $\mathsf{X}$ та $\mathsf{Y}$ після їх вимірювання:

У міру продовження курсу ми побачимо більше прикладів квантових схем, які зазвичай складніші за прості приклади вище. Ось кілька прикладів символів, що використовуються для позначення вентилів, які часто зустрічаються в діаграмах схем:

• Однокубітні вентилі зазвичай показуються як квадрати з буквою, що вказує, яка це операція, ось так:

  

  Вентилі NOT (або еквівалентно, вентилі $X$) також іноді позначаються колом з плюсом всередині:

  

• Вентилі swap позначаються так:

  

• Керовані вентилі, тобто вентилі, що описують керовано-унітарні операції, позначаються суцільним колом (що вказує на керуючий кубіт), з'єднаним вертикальною лінією з операцією, якою керують. Наприклад, вентилі керованого NOT, вентилі керованого-керованого NOT (або Тоффолі) та вентилі керованого swap (Фредкіна) позначаються так:

  

• Довільні унітарні операції на множинних кубітах можна розглядати як вентилі. Вони зображуються прямокутниками, позначеними ім'ям унітарної операції. Наприклад, ось зображення (невизначеної) унітарної операції $U$ як вентиля разом із керованою версією цього вентиля: