Везде

RAS Nano & ITПроблемы передачи информации Problems of Information Transmission

  • ISSN (Print) 0555-2923
  • ISSN (Online) 3034-5839

REDUCING DISCRETE OPTIMIZATION PROBLEMS TO THE QUBO FORM

You can
PII
S3034583925020041-1
DOI
10.7868/S3034583925020041
Publication type
Article
Status
Published
Authors
A.M. Semenov
  • Affiliation:
    Russian Quantum Center
    "Cloud Quantum Technologies" LLC
S.R. Usmanov
  • Affiliation:
    Russian Quantum Center
    "Cloud Quantum Technologies" LLC
A.K. Fedorov
  • Affiliation:
    Russian Quantum Center
    "Cloud Quantum Technologies" LLC
Volume/ Edition
Volume 61 / Issue number 2
Pages
50-68
Abstract
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.
Keywords
квадратичная бинарная оптимизация без ограничений () модель Изинга адиабатические квантовые вычисления комбинаторная оптимизация
Date of publication
18.08.2025
Year of publication
2025
Number of purchasers
0
Views
30

References

  1. 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. 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. 3. Arora R.K. Optimization: Algorithms and Applications. New York: Chapman & Hall/CRC, 2015. https://doi.org/10.1201/b18469
  4. 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. 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. 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. 7. Farhi E., Goldstone J., Gutmann S., Sipser M. Quantum Computation by Adiabatic Evolution. https://arXiv.org/abs/quant-ph/0001106, 2000.
  8. 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. 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. 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. 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. 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. 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. 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. 15. Farhi E., Neven H. Classification with Quantum Neural Networks on Near Term Processors. https://arXiv.org/abs/1802.06002 [quant-ph], 2018.
  16. 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. 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. 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. 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. 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. 21. Ratke D. List of QUBO Formulations, 2021. https://blog.xa0.de/post/List-of-QUBOformulations/ (accessed Feb. 20, 2025).
  22. 22. Leap User Documentation Handbook. D-Wave Systems Inc., 2025. https://docs.dwavequantum.com/en/latest/index.html (accessed Mar. 20, 2025).
  23. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 33. Guo C., Berkhahn F. Entity Embeddings of Categorical Variables. https://arXiv.org/abs/1604.06737 [cs.LG], 2016.
  34. 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. 35. Bondy J.A., Murty U.S.R. Graph Theory. New York: Springer, 2008.
  36. 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. 37. Kellerer H., Pferschy U., Pisinger D. Knapsack Problems. Berlin, Heidelberg: Springer, 2004. https://doi.org/10.1007/978-3-540-24777-7
  38. 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).
QR
Translate

Индексирование

Scopus

Scopus

Scopus

Crossref

Scopus

Higher Attestation Commission

At the Ministry of Education and Science of the Russian Federation

Scopus

Scientific Electronic Library