Better way of describing conditional gate execution

[AdriaanRol]

OpenQL is currently a combination of API calls. Expressing classical construct is very counter intuitive. This can be improved.

[wvlothuizen]

Below is a quote of an old post of mine on slack channel '#openql-and-friends' that pertains to this subject:

As some of you know, I'm working on an OpenQL backend for the new Central Controller. This CC differs from the CClight in that it has no notion of quantum operations and internally has a distributed architecture (with a separate processor per connected instrument). In order to be able to support conditional instructions, we need to be able to relate measurements (currently performed on an UHFQC) to actions (performed on VSM or maybe AWG). Because we have no a priori knowledge of the mapping of qubits on either, we devised an end user programmable (i.e. through the backend) Condition Engine. This Condition Engine can do many more things than the implicit conditional gates of the CClight (e.g. support expressions on 2 qubits, and support a concept of state), but these are currently difficult/impossible to express in OpenQL. Of course we can (and probably will) support the current conditional gates, but I think it would be a great improvement if the condition could be passed as a parameter (preferably a logic expression). We also support program flow conditional on measurement results ("comprehensive feedback"). This can only be expressed by the user in 'classical QASM', which is a bit awkward to support for us because it is very close to the CClight internal instruction set, but much less so to ours. As an example, we support a 'loop' instruction which combines decrementing a register and a conditional branch. As another example, in our instructions measurement results live in a register space different from the classic processor registers (namely in distributed shared memory controlled by the real time part of the processor). I think all of those translations would be easier if the classical part of QASM would be a higher level language. All in all I think a discussion on classical logic would be appropriate (maybe that is already going on for libqasm2.0, but I'm not connected to that)

[wvlothuizen]

meeting homework:

documentation on the CC can be found in the Central Controller dropbox. If you require access please let me know. Places to have a look are "doc/design/CC", "doc/presentations" and "doc/requirements/CC".

[wvlothuizen]

meeting homework:

indeed the instruction set of the CC does not operate at the qubit and quantum gate level like the CC-light, but instead it deals with digital inputs (from a UHFQC) and outputs (to an AWG). Moreover, the architecture is distributed: one sequence processor controls one instrument only, and sequence processors can exchange data (measurements) using Distributed Shared Memory. The current CC OpenQL backend mostly produces digital output (the seq_out instruction), the translation process from a quantum gate to a digital output happens in the backend (contrary to the CC-light where the ISA performs this), and involves the mapping of qubits to instruments. The CC "Q1" processor supports classical instructions like add, or, xor, see file "Q1_SEQ Instructionset.xlsx" in dropbox:/doc/design/CC. Additionally, the Distributed Shared Memory fabric supports a programmable feedback data path, see "cc_firmware_implementation-20191203.pdf" section 4.5.3.1 and 4.5.3.1 and also "CC-soft+firm-ware-design.docx" section 2.3

Feel free to ask more questions after reading through the documentation,

[wvlothuizen]

Meeting homework:

Feedback requirements are discussed in Sections A.11 and further of dropbox:doc/requirements/CC/QuSurf_CC_UseCases.docx

The feedback implementation of the CC was pointed to above: "Additionally, the Distributed Shared Memory fabric supports a programmable feedback data path, see "cc_firmware_implementation-20191203.pdf" section 4.5.3.1 and 4.5.3.1 and also "CC-soft+firm-ware-design.docx" section 2.3"

[wvlothuizen]

Update:

dropbox:doc/requirements/CC/CC_conditionalGates.docx discusses the relation between use cases for conditional gates and the code to implement those on the CC

[jvansomeren]

Introduction

We want to support binary conditional gates in OpenQL to map to the Central Controller. E.g.

    { measure q0, r0 }              # measure q0: r0 = meas q0
    { bitcomplement r0, r1 }        # bit-complement: r1 = ~r0
    { IF r0 X q0 | IF r1 Y q1 }     # have X q0 and Y q1 in parallel, conditionally on r0 and ~r0

Definition of conditional execution

Conditional gate execution means:

• depending on a classical condition value, execute the gate
• the classical condition value can be any logical expression but usually it depends on some measurement results collected earlier
• there is no control flow here, i.e. the gate is scheduled for execution, i.e. its resources are allocated, everything is prepared to execute it, but whether it has effect is finally decided by the processor based on the condition; when it is not executed, the involved qubits idle for the duration of the gate

CC support of conditional execution

The Central Controller supports conditional expressions in hardware (using a so-called feed-back multiplexer, MUX for short). These expressions have the power to shortcut the measurement and the conditional execution without the need of intermediate storage or operations: implementing the above example on the CC, the result of the measurement would be stored internally and used internally; there would be no need to pass them through r0 and r1:

