Goal : To partition the vertices of a graph into two sets such that the number of edges between the two sets is maximized.The Max-Cut problem is a NP-hard problem. Binary representation : For each vertex i i i x i x_i x i x i = 1 x_i = 1 x i = 1 i i i x i = 0 x_i = 0 x i = 0 i i i ( i , j ) (i,j) ( i , j ) x i ≠ x j x_i \neq x_j x i = x j The MaxCut objective function is exressed as:∑ ( i , j ) ∈ E w i j ( 1 − x i x j ) \sum_{(i,j) \in E} w_ij (1 - x_i x_j) ∑ ( i , j ) ∈ E w i j ( 1 − x i x j ) Using the substitution, x i = 1 − Z i 2 x_i = \frac{1 - Z_i}{2} x i = 2 1 − Z i
H ^ M a x C u t = ∑ ( i , j ) ∈ E I − Z i Z j 2 = − 1 2 ∑ ( i , j ) ∈ E ( Z i Z j ) + 1 2 ∣ E ∣ I \hat{H}MaxCut = \sum_{(i,j) \in E} \frac{I - Z_i Z_j}{2} \ = -\frac{1}{2} \sum_{(i,j) \in E} (Z_i Z_j) + \frac{1}{2} |E| I \ H ^ M a x C u t = ( i , j ) ∈ E ∑ 2 I − Z i Z j = − 2 1 ( i , j ) ∈ E ∑ ( Z i Z j ) + 2 1 ∣ E ∣ I
Where ∣ E ∣ |E| ∣ E ∣
Goal : To find the smallest set of vertices such that each edge in the graph has at least one endpoint in the set.Binary Representation : For each vertex j j j x j = 1 x_j=1 x j = 1 j j j x j = 0 x_j=0 x j = 0 Minimize ∑ j ∈ V x j \sum_{j \in V}{x_j} ∑ j ∈ V x j ( i , j ) (i,j) ( i , j ) E E E x i + x j ≥ 1 x_i + x_j \geq 1 x i + x j ≥ 1
For the constraint of MVC, we using the penalty function: P ( 1 − x − y + x y ) P(1-x-y+xy) P ( 1 − x − y + x y )
The penalty function can convert a constrinat problem to an unconstrained problem P P P w j w_j w j j j j w j = 1 w_j = 1 w j = 1
Minimize ∑ j ∈ V w j x j + P ( ∑ ( i , j ) ∈ E ( 1 − x i − x j + x i x j ) ) \text{Minimize } \sum_{j \in V}{w_j x_j} + P\left(\sum_{(i,j)\in E} (1 - x_i - x_j + x_i x_j)\right) Minimize j ∈ V ∑ w j x j + P ( i , j ) ∈ E ∑ ( 1 − x i − x j + x i x j )
Substitute x i = 1 − Z i 2 x_i = \frac{1 - Z_i}{2} x i = 2 1 − Z i
y = ∑ j ∈ V ( 1 − z j ) w j 2 + P ∑ ( i , j ) ∈ E [ 1 − 1 − z j 2 − 1 − z i 2 + 1 − z j 2 1 − z i 2 ] = ∣ V ∣ w j 2 − ∑ j ∈ V w j z j 2 + P ∑ ( i , j ) ∈ E [ 1 − 1 2 + z j 2 − 1 2 + z i 2 + 1 − z i − z j + z i z j 4 ] = ∣ V ∣ w j 2 − ∑ j ∈ V w j z j 2 + P ∑ ( i , j ) ∈ E [ 1 + z i z j + z i + z j 4 ] \begin{align} y &= \sum_{j\in V} \frac{(1-z_j)w_j}{2} + P \sum_{(i,j)\in E} \left[1-\frac{1-z_j}{2}-\frac{1-z_i}{2}+\frac{1-z_j}{2}\frac{1-z_i}{2}\right] \\ &= \frac{|V|w_j}{2} - \sum_{j\in V}w_j\frac{z_j}{2} + P \sum_{(i,j)\in E} \left[1-\frac{1}{2}+\frac{z_j}{2}-\frac{1}{2}+\frac{z_i}{2}+\frac{1-z_i-z_j+z_iz_j}{4}\right] \\ &= \frac{|V|w_j}{2} - \sum_{j\in V}w_j\frac{z_j}{2} + P \sum_{(i,j)\in E} \left[\frac{1+z_iz_j+z_i+z_j}{4}\right] \end{align} y = j ∈ V ∑ 2 ( 1 − z j ) w j + P ( i , j ) ∈ E ∑ [ 1 − 2 1 − z j − 2 1 − z i + 2 1 − z j 2 1 − z i ] = 2 ∣ V ∣ w j − j ∈ V ∑ w j 2 z j + P ( i , j ) ∈ E ∑ [ 1 − 2 1 + 2 z j − 2 1 + 2 z i + 4 1 − z i − z j + z i z j ] = 2 ∣ V ∣ w j − j ∈ V ∑ w j 2 z j + P ( i , j ) ∈ E ∑ [ 4 1 + z i z j + z i + z j ]
Then we have:
H ^ MVC = − ∑ j ∈ V w j Z j 2 + P ∑ ( i , j ) ∈ E [ Z i Z j + Z i + Z j 4 ] + ∣ V ∣ w j 2 I + ∣ E ∣ P 4 I \hat{H}_\text{MVC} = -\sum_{j\in V} w_j \frac{Z_j}{2} + P \sum_{(i,j)\in E} \left[\frac{Z_iZ_j + Z_i + Z_j}{4}\right] + \frac{|V|w_j}{2}\mathbb{I} + \frac{|E|P}{4}\mathbb{I} H ^ MVC = − j ∈ V ∑ w j 2 Z j + P ( i , j ) ∈ E ∑ [ 4 Z i Z j + Z i + Z j ] + 2 ∣ V ∣ w j I + 4 ∣ E ∣ P I
where ∣ V ∣ |V| ∣ V ∣ ∣ E ∣ |E| ∣ E ∣
The Ising Model is a mathematicla formulation used in quantum systems to encode Optimization Problems .
For a single qubit, energy can be encoded using Z gate : Z gate: Assigns +1 energy for the state ∣ 0 ⟩ \ket{0} ∣ 0 ⟩ ∣ 1 ⟩ \ket{1} ∣ 1 ⟩ For multiple qubits, interactions are defined using Ising couplings between qubits: Z i Z i Z_i Z_i Z i Z i +1 for states ∣ 00 ⟩ \ket{00} ∣ 00 ⟩ ∣ 11 ⟩ \ket{11} ∣ 11 ⟩ -1 for states ∣ 01 ⟩ \ket{01} ∣ 01 ⟩ ∣ 10 ⟩ \ket{10} ∣ 10 ⟩ The objective in QUBO is to minimize a cost function of the from:
E ( x 1 , x 2 , . . . , x n ) = ∑ i n c i x i + ∑ i , j n Q i j x i x j E(x_1, x_2, ..., x_n) = \sum_{i}^n c_i x_i + \sum_{i,j}^n Q_ij x_i x_j E ( x 1 , x 2 , ... , x n ) = ∑ i n c i x i + ∑ i , j n Q i j x i x j x i x_i x i
This cost function can be mapped to the Ising Hamiltonian: x i = 1 − Z i 2 x_i = \frac{1 - Z_i}{2} x i = 2 1 − Z i z i z_i z i