⚛️ quantum physics

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

The paper introduces SamBa-GQW, a non-variational quantum algorithm that utilizes an offline classical sampling protocol to guide a continuous-time quantum walk toward high-quality solutions for combinatorial optimization problems, demonstrating performance comparable to variational methods like QAOA without requiring classical optimizers.

Original authors: Ugo Nzongani, Dylan Laplace Mermoud, Giuseppe Di Molfetta, Andrea Simonetto

Published 2026-10-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ugo Nzongani, Dylan Laplace Mermoud, Giuseppe Di Molfetta, Andrea Simonetto

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of computing, some problems are like trying to find a single specific grain of sand on a beach that doubles in size every time you take a step. These are known as combinatorial optimization problems, where a computer must choose the best arrangement from a vast number of possibilities, such as the most efficient route for a delivery truck or the best mix of stocks for an investment portfolio. As the number of choices grows, the time required for a traditional computer to check every option increases so rapidly that even the most powerful supercomputers would take longer than the age of the universe to find the answer. Quantum computers, which use the strange rules of physics to process information, offer a potential shortcut. They can explore many possibilities at once, but current machines are noisy and imperfect, often requiring complex tuning to work correctly. This has led researchers to search for new ways to guide these quantum machines without needing a human to constantly adjust the settings.

A team of researchers has introduced a new method called SamBa-GQW, a technique designed to solve these difficult puzzles without relying on a classical computer to fine-tune the quantum process. Instead of using a trial-and-error approach that requires a classical computer to constantly check and correct the quantum machine's settings, this new method uses a smart, one-time preparation step. The researchers first take a small, manageable sample of the problem's landscape on a regular computer. This sample acts like a map, revealing the general shape of the solution space and where the best answers are likely to hide. Using this map, they set the quantum machine to run a specific journey, a continuous flow of probability that naturally drifts toward the best solutions. The quantum machine then follows this pre-calculated path, guided by a changing rhythm that slows down as it gets closer to the optimal answer, effectively letting the physics of the system do the heavy lifting.

The researchers tested this approach on a variety of challenging problems, including finding the best way to split a network into two groups, selecting the largest group of items that do not conflict with each other, and optimizing investment portfolios. They simulated the process on problems involving up to thirty variables, a size that is significant for current quantum technology. The results showed that the method consistently found high-quality solutions, often landing on the best possible answer or one very close to it. In many cases, the quantum state became highly focused on the correct solution, meaning that if you measured the computer's output, you would have a very good chance of getting the right answer. The team found that they only needed to sample a tiny fraction of the total possible decisions to build an effective map, proving that a full, exhaustive search of the problem's landscape was not necessary to guide the quantum walker.

When compared to other popular quantum methods, such as the Quantum Approximate Optimization Algorithm (QAOA), the new technique held its own, though with a different trade-off. The standard QAOA method relies on a classical computer to repeatedly adjust the quantum machine's settings to find the best performance, a process that can be slow and prone to getting stuck in local traps. In contrast, the SamBa-GQW method requires no such tuning; it runs a single, pre-determined sequence. While the standard method often achieves slightly better results when given very deep, complex circuits, the new method performs just as well when the circuit depth is allowed to grow large enough. This suggests that for future, more powerful quantum computers, this non-variational approach could be a highly efficient way to solve complex problems, bypassing the need for the difficult and time-consuming optimization loops that currently limit many quantum algorithms.

The study also explored how the method behaves with different types of problems and varying levels of difficulty. For some problems, like maximizing the number of satisfied conditions in a logic puzzle, the method found the best solutions with high probability even for complex versions of the problem. For others, like the traveling salesperson problem, the time required for the quantum machine to complete its journey depended on the specific distances between cities, but the method still successfully guided the system to the optimal route. The researchers observed that the quantum state would naturally concentrate on the best answers, shrinking from a broad spread of possibilities into a tight cluster around the solution. This localization happened quickly in many cases, suggesting that the method is robust and reliable.

Ultimately, this work presents a promising alternative for the next generation of quantum computing. By replacing the need for a classical optimizer with a simple, offline sampling protocol, the researchers have created a streamlined path for quantum machines to solve hard problems. The method does not claim to solve these problems instantly or with a magic trick; rather, it offers a practical, mathematically grounded way to navigate the vast search spaces of combinatorial optimization. As quantum hardware continues to improve, moving beyond the current noisy era, this approach could become a standard tool for tackling the large-scale logistical and scientific challenges that currently overwhelm classical computers. The findings suggest that with the right guidance, quantum systems can efficiently find their way to the best solutions without needing a human hand to steer them at every step.

Technical Summary: Sampled-Based Guided Quantum Walk (SamBa–GQW)

Problem Statement

The paper addresses the challenge of solving binary combinatorial optimization problems of arbitrary degree on quantum computers. These problems, often NP-hard, involve finding a binary vector $x^* \in \{0, 1\}^n$ that minimizes a cost function $C(x)$ , potentially subject to constraints. While quantum computers offer a natural way to explore exponential solution spaces with linear qubit resources, current Noisy Intermediate-Scale Quantum (NISQ) devices struggle with variational algorithms like the Quantum Approximate Optimization Algorithm (QAOA). These variational approaches rely on a classical optimizer to tune parameters, a process often plagued by "barren plateaus" (vanishing gradients) and exponential scaling in the number of required circuit evaluations as problem size increases.

Existing non-variational alternatives, such as the Guided Quantum Walk (GQW), attempt to avoid classical optimization by using a time-dependent hopping rate derived from the problem Hamiltonian's spectrum. However, calculating the exact spectrum is exponentially costly, and previous approximations using parametric curves (e.g., Bézier curves) still required classical optimization, leading to exponential scaling in the number of iterations.

