qml.qaoa.cost.max_weight_cycle

max_weight_cycle(graph, constrained=True)

Returns the QAOA cost Hamiltonian and the recommended mixer corresponding to the maximum-weighted cycle problem, for a given graph.

The maximum-weighted cycle problem is defined in the following way (see here for more details). 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.

Parameters

• graph (nx.Graph or rx.PyGraph or rx.PyDiGraph) – the directed graph on which the Hamiltonians are defined

• constrained (bool) – specifies the variant of QAOA that is performed (constrained or unconstrained)

Returns

The cost and mixer Hamiltonians, as well as a dictionary mapping from wires to the graph’s edges

Return type

(Hamiltonian, Hamiltonian, dict)

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 maximum weighted cycle cost Hamiltonian for unconstrained QAOA is

\[H_C = H_{\rm loss}.\]

Here, \(H_{\rm loss}\) is a loss Hamiltonian:

\[H_{\rm loss} = \sum_{(i, j) \in E} Z_{ij}\log c_{ij}\]

where \(E\) are the edges of the graph and \(Z_{ij}\) is a qubit Pauli-Z matrix acting upon the wire specified by the edge \((i, j)\) (see loss_hamiltonian() for more details).

The returned mixer Hamiltonian is cycle_mixer() given by

\[H_M = \frac{1}{4}\sum_{(i, j)\in E} \left(\sum_{k \in V, k\neq i, k\neq j, (i, k) \in E, (k, j) \in E} \left[X_{ij}X_{ik}X_{kj} +Y_{ij}Y_{ik}X_{kj} + Y_{ij}X_{ik}Y_{kj} - X_{ij}Y_{ik}Y_{kj}\right] \right).\]

This mixer provides transitions between collections of cycles, i.e., any subset of edges in \(E\) such that all the graph’s nodes \(V\) have zero net flow (see the net_flow_constraint() function).

Note

Recommended initialization circuit:

Your circuit must prepare a state that corresponds to a cycle (or a superposition of cycles). Follow the example code below to see how this is done.

Unconstrained

The maximum weighted cycle cost Hamiltonian for constrained QAOA is defined as:

\[H_C \ = H_{\rm loss} + 3 H_{\rm netflow} + 3 H_{\rm outflow}.\]

The netflow constraint Hamiltonian net_flow_constraint() is given by

\[H_{\rm netflow} = \sum_{i \in V} \left((d_{i}^{\rm out} - d_{i}^{\rm in})\mathbb{I} - \sum_{j, (i, j) \in E} Z_{ij} + \sum_{j, (j, i) \in E} Z_{ji} \right)^{2},\]

where \(d_{i}^{\rm out}\) and \(d_{i}^{\rm in}\) are the outdegree and indegree, respectively, of node \(i\). It is minimized whenever a subset of edges in \(E\) results in zero net flow from each node in \(V\).

The outflow constraint Hamiltonian out_flow_constraint() is given by

\[H_{\rm outflow} = \sum_{i\in V}\left(d_{i}^{out}(d_{i}^{out} - 2)\mathbb{I} - 2(d_{i}^{out}-1)\sum_{j,(i,j)\in E}\hat{Z}_{ij} + \left( \sum_{j,(i,j)\in E}\hat{Z}_{ij} \right)^{2}\right).\]

It is minimized whenever a subset of edges in \(E\) results in an outflow of at most one from each node in \(V\).

The returned mixer Hamiltonian is x_mixer() applied to all wires.

Note

Recommended initialization circuit:

Even superposition over all basis states.

Example

First set up a simple graph:

import pennylane as qml
import numpy as np
import networkx as nx

a = np.random.random((4, 4))
np.fill_diagonal(a, 0)
g = nx.DiGraph(a)

The cost and mixer Hamiltonian as well as the mapping from wires to edges can be loaded using:

>>> cost, mixer, mapping = qml.qaoa.max_weight_cycle(g, constrained=True)

Since we are using constrained=True, we must ensure that the input state to the QAOA algorithm corresponds to a cycle. Consider the mapping:

>>> mapping
{0: (0, 1),
 1: (0, 2),
 2: (0, 3),
 3: (1, 0),
 4: (1, 2),
 5: (1, 3),
 6: (2, 0),
 7: (2, 1),
 8: (2, 3),
 9: (3, 0),
 10: (3, 1),
 11: (3, 2)}

A simple cycle is given by the edges (0, 1) and (1, 0) and corresponding wires 0 and 3. Hence, the state \(|100100000000\rangle\) corresponds to a cycle and can be prepared using BasisState or simple PauliX rotations on the 0 and 3 wires.

code/api/pennylane.qaoa.cost.max_weight_cycle

 

Download Python script

 

Download Notebook

 

View on GitHub