Sampled-Based Guided Quantum Walk: Non-variational quantum algorithm for combinatorial optimization

arXiv:2509.15138 · quant-ph · Submitted 2025-09-18 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: Today's paper: "Sampled-Based Guided Quantum Walk".

Mira: SamBa–GQW introduces a novel, non-variational quantum algorithm for solving binary combinatorial optimization problems of arbitrary degree without relying on any classical optimizer.

Kai: First, who's behind it and why it matters.

Title and authors: Kai: We just touched on the core idea, and now I want to go into more detail about what the paper actually proposes as a solution for these optimization problems.

Mira: You’re right; we need to really unpack how this algorithm specifically addresses the structure of binary combinatorial problems defined by x* in arg min x in one n C(x) subject to constraints.

Lev: Can you explain what the continuous-time quantum walk is doing in this context, and why it’s a better fit than discrete time methods we've seen before?

Kai: The paper frames the problem as a continuous-time quantum walk on the solution space represented as a graph, where vertices are binary decision states and the walker explores this space to find vertices that minimize the cost function C(x).

Mira: That continuous-time aspect is important because it allows for smoother transitions between states, which aligns with how we think about adiabatic evolution in optimization problems, like those explored in "Adiabatic evolution for optimization".

Lev: So, if the walker moves continuously along edges defined by the graph structure, what is it looking for specifically? Is it minimizing a local cost or something more global?

Kai: The walker explores the solution space to find vertices that minimize the cost function of the optimization problem, which directly relates to finding an approximate solution x such that C(x) - C(x*) at most epsilon.

Mira: It’s not just about local minimization; by exploring this graph structure, it’s inherently guided toward regions of low cost, and the guidance comes from the hopping rate derived from the spectrum.

Lev: And this guidance is what makes it different from methods that just randomly walk or use a fixed mixer Hamiltonian; how does this spectral information translate into better search behavior?

Kai: The key novelty is using an offline classical sampling protocol to get information about the spectrum of the problem Hamiltonian, which then informs a time-dependent hopping rate.

Mira: So the sampling step acts as a pre-computation phase that gives us a map of where in the energy landscape we should spend our quantum evolution time, which is quite sophisticated.

Lev: That sounds like it’s trying to steer the continuous evolution toward regions where low-energy states are more likely to be measured, which is what they aim for in finding good solutions.

Kai: Precisely; by approximating the optimal hopping rate function (E) = C (E) squared, they create a time-dependent evolution that favors transitions that lead toward the optimal solution.

Mira: That's where it connects back to "Quantum walk optimization algorithm (QWOA)" mentioned earlier, but instead of relying on enumerating all feasible solutions classically, this method uses spectral information for guidance.

Lev: So the paper is essentially proposing a hybrid approach: classical sampling provides the 'where to go,' and the quantum walk performs the actual search guided by that classical knowledge.

Kai: That’s a good way to put it; it’s leveraging classical insight to optimize the quantum dynamics, which is a hallmark of this SamBa–GQW algorithm.

The paper's summary: Mira: Now that we understand the mechanism, let's talk about what they claim are the specific improvements over existing methods in terms of performance and scaling.

Kai: The authors highlight that a major improvement is overcoming the exponential scaling issues associated with classical optimization in previous guided quantum walk schemes.

Mira: That’s significant because traditional methods often require exponentially hard classical steps to set up the search space, and this method seems to bypass that bottleneck entirely by using polynomial-time sampling for guidance.

Lev: I wonder if that polynomial dependency on the sampling complexity actually holds up when we move from small n to larger, more realistic problem sizes we might encounter in error-corrected hardware.

Kai: They claim that the complexity of the sampling protocol depends on the mixer connectivity, which they select to be polynomial with respect to n, unlike GQW which requires optimizing six parameters classically.

Mira: So, by making the classical pre-processing complexity dependent only polynomially on n through clever connectivity choices, they avoid having to optimize a large number of classical parameters that would otherwise blow up exponentially.

Lev: That makes sense for hardware readiness because it keeps the preparation phase manageable, but I still need assurance that the approximation error introduced by sampling doesn't become too large when we have to run long evolution times.

Kai: They provide an example where they show high success probability on LABS for n=twenty qubits using quadratic sampling (q = n squared states), achieving P zeropsi T about zero point five.

Mira: That empirical evidence, especially reaching that success probability with just n squared samples, strongly suggests the guiding mechanism is robust enough for practical applications on near-term devices.

Lev: If we want to push this further, I think the next step would be seeing how these results translate when we consider the noise models inherent in real NISQ hardware and whether that P zeropsi T holds up under realistic decoherence.

