Алгоритм пошуку Гровера: Посилення амплітуди пояснено |… |…

Квантові біти та їх суперпозиція

Квантовий комп’ютер працює з кубітами – двома-рівневими системами, які, на відміну від класичних бітів, можуть існувати в будь-якій суперпозиції |ψ⟩ = α|0⟩ + β|1⟩, де |α|² + |β|² = 1. n-кубітний регістр живе у гілковій просторі з 2ⁿ комплексних амплітуд: 3 кубіти вже охоплюють 8 одночасних амплітуд. Гейт Хадамарда створює рівну суперпозицію, а набір {Hadamard, T, CNOT} є універсальним – будь-який квантовий обчислення може бути побудований з використанням лише цих трьох гейтів.

Алгоритм: оракул плюс дифузія

Ловер Гроувер (1996) розробив алгоритм для пошуку позначеного елемента в несортованій базі даних з N елементів, який класично потребує O(N) запитів у середньому. Алгоритм Гроувера потребує лише O(√N):

1. Initialise: |ψ⟩ = H^⊗n |0⟩ⁿ   (equal superposition of all N states)

2. Repeat ≈(π/4)·√N times:
   a. Oracle:     O|x⟩ = −|x⟩ if x matches, +|x⟩ otherwise
   b. Diffusion:  2|ψ⟩⟨ψ| − I   ("inversion about the mean")

3. Measure → obtains the marked item with probability ≥ 1 − ε

N = 2²⁰ ≈ 10⁶:  classical avg 500,000 queries  vs  Grover ~785 queries

жива демонстрація · пов'язана симуляція● LIVE

Геометрична картина

Кожне ітерація Гровера обертає вектор стану на фіквований кут 2θ у бік цільового стану, де sinθ = 1/√N. Оптимальна кількість ітерацій становить t = (π/4)·√N – перемахнути через цю точку та амплітуда повернеться від цільового стану, на відміну від класичного пошуку, більше ітерацій не завжди краще. При N = 2⁵⁶ ≈ 7×10¹⁶, класичний brute force потребує приблизно 10¹⁷ запитів у середньому; Grover потребує приблизно 2×10⁸ – різниця становить дев’ять порядків величини.

Чому це має значення для криптографії

Алгоритм Грувера має пряме наслідкування для симметричного шифрування з ключем. Ключ AES-128 (128 біт) потребує класичного пошуку всіх можливостей у 2¹²⁸; Grover зменшує це до приблизно 2⁶⁴ квантових запитів — фактично вдвіймаючи межу безпеки. NIST реагує просто: використовувати AES-256 замість AES-128 для підтримки справжнього рівня безпеки 128 біт проти квантових супротивників. Важливо, що прискорення Грувера є квадратичним, а не експоненціальним, як алгоритм Шора для розрахунку чисел — він не може вирішувати NP-пов’язані проблеми за поліноміальний час, оскільки основний простір пошуку все ще експоненційний навіть після зменшення квадратним коренем.

Frequently asked questions

Як алгоритм Гровера шукає швидше за класичний комп'ютер?

Він починається в рівночасному суперпозиції всіх N можливих станів, потім повторює приблизно (π/4)·√N разів два операції: оракул, який фазово перевертає амплітуду позначеного елемента, та крок дифузії, що виконує "інверсію відносно середнього значення", підсилюючи позначену амплітуду, а зменшуючи інші. Після оптимальної кількості ітерацій вимірювання реєстру повертається позначений елемент з майже певною ймовірністю — використовуючи лише O(√N) запитів до оракула замість класичних O(N).

Чи зламає алгоритм Гровера шифрування AES?

Він послаблює, але не ламає симетричного шифрування повністю. Класичний грубий пошук проти AES-128 потребує 2^128 запитів; Grover зменшує це приблизно до 2^64 запитів, що приблизно вдвічі скорочує ефективну довжину ключа. Рекомендація NIST полягає у використанні AES-256 замість AES-128, оскільки 2^128 квантових запитів до 256-бітного ключа залишається обчислювально неможливим.

Чому алгоритм Гровера не може ефективно розв'язувати NP-пов’язані проблеми?

Прискорення Гровером є квадратичним, а не експоненційним: воно перетворює O(N) неструктурований пошук на O(√N). Для NP-пов’язаних проблем простір пошуку зазвичай є експоненціальним у розмірі вхідних даних, тому навіть квадратичне зменшення експоненційного числа залишає експоненційне число запитів — ніде близько до поліноміального часу, необхідного для ефективного розв’язання NP-пов’язаних проблем.

Спробуйте наживо

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

▶ Відкрити симуляцію the simulation