Класичні обчислення на квантових комп'ютерах

Тепер звернемося до реалізації класичних алгоритмів на квантових комп'ютерах. Ми побачимо, що будь-яке обчислення, яке можна виконати з класичною булевою схемою, можна також виконати квантовою схемою з подібними асимптотичними обчислювальними витратами. Більш того, це можна зробити «чисто» — у спосіб, що буде описаний незабаром, — що є важливою вимогою для використання таких обчислень як підпрограм усередині більших квантових обчислень.

Симуляція булевих схем квантовими схемами

Булеві схеми складаються з вентилів AND, OR, NOT та FANOUT. Щоб симулювати булеві схеми квантовими схемами, почнемо з показу того, як кожен із цих чотирьох вентилів можна замінити квантовими вентилями. Після цього перетворення заданої булевої схеми на квантову — це проста справа симуляції одного вентиля за раз. Для цього знадобляться лише вентилі NOT, контрольовані NOT (CNOT) і вентилі Тоффолі — всі вони є детерміновними операціями, а також унітарними.

Вентилі Тоффолі

Вентилі Тоффолі можна також описати як контрольовано-контрольовані вентилі NOT, дія яких на стандартні базисні стани показана на наступному рисунку.

З урахуванням того, що ми використовуємо конвенцію впорядкування Qiskit, де кубіти впорядковані зі зростанням значущості зверху донизу, матрична вистава цього вентиля виглядає так:

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

Ще один спосіб думати про вентилі Тоффолі: вони, по суті, є запитними вентилями для функції AND в тому сенсі, що відповідають шаблону, який ми бачили в попередньому уроці для унітарних запитних вентилів з довільними бінарними рядковими входами та виходами.

Вентилі Тоффолі не входять до стандартного набору вентилів, розглянутого раніше в уроці, але з вентилів $H,$ $T,$ $T^{\dagger}$ та CNOT можна побудувати вентиль Тоффолі таким чином:

Симуляція булевих вентилів за допомогою Тоффолі, CNOT і NOT

Один вентиль Тоффолі у поєднанні з кількома NOT-вентилями може реалізувати вентилі AND та OR, а FANOUT легко реалізується за допомогою CNOT, як показано на наступних схемах.

У всіх трьох випадках кубіти, на які діють вентилі AND, OR та FANOUT, надходять зліва як входи, і для кожного з них потрібен один робочий кубіт, ініціалізований у нульовий стан. Ці робочі кубіти зображені всередині прямокутників, що представляють реалізації вентилів, щоб підкреслити, що вони нові і тому є частиною вартості цих реалізацій.

Для вентилів AND та OR є також два зайві кубіти, крім вихідного. Наприклад, всередині прямокутника на схемі для симуляції AND два верхніх кубіти залишаються у станах $\vert a\rangle$ та $\vert b\rangle.$ Ці кубіти показані як такі, що залишаються всередині прямокутника, бо вони більше не потрібні і не є частиною виходу. Їх можна поки що ігнорувати, хоча ми повернемося до них незабаром.

Вентиль NOT з нашого стандартного набору квантових вентилів, тому для нього не потрібна симуляція.

Симуляція булевих схем вентиль за вентилем

Припустимо, є звичайна булева схема $C,$ складена з вентилів AND, OR, NOT та FANOUT, з $n$ вхідними бітами і $m$ вихідними бітами. Нехай $t = \operatorname{size}(C)$ — кількість вентилів у $C,$ і назвемо $f$ функцію, яку обчислює $C,$ у вигляді

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

для $\Sigma = \{0,1\}.$

Тепер уявімо, що ми по одному проходимо вентилі AND, OR та FANOUT схеми $C,$ замінюючи кожен відповідною симуляцією, описаною вище, включаючи додавання необхідних робочих кубітів. Назвемо отриману схему $R$ і впорядкуємо кубіти $R$ так, щоб $n$ вхідних бітів $C$ відповідали верхнім $n$ кубітам $R,$ а робочі кубіти були знизу.

Тут $k$ — кількість необхідних робочих кубітів (по одному для кожного вентиля AND, OR та FANOUT схеми $C$), а $g$ — функція вигляду $g:\Sigma^n \rightarrow \Sigma^{n+k-m}$, що описує стани зайвих кубітів, створених симуляціями вентилів після виконання $R$. На рисунку кубіти, що відповідають виходу $f(x),$ знаходяться вгорі, а зайві кубіти зі значеннями $g(x)$ — знизу. Якщо бажаємо, можемо досягти цього, переставивши кубіти за допомогою SWAP-вентилів, які можна реалізувати трьома контрольованими NOT, як тут:

