Алгоритм Бернштейна — Вазирани

Алгоритм Бернштейна — Вазирани (англ. Bernstein–Vazirani algorithm) — квантовый алгоритм, решающий задачу нахождения -битного числа (в иностранной литературе также употребляется термин скрытая строка[1]), скрытого в черном ящике. Предложен Итаном Бернштейном и Умешем Вазирани в 1993 году. Данный алгоритм решает поставленную задачу значительно быстрее, чем это возможно в неквантовой постановке. Алгоритм может применяться в базах данных, атаках на блочные шифры, тестах производительности для квантовых компьютеров, был реализован на 5- и 16-кубитных квантовых компьютерах IBM.

История

Алгоритм предложен профессором Калифорнийского университета в Беркли Умешем Вазирани и его студентом Итаном Бернштейном. При описании алгоритма современные источники, как правило, ссылаются на выступление Бернштейна и Вазирани[2] на симпозиуме по теории вычислений в 1993 году[3]. Алгоритм Бернштейна — Вазирани является расширенной версией алгоритма Дойча — Йожи, поскольку вместо определения принадлежности функции к определённому классу — сбалансированная или постоянная (то есть принимает либо значение 0, либо 1 при любых аргументах) — алгоритм находит «спрятанный» вектор, позволяющий однозначно определить значение функции в любой точке[4].

Алгоритм Бернштейна — Вазирани демонстрирует в решаемой им задаче зазор между классическими и квантовыми алгоритмами по наименьшему требуемому количеству запросов к оракулу (чёрному ящику). Даже если разрешить использование вероятностных алгоритмов (с заранее ограниченной вероятностью ошибки), решение классической задачи потребует обращений к оракулу, в то время как в квантовом алгоритме достаточно обращений к нему[5].

Постановка задачи Бернштейна — Вазирани

Классическая задача

Рассмотрим оракул, преобразующий -битное число в один бит, то есть .

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

Требуется найти [1].

Квантовая задача

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

,

где  — кет-вектор, соответствующий квантовому состоянию ,  — бра-вектор, соответствующий квантовому состоянию ,  — произведение Кронекера,  — сложение по модулю 2.

Квантовым состояниям и соответствуют векторы и . Вектор для совместного состояния может быть представлен как произведение [6].

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

В квантовом случае, как и в классическом, предполагается, что , и требуется найти [1].

Алгоритм

Классическая задача

В классическом случае при каждом вызове оракула возвращается один бит числа , поэтому чтобы найти -битное число , нужно вызвать оракул раз. Ниже приведён вариант обращений к оракулу, позволяющих целиком восстановить [1]:

Количество обращений к оракулу в классическом случае равно , где  — количество бит числа . Несложными теоретико-информационными рассуждениями можно показать, что эта оценка не улучшаема даже в рамках класса BPP[1].

Квантовый алгоритм

В основу алгоритма положен n-кубитный оператор Адамара:

А также тот факт, что применение оператора к состоянию вида , где даёт в результате величину [1].

По шагам работа алгоритма может быть представлена следующим образом[1]:

  1. На первом шаге оператор Адамара применяется к -кубитному состоянию , состоящего из основного состояния и вспомогательного бита :
    ;
  2. Затем к результату предыдущего шага применяется оператор :
    ;
  3. После чего к первым кубитам результата применяется , что, с учётом того, что , даёт[4]:
    .

В результате измерение входного регистра даст значение [1]. Таким образом, в квантовой постановке задачи достаточно обращений к оракулу. В общем случае построение и использование оракула требует логических элементов, но это не учитывается при анализе алгоритма в данной модели, так как значимым для неё является только число обращений к оракулу[1]. Алгоритм в таком виде был реализован на 5- и 16-кубитных компьютерах IBM[1], также возможно собрать оптическую cистему, реализующую алгоритм[7].

Реализация алгоритма на компьютерах IBM

В любой практической реализации алгоритма Бернштейна — Вазирани основную сложность составляет создание оракула, так как построение и использование оракула требует логических элемента.[1]

Кроме сложности построения оракула, практической реализации сопутствуют проблемы с точностью. Тестирование системы проводилось на 1-, 2- и 3-битных строках, на которых симулятор IBM-Qiskit выдавал правильный ответ со 100 % точностью. Затем было проведено тестирование 1- и 2-битных строк на 5-кубитной машине ibmqx4 и 16-кубитной ibmqx5, где были зафиксированы ошибки вычислений и сильное отклонение от ожидаемого результата[1].

Практическое применение

Алгоритм Бернштейна — Вазирани может применяться:

  1. В базах данных[8]. С помощью алгоритма доступ к нужным данным теоретически можно получить значительно быстрее, чем в классическом случае.
  2. В атаке на блочный шифр[9]. Алгоритм Бернштейна — Вазирани предоставляет несколько новых, более совершенных, чем в классическом случае, способов атаки на блочный шифр.
  3. В тесте производительности для квантовых компьютеров[10]. Алгоритм используется в качестве теста производительности для 11-кубитного квантового компьютера.

Примечания

  1. Coles et al, 2018, p. 10—13.
  2. Ethan Bernstein, Umesh Vazirani. Quantum Complexity Theory // Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing. — New York, NY, USA: ACM, 1993. С. 11–20. ISBN 978-0-89791-591-5. doi:10.1145/167088.167097.
  3. Hidary, 2019, p. 104—107.
  4. Sevag Gharibian. Lecture 7: The Deutsch-Josza and Berstein-Vazirani algorithms (англ.) // Introduction to Quantum Computation Summer 2018, University of Paderborn. P. 1—10.
  5. Hidary, 2019, p. 12—13.
  6. Coles et al, 2018, p. 4.
  7. P. Londero, K. Banaszek, I. A. Walmsley, C. Dorrer, M. Anderson. Efficient optical implementation of the Bernstein-Vazirani algorithm (англ.) // Physical Review A. — 2004. Т. 69, вып. 1. С. 010302–010302.4. ISSN 1050-2947. doi:10.1103/PhysRevA.69.010302.
  8. А.А. Ежов. Некоторые проблемы квантовой нейротехнологии (рус.) // Научная сессия МИФИ–2003. V всероссийская научно-техническая конференция «Нейроинформатика–2003»: лекции по нейроинформатике. Часть 2. — 2003. С. 44—45.
  9. Huiqin Xie, Li Yang. Using Bernstein–Vazirani algorithm to attack block ciphers (англ.) // Designs, Codes and Cryptography. — 2019-05-01. Vol. 87, iss. 5. P. 1161–1182. ISSN 1573-7586. doi:10.1007/s10623-018-0510-5.
  10. K. Wright, K. M. Beck, S. Debnath, J. M. Amini, Y. Nam, N. Grzesiak, J.-S. Chen, N. C. Pisenti, M. Chmielewski, C. Collins, K. M. Hudek, J. Mizrahi, J. D. Wong-Campos, S. Allen, J. Apisdorf, P. Solomon, M. Williams, A. M. Ducore, A. Blinov, S. M. Kreikemeier, V. Chaplin, M. Keesan, C. Monroe & J. Kim. Benchmarking an 11-qubit quantum computer // Nature Communications. — 2019. — Vol. 10. — С. 5464. doi:10.1038/s41467-019-13534-2.

Ссылки

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.