Node and edge coloring with distance

[yaelbh]

What is the expected enhancement?

Rustworkx has code for node and edge coloring. Its original motivation as far as I know comes from circuit synthesis. Another use-case arises when users want to run the same 2-qubit circuit on all pairs of qubits. To increase efficiency, users combine multiple edges into one large circuit, hence running the small circuit in parallel on all these edges at the same time. Since edges sharing a qubit cannot be combined this way, edge coloring induces a partition of the edges to sets of edges that can be combined together. The number of circuits sent to the device is equal to the number of colors, therefore to increase efficiency we seek to minimize the number of colors.

Node coloring is useful in a similar case, where we wish to run a 1-qubit circuit in parallel on all device qubits, and, to avoid cross-talk, adjacent qubits don't belong to the same large circuit.

In both the 1-qubit and 2-qubit cases, to avoid cross-talk, we often want qubits/edges to be even more distant if executed together at the same large large circuit. To this end, I suggest to add a distance parameter to the coloring functions in Rustworkx. Implementation is very easy, and involves adding edges to the graph, in the case of node coloring with distance; and adding edges to the line graph, in the case of edge coloring with distance.

For edge coloring, it is possible that there exist other algorithms that solve the problem directly, and not by mapping to a line graph, and have better performance and/or approximation guarantees. I found this paper.

Other topics that may be of interest, for both node and edge coloring, also in the distance=1 case:

• Equitability - request the colors to be roughly of the same size.
• Exploit known structure of the graph, like bounded degree, or bipartite.