Quantum algorithm speeds up optimisation at a key transition point

Phasecraft Ltd. researchers have developed a quantum algorithm potentially capable of dramatically speeding up optimisation processes, reducing the required annealing time from a scaling dependent on system size N to O(1). The work explores how continuous reverse quantum annealing, crossing a many-body localisation transition, can be accelerated by focusing on the density of Landau-Zener crossings during a system quench.

This approach, detailed in a recent paper, interprets the algorithm’s behaviour using a Fokker-Planck equation, and demonstrates a circuit implementation with parameters determined by a time-dependent Hamiltonian. The researchers show the continuous dynamics can be adapted for near-term devices with a modest number of steps as system size increases.

Fast Reverse Iterative Optimisation (FRIO) Algorithm Design

Phasecraft Ltd. has developed a quantitative strategy to determine parameters for a time-dependent Hamiltonian within its Fast Reverse Iterative Optimisation (FRIO) algorithm, potentially offering a significant advantage in solving complex optimisation problems. This performance boost stems from FRIO’s resilience to challenges like non-adiabaticity and Trotterisation, making it suitable for implementation on near-term, noisy intermediate-scale quantum (NISQ) devices. The FRIO algorithm combines elements of several quantum annealing (QA) protocols, focusing on exploring the transition between localisation and delocalisation to control tunneling between local energy minima when a transverse field is applied.

This approach builds on recent work employing cyclic reverse annealing, but achieves substantially shorter annealing times. The process begins with a reference bitstring and applies a longitudinal magnetic field, establishing a minimum energy state before proceeding through a four-step process detailed by the researchers. “Non-adiabatic Optimisation via Localisation-Delocalisation Transitions” is central to the algorithm’s function, as it allows for more efficient exploration of the solution space.

Sherrington-Kirkpatrick Model for Algorithm Testing

This comparison focused on the number of one- and two-qubit rotation gates required for implementation, revealing FRIO’s potential for reduced computational cost. The researchers explored a second-order Trotterisation of FRIO, termed FRIO_2, and detailed its implementation in supplementary material. A comparison table shows that FRIO requires 4*M*N single-qubit gates and M*N*(N-1) two-qubit gates, while QAOA demands 3*M*N single-qubit gates and 3/2*M*N*(N-1) two-qubit gates, where M represents the number of Trotter steps.

Non-Adiabatic Optimisation and Many-Body Localisation

Scientists demonstrated a method for potentially accelerating quantum optimisation algorithms by exploiting the dynamics surrounding a many-body localisation transition, a phenomenon where quantum systems can become trapped in specific states. This interpretation reveals a potential improvement in annealing time, scaling from a dependence on system size N to a constant time, O(1), for reference states possessing non-vanishing energy density.

The derivation of this master equation begins with an initial state, |${\psi }_0$⟩, and expands the evolved state, |Ψ(t)⟩, in the bitstring basis, ultimately defining the success probability, P(t), as the sum of probabilities for states with energy less than a reference energy, Er. Further work involved adapting the continuous dynamics for implementation on near-term quantum devices.

Researchers achieved this through a second-order Trotterisation, a technique for approximating continuous quantum evolution with a series of discrete steps. The number of steps required remains modest even as system size increases, making the algorithm more practical for current hardware limitations.

FRIO’s Resilience to Trotterisation and NISQ Constraints

Researchers found that even with a small number of Trotter steps, the algorithm’s effectiveness remained high, although a single step led to a noticeable decrease in the ability to locate the ground state. Further investigation into the number of gates required to implement FRIO and QAOA revealed a significant advantage for the new algorithm. The team’s analysis, detailed in supporting material, compared the number of single- and two-qubit rotation gates needed for each approach.

Density of Landau-Zener Crossings for Acceleration

The rate at which a quantum algorithm crosses from a localised to a delocalised state directly impacts its efficiency, with analysis revealing a link between the density of Landau-Zener crossings and accelerated optimisation. Researchers found that manipulating the number of these transitions during a continuous reverse quantum annealing process can significantly reduce the time needed to find optimal solutions. This acceleration stems from a specific quenching process where a linear ramp function, $B_z(t)$ = $B_{z}t$, is applied, establishing a new ground state when the applied field exceeds a critical strength, $B_z^c$ = (E_r-E_(GS))/N.

