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

Алгоритм Ґровера (також GSA від англ. Grover search algorithm) — квантовий алгоритм вирішення задачі перебору, тобто пошуку рішення рівняння

${\displaystyle (1)\qquad f(x)=1,}$

де ${\displaystyle f}$ є булева функція від ${\displaystyle n}$ змінних, а ${\displaystyle x}$ — двійковий вектор довжини ${\displaystyle n}$. Був запропонований американським математиком в 1996 році.

Представлення алгоритму Ґровера

Передбачається, що функція задана у вигляді чорного ящика, або оракула, тобто в ході рішення ми можемо тільки задавати оракула питання типу: «чому дорівнює ${\displaystyle f}$ при даному ${\displaystyle x}$», І після отримання відповіді використовувати його в подальших обчисленнях. Тобто завдання вирішення рівняння (1) є загальною формою завдання перебору; тут потрібно знайти «пароль до пристрою ${\displaystyle f}$», Що класично вимагає прямого перебору всіх ${\displaystyle N=2^{n}}$ варіантів.

Алгоритм Ґровера знаходить деякий корінь рівняння, використовуючи ${\displaystyle {\frac {\pi }{4}}{\sqrt {N}}}$ звернень до функції ${\displaystyle f}$, з використанням ${\displaystyle O(n)}$ кубітів.

Сенс алгоритму Ґровера складається в «посиленні амплітуди» цільового стану за рахунок зменшення амплітуди всіх інших станів. Геометрично алгоритм Ґровера полягає в обертанні поточного вектора стану квантового комп'ютера у напрямку точно до цільового стану (рух по найкоротшому шляху забезпечує оптимальність алгоритму Ґровера). Кожен крок дає обертання на кут ${\displaystyle 2\alpha }$, де кут між ${\displaystyle I_{\tilde {0}}}$ і  ${\displaystyle I_{x_{tar}}}$становить ${\displaystyle \pi /2-\alpha }$. Подальше продовження ітерацій оператора G дасть продовження обходу кола в речовій площині, породженої даними векторами.

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

Застосування алгоритму

Хоча мета алгоритму Ґровера зазвичай описується як «пошук в базі даних», можна більш точно описати його як «інвертування функції». Насправді, так як «пророча машина» неструктурованої бази даних вимагає, хоча б лінійної складності, алгоритм не може бути використаний для реальних баз даних. Грубо кажучи, якщо функцію ${\displaystyle y=f(x)}$ можна оцінити на квантовому комп'ютері, алгоритм Ґровера обчислює ${\displaystyle x}$ за заданим ${\displaystyle y}$. Інверсія функція пов'язана з пошуком бази даних, тому що ми могли б придумати функцію, яка виробляє одне конкретне значення ${\displaystyle y}$ (наприклад «істинно»), якщо ${\displaystyle x}$ відповідає потрібному запису в базі даних, і інше значення ${\displaystyle y}$ («хибно») для інших значень ${\displaystyle x}$.

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

Налаштування

Розглянемо невпорядовану базу даних з ${\displaystyle N}$ записів. Алгоритм вимагає ${\displaystyle N}$-вимірний простір станів ${\displaystyle {\mathcal {H}}}$, в яких можуть перебувати ${\displaystyle n=\lceil log_{2}N\rceil }$ кубітів. Розглянемо задачу визначення індексу записи бази даних, який задовольняє деяким заданим критеріям. Нехай ${\displaystyle f}$ — функція, яка показує всі записи бази даних 0 або 1, де ${\displaystyle f(x)=1}$ тоді і тільки тоді, коли ${\displaystyle x}$ відповідає критерію пошуку (${\displaystyle x=\omega }$). Ми отримали доступ до цієї функції ${\displaystyle f}$ у вигляді унітарного оператора ${\displaystyle U_{\omega }}$ (так званий оракул або пророча машина), що діє в такий спосіб:

${\displaystyle {\begin{cases}U_{\omega }|x\rangle =-|x\rangle &{\text{for }}x=\omega {\text{, that is, }}f(x)=1,\\U_{\omega }|x\rangle =|x\rangle &{\text{for }}x\neq \omega {\text{, that is, }}f(x)=0.\end{cases}}}$

