Ugo Nzongani and colleagues have developed SamBa-GQW, a new quantum algorithm that efficiently tackles complex optimization problems. The researchers demonstrate solutions for problems reaching a size of 30 qubits by sampling only a polynomial number of states among the 2n possibilities, a marked gain in efficiency. SamBa-GQW successfully addresses challenges including MaxCut, portfolio optimization and a quartic reformulation of the travelling salesperson problem. This work positions the algorithm as a promising heuristic for tackling combinatorial problems beyond current quantum computer limitations.
SamBa-GQW Algorithm for Binary Combinatorial Optimization
SamBa-GQW, a new quantum algorithm, demonstrates effective problem-solving capabilities up to a scale of 30 qubits, a notable achievement given the limitations of current quantum hardware. The core innovation of SamBa-GQW lies in its use of a continuous-time quantum walk guided by information extracted from a classical sampling protocol. This protocol analyzes the spectrum of the problem’s Hamiltonian, providing insights that direct the quantum walk towards high-quality solutions.
Unlike many contemporary approaches, SamBa-GQW operates without relying on a classical optimizer during its quantum execution phase, making it a truly non-variational algorithm. This design choice aims to mitigate potential issues associated with hybrid quantum-classical optimization loops, which can sometimes hinder performance in noisy intermediate-scale quantum (NISQ) devices. The researchers empirically validated SamBa-GQW’s performance by comparing it to established techniques such as the variational guided quantum walk and the Quantum Approximate Optimization Algorithm (QAOA).
In their tests, SamBa-GQW achieved comparable results, particularly when QAOA was implemented with deep circuits. This suggests that SamBa-GQW presents a viable alternative for tackling combinatorial problems, potentially extending the reach of quantum optimization beyond the constraints of the NISQ era. This work is detailed in a recent publication in Quantum, where they outline the algorithm’s methodology and present their experimental findings. The efficiency of SamBa-GQW stems from its ability to intelligently explore the solution space, focusing computational resources on promising regions.
The classical sampling phase provides a roadmap for the quantum walk, allowing it to navigate the complex landscape of possible solutions more effectively. This guided approach contrasts with many other quantum algorithms that rely on random exploration or require extensive parameter tuning. The algorithm’s design prioritizes scalability, aiming to maintain performance as the size of the problem increases.
Further emphasizing the algorithm’s versatility, the researchers tested its performance on problems of varying complexity, from quadratic unconstrained binary optimization (QUBO) instances to higher-order polynomial formulations. This broad applicability emphasises the potential of SamBa-GQW to address a wide range of real-world optimization challenges. The team’s implementation is available on GitHub, facilitating further research and development within the quantum computing community.
The code repository allows others to reproduce their results and explore potential modifications and extensions to the algorithm. While challenges remain in scaling quantum algorithms to solve truly intractable problems, SamBa-GQW represents a step forward in developing practical and efficient quantum optimization techniques.
Offline Sampling Guides Quantum Walk Hopping Rates
The algorithm achieves solutions for optimization problems involving up to 30 qubits, a scale where many quantum algorithms struggle to demonstrate a practical advantage over classical methods. This capability stems from a novel approach to guiding a quantum walk, a process where the algorithm explores potential solutions by hopping between states in a defined solution space. Unlike many existing quantum algorithms, SamBa-GQW relies on pre-calculated data, an offline sampling protocol, to shape the walk’s trajectory.
This pre-processing step analyzes the problem’s Hamiltonian, a mathematical description of its energy landscape, to identify promising paths for the quantum walker. The efficiency of SamBa-GQW is further emphasised by its requirement of only sampling a polynomial number of states, where the number of qubits is represented by n, among the exponentially large 2n possible configurations.
Scaling SamBa-GQW to 30 Qubits with Poly(n) Sampling
This performance is enabled by a unique sampling strategy that drastically reduces the computational burden of exploring potential solutions. Instead of evaluating all 2n possibilities, the algorithm requires sampling only a polynomial number of states, a significant efficiency gain for larger problem sizes. This versatility stems from the algorithm’s ability to handle problems with quartic reformulations, expanding its applicability beyond simpler quadratic formulations.
This guidance is achieved through a time-dependent hopping rate within the quantum walk, effectively focusing the search on promising areas of the solution space. The team’s work builds upon established theoretical foundations, referencing the work of Childs et al. on Trotter error theory and Verchère et al. on optimizing variational circuits for higher-order binary optimization.
The researchers also highlight the work of Boulebnane and Montanaro, “Solving boolean satisfiability problems with the quantum approximate optimization algorithm”, PRX Quantum, 5 (3): 030348, September 2024, as relevant to the broader context of quantum optimization algorithms. Prado, Rattighieri, Arruda, Franco, de Oliveira and Fanchini, “Portfolio optimization via FALQON variants: warm starting, XY mixing, and circuit depth reduction”, Quantum Information Processing 25 8, 275 (2026), provides further context on optimization techniques relevant to this field.
SamBa-GQW Compares to Variational and QAOA Approaches
This efficiency stems from the algorithm’s core design, a continuous-time quantum walk exploring the solution space as a graph, and contrasts sharply with methods requiring examination of all 2n possibilities. The reduced sampling requirement represents a significant algorithmic advantage when tackling complex combinatorial problems. Specifically, SamBa-GQW demonstrated parity with classically optimized variational approaches, such as the variational guided quantum walk and QAOA, when the latter is run on deep circuits, across a range of benchmark problems, including MaxCut, maximum independent set and portfolio optimization.
This suggests its potential as a viable heuristic for problems beyond the current limitations of near-term quantum devices. This breadth of application distinguishes it from algorithms tailored to specific problem structures. The researchers also explored the algorithm’s performance in scenarios relevant to financial modeling, specifically portfolio optimization, a field where finding optimal solutions is computationally intensive.
The algorithm’s performance suggests it may offer a pathway towards addressing complex optimization challenges that are currently intractable for classical computers. The ability to find high-quality approximate solutions on problems up to 30 qubits, using only a polynomial number of samples, positions SamBa-GQW as a promising candidate for tackling combinatorial problems beyond the NISQ regime.
See today’s quantum computing news on Quantum Zeitgeist for the latest breakthroughs in qubits, hardware, algorithms, and industry deals.
