Circuit.insert has odd edge cases

[daxfohl]

I noticed a few oddities when investigating #6711 (comment). Documenting these here.

Of these, I'd say test_7 is the only one we might want to preserve, as it is the documented behavior. test_1 might also fall into the "let's preserve" category, because it doesn't necessarily do the wrong thing, and because Hyrum's law. The remainder seem like bugs that should be fixed (with the outputs of test_4 and test_6 being the corrected behavior of test_3 and test_5 respectively).

If we do want to change test_7, the algorithm would be "Insert at [i] if available. If not, try [i-1]. Last resort, create new moment at [i] and put it there". All equivalent to "put it at [i], or just before [i] if something is already there."

def test_1():
    q = cirq.LineQubit(0)
    c = cirq.Circuit(cirq.Moment(cirq.X(q)), cirq.Moment(), cirq.Moment(cirq.Z(q)))
    print(c)
    c.insert(1, cirq.Y(q), strategy=cirq.InsertStrategy.INLINE)
    print(c)

# 0: ───X───────Z───

# 0: ───X───Y───────Z───  # Creates extra moment unnecessarily

def test_2():
    q = cirq.LineQubit(0)
    c = cirq.Circuit(cirq.Moment(cirq.X(q)), cirq.Moment(), cirq.Moment(), cirq.Moment(cirq.Z(q)))
    print(c)
    c.insert(3, cirq.Y(q), strategy=cirq.InsertStrategy.EARLIEST)
    print(c)

# 0: ───X───────────Z───

# 0: ───X───────Y───Z───  # EARLIEST was requested

def test_3():
    a, b = cirq.LineQubit.range(2)
    c = cirq.Circuit(cirq.Moment(cirq.X(a)))
    print(c)
    c.insert(1, cirq.Y.on_each(b, a), strategy=cirq.InsertStrategy.INLINE)
    print(c)

# 0: ───X───

# 0: ───X───Y───
# 1: ───Y───────  # Seems like both Y's should go on moment[1], or maybe both to moment[0] (if you've read the docs about INLINE going to moment[i-1]), but this result puts them in two different moments, which is the least intuitive option.

def test_4():
    a, b = cirq.LineQubit.range(2)
    c = cirq.Circuit(cirq.Moment(cirq.X(a)))
    print(c)
    c.insert(1, cirq.Y.on_each(a, b), strategy=cirq.InsertStrategy.INLINE)  # opposite order from test_3
    print(c)

# 0: ───X───

# 0: ───X───Y───
# 1: ───────Y───  # Matches intuition, but inconsistent with test_3

def test_5():
    a, b = cirq.LineQubit.range(2)
    c = cirq.Circuit(cirq.Moment(cirq.X(a)))
    print(c)
    c.insert(0, cirq.Y.on_each(b, a), strategy=cirq.InsertStrategy.EARLIEST)
    print(c)

# 0: ───X───

# 0: ───X───Y───  # Insert to moment[0] ends up in moment[1] 
# 1: ───Y───────

def test_6():
    a, b = cirq.LineQubit.range(2)
    c = cirq.Circuit(cirq.Moment(cirq.X(a)))
    print(c)
    c.insert(0, cirq.Y.on_each(a, b), strategy=cirq.InsertStrategy.EARLIEST)  # opposite order from test_5
    print(c)

# 0: ───X───

# 0: ───Y───X───  # Matches intuition, but inconsistent with test_5
# 1: ───Y───────

def test_7():
    q = cirq.LineQubit(0)
    c = cirq.Circuit(cirq.Moment(), cirq.Moment(), cirq.Moment(cirq.Z(q)))
    print(c)
    c.insert(1, cirq.Y(q), strategy=cirq.InsertStrategy.INLINE)
    print(c)

# 0: ───────────Z───

# 0: ───Y───────Z───  # This is the documented behavior but I think not what most users would expect

These would all be "fixed" by the commit in the comment linked above, which looks ahead for ops that would create new moments, and creates them preemptively instead of op-by-op. But it would break anything that was for some reason dependent on this behavior. I didn't notice any cases of that in existing code, other than two test cases in circuit_test equivalent to test_7 and test_3 above.