Measurement and control keys can overlap in the same moment after circuit.insert

[codrut3]

Describe the issue

circuit.insert uses a helper method _group_into_moment_compatible to group operations that can be placed in the same moment, before attempting to insert them.

_group_into_moment_compatible doesn't check measurement and control keys, and so two possibly incompatible operations can be placed in the same moment.

Note that this happens only if strategy EARLIEST is used with an insertion index less than the number of moments. If the operations are always appended at the end of the circuit, then _PlacementCache is used, which checks for measurement and control keys.
Other helper methods for circuit.insert also check measurement and control keys (example).

It seems to me circuit.insert is inconsistent and I would like to understand what needs to be checked:

• can two operations that measure qubits and have the same measurement key be in the same moment? For example, cirq.measure(q0, key="k") and cirq.measure(q1, key="k").
• can two operations that use the same key for measurement and control be in the same moment? For example, cirq.measure(q0, key="k") followed by cirq.X(q1).with_classical_controls("k").

See also this comment by @daxfohl that mentioned that multiple measurements to the same key in the same moment was a requirement from the HW team.

Adding @ikd-sci and @chriseclectic for feedback if the current behavior is needed in some situations.

Explain how to reproduce the bug or problem

import cirq

q0, q1 = cirq.LineQubit.range(2)
c = cirq.Circuit(cirq.X(q0), cirq.X(q1))
ops_to_insert = [cirq.measure(q0, key="k"), cirq.X(q1).with_classical_controls("k")]
c.insert(0, ops_to_insert, strategy=cirq.InsertStrategy.EARLIEST)

print(repr(c))

Output:

cirq.Circuit([
    cirq.Moment(
        cirq.measure(cirq.LineQubit(0), key=cirq.MeasurementKey(name='k')),
        cirq.ClassicallyControlledOperation(cirq.X(cirq.LineQubit(1)), [cirq.KeyCondition(cirq.MeasurementKey(name='k'))]),
    ),
    cirq.Moment(
        cirq.X(cirq.LineQubit(0)),
        cirq.X(cirq.LineQubit(1)),
    ),
])

Tell us the version of Cirq where this happens

1.7.0.dev0

[dstrain115]

Adding triage/discuss so that this pops up next cirq cync to remind us all to ping people for comments/reviews.

[chriseclectic]

can two operations that measure qubits and have the same measurement key be in the same moment? For example, cirq.measure(q0, key="k") and cirq.measure(q1, key="k").

Yes, this should be supported. As long as the measure instructions are on the same number of qubits, this is a valid moment.

can two operations that use the same key for measurement and control be in the same moment? For example, cirq.measure(q0, key="k") followed by cirq.X(q1).with_classical_controls("k").

My intuition is that these should have to go in a different moment, but I would like to discuss with the compiler team. I would expect if you put these in the same moment, a wave form compiler would necessarily have to split them up so that the X gate is delayed until the readout and feedback completes which will have some latency.

[pavoljuhas]

@codrut3 - I discussed this with @chriseclectic and can confirm his summary from the previous comment. We should keep allowing multiple measurements in the same moment using the same key.

As for the measure and controlled operations it makes sense to put them to separate moments so there is no ambiguity in the control value used. This is not yet used in compiler so it should be a low-risk change.

Can you please update #7823 along those lines?

[daxfohl]

Maybe some flag should be added to specify behavior here? Changing existing behavior might break other existing users, and a flag seems reasonable since different users may want different behavior. I imagine other quantum devices might not be able to support multiple measurements to the same key in the same moment. At a minimum, anything that changes circuit construction results should probably be labeled as breaking.

Either way, there should probably be a unit test to check that appending multiple measurements to the same key will not create a new moment for each. I know it's come up a couple times as "hey this is weird, we should change it" (including by me), so having a test there would make it clear that it's actually the desired behavior.