Incorrect behaviour when inserting classical control circuit element, causing ValueError

[Bennybenassius]

Description of the issue
Under specific circumstances, it seems that classical controls are inserted wrongly and causing errors when getting measurement keys.

How to reproduce the issue

Run the following code:

from cirq import *
from cirq.transformers import *
import numpy as np

all_passes = { "align_left": align_left, "align_right": align_right}

def individual_pass(circ : Circuit, circ_num : int, pass_to_do : str):
	simulator = Simulator()
	shots = 1024

	# Takes the modified copy of circ
	if pass_to_do == "merge_k_qubit_unitaries":
		circ_new = all_passes[pass_to_do](circ, k=np.random.randint(1, 5))
	else :
		circ_new = all_passes[pass_to_do](circ)
	c_orig = simulator.run(circ, repetitions=shots).histogram(key="results")
	c_new = simulator.run(circ_new, repetitions=shots).histogram(key='results')

# Adding qubits 
qubits = NamedQubit.range(6, prefix="q")

main_circ = Circuit()

main_circ.append(measure(qubits[4], key="cbit0"))
main_circ.append(ry(0.645000).on(qubits[1]).with_classical_controls('cbit0'), strategy=InsertStrategy.INLINE) #Comment me out
# main_circ.append(ry(0.645000).on(qubits[1]).with_classical_controls('cbit0'), strategy=InsertStrategy.EARLIEST) #Uncomment me for working circuit

main_circ.append(measure(qubits, key="results"))
print(main_circ)
individual_pass(main_circ, 26, "align_right")
#individual_pass(main_circ, 26, "align_left") #Or uncomment me

The code above will run into an issue where the ry gate with classical controls will return an error where it cannot find the key cbit0, even though it was inserted before it.

Changing the circuit such that the passes use an insert strategy of EARLIEST or NEW_THEN_INLINE would make it work. Changing the pass to apply on the circuit to align_left instead would also make the circuit not throw an exception, however the resulting circuit would look the same as the wrong one. The commented lines of code above can be uncommented to demonstrate this.

Circuit that doesn't work looks like this:

          ┌───────────┐
q0: ──────────────────────M('results')───
                          │
q1: ────────Ry(0.205π)────M──────────────
            ║             │
q2: ────────╫─────────────M──────────────
            ║             │
q3: ────────╫─────────────M──────────────
            ║             │
q4: ───────M╫─────────────M──────────────
           ║║             │
q5: ───────╫╫─────────────M──────────────
           ║║
cbit0: ════@^════════════════════════════
          └───────────┘

This also throws an error:

ValueError: Measurement key cbit0 missing when testing classical control

Circuit that works looks like this:

q0: ───────────────────────M('results')───
                           │
q1: ──────────Ry(0.205π)───M──────────────
              ║            │
q2: ──────────╫────────────M──────────────
              ║            │
q3: ──────────╫────────────M──────────────
              ║            │
q4: ──────M───╫────────────M──────────────
          ║   ║            │
q5: ──────╫───╫────────────M──────────────
          ║   ║
cbit0: ═══@═══^═══════════════════════════

Using align right would give the same looking circuit without any exceptions thrown:

          ┌───────────┐
q0: ──────────────────────M('results')───
                          │
q1: ────────Ry(0.205π)────M──────────────
            ║             │
q2: ────────╫─────────────M──────────────
            ║             │
q3: ────────╫─────────────M──────────────
            ║             │
q4: ───────M╫─────────────M──────────────
           ║║             │
q5: ───────╫╫─────────────M──────────────
           ║║
cbit0: ════@^════════════════════════════
          └───────────┘

Cirq version

1.4.1

[daxfohl]

Looks like the INLINE strategy here

Cirq/cirq-core/cirq/circuits/circuit.py

Lines 2095 to 2098 in d74e0dc

	if strategy is InsertStrategy.INLINE:
	if 0 <= splitter_index - 1 < len(self._moments) and self._can_add_op_at(
	splitter_index - 1, op
	):

, the _can_add_op_at it calls doesn't take measurement keys into account. This seems like it would also allow for creating multiple measurement ops measuring to the same key in the same moment.

[dyates]

I am interested in taking this as my first issue.