СКОРОСТЬ СХОДИМОСТИ АЛГОРИТМОВ РЕШЕНИЯ ЛИНЕЙНОГО УРАВНЕНИЯ МЕТОДОМ КВАНТОВОГО ОТЖИГА

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Только для подписчиков

Аннотация

Рассмотрены различные итеративные алгоритмы решения линейного уравнения ax = b с помощью квантового вычислительного устройства, работающего по принципу квантового отжига. В предположении, что результат работы компьютера описывается распределением Больцмана, показано, при каких условиях алгоритмы решения уравнения сходятся, и дана оценка скорости их сходимости. Рассмотрено применение данного подхода для алгоритмов, использующих как бесконечное количество кубитов, так и малое количество кубитов. Библ. 31. Фиг. 2.

Об авторах

С. Б. Тихомиров

Pontificia Universidade Católica do Rio de Janeiro — PUC-Rio

Email: setgey.tikhomirov@gmail.com
Рио-де-Жанейро, Бразилия

В. С Шалгин

Санкт-Петербургский государственный университет

Email: st086496@student.spbu.ru
Санкт-Петербург, Россия

Список литературы

  1. Манин Ю.И. Вычислимое и невычислимое. М.: Советское радио, 1980.
  2. Feynman R.P. Simulating physics with computers // Int. J. Theor. Phys. 1982. V 21. № 6. P 467—488. https://doi.org/10.1007/BF02650179.
  3. Williams C.P. Explorations in quantum computing. New York: Springer, 1998. https://doi.org/10.1007/978-1-84628-887-6.
  4. Nielsen M.A., Chuang I.L. Quantum Computation and Quantum Information. Cambridge: Cambridge Univ. Press, 2010. https://doi.org/10.1017/CBO9780511976667.
  5. Grover L.K. A fast quantum mechanical algorithm for database search // Proceed. of the twenty eighth Ann. ACM Symp. on Theory of Computing, Philadelphia, Pennsylvania, USA: Association for Computing Machinery. 1996. P 212-219.https://doi.org/10.1145/237814.237866.
  6. Shor P.W. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer // SIAM J. on Comp. 1997. V. 26. № 5. P. 1484-1509. https://doi.org/10.1137/s0097539795293172.
  7. Harrow A.W., Hassidim A., Lloyd S. Quantum algorithm for linear systems of equations // Phys. Rev. Lett. 2009. V. 103. № 15. P. 150502. https://doi.org/10.1103/physrevlett.103.150502.
  8. Albash T., Lidar D.A. Adiabatic quantum computation // Rev. Mod. Phys. 2018. V. 90. № 1. P. 015002. https://link.aps.org/doi/10.1103/RevModPhys.90.015002.
  9. Kieu T.D. The travelling salesman problem and adiabatic quantum computation: an algorithm // Quant. Inform. Proces. 2019. V. 18. № 3. P. 1-19. https://doi.org/10.1007/s11128-019-2206-9.
  10. Farhi E., Goldstone J., Gutmann S., Sipser M. Quantum Computation by Adiabatic Evolution // arXiv preprint quant-ph/0001106. 2000. https://doi.org/10.48550/arXiv.quant-ph/0001106.
  11. Aharonov D., van Dam W., Kempe J., Landau Z., Lloyd S., Regev O. Adiabatic quantum computation is equivalent to standard quantum computation // SIAM Rev. 2008. V. 50. № 4. P. 755-787. https://doi.org/10.1137/080734479.
  12. Kadowaki T., Nishimori H. Quantum annealing in the transverse Ising model // Phys. Rev. E. 1998. V. 58. № 5. P. 5355-5363. https://doi.org/10.1103/physreve.58.5355.
  13. Bian Z., Chudak F., Macready W.G., Rose G. The Ising model: teaching an old problem new tricks // D-Wave Systems. 2010.
  14. Albash T., Martin-Mayor V., Hen I. Temperature scaling law for quantum annealing optimizers // Phys. Rev. Lett. 2017. V. 119. № 11. P. 110502. https://doi.org/10.1103/physrevlett.119.110502.
  15. D-Wave Systems. QPU Solver Datasheet. https://docs.dwavesys.com/docs/latest/doc_qpu.html, accessed 24 Oct 2023.
  16. Vinci W., Buffoni L., Sadeghi H., Khoshaman A., Andriyash E., Amin M.H. A path towards quantum advantage in training deep generative models with quantum annealers // Machine Learning: Science and Technology. 2020. V. 1. № 4. P. 045028. https://doi.org/10.1088/2632-2153/aba220.
  17. Korenkevych D., Xue Y., Bian Z., Chudak F., Macready W., Rolfe J., Andriyash E. Benchmarking quantum hardware for training of fully visible boltzmann machines // arXiv preprint arXiv:1611.04528. 2016. https://doi.org/10.48550/arXiv.1611.04528.
  18. Denil M., de Freitas N. Toward the implementation of a quantum RBM // NIPS Deep Learning and Unsupervised Feature Learning Workshop. 2011.
  19. Albash T., Lidar D.A. Demonstration of a scaling advantage for a quantum annealer over simulated annealing // Phys. Rev. X. 2018. V. 8. № 3. P. 031016. https://doi.org/10.1103/physrevx.8.031016.
  20. King A.D., Raymond J., Lanting T., Harris R., Zucca A., Altomare F., Berkley A.J., Boothby K., Ejtemaee S., Enderud C., Hoskinson E., Huang S., Ladizinsky E., MacDonald A.J.R., Marsden G., Molavi R., Oh T., Poulin-Lamarre G., Reis M., Rich C., Sato Y., Tsai N., Volkmann M., Whittaker J.D., Yao J., Sandvik A.W., Amin M.H. Quantum critical dynamics in a 5000-qubit programmable spin glass // Nature. 2023. V. 617. № 7959. P. 61-66. https://doi.org/10.1038/s41586-023-05867-2.
  21. O’Malley D., Vesselinov V.V. ToQ.jl: A high-level programming language for D-Wave machines based on Julia // 2016 IEEE High Performance Extreme Computing Conference (HPEC), Waltham, MA, USA. 2016. P. 1-7. 10.1109/HPEC.2016.7761616.
  22. Borle A., Lomonaco S.J. Analyzing the quantum annealing approach for solving linear least squares problems // Lect. Notes Comp. Sci. 2018. P. 289-301. https://doi.org/10.1007/978-3-030-10564-8_23.
  23. Rogers M.L., Singleton R.L. Floating-point calculations on a quantum annealer: Division and matrix inversion // Front. Phys. 2020. V. 8. https://doi.org/10.3389/fphy.2020.00265.
  24. Borle A., Lomonaco S.J. How viable is quantum annealing for solving linear algebra problems? // arXiv preprint arXiv:2206.10576, 2022. https://doi.org/10.48550/arXiv.2206.10576.
  25. Date P., Potok T. Adiabatic quantum linear regression // Sci. Rep. 2021. V. 11. № 1. https://doi.org/10.1038/s41598-021-01445-6.
  26. Souza A.M., Martins E.O., Roditi I., Sa N., Sarthour R.S., Oliveira I.S. An application of quantum annealing computing to seismic inversion // Front. Phys. 2022. V. 9. https://doi.org/10.3389/fphy.2021.748285.
  27. Meli N.K., Mannel F., Lellmann J. An Iterative Quantum Approach for Transformation Estimation from Point Sets // 2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), New Orleans, LA, USA. 2022. P 519-527. https://doi.org/10.1109/CVPR52688.2022.00061.
  28. Conley R., Choi D., Medwig G., Mroczko E., Wan D., Castillo P., Yu K. Quantum optimization algorithm for solving elliptic boundary value problems on D-Wave quantum annealing device // Proc. SPIE 12446, Quantum Computing, Communication, and Simulation III, 124460A. 2023. https://doi.org/10.1117/12.2649076.
  29. Lewis M., Glover F. Quadratic Unconstrained Binary Optimization Problem Preprocessing: Theory and Empirical Analysis // Networks. 2017. V. 70. № 2. P. 79-97. https://doi.org/10.1002/net.21751.
  30. Ширяев А.Н. Вероятность. М.: Наука, 1980.
  31. Lagarias J.C. Euler’s constant: Euler’s work and modern developments // Bull. Am. Math. Soc. 2013. V. 50. № 4. P. 527-628. https://doi.org/10.1090/s0273-0979-2013-01423-x.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

© Российская академия наук, 2024

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».