quil-lang / quilc Goto Github PK

src/addresser/astar-rewiring-search.lisp needs more documentation.

There is now only a single version shared by both components. Remove +CL-QUIL-VERSION+ in favour of +QUILC-VERSION+.

The file chip-specification.lisp is a pretty big offender. Hard-coded duration constants everywhere. But other files have it to. The approach should maybe be a bit more principled.

The trinary-classical-instruction method specialization of instantiate-instruction is essentially unusable (and untested) except as a pass-through. Specifically, the typing system in Quil is too awkward to allow for programs like

DECLARE values INT[80]
DEFCIRCUIT STORE-CIRCUIT a b c:
    STORE a b c

STORE-CIRCUIT values 20 values[10]

where it freaks out about passing the naked value 20 in as an argument (and probably parses the first argument values as the reference values[0] rather than as the region name).

The compressor sets up a bunch of queues based on qubit utilization and manually tracks the resource utilization of APPLICATION-type instructions to decide which queue to insert them into. This breaks the treatment of "classical" (e.g., NOT) and "hybrid" (e.g., MEASURE 0 [0]) sorts of instructions, which interact with more than just quantum resources. The compressor's structure should be reworked to permit the sorting of these sorts of instructions as well.

Instead of extending the following as and when necessary

       (setf *isa-descriptor*
             (cond
               ((or (null isa)
                    (string= isa "8Q"))
                (quil::build-8Q-chip))
               ((string= isa "20Q")
                (quil::build-skew-rectangular-chip 0 4 5))
               ((string= isa "16QMUX")
                (quil::build-nQ-trivalent-chip 1 1 8 4))
               ((string= isa "bristlecone")
                (quil::build-bristlecone-chip))
               ((probe-file isa)
                (quil::read-chip-spec-file isa))
               (t
                (error "ISA descriptor does not name a known template or an extant file."))))

it might be useful to have chip-specs define their names and have entry-point.lisp look them up at run-time like

    (setf *isa-descriptor* (lookup-isa-descriptor-for-name *isa-name-from-stdin*))

We would like to support at least CCL and ECL.

temporal-addresser.lisp is one of those complex machinery-type files. I'm making a note of the TODOs rather than explain and split them off into various tickets because I don't understand them :D

The compiler has very limited support for manipulating MEASURE instructions, but this is essentially untested because all the tests of quantum semantics are built around pure state simulation. (Look into density matrix simulation methods in the QVM and) introduce some tests that check correctness for programs involving mid-program MEASURE instructions.

I'm mostly thinking about docstrings. Some docstrings do not use line breaks, others do. It's a small issue, but I think consistency is important.

The compressor currently has no support at all for hardware objects of order greater than 1. Augmenting the compressor to deal with higher-order hardware objects is a tall ask, but I think it will ultimately result in a more maintainable code base: parts of the logic of the compressor are quite kludgy (and, accordingly, hard-to-follow) and read more like band-aids than like something well-reasoned. I think that accommodating higher-order hardware objects will necessarily entail sorting all of these kludges out.

https://arxiv.org/abs/1003.5760 contains efficient state preparation schemes for other small numbers of qubits beyond 1 and 2. Implement them!

Some of our compilation routines provide strong upper bounds on how long any sequence of instructions will eventually take after processing by the compressor. This information could be taken advantage of by the addresser to insert SWAPs at lower-than-expected cost: under certain circumstances where a HARDWARE-OBJECT has recently had instructions addressed to it, these preceding instructions will lower the threshold required to hit this threshold, so that the addition of a SWAP is liable to exceed it.

A first step toward employing this trick in the addresser is to store these upper bounds on the HARDWARE-OBJECTs for their easy access.

At various points in the code simple-errors are signaled. It would perhaps make for cleaner and clearer code if different error conditions had specific names. For example we could have a invalid-protoquil-error.

An issue that was reported on pyQuil claims that the error messages for a bad parse could be better.

Do we agree / is there a simple fix / is this WONTFIX?

The undocumented:

