Quantum Research News: Multi-stage Quantum Walks Demonstrate Efficient Strategy for Quantum Optimization
Large optimisation issues that are essential for domains ranging from materials science to machine learning yet frequently prove entirely unsolvable for conventional computers can be solved with quantum computation. This challenge is driving a lot of research into quantum solutions, and Multi-stage Quantum Walks (MSQW), a promising method, is at the forefront of this effort.
MSQW has been studied by researchers Asa Hopkins and Viv Kendon of the University of Strathclyde as a workable method for identifying the ground state, which is the lowest energy configuration of complex systems. Their research demonstrates that MSQW provides noticeably better performance than more antiquated, conventional single-stage techniques by meticulously structuring these quantum processes.
You can also read SmaraQ Project Adds On-Chip Photonics to Quantum Computing
The Core Concept: Chaining Quantum Processes
MSQW’s basic concept is straightforward but effective: it connects several quantum walks without requiring any intermediary measurements. As a result, the quantum state can progress towards the intended solution more smoothly and effectively. This method works well for approximating the optimal quantum annealing schedule.
Determining how to select the algorithm’s free parameters, such as the hopping rates (γ k) and evolution times (t i) for each stage, was a crucial breakthrough needed to make MSQW feasible. The group accomplished this by creating a productive heuristic approach to parameter selection. Importantly, this methodology avoids the exponential complexity that besets attempts to fine-tune parameters in existing guided quantum walk approaches by requiring only a polynomial amount of classical computational effort.
Victory on “Easy” Problems
The numerical testing produced outstanding results for problems that were simple to solve. In particular, the technique demonstrated efficient performance for typical Sherrington-Kirkpatrick (SK) spin glass problems with a significant minimum energy gap and up to 20 qubits.
In these simpler cases, MSQW shows an effective polynomial scaling relationship between the algorithm’s performance and the number of stages used. In essence, the solution scaling for these issues is consistently improved by adding more stages. For common problem situations, adding more stages (raising m) seems to increase the total success chance indefinitely. The overall success probability scales exponentially, P=ea(m)n+b(m).
You can also read Hamiltonian Embedding on IonQ & QuEra by Amazon Braket
The Point at Which Scaling Fails
Nonetheless, the researchers made it apparent that in more challenging situations, its effectiveness declines. The polynomial scaling breaks down for “hard problems,” which are purposefully chosen to have a tiny minimum energy gap.
The simulations demonstrated that in these challenging situations, the likelihood of identifying the right answer can actually be reduced by increasing the number of phases. As is typically assumed when working with intractable optimization problems, this leads to an overall scaling that eventually becomes exponential. For instance, simulations showed that for many of the challenging tasks evaluated, utilising 50 phases would result in a lower success chance than using only 10.
Outperforming Quantum Rivals
The compared to other quantum algorithms, the MSQW method has shown itself to be quite competitive. Previous work established that MSQW stages will always outperform the same number of stages in the Quantum Approximate Optimization Algorithm (QAOA), and that they are more robust to parameter choices, building on the expectation that quantum walks perform well when problems are encoded into Ising Hamiltonians.
Additionally, MSQW performs well in comparison to actual quantum annealing machines. A significant speedup was shown by simulations that compared the MSQW approach to a D-Wave Advantage2 1.6 annealer. The quantum walks reached comparable success percentages in about a quarter of the time needed by the simulated annealer.
You can also read California Launches “Quantum California” To Boost Tech Jobs
The Theoretical Engine
The effectiveness of MSQW is supported by a thorough theoretical framework. Infinite time averaging is extended to an arbitrary number of stages using the procedure. It is possible to think of the resulting mathematical framework (Equation 7 in the source) as a sequence of projections intended to progressively rotate the initial quantum states in the direction of the ground state.
In order for the ground states to have the same eigenvalue prior to being combined together, the hopping rate heuristics (γ k) were developed by scaling the Hamiltonians according to their spectral norm (energy spread). Every stage spins the state evenly towards the solution with this design.
The finite evolution time (t i) heuristics rely on an analytical method to determine the shortest feasible evolution time. One way to think of these time values is as the amount of time needed for the driver Hamiltonian (γH^G) can push any of the Ising Hamiltonian’s eigenstates (H^I ) to a neighboring eigenstate, and the other way around. For the slower of these two rotation methods to take place, enough time is guaranteed by the last heuristic.
Hardware Challenges and the Road Ahead
With the strong simulation findings, MSQW is challenging to run physically on existing D-Wave technology. For SK spin glasses, the evolution time for a single-stage quantum walk is incredibly quick, scaling as T=O(n −0.5). The resulting timescales are so short that, with physical anneals currently in use, the time required to ramp up the fields between each stage would exceed the necessary evolution time.
The researchers did, however, propose a method for implementation on different hardware: breaking down each MSQW stage into QAOA phases using Trotter decomposition. This would enable the use of a gate-based quantum computer to implement the multi-stage technique.
Creating a reliable heuristic for figuring out the ideal number of stages for a particular topic is still a major challenge. The energy gap, a figure that is usually unknown prior to the problem being solved, seems to be connected to this ideal number.
The multi-stage quantum walk is similar to a spacecraft performing a planned series of gravitational aids: instead of depending on a single, straightforward boost or a single, lengthy, slow burn (like standard annealing), MSQW employs a carefully timed, multi-step procedure to effectively steer the system through intricate energy landscapes straight towards its destination.
You can also read Coherent Information Framework Tackles Dual Quantum Errors
