REDUCING DISCRETE OPTIMIZATION PROBLEMS TO THE QUBO FORM

Cover Page

Cite item

Full Text

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

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.

About the authors

A. M Semenov

Russian Quantum Center; "Cloud Quantum Technologies" LLC

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

S. R Usmanov

Russian Quantum Center; "Cloud Quantum Technologies" LLC

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

A. K Fedorov

Russian Quantum Center; "Cloud Quantum Technologies" LLC

Email: akf@rqc.ru
Moscow; Moscow

References

  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).

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2025 Russian Academy of Sciences

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

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») на элемент с текстом «Принять и продолжить».