Applicable Problems
Quantum annealing processors naturally return low-energy solutions; some applications require the real minimum energy (optimization problems) and others require good low-energy samples (probabilistic sampling problems).
Optimization problems. In an optimization problem, you search for the best of many possible combinations. Optimization problems include scheduling challenges, such as “Should I ship this package on this truck or the next one?” or “What is the most efficient route a traveling salesperson should take to visit different cities?”
Physics can help solve these sorts of problems because you can frame them as energy minimization problems. A fundamental rule of physics is that everything tends to seek a minimum energy state. Objects slide down hills; hot things cool down over time. This behavior is also true in the world of quantum physics. Quantum annealing simply uses quantum physics to find low-energy states of a problem and therefore the optimal or near-optimal combination of elements.
Sampling problems. Sampling from many low-energy states and characterizing the shape of the energy landscape is useful for machine learning problems where you want to build a probabilistic model of reality. The samples give you information about the model state for a given set of parameters, which can then be used to improve the model.
Probabilistic models explicitly handle uncertainty by accounting for gaps in knowledge and errors in data sources. Probability distributions represent the unobserved quantities in a model (including noise effects) and how they relate to the data. The distribution of the data is approximated based on a finite set of samples. The model infers from the observed data, and learning occurs as it transforms the prior distribution, defined before observing the data, into the posterior distribution, defined afterward. If the training process is successful, the learned distribution resembles the distribution that generated the data, allowing predictions to be made on unobserved data. For example, when training on the famous MNIST dataset of handwritten digits, such a model can generate images resembling handwritten digits that are consistent with the training set.
Sampling from energy-based distributions is a computationally intensive task that is an excellent match for the way that the D-Wave quantum computer solves problems; that is, by seeking low-energy states.
How Quantum Annealing Works in D-Wave QPUs
The quantum bits—also known as qubits—are the lowest energy states of the superconducting loops that make up the D-Wave QPU. These states have a circulating current and a corresponding magnetic field. As with classical bits, a qubit can be in state of 0 or 1. But because the qubit is a quantum object, it can also be in a superposition of the 0 state and the 1 state at the same time. At the end of the quantum annealing process, each qubit collapses from a superposition state into either 0 or 1 (a classical state).
The physics of this process can be visualized with an energy diagram. At the start of the annealing process, the qubit is in a superposition state, which can be represented as a single valley with a single minimum energy. As the quantum annealing process runs, an energy barrier is raised which separates the single minimum energy into two valleys .
The probability of the qubit falling into the 0 or 1 state can be controlled by applying an external magnetic field to bias the qubit to end in one state over the other; the magnetic field is programmatically controlled via a qubit bias.
However, the real power of quantum annealing is realized when you link qubits together so they can influence each other, accomplished via a device called a coupler. A coupler can correlate two qubits such that they tend to end up in the same classical state—both 0 or both 1—or in opposite states. The correlation between coupled qubits is controlled programmatically. Together, programmable qubit biases and coupler correlations are the means by which a problem is defined in the D-Wave quantum computer.
Furthermore, couplers use another phenomenon of quantum physics called entanglement. When two qubits are entangled, they can be thought of as a single object with four possible states. The relative energy of each state depends on the biases of qubits and the couplers between them. During the anneal, the qubit states are potentially entangled in this landscape before finally settling into (1,1) at the end of the anneal.
As stated, each qubit has a bias and qubits interact via the couplers. When formulating a problem, you choose values for the qubit biases and couplers. The qubit biases and couplers define an energy landscape, and the D-Wave quantum computer finds the minimum energy of that landscape: this is quantum annealing.
Systems get increasingly complex as qubits are added: two qubits have four possible states over which to define an energy landscape; three qubits have eight. Each additional qubit doubles the number of states over which you can define the energy landscape: the number of states goes up exponentially with the number of qubits.
In summary, the system starts with a set of qubits, each in a superposition state of 0 and 1. They are not yet coupled. When they undergo quantum annealing, the couplers and qubit biases are introduced and the qubits become entangled. At this point, the system is in an entangled state of many possible answers. By the end of the anneal, each qubit is in a classical state that represents the minimum energy state of the problem, or one very close to it. All of this happens in D-Wave quantum computers in a matter of microseconds.
Underlying Quantum Physics
This section discusses some concepts essential to understanding the quantum physics that governs the D-Wave quantum annealing process.
The minimum energy state throughout the quantum annealing process so that—by the end—it is in the minimum energy state of the problem Hamiltonian and therefore has an answer to the problem you want to solve. By the end of the anneal, each qubit is a classical object.
Annealing in Low-Energy States
A plot of the eigenenergies versus time is a useful way to visualize the quantum annealing process. The lowest energy state during the anneal—the ground state—is typically shown at the bottom, and any higher excited states are above it.
As an anneal begins, the system starts in the lowest energy state, which is well separated from any other energy level. As the problem Hamiltonian is introduced, other energy levels may get closer to the ground state. The closer they get, the higher the probability that the system will jump from the lowest energy state into one of the excited states. There is a point during the anneal where the first excited state—that with the lowest energy apart from the ground state—approaches the ground state closely and then diverges away again. The minimum distance between the ground state and the first excited state throughout any point in the anneal is called the minimum gap.
Certain factors may cause the system to jump from the ground state into a higher energy state. One is thermal fluctuations that exist in any physical system. Another is running the annealing process too quickly. An annealing process that experiences no interference from outside energy sources and evolves the Hamiltonian slowly enough is called an adiabatic process, and this is where the name adiabatic quantum computing comes from. Because no real-world computation can run in perfect isolation, quantum annealing may be thought of as the real-world counterpart to adiabatic quantum computing, a theoretical ideal. In reality, for some problems, the probability of staying in the ground state can sometimes be small; however, the low-energy states that are returned are still very useful.
For every different problem that you specify, there is a different Hamiltonian and a different corresponding eigenspectrum. The most difficult problems, in terms of quantum annealing, are generally those with the smallest minimum gaps.