Опис алгоритму Гровера

У цьому розділі ми розглянемо алгоритм Гровера. Почнемо з обговорення фазових query-гейтів і способів їх побудови, а потім перейдемо до опису самого алгоритму Гровера. Насамкінець коротко поговоримо про те, як цей алгоритм природно застосовується до задач пошуку.

Фазові query-гейти

Алгоритм Гровера використовує операції, відомі як фазові query-гейти. На відміну від звичайного query-гейта $U_f$, визначеного для заданої функції $f$ стандартним способом, описаним раніше, фазовий query-гейт для функції $f$ визначається так:

$$Z_f \vert x\rangle = (-1)^{f(x)} \vert x\rangle$$

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

Операцію $Z_f$ можна реалізувати за допомогою одного query-гейта $U_f$, як показано на цій схемі:

Ця реалізація використовує ефект phase kickback і потребує одного допоміжного кубіта, ініціалізованого в стан $\vert -\rangle$. Після завершення роботи цей кубіт залишається в стані $\vert - \rangle$ і може бути повторно використаний (наприклад, для реалізації наступних гейтів $Z_f$) або просто відкинутий.

Окрім операції $Z_f$, ми також використаємо фазовий query-гейт для $n$-бітної функції АБО, яка визначається так для кожного рядка $x\in\Sigma^n$.

$$\mathrm{OR}(x) = \begin{cases} 0 & x = 0^n\\[0.5mm] 1 & x \neq 0^n \end{cases}$$

Явно фазовий query-гейт для $n$-бітної функції АБО діє так:

$$Z_{\mathrm{OR}} \vert x\rangle = \begin{cases} \vert x\rangle & x = 0^n \\[0.5mm] - \vert x\rangle & x \neq 0^n. \end{cases}$$

Зауважимо, що це дія $Z_{\mathrm{OR}}$ на стандартних базисних станах; її поведінка на довільних станах визначається з цього виразу за лінійністю.

Операцію $Z_{\mathrm{OR}}$ можна реалізувати у вигляді квантової схеми: спочатку будуємо булеву схему для функції АБО, потім конструюємо операцію $U_{\mathrm{OR}}$ (тобто стандартний query-гейт для $n$-бітної функції АБО) за процедурою, описаною в уроці Квантово-алгоритмічні основи, і, нарешті, отримуємо операцію $Z_{\mathrm{OR}}$ за допомогою ефекту phase kickback, як описано вище. Зверни увагу, що операція $Z_{\mathrm{OR}}$ не залежить від функції $f$ і тому може бути реалізована квантовою схемою, що не містить жодного query-гейта.

Опис алгоритму

Маючи дві операції $Z_f$ та $Z_{\mathrm{OR}}$, ми можемо описати алгоритм Гровера.

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

Алгоритм Гровера

1. Ініціалізуй регістр $\mathsf{Q}$ з $n$ кубітів у нульовий стан $\vert 0^n \rangle$, а потім застосуй операцію Адамара до кожного кубіта $\mathsf{Q}$.
2. Застосуй $t$ разів унітарну операцію $G = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f$ до регістра $\mathsf{Q}$
3. Виміряй кубіти $\mathsf{Q}$ в стандартному базисі і виведи отриманий рядок.

Операцію $G = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f$, що ітерується на кроці 2, упродовж усього уроку ми будемо називати операцією Гровера. Нижче наведено зображення квантової схеми для операції Гровера при $n=7\!:$

На цій діаграмі операція $Z_f$ зображена більшою за $Z_{\mathrm{OR}}$ — як неформальна візуальна підказка, що вона, ймовірно, є більш витратною. Зокрема, у рамках query-моделі $Z_f$ потребує одного запиту, тоді як $Z_{\mathrm{OR}}$ — жодного. Якщо ж ми маємо булеву схему для функції $f$ і перетворюємо її на квантову схему для $Z_f,$ то можна очікувати, що отримана квантова схема буде більшою і складнішою, ніж схема для $Z_{\mathrm{OR}}.$

Нижче зображено квантову схему для всього алгоритму при $n=7$ і $t=3$. Для більших значень $t$ можна просто вставляти додаткові копії операції Гровера безпосередньо перед вимірюваннями.

Застосування до пошуку

Алгоритм Гровера можна застосувати до задачі пошуку таким чином:

• Вибери число $t$ на кроці 2. (Це обговорюється пізніше в уроці.)

• Запусти алгоритм Гровера на функції $f$ з вибраним значенням $t$, щоб отримати рядок $x\in\Sigma^n$.

• Зроби запит до функції $f$ на рядку $x,$ щоб перевірити, чи є він допустимим розв'язком:

  • Якщо $f(x) = 1$, то ми знайшли розв'язок, тож можна зупинитися і вивести $x$.

  • Якщо $f(x) = 0$, — можна або запустити процедуру знову (можливо, з іншим $t$), або відмовитися і вивести «немає розв'язку».

Після аналізу роботи алгоритму Гровера ми побачимо, що, взявши $t = O(\sqrt{N})$, отримаємо розв'язок задачі пошуку (якщо він існує) з великою ймовірністю.