Алгоритм Гровера для четырёх элементов

Пространство поиска содержит четыре элемента 0,…, 3. Оракул помечает третий: $f(2)=1$, для остальных$f(x)=0$. Для каждого шага алгоритма Гровера нарисуйте столбики амплитуд и укажите нормированные значения. Каково оптимальное число итераций k? Какова вероятность успеха после каждой итерации? Сколько вызовов f в среднем нужно классически?

Шаги: начните с равномерной суперпозиции; оракул меняет знак помеченной амплитуды, затем выполняется отражение всех амплитуд относительно их среднего. В классическом сравнении индекс неизвестен, кандидаты не повторяются, а последний оставшийся определяется без нового вызова.