Неструктурований пошук

Зміст

Розпочнемо з опису задачі, яку розв'язує алгоритм Ґровера. Як завжди, позначимо двійковий алфавіт $\Sigma = \{0,1\}$ протягом усього обговорення.

Нехай

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

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

Алгоритм Ґровера виконує пошук рядка $x\in\Sigma^n$, для якого $f(x) = 1$. Такі рядки ми називатимемо розв'язками задачі пошуку. Якщо розв'язків кілька, будь-який із них вважається правильною відповіддю; якщо розв'язків немає, правильна відповідь — повідомити про їхню відсутність.

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

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

Один класичний спосіб виконати це завдання пошуку — просто перебрати всі рядки $x\in\Sigma^n$, обчислюючи $f$ для кожного, щоб перевірити, чи є він розв'язком. Позначимо далі

$$N = 2^n$$

для зручності. У $\Sigma^n$ є $N$ рядків, тому їх перебір вимагає $N$ обчислень $f$. Якщо ми обмежені обчисленням $f$ на обраних вхідних даних і хочемо гарантовано знайти відповідь, це найкраще, що можна зробити детермінованим алгоритмом. При ймовірнісному підході можна спробувати заощадити час, випадково обираючи вхідні рядки для $f$, але все одно знадобиться $O(N)$ обчислень $f$ для високої ймовірності успіху.

Алгоритм Ґровера розв'язує цю задачу пошуку з високою ймовірністю, виконуючи лише $O(\sqrt{N})$ обчислень $f$. Уточнимо: ці обчислення функції відбуваються у суперпозиції, аналогічно до алгоритмів із запитами з уроку «Квантові алгоритми з запитами», включаючи алгоритм Дойча, алгоритм Дойча–Йожі та алгоритм Саймона. На відміну від них, алгоритм Ґровера є ітеративним: він обчислює $f$ на суперпозиціях вхідних рядків і чергує ці обчислення з іншими операціями, що створюють інтерференційні картини, приводячи до розв'язку з високою ймовірністю (якщо він існує) після $O(\sqrt{N})$ ітерацій.

Формальна постановка задачі

Формалізуємо задачу, яку розв'язує алгоритм Ґровера, у моделі обчислень із запитами. Тобто припустимо, що ми маємо доступ до функції $f:\Sigma^n\rightarrow\Sigma$ через гейт запиту, визначений звичайним чином:

$$U_f \bigl( \vert a\rangle \vert x\rangle \bigr) = \vert a \oplus f(x) \rangle \vert x \rangle$$

для кожного $x\in\Sigma^n$ та $a\in\Sigma$. Це дія $U_f$ на базисних станах, а її дія в загальному випадку визначається лінійністю.

Як обговорювалося в уроці «Основи квантових алгоритмів», маючи булеву схему для обчислення $f$, її можна перетворити на квантову схему, що реалізує $U_f$ (використовуючи певну кількість додаткових кубітів, що починають і закінчують обчислення у стані $\vert 0\rangle$). Таким чином, хоча ми використовуємо модель запитів для формалізації задачі, яку розв'язує алгоритм Ґровера, він не обмежений цією моделлю: алгоритм Ґровера можна запускати для будь-якої функції $f$, для якої є булева схема.

Ось точне формулювання задачі, яка називається Пошук, оскільки ми шукаємо розв'язок — рядок $x$, для якого $f$ набуває значення $1$.

Пошук

Вхід: функція $f:\Sigma^n\rightarrow\Sigma$
Вихід: рядок $x\in\Sigma^n$, що задовольняє $f(x) = 1$, або «розв'язок відсутній», якщо такого рядка $x$ не існує

Зауважимо, що це не задача з обіцянкою — функція $f$ є довільною. Проте корисно розглянути таку варіацію з обіцянкою, де гарантовано існує рівно один розв'язок. Ця задача наводилася як приклад задачі з обіцянкою в уроці «Квантові алгоритми з запитами».

Унікальний пошук

Вхід: функція вигляду $f:\Sigma^n \rightarrow \Sigma$
Обіцянка: існує рівно один рядок $z\in\Sigma^n$, для якого $f(z) = 1$, і $f(x) = 0$ для всіх рядків $x\neq z$
Вихід: рядок $z$

Також зауважимо, що задача Або, згадана в тому ж уроці, тісно пов'язана із задачею Пошук. У тій задачі мета — лише визначити, чи існує розв'язок, а не знайти його.