CONVERGENCE RATE OF ALGORITHM FOR SOLVING LINEAR EQUATIONS BY QUANTUM ANNEALING

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

Abstract

Various iterative algorithms for solving the linear equation ax = b using a quantum computer operating on the principle of quantum annealing are studied. Assuming that the result produced by the computer is described by the Boltzmann distribution, conditions under which these algorithms converge are obtained and an estimate of their convergence rate is provided. Application of this approach for algorithms that use an infinite number of qubits and a small number of qubits is considered.

About the authors

S. B Tikhomirov

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

Email: setgey.tikhomirov@gmail.com
Rio de Janeiro, Brazil

V. S Shalgin

St. Petersburg State University

Email: st086496@student.spbu.ru
St. Petersburg, Russia

References

  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.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2024 Russian Academy of Sciences