Controlled empty subroutine causes `ValueError` on simulator

[IlanIwumbwe]

Benny and I found this bug

Description of the issue Controlled empty subroutine causes ValueError on simulator

How to reproduce the issue

from cirq import (Circuit, CNOT, CZ, Y, Simulator,
    NamedQubit, InsertStrategy, CircuitOperation, measure)
from pathlib import Path

from pyqir import qubit
from helpers.cirq_helpers import compare_circuits, individual_pass
from cirq.transformers import *

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

subcirc1 = Circuit()
subcirc1.append(CZ(qubits[0],qubits[3]), strategy = InsertStrategy.INLINE)
subcirc1.append(CZ(qubits[3],qubits[0]), strategy = InsertStrategy.INLINE)
subcirc1.append(CNOT(qubits[3],qubits[0]), strategy = InsertStrategy.EARLIEST)
subcirc1_op = CircuitOperation(subcirc1.freeze())

subcirc2 = Circuit()
#subcirc2.append(Y(qubits[0]))
subcirc2_op = CircuitOperation(subcirc2.freeze())

main_circ = Circuit()
main_circ.append(measure(qubits[0], key="cbit0"))
main_circ.append(subcirc1_op.with_classical_controls('cbit0'))
main_circ.append(measure(qubits[1], key="cbit1"))
main_circ.append(subcirc2_op.with_classical_controls('cbit1'))

print(main_circ)
main_circ.append(measure(qubits, key="results"))

simulator = Simulator()
circ = simulator.run(main_circ, repetitions=10)

Uncommenting the Y gate within the subroutine makes this work. Although users may not do something like this, it would probably be nice if this was treated like an identity instead.

``` sh ┌──┐ [ q0: ───@───@───X─── ] q0: ───────M─────[ │ │ │ ]────────────────────────────────── ║ [ q3: ───@───@───@─── ].with_classical_controls(cbit0) ║ ║ q1: ───────╫M────╫──────────────────────────────────────────────────────── ║║ ║ q3: ───────╫╫────#2─────────────────────────────────────────────────────── ║║ ║ cbit0: ════@╬════╩════════════════════════════════════════════════════════ ║ cbit1: ═════@═════════════════════════════════════════════════════════════ [ ].with_classical_controls(cbit1) └──┘ Traceback (most recent call last): File "quantum_circuits/circuit1.py", line 32, in circ = simulator.run(main_circ, repetitions=10) ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ File ".venv/lib/python3.11/site-packages/cirq/work/sampler.py", line 63, in run return self.run_sweep(program, param_resolver, repetitions)[0] ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ File ".venv/lib/python3.11/site-packages/cirq/sim/simulator.py", line 72, in run_sweep return list(self.run_sweep_iter(program, params, repetitions)) ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ File ".venv/lib/python3.11/site-packages/cirq/sim/simulator.py", line 103, in run_sweep_iter records = self._run( ^^^^^^^^^^ File ".venv/lib/python3.11/site-packages/cirq/sim/simulator_base.py", line 245, in _run for step_result in self._core_iterator(circuit=prefix, sim_state=sim_state): File ".venv/lib/python3.11/site-packages/cirq/sim/simulator_base.py", line 220, in _core_iterator protocols.act_on(op, sim_state) File ".venv/lib/python3.11/site-packages/cirq/protocols/act_on_protocol.py", line 141, in act_on result = action_act_on(sim_state) if is_op else action_act_on(sim_state, qubits) ^^^^^^^^^^^^^^^^^^^^^^^^ File ".venv/lib/python3.11/site-packages/cirq/ops/classically_controlled_operation.py", line 187, in _act_on_ if all(c.resolve(sim_state.classical_data) for c in self._conditions): ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ File ".venv/lib/python3.11/site-packages/cirq/ops/classically_controlled_operation.py", line 187, in if all(c.resolve(sim_state.classical_data) for c in self._conditions): ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ File ".venv/lib/python3.11/site-packages/cirq/value/condition.py", line 104, in resolve raise ValueError(f'Measurement key {self.key} missing when testing classical control') ValueError: Measurement key cbit1 missing when testing classical control ```

Cirq version You can get the cirq version by printing cirq.__version__. From the command line: 1.4.1

[daxfohl]

I think this is here: https://github.com/quantumlib/Cirq/blob/d74e0dce73adf45f15b873bf28236ef355d960ce/cirq-core/cirq/sim/simulator.py#L986-L992

This is the code that splits the circuit into a unitary ("predicate/matching") prefix and a non-unitary suffix, so that the result of the unitary prefix can be cached and reused for each repetition, so that only the non-unitary part has to be run subsequently.

It looks like the code places the empty classical controlled circuit in the prefix, since it has no qubits, so it'll get executed before the measurement (which goes in the suffix). I can't remember offhand why that's two separate if blocks. Seems like

            if not predicate(op) or not qs.isdisjoint(blocked_qubits):
                general_part.append(op)
                blocked_qubits |= qs
            else:
                matching_part.append(op)

would be more succinct and fix the error?

However, to be thorough, the function should be revised to take measurement keys into account just like qubits: once an op with a measurement key M has been allocated to the suffix ("general_part"), any subsequent op with the same measurement key M should also go into the suffix. So just set up a "blocked_measurement_keys" set and check those too e.g. if not predicate(op) or not qs.isdisjoint(blocked_qubits) or not keys.isdisjoint(blocked_keys). The normal simulator uses is_unitary as predicate, but other simulators use other predicates, so the same bug might happen in other simulators unless the measurement keys are explicitly taken into account.

[IlanIwumbwe]

I see, that makes sense.

[daxfohl]

I was going to say an even easier fix would be to ensure anything that touches a measurement key should go in the suffix. But it turns out that's actually not always the case: in principle, a classical simulator should put everything in the prefix. The only circuits it can handle are deterministic anyway, so samplers should simulate the circuit once and just return the same result N times rather than re-running the simulation. (Currently it's not implemented that way; one would have to override _can_be_in_run_prefix on ClassicalSimulator to return True always. Granted, nobody is running classical simulations with large repeat counts, but still, it's an easy improvement).

So, long story short, this should be fixed the "right" way by explicitly taking measurement keys into account, as described above.