Quantum Algorithm Finds Perfect Solutions to Complex Problems Beyond Classical Reach

Combinatorial optimisation presents a significant challenge for modern computation, with many real-world problems quickly exceeding the capabilities of classical algorithms. Kate V. Marshall, Daniel J. Egger, and Michael Garn, alongside their colleagues at IBM Quantum and The Hartree Centre, demonstrate a novel approach utilising quantum-enhanced Markov chain Monte Carlo (QeMCMC) to tackle these complex problems. Their research combines on-device sampling with established techniques like warm-starting and parallel tempering, offering a pathway towards solving intractable instances of combinatorial optimisation with near-term quantum hardware. The team empirically validates their algorithm by successfully recovering global optima for Maximum Independent Set (MIS) problems with up to 117 decision variables on a 117-qubit quantum processor, and provides initial evidence suggesting a potential scaling advantage over classical methods for this practically relevant problem, which impacts fields ranging from financial modelling to molecular biology.

This work demonstrates a novel approach to combinatorial optimization by integrating quantum-enhanced Markov chain Monte Carlo (QeMCMC) with techniques like warm-starting and parallel tempering.

The research offers a pathway to tackling complex problems that currently challenge even the most advanced classical solvers. The core innovation lies in the synergistic combination of QeMCMC, which leverages quantum mechanics to improve sampling efficiency, with warm-starting and parallel tempering, classical techniques used to guide the optimization process.
This hybrid approach allows the algorithm to explore the solution space more effectively, converging on optimal solutions faster than purely classical methods. For the largest instance tested, with 117 decision variables, the quantum hardware experiments converged in fewer iterations compared to classical simulations, suggesting that limitations in classical simulation techniques become more significant than hardware noise at larger scales.

This research provides an alternative strategy for approaching combinatorial optimization with near-term quantum computers, paving the way for tackling increasingly complex problems with potential real-world impact. Specifically, the algorithm addressed MIS problems with up to 117 decision variables, mapping each variable to a qubit on the quantum processor.

Warm-starting was employed to initialize the Markov chain with a good initial solution, reducing the time required to converge to an optimal or near-optimal solution. Parallel tempering, a technique involving multiple Markov chains at different temperatures, further aided exploration of the solution space and mitigated the risk of getting trapped in local optima.

The performance of this quantum-enhanced approach was benchmarked against classical Markov chain Monte Carlo (MCMC) implementations on the same MIS instances. Researchers observed an empirical scaling advantage, with the quantum algorithm demonstrating faster convergence for larger problem sizes, particularly the 117-variable instance.

Analysis revealed that the truncation error inherent in tensor network simulations of the algorithm became more significant than hardware noise as problem size increased, suggesting a potential pathway towards practical quantum advantage. Despite recent hardware improvements, executing empirical optimization experiments at scales challenging for current classical solvers remains difficult.

This work presents a novel approach to combinatorial optimization utilising near-term quantum computing, combining quantum-enhanced Markov chain Monte Carlo (QeMCMC) with warm-starting and parallel tempering techniques. Instances of the MIS problem are practically relevant in fields such as financial services and molecular biology, and can become computationally intractable for classical solvers with only a few hundred decision variables.

The study successfully implemented a practical QeMCMC algorithm on these non-trivial system sizes, marking a significant step forward in quantum optimization workflows. For the largest problem instance, comprising 117 decision variables, quantum hardware experiments converged faster in terms of iterations than classical simulations of the algorithm.

This suggests that the truncation error inherent in tensor network simulations becomes more detrimental than hardware noise as problem size increases. The observed convergence speed indicates a potential for improved performance with larger, more complex problems. This algorithm therefore provides an alternative method for approaching combinatorial optimization using quantum computing resources. The authors acknowledge the limitations of the current study, specifically the small number of non-trivial problem instances examined, and plan to investigate larger problems to better understand the scaling behaviour of the algorithm. Future research will focus on expanding the scope of the experiments to include more extensive datasets and larger problem instances, ultimately aiming to establish a clearer pathway towards quantum advantage in optimisation and contribute to benchmarking efforts within the quantum computing community.