qml.qaoa.cost.min_vertex_cover¶
- min_vertex_cover(graph, constrained=True)[source]¶
Returns the QAOA cost Hamiltonian and the recommended mixer corresponding to the Minimum Vertex Cover problem, for a given graph.
To solve the Minimum Vertex Cover problem, we attempt to find the smallest vertex cover of a graph — a collection of vertices such that every edge in the graph has one of the vertices as an endpoint.
- 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
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 Minimum Vertex Cover 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 \(G\).Note
- Recommended initialization circuit:
Each wire in the \(|1\rangle\) state.
Unconstrained
The Minimum Vertex Cover cost Hamiltonian for unconstrained QAOA is defined as:
\[H_C \ = \ 3 \sum_{(i, j) \in E(G)} (Z_i Z_j \ + \ Z_i \ + \ Z_j) \ - \ \displaystyle\sum_{i \in V(G)} Z_i\]where \(E(G)\) is the set of edges of \(G\), \(V(G)\) is the set of vertices, and \(Z_i\) is the Pauli-Z operator acting on 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.