Introduction to Quantum Annealing
By Ana Ciocoiu and Louise E. Turner
What is Quantum Annealing?
A quantum annealer is a type of quantum computer that exploits quantum mechanics to find the ground state (the lowest energy state of a system) of an encoded optimization problem.
Many real-world problems such as the traveling salesperson, job scheduling problem, knapsack problem, etc, can be encoded as energy minimization problems solvable using a quantum annealer. It is important to note that quantum annealing is different from gate-based quantum computing models, whose components are quantum gates and thus have classical analogues. Quantum annealing is a very different type of technology.
In physics, the Hamiltonian describes a system in terms of its energy. When dealing with a quantum system, the Hamiltonian becomes a function that will map certain states to their energy values.
Quantum annealing is an algorithm based on the principle of adiabatic quantum computation, in which a quantum system that starts in a ground-state and experiences a slow evolution of that state as a function of time, will remain in the ground state.
This principle can be leveraged to find the ground-state energy solution of an encoded optimization problem by setting the total Hamiltonian to be a sum of an initial Hamiltonian, where qubits are in a superposition state of 0 and 1, and a problem Hamiltonian, which describes the solution to the optimization problem you are trying to solve:
H(t) = (1-t) H init + t H _problem
Initially, at t=0, the system starts out in the ground state of the initial Hamiltonian. As time goes on, the problem Hamiltonian is introduced to the system. If this evolution is sufficiently slow, the system will remain in the ground state the whole time, eventually ending up in the ground state of the problem Hamiltonian.
From a hardware perspective, quantum annealers such as those used by D-Wave Systems are built using superconducting loops for qubits. The qubits are controlled using magnetic field biases and linked to each other using couplers. An optimization problem’s energy landscape can thus be mapped onto the hardware.
The annealing process can be visualized in Fig. 1 below: initially, qubits experiencing the initial Hamiltonian exist in a superposition state, whose energy can be represented as a simple parabola. As the system evolves, the potential evolves into a double-well shape, meaning that at the end of the anneal cycle, the qubit can end up in one of the two valley states. The problem encoding controls the outcome of this process: the magnetic field bias will tilt the potential, and the couplers allow interaction between qubits in a way that leads to correlation of their measurement outcomes.
By the end of the anneal cycle, qubits are in a state that ideally represents the minimum energy state of the encoded problem.
Quantum anneal cycle showing potential
Uses for Quantum Annealing
The strongest use for quantum annealing is in optimization and sampling problems, both of which require a definitive solution multiple samples for the ground-state energy. Optimization problems are abundant in many industries, such as transportation, finance, machine learning, and chemistry. Since a fundamental rule of physics is that everything tends to seek a minimum energy state, quantum annealers are used to find those low-energy states of problems, leading to the optimal solution (DWave). D-Wave's quantum annealers have already been used to solve various optimization problems for different organizations, including the Pattison Food Group. D-Wave's annealers were used to create an effective auto-scheduling solution for food delivery drivers that enabled an impressive time savings of 80%. (DWave)
Quantum Annealing Commercialization
British Columbia’s own D-Wave Systems is a pioneer in the quantum computing space, having built he “world’s first commercially viable quantum annealer” in 2011. They focus heavily on the development of quantum annealers and are regularly improving their hardware designs to permit a larger number of qubits to interact. Their processors are cloud-accessible, and they have had numerous industry partnerships, which are documented in their published applications.
Japanese multinational ICT equipment and services corporation Fujitsu has been developing quantum annealing “inspired” technology. Rather than using a physical quantum computer, Fujitsu’s digital annealer uses quantum concepts to solve complex optimization problems classically. (Fujitsu)