Запитна модель обчислень

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

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

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

Опис моделі

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

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

У цьому уроці ми працюватимемо виключно з двійковими рядками, а не з рядками, що містять різні символи, тому для зручності надалі позначимо двійковий алфавіт $\Sigma = \{0,1\}$. Ми розглядатимемо різні обчислювальні задачі, кілька простих прикладів яких буде описано незабаром, але для всіх них вхідні дані представлені функцією вигляду

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

для двох натуральних чисел $n$ та $m.$ Природно, замість $f$ можна вибрати іншу назву, але протягом усього уроку ми будемо користуватися $f$.

Сказати, що обчислення робить запит, означає, що вибирається деякий рядок $x \in \Sigma^n$, після чого оракул надає обчисленню рядок $f(x)\in\Sigma^m$. Точний спосіб роботи цього механізму для квантових алгоритмів буде описаний незабаром — необхідно переконатися, що це можливо реалізувати унітарною квантовою операцією, яка допускає запити в суперпозиції, — але поки що можна думати про це інтуїтивно на загальному рівні.

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

Приклади запитних задач

Ось кілька простих прикладів запитних задач.

• АБО. Вхідна функція має вигляд $f:\Sigma^n \rightarrow \Sigma$ (тобто $m=1$ для цієї задачі). Завдання — вивести $1$, якщо існує рядок $x\in\Sigma^n$, для якого $f(x) = 1,$ і вивести $0$, якщо такого рядка немає. Якщо розглядати функцію $f$ як послідовність $2^n$ бітів з довільним доступом, задача полягає в обчисленні АБО цих бітів.

• Парність. Вхідна функція знову має вигляд $f:\Sigma^n \rightarrow \Sigma.$ Завдання — визначити, є кількість рядків $x\in\Sigma^n$, для яких $f(x) = 1,$ парною чи непарною. Точніше, необхідно вивести $0$, якщо множина $\{x\in\Sigma^n : f(x) = 1\}$ має парну кількість елементів, і $1$ — якщо непарну. Якщо розглядати функцію $f$ як послідовність $2^n$ бітів з довільним доступом, задача полягає в обчисленні парності (або виключного АБО) цих бітів.

• Мінімум. Вхідна функція має вигляд $f:\Sigma^n \rightarrow \Sigma^m$ для будь-яких натуральних $n$ та $m.$ Необхідно вивести рядок $y \in \{f(x) : x\in\Sigma^n\}$, що стоїть першим у лексикографічному (тобто словниковому) порядку $\Sigma^m.$ Якщо розглядати функцію $f$ як послідовність $2^n$ цілих чисел, записаних як рядки довжини $m$ у двійковому записі з довільним доступом, задача полягає в знаходженні мінімуму цих чисел.

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

Ось приклад задачі з обіцянкою:

• Унікальний пошук. Вхідна функція має вигляд $f:\Sigma^n \rightarrow \Sigma,$ і нам обіцяно, що існує рівно один рядок $z\in\Sigma^n$, для якого $f(z) = 1,$ а $f(x) = 0$ для всіх рядків $x\neq z.$ Завдання — знайти цей унікальний рядок $z.$

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

На противагу цьому, деякі запитні задачі зовсім не є «природними». Насправді в дослідженнях запитної моделі інколи формулюються дуже складні та штучні задачі, і важко уявити, що хтось захотів би вирішувати їх на практиці. Але це не означає, що такі задачі нецікаві! Те, що здається штучним або неприродним спочатку, може дати несподівані підказки або надихнути на нові ідеї. Квантовий алгоритм Шора для факторизації, натхненний алгоритмом Саймона, — блискучий приклад. Крім того, важливою частиною вивчення запитної моделі є пошук крайніх випадків, які можуть пролити світло як на потенційні переваги, так і на обмеження квантових обчислень.

Запитні вентилі

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

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

Коли булева схема будується для запитної задачі, доступ до вхідної функції $f$ здійснюється через ці вентилі, а кількість запитів схеми — це просто кількість запитних вентилів у ній. Вхідні дроти самої булевої схеми ініціалізуються фіксованими значеннями, які слід розглядати як частину алгоритму (а не як вхідні дані задачі).

Наприклад, ось булева схема з класичними запитними вентилями, що розв'язує задачу парності для функції вигляду $f:\Sigma\rightarrow\Sigma$:

Цей алгоритм робить два запити, оскільки містить два запитних вентилі. Принцип роботи: функція $f$ запитується на двох можливих входах — $0$ та $1,$ — а результати подаються до булевої схеми, що обчислює XOR. (Ця конкретна схема була наведена як приклад булевої схеми в уроці Квантові схеми курсу Основи квантової інформації.)

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

Тут припускається, що $x\in\Sigma^n$ та $y\in\Sigma^m$ — довільні рядки. Позначення $y\oplus f(x)$ означає побітове виключне АБО двох рядків, що мають у цьому випадку довжину $m$. Наприклад, $001 \oplus 101 = 100.$

Інтуїтивно, вентиль $U_f$ (для будь-якої обраної функції $f$) передає вхідний рядок $x$ без змін і додає значення функції $f(x)$ до вхідного рядка $y$ через XOR, що є унітарною операцією для будь-якого вибору функції $f.$ Насправді це детерміновна операція, яка є своїм власним оберненим. Це означає, що як матриця $U_f$ завжди є матрицею перестановки — матрицею, яка має рівно по одній одиниці в кожному рядку та стовпці, а всі інші елементи рівні $0.$ Застосування матриці перестановки до вектора просто переставляє елементи вектора (звідси й назва матриця перестановки), не змінюючи його евклідову норму — що й підтверджує унітарність матриць перестановок.

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

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