qml.qaoa.cost.edge_driver

edge_driver(graph, reward)

Returns the edge-driver 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 as 1 (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 two-bit bitstrings that are assigned a lower energy by the Hamiltonian

Returns

Return type

Hamiltonian

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 rustworkx 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 in reward and the other is not. Finally, in the third example, both pairs are in reward.

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 vertex-colour 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 Pauli-Z 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 well-defined 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\).

code/api/pennylane.qaoa.cost.edge_driver

 

Download Python script

 

Download Notebook

 

View on GitHub