Enhance transformers to preserve moment structure and operations order in Circuit

[pavoljuhas]

Is your design idea/issue related to a use case or problem? Please explain

According to #8097 (comment) it is essential to support duplicate measurement keys in a single moment as this allows optimizations of internal QEC experiments. With such key reuse the measurement data form a single stream of bits where it is critical to know the order of measurements so result bits can be assigned to the individual measurement operations with a common key. Currently the cirq transformers such as cirq.map_operations have no guarantee that a transformed circuit would have the same moment structure or the order of transformed operations in a moment. As an example, a map_operation using an identity mapping splits a moment with a duplicate measurement key into two moments:

>>> q0, q1 = cirq.q(0), cirq.q(1)
>>> c = cirq.Circuit(cirq.Moment(cirq.M(q0, key="m"), cirq.M(q1, key="m")))
>>> print(c)

0: ───M('m')───

1: ───M('m')───

>>> c1 = cirq.map_operations(c, lambda op, index: op)
>>> print(c1)

0: ───M('m')────────────

1: ────────────M('m')───

While map_operations has a lot of flexibility in that it allows converting single operation to an OP_TREE it is a frequent the use case that an operation just needs to be transformed to a modified operation (or dropped).

The proposal here is to provide cirq transformers with an option to preserve the moment structure of the circuit and also the order of transformed operations within their moments. Such transformers should provide a native safe conversion for circuits with duplicate measurement keys, and should eliminate workarounds that are currently needed to obtain circuits with a desired order of measurements.

Describe your design idea/issue

The initial idea is to add a preserve_moments flag argument to map_operations which will require the map-function results from a source Moment to be packed to one target Moment in the same order. The transformer would fail if mapped operations cannot fit in a single moment, e.g., if several new operations act on the same qubit.

Before going any further, we need to check with the QEC colleagues to get a full picture of their requirements and understand what should be changed or added to Cirq (within its backward compatibility requirements) to support them.

Refs

• Deprecate overlapping measurement keys for Moment(m1, m2) #8097 (withdrawn)
• Measurement and control keys can overlap in the same moment after circuit.insert #7829 (closed by Fix bug in circuit.insert #7823)

cc: @maffoo

[daxfohl]

Random thought: adopt a convention with HW team where, rather than putting n measurements on the same key in a single moment, they instead make an n-moment subcircuit each with one measurement, and tag the subcircuit "run as single moment". Then have the hardware logic use that key and interpret it accordingly.

That approach would allow you to keep everything consistent in Cirq, and I imagine it would work seamlessly with the existing transformers code: since the effect of a transformation on a subcircuit stays inside that subcircuit, it'd naturally isolate the transformation's effect on those measurements from its effect on the rest of the circuit. Providing this functionality would be a lot harder in a flat circuit, because each transformer would need special casing for some moments versus others.

[pavoljuhas]

Thank you for your suggestion @daxfohl. IIUC, the main reason for the single-moment-duplicate-keys request is to streamline circuits construction and transpilation for the QEC, namely to do away with transformation and tracking of non-unique measurement keys and their results. I suppose the best is to have @maffoo chime in if the suggested approach would work for the QEC needs.

For my part, I am fine with having some inconsistency in how overlap is treated in op-by-op mutations vs explicit Moment construction. Perhaps the case of repeated keys could be thought-of as raw pointers in C++. They are not encouraged, but not prohibited either; one should better be well aware what to do when using them.

[daxfohl]

Just to provide a concrete example, align_left just rebuilds the circuit op-by-op and returns it, which works because circuits are left-aligned by default. But for same-moment-same-key measurements, that's broken because Circuit.append doesn't put same-key measurements in the same moment. So

0: ───M('a')───
1: ───M('a')───

Turns into

0: ───M('a')────────────
1: ────────────M('a')───

If OTOH the convention is to put them in subcircuits with a special "single_moment" tag, then align_right leaves them unchanged, as desired:

      [ 0: ───M('a')──────────── ]
0: ───[                          ]──────────────────
      [ 1: ────────────M('a')─── ][single_moment]
      │
1: ───#2────────────────────────────────────────────

Adding the smarts to align_right to detect multi-measurement-same-key moments and handling them specially would make that transformer's logic a lot more complex and may not even be what all users want, whereas with tagged subcircuits it's all handled automatically and consistently, and doesn't even require any code changes to Cirq itself.

I'm not sure it will work for all use cases though. I think there's a transformer that changes ───X───M─── into ───M!───, pushing bitflips into the terminal measurement. IDK if that would behave the same way if the terminal measurement is in a subcircuit, or how difficult it would be to make that work if it doesn't, or whether that would even be the desired behavior. So it's worth thinking through the cases of various transformers before committing. At least with the tagged subcircuit approach, you can test things today and see which ones behave the way you'd want them to and which ones might not work as desired, and come up with a more concrete list of desired behavior changes.

Also note that HW team could build a transformer to reduce any single_moment subcircuits to an actual multi-measurement-same-key moment as a last step before feeding it to HW, so that way it would be compatible with their existing firmware. I imagine that would be easier than updating the HW execution code itself.

[Adithyaphani]

@pavoljuhas and @mhucka can I work on this?

[Adithyaphani]

Hi, @pavoljuhas, @shatterednirvana and @mhucka , I've studied the _PlacementCache
behaviour and prototyped the preserve_moments flag as proposed — identity
map_operations now preserves single-moment structure for circuits with
duplicate measurement keys. All 47 tests pass with full coverage on both
map_operations and map_operations_and_unroll. PR: #8187 . Looking forward to your review on this PR.

[mhucka]

@Adithyaphani While we don't want to discourage contributors, in this particular case, please note that this issue was already assigned to Pavol. Please wait for him to get a chance to comment on the status of this. He is currently unavailable but will be back soon.

[Adithyaphani]

@mhucka thanks for your response. Okay I will proceed with this PR once , Pavol responds back.