Proposal: remove the uniqueness constraint on measurement keys

[maffoo]

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

Cirq circuits allow doing repeated measurements. This is particularly important in error correction experiments which typically include multiple "rounds" of an error detection circuit where syndrome qubits are measured. The classical data is then used to detect and correct errors.

Each measurement gate in cirq has a key that is used to identify data for that measurement in the cirq.Result object. The data for a measurement is a 2D array of shape (n_repetitions, n_qubits) where the first axis indexes the repetitions of the circuit, and the second axis indexes qubits that were measured.

Currently, measurement keys within a circuit must be unique within a circuit, which leads to some complexity:

• When building circuits with "control flow" using CircuitOperation, we need to be able to remap keys so that we can distinguish measurements from a subcircuit included more than once.
• When using a CircuitOperation with repetitions, we need to included "repetition ids" to distinguish measurements coming from each repetition of the subcircuit. This leads to some complicated logic and required the introduction of the cirq.MeasurementKey object to replace plain string keys.
• In some important applications such as error correction simulations with stim, we want to be able to describe error "detectors" that relate successive measurements on one or more qubits. In stim, this can be done by using relative indexing of targets to specify previous gates. This essentially treats measurements as being appended to a stream (the "measurement record" in stim). In current cirq where each instance of a measurement gate may have a different key, such relative indexing does not work and we would instead have to compute the key for a specific previous measurement (which is particularly complicated in the presence of loops, for example).

Describe your design idea/issue

I propose that we drop the requirement that measurement keys have to be unique. If measurements with the same key appear multiple times in a circuit (or in a looped CircuitOperation), they would get combined into a single data array in the result object. These arrays would have a new "instance" axis to account for this, so the data for each key would now be a 3D array of shape (n_repetitions, n_instances, n_qubits). This data would be made available via a new dict-like attribute on cirq.Result. For compatibility, the existing measurements attribute would still be available if n_instances is 1 for all measurements, as is the case in all circuits that are currently supported. Would have to determine how the new format would map to a pands dataframe as in the current cirq.Result.data property.

Another question TBD is whether measurements with the same key would be required to measure the same qubits. The simplest thing would probably be to require the same qubits (in the same order) on each instance of a particular measurement key in a circuit, as this would make it easy to interpret the result data. However, one could instead allow each instance to measure different qubits, or the same qubits in a different order, since we just need to be able to append a "row" to the result array for each measurement instance; this would put the burden on the user to interpret the data for each instance by remembering which qubits were measured each time (we would have to restrict that the same measure key cannot appear multiple times within a moment since there would be no way to order the results from measurements within a moment). I would lean toward requiring the same ordered qubits on each instance initially, though this restriction could perhaps be relaxed in the future.

[maffoo]

I had imagined that reusing the same key with instances with different n_qubits would be an error. If we think of a key as naming a classical register, that register would have a certain bit width and I probably would want each "write" to the register to write a full "word" instead of packing bits. But you might be able to do womething like write one qubit measurement to an 8-bit wide register by padding it with zeros.

[95-martin-orion]

I'm not opposed to this proposal at the conceptual level, but there are several related issues (#4040, #3721, #3868) which have ongoing work that operates under the assumption that measurement keys are unique. I've set up a meeting for us to go over these in more detail.

[smitsanghavi]

Classical control flow (#3232 and #3234) will add more complexity here. I was going through the repetition_id RFC and noticed that I had considered the option of removing the uniqueness constraint instead and noted an important downside there:

For future classically conditioned and flow control use cases, some of the instances of the measurements may be skipped at runtime. Not differentiating the measurement keys would make interpreting the results more difficult since we don’t know which ones were performed.

We may be able to get around this by some special casing but it won't be very clean.

[daxfohl]

Should this also update circuit.append so that measurement key also serves as a hard stop, like qubits do?

i.e. if user appends a measurement on q1 and then a measurement on q2 both to the same key, they probably intended for the q2 measurement to happen after q1.

Would we want to allow multiple distinct measurement ops with the same key within a single moment? (If we treat keys like qubits then the answer here is no. Which seems fine because you can just use a regular multi-qubit measurement op if that's what you want)

[daxfohl]

Also, rather than storing a whole extra dimension, would a measurement_op parameter on cirq.measure be sufficient? It could have values like {uniquewrite (current behavior), overwrite, xor, and, or, ignore}. So you could do something like measure(q0, key='a'), measure(q1, key='a', measurement_op='xor'), which would allow 'a' to remain a boolean creg containing the xor of the two measurements? (And possibly measurement_op can eventually take a sympy expression if you need something more complex).

This would be strictly less powerful than storing the entire array, but it would also be a less invasive change, and wouldn't change the output dataframe types at all. Would it cover the real-world use cases?

[maffoo]

Would we want to allow multiple distinct measurement ops with the same key within a single moment?

I think this is an central question to answer. We can allow this if ordering of ops within a moment is preserved, because otherwise when interpreting results one wouldn't be able to tell which bits came from which measurements in a moment. I think the order is preserved in the current implementation of Moment since it uses a tuple internally, but I don't think we explicitly guarantee this, and there may be places, for example in transformers, where we collect ops in a moment into sets and potentially change the ordering. Multi-qubit op in a moment also doesn't really behave the same way if the goal is to append the data from two measurements into a single "stream" of data, since the multi-qubit measurement would create a stream of a different shape (different number of qubits).

Re: measurement op, this is an interesting idea, but would not cover the use cases I have in mind since we need to preserve all the data. But It's something we could potentially do in the future.

[daxfohl]

I think I'd like to give this a shot. I think we can do it in a way that's still compatible with the existing measurement key paths.

1. Expand ClassicalDataStore with the extra dimension
2. Remove the exception if a measurement is repeated and just toss it into the extra dimension (option: require an measure(q, key=k, append=True) flag to allow this.
3. Ensure the generated log_of_measurement_results grabs the most recent index. (Eventually we're deprecating that property so this is just temporary).
4. Add an optional index property to Condition to specify which index to use in classical controls (default -1).
5. Add a flatten_indexes (or something) parameter to CircuitOperation that causes repetition keys to behave as repeated, without adding a new path segment.
6. Augment Result with the new dimension (or create a new subclass).

I feel like this could be a nice addition, and would meld well with #4884 and #3266 to augment our classical logic capabilities.

[Strilanc]

This would definitely make interop between stim and cirq a lot easier.

[maffoo]

Thanks to @95-martin-orion, we now have an official RFC for this proposal.

[daxfohl]

@maffoo Can this now be marked complete?

@Strilanc is there anything else you'd want for stim interop? There's possibly a repeat-until feature on the way #5018, if that applies.

[maffoo]

@daxfohl, yes, marking this complete. There will likely be follow-up changes, but the main feature is there.