qml.qaoa.cost.edge_driver¶

edge_driver
(graph, reward)[source]¶ Returns the edgedriver cost Hamiltonian.
Given some graph, \(G\) with each node representing a wire, and a binary colouring where each node/wire is assigned either \(0\rangle\) or \(1\rangle\), the edge driver cost Hamiltonian will assign a lower energy to edges represented by qubit states with endpoint colourings supplied in
reward
.For instance, if
reward
is["11"]
, then edges with both endpoints coloured as1
(the state \(11\rangle\)) will be assigned a lower energy, while the other colourings ("00"
,"10"
, and"01"
corresponding to states \(00\rangle\), \(10\rangle\), and \(10\rangle\), respectively) will be assigned a higher energy.See usage details for more information.
 Parameters
graph (nx.Graph or rx.PyGraph) – The graph on which the Hamiltonian is defined
reward (list[str]) – The list of twobit bitstrings that are assigned a lower energy by the Hamiltonian
 Returns
 Return type
Example
>>> import networkx as nx >>> graph = nx.Graph([(0, 1), (1, 2)]) >>> hamiltonian = qaoa.edge_driver(graph, ["11", "10", "01"]) >>> print(hamiltonian) (0.25) [Z0] + (0.25) [Z1] + (0.25) [Z1] + (0.25) [Z2] + (0.25) [Z0 Z1] + (0.25) [Z1 Z2]
>>> import retworkx as rx >>> graph = rx.PyGraph() >>> graph.add_nodes_from([0, 1, 2]) >>> graph.add_edges_from([(0, 1,""), (1,2,"")]) >>> hamiltonian = qaoa.edge_driver(graph, ["11", "10", "01"]) >>> print(hamiltonian) (0.25) [Z0] + (0.25) [Z1] + (0.25) [Z1] + (0.25) [Z2] + (0.25) [Z0 Z1] + (0.25) [Z1 Z2]
In the above example,
"11"
,"10"
, and"01"
are assigned a lower energy than"00"
. For example, a quick calculation of expectation values gives us:\[\langle 000  H  000 \rangle \ = \ 1.5\]\[\langle 100  H  100 \rangle \ = \ 0.5\]\[\langle 110  H  110\rangle \ = \ 0.5\]In the first example, both vertex pairs are not in
reward
. In the second example, one pair is inreward
and the other is not. Finally, in the third example, both pairs are inreward
.Usage Details
The goal of many combinatorial problems that can be solved with QAOA is to find a Graph colouring of some supplied graph \(G\), that minimizes some cost function. With QAOA, it is natural to consider the class of graph colouring problems that only admit two colours, as we can easily encode these two colours using the \(1\rangle\) and \(0\rangle\) states of qubits. Therefore, given some graph \(G\), each edge of the graph can be described by a pair of qubits, \(00\rangle\), \(01\rangle\), \(10\rangle\), or \(11\rangle\), corresponding to the colourings of its endpoints.
When constructing QAOA cost functions, one must “penalize” certain states of the graph, and “reward” others, by assigning higher and lower energies to these respective configurations. Given a set of vertexcolour pairs (which each describe a possible state of a graph edge), the
edge_driver()
function outputs a Hamiltonian that rewards the pairs in the set, and penalizes the others.For example, given the reward set: \(\{00\rangle, \ 01\rangle, \ 10\rangle\}\) and the graph \(G\), the
edge_driver()
function will output the following Hamiltonian:\[H \ = \ \frac{1}{4} \displaystyle\sum_{(i, j) \in E(G)} \big( Z_{i} Z_{j} \  \ Z_{i} \  \ Z_{j} \big)\]where \(E(G)\) is the set of edges of \(G\), and \(Z_i\) is the PauliZ operator acting on the \(i\)th wire. As can be checked, this Hamiltonian assigns an energy of \(1/4\) to the states \(00\rangle\), \(01\rangle\) and \(10\rangle\), and an energy of \(3/4\) to the state \(11\rangle\).
Note
reward
must always contain both \(01\rangle\) and \(10\rangle\), or neither of the two. Within an undirected graph, there is no notion of “order” of edge endpoints, so these two states are effectively the same. Therefore, there is no welldefined way to penalize one and reward the other.Note
The absolute difference in energy between colourings in
reward
and colourings in its complement is always \(1\).