Вступ

Алгоритм Гровера — це квантовий алгоритм для так званих задач неструктурованого пошуку, що забезпечує квадратичне покращення порівняно з класичними алгоритмами. Це означає, що алгоритм Гровера вимагає порядку квадратного кореня з кількості операцій, необхідних для розв'язання задачі неструктурованого пошуку класично, — що рівносильно тому, що класичні алгоритми для неструктурованого пошуку повинні мати вартість принаймні порядку квадрата від вартості алгоритму Гровера.

Алгоритм Гровера разом з його розширеннями та базовою методологією виявляється широко застосовним, забезпечуючи квадратичну перевагу для багатьох цікавих обчислювальних задач, які на перший погляд можуть не здаватися задачами неструктурованого пошуку.

Хоча широка застосовність техніки пошуку Гровера переконлива, варто визнати ще на початку уроку, що квадратична перевага, яку вона надає, навряд чи найближчим часом дасть практичну перевагу квантових обчислень над класичними. Класичне обчислювальне залізо значно досконаліше за квантове — і квадратична квантова перевага, забезпечувана алгоритмом Гровера, безумовно, буде нівельована вражаючими тактовими частотами сучасних класичних комп'ютерів для будь-якої задачі неструктурованого пошуку, яку можна було б запустити найближчим часом.

Проте в міру розвитку квантових технологій алгоритм Гровера може набути потенціалу. Дійсно, деякі з найважливіших і найвпливовіших класичних алгоритмів — зокрема швидке перетворення Фур'є та швидке сортування (наприклад, quicksort і merge sort) — забезпечують дещо менш ніж квадратичну перевагу над наївними підходами до розв'язання відповідних задач. Ключова відмінність тут, звичайно, полягає в тому, що для запуску алгоритму Гровера потрібна зовсім нова технологія (тобто квантові обчислення). Хоча ця технологія все ще знаходиться на дуже ранньому етапі розвитку порівняно з класичними обчисленнями, не варто недооцінювати потенціал технологічного прогресу, який міг би дозволити квадратичній перевазі квантових обчислень над класичними одного дня принести реальну практичну користь.

Відео уроку

У наступному відео Джон Уотрус крок за кроком пояснює зміст цього уроку про алгоритм Гровера. Також можна відкрити відео на YouTube в окремому вікні. Завантажити слайди до цього уроку.