Алгоритм Бернштейна — Вазирани
Алгоритм Бернштейна — Вазирани (англ. Bernstein–Vazirani algorithm) — квантовый алгоритм, решающий задачу нахождения [math]\displaystyle{ n }[/math]-битного числа (в иностранной литературе также употребляется термин скрытая строка[1]), скрытого в черном ящике. Предложен Итаном Бернштейном и Умешем Вазирани в 1993 году . Данный алгоритм решает поставленную задачу значительно быстрее, чем это возможно в неквантовой постановке . Алгоритм может применяться в базах данных, атаках на блочные шифры, тестах производительности для квантовых компьютеров , был реализован на 5- и 16-кубитных квантовых компьютерах IBM .
История
Алгоритм предложен профессором Калифорнийского университета в Беркли Умешем Вазирани и его студентом Итаном Бернштейном. При описании алгоритма современные источники, как правило, ссылаются на выступление Бернштейна и Вазирани[2] на симпозиуме по теории вычислений в 1993 году[3]. Алгоритм Бернштейна — Вазирани является расширенной версией алгоритма Дойча — Йожи, поскольку вместо определения принадлежности функции к определённому классу — сбалансированная или постоянная (то есть принимает либо значение 0, либо 1 при любых аргументах) — алгоритм находит «спрятанный» вектор, позволяющий однозначно определить значение функции в любой точке[4].
Алгоритм Бернштейна — Вазирани демонстрирует в решаемой им задаче зазор между классическими и квантовыми алгоритмами по наименьшему требуемому количеству запросов к оракулу (чёрному ящику). Даже если разрешить использование вероятностных алгоритмов (с заранее ограниченной вероятностью ошибки), решение классической задачи потребует [math]\displaystyle{ O(n) }[/math] обращений к оракулу, в то время как в квантовом алгоритме достаточно [math]\displaystyle{ O(1) }[/math] обращений к нему[5].
Постановка задачи Бернштейна — Вазирани
Классическая задача
Рассмотрим оракул, преобразующий [math]\displaystyle{ n }[/math]-битное число в один бит, то есть [math]\displaystyle{ f:\{0, 1\}^n\rightarrow\{0, 1\} }[/math].
Причём [math]\displaystyle{ f(x)= a \cdot x }[/math], где [math]\displaystyle{ \cdot }[/math] — скалярное произведение вида: [math]\displaystyle{ x \cdot y = x_1y_1\oplus x_2y_2\oplus...\oplus x_ny_n }[/math]. Считаем, что один вызов функции [math]\displaystyle{ f }[/math] осуществляется за константное время.
Требуется найти [math]\displaystyle{ a }[/math][1].
Квантовая задача
Постановка задачи в квантовой модели похожая, но доступ к оракулу в ней осуществляется не напрямую через функцию [math]\displaystyle{ f }[/math], а через линейный оператор [math]\displaystyle{ U_f }[/math], действующий на систему из [math]\displaystyle{ n+1 }[/math] кубита:
- [math]\displaystyle{ U_f = \sum_{x\in\{0,1\}^n, y\in\{0,1\}} |x\rangle \langle x| \otimes |y \oplus f(x) \rangle \langle y | }[/math],
где [math]\displaystyle{ |x\rangle }[/math] — кет-вектор, соответствующий квантовому состоянию [math]\displaystyle{ x }[/math], [math]\displaystyle{ \langle x| }[/math] — бра-вектор, соответствующий квантовому состоянию [math]\displaystyle{ x }[/math], [math]\displaystyle{ \otimes }[/math] — произведение Кронекера, [math]\displaystyle{ \oplus }[/math] — сложение по модулю 2.
Квантовым состояниям [math]\displaystyle{ 0 }[/math] и [math]\displaystyle{ 1 }[/math] соответствуют векторы [math]\displaystyle{ |0\rangle = \binom{1}{0} }[/math] и [math]\displaystyle{ |1\rangle = \binom{0}{1} }[/math]. Вектор для совместного состояния [math]\displaystyle{ x_1 x_2 \dots x_n }[/math] может быть представлен как произведение [math]\displaystyle{ |x_1x_2 \dots x_n\rangle = |x_1\rangle \otimes |x_2\rangle \otimes \dots \otimes |x_n\rangle }[/math][6].
Аналогично классическому случаю, предполагается, что обращение к оракулу, вычисляющему результат применения оператора [math]\displaystyle{ U_f }[/math] к входящей системе из [math]\displaystyle{ n+1 }[/math] кубита, выполняется за константное время.
В квантовом случае, как и в классическом, предполагается, что [math]\displaystyle{ f(x)= a \cdot x }[/math], и требуется найти [math]\displaystyle{ a }[/math][1].
Алгоритм
Классическая задача
В классическом случае при каждом вызове оракула возвращается один бит числа [math]\displaystyle{ a }[/math], поэтому чтобы найти [math]\displaystyle{ n }[/math]-битное число [math]\displaystyle{ a }[/math], нужно вызвать оракул [math]\displaystyle{ n }[/math] раз. Ниже приведён вариант [math]\displaystyle{ n }[/math] обращений к оракулу, позволяющих целиком восстановить [math]\displaystyle{ a }[/math][1]:
[math]\displaystyle{ f(1000...0_n) = a_1 }[/math]
[math]\displaystyle{ f(0100...0_n)=a_2 }[/math]
[math]\displaystyle{ \vdots }[/math]
[math]\displaystyle{ f(0000...1_n)=a_n }[/math]
Количество обращений к оракулу в классическом случае равно [math]\displaystyle{ O(n) }[/math], где [math]\displaystyle{ n }[/math] — количество бит числа [math]\displaystyle{ a }[/math]. Несложными теоретико-информационными рассуждениями можно показать, что эта оценка не улучшаема даже в рамках класса BPP[1].
Квантовый алгоритм
В основу алгоритма положен n-кубитный оператор Адамара:
- [math]\displaystyle{ H^{\otimes n} = \frac{1}{\sqrt{2^{n}}}\sum\limits_{x,y\in\{0,1\}^n}{{(-1)}^{x \cdot y}|y\rangle \langle x|} }[/math]
А также тот факт, что применение оператора [math]\displaystyle{ U_f }[/math] к состоянию вида [math]\displaystyle{ |x\rangle |-\rangle = |x\rangle \otimes |-\rangle }[/math], где [math]\displaystyle{ |-\rangle = \frac{|0\rangle - |1\rangle}{\sqrt 2} }[/math] даёт в результате величину [math]\displaystyle{ U_f(|x\rangle |-\rangle) = (-1)^{f(x)}|x\rangle |-\rangle }[/math][1].
По шагам работа алгоритма может быть представлена следующим образом[1]:
- На первом шаге оператор Адамара [math]\displaystyle{ H^{\otimes {(n+1)}} }[/math] применяется к [math]\displaystyle{ (n+1) }[/math]-кубитному состоянию [math]\displaystyle{ |0\rangle^n|1\rangle }[/math], состоящего из основного состояния [math]\displaystyle{ |0\rangle^n }[/math] и вспомогательного бита [math]\displaystyle{ |1\rangle }[/math]: [math]\displaystyle{ |0\rangle^n|1\rangle\xrightarrow{H^{\otimes {(n+1)}}} \frac{1}{\sqrt{2^{n}}}\sum\limits_{x\in\{0,1\}^n}|x\rangle |-\rangle }[/math];
- Затем к результату предыдущего шага применяется оператор [math]\displaystyle{ U_f }[/math]: [math]\displaystyle{ \frac{1}{\sqrt{2^n}} \sum\limits_{x \in \{0,1\}^n} |x\rangle |-\rangle\xrightarrow{~U_f~} \frac{1}{\sqrt{2^{n}}}\sum\limits_{x\in\{0,1\}^n}{(-1)}^{f(x)}|x\rangle|-\rangle }[/math];
- После чего к первым [math]\displaystyle{ n }[/math] кубитам результата применяется [math]\displaystyle{ H^{\otimes(n)} }[/math], что, с учётом того, что [math]\displaystyle{ f(x) = a\cdot x }[/math], даёт[4]: [math]\displaystyle{ \frac{1}{\sqrt{2^{n}}}\sum\limits_{x\in\{0,1\}^n}{(-1)}^{a\cdot x}|x\rangle|-\rangle\xrightarrow{~H^{\otimes(n)}~} \frac{1}{2^{n}}\sum\limits_{x,y\in\{0,1\}^n}{(-1)}^{(a\cdot x) \oplus (x\cdot y)}|y\rangle |-\rangle\sim |a\rangle|-\rangle }[/math].
В результате измерение входного регистра даст значение [math]\displaystyle{ |a\rangle }[/math][1]. Таким образом, в квантовой постановке задачи достаточно [math]\displaystyle{ O(1) }[/math] обращений к оракулу. В общем случае построение и использование оракула требует [math]\displaystyle{ O(4^n) }[/math] логических элементов, но это не учитывается при анализе алгоритма в данной модели, так как значимым для неё является только число обращений к оракулу[1]. Алгоритм в таком виде был реализован на 5- и 16-кубитных компьютерах IBM[1], также возможно собрать оптическую cистему, реализующую алгоритм[7].
Реализация алгоритма на компьютерах IBM
В любой практической реализации алгоритма Бернштейна — Вазирани основную сложность составляет создание оракула, так как построение и использование оракула требует [math]\displaystyle{ O(4^n) }[/math] логических элемента.[1]
Кроме сложности построения оракула, практической реализации сопутствуют проблемы с точностью. Тестирование системы проводилось на 1-, 2- и 3-битных строках, на которых симулятор IBM-Qiskit выдавал правильный ответ со 100 % точностью. Затем было проведено тестирование 1- и 2-битных строк на 5-кубитной машине ibmqx4 и 16-кубитной ibmqx5, где были зафиксированы ошибки вычислений и сильное отклонение от ожидаемого результата[1].
Практическое применение
Алгоритм Бернштейна — Вазирани может применяться:
- В базах данных[8]. С помощью алгоритма доступ к нужным данным теоретически можно получить значительно быстрее, чем в классическом случае.
- В атаке на блочный шифр[9]. Алгоритм Бернштейна — Вазирани предоставляет несколько новых, более совершенных, чем в классическом случае, способов атаки на блочный шифр.
- В тесте производительности для квантовых компьютеров[10]. Алгоритм используется в качестве теста производительности для 11-кубитного квантового компьютера.
Примечания
- ↑ 1,00 1,01 1,02 1,03 1,04 1,05 1,06 1,07 1,08 1,09 1,10 1,11 Coles et al, 2018, p. 10—13.
- ↑ 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.
- ↑ Hidary, 2019, p. 104—107.
- ↑ 4,0 4,1 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.
- ↑ 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.
- ↑ А.А. Ежов. Некоторые проблемы квантовой нейротехнологии (рус.) // Научная сессия МИФИ–2003. V всероссийская научно-техническая конференция «Нейроинформатика–2003»: лекции по нейроинформатике. Часть 2. — 2003. — С. 44—45. Архивировано 21 января 2022 года.
- ↑ 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.
- ↑ 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.
Ссылки
- 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. — doi:10.1098/rspa.1985.0070.
- Charles H. Bennett, Ethan Bernstein, Gilles Brassard, Umesh Vazirani. Strengths and Weaknesses of Quantum Computing (англ.) // SIAM J. Comput.. — 1997. — Vol. 26. — P. 1510–1523. — doi:10.1137/S0097539796300933. — arXiv:quant-ph/9701001.
- Jack D. Hidary. Quantum Computing: An Applied Approach. — Springer International Publishing, 2019. — С. 104—107. — ISBN 978-3030239213. — doi:10.1007/978-3-030-23922-0.