Improvements to auto-parallelism #538
Description
In the current iteration of the cirq parallelism tool, we parallelize in two stages. In stage 1, we parallelize the topological generations based on solving an integer linear program. Then in stage 2, we solve an edge coloring problem for each generation to parallelize the two-qubit gates. This is obviously sub-optimal-- a better version would mix it together into one stage that minimizes the maximum generation of the fully parallelized circuit. However, this is a hard computational problem, which we wish to avoid.
The problem is that for stage 2 coloring, any user-provided information about the similarity is lost, instead resorting to a naive edge coloring algorithm of the connectivity graph. An upgrade would be to use the similarity weights in the coloring algorithm as well, solving some constrained K-matching problem (np hard, apx easy).
Upgrade would be to the function colorize
A clear use case would be in the efficient optimization of brickwork (1d or 2d) circuits that have user-specified weights that fix the connectivity.
This is a low-priority nice-to-have. Autoparallelism must also be enhanced to fit within the framework of move synthesis, which is also possible via this autosimilarity using grid qubits to label parallel-y viable moves.