або коротко,

${\displaystyle U_{\omega }|x\rangle =(-1)^{f(x)}|x\rangle }$.

Тобто це фазовий оракул (такий, що додає мінус перед поміченими значеннями ${\displaystyle x}$, а інші залишає без змін). Альтернативне визначення ${\displaystyle U_{\omega }}$ за допомогою іншого типу оракулу ${\displaystyle U_{f}}$ може виникнути, якщо ми маємо додатковий кубіт (як у квантовій системі, яка зображена нижче). Операція ${\displaystyle U_{f}}$ тоді представляє собою:

${\displaystyle {\begin{cases}U_{f}|x\rangle |y\rangle =|x\rangle |\neg y\rangle &{\text{for }}x=\omega {\text{, that is, }}f(x)=1,\\U_{f}|x\rangle |y\rangle =|x\rangle |y\rangle &{\text{for }}x\neq \omega {\text{, that is, }}f(x)=0,\end{cases}}}$

або коротко,

${\displaystyle U_{f}|x\rangle |y\rangle =|x\rangle |y\oplus f(x)\rangle .}$

Це природний спосіб реалізувати бінарну операцію з використанням методу зворотного обчислення. Зверніть увагу, що якщо додатковий кубіт знаходиться в стані ${\displaystyle |-\rangle ={\frac {1}{\sqrt {2}}}{\big (}|0\rangle -|1\rangle {\big )}=H|1\rangle }$, ми отримаємо наш бажаний оракул ${\displaystyle U_{\omega }}$ та додатковий кубіт:

${\displaystyle {\begin{aligned}U_{f}{\big (}|x\rangle \otimes |-\rangle {\big )}&={\frac {1}{\sqrt {2}}}\left(U_{f}|x\rangle |0\rangle -U_{f}|x\rangle |1\rangle \right)\\&={\frac {1}{\sqrt {2}}}\left(|x\rangle |f(x)\rangle -|x\rangle |1\oplus f(x)\rangle \right)\\&={\begin{cases}{\frac {1}{\sqrt {2}}}\left(|x\rangle |1\rangle -|x\rangle |0\rangle \right)=-|x\rangle \otimes |-\rangle &{\text{if }}f(x)=1,\\{\frac {1}{\sqrt {2}}}\left(|x\rangle |0\rangle -|x\rangle |1\rangle \right)=|x\rangle \otimes |-\rangle &{\text{if }}f(x)=0\end{cases}}\\&=(U_{\omega }|x\rangle )\otimes |-\rangle \end{aligned}}}$

Не дивлячись на те, який саме оракул для ${\displaystyle f}$ нам задано, ми зможемо отримати потрібний ${\displaystyle U_{\omega }}$.

Робота алгоритму

Етапи роботи алгоритму Ґровера наведені нижче. Позначимо через ${\displaystyle |s\rangle }$ рівномірну суперпозицію по всім станам

${\displaystyle |s\rangle ={\frac {1}{\sqrt {N}}}\sum _{x=0}^{N-1}|x\rangle .}$

Тоді оператор

${\displaystyle U_{s}=2\left|s\right\rangle \left\langle s\right|-I}$

вважатимемо за оператор дифузії Ґровера.

Власне алгоритм:

1. Ініціалізуємо стан систем
   ${\displaystyle |s\rangle ={\frac {1}{\sqrt {N}}}\sum _{x=0}^{N-1}|x\rangle .}$
2. Виконуємо наступні «ітерації Ґровера» ${\displaystyle r(N)}$ раз. Функція ${\displaystyle r(N)}$ асимптотично є ${\displaystyle O({\sqrt {N}})}$, як описано нижче.
   1. Застосовуємо оператор ${\displaystyle U_{\omega }}$.
   2. Застосовуємо оператор ${\displaystyle U_{s}}$.
3. Вимірюємо отриманий квантовий стан.

