Refactor CircuitDag and use it to improve Merge* optimizers.

[tanujkhattar]

Is your feature request related to a use case or problem? Please describe.
MergeSingleQubitGates and MergeInteractions are currently implemented using PointOptimizers. The first step of both these optimizers is to find a maximal connected component containing a particular single qubit / two qubit operation. Once the connected component is found, all operations in the connected component are merged and the resulting unitary is then decomposed into the target gateset using analytical techniques.

However, PointOptimizer is not the right abstraction for this task because it first finds the necessary operation and then merges the operations that lie to the right of it. This results in bugs like #3144 (for MergeSingleQubitGates) and the example given below (for MergeInteractions).

In [16]: import cirq
    ...: q0, q1 = cirq.LineQubit.range(2)
    ...: optimizer = cirq.MergeInteractions()
    ...: c1 = cirq.Circuit([cirq.H(q0), cirq.H(q1)])
    ...: op1 = c1.copy(); optimizer.optimize_circuit(op1)
    ...: print(c1, op1, '', sep = '\n----------------\n')
    ...: c2 = cirq.Circuit([cirq.IdentityGate(2)(q0, q1)]) + c1
    ...: op2 = c2.copy(); optimizer.optimize_circuit(op2)
    ...: print(c2, op2, sep = '\n--------\n')
0: ───H───

1: ───H───
----------------
0: ───H───

1: ───H───
----------------

0: ───I───H───
      │
1: ───I───H───
--------
0: ───Y^0.5────S^-1───X───S^-1───

1: ───Y^-0.5───Z─────────────────

Describe the solution you'd like
Instead of using PointOptimizer for finding connected component to merge, we should use CircuitDag. An example diagram, borrowed from Qiskit's compiler's presentation (link) is given below:

This would have multiple sub tasks:

1. Refactor CircuitDag to make it more user friendly as an IR (eg: it's currently transitive complete, which makes it very hard for visualizing even basic circuit structures like the one given above. I'm also not sure if we need it to be transitive complete for other use cases).
2. Use CircuitDag in MergeSingleQubitGates and MergeInteractions.

What is the urgency from your perspective for this issue? Is it blocking important work?
P2 - we should do it in the next couple of quarters

Part of the roadmap item: #3239

[AnimeshSinha1309]

I would like to work on this please. Could you assign it to me?

[AnimeshSinha1309]

I think I know how to go about this one, but I am confused as to why the current design exists?

1. Why are the transitive closures a part of the graph
2. Why is can_reorder given as a function, when the only meaningful definition of 2 operations being reoderable is that they don't share a qubit and there exists no 3rd operation which enforces order between the prior 2.

So can I just go about completely removing the old structure and writing the whole thing including tests from scratch. Just get rid of the old api. Remove functions like append and stuff.

[tanujkhattar]

@AnimeshSinha1309 If two operations commute, then they can be reordered and we don't necessarily need to have an edge between them. This property is used in pauli_string_optimize. See the predicate pauli_string_reorder_pred.

[tanujkhattar]

Discussed in Cirq Sync:

Related #3816

1. CircuitDag should be fixed / deprecated. How to do that will need a design
2. Merge optimizers should be fixed.

[tanujkhattar]

Another issue with Merge* optimizers: The merge happens only if all operations in a moment are act on a subset of qubits of the original operation. This is unnecessary and leads to inefficiencies. For example:

>>> q = cirq.LineQubit.range(3)
>>> ops = [cirq.CX(q[0], q[1]), [cirq.H(q[0])] * 20, cirq.CX(q[1], q[2])]
>>> c1, c2 = cirq.Circuit(ops[:-1]), cirq.Circuit(ops)
>>> def opt(c):
        c = c.copy()
        cirq.MergeInteractions().optimize_circuit(c)
        cirq.DropEmptyMoments().optimize_circuit(c)
        return c
>>> print(c1, opt(c1), c2, opt(c2), sep = "\n-----\n") # H gates in c2 don' get merged because of CX(1, 2)

0: ───@───H───H───H───H───H───H───H───H───H───H───H───H───H───H───H───H───H───H───H───H───
      │
1: ───X───────────────────────────────────────────────────────────────────────────────────
-----
0: ───T───X^0.5─────S────────Y^-0.5───@───S^-1───Y^0.5───Y^-0.5───Z^0.75────
                                      │
1: ───Z───X^-0.25───Y^-0.5────────────@───S^-1───Y^0.5───Z────────X^-0.75───
-----
0: ───@───H───H───H───H───H───H───H───H───H───H───H───H───H───H───H───H───H───H───H───H───
      │
1: ───X───@───────────────────────────────────────────────────────────────────────────────
          │
2: ───────X───────────────────────────────────────────────────────────────────────────────
-----
0: ───Z^0.75────X^0.5────S^-1───Y^-0.5───@───S^-1───Y^0.5───Y^0.5─────Z^-0.75───H─────────H────────H──────H────────H───H──────H───────H─────────H─────────H───H───H───H───H───H───H───H───H───H───H───
                                         │
1: ───X^-0.25───Y^-0.5───────────────────@───S^-1───Y^0.5───X^-0.25─────────────Z^0.75────X^0.5────S^-1───Y^-0.5───@───S^-1───Y^0.5───Y^0.5─────Z^-0.75───────────────────────────────────────────────
                                                                                                                   │
2: ─────────────────────────────────────────────────────────────────────────────X^-0.25───Y^-0.5───────────────────@───S^-1───Y^0.5───X^-0.25─────────────────────────────────────────────────────────

[tanujkhattar]

Merge* optimizers have now been improved / fixed using the new merge_operations and merge_moments primitives. See #4722 for details.

We should now deprecate and remove CircuitDag class, which is being tracked in #3816