Алгоритм Deutsch-Jozsa является детерминированным квантовый алгоритм , предложенный Дэвидом Дойч и Ричард Джозза в 1992 году с улучшениями по Ричард Клив , Артур Экерт , Кьяра Macchiavello и Мишель Моска в 1998 году [1] [2] Хотя мало текущего практического использования, это один из первых примеров квантового алгоритма, который экспоненциально быстрее любого возможного детерминированного классического алгоритма. [3]
Постановка задачи
В задаче Дойча – Йожи нам дается квантовый компьютер черного ящика, известный как оракул, который реализует некоторую функцию. Функция принимает на вход n-значные двоичные значения и выдает на выходе либо 0, либо 1 для каждого такого значения. Нам обещают, что функция будет либо постоянной (0 на всех выходах или 1 на всех выходах), либо сбалансированной (возвращает 1 для половины входной области и 0 для другой половины). [4] Задача состоит в том, чтобы определить, постоянна или сбалансирована с помощью оракула.
Мотивация
Задача Дойча – Йожи специально разработана, чтобы быть простой для квантового алгоритма и сложной для любого детерминированного классического алгоритма. Мотивация состоит в том, чтобы показать проблему черного ящика, которая может быть эффективно решена квантовым компьютером без ошибок, в то время как детерминированный классический компьютер потребует большого количества запросов к черному ящику для решения проблемы. Более формально, это дает оракул, относительно которого EQP , класс задач, которые могут быть решены точно за полиномиальное время на квантовом компьютере, и P различны. [5]
Поскольку задачу легко решить на вероятностном классическом компьютере, она не приводит к разделению оракула с помощью BPP , класса задач, которые могут быть решены с ограниченной ошибкой за полиномиальное время на вероятностном классическом компьютере. Проблема Саймона - это пример проблемы, которая приводит к разделению оракула между BQP и BPP .
Классическое решение
Для обычного детерминированного алгоритма, где n - количество бит, оценки потребуется в худшем случае. Чтобы доказать, чтоявляется константой, необходимо оценить чуть более половины набора входов, и их выходы должны быть признаны идентичными (помня, что функция гарантированно будет либо сбалансированной, либо постоянной, а не где-то посередине). Наилучший случай имеет место, когда функция сбалансирована и первые два выходных значения, которые случаются, различны. Для обычного рандомизированного алгоритма постоянная оценок функции достаточно, чтобы дать правильный ответ с высокой вероятностью (отказ с вероятностью с участием ). Тем не мение,оценки по-прежнему необходимы, если мы хотим всегда правильный ответ. Квантовый алгоритм Дойча-Йозса дает ответ, который всегда является правильным при единственной оценке.
История
Алгоритм Дойча – Йозса обобщает более раннюю (1985 г.) работу Дэвида Дойча, которая предоставила решение для простого случая, когда .
В частности, нам была дана логическая функция , вход которой равен 1 биту,и спросил, постоянный ли он. [6]
Алгоритм, как первоначально предложил Дойч, на самом деле не был детерминированным. Алгоритм удался с вероятностью половина. В 1992 году Дойч и Йозса разработали детерминированный алгоритм, который был обобщен до функции, которая принимаетбит для его ввода. В отличие от алгоритма Дойча, этот алгоритм требовал двух вычислений функции вместо одного.
Дальнейшие усовершенствования алгоритма Дойча – Йозса были сделаны Кливом и др. [2], в результате чего был получен детерминированный алгоритм, требующий только одного запроса. Этот алгоритм до сих пор называют алгоритмом Дойча – Йозса в честь использованных в них новаторских методов. [2]
Алгоритм
Чтобы алгоритм Дойча – Йожа работал, вычисления оракула из должен быть квантовым оракулом, который не декогерируется . Он также не должен оставлять никаких копий валяется в конце вызова оракула.
Алгоритм начинается с состояние бита . То есть каждый из первых n битов находится в состоянии и последний бит . Преобразование Адамара применяется к каждому биту , чтобы получить состояние
- .
У нас есть функция реализован как квантовый оракул. Оракул отображает состояние к , где сложение по модулю 2 (подробности реализации см. ниже). Применение квантового оракула дает
- .
Для каждого равно 0 или 1. Проверяя эти две возможности, мы видим, что указанное выше состояние равно
- .
На этом этапе последний кубит могут быть проигнорированы, поэтому ниже остается:
- .
Мы применяем преобразование Адамара к каждому кубиту, чтобы получить
где - сумма побитового произведения (где сложение по модулю 2).
Наконец, мы исследуем вероятность измерения ,
который оценивается в 1, если постоянно ( конструктивная интерференция ) и 0, еслисбалансирован ( деструктивная интерференция ). Другими словами, окончательное измерение будет (т.е. все нули), если постоянна и даст некоторые другие состояния, если сбалансирован.
Алгоритм Дойча
Алгоритм Дойча является частным случаем общего алгоритма Дойча – Йоже. Нам нужно проверить состояние. Это эквивалентно проверке (где является сложением по модулю 2, которое также можно рассматривать как квантовый вентиль XOR, реализованный как вентиль Controlled NOT ), если ноль, то постоянно, иначе не является постоянным.
Начнем с двухкубитного состояния и применить преобразование Адамара к каждому кубиту. Это дает
Нам дана квантовая реализация функции что отображает к . Применяя эту функцию к нашему текущему состоянию, мы получаем
Мы игнорируем последний бит и глобальную фазу и поэтому имеем состояние
Применяя преобразование Адамара к этому состоянию, мы имеем
тогда и только тогда, когда мы измеряем а также тогда и только тогда, когда мы измеряем . Итак, мы с уверенностью знаем, постоянный или сбалансированный.
Смотрите также
Рекомендации
- ^ Дэвид Дойч и Ричард Джозз (1992). «Быстрое решение задач квантовыми вычислениями». Труды Королевского общества Лондона . 439 (1907): 553–558. Bibcode : 1992RSPSA.439..553D . CiteSeerX 10.1.1.655.5997 . DOI : 10,1098 / rspa.1992.0167 .
- ^ а б в Р. Клив; А. Экерт; К. Маккиавелло; М. Моска (1998). «Возвращение к квантовым алгоритмам». Труды Королевского общества Лондона . 454 (1969): 339–354. arXiv : квант-ph / 9708016 . Bibcode : 1998RSPSA.454..339C . DOI : 10,1098 / rspa.1998.0164 .
- ^ Саймон, Дэниел (ноябрь 1994 г.). «О силе квантовых вычислений» . 94 Материалы 35-го ежегодного симпозиума по основам информатики : 116–123.
- ^ «Уверенность от неопределенности» . Архивировано из оригинала на 2011-04-06 . Проверено 13 февраля 2011 .[ ненадежный источник? ]
- ^ Johansson, N .; Ларссон, Дж. (2017). «Эффективное классическое моделирование алгоритмов Дойча – Йожи и Саймона». Quantum Inf Process (2017) . 16 (9): 233. arXiv : 1508.05027 . DOI : 10.1007 / s11128-017-1679-7 .
- ^ Дэвид Дойч (1985). «Квантовая теория, принцип Чёрча-Тьюринга и универсальный квантовый компьютер» (PDF) . Труды Королевского общества Лондона . 400 (1818): 97–117. Bibcode : 1985RSPSA.400 ... 97D . CiteSeerX 10.1.1.41.2382 . DOI : 10,1098 / rspa.1985.0070 .[ постоянная мертвая ссылка ]
Внешние ссылки
- Лекция Дойча об алгоритме Дойча-Йозса