• any gate can be executed conditionally under a binary condition, unconditional is a special case of conditional
• during conditional gate execution, the conditional expression is evaluated, but there are limitations on the form of the conditional expression which can be executed in a single cycle, which in two cycles, etc.
• in a single cycle it can access measurement results, and do a boolean operation on those, in parallel for all qubits:
  • of each qubit the last measurement result and the previous measurement result are available as bits
  • a stored bit per qubit apart from these
  • a bit from a shared memory location
  • the bit inverse of these
  • the xor of these

It is limited what form of expression can be evaluated in a single cycle, in two, etc. It is possible to collect a result, store it in shared memory, and based on that do another expression in the next (or later) cycle.

It needs 3 program descriptions that are generated by the CC back-end:

• the conditional gate instruction in instruction memory (CODE); it refers to an entry in MUX
• the conditional gate expression in the feedback-multiplexer memory (MUX);
• the shared memory (SM) in case of multi-cycle expressions as internal storage

As far as I (@jvansomeren) can judge, the MUX and SM together can be used to implement classical conditional expressions (and, or, not, compare, xor): the MUX for the expressions and the SM for the registers. The support of classical integer expressions would require a simple ALU (add, subtract, compare) with a set of integer registers (REG) and a path to/from the SM and other bits for conditionals. This implementation is assumed below in the examples.

OpenQL layers and conditional execution

The processing sequence and layering in OpenQL regarding conditional gates is:

1. Representation in cQASM and/or the OpenQL API This describes the language support for binary conditional gates.

   • Since cQASM also functions as an external IR representation of the OpenQL compiler, it needs to be able to represent the high-level description, the result after decomposition, and the result after scheduling.
   • cQASM is read by a cqasm reader built on top of libqasm, a library for reading cQASM
   • the cqasm reader internally issues OpenQL API calls to create the gates in the IR
   • the available gates and gate decompositions are described in a configuration file

2. Decomposing gates to match the primitive gates that are supported by the CC. Any high-level descriptions are broken down to those that are supported:

   • complicated conditional expressions are broken down to those supported as primitives (which may depend on the gate in which they appear) plus additional stand-alone classical operations
   • non-primitive quantum gates are decomposed to lists of conditional primitive gates

3. Scheduling the circuit

   • after decomposition, the conditional gates are scheduled just as non-conditional ones except for the constraints on the conditional hardware and the use of classical registers, so all gates are primitive and cycles are assigned when they can be executed

4. Instruction generation by the back-end

What is already there?

Some proposals for representation were already done, some of which were already implemented:

• cQASM2.0 proposes syntax for binary-controlled gate execution of the form:

  c-GATE condition-register -> gate-operands

  e.g.

  c-x r0 -> q1 means a conditional execution of X q1 depending on r0
  c-Rx r0 -> q1,pi/3 means a conditional X rotation over pi/3 radians of q1 depending on r0

  In this:

  • GATE is an arbitrary gate (X, CNOT, Toffoli, Rx, ...)
  • the condition-register is a classical register; not an arbitrary logical expression
  • the gate-operands are those required by GATE (qubits, classical regs, angle, integer, etc.)

The "c-" prefix just indicates binary-control of any gate.

So:

    c-Rx r0 -> q1,pi/3              (cQASM2.0)
    c-Rx r0, q1, pi/3               (libqasm)
    IF r0 Rx q1, pi/3               (as in example above)
    COND r0 Rx q1, pi/3             (as used in earlier mail)

are just syntactically equivalent variants of the same.

• libqasm recognizes binary-controlled gates but the arrow -> of cQASM2.0 must be written as a comma:

  c-x r0, q1 c-Rx r0, q1, pi/3 c-CNOT r0, q1, q2

  and libqasm only knows default gates, i.e. it is not configured from a config file

• cqasm_reader doesn't support binary controlled gates

Implementation

There are two issues:

• representation and support of the conditional expressions
• representation and support of conditional gates

Conditional expressions

In cQASM we have several options how to represent the conditional expression in a gate. These seem all appealing but the last one turns out to be easiest, engineering-wise, and so easiest to support/implement:

1. only and exactly an expression that is supported by CC can be represented in the conditional gate, not a general expression, i.e. the programmer knows it exactly:

    { measure q0 }              # measure q0; implicitly keeps result in last[q0]
    { IF last[q0] X q0 | IF ~last[q0] Y q1 }     # have X q0 and Y q1 in parallel, conditionally on last measurement
   
   The programmer guarantees that the expression fulfills all CC constraints.
   This solution requires all kinds of special casing,
   while reading, keeping the result, scheduling, etc., and it probably turns out
   that generalized support would take as much time as this special casing.
   It is also not portable to later CC versions with different constraints.
   So although this seems to make life easy, it is not.