Kai: The paper also suggests that this method can be applied to problems where the exact spectral information of the Hamiltonian is computationally prohibitive, which is a big win for harder optimization tasks.

Mira: That means we are not restricted to problems where we have an easy way to calculate the full spectrum; we can tackle those where finding that spectrum itself would be computationally intractable.

Lev: So, in summary, the improvement isn't just speed; it’s a fundamental shift in how we manage the dependency on classical information for quantum dynamics setup.

Kai: The core idea is substituting exponential classical search with polynomial classical sampling to define the quantum evolution path.

The paper's improvements: Mira: To wrap up, we’ve seen how "Sampled-Based Guided Quantum Walk: Non-variational quantum algorithm for combinatorial optimization" offers a way to tackle these complex problems without relying on a classical optimizer for the core dynamics.

Kai: It seems like the main contribution of this work is successfully replacing that classical optimization with an efficient sampling protocol that approximates the hopping rate function derived from the Hamiltonian spectrum.

Lev: For my perspective as someone focused on error correction, I see a method that keeps the complexity polynomial in terms of problem size for both classical and quantum setup phases, which is a huge plus for building reliable systems.

Mira: Indeed, when we look at the overall picture, this SamBa–GQW framework provides a consistent pathway to finding high-quality approximate solutions across various benchmarks like MaxCut and MIS.

Kai: So the implication is that we might be able to apply this type of non-variational quantum algorithm effectively for solving NP-hard problems at scale on current and near-term hardware.

Lev: The main caveat I see is that we still have to deal with implementing that time-dependent evolution robustly, so the engineering challenge remains in managing the noise during those long evolution times.

Mira: Ultimately, the paper demonstrates a solid method for using classical information strategically to guide quantum walks effectively toward promising regions of solution space.

Kai: That’s our summary of SamBa–GQW; it’s a non-variational approach that leverages polynomial classical pre-processing to achieve high-quality optimization results on combinatorial problems.

Lev: We're looking forward to seeing how this concept matures when it moves from theory into more complex, noisy quantum hardware.

Conclusion: Kai: So we've walked through the details of "Sampled-Based Guided Quantum Walk: Non-variational quantum algorithm for combinatorial optimization," and it turns out this method uses offline classical sampling to guide a continuous-time quantum walk without needing a classical optimizer for the main dynamics.

Mira: Exactly, and what really stands out is how they use that spectral information to define a time-dependent hopping rate, which is the core mechanism underpinning the entire approach.

Lev: From my point of view on hardware constraints, it’s interesting because they manage to keep the quantum circuit depth polynomial in n, which means we aren't immediately looking at an impossible execution time for larger problem instances.

Kai: That polynomial depth is a big deal for experimentalists, as it makes gate-based implementation much more feasible compared to methods that might require exponential scaling in circuit size.

Mira: I agree, and the way they approximate the optimal hopping rate using those discrete energy gaps via interpolation shows a solid theoretical grounding for why that specific sampling protocol works so well.

Lev: If we were to run this on current hardware, I'd be watching how sensitive that continuous evolution is to noise because of all those nested discretizations they used to handle the time intervals.

Kai: That sensitivity is definitely something we need to monitor closely when we start looking at actual cooling and measurement outcomes for these walks.

Mira: The overall implication here is that we can tackle combinatorial problems with arbitrary degree that were previously intractable because the classical setup required an exponential search space.

Lev: That’s a huge conceptual win for error correction research; if you can guide the quantum walk efficiently, it simplifies the problem of finding a good solution state.

Kai: It really shows how hybrid methods, where classical pre-processing informs quantum evolution, can be very effective at bridging the gap between theory and practical application.

Mira: So this paper provides a concrete recipe for using spectral analysis to engineer more reliable quantum search algorithms for optimization tasks.

Lev: It gives us a new target for error correction research—focusing on maintaining coherence during the time-dependent evolution dictated by that sampled hopping rate.

Kai: We're definitely keeping an eye on this, and I think it sets a high bar for what we expect from these non-variational quantum algorithms in the near term.

Mira: And that brings us to our next topic, where we'll discuss how this approach compares to other methods like QAOA and why it might be preferred for certain problem structures.

Aix-Marseille Université · Unité de Mathématiques Appliquées, ENSTA, Institut Polytechnique de Paris CEDRIC, Conservatoire National des Arts et Métiers

quant-ph

Submitted: 2025-09-18

Updated: 2026-10-03

Code: https://github.com/ugo-nzongani/SamBa-GQW

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 87/100

