Qubit-efficient quantum local search for combinatorial optimization
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915137134264320 |
|---|---|
| author | Podobrii, M. Kuzmin, V. Voloshinov, V. Veshchezerova, M. Perelshtein, M. R. |
| author_facet | Podobrii, M. Kuzmin, V. Voloshinov, V. Veshchezerova, M. Perelshtein, M. R. |
| contents | 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 $l$ 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 $\lceil \log_2 l \rceil$ qubits and, therefore, can potentially work with classically intractable neighborhood sizes when realized on near-term quantum computers. 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_02245 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Qubit-efficient quantum local search for combinatorial optimization Podobrii, M. Kuzmin, V. Voloshinov, V. Veshchezerova, M. Perelshtein, M. R. Quantum Physics 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 $l$ 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 $\lceil \log_2 l \rceil$ qubits and, therefore, can potentially work with classically intractable neighborhood sizes when realized on near-term quantum computers. 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. |
| title | Qubit-efficient quantum local search for combinatorial optimization |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2502.02245 |