Multi-stage Quantum Walks Achieve Polynomial Scaling for Ising Ground States, Improving Optimization Performance

Quantum optimisation problems, crucial for fields ranging from materials science to machine learning, often prove intractable for classical computers, driving research into quantum solutions. Asa Hopkins and Viv Kendon, both from the University of Strathclyde, investigate multi-stage quantum walks as a promising approach to finding the lowest energy state of complex systems, known as the ground state. Their work demonstrates that carefully designing these walks, which involve chaining together multiple quantum processes, significantly improves performance compared to traditional single-stage methods. The team developed a practical method for optimising the parameters controlling these walks, achieving polynomial scaling for simpler problems and providing valuable insight into the limitations for more challenging scenarios, ultimately advancing the potential of quantum algorithms for real-world optimisation tasks.

This method addresses optimization problems by chaining together multiple quantum walks without intermediate measurements, creating a more efficient path to solutions. The team’s primary achievement lies in devising a heuristic that leads to a polynomial scaling relationship between the number of stages and the algorithm’s performance on easily solvable problems.

Hamiltonian Spectral Radius Estimation for Quantum Annealing

This research focuses on developing more accurate and efficient methods for estimating the spectral radius of the Hamiltonian in Ising spin glass problems, a crucial step for improving the simulation and performance of quantum annealing algorithms. The spectral radius dictates the timescale needed for accurate simulation, and the author explores methods beyond simple heuristics to achieve statistically grounded approaches. The work centers on characterizing the distribution of energy levels to refine spectral radius estimation. The research utilizes statistical moments, such as mean, variance, and kurtosis, to characterize the energy level distribution and improve estimation accuracy.

A maximum entropy distribution is employed to model the energy levels, and a Gumbel distribution is used to model the maximum energy level. The Lanczos algorithm is used for partial decomposition of the Hamiltonian, aiding in the estimation process. These techniques aim to overcome the computational challenges associated with accurately estimating the spectral radius, particularly for large problems. Successful implementation of these methods could significantly impact the field of quantum annealing, leading to improved simulation accuracy, faster simulation times, and better algorithm performance. The research offers a potential pathway to simulating larger problems than currently possible, advancing the development of more effective optimization algorithms.

Multi-Stage Quantum Walks Enhance Optimisation Scaling

The research team has developed a multi-stage quantum walk (MSQW) method for solving optimization problems, demonstrating improved scaling compared to single-stage approaches. Experiments using a dataset of Sherrington-Kirkpatrick (SK) spin glass problems, up to n=20, revealed that the method functions effectively for problems with a large minimum energy gap, indicating a polynomial scaling relationship. However, for more challenging problems, the scaling breaks down, and the success probability decreases with added stages. To achieve these results, the team developed a method for determining optimal hopping rates between quantum states within each stage of the walk. This involved extending the concept of infinite time averaging to an arbitrary number of stages, and deriving a formula that maximizes the probability of finding the ground state of the problem. The team’s heuristic constructs Hamiltonians that rotate the initial state towards the ground state, scaling these Hamiltonians using the spectral norm to match eigenvalues.

Multistage Walks Scale for Easy Problems

The team developed a new heuristic method for designing multistage quantum walks, a technique used to approximate quantum annealing schedules for solving complex optimization problems. Their work demonstrates that, for problems with easily identifiable optimal solutions, the number of stages required to achieve a solution scales favorably with the problem size, leading to an efficient algorithm. However, the researchers acknowledge that the effectiveness of this method diminishes when applied to more difficult problems, where increasing the number of stages can reduce the probability of finding a solution. Future research will focus on understanding how this heuristic performs with approximate solutions and exploring its applicability to a wider range of problem types.