Qubit-efficient quantum local search for combinatorial optimization
M. Podobrii, V. Kuzmin, V. Voloshinov, M. Veshchezerova, M. R. Perelshtein · 2025
Read Qubit-efficient quantum local search for combinatorial optimization by M. Podobrii, V. Kuzmin, V. Voloshinov, M. Veshchezerova, M. R. Perelshtein (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-02245.txt.
Introduction
Mikhail Podobrii and co-authors present a quantum version of local search, the routine inside many solvers that keeps swapping a solution for a better neighbor. Classical machines can only check a small set of neighbors at each step, because the cost grows with the set. Their quantum algorithm squeezes the neighborhood choice into few qubits: a set of size l needs only enough qubits to count to l. That frugality suits today's small quantum machines.
Spending more qubits buys a bigger neighborhood and, with it, better answers, a trade-off the authors highlight for near-term hardware. In simulations, their method solved the largest graph coloring problem tackled by a quantum approach. Graph coloring, assigning labels so linked points never match, stands in for many scheduling and routing tasks. The team argues their design gives small quantum devices a shot at large, hard problems.
Catalog record
| CREATOR | M. Podobrii, V. Kuzmin, V. Voloshinov, M. Veshchezerova, M. R. Perelshtein |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 66 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-02245
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Qubit-efficient quantum local search for combinatorial optimization M. Podobrii, V. Kuzmin, V. Voloshinov, M. Veshchezerova, M. R. Perelshtein Abstract 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 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 ⌈ log 2 l ⌉ \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. 1 Introduction Figure 1: Scheme of our approach. We reduce the initial (discrete) Ising ground state problem to the optimization of a continuous auxiliary function \mathcal{E}(\vec{q}) (Eq. ( 9 )). The auxiliary function is defined by choosing an initial state \vec{Z}^{(0)} and groups \{G_{k}\} , where G_{k}\subseteq[0{:}n{-}1] . To find approximate local minima of the auxiliary function, we employ a variational quantum algorithm, enabling function evaluation even when l is classically intractable. This is achieved by mapping the probability distribution \vec{P} generated from quantum state measurements to the auxiliary variables \vec{q} using Eq. ( 11 ). After optimization of the quantum circuit, we estimate \vec{p}=(1-\vec{q})/2 , which represents the probabilities of group flips. Using these probabilities, we sample several most probable \vec{z} , where z_{k}=-1 if the corresponding group G_{k} is flipped and 1 otherwise. We decode \vec{z} into the original variables \vec{Z} via Eq. ( 6 ) and choose the best \vec{Z} with the minimal energy. Then, we restart the procedure from the beginning taking \vec{Z}^{(0)}=\vec{Z}^{\mathrm{best}} . We perform several such rounds until the solution is not improved. Local search is one of the most fundamental heuristic algorithms successfully applied to many challenging combinatorial optimization problems. The so-called r -local search (or r -flip) algorithm [ 1 ] starts from a candidate solution and iteratively explores a chosen neighborhood, of size l , of solutions that differ by at most r bits (or Hamming distance r ). The process stops when all the neighbors are not better than the current solution. Many metaheuristics, such as simulated annealing [ 2 ] , tabu search [ 3 ] , and memetic algorithms [ 4 ] , are based on local search [ 5 ] . Increasing the size of the neighborhood by increasing r can yield better solutions at the cost of an exponentially growing runtime that follows the binomial coefficient l\sim C_{n}^{r}\sim O(n^{r}) where n is the total number of variables. Therefore, the parameter r typically must be chosen as small. In this work, we address the aforementioned problem by introducing a Variational Quantum Algorithm (VQA) that uses a parametrized quantum-circuit ansatz of sufficient depth to implement the r -local search heuristic. The distinct feature of our approach is that the number, N_{q} , of employed qubits adapts to the chosen parameter r , ranging from N_{q}=\lceil\log_{2}n\rceil when r=1 to N_{q}=n when r=n . In contrast to the previously proposed quantum local search method [ 6 , 7 ] , which reduces the number of qubits by breaking the problem into smaller subproblems, our approach addresses the entire problem directly and achieves qubit reduction through amplitude encoding. That is, for a chosen value of r , our method encodes the probabilities of flipping groups of bits, each involving no more than r bits, into the square norm of the quantum state’s amplitudes. Then, the parameters of the variational circuit are tuned so that the probabilities from the resulting quantum state minimize a designed non-linear objective function whose local minima coincide with the local minima of r -local search. We emphasize that, as demonstrated in our work, the required number of shots for estimating this cost function doesn’t explicitly grow with r , allowing our quantum algorithm to handle a classically intractable number of neighbors. Finally, the optimized quantum state decodes into a set of multi-bit flips that are applied to the initial candidate to generate the resulting solution. The scheme of our algorithm is depicted in Fig. 1 . Previously, qubit-efficient approaches that require only N_{q}=\lceil\log_{2}n\rceil qubits for solving n -variable optimization problems have been proposed in Refs. [ 8 , 9 , 10 , 11 , 12 ] . However, such an efficient encoding automatically implies that the complexity of classically simulating the involved quantum circuit scales only polynomially with the problem size, limiting the opportunities for achieving quantum advantage on actual quantum hardware. Moreover, in our work, we show that the performance of the method proposed in Refs. [ 8 , 9 ] , referred to as minimal encoding, is limited due to the presence of multiple local minima in the underlying cost function. While these functions can somehow be optimized with global optimization routines such as differential evolution [ 13 ] , gradient-based methods will inevitably fall into local minima. In contrast, while increasing neighborhood size l by employing a growing number, N_{q} , of qubits, our approach allows us to gradually eliminate these local minima. This leads to higher-quality solutions when the quantum variational ansatz is expressive enough. At the opposite limit, r=n , our algorithm requires N_{q}=n qubits. In this case, all solutions are neighbors to each other, and all the local minima in the cost function are caused by the finite-depth circuit ansatz. This limit is similar to algorithms that use the so-called complete encoding [ 8 ] , such as VQE [ 14 , 15 ] and QAOA [ 16 , 17 ] , where the number of qubits is equal to the number of classical variables. In this work, we show that at this limit, our method gives compatible results to VQE with complete encoding, see Appendix A . Thus, our method intends to fill the gap between the minimal and complete encodings. In this regime, the involved quantum circuit might not be efficiently simulatable, potentially offering a quantum advantage. At the same time, for a given problem, our method allows the required number of qubits to be adjusted depending on the quantum device at hand. Some other approaches [ 18 , 19 ] reduce the qubit number by only a constant factor. Reducing the number of qubits in a low-depth variational circuit could also improve the quality of solutions since the cost function of shallow circuits that have many qubits can suffer from severe under-parametrization, see Appendix A . Other methods with an adaptive number of qubits were previously proposed in Refs. [ 8 , 20 ] . However, Ref. [ 8 ] shows the advantage only on sparse problems, while for dense problems, it demonstrates even worse results