2. any conditional expression can be represented in the conditional gate, i.e. a more generalized one that the one allowed by CC, or also only a classical register, i.e. less than supported by CC:

    { measure q0 }              # measure q0; implicitly keeps result in last[q0]
    { SM[0] = ( ~last[q0] ) }   # keep this result inverted in shared memory
    { measure q1 }              # measure q1; implicitly keeps result in last[q1]
    { measure q1 }              # measure q1; implicitly keeps result in last[q1], previous now in previous[q0]
    { IF ( ~last[q0] | SM[0] | prev[q1] ) Y q1 }     # execute Y q1, conditionally on complicated expression
   
   Decomposition:
   
   - OpenQL decomposes this expression in the part done by CC (left in place in the gate)
     and the part(s) done by classical logical instructions (additional instructions).
     This is a CC-dependent decomposition pass.
   - These parts are connected by newly allocated classical registers.
   - Because measurement is a gate and because of the special support for the last and previous measurements, specials are needed to access those results.
   
   Pre-scheduling and RC-scheduling:
   - dependences on previous gates/qubits/classical registers of the CC-part and non-CC-part(s)
   - timing of CC part is separate from timing of the other parts
   - any constraints on CC-MUX etc.?
   
   Because of the special casing for last and previous measurement results inside the total conditional expression, this becomes dependent on what CC supports; that is not nice.

3. only a single register access

    { measure q0, r0}              # measure q0: r0 = meas 10
    { SM[0] = ( ~r0 ) }   # keep this result inverted in shared memory
    { measure q1, r1 }              # measure q1; keep in r1
    { measure q1, r2 }              # measure q1; keep in r2
    { SM[2] = SM[0] | SM[1] }
    { IF ( SM[2] | r1 ) Y q1 }     # execute Y q1, conditionally on primitive expression
   
   Data-flow analysis:
   
   - OpenQL uses the data dependence graph to trace back the data flow to the condition.
     The operations in this data flow graph are the measurements and the classical logical instructions.
     In this data flow graph, the CC-part is isolated and extracted into the gate;
     the original operations are deleted or transformed.
     This is a CC-dependent decomposition pass.
   Pre-scheduling and RC-scheduling:
   - as with 2.
   
   This is the most general solution.
   Because the last and previous measurement must be found, if any, those must be present in the same circuit, and not separate, reachable over a (conditional) branch.
   In the end, it is also probably the easiest to implement, exactly because of the absence of special casing.
   The CC-dependent decomposition pass has full control.

Conditional gates

OpenQL needs to be updated:

• gates needs extension with an attribute representing the condition (mostly documentation)
• it is assumed that every gate can be made conditional; this reduces configuration needs (...)
• libqasm, cQASM reader and OpenQL API need to be extended (easily a week)
• decomposition, scheduling, mapping, etc. must be made to work with conditional gates:
  • decomposition: copy the condition to the more-primitive gates; document this; warn on redefinitions of registers, a recursive measure, etc. (when condition is represented by just a register, this is almost no work)
  • scheduling: in the dependence graph construction, also take condition into account (simple); furthermore, there is knowledge how many cycles the evaluation of a condition takes (needs design)
  • mapping: take care that swaps aren't made conditional (simple)
• passes as above must be implemented (most of the time)

[wvlothuizen]

Some remarks per section...

CC support:

• the input is not necessarily limited to the last and previous measurements. It can choose bits from a 128 bit view of Shared Memory (which is 1024 bits in total). SM can be written by a measurement, or by QEC;
• apart from XOR, also AND and OR are supported;
• implementing complex expressions using multiple rounds through Programmable Logic is not intended. The PL cannot write to Shared Memory, only to the state variable.

OpenQL layers:

• I don't think we should support breaking down complex conditional expressions. The whole idea of the PL is to have a low (and fixed) latency mechanism for conditional gates that can operate on multiple qubits at the same time. Bringing in additional classical operations will make things slow and difficult to schedule. I'd say that if the expression is too complex, compilation should fail. If that happens in practice, we should extend the capabilities of PL.

What's already there:

• the cQASM/libqasm syntax has two problems in my opinion:
  • it 'breaks' the normal gate syntax because the condition is between the gate and the operands, which makes it difficult to read;
  • the "c-" prefix changes the gate name, which seems counterintuitive. It also leaves the question whether "c-x" uses the same gate definition as "x", and makes it impossible to have normal gates start with "c-".
• to me, OpenQASM's syntax "if(creg==int) qop;" is clear and would be extendible to allow more complex expressions.

Conditional expressions:

• I don't think implicit notion of last and previous measurements should be added, but that the user should explicitly assign two classical variables;
• the cQASM way to perform a bitcomplement r0, r1 is counterintuitive to me: it actually assigns a value to r1, while that's not what the user intends, neither is it what will happen on the CC. To me, { IF r0 X q0 | IF ~r0 Y q1 } is way more readable;
• if we redesign the syntax of conditional gates, we should also bear in mind the 'randomized benchmarking' use case, which requires real time selection of a gate from an array of gates (24 Cliffords in this case), based on a classic variable (a random number in this case);
• currently scheduling is done at the kernel level, and classic conditional constructs (FOR, IF, WHILE) operate on kernels. I think this precludes having a classical variable life time beyond a single kernel, which would be a severe limitation.