Алгоритм Бернштейна — Вазирани
Алгоритм Бернштейна — Вазирани (англ. Bernstein–Vazirani algorithm) — квантовый алгоритм, решающий задачу нахождения -битного числа (в иностранной литературе также употребляется термин скрытая строка[1]), скрытого в черном ящике. Предложен Итаном Бернштейном и Умешем Вазирани в 1993 году . Данный алгоритм решает поставленную задачу значительно быстрее, чем это возможно в неквантовой постановке . Алгоритм может применяться в базах данных, атаках на блочные шифры, тестах производительности для квантовых компьютеров , был реализован на 5- и 16-кубитных квантовых компьютерах IBM .
История
Алгоритм предложен профессором Калифорнийского университета в Беркли Умешем Вазирани[англ.] и его студентом Итаном Бернштейном. При описании алгоритма современные источники, как правило, ссылаются на выступление Бернштейна и Вазирани[2] на симпозиуме по теории вычислений[англ.] в 1993 году[3]. Алгоритм Бернштейна — Вазирани является расширенной версией алгоритма Дойча — Йожи, поскольку вместо определения принадлежности функции к определённому классу — сбалансированная или постоянная (то есть принимает либо значение 0, либо 1 при любых аргументах) — алгоритм находит «спрятанный» вектор, позволяющий однозначно определить значение функции в любой точке[4].
Алгоритм Бернштейна — Вазирани демонстрирует в решаемой им задаче зазор между классическими и квантовыми алгоритмами по наименьшему требуемому количеству запросов к оракулу (чёрному ящику). Даже если разрешить использование вероятностных алгоритмов (с заранее ограниченной вероятностью ошибки), решение классической задачи потребует обращений к оракулу, в то время как в квантовом алгоритме достаточно обращений к нему[5].
Постановка задачи Бернштейна — Вазирани
Классическая задача
Рассмотрим оракул, преобразующий -битное число в один бит, то есть .
Причём , где — скалярное произведение вида: . Считаем, что один вызов функции осуществляется за константное время.
Требуется найти [1].
Квантовая задача
Постановка задачи в квантовой модели похожая, но доступ к оракулу в ней осуществляется не напрямую через функцию , а через
- ,
где —
Квантовым состояниям и соответствуют векторы и . Вектор для совместного состояния может быть представлен как произведение [6].
Аналогично классическому случаю, предполагается, что обращение к оракулу, вычисляющему результат применения оператора к входящей системе из кубита, выполняется за константное время.
В квантовом случае, как и в классическом, предполагается, что , и требуется найти [1].
Алгоритм
Классическая задача
В классическом случае при каждом вызове оракула возвращается один бит числа , поэтому чтобы найти -битное число , нужно вызвать оракул раз. Ниже приведён вариант обращений к оракулу, позволяющих целиком восстановить [1]:
Количество обращений к оракулу в классическом случае равно , где — количество бит числа . Несложными теоретико-информационными рассуждениями можно показать, что эта оценка не улучшаема даже в рамках класса BPP[1].
Квантовый алгоритм
В основу алгоритма положен n-кубитный оператор Адамара:
А также тот факт, что применение оператора к состоянию вида , где даёт в результате величину [1].
По шагам работа алгоритма может быть представлена следующим образом[1]:
- На первом шаге оператор Адамара применяется к -кубитному состоянию , состоящего из основного состояния и вспомогательного бита[англ.] : ;
- Затем к результату предыдущего шага применяется оператор : ;
- После чего к первым кубитам результата применяется , что, с учётом того, что , даёт[4]: .
В результате измерение входного регистра даст значение [1]. Таким образом, в квантовой постановке задачи достаточно обращений к оракулу. В общем случае построение и использование оракула требует
Реализация алгоритма на компьютерах IBM
В любой практической реализации алгоритма Бернштейна — Вазирани основную сложность составляет создание оракула, так как построение и использование оракула требует
Кроме сложности построения оракула, практической реализации сопутствуют проблемы с точностью. Тестирование системы проводилось на 1-, 2- и 3-битных строках, на которых симулятор IBM-Qiskit[англ.] выдавал правильный ответ со 100 % точностью. Затем было проведено тестирование 1- и 2-битных строк на 5-кубитной машине ibmqx4 и 16-кубитной ibmqx5, где были зафиксированы ошибки вычислений и сильное отклонение от ожидаемого результата[1].
Практическое применение
Алгоритм Бернштейна — Вазирани может применяться:
- В базах данных[8]. С помощью алгоритма доступ к нужным данным теоретически можно получить значительно быстрее, чем в классическом случае.
- В атаке на блочный шифр[9]. Алгоритм Бернштейна — Вазирани предоставляет несколько новых, более совершенных, чем в классическом случае, способов атаки на блочный шифр.
- В тесте производительности для квантовых компьютеров[10]. Алгоритм используется в качестве теста производительности для 11-кубитного квантового компьютера.
Примечания
- ↑ 1 2 3 4 5 6 7 8 9 10 11 12 Coles et al, 2018, p. 10—13.
- .
- ↑ Hidary, 2019, p. 104—107.
- ↑ 1 2 Sevag Gharibian. Lecture 7: The Deutsch-Josza and Berstein-Vazirani algorithms (англ.) // Introduction to Quantum Computation Summer 2018, University of Paderborn. — P. 1—10.
- ↑ Hidary, 2019, p. 12—13.
- ↑ Coles et al, 2018, p. 4.
- .
- ↑ А.А. Ежов. Некоторые проблемы квантовой нейротехнологии (рус.) // Научная сессия МИФИ–2003. V всероссийская научно-техническая конференция «Нейроинформатика–2003»: лекции по нейроинформатике. Часть 2. — 2003. — С. 44—45. Архивировано 21 января 2022 года.
- .
- .
Ссылки
- Patrick J. Coles, Stephan Eidenbenz, Scott Pakin, Adetokunbo Adedoyin, John Ambrosiano. Quantum Algorithm Implementations for Beginners // arXiv:1804.03719 [quant-ph]. — 2018.
- David Deutsch, Roger Penrose. Quantum theory, the Church–Turing principle and the universal quantum computer (англ.) // Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences. — 1985. — 8 July (vol. 400, iss. 1818). — P. 97–117. — .
- Charles H. Bennett, Ethan Bernstein, Gilles Brassard, Umesh Vazirani. Strengths and Weaknesses of Quantum Computing (англ.) // SIAM J. Comput.. — 1997. — Vol. 26. — P. 1510–1523. — .
- Jack D. Hidary. Quantum Computing: An Applied Approach. — Springer International Publishing, 2019. — С. 104—107. — .
Эта статья входит в число добротных статей русскоязычного раздела Википедии. |