Add different coloring options to `PauliList.group_commuting`

[willkirby1]

What should we add?

The group_commuting method of PauliList (qiskit.quantum_info.pauli_list) currently only has one method for grouping the list of Pauli operators into commuting subsets, using a greedy method. To group a set of Pauli operators based on commutation (or qubit-wise commutation), one forms the anticommutation (or qubit-wise anticommutation) graph, in which nodes representing qubits are connected with edges if they do NOT commute (or qubit-wise commute). Then a node coloring on this graph corresponds to a grouping into commuting (qubit-wise commuting) subsets.

The current method is restricted to use Rustworkx's graph_greedy_color function, but there are many other heuristics for node coloring out there, such as Recursive Largest First (https://en.wikipedia.org/wiki/Recursive_largest_first_algorithm) and DSatur (e.g. https://link.springer.com/book/10.1007/978-3-030-81054-2, which also contains other examples). It would be great to give the user a few options of heuristic (greedy_graph_color could still be used as the default), since this is an NP-complete problem in worst-cases and in practical cases of relevance, greedy_graph_color often does not find the optimal grouping.

[willkirby1]

@jakelishman

[willkirby1]

A number of heuristics are implemented here in C++ https://rhydlewis.eu/gcol/

[ikkoham]

Need to enhance rustworkx as well @mtreinish

Edited: I mean we need to enhance https://www.rustworkx.org/apiref/rustworkx.graph_greedy_color.html

[jakelishman]

Hamamura-san: there's already a couple of alternative edge-colouring algorithms in Rustworkx, so I think we can get started on exposing an interface to the existing choices immediately, and expand it in the future when there are more choices (especially more direct node-colouring algorithms, where we don't have to play with the dual graph)?

edit: actually, maybe it's not as easy to recast this as an edge-colouring problem as I had originally thought. There might be a way, but it's not immediately coming to me.

For example, perhaps something like this works:

def group_commuting(self, qubit_wise=False, method="greedy-node"):

where method must be one of some supported set of algorithms? For the use-case of callers that just want "try everything and give me the best", maybe we either allow method to be an iterable, or have a special value "best", where we try all methods selected and return the best one?

[alexanderivrii]

Indeed, it's easy to reduce an edge-coloring problem to a node-coloring problem, but not the other way around (afaik) . I don't think that the original problem can be easily recast as an edge-coloring problem.

@willkirby1, what are the typical graph sizes (number of nodes and edges) for the pauli commutation problems (in practical applications)? Also, do you know which of the algorithms described in the book perform best for these problems?

[mrossinek]

I just came across this coincidentally. Whether or not additional coloring methods can/should be exposed as part of the group_commuting API aside, I would suggest that we actually make the method which constructs the Pauli graph part of the public API. Specifically, this means turning PauliList._create_graph into a public method, such as PauliList.noncommutation_graph. The equivalent can be exposed via SparsePauliOp. This will give users the freedom to use whatever rustworkx algorithm to perform the coloring themselves until more options are exposed via the group_commuting API.

I can work on a PR to do this, as well as some other minor de-duplication of code around this topic inside PauliList and SparsePauliOp if that is a desired approach :+1:

[willkirby1]

@alexanderivrii the graph sizes could vary widely, from e.g. 10s of Paulis for tiny toy Hamiltonians up to millions or more for medium-sized chemistry Hamiltonians. IMO, though, adding more options for heuristics and making the method performant enough to handle such extremely large cases are really two different issues. And no, I don't know which heuristics work best or if there is any real pattern to them, which is part of why I thought it would be good to just have a few options that the user could try.

[alexanderivrii]

And one more question: how are these commuting subsets of Pauli operators used later? In particular, do you want them to satisfy other properties, or the only required property is that their number is as small as possible?

[willkirby1]

The only property we would still want is that we can specify whether local or global commutation is used to form the graph. Otherwise, I think for the coloring itself the main goal would just be as few colors as possible since that will translate into the smallest number of distinct circuits. There might be other desiderata in some circumstances, but I don't know of any...

[jakelishman]

We're now merging #11795, which will make the non-commutation graph part of the public API, but that PR doesn't change the mechanisms of SparsePauliOp.group_commuting, so I'll leave this issue open for further discussion.