Quantum annealing is a quantum computing paradigm particularly suited to solving optimization problems, including some NP-complete problems, such as the traveling salesman problem. Contrary to gate-based approaches, quantum annealing will evolve a state through a change in energy landscape. These types of quantum computers have been implemented and have first been commercialised by D-Wave.
The first step is to encode the optimization problem as a Hamiltonian which is referred to as the problem Hamiltonian: states with low energy will correspond to “good states” while higher energy states correspond to less optimal states. The task is therefore to find the ground state (i.e. the state with the lowest energy) of this problem Hamiltonian, which will correspond to the global minimum of the cost function. At the beginning of the annealing process, the quantum system is prepared in the ground state of a known Hamiltonian; this initial state is usually the uniform superposition of all possible bit strings. The Hamiltonian is then slowly changed from the initial Hamiltonian to the problem Hamiltonian. If the system evolves slowly enough, the final system will remain in the ground state of the Hamiltonian throughout the annealing process; therefore, the final state should be the ground state of the problem Hamiltonian.
This procedure is the quantum analogue of the simulated annealing algorithm which has historically been used to solve optimization problems as well. However, the simulated annealing algorithm is prone to get stuck in a local minimum of the cost function whenever the energy barrier between two neighbours is too high. This issue is alleviated in the case of quantum annealing as the quantum system is allowed to tunnel through the energy barriers, hence increasing the chance of reaching the global minimum of the cost function.
Suitable problems for quantum annealing
Problems solved by quantum annealers are generally expressed as Ising model problems (valued in {+1, -1}), or equivalently as a Quadratic Unconstrained Binary Optimisation (QUBO) problem (valued in {0, 1}). Since finding the ground state of an Ising model is NP-hard, every problem in NP can be mapped into an Ising model problem in polynomial time. Quantum annealing has therefore a wide range of applications including logistics, finance, and machine learning.