concat_ragged allows measurements to overlap

[daxfohl]

Description of the issue

Circuit.concat_ragged allows measurements and classical controls to commute past each other or overlap, resulting in unexpected behavior or invalid circuits.

How to reproduce the issue

q1, q2 = cirq.LineQubit.range(2)
c1 = cirq.Circuit(cirq.measure(q1, key='a'))
c2 = cirq.Circuit(cirq.measure(q2, key='a'))
c = c1.concat_ragged(c2)
print(c)

Result is two independent measurements to a at the same time.

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

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

Note: classical controls on a measurement key can commute past each other and/or overlap in a single moment; just measurements cannot commute past other measurements or classical controls on the same measurement key.

Cirq version v1.0

[verult]

From Cirq sync - to what extent is classical controls broken by this? cc @MichaelBroughton @tanujkhattar @95-martin-orion

[95-martin-orion]

Pretty broken - see also: #5775

[tanujkhattar]

What is the expected behavior for putting two measurements with the same key on two different qubits? Do we support repeated measurements on different qubits? My understanding was that a measurement with the same key can be repeated only when the qubits on which it acts doesn't change. So, for example, the following also breaks:

In [1]: import cirq

In [2]: q = cirq.LineQubit.range(2)

In [3]: circuit = cirq.Circuit(cirq.measure(q[0], key="a"), cirq.measure(q[1], key="a"))
   ...: 

In [4]: circuit
Out[4]: 
0: ───M('a')────────────

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

In [5]: cirq.Simulator().sample(circuit, repetitions=1000)
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-5-609ed0eb90ae> in <module>
----> 1 cirq.Simulator().sample(circuit, repetitions=1000)

~/quantum/Cirq/cirq-core/cirq/work/sampler.py in sample(self, program, repetitions, params)
    174                 param_values_once = [resolver.value_of(key) for key in keys]
    175                 param_table = pd.DataFrame(data=[param_values_once] * repetitions, columns=keys)
--> 176                 results.append(pd.concat([param_table, result.data], axis=1))
    177 
    178         return pd.concat(results)

~/quantum/Cirq/cirq-core/cirq/study/result.py in data(self)
    370     def data(self) -> pd.DataFrame:
    371         if self._data is None:
--> 372             self._data = self.dataframe_from_measurements(self.measurements)
    373         return self._data
    374 

~/quantum/Cirq/cirq-core/cirq/study/result.py in measurements(self)
    341                 reps, instances, qubits = data.shape
    342                 if instances != 1:
--> 343                     raise ValueError('Cannot extract 2D measurements for repeated keys')
    344                 self._measurements[key] = data.reshape((reps, qubits))
    345         return self._measurements

ValueError: Cannot extract 2D measurements for repeated keys

[95-martin-orion]

@maffoo for comments on same-moment measurements sharing a key.

In my opinion: measurements sharing a key but on different qubits should not commute past each other or be allowed in the same moment. The example @tanujkhattar gave above looks like a bug to me - sampler.py is accessing the 2D data (no repetitions allowed) instead of the 3D records (repetitions allowed).

[maffoo]

A agree that measurements with the same key on different qubits should not be commuted past each other, because that changes the order of results in the measurement record. I think allowing the same key on different qubits within a moment is fine though, because operations in a moment are ordered, and the hardware interface layer does support this. We do need to be careful if we combine measurements with the same key into a moment that we preserve the relative order of the ops.

[maffoo]

The sampler error is a known limitation of the current implementation because we never defined how repeated keys should be mapped into the 2D data frame produced by the sample method, so we intentionally left this code as it was where it would try to access .measurements, which fails if any measurement keys are repeated.

[tanujkhattar]

I think allowing the same key on different qubits within a moment is fine though, because operations in a moment are ordered, and the hardware interface layer does support this.

I don't think ordering of operations within a moment is well defined. Currently, we just preserve insertion ordering in Moment._operations and Moment._sorted_operations is used for equality comparison and diagrams.

[maffoo]

Insertion ordering is what I mean.

[tanujkhattar]

So then the original issue raised is not a bug (because measurements with same key in the same moment are well defined) and we should instead fix the sampler error that I raised (to support measurements with same key on more than one qubit)?

[maffoo]

In my view, measurements overlapping is not a problem as long as we maintain the output order. So, for example, if we have a circuit:

cirq.Circuit(
    cirq.Moment(cirq.measure(a, key='m')),
    cirq.Moment(cirq.measure(b, key='m')),
)

then transforming this into the following would be fine:

# ok; measurement order in the same moment is the same as before
cirq.Circuit(
    cirq.Moment(cirq.measure(a, key='m'), cirq.measure(b, key='m')),
)

but we should not transform it into either of the following, since these change the order of outputs:

# bad; measurement order in the same moment has changed
cirq.Circuit(
    cirq.Moment(cirq.measure(b, key='m'), cirq.measure(a, key='m')),
)

# bad; measurement order in different moments has changed
cirq.Circuit(
    cirq.Moment(cirq.measure(b, key='m')),
    cirq.Moment(cirq.measure(a, key='m')),
)

[daxfohl]

I think this discussion is outside the scope of this issue. This issue is to fix a specific bug. It wouldn't make sense to fix it in a way that makes concat_ragged behave differently from append, and I don't think anyone is suggesting that we do.

Changing the behavior of how measurements are appended and how circuits are constructed is a breaking change that has many implications. If that is a consideration then it should be its own issue. But discussion of that issue should not block this bug fix.

[daxfohl]

Closing due to lack of activity.