A* swap search takes "forever" when compiling some benchmarking files

[appleby]

Compiling the following program takes a racoon's age (maybe infiniloop):

(let ((quil::*addresser-swap-search-type* :a*))
  (time (quil::compiler-hook (quil::read-quil-file #P"benchmarking/quil-rewiring/0005q-0000160.quil")
                 (quil::build-nQ-linear-chip 20))))

I noticed this while looking into another CL-QUIL-BENCHMARKING issue (#346). I'm not certain whether the search is infinite looping or just taking a really long time. Definitely doesn't finish within ~5 mins, whereas compiling with the default :GREEDY-QUBIT swap search strategy takes ~1.5 seconds.

(time (quil::compiler-hook (quil::read-quil-file #P"benchmarking/quil-rewiring/0005q-0000160.quil")
                   (quil::build-nQ-linear-chip 20)))
Evaluation took:
  1.621 seconds of real time
...

The same issue occurs when compiling other high-gate-depth files under benchmarking/quil-rewiring, like 0008q-0000418-qaoa-8-5.quil and 0020q-0000654-johannes.quil.

Git bisect points to the swap fidelity commit (30882c05). Prior to 30882c05, compiling with :A* swap search takes about the same time as :GREEDY-QUBIT does after:

;; with git HEAD pointing to 942b107d
(let ((quil::*addresser-swap-search-type* :a*))
  (time (quil::compiler-hook (quil::read-quil-file #P"benchmarking/quil-rewiring/0005q-0000160.quil")
                             (quil::build-nQ-linear-chip 20))))
Evaluation took:
  1.290 seconds of real time
....

[appleby]

*COMPILER-NOISE-STREAM* output appears to be stuck in loop applying EULER-YZY-COMPILER H 2 -> RY-TO-XZX RY(-3*pi/4) 2 -> RY-TO-XZX RY(-pi/4) 2 -> EULER-YZY-COMPILER H 2 -> ...

DEQUEUE-LOGICAL-TO-PHYSICAL: entering dequeueing phase.
APPLY-TRANSLATION-COMPILERS: Applying #<COMPILER EULER-YZY-COMPILER {10057303FB}> to H 2.
    RY(-3*pi/4) 2
    RZ(-pi) 2
    RY(-pi/4) 2
APPLY-TRANSLATION-COMPILERS: Applying #<COMPILER RY-TO-XZX {1003413C7B}> to RY(-3*pi/4) 2.
    RX(pi/2) 2
    RZ(-3*pi/4) 2
    RX(-pi/2) 2
APPLY-TRANSLATION-COMPILERS: Applying #<COMPILER RY-TO-XZX {1003413C7B}> to RY(-pi/4) 2.
    RX(pi/2) 2
    RZ(-pi/4) 2
    RX(-pi/2) 2
APPLY-TRANSLATION-COMPILERS: Applying #<COMPILER EULER-YZY-COMPILER {10057303FB}> to H 2.
    RY(-3*pi/4) 2
    RZ(-pi) 2
    RY(-pi/4) 2
APPLY-TRANSLATION-COMPILERS: Applying #<COMPILER RY-TO-XZX {1003413C7B}> to RY(-3*pi/4) 2.
    RX(pi/2) 2
    RZ(-3*pi/4) 2
    RX(-pi/2) 2
APPLY-TRANSLATION-COMPILERS: Applying #<COMPILER RY-TO-XZX {1003413C7B}> to RY(-pi/4) 2.
    RX(pi/2) 2
    RZ(-pi/4) 2
    RX(-pi/2) 2
APPLY-TRANSLATION-COMPILERS: Applying #<COMPILER EULER-YZY-COMPILER {10057303FB}> to H 2.
    RY(-3*pi/4) 2
    RZ(-pi) 2
    RY(-pi/4) 2
... many repitions of above sequence ...
DEQUEUE-LOGICAL-TO-PHYSICAL: entering dequeueing phase.
APPLY-TRANSLATION-COMPILERS: Applying #<COMPILER EULER-YZY-COMPILER {10057303FB}> to H 2.
    RY(-3*pi/4) 2
    RZ(-pi) 2
    RY(-pi/4) 2
...

[ecpeterson]

Weird. Where is the H even coming from?

[appleby]

This compiling the benchmarking/quil-rewiring/0005q-0000160.quil file, which has 11 H 2 applications. Not sure yet if it's stuck on the same one or if those are different instances, but there are many more than 11 attempts to apply the EULER-YZY-COMPILER to an H 2.

[appleby]

Going to let it run for a bit over lunch while logging to a file. Logging to stdout slows things to a crawl, so maybe it will get itself unstuck and/or get stuck somewhere else... will report back later.

[appleby]

Let it run for 10 minutes, and the tail end of the logs look identical to the snippet I posted above.

[appleby]

Appears to only be an issue for the fidelity addresser. Temporal addresser still runs in about the same time as before the fidelity changes.

(let ((quil::*addresser-swap-search-type* :a*)
      (quil::*default-addresser-state-class* 'quil::temporal-addresser-state))
       (time (quil::compiler-hook (quil::read-quil-file #P"/Users/mappleby/src/repos/rigetti/quilc/benchmarking/quil-rewiring/0005q-0000160.quil")
                 (quil::build-nQ-linear-chip 20))))
Evaluation took:
  1.651 seconds of real time

[appleby]

Managed to scrounge it down to a smaller repro case. The following 13-line prefix of benchmarking/quil-rewiring/0005q-0000160.quil fails to compile in under 5 minutes. If I remove any one line from that program, it compiles in under 5 seconds, usually in under 0.5 seconds.

H 0
H 1
H 2
H 3
H 4
X 0
PHASE(4.3806879867915676) 0
X 0
PHASE(4.3806879867915676) 0
CNOT 0 4
RZ(2.1903439933957838) 4
CNOT 0 4
CNOT 1 4

[appleby]

Slightly simpler example consisting of only X, RX, and CZ. This feels like a sufficiently simple case to just start poking it with a debugger.

X 0
X 1
X 2
X 3
X 4
X 0
X 0
X 0
X 0
CZ 0 4
RX(0.0) 4
CZ 0 4
CZ 1 4

[appleby]

An extra tidbit. If I compile the above program of X/RX/CZ with a chip spec of (build-nQ-linear-chip 20), then it does not terminate within ~12 hours. If I reduce the size of the chip from 20 to 19 qubits, it takes about 14 seconds to compile. For 18 qubits, about 1.4 seconds.

[appleby]

Shelving this for now to work on something else. Parting note to self. Here is a snippet from the logs when compiling the example here with a 20q linear chip:

...
DEQUEUE-LOGICAL-TO-PHYSICAL: entering dequeueing phase.
DEQUEUE-LOGICAL-TO-PHYSICAL: entering dequeueing phase.
DEQUEUE-LOGICAL-TO-PHYSICAL: entering dequeueing phase.
SEARCH-REWIRING: Iterations 2002
EMBED-SWAP: New rewiring: #S(CL-QUIL::REWIRING :L2P #(10 13 17 1 0 NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL) :P2L #(4 3 NIL NIL NIL NIL NIL NIL NIL NIL 0 NIL NIL 1 NIL NIL NIL 2 NIL NIL))
EMBED-SWAP: New rewiring: #S(CL-QUIL::REWIRING :L2P #(10 13 17 1 0 NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL) :P2L #(4 3 NIL NIL NIL NIL NIL NIL NIL NIL 0 NIL NIL 1 NIL NIL NIL 2 NIL NIL))
EMBED-SWAP: New rewiring: #S(CL-QUIL::REWIRING :L2P #(10 13 17 1 0 NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL) :P2L #(4 3 NIL NIL NIL NIL NIL NIL NIL NIL 0 NIL NIL 1 NIL NIL NIL 2 NIL NIL))
EMBED-SWAP: New rewiring: #S(CL-QUIL::REWIRING :L2P #(10 13 17 1 0 NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL) :P2L #(4 3 NIL NIL NIL NIL NIL NIL NIL NIL 0 NIL NIL 1 NIL NIL NIL 2 NIL NIL))
EMBED-SWAP: New rewiring: #S(CL-QUIL::REWIRING :L2P #(10 13 17 1 0 NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL) :P2L #(4 3 NIL NIL NIL NIL NIL NIL NIL NIL 0 NIL NIL 1 NIL NIL NIL 2 NIL NIL))
EMBED-SWAP: New rewiring: #S(CL-QUIL::REWIRING :L2P #(10 13 17 1 0 NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL) :P2L #(4 3 NIL NIL NIL NIL NIL NIL NIL NIL 0 NIL NIL 1 NIL NIL NIL 2 NIL NIL))
EMBED-SWAP: New rewiring: #S(CL-QUIL::REWIRING :L2P #(9 13 17 1 0 NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL) :P2L #(4 3 NIL NIL NIL NIL NIL NIL NIL 0 NIL NIL NIL 1 NIL NIL NIL 2 NIL NIL))
EMBED-SWAP: New rewiring: #S(CL-QUIL::REWIRING :L2P #(9 13 17 1 0 NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL) :P2L #(4 3 NIL NIL NIL NIL NIL NIL NIL 0 NIL NIL NIL 1 NIL NIL NIL 2 NIL NIL))
ADDRESSER-FSM: New pass.
DEQUEUE-LOGICAL-TO-PHYSICAL: entering dequeueing phase.
ADDRESSER-FSM: LSCHED unchanged, selecting a permutation.
SELECT-AND-EMBED-A-PERMUTATION: entering SWAP selection phase.
DEQUEUE-LOGICAL-TO-PHYSICAL: entering dequeueing phase.
...

Why is embed-swap embedding swaps that don't appear to change the working l2p (presumably swaps on qubits that aren't wired?).

[ecpeterson]

Perhaps this is the same logical / physical discrepancy that Mark is presently working on.

[appleby]

I was hoping that might be the case. Was planning to take a closer look and take his PR for test drive once the test failures there are resolved.

[appleby]

Was hoping the fix for #534 might coincidentally resolve this issue as well, but it seems not.