qiskit.optimization.applications.ising.clique

Convert clique instances into Pauli list

Deal with Gset format. See https://web.stanford.edu/~yyye/yyye/Gset/

Functions

get_graph_solution(x)	Get graph solution from binary string.
get_operator(weight_matrix, K)	Generate Hamiltonian for the clique.
satisfy_or_not(x, w, K)	Compute the value of a cut.

get_graph_solution(x)

Get graph solution from binary string.

パラメータ

x (numpy.ndarray) – binary string as numpy array.

戻り値

graph solution as binary numpy array.

戻り値の型

numpy.ndarray

get_operator(weight_matrix, K)

Generate Hamiltonian for the clique.

The goals is can we find a complete graph of size K?

To build the Hamiltonian the following logic is applied.

Suppose Xv denotes whether v should appear in the clique (Xv=1 or 0)n

H = Ha + Hbn

Ha = (K-sum_{v}{Xv})^2

Hb = K(K−1)/2 - sum_{(u,v)in E}{XuXv}

Besides, Xv = (Zv+1)/2

By replacing Xv with Zv and simplifying it, we get what we want below.

Note: in practice, we use H = A*Ha + Bb, where A is a large constant such as 1000.

A is like a huge penality over the violation of Ha, which forces Ha to be 0, i.e., you have exact K vertices selected. Under this assumption, Hb = 0 starts to make sense, it means the subgraph constitutes a clique or complete graph. Note the lowest possible value of Hb is 0.

Without the above assumption, Hb may be negative (say you select all). In this case, one needs to use Hb^2 in the hamiltonian to minimize the difference.

パラメータ

• weight_matrix (numpy.ndarray) – adjacency matrix.

• K (numpy.ndarray) – K

戻り値

The operator for the Hamiltonian and a constant shift for the obj function.

戻り値の型

tuple(WeightedPauliOperator, float)

satisfy_or_not(x, w, K)

Compute the value of a cut.

パラメータ

• x (numpy.ndarray) – binary string as numpy array.

• w (numpy.ndarray) – adjacency matrix.

• K (numpy.ndarray) – K

戻り値

value of the cut.

戻り値の型

float