qml.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 represenation

  • 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.])]}