Three gates that should have left one behind

I have been building a linter for quantum chemistry setups, nqf-lint. Some of it
is easy. Some of it fights back, mostly the borrow checker. I spend my nights in
there, and around it I keep studying the algorithms I like, VQE and QAOA.

At some point I stopped trusting the simulators underneath all of it. They
looked too tidy. Every run handed me a clean number and never complained about
anything. Nothing that never complains is that correct.

So I wrote a small fuzzer that throws random circuits at them and checks if they
disagree with each other. The first time it stopped and told me two backends did
not match, I was not excited. I assumed the bug was mine.

The bug

It was small enough to hold in your head. Three gates, one qubit.

from qiskit import QuantumCircuit
from qiskit.transpiler import PassManager
from qiskit.transpiler.passes import CommutativeCancellation

qc = QuantumCircuit(1)
qc.sxdg(0)
qc.sxdg(0)
qc.sx(0)

out = PassManager([CommutativeCancellation()]).run(qc)
print(out.count_ops())

On paper those three add up to a quarter turn in the negative direction. One
gate should come out the other side. What comes out is an empty circuit.

OrderedDict()

No error. No warning. Nothing in the logs. The rotation is just gone, and if
you measure that qubit you get a different answer than the one your circuit
says you should get. Nothing tells you why, because as far as the compiler is
concerned nothing went wrong.

I ran it again. I was sure I had typed the command wrong.

If you want to see it yourself, you need pip install qiskit==2.5.0. It is fixed
in 2.5.1, which is the whole point of the rest of this post.

Where I went wrong

So I opened an issue. And I did not stop at "here is a circuit that comes out
wrong". I had read the code, or I thought I had, so I told them why.

What I wrote was this:

Looks like the cause is in the pass itself: _x_rotations includes sx and
sxdg (line 69 of commutative_cancellation.py) and two sxdg get treated as
an inverse pair.

I put "looks like" in front of it. That does not count for much. When you name a
file and a line number, you are not hedging anymore, you are making a claim.

I had come at the problem from several directions by then. There was one
explanation left that I had not tested yet, and that was enough for me. That is
where the certainty came from.

I was wrong. And I was wrong in a worse way than being off by a line.

The answer came the same day, from Jake Lishman, one of the core maintainers:

Thanks for the report, we can get this fixed. The actual root cause is
quite different (all this code is in Rust), and commutative cancellation
is calculating the necessary rotation angle correctly, it just fails to
correctly synthesise that into gates when the combined X rotation is a
negative odd multiple of pi/2 and sx appears to be a supported gate.

Read that first parenthesis again. All this code is in Rust.

I had pointed at a Python file. The logic I was describing does not live in
Python at all, and the part I said was broken was working correctly. The pass
computes the angle right. It fails when it turns that angle back into gates.

So I was not slightly off. I was reading a different file than the one that
runs.

Measuring instead of arguing

Here is the part I want to be honest about, because it is the only part I would
do the same way again.

I did not argue. I wrote this:

Thanks for the quick triage, and for correcting me on the cause. I was
reading the Python and guessed wrong.

And then I went to measure, because that was the only thing I had that was
worth anything. If I could not explain the bug, I could at least map it.

I swept the combined rotation across every multiple of pi/2 from -8 to 8,
forcing exact angles with pairs of rx gates, and checked each result against
the exact operator. It came back with something neither of us had said: it is
not only the odd multiples. There were even multiples failing too.

Then I found something worse, and it was in my own report. I had written that
the bug needed a gate on another qubit sitting between the two sxdg. That was
wrong. It happens on a single qubit, alone, with nothing else in the circuit:

qc = QuantumCircuit(1)
qc.sxdg(0); qc.sxdg(0); qc.sx(0)

I posted that correction against myself before anyone asked for it.

Somewhere in there I stopped trying to be right and started trying to be
useful, and the second one turned out to be much easier.

The line

With the map in hand, the line was not hard to find:

let num_sx = (total_angle / FRAC_PI_2).round();
for _ in 0..(num_sx as i64) % 4 {
    dag.insert_1q_on_incoming_qubit((StandardGate::SX, &[]), cancel_set[0]);
}

In Rust, % keeps the sign of the dividend. So -1 % 4 is -1, not 3. That makes
the loop 0..-1, which is an empty range, so no sx is emitted and the rotation
is dropped on the floor. rem_euclid(4) gives 0..3 for either sign.

I posted it. Jake replied:

Yes, there's a PR (two, actually) linked above your comment that changes
that line.

He had already opened it. My comment was not the fix, and I want to be clear
about that because the timeline is public and anyone can check it. We landed on
the same one line change from different directions, and he got there first.

It was still the best day I have had in a long time.

What I take from it

The habit I actually changed is smaller than a lesson. When I want to write "the
cause is X", I now go and make X happen on purpose first. If I cannot make it
happen, I do not know it yet, and I write what I measured instead.

It sounds obvious written down. It was not obvious at the time, because being
almost sure feels exactly like being sure.

I used it again this week, on someone else's compiler. I thought I had found a
sign error in a gate decomposition, and instead of writing that down I put the
old sign back, ran the test I had just written, and watched it fail. Then I put
the new sign in and watched it pass. Two minutes. That is the whole habit.