Алгоритм Гровера, розроблений Ловом Гровером у 1996 році, — це квантовий алгоритм, який знаходить потрібний елемент у невпорядкованій базі з N записів за час порядку кореня квадратного з N, тоді як класичний пошук у середньому потребує N кроків. Це квадратичне прискорення виникає завдяки процесу підсилення амплітуди, коли квантова суперпозиція дозволяє обчислювати всі варіанти одночасно.
Алгоритм починає з переведення кубітів у рівну суперпозицію всіх станів, а потім послідовно застосовує дві операції: оракул, що позначає цільовий стан інверсією його фази, та оператор дифузії, що віддзеркалює всі амплітуди навколо їхнього середнього значення. Кожна ітерація приблизно подвоює ймовірнісну амплітуду правильної відповіді.
Після приблизно пі поділити на чотири, помножити на корінь квадратний з N ітерацій цільовий стан має майже стовідсоткову ймовірність бути виміряним. Алгоритм Гровера доведено оптимальний для неструктурованого пошуку і застосовується в криптографії, оптимізації та пошуку в базах даних, що робить його одним із найперспективніших квантових алгоритмів для практичного застосування.
Алгоритм Гровера дає квадратичне прискорення: він знаходить потрібний елемент серед N записів за час порядку кореня квадратного з N замість N кроків. Для бази з мільйона записів це скорочує кількість операцій приблизно з мільйона до тисячі.
Оракул — це квантова підпрограма, яка розпізнає цільовий елемент і інвертує знак (фазу) його амплітуди, не вимірюючи стан. Ця зміна фази позначає розв'язок, лишаючи всі інші стани незмінними.
Алгоритм Гровера вдвічі скорочує ефективну довжину ключа симетричного шифрування. AES-128 матиме рівень захисту 64-бітного ключа проти квантового зловмисника, тому NIST рекомендує AES-256 для постквантової безпеки.
Оптимальна кількість ітерацій дорівнює приблизно пі поділити на чотири, помножити на корінь квадратний з N, де N — розмір бази даних. Занадто мала або занадто велика кількість ітерацій знижує ймовірність знайти правильну відповідь.
Щоб реалізувати повну перевагу в масштабі, алгоритму Гровера потрібен відмовостійкий квантовий комп'ютер. Сучасні шумні проміжного масштабу квантові пристрої (NISQ) можуть продемонструвати принцип на малих прикладах, але поки не перевершують класичне обладнання.
Алгоритм Гровера, опублікований Ловом Гровером у 1996 році, — це квантовий алгоритм, який знаходить позначений елемент у невпорядкованій базі з N записів за приблизно корінь квадратний з N звернень — квадратичне прискорення порівняно з класичним повним перебором за N кроків. Хоча це прискорення не експоненційне, як в алгоритмі факторизації Шора, прискорення Гровера доведено оптимальне для квантового пошуку (жоден квантовий алгоритм не може зробити краще), і воно застосовується широко: будь-яка задача, що зводиться до пошуку в неструктурованому просторі, виграє від квадратичного прискорення Гровера. Алгоритм використовує квантову суперпозицію та підсилення амплітуди — квантовий аналог явища резонансу через інтерференцію — щоб сконцентрувати ймовірнісну амплітуду на цільовому стані.
Алгоритм починає з розміщення всіх N базисних станів у рівній суперпозиції. Оператор-оракул інвертує фазу цільового стану (амплітуда цільового елемента множиться на мінус одиницю). Оператор дифузії потім віддзеркалює всі амплітуди навколо їхнього середнього значення — це поєднання (ітерація Гровера) збільшує амплітуду цільового стану приблизно на два поділити на корінь квадратний з N за кожну ітерацію. Після приблизно пі, помноженого на корінь квадратний з N і поділеного на чотири ітерацій, амплітуда цільового стану наближається до одиниці, і вимірювання з високою ймовірністю знаходить ціль. Ще одна зайва ітерація — і результат "перескакує" оптимум, тому алгоритм потрібно зупинити на правильному кроці.
Цей симулятор візуалізує алгоритм Гровера геометрично, використовуючи двовимірний підпростір, натягнутий на цільовий стан і рівномірну суперпозицію, показуючи, як вектор стану обертається до цілі приблизно за корінь квадратний з N, поділений на чотири, обертань. Ви можете встановити N (розмір бази даних), спостерігати, як амплітуда цільового стану зростає з кожною ітерацією, побачити "перескок" оптимуму та виміряти кінцевий стан, щоб переконатися, що ціль знайдено. Симулятор також демонструє квантове кодування амплітуди та модель оракула-чорної скриньки, фундаментальну для теорії квантової складності запитів.
Як алгоритм Гровера досягає прискорення порівняно з класичним пошуком?
Класичний пошук у невпорядкованій базі з N елементів вимагає в середньому N поділити на два звернень, перш ніж знайдеться ціль. Алгоритм Гровера досягає приблизно кореня квадратного з N звернень, використовуючи квантовий паралелізм: квантовий стан може перебувати в суперпозиції всіх N записів одночасно, а ітерація Гровера підсилює амплітуду цільового стану, придушуючи інші через інтерференцію. Кожне звернення до квантового оракула обчислює всі N записів одночасно в суперпозиції. Різниця у швидкості між коренем квадратним з N та самим N стає вирішальною для великих N: пошук серед 10 у дванадцятому степені записів вимагає половини цієї кількості класичних звернень, але лише близько 500 000 ітерацій Гровера.
Що таке оракул у квантових обчисленнях?
Оракул (або чорна скринька) — це квантовий вентиль, який реалізує функцію пошуку, не розкриваючи свою внутрішню будову. В алгоритмі Гровера оракул позначає цільовий стан, змінюючи його фазу на протилежну: якщо елемент є розв'язком, амплітуда стану множиться на мінус одиницю, інакше залишається незмінною. Оракул діє на всі N станів у суперпозиції одночасно за один крок. У теорії складності кількість звернень до оракула називають складністю запитів; для алгоритму Гровера складність запитів порядку кореня квадратного з N доведено оптимальною. На практиці оракули компонують із квантових вентилів, що реалізують конкретну умову пошуку.
Що таке підсилення амплітуди?
Підсилення амплітуди — це узагальнення алгоритму Гровера на довільні квантові алгоритми. Воно бере будь-який квантовий алгоритм із імовірністю успіху p і підсилює її майже до одиниці за допомогою приблизно одного поділити на корінь квадратний з p повторень операції з двох віддзеркалень (віддзеркалення оракулом плюс дифузія навколо початкового стану). Алгоритм Гровера — це окремий випадок, коли початковий алгоритм є рівномірною суперпозицією (імовірність успіху дорівнює одиниці поділеній на N). Підсилення амплітуди дає квадратичне прискорення для будь-якого алгоритму Монте-Карло і застосовується в квантових алгоритмах Монте-Карло для числового інтегрування та в алгоритмах квантового блукання.
Експоненційне квантове прискорення (як в алгоритмі факторизації Шора) виникає завдяки використанню конкретної математичної структури задачі — періодичної структури модульного піднесення до степеня, яку квантове перетворення Фур'є може ефективно виявити. У неструктурованому пошуку немає жодної математичної структури, яку можна використати: цільовий елемент може бути будь-яким, і немає жодної закономірності, що відрізняла б його від інших. З інформаційно-теоретичної точки зору, щоб знайти один елемент серед N, потрібно отримати щонайменше логарифм за основою два від N бітів інформації; кожне звернення до оракула дає щонайбільше один біт; тож квантові оракули дають квадратичний виграш завдяки інтерференції, але не можуть подолати фундаментальну інформаційно-теоретичну межу, кращу за порядок кореня квадратного з N.
Алгоритм Гровера застосовний скрізь, де вузьким місцем є неструктурований пошук. Криптографічні наслідки: квантовий комп'ютер, що виконує алгоритм Гровера, може підібрати n-бітний симетричний ключ методом повного перебору за експоненту від n поділеного на два операцій — це вдвічі скорочує ефективну довжину ключа. Це означає, що AES-128 забезпечує лише 64-бітний рівень безпеки проти квантових зловмисників; NIST рекомендує AES-256 для постквантової безпеки. В оптимізації алгоритм Гровера можна використовувати як підпрограму для пошуку в просторі розв'язків NP-задач, даючи квадратичне прискорення для алгоритмів з експоненційним часом виконання. Пошук у базах даних, комбінаторний пошук у штучному інтелекті та оцінка амплітуди в квантовому інтегруванні Монте-Карло — усе це виграє від прискорень на основі алгоритму Гровера.