Алгоритм Бернштейна — Вазирани () — квантовый алгоритм, решающий задачу нахождения -битного числа (в иностранной литературе также употребляется термин скрытая строка), скрытого в черном ящике. Предложен Итаном Бернштейном и Умешем Вазирани в 1993 году. Данный алгоритм решает поставленную задачу значительно быстрее, чем это возможно в неквантовой постановке. Алгоритм может применяться в базах данных, атаках на блочные шифры, тестах производительности для квантовых компьютеров, был реализован на 5- и 16-кубитных квантовых компьютерах IBM.
История Алгоритм предложен профессором Калифорнийского университета в Беркли Умешем Вазирани и его студентом Итаном Бернштейном. При описании алгоритма современные источники, как правило, ссылаются на выступление Бернштейна и Вазирани на в 1993 году. Алгоритм Бернштейна — Вазирани является расширенной версией алгоритма Дойча — Йожи, поскольку вместо определения принадлежности функции к определённому классу — сбалансированная или постоянная (то есть принимает либо значение 0, либо 1 при любых аргументах) — алгоритм находит «спрятанный» вектор, позволяющий однозначно определить значение функции в любой точке.
Алгоритм Бернштейна — Вазирани демонстрирует в решаемой им задаче зазор между классическими и квантовыми алгоритмами по наименьшему требуемому количеству запросов к оракулу (чёрному ящику). Даже если разрешить использование вероятностных алгоритмов (с заранее ограниченной вероятностью ошибки), решение классической задачи потребует обращений к оракулу, в то время как в квантовом алгоритме достаточно обращений к нему.
Постановка задачи Бернштейна — Вазирани
Классическая задача Рассмотрим оракул, преобразующий -битное число в один бит, то есть .
Причём , где — скалярное произведение вида: . Считаем, что один вызов функции осуществляется за константное время.
Требуется найти .
Квантовая задача Постановка задачи в квантовой модели похожая, но доступ к оракулу в ней осуществляется не напрямую через функцию , а через линейный оператор , действующий на систему из кубита:
,
где — кет-вектор, соответствующий квантовому состоянию , — бра-вектор, соответствующий квантовому состоянию , — произведение Кронекера, — сложение по модулю 2.
Квантовым состояниям и соответствуют векторы и . Вектор для совместного состояния может быть представлен как произведение .
Аналогично классическому случаю, предполагается, что обращение к оракулу, вычисляющему результат применения оператора к входящей системе из кубита, выполняется за константное время.
В квантовом случае, как и в классическом, предполагается, что , и требуется найти .
Алгоритм
Классическая задача В классическом случае при каждом вызове оракула возвращается один бит числа , поэтому чтобы найти -битное число , нужно вызвать оракул раз. Ниже приведён вариант обращений к оракулу, позволяющих целиком восстановить :
Количество обращений к оракулу в классическом случае равно , где — количество бит числа . Несложными теоретико-информационными рассуждениями можно показать, что эта оценка не улучшаема даже в рамках класса BPP.
Квантовый алгоритм В основу алгоритма положен n-кубитный оператор Адамара:
А также тот факт, что применение оператора к состоянию вида , где даёт в результате величину .
По шагам работа алгоритма может быть представлена следующим образом:
На первом шаге оператор Адамара применяется к -кубитному состоянию , состоящего из основного состояния и вспомогательного бита : ; Затем к результату предыдущего шага применяется оператор : ; После чего к первым кубитам результата применяется , что, с учётом того, что , даёт: .
В результате измерение входного регистра даст значение . Таким образом, в квантовой постановке задачи достаточно обращений к оракулу. В общем случае построение и использование оракула требует логических элементов, но это не учитывается при анализе алгоритма в данной модели, так как значимым для неё является только число обращений к оракулу. Алгоритм в таком виде был реализован на 5- и 16-кубитных компьютерах IBM, также возможно собрать оптическую систему, реализующую алгоритм.
Реализация алгоритма на компьютерах IBM В любой практической реализации алгоритма Бернштейна — Вазирани основную сложность составляет создание оракула, так как построение и использование оракула требует логических элемента.
Кроме сложности построения оракула, практической реализации сопутствуют проблемы с точностью. Тестирование системы проводилось на 1-, 2- и 3-битных строках, на которых симулятор выдавал правильный ответ со 100 % точностью. Затем было проведено тестирование 1- и 2-битных строк на 5-кубитной машине ibmqx4 и 16-кубитной ibmqx5, где были зафиксированы ошибки вычислений и сильное отклонение от ожидаемого результата.
Практическое применение Алгоритм Бернштейна — Вазирани может применяться:
В базах данных. С помощью алгоритма доступ к нужным данным теоретически можно получить значительно быстрее, чем в классическом случае. В атаке на блочный шифр. Алгоритм Бернштейна — Вазирани предоставляет несколько новых, более совершенных, чем в классическом случае, способов атаки на блочный шифр. В тесте производительности для квантовых компьютеров. Алгоритм используется в качестве теста производительности для 11-кубитного квантового компьютера.
Примечания
Ссылки
Категория:Квантовые алгоритмы