qml.pauli.grouping.graph_colouring.largest_first

largest_first(binary_observables, adj)[source]

Performs graph-colouring using the Largest Degree First heuristic. Runtime is quadratic in number of vertices.

Parameters:
  • binary_observables (array[int]) – the set of Pauli words represented by a column matrix of the Pauli words in binary vector representation

  • adj (array[int]) – the adjacency matrix of the Pauli graph

Returns:

keys correspond to colours (labelled by integers) and values are lists of Pauli words of the same colour in binary vector representation.

Return type:

dict(int, list[array[int]])

Example

>>> binary_observables = np.array([[1., 1., 0.],
... [1., 0., 0.],
... [0., 0., 1.],
... [1., 0., 1.]])
>>> adj = np.array([[0., 0., 1.],
... [0., 0., 1.],
... [1., 1., 0.]])
>>> largest_first(binary_observables, adj)
{1: [array([0., 0., 1.])], 2: [array([1., 0., 0.]), array([1., 1., 0.])]}