prefer shorter sequences during compression with decompilation

[stylewarning]

When we have two equal fidelities resulting from an algebraically reduced program, and an algebraically reduced decompiled program, prefer the one that's shorter.

Fixes issue #801.

[stylewarning]

Adding this secondary length test doesn't feel 100% right, because I'd expect that a proper fidelity calculation would encapsulate program length in some way (aren't imperfect RZ's supposed to do that?). Not that program length matters in and of itself, but it matters when you have two programs of equal execution fidelity. However, it seems economical here to do this secondary test as opposed to re-jiggering the whole fidelity metric. The major negative is that this bug can pop up in other places without addressing the root cause.

Would be curious if @ecpeterson is in staunch opposition of this band-aid.

[ecpeterson]

I’m not opposed. When I was running the show, I had the privilege of not thinking that this output counted as a bug, and so I made no particular effort to stem this behavior — but y’all aren’t wrong to dislike it now.

You’re right that I’d expect fidelity sorting and imperfect RZs to handle this, and I’d advise carefully tracing that or else you’re sure to get bitten elsewhere. Does it really think circuits with and without (R)Zs have the same fidelity? Why?

Re: the actual issue dump, I’m more puzzled why it’s injecting a SWAP to begin with, and then why it preferences anything involving PSWAP.

[ecpeterson]

Robert reminded me out of band that quilc’s early output is from it assessing the in-context fidelity of the nativizers, so one has to skim a ways down in the issue dump before seeing relevant steps.

[notmgsk]

You’re right that I’d expect fidelity sorting and imperfect RZs to handle this, and I’d advise carefully tracing that or else you’re sure to get bitten elsewhere. Does it really think circuits with and without (R)Zs have the same fidelity? Why?

Yes

instructions: (#<CZ 0 1>)
    fidelity: 0.95d0
decompiled instructions: (#<RZ(-pi/2) 1> #<RX(pi/2) 1> #<RZ(0.0) 1>
                          #<RX(-pi/2) 1> #<RZ(-pi) 1> #<RZ(-pi) 0>
                          #<RX(pi/2) 0> #<RZ(0.0) 0> #<RX(-pi/2) 0>
                          #<RZ(-pi/2) 0> #<RZ(pi/2) 1> #<RX(pi/2) 1>
                          #<RZ(0.0) 1> #<RX(-pi/2) 1> #<RZ(0.0) 1> #<RZ(pi) 0>
                          #<RX(pi/2) 0> #<RZ(0.0) 0> #<RX(-pi/2) 0>
                          #<RZ(-pi/2) 0> #<CZ 0 1> #<RZ(pi) 1> #<RX(pi/2) 1>
                          #<RZ(0.0) 1> #<RX(-pi/2) 1> #<RZ(0.0) 1> #<RZ(0.0) 0>
                          #<RX(pi/2) 0> #<RZ(0.0) 0> #<RX(-pi/2) 0>
                          #<RZ(-pi) 0> #<RZ(pi) 1> #<RX(pi/2) 1> #<RZ(0.0) 1>
                          #<RX(-pi/2) 1> #<RZ(-pi) 1> #<RZ(pi) 0> #<RX(pi/2) 0>
                          #<RZ(0.0) 0> #<RX(-pi/2) 0> #<RZ(-pi) 0>)
    fidelity: 0.9087228182846407d0
reduced decompiled instructions: (#<RZ(-pi) 1> #<RZ(-pi) 0> #<CZ 0 1>
                                  #<RZ(-pi) 1> #<RZ(-pi) 0>)
    fidelity: 0.95d0
reduced instructions: (#<RZ(-pi) 1> #<RZ(-pi) 0> #<CZ 0 1> #<RZ(-pi) 1>
                       #<RZ(-pi) 0>)
    fidelity: 0.95d0

Probably because get-fidelity for a near-perfect fidelity RZ gives 1.232595164407831d-32 and adding up a few of those gets lost to floating point precision?

[braised-babbage]

I put my comment in the wrong spot, but what @notmgsk says is correct. Copying below:

I looked into it a bit, and I think the main reason why we can't rely on RZ fidelity in this calculation is just that we lose float precision during the computation. Right now, RZ fidelity is defined to be +near-perfect-fidelity+, which is (- 1 double-float-epsilon). In lscheduler-calculate-log-fidelity we take logs, square this, and then sum the results. So with this set-up, we can't even distinguish between CZ 0 1 and RZ 0; CZ 0 1 (assuming CZ fidelity is 0.95).

QUIL> (+ (expt (log (- 1 double-float-epsilon)) 2) (expt (log 0.95d0) 2))
0.0026310020491279278d0
QUIL> (= * (expt (log 0.95d0) 2))
T

Actually, there's a further thing that lscheduler-calculate-log-fidelity does: it takes a square root at the end.

Without thinking too hard about this, we could at least get around this by managing not fidelities but (log(fidelity))^2, and then setting this to double-float-epsilon for a near perfect fidelity. Also, when making fidelity comparisons, we don't need to take square roots at the end (which can halve our precision), because we just care about relative magnitude for instruction selection.

QUIL> (+ double-float-epsilon (expt (log 0.95d0) 2))
0.002631002049128039d0
QUIL> (> * (expt (log 0.95d0) 2))
T

As a tiebreaking mechanism I can't object to this PR, so I'm fine with it regardless of whether it fixes the "root cause" of #801.

[stylewarning]

Can anybody spare a review approval?

[ecpeterson]

My approvals don’t count 🤷‍♀️