The gist: SamBa–GQW introduces a novel, non-variational quantum algorithm for solving binary combinatorial optimization problems of arbitrary degree without relying on any classical optimizer.

Key concepts

Continuous-Time Quantum Walk (QW)
This is a quantum evolution where the state moves continuously across a graph representing the problem's solution space. Vertices are binary decisions, and the walk's speed is controlled by a time-dependent hopping rate derived from the problem's energy gaps.
Offline Classical Sampling Protocol
This is an efficient classical step used to approximate the complex function that determines how fast the quantum walk hops between states. Instead of calculating every possible energy gap exactly, this protocol samples key points to estimate these gaps, making the process computationally feasible.
Hopping Rate Function Γ(E)
The hopping rate is a crucial parameter in continuous quantum walks that dictates the evolution speed. In this algorithm, it is approximated by sampling energy gaps from the problem's Hamiltonian spectrum. This approximation allows for a smooth, continuous evolution schedule without needing to solve the full spectral problem classically.
Non-Variational Algorithm
This means the algorithm does not rely on iterative classical optimization loops or variational parameter tuning, which often suffer from scaling problems. Instead, it uses a direct quantum evolution guided by pre-calculated classical information (the sampling) to find solutions directly.

Terminology

Summary

SamBa–GQW introduces a novel, non-variational quantum algorithm for solving binary combinatorial optimization problems of arbitrary degree without relying on any classical optimizer. This method overcomes scaling issues and potential barren plateaus associated with existing variational approaches by employing an offline classical sampling protocol to guide a continuous-time quantum walk using a time-dependent hopping rate derived from the problem's Hamiltonian spectrum.

How it works

The core of SamBa–GQW is based on a continuous-time quantum walk (QW) on the solution space represented as a graph, where vertices correspond to binary decision states. The algorithm operates in two main parts: an offline classical sampling protocol and an online quantum walk evolution. The key novelty lies in using an offline classical sampling protocol that gives information about the spectrum of the problem Hamiltonian to approximate the optimal hopping rate function, which is derived from balancing energy gaps between vertices.

Classical Offline Part: Sampling

The first step involves performing a classical offline part, specifically an efficient sampling protocol (Sampler, Alg. 2), to approximate Eq. (7), which defines the hopping rate as a function of energy: Γ(E) = ⟨∆C⟩(E)2. Instead of computing the exact spectrum, this protocol computes candidate points and stores the largest gap with its associated energy, leading to an approximation that is computationally advantageous. The complexity of this sampling is polynomial, specifically Csampling ≤ q Nneigh Ccost, where for the X-mixer connectivity, it remains polynomial.

Hopping Rate Determination

Once the sampled energy gaps are obtained, the next step is to build the annealing schedule Γ(t) using a method described in Algorithm 3 (Builder). This involves interpolation between discrete energy gaps to create a continuous and smooth hopping rate as a function of energy. The optimal evolution time T is then determined by maximizing the probability of measuring low-energy states, leading to an approximation: T = π/2√2 X(jk)∈ES Γ−1jk.

Online Quantum Part: Continuous Quantum Walk

The second part is the quantum online part, which runs the continuous-time evolution of Eq. (6), defined by a time-dependent hopping rate. The evolution is described by the time-dependent Schrödinger equation, and for gate-based implementation, this is discretized using a technique involving two nested discretization of the time interval to maintain manageable circuit depth. This leads to a unitary evolution expressed as: U(t) = lim→∞ e− i p Λ([0,t])HM e − i p tHC, where the time intervals are dissected based on the sampled energy levels.

Performance and Comparison

SamBa–GQW is demonstrated on several problems, including MaxCut, Maximum Independent Set (MIS), portfolio optimization, and higher-order polynomial problems like LABS and MAX-k-SAT. Empirically, it finds high quality approximate solutions on problems up to a size of n = 20 qubits by only sampling n2 states among 2n possible decisions. The algorithm compares very well also to other guided quantum walks and QAOA, reducing execution time by at least one order of magnitude compared to the original GQW, while avoiding the exponential scaling issues associated with classical optimization in that scheme. For instance, on LABS for n=20 qubits, it achieves a high success probability of measuring optimal solutions with P0[ψT] ≈ 0.5 when using quadratic sampling (q = n2 states).

Circuit Implementation and Scaling

The quantum circuit implementation of SamBa–GQW is polynomial in depth with respect to the number of qubits, scaling as d(n, p) ≤ dSP (n) + n2τq (dM(n) + dC(n)) when q = n2 samples are used. This depth depends on the number of samples and the annealing time corresponding to the lowest energy level sampled. The overall advantage is that the complexity of the sampling protocol depends on the mixer connectivity, which we select to be polynomial with the number of qubits n, unlike GQW which requires optimizing six parameters classically, leading to a significant running time gain in practice.

