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.

          ┌──┐
                 [ 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 <module>
    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 <genexpr>
    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:

Cirq/cirq-core/cirq/sim/simulator.py

Lines 986 to 992 in d74e0dc

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

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.

[NoureldinYosri]

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.

cirq-sync: @daxfohl do you know what was the reason for splitting the circuit into prefix and suffix? and is it still relevant?

[daxfohl]

The reason is in that quote. So for example, if you run a simulation with 100 iterations of a unitary circuit with terminal measurements, then this splitting up allows it to run the unitary prefix once, cache the waveform at that point just prior to measurement, and then run the 100 iterations starting from that waveform and just doing the measurement steps on it, so subsequent iterations get to skip the whole simulation and perform like a sampler. Without this, each iteration would rerun the whole circuit from scratch. Similarly, if there is a channel or classical logic near the end of the circuit, then same thing, the unitary prefix result gets cached and the repetitions can all start over from the first non-unitary spot.

Density matrix simulator overrides the predicate, so mixtures and channels can be included in the prefix but measurements classical controls still cannot.

Is it still relevant?

Should be. But one could argue that in the first case, the user should just use a sampler instead of a simulator. And other cases, IDK how often it occurs in practice that most of the circuit is unitary until the very end. Removing this optimization would adversely affect those cases, but maybe they're infrequent enough not to be worthwhile.