(loop for s being each external-symbol of (symbol-package 'cl-quil:**empty-memory-model**) 
      when (and (fboundp s)
                (not (documentation (symbol-function s) t)))
        collect s)
(CL-QUIL:BUILD-8Q-CHIP CL-QUIL:PRAGMA-MATRIX-ENTRIES
                       CL-QUIL:PARSED-PROGRAM-CIRCUIT-DEFINITIONS
                       CL-QUIL:IS-PARAM CL-QUIL:CONSTANT-VALUE
                       CL-QUIL:APPLICATION-OPERATOR
                       CL-QUIL:MEMORY-DESCRIPTOR-NAME
                       CL-QUIL:MEMORY-ALIAS-SIZE-IN-BITS
                       CL-QUIL:MEMORY-REF-NAME CL-QUIL:PRAGMA-QUBIT-ARGUMENTS
                       CL-QUIL:MEMORY-DESCRIPTOR-LENGTH
                       CL-QUIL:PARSED-PROGRAM-GATE-DEFINITIONS
                       CL-QUIL:CONDITIONAL-JUMP-ADDRESS
                       CL-QUIL:PARSED-PROGRAM-MEMORY-DEFINITIONS
                       CL-QUIL:MEMORY-ALIAS-LENGTH CL-QUIL:GATE-NAME
                       CL-QUIL:MEMORY-MODEL-NAMES CL-QUIL:TARGET CL-QUIL:PARAM
                       CL-QUIL:CLASSICAL-TARGET CL-QUIL:PARAM-NAME
                       CL-QUIL:CLASSICAL-LEFT-OPERAND
                       CL-QUIL:CONTROLLED-OPERATOR CL-QUIL:PRAGMA-QUBIT-INDEX
                       CL-QUIL:MEASURE-ADDRESS CL-QUIL:MEMORY-NAME-REGION-NAME
                       CL-QUIL:MREF CL-QUIL:MAKE-PRAGMA CL-QUIL:DAGGER-OPERATOR
                       CL-QUIL:RESET-QUBIT-TARGET CL-QUIL:QUBIT
                       CL-QUIL:JUMP-LABEL CL-QUIL:GATE-DEFINITION-PARAMETERS
                       CL-QUIL:MEMORY-MODEL-SIZEOF
                       CL-QUIL:QUIL-MEMORY-MODEL-ERROR
                       CL-QUIL:SIMPLE-GATE-MATRIX CL-QUIL:MEMORY-ALIAS-TYPE
                       CL-QUIL:IS-MREF CL-QUIL:MEMORY-ALIAS-NAME
                       CL-QUIL:MEMORY-ALIAS-ROOT-MEMORY
                       CL-QUIL:MEMORY-REF-POSITION CL-QUIL:MEMORY-MODEL-ALIASES
                       CL-QUIL:APPLICATION-PARAMETERS
                       CL-QUIL:APPLICATION-ARGUMENTS
                       CL-QUIL:MEMORY-DESCRIPTOR-TYPE
                       CL-QUIL:GATE-DEFINITION-ENTRIES
                       CL-QUIL:CLASSICAL-RIGHT-OPERAND
                       CL-QUIL:PRINT-INSTRUCTION
                       CL-QUIL:PARSED-PROGRAM-EXECUTABLE-CODE
                       CL-QUIL:MEMORY-MODEL-ALIGNMENT CL-QUIL:MEASUREMENT-QUBIT
                       CL-QUIL:NAMED-OPERATOR CL-QUIL:MEMORY-NAME
                       CL-QUIL:PRAGMA-OPERATOR-NAME CL-QUIL:CONSTANT
                       CL-QUIL:GATE-DEFINITION-NAME
                       CL-QUIL:PERMUTATION-GATE-PERMUTATION
                       CL-QUIL:PRAGMA-WORDS CL-QUIL:MEMORY-MODEL-ROOTS
                       CL-QUIL:MEMORY-ALIAS-STARTING-BIT
                       CL-QUIL:PRAGMA-FREEFORM-STRING
                       CL-QUIL:DYNAMIC-GATE-ARITY
                       CL-QUIL:MEMORY-MODEL-REAL-BITS
                       CL-QUIL:MEMORY-MODEL-INTEGER-BITS CL-QUIL:QUBIT-INDEX)

The test coverage for quilc's RPCQ server endpoints is very meager. There is template code that covers the simpler endpoints (e.g., the version info endpoint) and template code that covers semantic faithfulness; combine these to make some interesting tests of the actual compilation endpoints.

The guts of lscheduler-replace-instruction can be used to write a generic lscheduler-append-lschedule function. (For that matter, the rest of lscheduler-replace-instruction probably then forms a generalization of lscheduler-dequeue-instruction.) This was too hard to get right under time pressure, but it's worth revisiting how these methods can be refactored.

The implementation of ISWAP-to-native-ISWAPs currently uses the expression of ISWAP in terms of a pair of CNOTs, then does long-range decomposition on the CNOTs instead. I do not know how to do this decomposition purely in terms of ISWAPs. I have no idea whether the CNOT approach gives an efficient decomposition, but I strongly suspect it doesn't, and this might be worth exploring.

A foothold may be that

ISWAP 0 2
ISWAP 1 2
ISWAP 0 1
ISWAP 1 2
RZ(-pi/2) 0
RZ(pi/2) 2

emits a diagonal matrix of 1s and -1s, and so should be modelable by a sequence of UCRs—but this ultimately seems to give a circularly dependent decomposition.

Another place where one might be able to pick this up is using the following encoding of CNOT 1 0 to demonstrate that P, H, and ISWAP generate the Clifford group:

P q0
P q0
P q1
P q1
ISWAP q0 q1
H q0
P q0
P q0
ISWAP q0 q1
P q1
H q1
P q1
P q0
P q0
P q0

and then appeal to God table techniques to produce a decomposition of a long range ISWAP across three qubits.

This is possible with Embeddable Common Lisp and I think would be the most straightforward way to do it instead of trying to coax SBCL into doing it.

quilc isn't all portable to ECL, so this issue would require stubbing out the appropriate ECL functionality.

The biggest trouble, however, is that arrays of (complex double-float) must be supported by MAGICL. ECL doesn't support it yet, and would be critical to getting this to work. See this thread on the ECL issue tracker.

@ntezak was trying to run a simple parallel 1Q program

DECLARE ro BIT[3]

RX(pi/2) 1
RX(pi/2) 2
RX(pi/2) 3
MEASURE 1 ro[0]
MEASURE 2 ro[1]
MEASURE 3 ro[2]

on the disconnected ISA

{'1Q': {'0': {'dead': True}, '1': {}, '2': {}, '3': {}}, '2Q': {}}

which resulted in a QUILC error:

QuilcError(result['status']) compiler_server.quilc.QuilcError: User program used too many qubits: 3 used and 1 available in the largest connected component

This is because the compiler will blanket-reject programs that it can't fit onto a single connected component of the device. This is unnecessary: it should only reject programs if there's no assignment to connected components that permits the requested two-qubit operations. This change would require being a little more delicate in the guts of the addresser loop, which is why we were using this simpler heuristic instead.

Would be nice if it was just 5 or 6.

The current output of parametric expressions can only such ugly expressions as theta[0]*2/2+pi/2-pi/2, which is unnecessarily ugly. Implement a rewriting ruleset, probably as a post-linear-algebraic program transformation, which reduces expressions to normal form.

We're looking to introduce exponentiated skew-Hermitians as a Quil primitive, on the premises that:

• Many QPU users (and physicists in particular) are experienced at expressing problems in this language.
• This lends itself more readily to a 'sparse' representation than DEFGATEs do, which the compiler ought to be able to exploit.
• It is the compiler's job (rather than pyQuil's job, as is done presently) to translate these to native Quil instructions.

