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