Продолжаем изучать квантовые вычисления: алгоритм Дойча-Йожи
Ранее мы уже рассмотрели алгоритм Дойча, и тогда мы решали простейшие задачи по квантовым вычислениям. Продолжая развивать разработанный фреймворк, сегодня я предлагаю рассмотреть расширение первоначального алгоритма, которое получило название алгоритма Дойча-Йожи. (Фамилия второго автора алгоритма в русском языке имеет множество вариантов, использованных в литературе: Джоза, Джозса, Йожа; причём иногда фамилия склоняется, а иногда нет. Я предлагаю затвердить вариант Йожа со склонением, поскольку это правильная транслитерация венгерской фамилии Jozsa).Эта статья является продолжением в цикле статей по модели квантовых вычислений, поэтому если начать читать её без ознакомления с предыдущими статьями цикла, что-то может показаться непонятным. Так что читателя, который впервые набрёл на эти мои заметки, я отправляю к первым статьям: 1, 2, 3.
Далее в статье вы узнаете, как на основе данного определения бинарной функции построить оракул, причём не вручную, как это бывало раньше, а автоматически. Ещё вы узнаете о том, как при помощи всего лишь одного вызова оракула понять тип функции. Ну и ещё мы проведём один занимательный эксперимент, результаты которого для меня, например, были в меру удивительными. Так что всех заинтересовавшихся я попрошу под кат.
Дэвид Дойч разработал самый первый алгоритм в рамках модели квантовых вычислений в далёком 1985 году. Честно говоря, это был небольшой прорыв, поскольку этот алгоритм впервые показал превосходство модели квантовых вычислений над классической моделью. Далее он стал примером для исследователей, и в результате появились следующие прорывные алгоритмы (в первую очередь алгоритм факторизации Шора и его же алгоритм вычисления дискретного логарифма, которые не дают покоя криптографам и криптоаналитикам).Сама по себе задача Дойча не очень показательна. Но он заметил, что при помощи модели квантовых вычислений можно одновременно вычислить значения некоторой двоичной функции на всём множестве входных значений. Поскольку входные кубиты можно перевести в равновероятностную суперпозицию всех базисных состояний, а потом применить заданную функцию, то как раз в этой случае проявится принцип квантового параллелизма. Однако что дальше? Достать все полученные значения функции невозможно, поскольку в результате измерения с той или иной вероятностью получается одно значение из всего множества. Но здесь есть один тонкий момент, который и был запримечен Д. Дойчем. Поскольку до измерения в результирующем состоянии квантового регистра скрыто всё множество значений функции, при должных манипуляциях с этим квантовым регистром можно получить информацию о некоторых общих свойствах функции. То есть, ещё раз, мы получаем не какие-то конкретные значения функции, но информацию о её общих свойствах.
И вот на свет появляется задача Дойча, в которой надо понять, является ли двоичная функция на одном двоичном же аргументе константной или сбалансированной (снова отправляю к статье про этот алгоритм). Свойство того, что функция является константной или сбалансированной — это как раз пример такого общего свойства функции. Так что принцип квантового параллелизма вполне можно применить для его изучения. Что и сделал Д. Дойч.
В 1992 году Ричард Йожа предложил расширить задачу Д. Дойча и рассмотреть функцию f : {0, 1}n → {0, 1}, то есть не ограничиваться 4-мя функциями, рассмотренными нами ранее. Проблема лишь в том, что количество различных таких функций равно 22n, и среди этого количества большую часть составляют функции, которые не являются ни константными, ни сбалансированными. Поэтому задачу сформулировали несколько искусственным образом, а именно ограничили возможные виды функции, и она может быть либо константной, либо сбалансированной.
Как это ни странно, расширение задачи нисколько не сказалось на сложности алгоритма. В случае задачи Йожи алгоритм остаётся абсолютно тем же самым. Вот словесное описание последовательности его шагов: Инициализировать начальное состояние из n кубитов, которое должно быть |0n>.
Применить к начальному состоянию гейт Адамара для n кубитов H⊗n, в результате чего получается равновероятностная суперпозиция всех возможных значений n кубитов.
Применить оракул Of, который строится несколько иначе, чем было рассмотрено при описании алгоритма Дойча.
Снова применить гейт Адамара H⊗n.
Произвести измерение. Если в результате измерения будет получено значение |0n>, то функция константна. В противном случае она сбалансирована (при этом значение в результате измерения может быть использовано для получения общего понимания того, на каких значениях функция возвращает значение 1).
Вот диаграмма квантовой схемы описанного алгоритма: Оракул Of меняет фазу на -1 у тех квантовых состояний, для которых функция f возвращает значение 1. Здесь нет особого смысла использовать служебный кубит, поскольку матрица, у которой на главной диагонали стоят только 1 и -1, а в остальных позициях стоят 0, унитарна.Далее с математической точки зрения происходит следующее. Начальное квантовое состояние переходит в равновероятностную суперпозицию. Затем у каждого квантового состояния в этой суперпозиции меняется знак фазы, если функция принимает на этом квантовом состоянии значение 1. Потом, после второго применения гейта Адамара, все квантовые состояния «схлопываются». И если функция является константной, то происходит деструктивная интерференция фаз всех квантовых состояний, кроме |0n>, а у этого квантового состояния наоборот происходит конструктивная интерференция, и его амплитуда становится равна 1.
Проще всего понять эти выкладки на примерах, поэтому реализуем этот алгоритм при помощи тех же самых функций и прочих программных сущностей, которые мы уже использовали при реализации алгоритма Дойча. Алгоритм Дойча-Йожи, в свою очередь, очень интересен для проведения различных экспериментов и замеров частотных вероятностей, поэтому далее приводится некоторое расширение разработанных функций и описывается один эксперимент, который будет небезынтересным заинтересованному читателю.
Для начала определим функцию для создания оракулов. То, что в предыдущий раз мы вручную определяли оракулы в виде матриц, это хорошо, поскольку позволяет отточить навыки в квантовой схемотехнике. Но пришла пора сделать нормальную функцию для построения оракула для алгоритма Дойча-Йожи при использовании произвольной функции f : {0, 1}n → {0, 1}. Так что вот определение: makeOracle: ([Bool] → Bool) → Int → Matrix (Complex Double) makeOracle f n = matrixToComplex $ zipWith makeLine domain [1…2^n] where zeroes = replicate (2^n) 0 domain = replicateM n [False, True] makeLine: [Bool] → Int → [Int] makeLine x i = changeElement zeroes i ((-1)^(if f x then 1 else 0)) Функция makeOracle принимает на вход функцию f с типом [Bool] → Bool, а также количество кубитов n. Далее она строит всю область определения функции (domain), представляющую из себя список всех возможных комбинаций значений False и True длиной n. Область определения (длина списка составляет 2n) сшивается в пары со списком индексов от 1 до 2n. Это необходимо для построения матрицы.Матрицу оракула строим при помощи локально определённой функции makeLine, которая строит одну строку матрицы. На вход она получает элемент области определения функции и номер строки матрицы. Дальше она заменяет в списке из нулей длины 2n элемент, стоящий на позиции, равной номеру строки матрицы, на 1 или -1 в зависимости от значения функции.
После этого матрица преобразуется в комплекснозначную при помощи уже известной функции matrixToComplex и возвращается в качестве результата.
Здесь есть вызов функции changeElement, которая меняет элемент в списке на заданной позиции. Её определение очень просто:
changeElement: [a] → Int → a → [a] changeElement xs i x = take (i — 1) xs ++ [x] ++ drop i xs Размерность списка и номер элемента не проверяются на адекватность, поэтому разработчику необходимо самостоятельно следить за этим делом.Теперь можно применить функцию makeOracle для построения оракула. Но в целях экспериментирования сделаем девять оракулов:
oracle: Int → [Bool] → Bool oracle 1 [_, _, _] = False oracle 2 [x, y, z] = x && y && z oracle 3 [x, y, _] = x && y oracle 4 [x, y, z] = x && (z || y && not z) oracle 5 [x, _, _] = x oracle 6 [x, y, z] = y && z || x && (not y || y && not z) oracle 7 [x, y, z] = y || oracle 6 [x, y, z] oracle 8 [x, y, z] = x || y || z oracle 9 [_, _, _] = True Первый аргумент функции oracle принимает на вход номер оракула. Частичное применение этой функции с номером даёт функцию, которую ожидает на вход функция makeOracle. Такой подход позволяет использовать списки номеров для массового вызова функции, что будет использовано далее.Все девять оракулов определены так, как показывает следующая таблица:
X1 X2 X3 f 1 2 3 4 5 6 7 8 9 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 1 1 1 0 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 0 1 0 0 0 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 Ясно, что для номеров оракула 1 и 9 алгоритм должен вернуть |000>, а вот что он вернёт для остальных функций? Давайте разберёмся…Вот определение функции, реализующей сам алгоритм Дойча-Йожи. Оно очень несложное:
jozsa: Matrix (Complex Double) → Int → IO String jozsa f n = initial |> gateHn n |> f |> gateHn n >>> (measure. fromVector n) where initial = toVector $ foldl1 entangle $ replicate n qubitZero Всё по описанию: готовим начальное состояние при помощи свёртки списка из n кубитов в состоянии |0> и одного (служебного) кубита в состоянии |1>, применяем гейт Адамара, далее оракул, и снова гейт Адамара. После этого производим измерение. Как видно, определение этой функции общее, и она принимает на вход оракул для функции f : {0, 1}n → {0, 1}, но надо ещё и указать значение n.Для эксперимента нам потребуется строить гистограммы, причём для девяти разных вариантов функции, поэтому для этих целей напишем специальную функцию. Вот она:
histogram: (Monad m, Ord a) => m a → Int → m [(Int, a)] histogram qs n = do l <- replicateM n qs return $ map (length &&& head) $ group $ sort l Здесь при помощи функции replicateM заданное число раз (n) выполняется квантовый алгоритм, передаваемый в виде аргумента qs. Результаты его выполнения собираются в список l. Далее этот список результатов выполнения квантовой схемы сортируется, группируется (получается список списков), потом к каждому списку в списке применяется функция (length &&& head), которая преобразует список в пару вида (длина списка, голова списка). Оставляем головы потому, что все элементы этих списков одинаковы после группировки. В итоге получается список пар, а это и есть требуемая гистограмма.Теперь перейдём к определению функции main:
main: Int → IO [[(Int, String)]] main n = mapM (\i → histogram (jozsa (makeOracle (oracle i) 3) 3) n) [1…9] Вот тут и используется тот метод, использованный в определении функции oracle. Мы просто берём список [1…9] и при помощи функции map применяем к каждому его элементу процесс построения оракула, его прогонки через алгоритм Дойча-Йожи и построения гистограммы. В результате запуска этой функции (скажем, для каждого оракула прогоним алгоритм один миллион раз), получается занимательная таблица: X1 X2 X3 f 1 2 3 4 5 6 7 8 9 0 0 0 1 000 000 561 592 249 916 62 405 62 504 250 329 562 946 1 000 000 0 0 1 69 964 62 373 62 706 62 096 0 1 0 62 666 249 794 62 694 62 515 249 748 62 240 0 1 1 62 108 62 098 62 525 62 560 1 0 0 63 144 250 264 562 886 1 000 000 562 153 250 030 62 595 1 0 1 62 304 62 517 62 357 62 763 1 1 0 62 799 250 026 62 505 62 386 249 893 62 628 1 1 1 62 423 62 522 62 854 62 172 Результаты очень показательны. Они абсолютно подтверждают то, что для константных функций результат должен быть |000>. Но почему для сбалансированной функции № 5 результатом стало |100>, а не, например, |001>? Единица в первом кубите показывает, что функция сбалансирована именно по первому кубиту (вспомним её определение). Если бы мы использовали определение: oracle 5 [_, _, z] = z то в результате 100% измерений дали бы именно результат |001>. А если бы функция не была сбалансирована по какой-либо переменной, то её результат был бы вероятностным.Далее смотрим на функции № 2 и 8. Они почти константны. Именно поэтому с более 55% вероятностью на выходе получается результат |000>. То же самое можно сказать о функциях № 4 и 6 — они почти сбалансированы, поэтому опять с более чем 55% вероятности в результате выходит уже понятное нам значение |100>.
Что касается функций № 3 и 5, то они одинаково далеко находятся от константных и сбалансированных, поэтому результаты примерно равновероятностно распределены между четырьмя возможными значениями. Эти значения опять намекают на то, на каких именно входных аргументах функция принимает значение 1.
Заинтересованному читателю рекомендуется дальше поэкспериментировать с разработанным алгоритмом, чтобы закрепить у себя понимание того, как он работает. Ну, а я постепенно буду готовить материалы для рассмотрения следующего алгоритма.Исходный код каждый желающий может получить здесь.
Мои предыдущие статьи по теме квантовых вычислений:
