Deferred Measurement Transformer

[daxfohl]

Is your feature request related to a use case or problem? Please describe.

Create a transformer that implements the Deferred Measurement Principle

Describe the solution you'd like

The transformer would create qubits that correspond to every non-terminal measurement in the circuit (call them q_mkey for this discussion). The measurement ops from e.g. q1 onto mkey1 would be changed to a CX(q1, q_mkey1), and then X(q_mkey1) if there's a bitmask. Any classical controlled operations conditional upon mkey1 would be changed to a conditional operation from q_mkey1. (It would only be compatible with KeyCondition types, not SympyCondition). Then measurement gates for all the q_mkeys would be appended to the end of the circuit (plausibly there would be a use case to make this last step optional).

(The above would be the "straightforward" approach. There are optimizations that can avoid creating new qubits in some circumstances).

Once this is complete, I believe ignore_measurement_results can be deprecated (in a subsequent PR). It seems like it was intended to do something like this at simulation time, but was never fleshed out. That flag had a few notable bugs and no unit tests until I recently just noticed and fixed them, which tells me that the feature isn't being used in the wild, and should be safe to deprecate.

[optional] Describe alternatives/workarounds you've considered

Flesh out ignore_measurement_results logic such that these transformations all occur during runtime of the circuit. We discussed during cirq sync that a transformer would be preferred.

What is the urgency from your perspective for this issue? Is it blocking important work?

P3 - I'm not really blocked by it, it is an idea I'd like to discuss / suggestion based on principle

[Edit: updated issue heavily based on discussion at cirq sync]

[vtomole]

Discussion from Cirq sync: Let's look into how the Deferred Measurement Principle can help us.

[daxfohl]

@tanujkhattar Can you change the tag on this to transformers or optimizers, and mark as triage/accepted? Also can you give a pointer to an example optimizer that has been moved to the newer transformers design that can be used as a template? (Sanity check -- can transformers add qubits to a circuit?)

[daxfohl]

Blocked by #4512, as we need some way of defining the condition "at least one qubit is not zero" to match the classical interpretation of a multi-qubit measurement.

[daxfohl]

This also ends up being fairly difficult to do "right". I have a basic implementation at #4849. That one does the job for basic circuits (except the part where #4512 is required, but that'll be just one line of code), however there are two key things missing.

1. Subcircuits: While not specifically required, it would be nice to preserve subcircuit structure. The linked PR gets around this by flattening the circuit prior to running the deferred measurement algo. This is equivalent physically, but it would be much better to work with if we preserve structure. Doing this requires integrating with with_rescoped_keys protocol, adding that to the new MeasurementKeyQid that the linked PR creates, and also adding it to the ControlledOperation, ControlledGate, and CX classes, so that the links between the deferred measurement and the controlled operations that depend on them stay in place.
2. Measurements: The implementation uses isinstance(MeasurementGate) to identify measurements. At a bare minimum, this overlooks PauliMeasurements, which would need added. However there is now an initiative to add new measurement types, meaning we would need to come up with some abstraction allowing arbitrary measurement types to be supported. My knee-jerk reaction is to create a Gate.as_deferred that by default returns self, but can be overridden in measurement gates to return the corresponding quantum gate. But a lot of that depends on how we decide to create the measurement abstraction.

Granted, these both could be done after the initial implementation, but I think it's better to be thorough here and do it right the first time, rather than have to come back and fix it later. (Especially item 1, since subcircuits are used everywhere and it would be good to see how deep this change goes before committing to the feature. Item 2, I think it would be okay to say non-standard measurements aren't supported initially).

[daxfohl]

RE (1) above, I got this to work here, d69684a, but on second thought I'm reluctant to make an invasive change (it's not that invasive, but still) for a niche feature. I think it's better to keep things self-contained until someone specifically asks for this to preserve subcircuit structure.

For (2), I think it's fair to say that only standard measurement gates are supported in the docstring for now.