I have always been fascinated by computing. Thanks to my friends Ernesto Adorio (♱) and Augusto Hermosilla, both of whom are mathematicians, who introduced me to optimization. Ernie and I built the first MathNOW (Network of Workstations) in the University of the Philippines powered by Linux and MPI (Message Passing Interface). We then used this cluster to come up with a paper on Parallel Genetic Algorithms. This blog post is a first part of a series about how Quantum Computing is used to tackle NP-Complete problems.
Doing Quantum Computing is like creating musical scores as you can see from the image above. That’ s probably what inspired me to give this blog the title “I Sing Quantum Computing”. Apart from that, this blog post is about the Ising Model of Quantum Physics.
The Ising model is a model to describe magnetic materials as a lattice of particles with spin-up or spin-down orientation. When a magnetic material such as iron is hot, the orientation of the spins is random. But when it cools, spins tend to form regions (called magnetic domains) such that the spins in each region is aligned. Each particle interacts with its nearest neighbor with a weight of . The Hamiltonian (total energy) of the system of particles is given by
where is either 1 or -1 representing the spin of the particle. From the hamiltonian, we can compute the minimum eigenvalue and the corresponding eigenstate. The eigenstate will correspond to the orientations of the spins of each particle.
Mapping NP-Complete Problems to the Ising Model
Consider a graph of N nodes and edges between nodes. Each edge has a weight corresponding to the interaction between the nodes connected by the edge. Partition this graph into 2 subsets by assigning a value of 0 or 1 to each node. Get the total interaction of this partitioning by summing the interaction term for every edge that connects a node from subset 1 to subset 2, that is
The total interaction is called the cost function. Now we want to find a subset such that the cost function is maximum. This is called the max-cut problem. It’s like cutting the graph into 2 subsets and maximizing the sum of the interaction terms of each edge that crosses the cut.
An Example: Maximum Cut
Suppose we have 4 nodes connected to each other in the following way and :
Assign 0 or 1 to each node and compute the cost function C. An example assignment looks like:
Since node0 is connected to node1, node2 and node3, then we have
Below are 16 possible ways to assign 0’s and 1’s and the corresponding value of the cost function computed using the above method:
From the above, the we can see that the cost function attains a maximum at (1,0,1,0) and (0,1,0,1) with a value of C=4.
We can map this to the Ising model in the following way. Let be the Pauli Z operator defined by
Then by a change of variables
and remembering that , we can transform C into:
Therefore, to maximize C, we need to minimize the Ising Hamiltonian:
Representing the Nodes as Qubits
Using qubits, we can represent an assignment of 0’s and 1’s as a tensor product of single qubits :
In this representation, the basis states are:
In this basis, we can compute the matrix representation of . Remember that means that the Pauli Z operator operates on the ith qubit. For example,
In the same way,
Given the above, we can now compute the matrix representation of and is given by
Doing the same thing for , we can then compute the matrix for our Hamiltonian:
Since H is a diagonal matrix, the eigenvalues are the diagonal elements themselves. Looking at the values, we see that the minimum value is -1.5 which corresponds to and . Coloring the node with state as blue and as red, we get the configuration of below:
In the same way, we can map problems like the Traveling Salesman, Maximum Stable Set, Maximum 3-satisfiability, Number Partitioning and Market Split using the Ising Model. Refer to Performance of hybrid quantum/classical variational heuristics for combinatorial optimization.
Using IBM QISKit, we can get the same result:
import qiskit.aqua.translators.ising.max_cut as maxcut import numpy as np from qiskit.aqua.algorithms import VQE, ExactEigensolver adjacency_list=[[0,1,1,1],[1,0,1,0],[1,1,0,1],[1,0,1,0]] w = np.array(adjacency_list) print(w) qubitOp, offset = maxcut.get_max_cut_qubitops(w) ee = ExactEigensolver(qubitOp, k=1) result = ee.run() x = maxcut.sample_most_likely(result['eigvecs']) print('Minumum Value:', result['energy']) print('Cost Function:', result['energy'] + offset) print('EigenState:', maxcut.get_graph_solution(x))
In the next series, we will show how Variational Quantum EigenSolver is used to optimize the Ising Hamiltonian.