We should research some of the most common kinds of Pauli sums appearing in practice and corresponding expansion techniques, and then we should implement them.

Seeing an intermittent error when running the quilc tests.

QUILC-TESTS (Suite)
  TEST-FAITHFULNESS                                                       [ OK ]
[2018-12-17T17:07:09.116870-08:00 | Anonymous thread] Spawning server at (tcp://*:5555) .

[2018-12-17T17:07:10.122782-08:00 | RPC-server-thread-0] Got request: get_version_info
[2018-12-17T17:07:10.123270-08:00 | RPC-server-thread-0] Finishing request: get_version_info
  TEST-EASY-VERSION-CALL                                                  [ OK ]
[2018-12-17T17:07:10.124907-08:00 | Anonymous thread] Spawning server at (tcp://*:5555) .

debugger invoked on a PZMQ:EADDRINUSE in thread
#<THREAD "Anonymous thread" RUNNING {10051C3903}>:
  C error EADDRINUSE: Address already in use.

Run the following for a lil while

(ql:quickload :quilc-tests)

(loop for i below 100 do (asdf:test-system :quilc)

Originally raised on pyQuil.

Compiling a PHASE gate that has a memory-ref as its parameter fails with the following error

* (compiler-hook (parse-quil-string "DECLARE gamma REAL[1]
PHASE(2*gamma[0]) 0") (build-8q-chip))

Condition CL-QUIL::UNKNOWN-GATE-PARAMETER was signalled.
   [Condition of type UNKNOWN-GATE-PARAMETER]

e.g.:

• compiler-invalid-domain
• compiler-acts-trivially
• compiler-rewrite-does-not-apply
  etc.

Any more?

It is hit in code coverage, but has no specific tests.

If we add a :CNOT case to the function gate-application-trivially-satisfies-2q-target-requirements so that CNOT p q simply gets optimally compiled to CNOT p q, then the compiler gets itself into infinite loops. The doc string of that function (which I wrote) is:

"Does the gate application INSTR trivially satisfy the requirements imposed by REQUIREMENTS? (In other words, do we actually need to do decomposition?)"

and it seems that CNOT is appropriate since it's a valid target. Maybe it shouldn't be a target? Maybe 2q compile is wrong? I'm not sure.

It seems like if there is this bug, there must be other ones lurking.

(CC @ecp-rigetti)

The argument of compiler-hook mutates currently as a part of the compilation process. Should it?

Some things it is missing:

• RPCQ

e.g. in

(defun CNOT-to-native-CNOTs (chip-spec cnot-gate)
  (operator-match
    (((("CNOT" () q0 q1) cnot-gate))
     ;; ...
     )
    (_
     (give-up-compilation))))

IMO writing the above is difficult to do successfully on the first or second try.

I think we should have documentation/references for the functions that compile things like GATE a x into a sequence of (possibly) different gates if a and x are not adjacent in the chip spec.

In various places, something like the following is used:

(defun CZ-to-native-CZs (chip-spec cz-gate)
  (unless (operator-match-p cz-gate '("CZ" () _ _))
    (give-up-compilation))
  (let ((q1 (qubit-index (first (application-arguments cz-gate))))
        (q0 (qubit-index (second (application-arguments cz-gate)))))
    (nconc
     (list (build-gate "RY" '(#.(/ pi 2)) q0))
     (CNOT-to-native-CNOTs chip-spec
                           (build-gate "CNOT" () q1 q0))
     (list (build-gate "RY" '(#.(/ pi -2)) q0)))))

where it could be cleaned up / clarified by using operator-match.

We should implement a couple of algorithms (perhaps one general-purpose and one specialized to a particular gate-set) that target a gate-set suitable for use as a "logical" native gate set in some fault-tolerant scheme. This would significantly widen the interested audience in quilc.

The present addresser loop is designed to function for an arbitrary QPU layout. On the other hand, there exist custom SWAP schemes for rectangular lattices that outperform our generic algorithm by a wide margin. Now that Rigetti has settled on a particular lattice (trivalent and octangular), we should look into bespoke SWAP schemes for graphs of this form.

Such schemes should function in the presence of some small fraction of dead qubits. Such schemes should also take into account the "low qubit case", where the ratio of qubits at the boundary of the chip to all qubits is relatively high.

build-link in chip-specification.lisp has some notion of duration but just reading the code it's not clear what it is or how it's used. Why do some of those entries use underscores where others do not? why the backticks? why the repetition?

I think this could be cleaned up by defining some duration data structure.

Generating a God table works when the generators are Clifford elements, but will later cause failure if those generators only generate a subgroup of the Clifford group.

Example we ran into:

{ "depth": 2, "qubits": 1, "gateset": ["PHASE(pi) 0", "H 0"] }

Here, PHASE(pi) is not a generator of the Clifford group. It should be PHASE(pi/2) or S to generate C_1.

Putting the above in a hash table and running (rb-post nil ht nil nil) repeatedly causes failure. It should fail! But it needs a better error message/detected earlier.

Possible solution: Return an error "No decomposition exists." or the like.

Reported by @stylewarning .

Current lscheduler depends on gates being referentially different, because it uses an EQL hash table. This has led to at least one difficult-to-track bug.

Either make it so that the objects don't need to be referentially different, or do the work to make them distinct automatically, or error if you try to do some kind of operation (like add to the lscheduler when something already exists)

The compressor currently contains routines for generating circuits that carry a fixed complex line in the state space to another complex line. This restricts the applicability of compression by state preparation, and we could try to widen this by understanding how to send a complex n-frame to a complex n-frame.

I'm not aware of literature resources that address this specifically. This task will be made much easier by finding those.

Right now entire Quil files have to be slurped into a string and the entire thing has to be processed. Can we instead do lexical analysis on a stream to create a token stream?

In chip-specification.lisp you'll see plenty of (vnth 1 (hardware-object-cxns ...)) and to the uninformed it's not exactly clear what that is doing. Maybe a better interface would be to define hardware-object-qubits and hardware-object-links.

At the top of a ProtoQuil program, the compiler will automatically eliminate program-initial SWAPs that it inserts, choosing instead to modify the initial rewiring. We should also do this for user-supplied program-initial SWAPs.