Math
Пошук Ґровера
Досліджувати підсилення амплітуди у неструктурованому пошуку. Фазовий оракул змінює знак позначеної амплітуди без зміни ймовірностей у обчислювальній базі. Крок дифузії перетворює відносну фазу на більшу ймовірність успіху. Занадто багато ітерацій знову зменшують цю ймовірність.
Що відбувається
Фазовий оракул позначає кандидата, змінюючи його відносну фазу. Вимірювання негайно у обчислювальній базі дає такі ж ймовірності, як і перед оракулом; Це не робить відносну фазу неспостережуваною у кожній базі вимірювання. Інтерференція на кроці дифузії перетворює фазову позначку на амплітудне підсилення.
Одна ітерація Grover складається з оракула і дифузії. Ймовірність успіху коливається, а не збігається: зупинитися біля першого максимуму, а потім порівняти з пізнішими ітераціями. Кількість запитів масштабується за квадратним коренем розміру простору пошуку для одного позначеного елемента; побудова оракула і підготовка даних також мають свої витрати. Модуль показує ідеальне симуляційне векторне моделювання стану, точні раціональні амплітуди для вибраних розмірів, а також відтворювану кількість вимірювань вибірки.
Рівняння модуля
Рівняння 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 - кожне в межах трьох сигм від точної ймовірності
