Inconsistent behavior of Default Insert Strategy

[glanzz]

Description of the issue
The default insert strategy is placing the given list of gates in different positions.
How to reproduce the issue

from cirq.contrib.qasm_import import circuit_from_qasm
from cirq import Simulator, measure_each, X
import cirq as c


circuit = None
with open("mycircuit.qasm", "r") as file:
    circuit = circuit_from_qasm(file.read())


s = Simulator()
qubits = [X(q) for q in circuit.all_qubits()]
circuit.insert(0, qubits)
circuit.append(measure_each(*circuit.all_qubits()))

print(circuit)
REPEATS = 100
result = s.run(circuit,repetitions=REPEATS)

counter = result.multi_measurement_histogram(keys=[key for key in result.measurements])

resultdict = {}
for k in counter:
    key = "".join([str(v) for v in k])
    resultdict[key] = resultdict.get(key, 0) + counter[k]
print(resultdict)

mycircuit.qasm

OPENQASM 2.0;
OPENQASM 2.0;
include "qelib1.inc";
qreg q[7];
id q[6];
h q[4];
cx q[1],q[4];
tdg q[4];
cx q[0],q[4];
t q[4];
cx q[1],q[4];
tdg q[4];
cx q[0],q[4];
t q[1];
t q[4];
cx q[0],q[1];
h q[4];
t q[0];
tdg q[1];
cx q[0],q[1];
h q[3];
cx q[2],q[3];
tdg q[3];
cx q[5],q[3];
t q[3];
cx q[2],q[3];
tdg q[3];
cx q[5],q[3];
t q[2];
t q[3];
cx q[5],q[2];
h q[3];
t q[5];
tdg q[2];
cx q[5],q[2];
ch q[3],q[1];
ch q[0],q[2];
cz q[5],q[6];
ry(3.1383122094800475) q[4];
h q[6];

Run1:

                ┌──┐          ┌──┐       ┌──┐          ┌──┐   ┌──┐          ┌───────────┐   ┌──┐
q_0: ───X──────────────────────@────────────────────────@──────@─────T───────@────────────────@────M───────
                               │                        │      │             │                │
q_1: ───X────────@─────────────┼──────────@─────T───────┼──────X─────T^-1────X───────────────H┼────M───────
                 │             │          │             │                                    ││
q_2: ───X────────┼@────────────┼──────────┼@────T───────┼───────X────T^-1────X───────────────┼H────M───────
                 ││            │          ││            │       │            │               │
q_3: ───X───H────┼X────T^-1────┼X────T────┼X────T^-1────┼X─────T┼────H───────┼───────────────@─────M───────
                 │             ││         │             ││      │            │
q_4: ───X───H────X─────T^-1────X┼────T────X─────T^-1────X┼─────T┼────H───────┼Ry(0.999π)─────M─────────────
                                │                        │      │            │
q_5: ───X───────────────────────@────────────────────────@──────@────T───────@───────────────@─────M───────
                                                                                             │
q_6: ───X───I────────────────────────────────────────────────────────────────────────────────@─────H───M───
                └──┘          └──┘       └──┘          └──┘   └──┘          └───────────┘   └──┘
Counter({(1, 0, 1, 1, 1, 1, 0): 29, (1, 0, 1, 1, 1, 1, 1): 24, (1, 0, 1, 1, 0, 1, 1): 24, (1, 0, 1, 1, 0, 1, 0): 23})
{'1011111': 24, '1011110': 29, '1011010': 23, '1011011': 24}

Run2:

                ┌──┐          ┌──┐       ┌──┐          ┌──┐   ┌──┐          ┌───────────┐   ┌──┐
q_0: ───X──────────────────────@────────────────────────@──────@─────T───────@────────────────@────M───────
                               │                        │      │             │                │
q_1: ───X────────@─────────────┼──────────@─────T───────┼──────X─────T^-1────X───────────────H┼────M───────
                 │             │          │             │                                    ││
q_2: ───X────────┼@────────────┼──────────┼@────T───────┼───────X────T^-1────X───────────────┼H────M───────
                 ││            │          ││            │       │            │               │
q_3: ───H───X────┼X────T^-1────┼X────T────┼X────T^-1────┼X─────T┼────H───────┼───────────────@─────M───────
                 │             ││         │             ││      │            │
q_4: ───H───X────X─────T^-1────X┼────T────X─────T^-1────X┼─────T┼────H───────┼Ry(0.999π)─────M─────────────
                                │                        │      │            │
q_5: ───X───────────────────────@────────────────────────@──────@────T───────@───────────────@─────M───────
                                                                                             │
q_6: ───I───X────────────────────────────────────────────────────────────────────────────────@─────H───M───
                └──┘          └──┘       └──┘          └──┘   └──┘          └───────────┘   └──┘
Counter({(0, 1, 1, 0, 1, 1, 1): 24, (0, 1, 1, 1, 1, 1, 1): 13, (0, 1, 0, 1, 1, 1, 1): 13, (0, 1, 0, 0, 1, 1, 0): 12, (0, 1, 1, 0, 1, 1, 0): 10, (0, 1, 1, 1, 1, 1, 0): 10, (0, 1, 0, 1, 1, 1, 0): 9, (0, 1, 0, 0, 1, 1, 1): 9})
{'0100110': 12, '0101110': 9, '0100111': 9, '0111111': 13, '0110110': 10, '0111110': 10, '0110111': 24, '0101111': 13}

