Combinatorial optimization permeates science and engineering, from route planning to resource allocation. Many such problems are equivalent to finding the ground state of the Ising model, which belongs to the NP-hard class. Classical heuristics like simulated annealing often get stuck in local minima due to rugged energy landscapes. Quantum approaches, particularly QAOA, promise speedups but suffer from trainability issues and limited circuit depth on current hardware. This work joins recent efforts to harness noisy intermediate-scale quantum (NISQ) processors for practical tasks: neighboring studies explore quantum algorithms, error correction, and quantum information. What sets this work apart is its specific hybrid scheme, where the quantum part only proposes 'jumps' between basins, while all fine-grained optimization remains classical.
The Qjump algorithm works iteratively. Given a current solution (a bit string), the quantum circuit generates a set of candidates by 'jumping' into neighboring energy basins. The circuit consists of an encoding layer, L layers of cost and mixer operators (inspired by QAOA), and measurements. The circuit parameters are not optimized variationally; instead, they are taken from precomputed values for deep QAOA, which avoids the barren plateau problem. After quantum sampling, the classical computer performs local search (greedy descent) for each candidate and selects the best solution. Experiments were run on a 104-qubit superconducting processor with a median two-qubit gate fidelity of 99.5%. For comparison, a highly optimized classical simulated annealer (SA) ran on a single-core CPU.
On 20 specially selected hard Ising instances with 104 qubits, Qjump found the global minimum 2.23 times more often than SA in a fixed time. Moreover, the quantum sampler showed a higher probability of landing in the global minimum region compared to classical random sampling with the same fraction of flipped bits. Based on assumptions about future quantum hardware (sampling rate 0.4 MHz, fast control via FPGA), the time-to-solution (TTS) was estimated: Qjump outperformed SA on a single-core CPU by a factor of 2.34. For smaller systems (60 and 84 qubits), the advantage was smaller (0.98 and 1.56 times, respectively), indicating improvement with problem size. QAOA with local search proved nearly ineffective for these problems.
This work shows that hybrid schemes, where the quantum processor is used only for 'jumps' across the landscape and the classical part handles precise optimization, can be a practical route to quantum advantage on NISQ devices. Unlike neighboring works that focus on purely quantum algorithms or error correction, this proposes a concrete division of labor that reduces demands on circuit depth and qubit quality. This extends the applicability of existing quantum processors to optimization problems today.
The natural next step is scaling to thousands of qubits and improving qubit metrics. It is also interesting to explore optimal sampler parameters and circuit structure, as well as the impact of gate and measurement noise. Potentially, Qjump could be combined with other classical heuristics (tabu search, branch and bound) or used as a module in an ensemble of algorithms.
The results could impact fields that require solving NP-hard problems: logistics, finance, materials science, and machine learning. The hybrid approach could be adapted to other quantum platforms.
Conduct experiments on systems with thousands of qubits and improved gate fidelities. Investigate the scaling of Qjump's time complexity with problem size.
In quantum computing, an open question remains whether noisy intermediate-scale quantum devices can provide a practical advantage over classical algorithms for optimization problems. This work contributes by demonstrating a concrete hybrid algorithm and experimental evidence of advantage on 104 qubits, but a rigorous proof of quantum speedup requires further research.
This section is addressed to the author of the paper and their colleagues. Neighbouring works were found by meaning-based search across our archive, not by word overlap. We do not review: we show the field around the work.
What the work does
The paper proposes a hybrid quantum-classical algorithm called Qjump, which uses a quantum sampler to generate candidates across different energy basins and a classical local search for descent. On a 104-qubit processor, the algorithm found the global minimum more often than classical simulated annealing and showed an extrapolated speedup of 2.34 times in time-to-solution.
Where its strength is
The strong point is the specific hybrid scheme, where the quantum part handles only the 'jumps' between basins, while fine-grained optimization remains classical. This avoids the pitfalls of variational optimization and allows the use of fixed circuit parameters.
Where it could go next
Worth trying
Nearby works in our archive
The archive is sparse around this work: the closest review is only 0.58, against a usual 0.64. It looks like few have drilled nearby.
To select hard problem instances, the researchers generated 4000 random configurations of couplings and fields, then kept only the 20 on which classical simulated annealing performed worst. This ensures a fair comparison: the quantum algorithm was tested on the hardest cases.