The team’s interpretation of this behaviour relies on a Fokker-Planck equation, which describes the probability of successfully finding the lowest energy state. Simulations using Sherrington-Kirkpatrick (SK) model instances and reference states, detailed in supplementary figure S5, demonstrated that the success ratio scales favourably with system size.

The work highlights that the final state’s independence from quench speed, when restricted to a time interval of t ∈, allows for focused manipulation of Landau-Zener crossings. By focusing on the density of these crossings, the algorithm effectively navigates the energy landscape, improving the probability of finding the optimal solution and offering a pathway towards more efficient quantum optimisation.

Fokker-Planck Equation for Success Probability Interpretation

An effective Fokker-Planck equation provides a new way to interpret the success probability of a quantum algorithm designed to accelerate optimisation problems, potentially bypassing limitations tied to system size. The equation, detailed in recent work, allows for a re-evaluation of the time required to achieve an optimal solution, suggesting a reduction from a scaling dependent on the number of qubits N to O(1) for certain conditions.

The algorithm’s efficacy was tested on instances of the Sherrington-Kirkpatrick model and weighted k-local graphs, disordered spin-glass systems commonly used to study many-body localisation. Researchers found that by modelling the evolution of the algorithm’s state, they could describe the probability of finding the correct solution using the Fokker-Planck equation, a mathematical tool for describing diffusion processes.

This approach allows for a coarse-grained description of the algorithm’s behaviour, focusing on the overall probability of success rather than the detailed dynamics of individual qubits. The team’s work builds on an effective hopping model between energy levels, providing a framework for understanding how the algorithm navigates the complex energy landscape of the optimisation problem. Further analysis revealed that the continuous dynamics inherent in the algorithm can be effectively approximated using a discrete, “Trotterised” approach. Reads a key equation from the paper, defining the success probability as a sum over energy levels.

Reverse Quantum Annealing and Algorithm Improvements

By focusing on these crossings as the system is quenched, researchers have identified a means of potentially circumventing limitations inherent in traditional quantum annealing protocols. This approach addresses a key challenge in implementing quantum optimisation on existing hardware. The team’s analysis reveals a method for achieving a non-zero success probability, defined as the sum over instantaneous eigenstates with energy below a reference energy, even with reduced annealing times.

The success probability is mathematically expressed as P(E(tf)

Thermalization Dynamics for Parameter Selection

Researchers examined the short-time dynamics of the rescaled IPR for a four-qubit marginal across multiple system sizes, observing consistent behaviour that supports this conclusion. A more traditional measure of thermalization, the spin-imbalance, was also considered, providing a global perspective on the system’s evolution. This global measure reinforces the understanding of thermalization dynamics and provides an additional validation point for the parameter selection protocol, which is designed to identify optimal solutions by navigating the transition between localized and delocalized states.

Performance of FRIO Versus Quantum Approximate Optimisation Algorithm (QAOA)

Numerical results indicate that FRIO, with efficiently determined circuit parameters using thermalizing dynamics, consistently surpasses the performance of QAOA using pre-optimized angles. This comparison focuses on finding optimal solutions for these challenging optimisation tasks, a key benchmark for quantum algorithms. The digitised FRIO algorithm was tested against QAOA using a first-order Trotter decomposition with varying numbers of steps, alongside QAOA circuits of differing depths. Results across multiple system sizes show FRIO either matches or exceeds QAOA’s performance, even when the system operates near the many-body localisation-thermal critical line, where the algorithm is still competitive.

While QAOA requires classical resources for angle optimisation, FRIO’s parameters are found through thermalizing dynamics, streamlining the process. Comparisons using a second-order Trotter decomposition further support these findings, demonstrating FRIO’s robustness across different circuit implementations.

More like this

Quantum PhysicsA new quantum thermometer hits both precision limits at once

Quantum AlgorithmsQuantum algorithm finds states of systems driven by periodic forces

PhysicsA 152-qubit model tested by classical quantum chemistry

Quantum PhysicsQuantum system’s evolution defies standard approximation