Quantum Annealing Outperforms Classical Algorithms in Optimization Problems, Study Shows

Quantum annealing (QA) is a quantum algorithm used to solve optimization problems, gaining attention for its potential in combinatorial optimization. It operates on the adiabatic quantum computing (AQC) framework, introduced in 2000. A recent study suggests that the Quantum Approximate Optimization Algorithm (QAOA), inspired by QA, may offer a quantum advantage over classical algorithms. The study also introduces a parametrized version of QA, enabling a precise 1-local analysis of the algorithm. The researchers suggest that schedule optimization could further improve QA’s performance, highlighting its promise in the current Noisy Intermediate-Scale Quantum (NISQ) era.

What is Quantum Annealing and Why is it Important?

Quantum annealing (QA) is a promising quantum algorithm that is used to solve optimization problems. It operates on the quantum analog computational framework, also known as adiabatic quantum computing (AQC). This framework was introduced by Fahri et al. in 2000 and represents the analog part of the gate-based model. While both the gate-based model and AQC are known to be equivalent, their studies rely on different theoretical tools. QA has gained significant attention over the past decade due to its suitability for solving combinatorial optimization problems.

The goal of quantum annealing is to allow a quantum system to evolve along a trajectory according to the Schrödinger equation, subject to a problem-dependent Hamiltonian. A gate-based algorithm, known as Quantum Approximate Optimization Algorithm (QAOA), is inspired by QA and has brought significant attention to the Noisy Intermediate-Scale Quantum (NISQ) era. The NISQ era refers to the current period in quantum computing where quantum devices are not yet error-free, but they are advanced enough to perform certain tasks better than classical computers.

How Does Quantum Annealing Compare to Other Algorithms?

A recent study suggests that QAOA, even in the NISQ era, may offer a quantum advantage over classical algorithms for approximation in optimization problems. Several numerical studies suggest that QA performs well compared to QAOA. However, numerical studies in QA are rarely convincing because the size of the instance is limited by the classical computational power required to solve the Schrödinger equation or by the largest available quantum annealer.

The downside of this approach is that due to the limited size of the input data for numerical experiments, it is not possible to deduce a reliable asymptotic scale. To tackle this comparison, some researchers have tried to develop new mathematical tools to derive an analytical bound on the algorithmic performance of QA.

What is the Lieb Robinson Bound and How Does it Apply to Quantum Annealing?

In 1972, Lieb and Robinson showed the existence of an information speed limit inside a quantum system. This means that for a short enough evolution time, the correlation between two remote sites of the quantum system decreases exponentially fast with respect to their distance. This observation can be used to analyze QA as a local algorithm by taking into account this exponential decrease in correlation strength.

In this work, a super tight Lieb Robinson (LR) bound is developed using the commutativity graph construction over general regular graphs. This LR bound is adapted to linear-schedule QA applied to MaxCut, a benchmark optimization problem.

How Does Quantum Annealing Perform in Comparison to Other Algorithms?

The researchers show that a linear-schedule QA with a 1-local analysis achieves an approximation ratio over 0.7020, outperforming any known 1-local algorithms. This value shows that constant time QA outperforms both single-layer QAOA and the best-known classical 1-local algorithm.

The researchers also slightly modify the standard initial Hamiltonian with a free parameter α in front of it. It appears that this additional degree of freedom in the algorithm formulation allows for a tighter performance analysis.

What are the Future Prospects for Quantum Annealing?

The researchers suggest that schedule optimization should bring further improvements to the performance of QA. They have suggested one with a cubic function. The global overview of the different steps used to derive an approximation ratio is detailed in the study.

In conclusion, quantum annealing holds promise for optimization problems in quantum computing, especially for combinatorial optimization. This analog framework attracts attention for its potential to address complex problems. Its gate-based homologous QAOA with proven performance has attracted a lot of attention to the NISQ era. The researchers’ work introduces a parametrized version of QA, enabling a precise 1-local analysis of the algorithm.