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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Алгоритм Дойча — Йожи для функции от переменных.  — преобразование Адамара.  — фазовый запрос. Нижний кубит — вспомогательный, используемый для осуществления фазового запроса.

Алгоритм Дойча — Йожи (упоминается также как алгоритм Дойча — Джозы) — квантовый алгоритм, предложенный Давидом Дойчем и Ричардом Йожей[en] в 1992 году, и ставший одним из первых примеров алгоритмов, предназначенных для выполнения на квантовых компьютерах. Наряду с другими квантовыми алгоритмами, благодаря использованию явления квантовой запутанности и принципа суперпозиции, обладает возможностью продемонстрировать квантовое превосходство[en] — значительное ускорение выполнения по сравнению с соответствующими классическими алгоритмами.

Задача Дойча — Йожи заключается в определении, является ли функция нескольких двоичных переменных постоянной (принимает либо значение 0, либо 1 при любых аргументах) или сбалансированной (для половины области определения принимает значение 0, для другой половины 1). При этом считается априорно известным, что функция либо является константой, либо сбалансирована.

Для решения этой задачи классическому детерминированному алгоритму необходимо произвести вычислений функции в худшем случае. Классическому вероятностному алгоритму потребуется меньше времени, чтобы дать верный ответ с высокой вероятностью. Но в любом случае для получения верного ответа с единичной вероятностью потребуется вычислений. Алгоритм даёт верный ответ, один раз применив фазовый запрос, соответствующий заданной функции .

Если функция несбалансированна, то алгоритм может выдать ответ «константа» с некоторой вероятностью, причём чем больше разница между количеством «0» и «1», тем больше будет эта вероятность[1].

Алгоритм Дойча — первый вариант алгоритма, разработанный Дойчем в 1985 году; в нём рассматривается функция от одной переменной.

Алгоритм[править | править код]

На входе алгоритма есть булева функция от булевых переменных. Алгоритм представляет собой применение к нулевому вектору оператора и измерение состояния регистра. Если все биты регистра равны 0, значит значение функции не зависит от , в противном случае функция является сбалансированной.

Здесь  — преобразование Адамара[en]:

,

а  — фазовый запрос, который инвертирует фазу для состояний регистра, соответствующих единицам функции и не изменяет состояния, соответствующие нулям функции[2]:

.

Работа алгоритма на примере задачи Дойча[править | править код]

На вход алгоритму подаётся булева функция одной переменной . Всего существуют четыре таких функции[2]:

1 0 0
2 1 1
3 0 1
4 1 0

Функции 1 и 2 — константные, а функции 3 и 4 — сбалансированные.

На первом шаге кубиту задаётся нулевое состояние:

Применение преобразования Адамара даёт:

.

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

Применение фазового запроса к функции , получается следующее состояние:

.

Второе преобразование Адамара приводит к следующему состоянию:

.

При измерении состояния кубита получается 0 для константных функций и 1 для сбалансированных:

Состояние кубита Вероятность получения 0 Вероятность получения 1
1
2
3
4

Примечания[править | править код]