EUVIMEDEUVIMED entdecken
Open Access · CC BY-NC 4.0

Qubit‐Efficient Quantum Local Search for Combinatorial Optimization

Mikhail Podobrii, Viacheslav Kuzmin, Vladimir Voloshinov, Margarita Veshchezerova, Michael R. Perelshtein

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

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →