qml.qaoa.cycle.loss_hamiltonian

loss_hamiltonian(graph)

Calculates the loss Hamiltonian for the maximum-weighted cycle problem.

We consider the problem of selecting a cycle from a graph that has the greatest product of edge weights, as outlined here. The product of weights of a subset of edges in a graph is given by

\[P = \prod_{(i, j) \in E} [(c_{ij} - 1)x_{ij} + 1]\]

where \(E\) are the edges of the graph, \(x_{ij}\) is a binary number that selects whether to include the edge \((i, j)\) and \(c_{ij}\) is the corresponding edge weight. Our objective is to maximize \(P\), subject to selecting the \(x_{ij}\) so that our subset of edges composes a cycle.

The product of edge weights is maximized by equivalently considering

\[\sum_{(i, j) \in E} x_{ij}\log c_{ij},\]

assuming \(c_{ij} > 0\).

This can be restated as a minimization of the expectation value of the following qubit Hamiltonian:

\[H = \sum_{(i, j) \in E} Z_{ij}\log c_{ij}.\]

where \(Z_{ij}\) is a qubit Pauli-Z matrix acting upon the wire specified by the edge \((i, j)\). Mapping from edges to wires can be achieved using edges_to_wires().

Note

The expectation value of the returned Hamiltonian \(H\) is not equal to \(P\), but minimizing the expectation value of \(H\) is equivalent to maximizing \(P\).

Also note that the returned Hamiltonian does not impose that the selected set of edges is a cycle. This constraint can be enforced using a penalty term or by selecting a QAOA mixer Hamiltonian that only transitions between states that correspond to cycles.

Example

>>> import networkx as nx
>>> g = nx.complete_graph(3).to_directed()
>>> edge_weight_data = {edge: (i + 1) * 0.5 for i, edge in enumerate(g.edges)}
>>> for k, v in edge_weight_data.items():
        g[k[0]][k[1]]["weight"] = v
>>> h = loss_hamiltonian(g)
>>> h
(
    -0.6931471805599453 * Z(0)
  + 0.0 * Z(1)
  + 0.4054651081081644 * Z(2)
  + 0.6931471805599453 * Z(3)
  + 0.9162907318741551 * Z(4)
  + 1.0986122886681098 * Z(5)
)

>>> import rustworkx as rx
>>> g = rx.generators.directed_mesh_graph(3, [0, 1, 2])
>>> edge_weight_data = {edge: (i + 1) * 0.5 for i, edge in enumerate(sorted(g.edge_list()))}
>>> for k, v in edge_weight_data.items():
        g.update_edge(k[0], k[1], {"weight": v})
>>> h = loss_hamiltonian(g)
>>> print(h)
(
    -0.6931471805599453 * Z(0)
  + 0.0 * Z(1)
  + 0.4054651081081644 * Z(2)
  + 0.6931471805599453 * Z(3)
  + 0.9162907318741551 * Z(4)
  + 1.0986122886681098 * Z(5)
)

Parameters

graph (nx.Graph or rx.PyGraph or rx.PyDiGraph) – the graph specifying possible edges

Returns

the loss Hamiltonian

Return type

qml.Hamiltonian

Raises

• ValueError – if the graph contains self-loops

• KeyError – if one or more edges do not contain weight data

code/api/pennylane.qaoa.cycle.loss_hamiltonian

 

Download Python script

 

Download Notebook

 

View on GitHub