Ising Model, Graph Similarity, QUBO and Quantum Computing

A wonderful bridge between graph, Ising Model via QUBO?

Introduction

In this short article, we consider the relationships between these topics through QUBO:

• Ising Model
• Labelled Maximum Weighted Common Subgraph (LMWCS)
• Maximum Independent Set (MIS)
• Maximum Co-k-plex Problem

• Quadratic Unconstrained Binary Optimization (QUBO)

• Quantum Approximate Optimization Algorithm (QAOA)
• Quantum Digital Annealing (QDA)

Definitions

Quadratic Unconstrained Binary Optimization (QUBO)

The QUBO problem seeks to optimize (usually minimize) a quadratic function of binary variables.

definition:

1. Variables:
   • Let \(x_i\) be binary variables where \(x_i \in \{0, 1\}\) for \(i = 1, ..., n\).
2. Objective: Optimize (commonly minimize) the following quadratic function:

\[\text{minimize} \quad \sum_{i=1}^{n} Q_{ii} x_i + \sum_{i=1}^{n} \sum_{j=i+1}^{n} Q_{ij} x_i x_j\]

Where:

• \(Q_{ii}\) are the linear coefficients.
• \(Q_{ij}\) are the quadratic coefficients.
• \(Q\) is an \(n \times n\) symmetric matrix, commonly referred to as the QUBO matrix.

Objective in Matrix Form:

• The objective function can also be compactly represented using matrix notation: \(f(x) = x^T Q x\) Where \(x\) is a column vector of binary variables and \(Q\) is the QUBO matrix.

The QUBO problem is NP-hard and arises naturally in many optimization problems across various domains.

Ising Model

The Ising model is a mathematical model used in statistical mechanics to describe phase transitions, particularly the transition between magnetized and non-magnetized states in ferromagnetic materials.

Definition:

Consider a lattice where each site \(i\) has a spin variable \(s_i\) which can take the values +1 (spin up) or -1 (spin down). The Hamiltonian (or energy) \(H\) of the system is given by:

\[H = -J \sum_{\langle i,j \rangle} s_i s_j - h \sum_i s_i\]

where:

• The first sum \(\sum_{\langle i,j \rangle}\) runs over all nearest neighbor pairs on the lattice.
• \(J\) is the exchange interaction which determines the strength and nature (ferromagnetic or antiferromagnetic) of the interaction between neighboring spins.
  • If \(J > 0\), the system is ferromagnetic meaning spins prefer to align in the same direction.
  • If \(J < 0\), the system is antiferromagnetic meaning spins prefer to align in opposite directions.
• \(h\) is an external magnetic field.
• The second sum \(\sum_i\) runs over all sites in the lattice.

The main goal in the Ising model is to compute the statistical properties of the system, like its magnetization, given the Hamiltonian. By studying how these properties change with temperature, one can learn about phase transitions and critical phenomena.

Relation to QUBO: By using the following transformation, the Ising model can be mapped to a QUBO problem:

\[\begin{aligned} & s_i=1 \text { to } x_i=0 \\ & s_i=-1 \text { to } x_i=1 \end{aligned}\]

Maximum Independent Set (MIS)

Given a graph \(G = (V, E)\), the MIS problem is to find the largest subset \(S \subseteq V\) such that no two vertices in \(S\) are adjacent.

definition:

Let \(x_i\) be a binary variable that is 1 if vertex \(i\) is in the independent set and 0 otherwise. The MIS problem can be formulated as:

\[\text{maximize} \sum_{i \in V} x_i\]

\(\text{subject to}\) \(x_i + x_j \leq 1 \quad \forall (i, j) \in E\) \(x_i \in \{0, 1\} \quad \forall i \in V\)

LMWCS (Labelled maximum weighted common subgraph problem)

This problem seeks to find a common subgraph between our derived graph \(G_1\) and the graph \(G_2\). The objective is to maximize the weight, considering the labels on the nodes and edges.

Definitions:

• LMWCS (labelled maximum weighted common subgraph): A problem aiming to find the common subgraph between two labelled graphs that has the maximum sum of weights.

Consider two arbitrary graphs \(G_1=(V_1, E_1)\) and \(G_2=(V_2, E_2)\). For the LMWCS problem, a binary variable \(b_{ij}\) is assigned for each pair \((i, j) \in V_1 \times V_2\). Its weight is \(w_{ij}\), with:

\[b_{ij} = \begin{cases} 1 & \text{if }(i, j) \text{ is in mapping} \\ 0 & \text{otherwise} \end{cases}\]

Certain pairings might be excluded based on vertex labels. We define two sets for bijection and user-defined constraints:

\[C = \{((i, j),(m, n)) | i=m \text{ or } j=n\}\] \[C^* = \{((i, j),(m, n)) | b_{ij} b_{mn}=0 \text{ is user-defined}\}\]

For the MIS formulation, we introduce a conflict graph \(G_c=(V_c, E_c)\) with \(V_c \subset V_1 \times V_2\) and \(E_c = C \cup C^*\). Vertices represent labelled graph vertex pairs, with edges (or conflicts) representing constraints in \(C\) and \(C^*\).

• Vertices: Represent all possible single vertices mapping between \(G_1\) and \(G_2\).
• Edges: Denote conflicts between mappings. Specifically, the edge indicates that the two vertex mappings it connects cannot co-exist in the common subgraph.

The problem of finding the LMWCS of \(G_1\) and \(G_2\) can be transformed into the problem of finding the MIS in \(G_c\).

Relation to QUBO:

The objective function to maximize is:

\[\text{maximize} \sum_{s \in V_c} w_s x_s - \sum_{(s,l) \in E_c} a_{sl} x_s x_l\]

Where:

• \(x_s\) is a binary variable: \(x_s = 1\) if vertex \(s\) is in the independent set, and \(x_s = 0\) otherwise.
• \(w_s\) is the weight of the vertex \(s\).
• \(a_{sl}\) is a constant such that \(a_{sl} > \min(w_s, w_l)\).

Maximum Co-k-plex problem

A co-\(k\)-plexes is a generalization of cliques to allow for “near-cliques” or “almost-cliques” in graphs.

Definition (co-\(k\)-plex): A co-k-plex of a graph \(G\) is a subgraph of \(G\) in which each vertex has a degree of at most \(k-1\).

Definition (star graph): A graph \(S^k=(V, E)\) is a star graph of size \(k\) if it is a tree with \(k+1\) vertices and one vertex of degree \(k\).

The maximum co-\(k\)-plex problem seeks to find a co-\(k\)-plex of maximum size in a given graph.Therefore, the maximum weighted co- \(k\)-plex of the conflict graph \(G_c\) corresponds to the maximum weighted common subgraph of \(G_1\) and \(G_2\), where each possible pairing can violate at most \(k-1\) constraints, either bijection or user-defined.

Overview:

• The Maximum Independent Set (MIS) problem is relaxed to the co-1-plex problem.
• The aim is to find the largest set of vertices in the graph such that each vertex has at most \(k-1\) edges connecting it to the other vertices.
• This is achieved by penalizing on a star graph of size \(k\).

Mathematical Definitions:

Let \(A_{v_1,...,v_{k+1}}\) be defined as:

\[A_{v_1,...,v_{k+1}} = \begin{cases} 1 & \text{if } \{v_1, ..., v_{k+1}\} \text{ induces } S_k, \\ 0 & \text{otherwise.} \end{cases}\]

The objective function to be maximized is:

\[\max \left( \sum_{v_i \in V_c} w_{v_i} x_{v_i} - \sum_{(v_1,v_2) \in E_c} a_{v_1,v_2} x_{v_1} x_{v_2} - \sum_{(v_1,...,v_{k+1})} a_{v_1,...,v_{k+1}} A_{v_1,...,v_{k+1}} \prod_{i=1}^{k+1} x_{v_i} \right)\]

Where:

• \(x_{v_i}\) is a binary variable indicating the presence of vertex \(v_i\).
• \(w_{v_i}\) is the weight of the vertex \(v_i\).
• \(a_{v_1,v_2}\) and \(a_{v_1,...,v_{k+1}}\) are penalizing constants.

Measure:

• Similarity Measure: With the processed graph \(G\), the dataset’s graph \(G_0\), and the known binding energy \(E_0\), a similarity measure is computed using the formula:

  \[S(G_1, G_2) = \delta \max \left( \frac{|V^1_c|}{|V_1|}, \frac{|V^2_c|}{|V_2|} \right) + (1 - \delta) \min \left( \frac{|V^1_c|}{|V_1|}, \frac{|V^2_c|}{|V_2|} \right) \quad \text{where } \delta \in [0,1]\]

Quantum Approximate Optimization Algorithm (QAOA)

The Quantum Approximate Optimization Algorithm (QAOA) is a quantum algorithm introduced for tackling combinatorial optimization problems. It is particularly well-suited for problems that can be represented as QUBO or Ising Hamiltonians, which makes it a popular choice for quantum computing applications in optimization.

Quantum Approximate Optimization Algorithm (QAOA) for QUBO:

1. Encoding the Problem: The QUBO problem is encoded into a Hamiltonian, often termed as the problem Hamiltonian \(H_P\).
2. Ansatz Preparation: QAOA uses a quantum circuit that is parameterized by angles. This circuit is designed to generate a superposition of possible solutions.
3. Cost Function Evaluation: The expectation value of the problem Hamiltonian \(H_P\) is evaluated with respect to the state produced by the ansatz. This gives a measure of the quality of the solution.
4. Classical Optimization: The parameters of the ansatz are optimized using classical optimization techniques to minimize the expectation value of \(H_P\), which would correspond to finding a good approximation to the ground state of the problem Hamiltonian.
5. Iteration: Steps 2-4 are repeated for increasing depths (i.e., more layers in the ansatz) or until a satisfactory solution is found.

Let’s look at a simple QUBO problem and use Qiskit’s QAOA implementation to solve it.

Example using Qiskit:

Suppose you have the QUBO matrix:

\[Q = \begin{pmatrix} 1 & -1 \\ 0 & 1 \end{pmatrix}\]

This matrix represents the QUBO problem \(f(x) = x_0 - x_0 x_1 + x_1\).

Below is an example to solve this QUBO using QAOA and Qiskit:

from qiskit import Aer
from qiskit.algorithms import QAOA, NumPyMinimumEigensolver
from qiskit.algorithms.optimizers import COBYLA
from qiskit.utils import QuantumInstance
from qiskit_optimization import QuadraticProgram
from qiskit_optimization.algorithms import MinimumEigenOptimizer

# Define the QUBO problem
qubo = QuadraticProgram()
qubo.binary_var('x0')
qubo.binary_var('x1')
qubo.minimize(linear=[1, 1], quadratic={('x0', 'x1'): -2})

# Convert the QUBO problem to an operator
qp2op = QuadraticProgramToQubo()
qubo_op, offset = qp2op.convert(qubo)

# Define the QAOA with a classical optimizer and backend
optimizer = COBYLA(maxiter=100)
backend = Aer.get_backend('statevector_simulator')
quantum_instance = QuantumInstance(backend)
qaoa = QAOA(optimizer=optimizer, reps=2, quantum_instance=quantum_instance)

# Solve the QUBO problem using QAOA
qaoa_meo = MinimumEigenOptimizer(qaoa)
result = qaoa_meo.solve(qubo)

print(result)