Cirq version
You can get the cirq version by printing cirq.__version__. From the command line:

Cirq Version: 1.4.1

[pavoljuhas]

csynque meeting - H gates for the q_3 and q_4 qubits at the 0 position seem incorrect, indeed it looks like a bug here.

[daxfohl]

The code is pretty hard to follow, but definitely looks like https://github.com/quantumlib/Cirq/blob/main/cirq-core/cirq/circuits/circuit.py#L2167 causes the splitter index to increment (note it passes k to _pick_or_create_inserted_op_moment_index). For some reason, one of the fallback strategies in _pick_or_create_inserted_op_moment_index uses splitter_index - 1. I don't really understand what the intent was for that, but I assume that's why sometimes the insert does work. Otherwise it'd put them on increasing moments.

Also I haven't checked, but i assume circuit.all_qubits() is nondeterministic, so that would account for why sometimes it works and sometimes it doesn't. It most likely depends on whether the first qubit returned already has a gate on the first moment or not.

[daxfohl]

Okay, yeah, if the first qubit already has a gate, it falls all the way back to NEW, and creates a new moment. While splitter_index then becomes 1, all subsequent inserts with EARLIEST either get placed at zero by the EARLIEST strategy if nothing exists in moment 1, or fall back to the INSERT strategy, which places them at splitter_index-1 aka zero.

However if the first qubit does not have a gate, then the EARLIEST strategy just places it at zero without creating a new moment, then subsequently the splitter index is at 1 and so it adds all the Xs to the first moment. For qubits without a gate, the X's fall back to zero, but for qubits that have a gate at moment zero, the X's end up getting placed in moment 1.

But in general the splitter index incrementing in line 2167 seems to assume that all inserted operations are on the same qubits, and will thus be inserted after the other. This is a bad assumption, as this case shows.

So the function needs to track what qubits have been inserted to what indexes, and determine k for each operation based on the intersection of that op's qubits and the qubits that have already been inserted. I assume the desired outcome would be equivalent to splitting the original circuit into pre- and post-index halves, appending the operations one-by-one onto the prefix circuit, and then appending the suffix with concat_ragged (or maybe even just concat). Which, may even be the most efficient way to do it.

Anyway, the behavior for multi-gate inserts in InsertStrategy isn't fully specified, so probably best to start by fleshing out those specs first, then implement however it makes sense.

[daxfohl]

Tried a few things but nothing worked. Biggest issue is here

Cirq/cirq-core/cirq/circuits/circuit.py

Line 2117 in 79d562a

self._moments.insert(splitter_index, Moment())

it inserts a Moment, but say you've got another op in that same batch on a different qubit. If you insert that first, then the above line will move it back. But if you insert it later then it won't.

Here's a minimal test. One could argue, you're doing different things so it's expected the results will be different. Which is valid. But regardless I'd expect both of the below to have two Y gates at the beginning of the circuit.

def test_insert_qubit_order():
    q0, q1 = cirq.LineQubit.range(2)
    c0 = cirq.Circuit(cirq.X(q0))
    c0.insert(0, cirq.Y.on_each(q0, q1))
    c1 = cirq.Circuit(cirq.X(q0))
    c1.insert(0, cirq.Y.on_each(q1, q0))  # opposite order
    assert c0 == c1

[daxfohl]

Found a fix: #6978

I'm not going to merge it yet (in fact I'll close it for now, to keep the PR list clean), because it's ugly and a little slow (test_append_speed about 30% slower). I think it also might need specific handling around measurement keys.

But the idea is, instead of looking at one op at a time, to look at all consecutive new ops that could fit together on one moment, and if any of them would require inserting a new moment, then insert that new moment before placing any of them. That avoids the problem where the earlier ops of that group get shifted forward when the new moment is inserted after they've been placed.

That at least proves out the reason for the problem. I'm not sure I'll have time to fix the perf or clean up the code. If anyone wants to take it over, feel free.

[daxfohl]

Also note that while investigating the issue, I noticed that the existing behavior of INLINE is probably not what we really wanted, or what users would intuitively expect. In particular, test_insert_inline_near_start is odd: why would inserting an op INLINE at empty moment 1 end up placing the op at 0?

Cirq/cirq-core/cirq/circuits/circuit_test.py

Lines 861 to 868 in 79d562a

	def test_insert_inline_near_start():
	a = cirq.NamedQubit('a')
	b = cirq.NamedQubit('b')
	c = cirq.Circuit([cirq.Moment(), cirq.Moment()])
	c.insert(1, cirq.X(a), strategy=cirq.InsertStrategy.INLINE)
	assert c == cirq.Circuit([cirq.Moment([cirq.X(a)]), cirq.Moment()])

My guess is it was a result of the same problem; insert didn't have any other way to tell the loop not to increase the k index to allow subsequent ops on different qubits to be placed moment, since it was only looking at one op at a time. So we just codified the weird behavior as a hack. If we do #6978 to fix the foundational problem, I think it'd make sense to change INLINE to make the behavior more intuitive as well. I made a follow-up commit that addresses this problem daxfohl@0286fa4, and you can see it causes behavior change on two tests, both of which seem to have a more intuitive result (to me at least) after the change. Of course it would be a breaking change, so up to the maintainers.