UK 
EnglishТипова
Polski🔍 Алгоритм Гровера
Покрокова симуляція алгоритму Гровера для 4-кубітного регістра (N=16). Оракул + дифузія показані як гістограма амплітуд. O(√N)≈3 проти класичного O(N).
🔍 Алгоритм Гровера
Покроково пройдіть квантовий алгоритм пошуку Гровера на регістрі з 16 елементів. Спостерігайте, як підсилення амплітуди піднімає ймовірність цільового елемента за O(√N) ітерацій замість класичного O(N).
🔬 Що демонструє
Алгоритм Гровера використовує дві операції на ітерацію: оракул, що змінює знак амплітуди цілі, та оператор дифузії, що відображає амплітуди відносно їхнього середнього. Після ~√N ітерацій ймовірність цілі наближається до 1.
🎮 Як використовувати
Оберіть цільовий елемент у 16-елементному регістрі. Проходьте ітерації покроково та спостерігайте за гістограмою амплітуд. Стовпчик цілі зростає, поки інші зменшуються. Порівняйте квантові O(√N) = 3 ітерації з класичним O(N) = 16.
💡 Чи знали ви?
Алгоритм Гровера забезпечує доведено оптимальне квадратичне прискорення для неструктурованого пошуку — жоден квантовий алгоритм не може зробити краще. Для бази даних з 1 мільйона елементів він знаходить відповідь приблизно за 1000 запитів замість 500 000.
Про алгоритм Гровера
Ця симуляція проходить крізь квантовий алгоритм пошуку Гровера на регістрі з 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, а також атаки на симетричну криптографію (зменшуючи ефективну стійкість ключа вдвічі), тому рекомендації постквантової безпеки радять більші розміри ключів.