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

Обложка

Цитировать

Полный текст

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

Аннотация

Рассмотрены различные итеративные алгоритмы решения линейного уравнения 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