qml.qaoa.cost.max_clique

max_clique(graph, constrained=True)

Returns the QAOA cost Hamiltonian and the recommended mixer corresponding to the Maximum Clique problem, for a given graph.

The goal of Maximum Clique is to find the largest clique of a graph — the largest subgraph such that all vertices are connected by an edge.

Parameters

• graph (nx.Graph or rx.PyGraph) – a graph whose edges define the pairs of vertices on which each term of the Hamiltonian acts

• constrained (bool) – specifies the variant of QAOA that is performed (constrained or unconstrained)

Returns

The cost and mixer Hamiltonians

Return type

(Hamiltonian, Hamiltonian)

Usage Details

There are two variations of QAOA for this problem, constrained and unconstrained:

Constrained

Note

This method of constrained QAOA was introduced by Hadfield, Wang, Gorman, Rieffel, Venturelli, and Biswas in arXiv:1709.03489.

The Maximum Clique cost Hamiltonian for constrained QAOA is defined as:

$$H_C \ = \ \displaystyle\sum_{v \in V(G)} Z_{v},$$

where $V(G)$ is the set of vertices of the input graph, and $Z_i$ is the Pauli-Z operator applied to the $i$-th vertex.

The returned mixer Hamiltonian is bit_flip_mixer() applied to $\bar{G}$, the complement of the graph.

Note

Recommended initialization circuit:

Each wire in the $|0\rangle$ state.

Unconstrained

The Maximum Clique cost Hamiltonian for unconstrained QAOA is defined as:

$$H_C \ = \ 3 \sum_{(i, j) \in E(\bar{G})} (Z_i Z_j \ - \ Z_i \ - \ Z_j) \ + \ \displaystyle\sum_{i \in V(G)} Z_i$$

where $V(G)$ is the set of vertices of the input graph $G$, $E(\bar{G})$ is the set of edges of the complement of $G$, and $Z_i$ is the Pauli-Z operator applied to the $i$-th vertex.

The returned mixer Hamiltonian is x_mixer() applied to all wires.

Note

Recommended initialization circuit:

Even superposition over all basis states.

code/api/pennylane.qaoa.cost.max_clique

 

Download Python script

 

Download Notebook

 

View on GitHub