Quantum Annealing Beats Prior Algorithm on Optimization

Researchers at the Wroc law University of Science and Technology, led by Jakub Pawłowski, have introduced Simulated Bifurcation Quantum Annealing (SBQA), a novel quantum-inspired algorithm designed to improve the efficiency of optimisation processes. SBQA extends the established technique of simulated bifurcation by incorporating inter-replica interactions, a mechanism intended to mimic the behaviour of quantum tunneling, thereby enhancing performance on particularly complex energy landscapes. Their rigorous benchmarking demonstrates that SBQA consistently surpasses the performance of standard simulated bifurcation methods when applied to sparse and rugged problem spaces, positioning it as a significant classical heuristic and a useful tool for evaluating the capabilities of emerging quantum optimisation hardware.

Inter-replica tunnelling enhances performance on complex optimisation landscapes

A substantial 35% reduction in optimality gaps, a key metric for evaluating the quality of a solution, was achieved using SBQA compared to standard Simulated Bifurcation Machine (SBM) methods when tested on challenging problem instances. These instances are characterised by complex and uneven ‘energy’ surfaces, which represent the cost or value associated with different potential solutions. Traditional SBM methods often struggle with these landscapes, reaching performance limits on sparse and rugged optimisation problems previously considered intractable due to the vastness of the search space and the presence of numerous local optima. SBQA addresses this limitation by introducing inter-replica interactions, allowing information exchange between different instances of the algorithm running in parallel. This exchange effectively simulates quantum tunneling, enabling the algorithm to traverse barriers in the energy landscape that would otherwise trap conventional methods. The algorithm doesn’t actually use quantum mechanics, but imitates its effects to improve performance on classical computers.

Comprehensive assessment, utilising parameters up to a maximum value of six, confirms SBQA’s adaptability across a diverse range of problem families and solidifies its position as a robust classical heuristic. The researchers found that selecting an inverse temperature parameter between 0.5 and 1.5 consistently yielded the lowest error rates. This was determined through analysis using Wishart ensembles, random matrices used to model complex systems, Pegasus 3D spin glasses, which represent disordered magnetic systems, and 50×50 square lattices, serving as a model for spatial arrangements. This stable operational range is analogous to the careful control of temperature in conventional annealing processes, where gradual cooling allows the system to settle into a low-energy state. Benchmarking on instances specifically designed to challenge current quantum annealers, including Zephyr graphs, sparse graphs used in optimisation, and problems employed in Quantum Annealing Correction schemes, demonstrated that SBQA maintained its improved performance even on problems intended to push the boundaries of existing hardware. The best results were consistently achieved when employing a schedule exponent, controlling the rate of exploration, between 0.5 and 1.0, indicating a balanced approach between exploration and exploitation of the solution space.

The significance of this parameter tuning lies in the algorithm’s ability to avoid becoming trapped in local minima. By carefully controlling the ‘temperature’ and exploration rate, SBQA can more effectively navigate the complex energy landscape and identify solutions closer to the global optimum. The use of diverse benchmark problems ensures that the observed improvements are not specific to a particular problem structure, but rather reflect a general enhancement in the algorithm’s optimisation capabilities. Furthermore, the ability of SBQA to perform well on problems designed for quantum annealers suggests its potential as a valuable tool for developing and testing new quantum algorithms and hardware.

Collective learning enhances solution discovery in complex optimisation problems

Identifying the optimal solution from a vast number of possibilities is a computationally intensive task, as optimisation forms the core of numerous contemporary challenges, ranging from the design of efficient logistics networks and financial modelling to the discovery of novel materials and drug design. The computational cost increases exponentially with the size and complexity of the problem. SBQA offers a refined approach to optimisation by introducing interactions between multiple solution pathways, effectively creating a ‘collective’ of algorithms that learn from each other. This allows the algorithm to explore complex problems more effectively than traditional methods, representing a significant refinement of existing optimisation approaches. The inter-replica interactions facilitate a form of collective learning, where information gained from exploring one part of the solution space is shared with other replicas, accelerating the search for the optimal solution.

Benchmarking consistently demonstrates SBQA’s outperformance of Simulated Bifurcation Machine, particularly when tackling sparse and rugged ‘energy landscapes’. This establishes the method not only as a valuable tool for assessing future quantum optimisation hardware, providing a classical benchmark against which to compare quantum performance, but also as a source of insights into the potential of inter-replica interactions for improving classical heuristics. The ability to accurately model and navigate these complex landscapes is crucial for solving real-world problems where the search space is vast, and the cost function is highly non-convex. The algorithm’s efficiency stems from its ability to maintain the parallelism of simulated bifurcation while incorporating the benefits of quantum-inspired tunneling, resulting in a powerful and versatile optimisation tool. Further research could explore the application of SBQA to even more complex problems and investigate the potential for combining it with other optimisation techniques.

The development of SBQA contributes to the broader field of quantum-inspired algorithms, which aim to leverage concepts from quantum mechanics to improve classical computation. While not a quantum algorithm itself, SBQA demonstrates the potential of borrowing ideas from quantum physics to develop more efficient and robust classical heuristics, paving the way for advancements in various fields reliant on effective optimisation techniques.

Simulated Bifurcation Quantum Annealing successfully improves upon existing optimisation methods, particularly on complex problems with sparse and rugged ‘energy landscapes’. The algorithm achieves this by incorporating inter-replica interactions, allowing for a collective learning process that accelerates the search for optimal solutions. This research positions SBQA as a useful classical benchmark for evaluating future quantum optimisation hardware. The authors suggest further work could explore applying SBQA to increasingly complex problems and combining it with other optimisation techniques.