Qubit‐Efficient Quantum Local Search for Combinatorial Optimization
Advanced Quantum Technologies · 2026-03 · 9 (3)
DOI: 10.1002/qute.202500438 ↗Kurz gefasst
Fachartikel in der Zeitschrift Advanced Quantum Technologies, online erschienen am 04.03.2026. Verfasst von Mikhail Podobrii und 4 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 46 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC 4.0).
Abstract (Originalsprache)
An essential component of many sophisticated metaheuristics for solving combinatorial optimization problems is some variation of a local search routine that iteratively searches for a better solution within a chosen set of immediate neighbors. The size of this set is limited due to the computational costs required to run the method on classical processing units. We present a qubit‐efficient variational quantum algorithm that implements a quantum version of local search with only qubits and, therefore, can potentially work with classically intractable neighborhood sizes. Increasing the amount of quantum resources employed in the algorithm allows for a larger neighborhood size, improving the quality of obtained solutions. This trade‐off is crucial for present and near‐term quantum devices characterized by a limited number of logical qubits. Numerically simulating our algorithm, we successfully solved the largest graph coloring instance that was tackled by a quantum method. This achievement highlights the algorithm's potential for solving large‐scale combinatorial optimization problems on near‐term quantum devices.
Zitieren
APA
Podobrii, M., Kuzmin, V., Voloshinov, V., Veshchezerova, M., & Perelshtein, M. R. (2026). Qubit‐Efficient Quantum Local Search for Combinatorial Optimization. Advanced Quantum Technologies, 9(3). https://doi.org/10.1002/qute.202500438
Vancouver
Podobrii M, Kuzmin V, Voloshinov V, Veshchezerova M, Perelshtein MR. Qubit‐Efficient Quantum Local Search for Combinatorial Optimization. Advanced Quantum Technologies. 2026;9(3). doi:10.1002/qute.202500438
BibTeX
@article{Podobrii2026,
author = {Podobrii, Mikhail and Kuzmin, Viacheslav and Voloshinov, Vladimir and Veshchezerova, Margarita and Perelshtein, Michael R.},
title = {Qubit‐Efficient Quantum Local Search for Combinatorial Optimization},
journal = {Advanced Quantum Technologies},
year = {2026},
volume = {9},
number = {3},
doi = {10.1002/qute.202500438}
}
EUVIMED