Conclusion

SamBa–GQW is proposed as a non-variational quantum algorithm that overcomes scaling problems by replacing classical optimization with an efficient sampling protocol for approximating the hopping rate. It consistently finds high-quality approximate solutions across various combinatorial optimization benchmarks, showing favorable performance compared to both Guided Quantum Walks and QAOA, making it promising for solving combinatorial problems at scale.

The gist: SamBa–GQW introduces a novel, non-variational quantum algorithm for solving binary combinatorial optimization problems of arbitrary degree without relying on any classical optimizer.

Improvements for AI systems

Based on the provided scientific paper, here are specific ways to improve AI systems and what those improved systems could achieve:

  1. Improve Combinatorial Optimization in NISQ Devices via SamBa–GQW:

  2. Enhance Robustness Against Barren Plateaus in Variational Quantum Algorithms (VQAs):

  3. Develop Scalable Quantum Circuits for Continuous-Time Walks:

  4. Achieve Faster Convergence for Optimization Problems using Non-Variational Methods:

5.1 SamBa–GQW enables solving complex combinatorial optimization problems (like MaxCut, MIS, and Portfolio Optimization) on quantum hardware by utilizing a continuous-time quantum walk guided by an offline classical sampling protocol. This allows the algorithm to find high-quality approximate solutions with high probability in a short evolution time.

5.2 The improved system can:

  • Solve NP-hard problems (QUBOs, MAX-k-SAT, TSP) on near-term devices (NISQ).

  • Achieve state localization around the optimal solution distribution rapidly, even for hard instances like Unit Disk Graphs or complex portfolio optimization datasets.

  • Demonstrate a significant speedup over classical post-processing methods by achieving high success probabilities (e.g., up to 0.983 for weighted MaxCut).

5.3 By replacing the classical optimizer in guided quantum walks with an efficient polynomial-time sampling protocol, the system avoids the exponential scaling issues and barren plateaus associated with traditional Variational Quantum Algorithms (VQAs) like QAOA, leading to more reliable performance on larger problem sizes.

5.4 The improved system can:

  • Be applied to problems where exact spectral information of the Hamiltonian is computationally prohibitive (scaling exponentially in qubit count).

  • Offer a scalable approach where the classical pre-processing time grows only polynomially with the problem size, significantly outperforming existing methods that require exponential classical optimization steps.

5.5 The quantum circuit implementation of SamBa–GQW can be designed to be polynomial in depth with respect to the number of qubits, making it directly executable on gate-based quantum computers (like those available today).

5.6 This system can:

  • Be used for tasks requiring high precision in state preparation by implementing sophisticated time-dependent evolution via nested discretization and Trotterization schemes tailored to the sampled hopping rate.

  • Provide a consistent performance advantage over QAOA across various problem instances (MaxCut, MIS, Portfolio Optimization) without relying on classical optimization for the core quantum walk dynamics.

5.7 The system can be used for problems where constraints are present (e.g., Maximum Independent Set with weight constraints or portfolio optimization with asset limits) by using appropriate mixer Hamiltonians (like XY-mixers) that restrict the walker to feasible solution spaces defined by the constraint set.

Abstract

We introduce SamBa-GQW, a novel quantum algorithm for solving binary combinatorial optimization problems of arbitrary degree with no use of any classical optimizer. The algorithm is based on a continuous-time quantum walk on the solution space represented as a graph. The walker explores the solution space to find its way to vertices that minimize the cost function of the optimization problem. The key novelty of our algorithm is an offline classical sampling protocol that gives information about the spectrum of the problem Hamiltonian. Then, the extracted information is used to guide the walker to high quality solutions via a quantum walk with a time-dependent hopping rate. We investigate the performance of SamBa-GQW on several quadratic problems, namely MaxCut, maximum independent set, portfolio optimization, and higher-order polynomial problems such as LABS, MAX- k-SAT and a quartic reformulation of the travelling salesperson problem. We empirically demonstrate that SamBa-GQW finds high quality approximate solutions on problems up to a size of n=30 qubits by only sampling poly(n) states among 2 n possible decisions. Furthermore, SamBa-GQW compares in par with classically optimized variational approaches, such as the variational guided quantum walk and QAOA (the latter when run on deep circuits). This places Samba-GQW as a promising heuristic to tackle combinatorial problems beyond the NISQ regime.

Sources

Related papers