`synchronize_terminal_measurements()` misorders measurements with the same key

richrines1 commented 10 months ago

Description of the issue

(not 100% sure this isn't intended behavior)

when two measurements have the same key, reordering them results in a logically different circuit. Transformers like align_left() and align_right() correctly account for this by preventing the reordering of measurements with the same key, but synchronize_terminal_measurements() does not (see below)

How to reproduce the issue

circuit = cirq.Circuit(
    cirq.X(cirq.q(1)),
    cirq.measure(cirq.q(0), key="key1"),
    cirq.measure(cirq.q(1), key="key1"),
    cirq.measure(cirq.q(1), key="key2"),
)

print(circuit)
print(cirq.align_right(circuit))  # no change, as it would require reordering the two measurements with `key="key1"`
print(cirq.synchronize_terminal_measurements(circuit))

prints:

0: ───M('key1')───────────────────────────

1: ───X───────────M('key1')───M('key2')───

0: ───M('key1')───────────────────────────

1: ───X───────────M('key1')───M('key2')───

0: ───────────────────M('key1')───

1: ───X───M('key1')───M('key2')───

where the final circuit is not logically equivalent (the expected measurement outcome for "key1" is flipped)

Cirq version

1.3.0.dev20230830191034

tanujkhattar commented 9 months ago

@richrines1 This is a subtle issue, thanks for raising this! Do you have a real world scenario where this becomes a problem?

Specifically, in Cirq we do not have explicit wires corresponding to classical measurement results. So two operations op1 and op2 have an ordering dependency b/w each other if (a) they either share a qubit (i.e. a quantum wire) or (b) op2 is a classically controlled operation controlled on measurement outcome of op1 (i.e. a hacky version of a classical wire).

In this case, we've run into the scenario where both op1 and op2 are both independent measurement operations but they overwrite their results to the same classical register named "key1". And we don't add an (implicit) edge dependency b/w these two operations by design right now. Whether we should start doing that is a feature request that we can consider but I'm curious to know more about the use case where this came up.

@mpharrigan If we were to do support this use case in Qualtran, I'd imagine the measurement gate would have a RIGHT register for measurement outcome and not a THRU register. In that case as well, op1 and op2 would not have an edge in the explicit compute graph. However, if measurement gates end up having THRU registers for classical outputs, then op1 and op2 would have an explicit edge b/w them. This subtlety is worth keeping in mind when designing for adding support for classical registers in Qualtran.

richrines1 commented 8 months ago

thanks for the response @tanujkhattar! admittedly this came up as a corner case in a test, for which i don't really have a (non-contrived) application. so definitely not a blocking issue

mostly i was surprised by the inconsistency between align_right and synchronize_terminal_measurements:

if i think about measurement keys as classical wires, i guess i wouldn't consider the measurement on qubit 0 as "terminal" because a subsequent operation acts on the same wire. If i were to simulate the circuits above, i'd get a different measurement outcome after applying synchronize_terminal_measurements
if instead there shouldn't be an ordering dependency for measurements with the same key (assuming the key isn't then used in a classically-controlled op), then i'd expect align_right to do the same thing as synchronize_terminal_measurements

(but probably in any realistic application i'd just make sure the keys weren't the same, so afaict this isn't likely to ever be an issue in practice)