Should cirq.Moment store operations sorted by the underlying qubits?

[tanujkhattar]

The iteration order of operations in a cirq.Moment currently depends upon the order in which the operations were inserted in the moment. This can lead to cases where two moments m1 == m2 is True but their reprs and iteration order of underlying operations are not the same.

> q = cirq.LineQubit.range(2)
> ops = [cirq.X(q[0]), cirq.Y(q[1])]
> m1, m2 = cirq.Moment(ops), cirq.Moment(ops.reverse())
> assert m1 == m2
> for op1, op2 in zip(m1, m2):
    ...:     print(op1 == op2) # Prints False

The proposal is to directly store and use sorted(self.operations, key=lambda op: op.qubits) as the list of underlying operations in a moment to avoid such inconsistencies and uniquely define the traversal order of operations in equal moments.

[95-martin-orion]

Potentially a breaking change, since there's an implicit rule that insertion order is preserved, but otherwise accepted.

[tanujkhattar]

I tried this change locally and it's indeed a pretty large breaking change. Specifically, it breaks:

• Existing PointOptimizer based transformers because iteration order (and hence second order effects like inserting new operations in new moments etc.) currently depends upon the insertion order of operations in the moment.
• Serialization of circuits / moments breaks which leads to a domino effect further breaking serialization of objects like QuantumExecutableGroups etc.

I was mainly interested in this change because I wanted to make the iteration order deterministic for new transformer primitives (i.e.merge_operations). I'm now doing that independently in #4764 and would propose to close this issue as this would be a huge breaking change.