104 lines
4.1 KiB
Plaintext
104 lines
4.1 KiB
Plaintext
---
|
||
title: clique
|
||
description: API reference for qiskit.optimization.applications.ising.clique
|
||
in_page_toc_min_heading_level: 2
|
||
python_api_type: module
|
||
python_api_name: qiskit.optimization.applications.ising.clique
|
||
---
|
||
|
||
<span id="qiskit-optimization-applications-ising-clique" />
|
||
|
||
# qiskit.optimization.applications.ising.clique
|
||
|
||
Convert clique instances into Pauli list
|
||
|
||
Deal with Gset format. See [https://web.stanford.edu/\~yyye/yyye/Gset/](https://web.stanford.edu/~yyye/yyye/Gset/)
|
||
|
||
**Functions**
|
||
|
||
| | |
|
||
| --------------------------------------------------------------------------------------------------------------------------------------------------------------- | -------------------------------------- |
|
||
| [`get_graph_solution`](#qiskit.optimization.applications.ising.clique.get_graph_solution "qiskit.optimization.applications.ising.clique.get_graph_solution")(x) | Get graph solution from binary string. |
|
||
| [`get_operator`](#qiskit.optimization.applications.ising.clique.get_operator "qiskit.optimization.applications.ising.clique.get_operator")(weight\_matrix, K) | Generate Hamiltonian for the clique. |
|
||
| [`satisfy_or_not`](#qiskit.optimization.applications.ising.clique.satisfy_or_not "qiskit.optimization.applications.ising.clique.satisfy_or_not")(x, w, K) | Compute the value of a cut. |
|
||
|
||
### get\_graph\_solution
|
||
|
||
<Function id="qiskit.optimization.applications.ising.clique.get_graph_solution" github="https://github.com/qiskit-community/qiskit-aqua/tree/stable/0.9/qiskit/optimization/applications/ising/clique.py" signature="get_graph_solution(x)">
|
||
Get graph solution from binary string.
|
||
|
||
**Parameters**
|
||
|
||
**x** (*numpy.ndarray*) – binary string as numpy array.
|
||
|
||
**Returns**
|
||
|
||
graph solution as binary numpy array.
|
||
|
||
**Return type**
|
||
|
||
numpy.ndarray
|
||
</Function>
|
||
|
||
### get\_operator
|
||
|
||
<Function id="qiskit.optimization.applications.ising.clique.get_operator" github="https://github.com/qiskit-community/qiskit-aqua/tree/stable/0.9/qiskit/optimization/applications/ising/clique.py" signature="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.
|
||
|
||
**Parameters**
|
||
|
||
* **weight\_matrix** (*numpy.ndarray*) – adjacency matrix.
|
||
* **K** (*numpy.ndarray*) – K
|
||
|
||
**Returns**
|
||
|
||
The operator for the Hamiltonian and a constant shift for the obj function.
|
||
|
||
**Return type**
|
||
|
||
tuple([WeightedPauliOperator](qiskit.aqua.operators.legacy.WeightedPauliOperator "qiskit.aqua.operators.legacy.WeightedPauliOperator"), float)
|
||
</Function>
|
||
|
||
### satisfy\_or\_not
|
||
|
||
<Function id="qiskit.optimization.applications.ising.clique.satisfy_or_not" github="https://github.com/qiskit-community/qiskit-aqua/tree/stable/0.9/qiskit/optimization/applications/ising/clique.py" signature="satisfy_or_not(x, w, K)">
|
||
Compute the value of a cut.
|
||
|
||
**Parameters**
|
||
|
||
* **x** (*numpy.ndarray*) – binary string as numpy array.
|
||
* **w** (*numpy.ndarray*) – adjacency matrix.
|
||
* **K** (*numpy.ndarray*) – K
|
||
|
||
**Returns**
|
||
|
||
value of the cut.
|
||
|
||
**Return type**
|
||
|
||
float
|
||
</Function>
|
||
|