Для правильного вибраної кількості ітерацій ${\displaystyle r}$ результат буде ${\displaystyle |\omega \rangle }$ з імовірністю, що наближається до 1 при N ≫ 1. Аналіз показує, що ${\displaystyle r(N)\leq {\Big \lceil }{\frac {\pi }{4}}{\sqrt {N}}{\Big \rceil }}$.

Перша ітерація

Попереднє спостереження, паралельно з нашим визначенням

${\displaystyle U_{s}=2|s\rangle \langle s|-I,}$

є ${\displaystyle U_{\omega }}$, що може бути виражено альтернативним шляхом:

${\displaystyle U_{\omega }=I-2|\omega \rangle \langle \omega |.}$

Іншими словами, обидва перетворення мають перетворення типу Хаусхолдера. Для доказу цього достатньо, щоб перевірити, як ${\displaystyle U_{\omega }}$ діє на основні стани:

${\displaystyle {\begin{aligned}(I-2|\omega \rangle \langle \omega |)|\omega \rangle &=|\omega \rangle -2|\omega \rangle \langle \omega |\omega \rangle =-|\omega \rangle =U_{\omega }|\omega \rangle ,\\(I-2|\omega \rangle \langle \omega |)|x\rangle &=|x\rangle -2|\omega \rangle \langle \omega |x\rangle =|x\rangle =U_{\omega }|x\rangle &&\forall x\neq \omega .\end{aligned}}}$

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

${\displaystyle {\begin{aligned}\langle \omega |s\rangle &=\langle s|\omega \rangle ={\tfrac {1}{\sqrt {N}}},\\\langle s|s\rangle &=N{\tfrac {1}{\sqrt {N}}}\cdot {\tfrac {1}{\sqrt {N}}}=1,\\U_{\omega }|s\rangle &=(I-2|\omega \rangle \langle \omega |)|s\rangle =|s\rangle -2|\omega \rangle \langle \omega |s\rangle =|s\rangle -{\tfrac {2}{\sqrt {N}}}|\omega \rangle ,\\U_{s}\left(|s\rangle -{\tfrac {2}{\sqrt {N}}}|\omega \rangle \right)&=\left(2|s\rangle \langle s|-I\right)\left(|s\rangle -{\tfrac {2}{\sqrt {N}}}|\omega \rangle \right)=2|s\rangle \langle s|s\rangle -|s\rangle -{\tfrac {4}{\sqrt {N}}}|s\rangle \langle s|\omega \rangle +{\tfrac {2}{\sqrt {N}}}|\omega \rangle \\&=2|s\rangle -|s\rangle -{\tfrac {4}{\sqrt {N}}}\cdot {\tfrac {1}{\sqrt {N}}}|s\rangle +{\tfrac {2}{\sqrt {N}}}|\omega \rangle =|s\rangle -{\tfrac {4}{N}}|s\rangle +{\tfrac {2}{\sqrt {N}}}|\omega \rangle \\&={\tfrac {N-4}{N}}|s\rangle +{\tfrac {2}{\sqrt {N}}}|\omega \rangle .\end{aligned}}}$

Варто відзначити окремий випадок при N = 4 з одним визначеним станом. Це ${\displaystyle U_{s}U_{w}|s\rangle =|\omega \rangle }$ означає, що в одному застосуванні ітератора Ґровера зазначений стан повертається.

Після застосування операторів ${\displaystyle U_{\omega }}$ і ${\displaystyle U_{s}}$, квадрат амплітуди запитуваного елемента збільшиться з ${\displaystyle \left|\langle \omega |s\rangle \right|^{2}={\tfrac {1}{N}}}$ до ${\displaystyle \left|\langle \omega |U_{s}U_{\omega }|s\rangle \right|^{2}=\left|{\tfrac {1}{\sqrt {N}}}\cdot {\tfrac {N-4}{N}}+{\tfrac {2}{\sqrt {N}}}\right|^{2}={\tfrac {(3N-4)^{2}}{N^{3}}}=9\left(1-{\tfrac {4}{3N}}\right)^{2}\cdot {\tfrac {1}{N}}}$

