Logical schedule sometimes contains superfluous links

[braised-babbage]

Consider the following program

CNOT 0 1
X 1
CNOT 1 2

Naively, one would expect that the dependency graph of these instructions looks like this:

CNOT 0 1
     |
   X 1
     | 
CNOT 1 2

but, if we construct a logical schedule with these instructions, we see something like

CNOT 0 1
  |   |
X 1   |
  |   |
CNOT 1 2

Concretely, what I am showing comes from the following

QUIL> (let ((program (parse-quil "CNOT 0 1; X 1; CNOT 1 2"))
            (lschedule (make-lscheduler)))
        (append-instructions-to-lschedule lschedule (coerce (parsed-program-executable-code program) 'list))
        (alexandria:hash-table-alist (lscheduler-earlier-instrs lschedule)))
((#<CNOT 1 2> #1=#<CNOT 0 1> #2=#<X 1>) (#2# #1#))

with the links representing the earlier relation.

The extra link is superfluous (since the dependency between CNOT 1 2 and CNOT 0 1 is already mediated by X 1), and makes the lscheduler behavior just a bit more confusing than need be. The reason it comes about is evident in the source for append-instruction-to-logical-schedule, since at the point at which CNOT 1 2 is appended, both X 1 and CNOT 0 1 are considered to the bottom. A fix would involve tracking how the bottom instructions partition the set of resources, so that e.g. qubit 1 is considered "owned" by X 1 rather than both X 1 and CNOT 0 1.

IMO, this is not a "real" problem, and probably not worth changing right now as a standalone fix, since the logical scheduling stuff works fine as a whole. It should be kept in mind if we ever do a more serious refactor of the logical scheduling code.

[stylewarning]

This is a good point; I agree there's no reason to rush to fix. (However, it's nice when you can depend on certain invariants being true; if I was a new programmer on the QUILC project and I had to hack on the logical scheduler, I'd perhaps assume that such extra links wouldn't exist, which means I might inadvertently write subtly buggy code.)