`ValueError: Measurement key missing` when using classically controlled CircuitOperation with controlled subcircuit

[YaegakiY]

Describe the issue

Running the following code raises an unexpected ValueError: Measurement key c missing when testing classical control. The error only occurs when both controlled operations are included inside the subcircuit and when both optimize_for_target_gateset and stratified_circuit transformers are applied.

Explain how to reproduce the bug or problem

To reproduce:

import cirq
from cirq.transformers import *

q = cirq.LineQubit.range(3)
circuit = cirq.Circuit()

sub_circuit = cirq.Circuit()

sub_circuit.append(cirq.MSGate(rads=0.19634954084936207).on(q[0], q[1]).controlled_by(q[2]))
sub_circuit.append(cirq.H(q[1]).controlled_by(q[0]))

sub_op = cirq.CircuitOperation(sub_circuit.freeze()) 
circuit.append(cirq.measure(q[1], key="c"))
circuit.append(sub_op.with_classical_controls("c"))

circuit.append(cirq.measure(q, key="m"))

circuit = optimize_for_target_gateset(circuit)
circuit = stratified_circuit(circuit)

simulator = cirq.Simulator() 
result = simulator.run(circuit, repetitions=5)
print(result.histogram(key='m'))

Traceback (most recent call last): File "C:\Users\fuzzing_cirq\buggy_program\crash\fuzzing_4.py", line 26, in result = simulator.run(circuit, repetitions=5) ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ File "C:\Users\venv\Lib\site-packages\cirq\work\sampler.py", line 68, in run return self.run_sweep(program, param_resolver, repetitions)[0] ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ File "C:\Users\venv\Lib\site-packages\cirq\sim\simulator.py", line 59, in run_sweep return list(self.run_sweep_iter(program, params, repetitions)) ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ File "C:\Users\venv\Lib\site-packages\cirq\sim\simulator.py", line 90, in run_sweep_iter records = self._run( ^^^^^^^^^^ File "C:\Users\venv\Lib\site-packages\cirq\sim\simulator_base.py", line 249, in _run for step_result in self._core_iterator( ^^^^^^^^^^^^^^^^^^^^ File "C:\Users\venv\Lib\site-packages\cirq\sim\simulator_base.py", line 209, in _core_iterator protocols.act_on(op, sim_state) File "C:\Users\venv\Lib\site-packages\cirq\protocols\act_on_protocol.py", line 143, in act_on result = action_act_on(sim_state) if is_op else action_act_on(sim_state, qubits) ^^^^^^^^^^^^^^^^^^^^^^^^ File "C:\Users\venv\Lib\site-packages\cirq\ops\classically_controlled_operation.py", line 205, in _act_on_ if all(c.resolve(sim_state.classical_data) for c in self._conditions): ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ File "C:\Users\venv\Lib\site-packages\cirq\ops\classically_controlled_operation.py", line 205, in if all(c.resolve(sim_state.classical_data) for c in self._conditions): ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ File "C:\Users\venv\Lib\site-packages\cirq\value\condition.py", line 110, in resolve raise ValueError(f'Measurement key {self.key} missing when testing classical control') ValueError: Measurement key c missing when testing classical control

Tell us the version of Cirq where this happens

1.6.0.dev20250702012506

[daxfohl]

Confirmed. This appears to be the same issue as in #6899. The stratify transformer's code naively reverses the circuit by reversing moments, but does not reverse the operations within moments, which does matter because multiple interactions with the same measurement key are allowed in a single moment, and they will be sequenced in the order that they're added to the moment.

Cirq/cirq-core/cirq/transformers/stratify.py

Lines 83 to 90 in a89f5b9

	# Do the same thing, except this time in reverse. This helps for some
	# circuits because it inserts operations at the end instead of at the
	# beginning.
	solution = _stratify_circuit(
	reversed_circuit,
	classifiers=ordered_classifiers,
	context=context or transformer_api.TransformerContext(),
	)[::-1]

.

#6899 fixed this for the align_right transformer, reversing the operations within each moment when it reversed the circuit. So the same fix should be applied here. It's probably worth creating a Circuit.reverse() method to avoid copy-paste, and to reduce the likelihood of this happening in the future.

The example attached to the issue produces a huge circuit after transforming. Here's a much simpler one.

    q0, q1 = cirq.LineQubit.range(2)
    circuit =  cirq.Circuit([
        cirq.measure(q0, key='c'),
        cirq.X(q1).with_classical_controls("c"),
        cirq.X(q0).with_classical_controls("c"),
        cirq.X(q1),
    )
    print(repr(circuit))
    circuit = stratified_circuit(circuit)
    print(repr(circuit))

    simulator = cirq.Simulator()
    simulator.run(circuit)

Note this bug has nothing to do with subcircuits.

[wang-anthony03]

Hi, if no one else is currently working on this issue I'd like to pick it up.

[wang-anthony03]

After creating a Circuit.reverse() method, would it be in scope for this issue to search for naive reversing of circuits and replace those with the new Circuit.reverse() method? Or would it be better to open a new issue for that refactoring?

[daxfohl]

Probably the latter