Variational Product States Achieve Superior Optimization on 50000-Variable Problems

Combinatorial optimisation problems, which involve finding the best solution from a vast number of possibilities, pose a significant challenge for both classical and emerging quantum computers. Guillermo Preisser, Conor Mc Keever, and Michael Lubasch, all from Quantinuum, now demonstrate a new approach using variational methods based on product and matrix product states. Their work introduces algorithms inspired by the iterated local search technique, effectively harnessing randomness to improve performance on complex problems, and benchmarks these methods on maximum cut problems involving up to 50,000 variables. The results show these new algorithms outperform existing classical and variational methods, representing a substantial advance in tackling computationally demanding optimisation challenges.

The study pioneers a technique that combines variational energy minimization with respect to a quantum annealing Hamiltonian and embeds the approach within the iterated local search framework. This resulted in quantum-inspired ILS algorithms, which researchers benchmarked on maximum cut problems involving up to 50,000 variables, demonstrating superior performance compared to traditional methods, classical ILS, and other variational quantum-inspired solvers. The team engineered a parallel alternative to QiILS, termed Quantum-inspired iterative global search, which employs global gradient updates to enable efficient parallelization. Experiments utilizing GPU-based parallel computing demonstrated that this approach exhibits a runtime nearly independent of problem size, achieving a significant speedup for large instances. Performance was evaluated using the approximation ratio, a measure of solution quality.

QiILS Outperforms Algorithms on MaxCut Problems

Scientists achieved significant advancements in solving complex combinatorial optimization problems using novel variational methods based on product state and matrix product state ansatzes. The research team developed algorithms inspired by the iterated local search metaheuristic, demonstrating improved performance on maximum cut problems with up to 50,000 variables. Experiments reveal that these new approaches outperform traditional methods, classical iterated local search, and other variational solvers. Performance comparisons on a benchmark graph demonstrated that the developed algorithm consistently achieves superior results. The team measured performance using the approximation ratio, a metric for evaluating solution quality.

Variational Algorithms Excel at Maximum Cut Problems

This research presents new variational methods for tackling complex combinatorial optimization problems, specifically employing product state and matrix product state techniques within an iterated local search framework. By combining these approaches, scientists have developed algorithms that demonstrably outperform traditional methods and classical local search when tested on maximum cut problems involving up to 50,000 variables. The team investigated the impact of key parameters on algorithm performance, finding that careful selection of these parameters can maximize the rate of improvement. The study highlights the potential of combining limited quantum entanglement with randomness to effectively navigate the solution space of challenging optimization problems.