Sampled-based Guided Quantum Walk Solves Binary Combinatorial Optimization Problems Without Classical Optimization

Combinatorial optimization problems, which involve finding the best solution from a vast number of possibilities, challenge both classical and quantum computers. Ugo Nzongani, Dylan Laplace Mermoud, Giuseppe Di Molfetta, and colleagues, from Aix-Marseille Université, ENSTA, and the CNRS, present a new quantum algorithm, SamBa-GQW, that tackles these problems without relying on classical optimization techniques. The team’s approach employs a quantum walk, a quantum analogue of a random walk, guided by information gleaned from a classical sampling process, allowing the algorithm to efficiently explore potential solutions. This innovative method demonstrates strong performance on a range of complex problems, including MaxCut, portfolio optimization, and even a quantum reformulation of the travelling salesperson problem, finding high-quality approximate solutions for systems of considerable size and offering a promising new direction in quantum algorithm design.

QAOA Variations and Adaptive Optimisation Techniques

This work presents a comprehensive overview of research into quantum computing, optimization, and graph algorithms. Investigations focus on the Quantum Approximate Optimization Algorithm (QAOA) and its numerous variations, alongside explorations of related techniques and applications. Research encompasses improvements to QAOA, its application to diverse problems like Max Independent Set and the Travelling Salesman Problem, and theoretical analyses of its performance and limitations. Quantum Imaginary Time Evolution (QITE) is also explored as a method for enhancing optimization performance. Quantum Annealing and Variational Quantum Circuits (VQCs) provide broader contexts for these investigations.

A significant focus lies on graph problems, including Max Independent Set, Max K-SAT, and graph coloring, with particular attention given to the challenges posed by hard instances and the potential for quantum speedups. Combinatorial optimization, portfolio optimization, and constraint satisfaction problems are also actively investigated, extending to practical applications like smart charging of electric vehicles. Theoretical foundations are strengthened through complexity theory, random graph theory, and the application of mathematical tools like Lie groups and Lie algebras. Researchers utilize and develop tools such as Qiskit, Quantikz, SamBa-GQW, and QOBLib to facilitate their work and benchmark algorithms.

Key themes emerge, including the identification of hard optimization problems, the pursuit of quantum advantage, and the challenge of scaling quantum algorithms to larger problem sizes. Error mitigation and correction, alongside hybrid quantum-classical approaches, are crucial areas of investigation. Foundational results like Cook’s Theorem and the Erdos-Renyi Random Graph Model provide essential theoretical frameworks for these studies.

SamBa-GQW Algorithm for Combinatorial Optimization

Scientists have developed SamBa-GQW, a novel quantum algorithm for solving binary combinatorial optimization problems without relying on classical optimization techniques. The algorithm employs a continuous-time quantum walk, where a quantum walker explores potential solutions represented as a graph, seeking configurations that minimize the problem’s cost function. A key innovation lies in an offline classical sampling protocol that analyzes the problem’s Hamiltonian, providing information to guide the walker’s movement via a time-dependent hopping rate. This approach differs from variational methods like QAOA, circumventing challenges associated with barren plateaus and scaling issues.

The team implemented a method to determine the optimal hopping rate for the quantum walker through classical sampling, performed entirely before the quantum walk begins. This sampling protocol analyzes the Hamiltonian spectrum, providing crucial data to shape the walker’s trajectory and direct it towards high-quality solutions. Researchers translated the continuous-time quantum walk into a gate-based quantum circuit, ensuring its implementability on current and near-future quantum computers, with a circuit depth that scales polynomially with the number of qubits. Experiments employed this circuit to solve several quadratic and higher-order polynomial problems, including MaxCut, maximum independent set, portfolio optimization, LABS, MAX-SAT, and a quartic reformulation of the travelling salesperson problem.

The study demonstrates that SamBa-GQW achieves high-quality approximate solutions on problems with up to a significant number of qubits, by sampling among possible decisions. Results show the algorithm consistently delivers solutions comparable to, and often exceeding the performance of, other guided quantum walks and QAOA. The team achieved a significant reduction in execution time, at least one order of magnitude faster than the original GQW, by eliminating the need for a classical optimizer and streamlining the process with the pre-calculated hopping rate. The worst-case time complexity of SamBa-GQW in the continuous-time regime is inverse.

Quantum Walk Algorithm Solves Binary Optimization Problems

Scientists have developed SamBa-GQW, a novel quantum algorithm for solving complex binary optimization problems without relying on classical optimization techniques. The algorithm utilizes a continuous-time quantum walk, where a ‘walker’ explores potential solutions represented as a graph, seeking configurations that minimize a defined cost function. A key innovation lies in an offline classical sampling protocol that analyzes the problem’s Hamiltonian, providing information to guide the quantum walker towards high-quality solutions through a time-dependent hopping rate. Experiments demonstrate that SamBa-GQW successfully finds approximate solutions for problems involving up to a significant number of qubits by sampling among possible decisions.

The algorithm’s performance is notably strong when tested on quadratic problems like MaxCut and portfolio optimization, as well as more complex polynomial problems including LABS, MAX-SAT, and a quartic reformulation of the travelling salesperson problem. Results show the algorithm consistently delivers high-quality approximate solutions, often achieving optimal results with high probability. The team achieved a significant reduction in execution time, at least one order of magnitude faster, compared to the original Guided Quantum Walk (GQW) and Quantum Approximate Optimization Algorithm (QAOA). The worst-case time complexity of SamBa-GQW is inversely proportional to the spectral gap of the problem Hamiltonian, mirroring characteristics of adiabatic evolutions, yet simulations reveal short evolution times with respect to the number of qubits for most problems.

Furthermore, researchers observed that the quantum walk does not require full evolution to achieve well-localized state vectors, allowing for premature measurement and efficient recovery of optimal solutions. This breakthrough delivers a quantum circuit implementation with a polynomial depth relative to the number of qubits, enabling the continuous-time quantum walk to be implemented on gate-based quantum computers. The team’s work overcomes scaling problems associated with GQW by introducing the offline classical sampling protocol, avoiding the need for classical optimizers and potential barren plateaus. Measurements confirm that the algorithm’s performance is competitive with, and often surpasses, existing methods in solving complex optimization challenges.

SamBa-GQW Solves Complex Optimization Problems

Researchers have developed a new quantum algorithm, SamBa-GQW, designed to tackle complex binary combinatorial optimization problems without relying on classical optimization techniques. The algorithm utilizes a continuous-time quantum walk, navigating the potential solution space to identify configurations that minimize the problem’s cost function. A key innovation lies in an offline classical sampling procedure which provides information about the problem’s underlying structure, guiding the quantum walk with a time-dependent hopping rate to efficiently locate high-quality solutions. Demonstrated on a range of challenging problems including MaxCut, portfolio optimization, and the travelling salesperson problem, SamBa-GQW successfully finds approximate solutions for systems containing up to a significant number of qubits by sampling among possible decisions.

Results indicate the algorithm performs favorably when compared to other guided quantum walks and the Quantum Approximate Optimization Algorithm (QAOA), suggesting its potential for scaling to address larger, more complex problems. Notably, the algorithm’s parameters exhibit similarities to those obtained with QAOA as the number of layers increases, hinting at a possible connection between the two methods. The authors acknowledge that the accuracy of the classical sampling procedure impacts the algorithm’s performance, and further investigation into optimizing this step is warranted.