Алгоритм Дойча

Как это ни странно, расширение задачи нисколько не сказалось на сложности алгоритма. В случае задачи Йожи алгоритм остаётся абсолютно тем же самым. Вот словесное описание последовательности его шагов:

1. Инициализировать начальное состояние из n кубитов, которое должно быть |0n>.

2. Применить к начальному состоянию гейт Адамара для n кубитов H^⊗n, в результате чего получается равновероятностная суперпозиция всех возможных значений n кубитов.

3. Применить оракул Of, который строится несколько иначе, чем было рассмотрено при описании алгоритма Дойча.

4. Снова применить гейт Адамара H^⊗n.

5. Произвести измерение. Если в результате измерения будет получено значение |0n>, то функция константна. В противном случае она сбалансирована (при этом значение в результате измерения может быть использовано для получения общего понимания того, на каких значениях функция возвращает значение 1).

Вот диаграмма квантовой схемы описанного алгоритма:

Оракул O_f меняет фазу на -1 у тех квантовых состояний, для которых функция f возвращает значение 1. Здесь нет особого смысла использовать служебный кубит, поскольку матрица, у которой на главной диагонали стоят только 1 и -1, а в остальных позициях стоят 0, унитарна.
Далее с математической точки зрения происходит следующее. Начальное квантовое состояние переходит в равновероятностную суперпозицию. Затем у каждого квантового состояния в этой суперпозиции меняется знак фазы, если функция принимает на этом квантовом состоянии значение 1. Потом, после второго применения гейта Адамара, все квантовые состояния «схлопываются». И если функция является константной, то происходит деструктивная интерференция фаз всех квантовых состояний, кроме |0n>, у которого наоборот происходит конструктивная интерференция, и его амплитуда становится равной 1.
Проще всего понять эти выкладки на примерах, поэтому реализуем этот алгоритм при помощи тех же самых функций и прочих программных сущностей, которые мы уже использовали при реализации алгоритма Дойча. Алгоритм Дойча-Йожи, в свою очередь, очень интересен для проведения различных экспериментов и замеров частотных вероятностей, поэтому далее приводится некоторое расширение разработанных функций и описывается один эксперимент, который будет небезынтересным заинтересованному читателю.