qml.qaoa.cost.min_vertex_cover¶

min_vertex_cover
(graph: Union[networkx.classes.graph.Graph, retworkx.PyGraph], constrained: bool = 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 PauliZ 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 PauliZ 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.