Алгоритм Гровера: Пошук у Квадратному Коренні з Часу

Сен і N сірців

Пошук одного елемента в несортованому списку з N елементів, який відповідає певній умові, класично є проблемою O(N): без структури для використання потрібно перевіряти елементи по одному та в середньому потрібно близько N/2 спроб. Лов Гровер показав у 1996 році, що квантовий комп'ютер може виконати цю ж задачу приблизно з √N викликами до чорного ящика-оракула – це квадратове прискорення. Це не експоненційний стрибок, який надає алгоритму Shor проти факторингу, але це доведено найкращим, що будь-який квантовий алгоритм може отримати для неструктурованого пошуку, і воно достатньо загальне, щоб прискорити будь-яку проблему, яка може бути сформульована як «перевірте цього кандидата проти тесту так/ні».

Перехресне затрунення спочатку: ставити всі запитання одночасно

Алгоритм починається з того, що n кубітів (N = 2^n) поміщаються в рівноправний суперпозиційний стан усіх можливих індексів, використовуючи шар гейтів Гадамарда на стані нуль-нуль. Кожен із цих N базових станів тепер несе однакову амплітуду, 1/√N, тому ймовірність вимірювання будь-якого конкретного стану становить 1/N - точно як шанси одного класичного вгадування. Хитресть полягає не у вгадуванні ще, а у переупорядкуванні цього рівномірного ландшафту амплітуд так, щоб амплітуда позначеного стану зростала за рахунок решти, перш ніж взагалі вимірювати.

Оракул: знак, який ніхто не бачить

Оракул U_f є унітарним оператором, який розпізнає позначену величину, не розкриваючи її: він не змінює жодного не-позначеного базису та множить амплітуду позначеної величини на -1. Виміряний негайно, цей фазовий зсув був би непомітним – ймовірність будь-якого результату є квадратом амплітуди, а піднесення до квадрату видаляє знак. Весь алгоритм — це спосіб перетворити цю невидиму фазову різницю на видиму відмінність у ймовірностях перед вимірюванням кубітів.

Дифузія: інверсія навколо середнього значення

Другий оператор, дифузійний оператор, відбиває кожну амплітуду приблизно навколо свого середнього значення. Оскільки оракул лише зробив одну амплітуду негативною, залишаючи решту позитивними та рівними, середнє значення трохи знижується нижче за звичайне. Відбиття навколо цього зниженого середнього значення відсуває позначену амплітуду приблизно на 2/√N вгору, а кожну іншу амплітуду трохи знижує. Один виклик оракула плюс один дифузійний оператор називається ітерацією Грувера, і геометрично це фіксоване під кутом обертання вектора стану у площині, що пронизується позначеним та немаркованим підпросторами.

|s⟩ = H^⊗n |0⟩                    every state gets amplitude 1/√N

repeat k ≈ (π/4)·√(N/M) times:
  |s⟩ ← Uf |s⟩                    oracle: flip the sign of marked states
  |s⟩ ← (2|s⟩⟨s| − I) |s⟩         diffusion: reflect about the mean amplitude

measure |s⟩                        marked state now dominates
P(marked after k steps) = sin²( (2k+1)·θ ),   θ = arcsin(√(M/N))

Чому квадратний корінь, а не більше

Кожна ітерація обертає стан на однаковий невеликий кут θ ≈ 2/√N (для одного позначеного елемента серед N), тому кількість ітерацій, необхідних для обертання приблизно на чверть обороту – точку, де максимальна амплітуда позначеності – становить близько (π/4)·√N. Продовжуйте виконувати більше ітерацій, і стан продовжує обертатися за цією точкою, тому ймовірність успіху падає знову і потім зростає, коливаючись з періодом приблизно π√N кроків: це відома проблема перекосу, і тому реальні впровадження потребують принаймні грубої оцінки N (або кількості позначених елементів M) заздалегідь. Беннетт, Бернстайн, Брасс та Вазірани довели у 1997 році, що жоден квантовий алгоритм, який розглядає оракул як чорний ящик, не може перевершити Ω(√N) запитів, тому Алгоритм Гровера не просто швидкий, він оптимальний.

Розбиття ключів і чому AES-256 все ще є надійним, "

Найбільш цитоване застосування стосується простору ключів симетричного шифру як невідсортованого списку: за заданих парою plaintext/ciphertext, "чи правильний цей ключ" - це оракул, і Grover знаходить ключ приблизно за 2^(n/2) спроб замість 2^n. Це вдвічі зменшує ефективну безпеку ключа n-бітного розміру, а не руйнує його повністю, тому стандартною оборонною мірою проти майбутніх великих квантових комп'ютерів є просто подвоєння довжини ключа - AES-256 при поведінці Grover схожий на AES-128 сьогодні, і AES-128 вважається безпечним від класичних атак. Це значно м’якша загроза, ніж алгоритм Shor становить для RSA та еліптичної криптографії, який руйнує їх повністю та ефективно, а не лише послаблює їх".

Frequently asked questions

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

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