Quadratic Unconstrained Binary Optimization (QUBO)

Introduction

The Quadratic Unconstrained Binary Optimization (QUBO) model can solve several optimization problems such as max-cut, max-clique, network flows, vertex cover, and other graph management problems. Since qubit network structures using Ising spins can encode QUBO problems, it is an interesting application area for the current generation of quantum computers. The following statement defines the QUBO problems:

\[\text{maximize}\ or\ \text{minimize}\ f\left(x\right)=\ x^TQx\]

where \(x_i\in0,1\) is a binary vector of decision variables and \(Q\) is a square matrix of constants. The \(Q\) matrix can be symmetric or upper triangular. In terms of cost functions, the QUBO problem can be stated as follows:

Given a graph \(G=V,E\) with \(V=1,2,3,..i..n\) vertices (or nodes) and \(E=‍i,j:i,j ∈N\) edges. Let the weight of the edges be \(Q_{ij}\). Then the QUBO problem is the following maximization, with both linear and quadratic terms:

\[f\left(x\right)=\max{\sum_{i\ \in N}{Q_{ii}x_i+\ \sum_{\left(i,j\right)\in N}{Q_{ij}x_ix_j}}}\]

In the symmetric form, the transformation is given by \(\forall i\neq j,\ Q_{ij}^\prime=\ \frac{\left(Q_{ij}+Q_{ji}\right)}{2}\).

\[f\left(x\right)=\max{\sum_{i\ \in N}{Q_{ii}x_i+\ \sum_{i\neq j}{\frac{\left(Q_{ij}+Q_{ji}\right)}{2}x_ix_j}}}\]

In the upper triangle form, the transformation is given by:

\[ \begin{align}\begin{aligned}\begin{split} \forall i,j,Q'_{i,j} = \left\{ \begin{array}{cl} (Q_{ij}+Q_{ji}) & : \ i < j \\ 0 & : \ i > j \\ \end{array} \right.\end{split}\\f\left(x\right)=\max{\sum_{i\ \in N}{Q_{ii}x_i+\ \sum_{i<j}{\left(Q_{ij}+Q_{ji}\right)\ x_ix_j}}}\end{aligned}\end{align} \]

Recall the following Pauli-\(Z\) operator and its action on the computational basis states:

\[\begin{split}Z=\sigma_z=\ \left[\begin{matrix}1&0\\0&-1\\\end{matrix}\right]\end{split}\]

The action of this operator on the computational basis states is as follows:

\[Z\left|\left.\ 0\right\rangle=\left|\left.\ 0\right\rangle\right.\right.,\ \ \ \ \ \ \ \ \ \ \ Z\left|\left.\ 1\right\rangle=-\left|\left.\ 1\right\rangle\right.\right.,\]

which means the eigenvalues of the \(\sigma_z\) operator is \(\pm1\). Therefore, we can use it to encode Ising spin states by mapping the variables \(x_i\ \in\ \left\{0,1\right\}^n\) into spin states \(x_i\ \in\ \left\{-1,1\right\}^n\), with \(x_i=\ \frac{\left(1+\sigma_i^z\right)}{2}\). Plugging these mappings, we get a summation of the weighted tensor products of \(\sigma_z\). Each term in the summation contains one or two terms of \(\sigma_z\), which can be interpreted using the classical Ising spin model.

The Hamiltonian of a 1-D Ising spin chain is a quadratic function of \(n\) spins, each with eigenvalues \(\pm1\), described by the following equation:

\[H=-\sum_{i=1}^{n} J \sigma_{i}^{z} \cdot \sigma_{i+1}^{z} - \sum_{i=1}^{n}g\sigma_{i}^{z}\]

where \(\sigma_i^x\) and \(\sigma_i^z\) are the spins at the \(i^{th}\) location of the chain. \(g\) is a dimensionless coupling constant denoting the relative strength of the external field compared with the nearest neighbor interaction. \(J\) is a term that includes the inverse of temperature and energy scale. \(\sigma_i^z\sigma_{i+1}^z\) denotes the interaction between adjacent spins. The terms in the above equation commute. Hence \(H\) can be implemented as a phase operator \(U\left(\gamma\right)=\ e^{-i\gamma H}\).

Historically, simulated annealing algorithms employed the statistical physics of the Ising spin glasses. More relevant to the present discussions, we shall find that the Ising spin glasses represent the QUBO class of problems. If the binary quadratic optimization problem has constraints, the addition of quadratic penalties can compensate for the constraint violations in the objective function. The decision form of the Ising spin glass is NP-complete. Hence there exists a polynomial-time mapping to all other NP-complete problems using this model.