ПРИВЕДЕНИЕ ЗАДАЧ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ К ФОРМЕ QUBO

Обложка

Цитировать

Полный текст

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

Аннотация

Практические задачи дискретной оптимизации часто содержат многомерные массивы переменных с линейными ограничениями, что осложняет их приведение к форме QUBO (квадратичной бинарной оптимизации без ограничений). В статье предложен систематический подход к преобразованию таких задач, включающий три ключевых этапа: переход от многомерного представления переменных к одномерному с использованием произведения Кронекера матриц, приведение смешанных переменных к бинарным и введение линейных ограничений в целевую функцию через квадратичные штрафы. Для каждого этапа получены явные вычислительные формулы, упрощающие их программную реализацию. Разработанный метод проиллюстрирован на примерах задач теории графов и комбинаторной оптимизации, включая классические постановки, что подтверждает его универсальность. Результаты статьи позволяют стандартизировать процесс адаптации задач для решения на квантовых алгоритмах отжига (например, D-Wave) и классических QUBO-решателях.

Об авторах

А. М Семенов

Российский квантовый центр (ООО "МЦКТ"); ООО "Облачные квантовые технологии"

Email: a.semenov@rqc.ru
Москва; Москва

С. Р Усманов

Российский квантовый центр (ООО "МЦКТ"); ООО "Облачные квантовые технологии"

Email: s.usmanov@rqc.ru
Москва; Москва

А. К Федоров

Российский квантовый центр (ООО "МЦКТ"); ООО "Облачные квантовые технологии"

Email: akf@rqc.ru
Москва; Москва

Список литературы

  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
Скачать

© Российская академия наук, 2025