REDUCING DISCRETE OPTIMIZATION PROBLEMS TO THE QUBO FORM

Мұқаба

Дәйексөз келтіру

Толық мәтін

Ашық рұқсат Ашық рұқсат
Рұқсат жабық Рұқсат берілді
Рұқсат жабық Рұқсат ақылы немесе тек жазылушылар үшін

Аннотация

Practical discrete optimization problems often contain multidimensional arrays of variables with linear constraints, which complicates their conversion to QUBO (quadratic unconstrained binary optimization) form. The article proposes a systematic approach to transforming such problems, which includes three key steps: the transition from a multidimensional representation of variables to a one-dimensional one using the Kronecker product of matrices, the reduction of mixed variables to binary ones, and the introduction of linear constraints into the objective function through quadratic penalties. Explicit computational formulas are obtained for each stage, simplifying their software implementation. The developed method is illustrated with examples from graph theory and combinatorial optimization, including classical formulations, confirming its universality. The results of the article allow standardizing the process of adapting problems for solving on quantum annealing algorithms (e.g., D-Wave) and classical QUBO solvers.

Авторлар туралы

A. Semenov

Russian Quantum Center; "Cloud Quantum Technologies" LLC

Email: a.semenov@rqc.ru
Moscow; Moscow

S. Usmanov

Russian Quantum Center; "Cloud Quantum Technologies" LLC

Email: s.usmanov@rqc.ru
Moscow; Moscow

A. Fedorov

Russian Quantum Center; "Cloud Quantum Technologies" LLC

Email: akf@rqc.ru
Moscow; Moscow

