Intro to Quantum Annealing
Let’s demystify this new buzzword: “Quantum Annealing”. Here you will get an overview over Hamiltonian energy functions, binary quadratic models (Ising and QUBO) and the complete workflow for solving problems on a quantum annealer. We will discuss problem reformulation using a penalty term and minor embedding on a concrete example.
Let’s first take a look at the general workflow for solving problems on a quantum annealer. A real-world problem is our starting point. This problem is modeled mathematically and then expressed using a specific formulation (QUBO) we will talk about later. This formulation allows us to represent the problem as a graph which is then “mapped” to a quantum annealer. We can then let the annealer do the rest for us and hopefully find good solutions to our original real-world problem.
We will dive in deeper, but this is the high-level overview to keep in mind while exploring quantum annealing. Note that we won’t explain every single term in detail, so this might not be the right article as a complete novice to the topic. [2] also offers a great introduction which should make the basic concepts clear and may make for a good read before this article.
Quantum Annealing
Quantum annealing is an optimization process leveraging quantum effects in physics in order to find the ground state (the systems’ lowest energy state) of an encoded optimization problem, thus yielding optimal or near-optimal solutions for the original problem. In 2000, Farhi et al. proposed a quantum algorithm based on the principle of quantum adiabatic evolution [1]. They construct a time-dependent Hamiltonian H(t) which describes the energy for a particular state of the system. This Hamiltonian is the sum of the initial Hamiltonian H_init and the problem Hamiltonian H_final. H_init describes the state of the system where all qubits are in a superposition state of 0 and 1 at the same time [2]. It is designed so that its ground state is known and we initialize the quantum system to this state in the beginning. We then evolve according to
where T is the evolution time or total running time of the algorithm and t ∈ [0, T]. As can be seen, we interpolate between the initial and the problem Hamiltonian.
While H_final is also easy to construct, its ground state is usually not known. It describes the solution to the optimization problem, hence we need the system to remain in its ground state, so that at time t = T it is equal to or very close to the ground state of H_final encoding the final solution [1, 3]. According to the adiabatic theorem, this behavior is guaranteed in theory for “big enough” T, i. e. the system is evolved slowly enough to ensure H(t) does not jump to a higher, excited state throughout the process [1, 2]. (Note that the minimum gap is defined as the distance between the two lowest energy levels, i. e. the ground state (lowest energy) and the first excited state of the interpolating Hamiltonian.)
To summarize, the system is initialized according to the Hamiltonian H_initial and then adiabatically evolved introducing the problem Hamiltonian H_final. In the best case, the system will end in the ground state of H_final encoding the desired solution to the optimization problem.
Binary Quadratic Models: Ising and QUBO
In order to define our problem Hamiltonian, we use a binary quadratic model that maps directly onto the qubits and couplers of a Quantum Processing Unit (QPU). A well-studied Hamiltonian is that of the Ising model used in statistical physics. The reader is referred to [4] and [5] for an (advanced) introduction to the Ising model. Its Hamiltonian is given by: [6]
with σᵢ , σⱼ ∈ {−1,+1} indicating the atomic spin of the qubits. Note that this notation reflects the qubits’ layout in the QPU: their topology is given by a graph G with edges (couplings) E(G) and vertices (qubits) V(G). Qubit biases (external influences on the spin) are given by the linear coefficients hᵢ, whereas the quadratic coefficients Jᵢⱼ correspond to coupling (interaction) strengths. (We assume the Ising model to be ferromagnetic, i. e. Jᵢⱼ > 0, but also allow Jᵢⱼ = 0 when qubits i and j are not entangled (there is no interaction between them).) µ is the strength of the external magnetic field. As the previous equation is our objective function, we can adopt the following simplifications which won’t change the position of the optimum x*:
Rendering the Hamiltonian into [7, 8]:
While the Ising model draws on spin values “up” and “down” (σᵢ ∈ {−1,+1}), Quadratic Unconstrained Binary Optimization (QUBO) problems stem from computer science and use values x ∈ {0, 1} (true, false). In the QUBO model, we try to minimize the following energy function:
In the matrix notation Q is an upper-diagonal matrix with entries on the diagonal corresponding to the linear coefficients and nonzero off-diagonal terms corresponding to the quadratic coefficients. Note that we can easily express an Ising problem as QUBO problem using the identity σ → 2x − 1.
Solving problems on Quantum Annealers
D-Wave Systems Inc. (hereinafter referred to as D-Wave) is a quantum computing company producing commercially available quantum annealers debuting in 2011 [9]. Their QPU is made up of a lattice of tiny metal loops that get cooled down to the point where they become superconductors and exhibit quantum-mechanical effects. Each superconducting loop represents either a quantum bit (referred to as qubit) or a coupler entangling multiple qubits. The energy state of a qubit is biased by a programmable external magnetic field which alters the probability of a qubit “falling” into the classical state 0 or 1 when it collapses from the initial superposition state. We will refer to this quantity as qubit bias. Likewise, we can use the magnetic field to control coupling strengths. Qubit biases and coupling strengths together describe the energy landscape of the system and are introduced as problem Hamiltonian H_final over time. Hence, when the user wants to solve a specific optimization problem, they need to encode it into a Hamiltonian function. [2]
Problem reformulations
In order to set up our problem Hamiltonian (our objective function), we will make use of a binary quadratic model. This is since D-Wave’s quantum annealers are constrained to these models by the way they are built with qubits obeying the Ising model. To illustrate the steps of solving an optimization problem using a quantum annealer, we introduce the Minimum Vertex Cover Problem (MVCP) on graphs.
The MVCP is defined as follows: Given an undirected graph G = (V, E) with vertices V and edges E, a vertex cover is a subset of vertices such that every edge of the graph is incident to at least one vertex in that subset. The MVCP asks for a vertex cover with the smallest number of vertices. Let xᵢ be a binary variable on each vertex, which is 1 if vertex i is in the cover and 0 otherwise. As we want to use as few vertices as possible for the cover, our objective function is given by:
It is subject to the constraint that every edge is incident to at least one vertex in the cover:
However, in the QUBO format, no constraints are allowed, which is why we reformulate our problem, for example, we map it to a quadratic model. There are many different approaches to reformulation, we will only cover one of them. To reformulate our constraint, we introduce a penalty term, which we design to equal zero for feasible solutions and some positive scalar for infeasible solutions [10]. For the MVCP, the penalty term becomes: [11]
It will be 0 for every edge where at least one end is in the cover (either xᵢ or xⱼ is 1) and 1 if both incident vertices are not in the cover (xᵢ and xⱼ are zero). This allows us to write our objective function as follows:
where λ is a positive, scalar penalty value used to weight the penalty term. We are now able to write this equation, so that it bears resemblance to QUBO notation:
where m = |E|. Note we can drop the additive constant mλ as it has no impact on the optimum. This should clarify that the equation can easily be written in QUBO notation for a specific instance of the MVCP.
As an example, consider the following graph:
The minimum vertex cover is already marked in blue; it consists of vertices 3 and 5. The MVCP for this graph is modeled as follows:
Dropping the additive constant 5λ, we can write down our QUBO model with the upper-diagonal matrix Q given by:
Minor Embedding
After having formulated the problem in Ising or QUBO notation, we map our objective function to the QPU topology [2]. We will refer to this process as minor embedding. Let us represent the QPU topology by a graph G = (V, E) with vertices V and edges E. First, we represent our objective function as graph of logical qubits as follows:
- Linear coefficients of the objective function (σᵢ or qᵢᵢ) become nodes of the graph, which in turn stand for logical qubits in the QPU.
- Quadratic coefficients of the objective function (Jᵢⱼ or qᵢⱼ ) become weighted edges of the graph, which in turn stand for couplers and their coupling strengths in the QPU.
For the MVCP example, the graph representing the QUBO problem obtained by following the “mapping rules” will look exactly as our sample graph shown before. This is the special case, where our underlying optimization problem itself refers to a graph. In general, however, we do not need to find a separate graph representation of our mathematical problem as long as we can transform it into a binary quadratic model, which we can always map to a graph as described above.
The actual minor embedding then refers to the process of mapping this graph of logical qubits to the physical qubits which are arranged in a graph as well representing the topology of the annealer’s qubits. For D-Wave systems, this is either the Chimera or Pegasus topology (see Chimera below). To ease talking about the different graphs, we define:
Definition (Input and hardware graph)
- The input graph H is the undirected graph of the objective function given as a binary quadratic model. Its vertices represent logical qubits.
- The hardware graph G is the undirected graph of the quantum annealer’s topology of physical qubits.
Super vertex placement. Multiple physical qubits in the hardware graph may represent the same logical qubit in the input graph, that is, the same variable of the problem Ising model. This is needed, so that we can map arbitrary binary quadratic models to the hardware graph. For example, notice that we cannot embed the input graph H for our MVCP in the Chimera graph G_Chimera using just five physical qubits. This stems from the fact that H contains the fully connected graph K₃ which is not native to G_Chimera as there is no way in the Chimera graph to connect three qubits in a closed loop. Instead, we “chain together” multiple physical qubits to represent one variable, e. g. x₄. With this approach, we can find a valid embedding, where the “chain” or super vertex representing x₄ is marked in red:
In practice, chains are realized by defining a strong coupling between the chained physical qubits, so that they take the same value at the optimal solution. Mathematically, chains are disjoint, connected subgraphs of G. An edge between two subgraphs indicates that two logical qubits are connected in the input graph H. In terms of graph theory, we can assert these properties if and only if the input graph H (graph of our binary quadratic model) is a minor of the hardware graph G [2], which is equivalent to the requirement that H is embeddable in G (see Lemma 6 in [12]). To briefly touch on minor embedding: we define a super vertex placement function ϕ that maps vertices of H to subsets of vertices of G. In D-Wave systems the subsets of vertices in the hardware graph are called “chains”, while we refer to them mainly as super vertices.
The problem of finding a minor embedding for arbitrary input graphs and arbitrary hardware graphs is NP-hard as discussed in [12]. While we do consider fixed topologies for the hardware graphs, not all physical qubits might be accessible for the embedding due to engineering limitations, i. e. not all qubits function as desired and are therefore deactivated. Moreover, after each calibration phase, different qubits might be inaccessible (“broken”), so the ideal hardware graph (Chimera etc.) differs from the actual hardware graph G presented to the user when embedding a problem. This is why researches “are interested in [minor embedding] algorithms in which both G and H are part of the input” [13]. As in [12], we assume the embedding problem to remain relevant in the long term because, first, the number of “broken” qubits will probably decrease, but not reach 0, and second, a fully connected hardware topology is not yet in sight.
Summarized workflow
The following list summarizes the steps needed to solve a real-world problem on a quantum annealer:
- First, state the problem to be solved, for example, “Which routers in my communication network are central in the sense that with those routers identified I can reach every router in the network?”
- In the next step, the problem must be represented mathematically as an objective function, e. g. we can pose our question as MVCP.
- If our objective function is not in the Ising or QUBO format, we have to reformulate it using reformulation techniques, e. g. express constraints with penalty terms. Our objective function is constructed, so that low energy states represent good solutions to our problem.
- The objective function in Ising or QUBO format can then be represented by an input graph H, where linear coefficients correspond to nodes and quadratic coefficients to edges.
- In order to solve the problem on the annealer’s QPU, we need to map the input graph H to the hardware topology graph G by finding a valid minor embedding ϕ. One logical qubit might get mapped to multiple physical qubits.
- During the actual annealing where qubits exhibit quantum effects, our problem objective function is introduced over time by altering the magnetic field accordingly, so that the energy landscape represents our problem. Vertices of the embedded graph correspond to qubit biases and edges to coupling strengths.
- Finally, qubits collapse from a superposition state to a classical state. If the system stayed in the ground state throughout the entire time, this minimum of the resulting energy landscape corresponds to a solution to our problem. The annealing might be repeated multiple times to account for inaccuracies.
Sources
“Most important” sources (subjectively for this article) are bold-faced. Source [2] offers a great and easy-to-follow introduction to quantum annealing.
[1] Farhi, E. et al. Quantum Computation by Adiabatic Evolution. 2000. arXiv: quantph/0001106 [quant-ph]. Visited on March 2, 2022.
[2] D-Wave Systems Inc. Getting Started with D-Wave Solvers: User Manual. October 4, 2021. Visited on January 16, 2021.
[3] Choi, V. Minor-Embedding in Adiabatic Quantum Computation: I. The Parameter Setting Problem. April 30, 2008. Visited on February 17, 2022.
[4] Cai, W. Handout 12. Ising Model: ME346A Introduction to Statistical Mechanics. Stanford University, February 25, 2011. Visited on March 2, 2022.
[5] Mbeng, G. B./ Russomanno, A./ Santoro, G. E. The quantum Ising chain for beginners. September 22, 2020. Visited on March 2, 2022.
[6] Kadowaki, T./ Nishimori, H. Quantum annealing in the transverse Ising model. In: Physical Review E 58.5 (1998), pp. 5355–5363. doi: 10.1103/physreve.58.5355. Visited on March 16, 2022.
[7] Bian, Z. et al. Discrete optimization using quantum annealing on sparse Ising models. In: Frontiers in Physics 2 (2014). doi: 10.3389/fphy.2014.00056. Vvisited on March 1, 2022.
[8] Sugie, Y. et al. Minor-embedding heuristics for large-scale annealing processors with sparse hardware graphs of up to 102,400 nodes. In: Soft Computing 25.3 (2021), pp. 1731–1749. doi: 10.1007/s00500–020–05502–6. Visited on February 17, 2022.
[9] Zyga, L. D-Wave sells first commercial quantum computer. PhysOrg, June 1, 2011. Visited on March 16, 2022.
[10] Glover, F./ Kochenberger, G./ Du, Y. A Tutorial on Formulating and Using QUBO Models. 2019.[cs.DS]
[11] Lucas, A. Ising formulations of many NP problems. In: Frontiers in Physics 2 (2014). doi: 10.3389/fphy.2014.00005.
[12] Lobe, E./ Lutz, A. Minor Embedding in Broken Chimera and Pegasus Graphs is NP-complete. September 15, 2021. Visited on March 25, 2022.
[13] Cai, J./ Macready, W. G./ Roy, A. A practical heuristic for finding graph minors. June 12, 2014. Visited on February 15, 2022.
