ЯдроКодаподготовка к экзаменам
Подготавливаем текст, источники и редакционные примечания без изменения разметки страницы.
Объясняем алгоритм Гровера: O(√N) запросов, фазовый оракул, амплитудное усиление, пример Qiskit и ограничения реального ускорения.
Алгоритм Гровера даёт квадратичное уменьшение числа запросов для неструктурированного поиска: вместо порядка N проверок требуется порядок √N обращений к оракулу. Это сильный теоретический результат, но фраза «квантовый компьютер ищет в базе в квадратный корень раз быстрее» скрывает главные условия. Данные должны быть представлены квантовой схеме, условие — реализовано обратимым оракулом, а стоимость подготовки, коррекции ошибок и измерений тоже входит в практическую систему.
Есть пространство из N вариантов и булева функция f(x). Нужно найти x, для которого f(x)=1, не используя дополнительную структуру вроде сортировки, индекса или геометрии. Классический алгоритм в худшем случае проверяет порядок N вариантов. Гровер строит суперпозицию вариантов и усиливает амплитуду отмеченных состояний, выполняя порядок √(N/M) итераций, если решений M.
Оракул не сообщает готовый индекс. Он меняет фазу отмеченного состояния. Затем diffusion operator отражает амплитуды относительно среднего значения. Повторение пары «оракул + диффузия» переносит вероятность в отмеченные состояния, после чего выполняется измерение.
Если объединить все решения в одно направление, а все остальные состояния — во второе, состояние алгоритма вращается в двумерной плоскости. Начальный угол определяется долей M/N. Каждая итерация поворачивает вектор примерно на удвоенный угол к направлению решений.
Слишком мало итераций не успевает накопить вероятность, слишком много — проходит оптимум и снова уменьшает её. Поэтому число повторов выбирается по N и M. Когда M неизвестно, нужны варианты алгоритма с другим расписанием итераций; нельзя бездумно подставить формулу для единственного решения.
Официальный tutorial IBM строит оракул, использует функцию grover_operator и запускает схему через sampler. Ниже показана малая симуляция для двух кубитов и отмеченного состояния 11. API следует проверять по актуальной документации перед запуском.
from qiskit import QuantumCircuit
from qiskit.circuit.library import grover_operator
from qiskit.primitives import StatevectorSampler
# CZ меняет фазу |11>, поэтому служит оракулом для этого примера.
oracle = QuantumCircuit(2)
oracle.cz(0, 1)
circuit = QuantumCircuit(2)
circuit.h([0, 1])
circuit.compose(grover_operator(oracle), inplace=True)
circuit.measure_all()
sampler = StatevectorSampler(seed=7)
result = sampler.run([circuit], shots=2_000).result()
print(result[0].data.meas.get_counts())На идеальном симуляторе после одной итерации состояние 11 должно доминировать. Это учебная демонстрация амплитудного усиления, а не доказательство выигрыша над классической системой: пространство из четырёх вариантов, оракул заранее известен, шум и стоимость загрузки данных отсутствуют.
Сложность Гровера считается в модели query complexity. Один запрос к f предполагается квантовой операцией, способной обработать суперпозицию. Если условие — сложная программа, её нужно превратить в обратимую схему с ancilla-кубитами, развернуть временные результаты и учесть глубину вентилей.
Обычная база данных хранится в классической памяти и использует индексы. Загрузить N произвольных записей в квантовое состояние бесплатно нельзя. Для задачи с B-tree, хеш-таблицей или сортированным массивом классический структурный алгоритм уже использует знания, которых нет в модели неструктурированного поиска. Сравнивать √N с O(log N), не посчитав подготовку и оракул, некорректно.
На шумных устройствах многоуправляемые операции раскладываются в глубокие цепочки двухкубитных вентилей. Официальная документация IBM прямо относит масштабируемый вариант Гровера к fault-tolerant алгоритмам и демонстрирует на текущем оборудовании только малый пример. Теоретический выигрыш сохраняет значение, но практическая точка окупаемости требует зрелой коррекции ошибок и полной оценки ресурсов.
Публикация Lov Grover 1996 года представила квантовый алгоритм для поиска выделенного элемента в неупорядоченном пространстве с O(√N) запросами и высокой вероятностью успеха. Последующие результаты показали оптимальность такого порядка в модели чёрного ящика и обобщили идею до amplitude amplification.
Сильный результат относится к числу запросов, а не обещает одинаковое ускорение wall-clock time. Квантовый запрос может быть намного дороже классической проверки, а запуск приходится повторять для статистической уверенности и обработки ошибок.
Сначала сформулируйте f(x) и посчитайте стоимость её обратимой схемы. Затем опишите, откуда берётся суперпозиция входов, сколько решений ожидается и сколько логических кубитов нужно. Сравните не с линейным перебором по умолчанию, а с лучшим классическим алгоритмом, использующим ту же структуру задачи. После этого добавьте коррекцию ошибок, число повторов и ввод-вывод.
Алгоритм Гровера важен как ясный пример квантового преимущества в query model и как универсальная техника amplitude amplification. Его правильное понимание начинается с условий теоремы, а не с метафоры о мгновенном просмотре всех строк базы.
Самостоятельный редакционный разбор ЯдроКода по работе Lov Grover и актуальной официальной документации IBM Quantum/Qiskit. Чужие иллюстрации и текст не воспроизводятся.
Квантовая схема описана собственным учебным кодом редакции; рисунки и листинги первоисточников не переносятся.