qml.qaoa.cost.max_clique

max_clique(graph, constrained=True)[source]

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)

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.