EUVIMEDEUVIMED entdecken
Crossref

REDUCING DISCRETE OPTIMIZATION PROBLEMS TO THE QUBO FORM

A.M. Semenov

Проблемы передачи информации / Problems of Information Transmission · 2025

DOI: 10.7868/s3034583925020041 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Проблемы передачи информации / Problems of Information Transmission, 2025. Verfasst von A.M. Semenov.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

APA

Semenov, A. (2025). REDUCING DISCRETE OPTIMIZATION PROBLEMS TO THE QUBO FORM. Проблемы передачи информации / Problems of Information Transmission. https://doi.org/10.7868/s3034583925020041

Vancouver

Semenov A. REDUCING DISCRETE OPTIMIZATION PROBLEMS TO THE QUBO FORM. Проблемы передачи информации / Problems of Information Transmission. 2025. doi:10.7868/s3034583925020041

BibTeX
@article{Semenov2025,
  author = {Semenov, A.M.},
  title = {REDUCING DISCRETE OPTIMIZATION PROBLEMS TO THE QUBO FORM},
  journal = {Проблемы передачи информации / Problems of Information Transmission},
  year = {2025},
  doi = {10.7868/s3034583925020041}
}
Kostenlos starten →