Покроковий алгоритм квантового пошуку Гровера на 16-елементному регістрі. Спостерігайте підсилення амплітуди цільового елемента за O(√N) ітерацій проти класичних O(N).
Алгоритм використовує дві операції: оракул, що інвертує знак цільової амплітуди, та оператор дифузії, що відображає амплітуди відносно середнього. Після ~√N ітерацій ймовірність цілі наближається до 1.
Оберіть цільовий елемент у 16-елементному регістрі. Проходьте ітерації та спостерігайте гістограму амплітуд. Порівняйте квантовий O(√N) = 3 ітерації з класичним O(N) = 16.
Алгоритм Гровера забезпечує доведено оптимальне квадратичне прискорення для невпорядкованого пошуку. Для бази даних із 1 мільйона елементів він знаходить відповідь за ~1000 запитів замість 500000.
Ця симуляція покроково демонструє алгоритм квантового пошуку Гровера на регістрі з N = 16 базисних станів. Система починає з рівномірної суперпозиції, де кожна амплітуда дорівнює 1/√16. На кожній ітерації застосовується оракул, що інвертує знак амплітуди позначеної цілі, а потім оператор дифузії, який відображає всі амплітуди відносно їхнього середнього (D = 2|s⟩⟨s| − I). Разом ці дії виконують поворот, що поступово концентрує ймовірність на цільовому елементі.
Ви обираєте цільовий елемент зі спадного списку з 16 позицій, потім використовуєте «Крок» для виконання однієї ітерації, «Авто» для автоматичного запуску та «Скинути» для повернення до рівномірного стану. Гістограма амплітуд показує, як стовпець цілі зростає, а решта зменшуються, досягаючи піку приблизно через π/4·√N ≈ 3 ітерації. Це квадратичне прискорення O(√N) лежить в основі пришвидшеного перебору, криптоаналізу та пошуку в базах даних на квантових комп'ютерах.
Що демонструє ця симуляція?
Вона візуалізує алгоритм Гровера, що шукає єдиний позначений елемент у невпорядкованому регістрі з N = 16 позицій. Амплітуда кожного елемента відображається у вигляді стовпця, і ви спостерігаєте, як стовпець цілі зростає до майже стовідсоткової ймовірності з кожною ітерацією Гровера.
Як працює алгоритм Гровера?
Кожна ітерація складається з двох кроків. Оракул інвертує знак амплітуди цілі, позначаючи її; оператор дифузії відображає всі амплітуди відносно їхнього середнього. Це «відображення відносно середнього» піднімає ціль і знижує решту, повертаючи вектор стану до розв'язку.
Що роблять елементи керування?
Спадний список вибирає, який із 16 елементів (від |0000⟩ до |1111⟩) є позначеним розв'язком. «Крок» виконує одну ітерацію (оракул + дифузія), «Авто» запускає ітерації кожні 0,9 секунди, а «Скинути» відновлює рівномірну суперпозицію 1/√16 з нулем ітерацій.
Оптимальна кількість приблизно дорівнює π/4·√N. Для N = 16 це округлюється до 3 ітерацій, після яких ймовірність цілі близька до максимуму. Інформаційна панель показує це як «π/4·√16 ≈ 3».
Класично пошук у невпорядкованому списку з N елементів потребує в середньому N/2 порівнянь (8 для N = 16). Гровер знаходить ціль лише за O(√N) ітерацій — квадратичне прискорення. Для мільйона елементів це ~1000 запитів замість 500 000.
Ітерації Гровера — це обертання, тому вони можуть «перелетіти». Після оптимальної точки ймовірність цілі знову падає, бо стан обертається минаючи розв'язок. Симуляція позначає це «перебільшенням», показуючи, що більше ітерацій не завжди краще.
Це унітарний оператор D = 2|s⟩⟨s| − I, де |s⟩ — рівномірна суперпозиція. На практиці він відображає кожну амплітуду відносно середнього всіх амплітуд, підсилюючи будь-яке значення, яке оракул опустив нижче середнього, тобто позначену ціль.
Арифметика амплітуд є точною для ідеалізованого квантового комп'ютера без шуму з дійсними амплітудами, що й вимагає алгоритм Гровера. Модель не враховує реальних ефектів — декогеренції, помилок воріт і колапсу при вимірюванні, тому це вірна математична модель, а не апаратна емуляція.
Алгоритм починається з рівномірної суперпозиції, зазвичай створеної воротами Адамара, тому кожен елемент має амплітуду 1/√N = 1/4 і ймовірність 1/16 (6,25%). Ця рівна стартова точка відображає відсутність апріорних знань про розташування цілі.
Ні. Для невпорядкованого пошуку масштабування O(√N) є доведено оптимальним; жоден квантовий алгоритм не може знайти позначений елемент за меншу кількість запитів до оракула. Ця оптимальність, доведена Беннетом, Бернштейном, Брасаром і Вазірані, робить Гровера еталоном для квантового пошуку.
Амплітудна ампліфікація у стилі Гровера пришвидшує завдання перебору: пошук у невпорядкованих базах даних, інвертування функцій, розв'язання задач обмежень і SAT, а також атаки на симетричну криптографію (вдвічі зменшуючи ефективну довжину ключа), тому пост-квантові рекомендації передбачають збільшення розмірів ключів.