Як ми побачимо в наступному розділі, переставляти вихідні кубіти насправді не обов'язково, але це можна легко зробити за бажання.

Функція $g,$ що описує класичні стани зайвих кубітів, визначається схемою $C,$ але насправді нам не потрібно занадто перейматись нею; нам не важливо, в якому конкретно стані ці кубіти опиняються після завершення обчислення. Літера $g$ стоїть після $f,$ тому це розумна назва і з цієї причини, але є ще одна, краща причина для назви $g$ — скорочення від garbage (сміття).

Прибирання сміття

Якщо нас цікавить лише обчислення функції $f,$ яку обчислює дана булева схема $C,$ з квантовою схемою, ми можемо зупинитися на покроковій симуляції, описаній вище. Це означає, що на додаток до виходу функції залишиться купа сміття.

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

На щастя, прибрати сміття нескладно. Ключем є використання того факту, що оскільки $R$ — квантова схема, ми можемо запустити її у зворотному напрямку, просто замінивши кожен вентиль його оберненим і застосувавши їх у зворотному порядку, отримавши квантову схему для операції $R^{\dagger}.$ Вентилі Тоффолі, CNOT та NOT є власними оберненими, тому запуск $R$ у зворотному напрямку — це просто питання застосування вентилів у зворотному порядку, але загалом будь-яку квантову схему можна обернути так само.

Конкретно, ми додаємо $m$ кубітів (нагадаємо, що функція $f$ має $m$ вихідних бітів), використовуємо вентилі CNOT для копіювання виходу $R$ на ці кубіти і обертаємо $R$ для прибирання сміття. Наступний рисунок ілюструє отриману схему і описує її дію на стандартні базисні стани.

Якщо поставити рамку навколо всієї схеми і назвати її $Q,$ вона виглядає так:

Якщо $C$ має $t$ вентилів, то схема $Q$ матиме $O(t)$ вентилів.

Якщо знехтувати $k$ додатковими робочими кубітами, то маємо схему $Q,$ яка функціонує точно як запитний вентиль для функції $f.$ Якщо просто хочемо обчислити функцію $f$ на рядку $x,$ можна встановити $y = 0^m$ і результуюче значення $f(x)$ з'явиться на нижніх $m$ кубітах — або можна подати інший стан на нижні $m$ кубітів за бажанням (можливо, щоб використати фазовий зворотний зв'язок, як в алгоритмах Дойча або Дойча-Йозса).

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

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

Реалізація оборотних функцій

Описана конструкція дозволяє симулювати будь-яку булеву схему квантовою схемою без сміття. Якщо $C$ — булева схема, що реалізує функцію $f:\Sigma^n \rightarrow \Sigma^m,$ то отримуємо квантову схему $Q,$ яка діє так на стандартні базисні стани:

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

Число $k$ вказує на загальну кількість необхідних робочих кубітів. Цього достатньо для цілей цього курсу, але методологію можна розвинути далі, коли функція $f$ сама є оборотною.

Точніше, припустимо, що функція $f$ має вигляд $f:\Sigma^n \rightarrow \Sigma^n,$ і також припустимо, що існує функція $f^{-1}$ така, що $f^{-1}(f(x)) = x$ для кожного $x\in\Sigma^n$ (яка є єдиною, коли існує). Це означає, що операція, яка перетворює $\vert x \rangle$ у $\vert f(x) \rangle$ для кожного $x\in\Sigma^n,$ є унітарною, тому можна сподіватися побудувати квантову схему, яка реалізує унітарну операцію, визначену як

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

для кожного $x\in\Sigma^n.$

Щоб уточнити, унітарність цієї операції залежить від оборотності $f$ — вона не є унітарною, коли $f$ необоротна. Не враховуючи робочі кубіти, $U$ відрізняється від операції, яку реалізує схема $Q,$ оскільки ми не зберігаємо копію входу та не XOR-имо її з довільним рядком, а замінюємо $x$ на $f(x).$

Питання: коли $f$ є оборотною, чи можна це зробити?

Відповідь — так, за умови, що нам дозволено використовувати робочі кубіти і, крім булевої схеми, що обчислює $f,$ ми також маємо схему для $f^{-1}.$ Тобто це не є обхідним шляхом для обчислювального обернення функцій, коли ми ще не знаємо, як це робити! Наступна діаграма ілюструє, як це можна зробити, компонуючи дві квантові схеми — $Q_f$ та $Q_{f^{-1}},$ отримані окремо для функцій $f$ та $f^{-1}$ за описаним вище методом, разом з $n$ вентилями транспозиції, беручи $k$ рівним максимуму кількостей необхідних робочих кубітів для $Q_f$ та $Q_{f^{-1}}$.