Infinite loop in expanding native instructions with single-direction 2q gate in chip-spec

[colescott]

When running quilc with a chip-spec file with a one-directional 2q gate, quilc infinite loops on warming addresser cache. This is caused by expand-instruction-to-native-instructions recursing forever, eventually crashing sbcl. From what I can tell, it seems like none of the compilers are able to take a 2q instruction to the reverse gate a b -> gate b a.

The compiler should ideally be able to produce a sequence with SWAPs (in the example chip file, SWAP is native), or signal that it is not able to convert this instruction to native due to chip constraints.

---

Sample 'cycle' in output:

APPLY-TRANSLATION-COMPILERS: Applying #<COMPILER CANONICAL-DECOMPOSITION {1006207E8B}> to CZ 3 2.
    B0-4900 2
    B1-4901 3
    CAN(pi/2, 0.0, 0.0) 3 2
    A0-4902 2
    A1-4903 3
APPLY-TRANSLATION-COMPILERS: Applying #<COMPILER EULER-ZXZ-COMPILER {10017993CB}> to B0-4900 2.
    RZ(-pi/2) 2
    RX(0.0) 2
    RZ(-pi) 2
APPLY-TRANSLATION-COMPILERS: Applying #<COMPILER EULER-ZXZ-COMPILER {10017993CB}> to B1-4901 3.
    RZ(-pi) 3
    RX(0.0) 3
    RZ(-pi/2) 3
APPLY-TRANSLATION-COMPILERS: Applying #<APPROXIMATE-COMPILER NEAREST-CZ-CIRCUIT-OF-DEPTH-1 {100170FD6B}> to CAN(pi/2, 0.0, 0.0) 3 2.
    B0-4904 2
    B1-4905 3
    CZ 3 2
    A0-4906 2
    A1-4907 3
APPLY-TRANSLATION-COMPILERS: Applying #<COMPILER EULER-ZXZ-COMPILER {10017993CB}> to B0-4904 2.
    RZ(pi/2) 2
    RX(0.0) 2
    RZ(0.0) 2
APPLY-TRANSLATION-COMPILERS: Applying #<COMPILER EULER-ZXZ-COMPILER {10017993CB}> to B1-4905 3.
    RZ(pi) 3
    RX(0.0) 3
    RZ(-pi/2) 3

Code to reproduce:

(let ((*compiler-noise* t)
      (chip (read-chip-spec-file "reproduce-loop.qpu"))
      (inst (vnth 0 (parsed-program-executable-code (parse-quil "CZ 3 2")))))
  (expand-instruction-to-native-instructions inst chip))

With the qpu file at https://gist.github.com/colescott/fbc58818bf61ed9d2e546b3883c5564b. Note that CZ 2 3 is native but CZ 3 2 is not.

[karlosz]

Well, one valid sequence for CZ 3 2 on this chip architecture would be:

SWAP 2 3
CZ 2 3
SWAP 2 3

Now, the question is what in the compiler needs to understand that SWAP can help with chip topology in this case.

[karlosz]

As a first step to tackling this bug, PR #783 at least endows the nativizer with the ability to signal an error in this situation rather than just infinite looping. I had though it was enough to catch this error when computing single operation bounds but somewhere else in the greedy addresser is unable to understand that swaps can appropriately be inserted.