router mishandling mid-circuit measurements #6293
Description
Description of the issue
cirq.RouteCQC will sometimes commute gates through mid-circuit measurements in a way that changes the expected outcome
How to reproduce the issue
q0, q1, q2 = cirq.LineQubit.range(3)
circuit = cirq.Circuit(
cirq.CZ(q0, q1),
cirq.CZ(q1, q2),
cirq.CZ(q0, q2),
cirq.measure(q0, q1, q2, key="key"),
cirq.H.on_each(q0, q1, q2),
cirq.measure_each(q0, q21, q2),
)
graph = nx.Graph([[q0, q1], [q1, q2]])
router = cirq.RouteCQC(graph)
print(circuit)
print(router.route_circuit(circuit)[0])prints
0: ───@───────@───M('key')───H───M───
│ │ │
1: ───@───@───┼───M──────────H───M───
│ │ │
2: ───────@───@───M──────────H───M───
0: ───×───────@───────────────@───M──────────H───M('q(2)')───
│ │ │ │
1: ───×───@───@───H───M───×───@───M('key')───H───M('q(0)')───
│ │ │
2: ───────@───────────────×───────M──────────────────────────
where one of the hadamards and one of the terminal measurement have incorrectly been commuted through the mid-circuit measurement
Cirq version
1.3.0.dev20230830191034