Әдебиет тізімі

  1. Castillo-Salazar J.A., Landa-Silva D., Qu R. Workforce Scheduling and Routing Problems: Literature Survey and Computational Study // Ann. Oper. Res. 2014. V. 239. №1. P. 39–67. https://doi.org/10.1007/s10479-014-1687-2
  2. Cook S.A. An Overview of Computational Complexity // Comm. ACM. 1983. V. 26. № 6. P. 400–408. https://doi.org/10.1145/358141.358144
  3. Arora R.K. Optimization: Algorithms and Applications. New York: Chapman & Hall/CRC, 2015. https://doi.org/10.1201/b18469
  4. Tian Y., Zhu W., Zhang X., Jin Y. A Practical Tutorial on Solving Optimization Problems via PlatEMO // Neurocomputing. 2023. V. 518. P. 190–205. https://doi.org/10.1016/j.neucom.2022.10.075
  5. Fedorov A.K., Gisin N., Beloussov S.M., Lvovsky A.I. Quantum Computing at the Quantum Advantage Threshold: A Down-to-Business Review. https://arXiv.org/abs/2203.17181 [quant-ph], 2022.
  6. Tiunov E.S., Ulanov A.E., Lvovsky A.I. Annealing by Simulating the Coherent Ising Machine // Opt. Express. 2019. V. 27. № 7. P. 10288–10295. https://doi.org/10.1364/OE.27.010288
  7. Farhi E., Goldstone J., Gutmann S., Sipser M. Quantum Computation by Adiabatic Evolution. https://arXiv.org/abs/quant-ph/0001106, 2000.
  8. Das A., Chakrabarti B.K. Colloquium: Quantum Annealing and Analog Quantum Computation // Rev. Mod. Phys. 2008. V. 80. № 3. P. 1061–1081. https://doi.org/10.1103/RevModPhys.80.1061
  9. Albash T., Lidar D.A. Adiabatic Quantum Computation // Rev. Mod. Phys. 2018. V. 90. № 1. P. 015002 (64 pp.). https://doi.org/10.1103/RevModPhys.90.015002
  10. McCollum J., Krauss T. QUBO Formulations of the Longest Path Problem // Theor. Comput. Sci. 2021. V. 863. P. 86–101. https://doi.org/10.1016/j.tcs.2021.02.021
  11. Papalitsas C., Andronikos T., Giannakis K., Theocharopoulou G., Fanarioti S. A QUBO Model for the Traveling Salesman Problem with Time Windows // Algorithms. 2019. V. 12. № 11. P. 224 (21 pp.). https://doi.org/10.3390/a12110224
  12. Alidaee B., Kochenberger G., Lewis K., Wang H. A New Approach for Modeling and Solving Set Packing Problems // European J. Oper. Res. 2008. V. 186. № 2. P. 504–512. https://doi.org/10.1016/j.ejor.2006.12.068
  13. Bomze I.M., Budinich M., Pardalos P.M., Pelillo M. The Maximum Clique Problem // Handbook of Combinatorial Optimization: Supplement Volume A. Boston, MA: Springer, 1999. P. 1–74. https://doi.org/10.1007/978-1-4757-3023-4_1
  14. Date P., Arthur D., Pusey-Nazzaro L. QUBO Formulations for Training Machine Learning Models // Sci. Rep. 2021. V. 11. P. 10029 (10 pp.). https://doi.org/10.1038/s41598-021-89461-4
  15. Farhi E., Neven H. Classification with Quantum Neural Networks on Near Term Processors. https://arXiv.org/abs/1802.06002 [quant-ph], 2018.
  16. Boev A.S., Usmanov S.R., Semenov A.M., Ushakova M.M., Salahov G.V., Mastiukova A.S., Kiktenko E.O., Fedorov A.K. Quantum-Inspired Optimization for Wavelength Assignment // Front. Phys. 2022. V. 10. P. 1092065 (11 pp.). https://doi.org/10.3389/fphy.2022.1092065
  17. Seker O., Bodur M., Pouya H. Routing and Wavelength Assignment with Protection: A Quadratic Unconstrained Binary Optimization Approach Enabled by Digital Annealer Technology // IISE Trans. 2024. V. 56. № 2. P. 156–171. https://doi.org/10.1080/24725854.2023.2193835
  18. Rahman M.T., Han S., Tadayon N., Valaee S. Ising Model Formulation of Outlier Rejection, with Application in WiFi Based Positioning // Proc. 2019 IEEE Int. Conf. on Acoustics, Speech and Signal Processing (ICASSP 2019). Brighton, UK. May 12–17, 2019. P. 4405–4409. https://doi.org/10.1109/ICASSP.2019.8683807
  19. Phillipson F., Bhatia H.S. Portfolio Optimisation Using the D-Wave Quantum Annealer // Proc. 21st Int. Conf. on Computational Science (ICCS 2021). Krakow, Poland. June 16–18, 2021. Part VI. Lect. Notes Comp. Sci. V. 12747. Berlin, Heidelberg: Springer-Verlag, 2021. P. 45–59. https://doi.org/10.1007/978-3-030-77980-1_4
  20. Mugel S., Kuchkovsky C., S´anchez E., Fern´andez-Lorenzo S., Luis-Hita J., Lizaso E., Or´us R. Dynamic Portfolio Optimization with Real Datasets Using Quantum Processors and Quantum-Inspired Tensor Networks // Phys. Rev. Res. 2022. V. 4. № 1. P. 013006 (12 pp.). https://doi.org/10.1103/PhysRevResearch.4.013006
  21. Ratke D. List of QUBO Formulations, 2021. https://blog.xa0.de/post/List-of-QUBOformulations/ (accessed Feb. 20, 2025).
  22. Leap User Documentation Handbook. D-Wave Systems Inc., 2025. https://docs.dwavequantum.com/en/latest/index.html (accessed Mar. 20, 2025).
  23. Kochenberger G., Hao J.-K., Glover F., Lewis M., L¨u Z., Wang H., Wang Y. The Unconstrained Binary Quadratic Programming Problem: A Survey // J. Comb. Optim. 2014. V. 28. № 1. P. 58–81. https://doi.org/10.1007/s10878-014-9734-0
  24. Lucas A. Ising Formulations of Many NP Problems // Front. Phys. 2014. V. 2. P. 5 (15 pp.). https://doi.org/10.3389/fphy.2014.00005
  25. Glover F., Kochenberger G., Hennig R., Du Y. Quantum Bridge Analytics I: A Tutorial on Formulating and Using QUBO Models // Ann. Oper. Res. 2022. V. 314. № 1. P. 141–183. https://doi.org/10.1007/s10479-022-04634-2
  26. Asghari M., Fathollahi-Fard A.M., Mirzapour Al-e-hashem S.M.J., Dulebenets M.A. Transformation and Linearization Techniques in Optimization: A State-of-the-Art Survey // Mathematics. 2022. V. 10. № 2. P. 283 (26 pp.). https://doi.org/10.3390/math100202830
  27. Castro E.R., Martins E.O., Sarthour R.S., Souza A.M., Oliveira I.S. Improving the Convergence of an Iterative Algorithm for Solving Arbitrary Linear Equation Systems Using Classical or Quantum Binary Optimization // Front. Phys. 2024. V. 12. P. 1443977 (12 pp.). https://doi.org/10.3389/fphy.2024.1443977
  28. Veszeli M.T., Vattay G. Mean Field Approximation for Solving QUBO Problems // PLoS ONE. 2021. V. 17. № 8. P. e0273709 (12 pp.). https://doi.org/10.1371/journal.pone.0273709
  29. Kanao T., Goto H. Simulated Bifurcation Assisted by Thermal Fluctuation // Commun. Phys. 2022. V. 5. P. 153 (7 pp.). https://doi.org/10.1038/s42005-022-00929-9
  30. Drubin M. Kronecker Product Factorization of the FFT Matrix // IEEE Trans. Comput. 1971. V. 20. № 5. P. 590–593. https://doi.org/10.1109/T-C.1971.223306
  31. Frolkoviˇc P. Numerical Recipes: The Art of Scientific Computing // Acta Appl. Math. 1990. V. 19. № 3. P. 297–299. https://doi.org/10.1007/BF01321860
  32. Langville A.N., Stewart W.J. The Kronecker Product and Stochastic Automata Networks // J. Comput. Appl. Math. 2004. V. 167. № 2. P. 429–447. https://doi.org/10.1016/j.cam.2003.10.010
  33. Guo C., Berkhahn F. Entity Embeddings of Categorical Variables. https://arXiv.org/abs/1604.06737 [cs.LG], 2016.
  34. Pardalos P.M., Xue J. The Maximum Clique Problem // J. Glob. Optim. 1994. V. 4. № 3. P. 301–328. https://doi.org/10.1007/BF01098364
  35. Bondy J.A., Murty U.S.R. Graph Theory. New York: Springer, 2008.
  36. Loiola E.M., de Abreu N.M.M., Boaventura-Netto P.O., Hahn P., Querido T. A Survey of the Quadratic Assignment Problem // European J. Oper. Res. 2007. V. 176. №2. P. 657–690. https://doi.org/10.1016/j.ejor.2005.09.032
  37. Kellerer H., Pferschy U., Pisinger D. Knapsack Problems. Berlin, Heidelberg: Springer, 2004. https://doi.org/10.1007/978-3-540-24777-7
  38. Semenov A.M., Usmanov S.R., Fedorov A.K. Technique for Transforming Discrete Optimization Problems into QUBO Form // Probl. Inf. Transm. 2025. V. 61. № 2 (to appear).

Қосымша файлдар

Қосымша файлдар
Әрекет
1. JATS XML
Жүктеу

© Russian Academy of Sciences, 2025