Зауваження

Припустимо, рівняння (1) має корені. Класичний алгоритм вирішення такого завдання (лінійний пошук), очевидно, вимагає ${\displaystyle O({\tfrac {N}{l}})}$ звернень до ${\displaystyle f}$ для того, щоб вирішити задачу з імовірністю ½. Алгоритм Ґровера дозволяє вирішити задачу пошуку за час ${\displaystyle O({\sqrt {\tfrac {N}{l}}})}$, тобто близько квадратного кореня з класичного, що є величезним прискоренням. Доведено, що Алгоритм Ґровера є оптимальним в наступних випадках:

• константу ${\displaystyle {\tfrac {\pi }{4}}}$ не можна поліпшити.
• Більшого квантового прискорення, ніж квадратичне, не можна отримати.

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

Те, що f задана у вигляді чорного ящика, ніяк не впливає в загальному випадку на складність як квантових, так і класичних алгоритмів. Знання «пристрою» функції f (наприклад, знання задає її схеми з функціональних елементів) в загальному випадку ніяк не може допомогти у вирішенні рівняння (1). Пошук в базі даних співвідноситься зі зверненням функції, яка приймає певне значення, якщо аргумент x відповідає шуканої записи в базі даних.

Оптимізація

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

Якщо проблема пошуку в Ґровера мала розв'язок з log^c N застосувань U_ω, що означало б, що NP міститься в BQP, шляхом перетворення проблем в NP в пошукових завдань Ґровер-типу. Оптимальність алгоритму Ґровера передбачає (але не доводить), що NP не міститься в BQP.

Число ітерацій для ${\displaystyle k}$ «помічених» записів, ${\displaystyle {\frac {\pi }{4}}{\sqrt {\frac {N}{k}}}}$, також є оптимальним.

Застосовність і обмеження

В базах даних, які не представлені в явному вигляді оракул викликається для оцінки елемента по його індексу, при цьому читання елементів повної бази даних один за одним і перетворення його в доступне подання може зайняти набагато більше часу, ніж пошук Ґровера. Для врахування таких ефектів, алгоритм Ґровера можна розглядати як рішення рівняння або задовольняють обмеження. У таких використаннях, оракул є способом перевірити обмеження і не пов'язаний з алгоритмом пошуку. Це поділ, як правило, запобігає алгоритмічній оптимізації, в той час як звичайні алгоритми пошуку часто покладаються на такі оптимізації і уникнути повного перебору. Ці та інші міркування з приводу використання алгоритму Ґровера обговорюються в статті Віамонте, Маркова та Хеєса.

Алгоритми, що використовують схему Ґровера

• Алгоритм пошуку екстремуму цілочисельної функції (P. Hoyer і ін.). Шукається найбільше значення функції ${\displaystyle f:\ \{0,1\}^{n}\rightarrow \{0,1\}^{n}}$. Квантовий алгоритм знаходить максимум за ${\displaystyle O({\sqrt {N}})}$ звернень до ${\displaystyle f}$.
• Алгоритм пошуку співпадаючих рядків в базі даних (Амбайніс). Шукається пара різних аргументів ${\displaystyle x_{1}\neq x_{2}}$, на яких функція ${\displaystyle f:\ \{0,1\}^{n}\rightarrow \{0,1\}^{n}}$ приймає одне і те ж значення. Алгоритм вимагає ${\displaystyle O(N^{3/4})}$ звернень до ${\displaystyle f}$.

Варіації і узагальнення

Безперервні версії алгоритму Ґровера

