Math
Поиск Гровера
Исследуйте усиление амплитуды при неструктурированном поиске. Фазовый оракул меняет знак амплитуды отмеченного состояния, не меняя вероятностей в вычислительном базисе. Шаг диффузии превращает относительную фазу в увеличение вероятности успеха. Слишком много итераций снова уменьшают эту вероятность.
Что происходит
Фазовый оракул отмечает кандидата изменением относительной фазы. Измерение сразу после оракула в вычислительном базисе даёт прежние вероятности; это не означает, что относительная фаза ненаблюдаема в любом базисе измерения. Интерференция на шаге диффузии превращает фазовую метку в усиление амплитуды.
Одна итерация Гровера состоит из оракула и диффузии. Вероятность успеха колеблется, а не сходится: остановитесь около первого максимума и сравните результат с более поздними итерациями. Для одного отмеченного элемента число запросов растёт как квадратный корень из размера пространства поиска; построение оракула и подготовка данных также требуют ресурсов. Модуль показывает идеальную симуляцию вектора состояния, точные рациональные амплитуды для выбранных размеров и воспроизводимую выборку результатов измерений.
Уравнения модуля
Уравнения sin θ = 1/√N; после k поворотов амплитуда отмеченного элемента равна sin((2k+1)θ), а шанс - её квадрат один поворот = один вызов оракула (знак минус у отмеченной амплитуды) + одно отражение относительно среднего: a -> 2·mean − a оптимальное число поворотов k* = floor(π/4·√N) = 3, 6, 12, 25 при N = 16, 64, 256, 1024; слепой поиск в среднем делает (N + 1)/2 = 8.5, 32.5, 128.5, 512.5 при N = 4^m амплитуда есть точная ДРОБЬ, по целочисленной рекурсии u(k+1) = (2q² − 4)·u(k) − q⁴·u(k−1) при q = 2^(n/2), sin((2k+1)θ) = u(k)/q^(2k+1) шестнадцать элементов: 1/4, 11/16, 61/64, 251/256 (k* = 3), 781/1024, 1451/4096, −2339/16384 (k = 6, шанс 0.0204 - хуже, чем 0.0625 в начале), … , 2269261/67108864 (k = 12) шестьдесят четыре элемента после шести поворотов: 133988401/134217728 = 0.99829138070344925, что регистр воспроизводит до последнего бита измерено против подсчитанного: 2000 запусков при k* дают 1913, 1994, 2000, 2000 попаданий для N = 16, 64, 256, 1024 - каждое в пределах трёх сигм от точного шанса