Methodology: SamBa–GQW

The authors propose SamBa–GQW (Sampled-Based Guided Quantum Walk), a non-variational quantum algorithm that eliminates the need for a classical optimizer during the quantum execution phase. The algorithm operates in two distinct stages:

1. Classical Offline Sampling Protocol

Instead of computing the exact spectrum of the cost Hamiltonian $H_C$ (which requires $2^n$ evaluations) or optimizing a parametric curve, the algorithm employs an efficient sampling protocol.

Sampling: The protocol randomly selects a polynomial number of candidate states, $q = \text{poly}(n)$ (empirically found to be sufficient at $q=n^2$ ), from the $2^n$ solution space.
Gap Estimation: For each sampled state, the algorithm computes the energy gaps between the state and its neighbors (defined by the mixer connectivity, e.g., the hypercube for an X-mixer).
Spectrum Approximation: It calculates the average of the largest energy gaps for specific energy levels. This provides an approximation of the function $\Gamma(E)$ , which relates the hopping rate to the energy gap, as derived in previous GQW literature.
Schedule Construction: Using these sampled points, the algorithm constructs a continuous, smooth, time-dependent hopping rate $\Gamma(t)$ via interpolation. This schedule is designed to balance the mixing Hamiltonian $H_M$ and the cost Hamiltonian $H_C$ , maximizing the transfer of amplitude from high-energy to low-energy states.

2. Quantum Online Execution

Once the hopping schedule $\Gamma(t)$ is determined, the quantum computer executes a continuous-time quantum walk (CTQW) guided by this schedule.

Hamiltonian: The system evolves under the time-dependent Hamiltonian $H(t) = \Gamma(t)H_M + H_C$ .
Circuit Implementation: To run this on gate-based quantum computers, the authors propose a two-level discretization strategy. The time interval is first divided into periods where the hopping rate is linearly interpolated. These periods are further subdivided to apply Trotter-Suzuki decomposition. This results in a quantum circuit with alternating layers of cost ( $U_C$ ) and mixer ( $U_M$ ) unitaries, similar in structure to QAOA but with parameters determined a priori rather than optimized.
Measurement: The algorithm performs a single set of measurements in the computational basis. The best solution found among the measurements is selected.

Key Contributions

Non-Variational Framework: SamBa–GQW is a "one-shot" algorithm that does not require a classical optimizer to tune quantum parameters, thereby avoiding barren plateaus and the exponential scaling associated with variational loops.
Efficient Sampling: The paper demonstrates that a polynomial number of samples ( $q \approx n^2$ ) is sufficient to approximate the optimal hopping rate, avoiding the exponential cost of exact spectral analysis.
Circuit Implementation: The authors provide a concrete method to discretize the continuous-time evolution into a gate-based quantum circuit with polynomial depth relative to the number of qubits and samples.
Broad Applicability: The algorithm is tested on a diverse set of problems, including:
- Quadratic Problems: MaxCut, Maximum Independent Set (MIS), and Portfolio Optimization (with constraints).
- Higher-Order Problems: Low Autocorrelation Binary Sequences (LABS), MAX-k-SAT, and a quartic reformulation of the Traveling Salesperson Problem (TSP).

Results

The authors present numerical simulations (both Hamiltonian and circuit-based) for problem sizes up to $n=30$ qubits.

Performance: SamBa–GQW consistently finds high-quality approximate solutions. For many instances, the probability of measuring the optimal solution or solutions within the top 5% of rankings is very high.
Comparison with GQW: When compared to the variational GQW (which uses a classical optimizer to fit a Bézier curve), SamBa–GQW achieves comparable approximation ratios. Crucially, SamBa–GQW reduces the execution time by at least one order of magnitude because it avoids the iterative classical optimization loop.
Comparison with QAOA:
- Shallow Circuits (NISQ regime): When restricted to shallow circuit depths (e.g., $p < 20$ ), QAOA generally outperforms SamBa–GQW, particularly for weighted MaxCut and MIS. This is attributed to QAOA's ability to use classical optimization to fine-tune parameters for specific problem instances.
- Deep Circuits (Beyond NISQ): When the circuit depth is allowed to increase (up to $p \approx 100$ or more), SamBa–GQW performs "in par" with QAOA in terms of approximation ratios. The paper notes that SamBa–GQW requires deeper circuits to reach its peak performance compared to QAOA's shallow saturation, but it achieves similar final quality without the variational overhead.
Scalability: The algorithm scales reasonably well with the number of qubits. For problems like MaxCut and MIS, the approximation ratio remains high even as $n$ increases, provided the sampling parameter $q$ and circuit depth are adjusted appropriately.

Significance and Claims

The paper positions SamBa–GQW as a promising heuristic for tackling combinatorial optimization problems beyond the NISQ regime. Its primary significance lies in offering a non-variational alternative that is robust against barren plateaus and does not suffer from the exponential scaling of classical optimization iterations found in variational methods.

The authors claim that while SamBa–GQW may require deeper circuits than QAOA to achieve optimal results, it offers a favorable trade-off between solution quality and computational cost by eliminating the need for repeated quantum circuit evaluations during a classical optimization loop. The algorithm is presented not as a polynomial-time solution to NP-hard problems, but as a method where polynomial resources (in terms of sampling and circuit depth) may be sufficient to effectively guide the search toward high-quality states. The work suggests that as quantum hardware improves and deeper circuits become feasible, SamBa–GQW could serve as a competitive, scalable approach for large-scale combinatorial optimization.