• Нехай гамільтоніан квантової системи має вигляд ${\displaystyle H=H_{1}+H_{2}}$ , де ${\displaystyle \exp(iH_{1})}$  і  ${\displaystyle \exp(iH_{2})}$ являють собою оператори ${\displaystyle I_{\tilde {0}}}$ і ${\displaystyle I_{\tilde {0}}}$ відповідно. Тоді безперервна унітарна еволюція з гамільтоніаном ${\displaystyle H}$, починаючи з ${\displaystyle |{\tilde {0}}\rangle }$, приводить до ${\displaystyle |x_{tar}\rangle }$. Складність такого безперервного аналога алгоритму Ґровера точно та ж, що і для дискретного випадку.
• Адіабатичний варіант алгоритму Ґровера. Повільна еволюція основного стану типу ${\displaystyle |{\tilde {0}}\rangle }$ під дією гамільтоніана, залежить від f , згідно адіабатичній теоремі, за час порядку ${\displaystyle {\sqrt {N}}}$ веде до стану ${\displaystyle |x_{tar}\rangle }$.

Див. також

• Алгоритм Шора
• Алгоритм з оракулом
• Квантові обчислення

Посилання

1. (PDF). Архів оригіналу (PDF) за 3 лютого 2021. Процитовано 15 листопада 2020.{{}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title ()
2. Grover, Lov K. (1997). A framework for fast quantum mechanical algorithms. arXiv:quant-ph/9711043.
3. Chuang, Isaac L. (2010). Quantum computation and quantum information (вид. 10th anniversary ed). Cambridge: Cambridge University Press. ISBN . OCLC 665137861.
4. Bennett C.H.; Bernstein E.; Brassard G.; Vazirani U. (1997). . . 26 (5): 1510—1523. arXiv:quant-ph/9701001. doi:10.1137/s0097539796300933. Архів оригіналу за 6 березня 2016. Процитовано 15 листопада 2020.
5. Michel Boyer; Gilles Brassard; Peter Høyer; Alain Tapp (1998), Tight Bounds on Quantum Searching, Fortsch. Phys., 46: 493—506, arXiv:quant-ph/9605034, Bibcode:1998ForPh..46..493B, doi:10.1002/3527603093.ch10, ISBN 
6. Viamontes G.F.; Markov I.L.; Hayes J.P. (2005), (PDF), Computing in Science and Engineering, 7 (3): 62—70, arXiv:quant-ph/0405001, Bibcode:2005CSE.....7c..62V, doi:10.1109/mcse.2005.53, архів оригіналу (PDF) за 3 лютого 2021, процитовано 15 листопада 2020

Джерела

• Grover L.K.: A fast quantum mechanical algorithm for database search [ 1 жовтня 2017 у Wayback Machine.], Proceedings, 28th Annual ACM Symposium on the Theory of Computing, (May 1996) p. 212
• Grover L.K.: From Schrödinger's equation to quantum search algorithm [ 11 листопада 2020 у Wayback Machine.], American Journal of Physics, 69(7): 769—777, 2001. Pedagogical review of the algorithm and its history.
• Grover L.K.: QUANTUM COMPUTING: How the weird logic of the subatomic world could make it possible for machines to calculate millions of times faster than they do today [ 10 березня 2017 у Wayback Machine.] The Sciences, July/August 1999, pp. 24–30.
• Nielsen, M.A. and Chuang, I.L. Quantum computation and quantum information. Cambridge University Press, 2000. Chapter 6.
• , Lov Grover, Lucent Technologies
• Grover's Algorithm: Quantum Database Search [ 7 листопада 2021 у Wayback Machine.], C. Lavor, L.R.U. Manssur, R. Portugal
• Grover's algorithm on arxiv.org
• Davy Wybiral. . Архів оригіналу за 16 січня 2017. Процитовано 13 січня 2017.
• Craig Gidney (5 березня 2013). . Архів оригіналу за 17 листопада 2020. Процитовано 15 листопада 2020.
• François Schwarzentruber (18 травня 2013). . Архів оригіналу за 16 листопада 2020. Процитовано 15 листопада 2020.
• Alexander Prokopenya. . Wolfram Alpha. Архів оригіналу за 20 листопада 2020. Процитовано 15 листопада 2020.
• Hazewinkel, Michiel, ред. (2001), computation, theory of Quantum computation, theory of, Математична енциклопедія, , ISBN 
• Roberto Maestre (11 травня 2018). . Архів оригіналу за 17 жовтня 2021. Процитовано 15 листопада 2020.