RFC: unitary subroutines, as a gate-like subroutine acting on quantum registers and with more versatile control flow

[ndebeaudrap]

Notes

• In light of discussions below and elsewhere, we have revised this proposal. Below is the original proposal as it stood prior to 4 April. A self-contained revision as of 6 April can be found further below.

• This proposal now has a corresponding PR (#346) for the open specification.

Original proposal

The "Circuit Families & Generics" workgroup propose for OpenQASM3 to support a new kind of subroutine, which we call unitary subroutines. These are in a sense intermediate between a gate subroutine and a def subroutine: they represent unitary transformations which can be controlled and inverted, but they may take qubit registers as operands and be specified with control-flow structures such as for loops and if statements involving run-time constants.

The following is a high-level description of such subroutines, and the syntax with which they would be defined and invoked. We propose this as a feature to be added to OpenQASM3.

Considerations

As more complex procedures are developed, it will be useful to have a kind of subroutine which acts unitarily on registers of more than a handful of qubits, and which as a sequence of gates would be complicated. This is likely to occur when expressing unitary operations to diagonalise the Hamiltonian of a complex system to be simulated, or when expressing reversible 'classical' functions to be performed coherently. Functionality of this sort provided by def subroutines. However, it will be useful to have subroutines of this sort, which may be coherently controlled and inverted in the same way that gate subroutines can.

At present, there is no way to do this within OpenQASM3. The following are the closest that one can come to doing so.

• One may write a gate subroutine, acting on many individual qubits, as a potentially complicated sequence of gates without use of control flow. Making such a gate specification human-readable in OpenQASM is likely to be difficult. This may be mitigated in part by using a program in an axuiliary programming langauge (such as Python) to emit it. However, the specification of the program would be sensitive to the dependencies of the code in the auxiliary language, and therefore less portable. The emitted code will also remain unwieldly.

• Alternatively: one may write a def subroutine, involving control flow, to realise a sequence of unitary operations, and then a separate def subroutine for the inverse of those unitary operations, and a third def subroutine if needed to realise a coherently-controlled version of those unitary operations, etc. This provides more opportunities for programmer error which in principle could be avoided by having a functionality to define the subroutine once, and to derive these related subroutines from that specification. Again, this might be mitigated by emitting OpenQASM code from a program written in an auxiliary language, with the same drawbacks as described above.

The proposed solution, of introducing a new variety of subroutine, will allow the specification to be both human-readable and expressed in OpenQASM3, while avoiding the pitfalls of redundant specifications.

Proposed syntax

Declaring unitary subroutines

We propose declaration syntax for these subroutines as follows:

    // a unitary subroutine with a single register of size 8 as an operand
    unitary subr1 : qubit[8] q { /* ... body ... */ }

    // a unitary subroutine with two registers as operands
    unitary subr2 : qubit[5] x, qubit[3] y { /* ... body ... */ }

    // a unitary subroutine with some classical parameters
    unitary subr3 (int n, angle theta) : qubit[9] q { /* ... body ... */ }

Apart from the bodies of the subroutines, these declarations are broadly similar to the syntax of a gate declaration, with two notable exceptions: the specification of types of the parameters / operands, and the presence of the delimiter : separating the quantum operands from the rest of the declaration.

Unlike gate subroutines, we must allow for the possibility of quantum operands which are not individual qubits. This requires that we specify the types of the operands. In order to visually separate the type signature of the first quantum operand, from the identifier of the unitary subroutine, we propose to use a : delimiter.

As with gate declarations, we separate the classical parameters from the quantum operands, by grouping the former together in parentheses, leaving the latter out. This is motivated by ways in which these subroutines may be invoked, with the ctrl @ gate modifier, as described further below.

The structure of the body

The body of a unitary subroutine would be similar in structure to that of a def subroutine, but with the following restrictions.

• All quantum operations in the body must be gate subroutines, or other unitary subroutines. In particular, measure and reset operations are not allowed.

• All classical identifiers, including locally defined variables, classical parameters, and iterators, are treated as immutable. Iterators can only be modified by the for loop construct itself, and assignments to variables are not allowed after initialisation.

The above constraints are necessary for the compiler to be possible to define inverses and coherently-controlled versions of unitary subroutines.

Examples of use

We present a number of examples below. For the sake of brevity, most of these are 'toy' examples which may be more typical of an educational setting rather than application.

Simple unitary subroutine declarations and invocations

The following snippet relies on declarations of a Pauli x gate, a Z-rotation gate rz, and a controlled-NOT cx gate, to define operations acting on a register of two qubits. (In this case, similar functionality could be described as a two-qubit gate: we present it as a unitary subroutine on a two-qubit register, to suggest a use-case in which one describes a register as a logical unit.)

    // define a cyclic shift operation on a three-dimensional subspace
    // spanned by |00>, |01>, |10> of a two-qubit state, representing
    // addition of one (mod 3) on an encoded qutrit
    unitary qutritX : qubit[2] a {
      x a[1];
      cx a[1], a[0];
      cx a[0], a[1];
    }

    // define a ‘clock’ operator on a three-dimensional subspace
    // spanned by |00>, |01>, |10>, a two-qubit state
    unitary qutritZ : qubit[2] a {
      rz(2*pi/3) a[0];
      rz(-2*pi/3) a[1];
    }

In both cases the operand is a single register a consisting of two qubits.

Using gate modifiers

We may use these subroutines, to define further unitary subroutines which apply gate modifiers to them:

    // define a controlled-addition gate on two qutrits,
    // where each qutrit is encoded in two qubits
    unitary qutritCX : qubit[2] c, qubit[2] t {
      ctrl @ qutritX c[0], t;
      ctrl @ inv @ qutritX c[1], t;
    }

In this example, we define a unitary subroutine acting on two operands, each of which is a register of two qubits. The unitaries are defined by modifications of the qutritX subroutine, in each case using the ctrl @ modifier. As with gate subroutines, applying a ctrl @ modifier adds a single qubit to the beginning of the list of quantum operands: this syntax motivates separating the quantum operands from any classical arguments that may be present, also as with gate subroutines.

Using declarations as above, we may invoke qutritCX on the top level of an OpenQASM3 program as follows (relying on a h gate to realise a Hadamard operation):

    qubit[2] a;
    qubit[2] b;
    h a[0];
    qutritCX a, b;
    qutritZ a;

Note that the invocations of qutritCX and qutritZ are in effect similar in style to invocations of gates. However, they do not involve any broadcast semantics. In particular, invocations of these subroutines are only well-typed if they are invoked on quantum registers whose widths match the operands described in the respective subroutine declarations.

Classical parameters, local variables, and control flow

A unitary subroutine may be defined using zero, one, or more classical parameters. For example:

    // define an operation which simulates adding an integer (mod 3) to
    // the state of a qutrit, encoded in two qubits
    unitary qutritPlus (int b) : qubit[2] a {
      if (b % 3 == 1) qutritX a;
      else if (b % 3 == 2) inv @ qutritX a;
    }

The control flow allowed in the declaration of a unitary subroutine cannot involve any measurements, and therefore cannot involve any feedback between the classical parameters and the quantum operands. To allow such a subroutine to be coherently controlled and inverted, all parameters in the subroutine are immutable. Thus, using the above subroutine qutritPlus, one may write a subroutine invocation as follows:

    input int s;
    qubit[2] t;
    qubit c;

    h c;

    ctrl @ qutritPlus(s) c, t;

Again, Note that the additional quantum operand (a single qubit) introduced by the ctrl @ modifier, occurs after the classical argument s to the subroutine qutritPlus, as it would for a controlled gate invocation.

We allow declarations of local variables within the scope of a unitary subroutine as a convenience, but these too are immutable once initialised. This behaviour extends also to the iterators of for loops, which may be used in the definition of a unitary subroutine:

    unitary QFT256 : qubit[8] q {
      uint n = 8;
      for j in [0 : n-1] {
        h q[j];
        for k in [j+1 : n-1]
          ctrl @ Rz(pi / 2**(k-j+1)) q[j], q[k];
        }
      for uint j in [0:n-1]
        if (j != n-1-j)
          swap q[j], q[n-1-j]
    }

While the iterators j and k above change their values in the course of their loops, we treat them as run-time constants. This allows the inverse or a coherently controlled version of this same circuit to be easily computable from the subroutine definition. Compare this with the following equivalent gate subroutine declaration:

    gate QFT256gate  q0, q1, q2, q3, q4, q5, q6, q7 {
      h q0;
      ctrl @ Rz(pi / 2) q0, q1;
      ctrl @ Rz(pi / 4) q0, q2;
      ctrl @ Rz(pi / 8) q0, q3;
      ctrl @ Rz(pi / 16) q0, q4;
      ctrl @ Rz(pi / 32) q0, q5;
      ctrl @ Rz(pi / 64) q0, q6;
      ctrl @ Rz(pi / 128) q0, q7;
      h q1;
      ctrl @ Rz(pi / 2) q1, q2;
      ctrl @ Rz(pi / 4) q1, q3;
      ctrl @ Rz(pi / 8) q1, q4;
      ctrl @ Rz(pi / 16) q1, q5;
      ctrl @ Rz(pi / 32) q1, q6;
      ctrl @ Rz(pi / 64) q1, q7;
      h q2;
      ctrl @ Rz(pi / 2) q2, q3;
      ctrl @ Rz(pi / 4) q2, q4;
      ctrl @ Rz(pi / 8) q2, q5;
      ctrl @ Rz(pi / 16) q2, q6;
      ctrl @ Rz(pi / 32) q2, q7;
      h q3;
      ctrl @ Rz(pi / 2) q3, q4;
      ctrl @ Rz(pi / 4) q3, q5;
      ctrl @ Rz(pi / 8) q3, q6;
      ctrl @ Rz(pi / 16) q3, q7;
      h q4;
      ctrl @ Rz(pi / 2) q4, q5;
      ctrl @ Rz(pi / 4) q4, q6;
      ctrl @ Rz(pi / 8) q4, q7;
      h q5;
      ctrl @ Rz(pi / 2) q5, q6;
      ctrl @ Rz(pi / 4) q5, q7;
      h q6;
      ctrl @ Rz(pi / 2) q6, q7;
      h q7;
      swap q0, q7;
      swap q1, q6;
      swap q2, q5;
      swap q3, q4;
    }

This definition is repetitive, and scales quadratically in the number of qubits on which it acts (where those qubits must tehmselves be described as separate operands to the subroutine). To modify this QFT256gate to represent a quantum Fourier transform which acts on a different number of qubits, would require the programmer to modify many lines of code, and provides opportunities for errors in the specifications of the angles and the operands. In contrast, we may modify the unitary subroutine QFT256 to represent a quantum Fourier transform acting on a different number of qubits, by modifying two lines of code: the specification of the quantum operand q, and the value of the identifier n.

Approaches to implementation

In the first instance, it would be practical to support invocations of unitary subroutines, which can be resolved to sequences of gate invocations at compile time (before execution). This could in principle be realised as a pre-processing step.

A different approach would be required to extend support for unitary subroutine invocations which depend on parameters computed in run-time — for instance, where the subroutine has control-flow which depends on some parameters, but where the invocation uses arguments which are computed only at run-time for some of those parameters. Possibly these might be supported in a similar way to def subroutine calls.

Context / related concepts

It is possible that gate subroutines can be usefully extended to allow operands which are not qubits, and classical parameters which are not of type angle. For instance, on a hardware platform which natively supports a qutrit type (a three-level system), one might wish to define gate subroutines on qutrits which are not realised by two-qubit registers. This might motivate a similar elaboration of the gate declaration syntax, as we have proposed for unitary subroutines. However, it seems reasonable to suppose that gate subroutines would continue to be defined without use of classical control-flow, so that more complicated examples of subroutines (such as QFT64 described above) would still require functionality apart from gate subroutines to succinctly define.

It is anticipated that unitary subroutines will be most useful in combination with a capacity to define 'generic' subroutines, a template-like declaration (which could also be applied to def subroutines) which would allow the size of quantum operands to be determined by some 'meta-parameter'. Such generic subroutines would naturally allow for the possibility of subroutines to act on registers of many qubits, which in some cases might be useful to invert or to coherently control.

Supporting unitary subroutines will, in general, encounter similar technical issues as supporting def subroutines, in the dereferencing of qubits using values which are only known at run-time. However, there is some value in supporting at least invocations of unitary subroutines which do not require such dynamical dereferencing in an essential way, by unrolling their definitions into sequences of gates computable at compile time.

Summary

In the medium to long term, complex unitary subroutines are likely to play an important role in the practise of quantum computation, whether these are coherently-performed reversible computations on registers, or subroutines to simulate Hamiltonian dynamics by performing a diagonalising unitary, simulating a diagonal operator, and then performing the inverse of that diagonalising unitary. Supporting such subroutines natively will improve the versatility of OpenQASM, and the portability of subroutines to perform such operations.

Open questions

• Would there be any difficulties to incorporate the proposed syntax for unitary subroutine declarations into the grammar?

• What difficulties might arise in semantic analysis or code-generation for unitary subroutines (either in their declarations, or their invocations)?

• In particular, are there additional constraints on the allowed contents of the body of a unitary subroutine declaration, beyond the above, which are motivated by allowing them to be acted on by gate modifiers?

Revised proposal (6 April)

After discussion with Ali Javadi-Abhari and Steven Heidel, and further discussion within the WG on 6 April, we amend our proposal as follows.

It is felt that it is useful to have a single language feature, which represents operations that could be regarded in terms of unitary matrices (in contrast, for instance, with def subroutines which may give rise to changes in classical data storage). For this reason, it was suggested that the functionality described above, be presented instead as an extension to gate subroutine functionality. Below is a suggestion for how this might be done.

Considerations

As more complex procedures are developed, it will be useful to be able to perform unitary operations on registers of more than a handful of qubits, and which in particular can be inverted or coherently controlled, but which can be described using program logic rather than simply as a linear sequence of simpler operations. This is likely to occur when expressing unitary operations to diagonalise the Hamiltonian of a complex system to be simulated, or when expressing reversible 'classical' functions to be performed coherently.

At present, there is no way to do this within OpenQASM3. The following are the closest that one can come to doing so.

• A def subroutine allows the possitibility of control flow, and of acting on quantum arguments consisting of registers, to realise a sequence of unitary operations. One might then define a separate def subroutine for the inverse of those unitary operations, and a third def subroutine if needed to realise a coherently-controlled version of those unitary operations, etc. However, this provides opportunities for programmer error which in principle could be avoided by having a functionality to define the subroutine once, and to derive these related subroutines from that specification. This might be mitigated by emitting OpenQASM code from a program written in an auxiliary language, but the specification of the program would be sensitive to the dependencies of the code in the auxiliary language, and therefore less portable. The emitted code will also remain unwieldly.

• One may instead write a gate subroutine, acting on many individual qubits, as a potentially complicated sequence of gates without use of control flow. Making such a gate specification human-readable in OpenQASM is likely to be difficult. This may be mitigated in part, again, by using a program in an axuiliary programming langauge, with the same issues as described above.

The proposed solution is to extend the functionality of gate subroutines, allowing them to have more complicated specifications — in particular, admitting the possibility of program logic similar to control-flow, the possibility of acting on typed registers and to admit typed classical parameters, and the possibility of acting on registers without an expectation of 'broadcasting' behaviour.

Proposed syntax

An extended syntax for gate declarations

Declarations for gates currently have formats of the form

    gate myGateA qmOpd1, qmOpd2 { /* ... body ... */ }
    gate myGateB (ang1, ang2, ang3) qmOpd { /* ... body ... */ }

and other variations. There is a separation between 'classical parameters' (the parameters ang1, ang2, and ang3 in the second example) and 'quantum operands'. This is for backwards-compatibility reasons, but is also useful to describe how the ctrl @ modifier allows the definition of further gate subroutines from existing ones. The classical parameters do not require an explicit type specification, and are all presumed to have an angle type. The quantum operands also do not require an explicit type specification, and are all presumed to have a qubit type. In this syntax, the declaration body consists of a sequence of gate invocations, without any further identifier declarations or program logic, which would be compiled into a single basic block.

We propose that the above syntax be left unchanged, except to admit some degree of program logic in the body of the specification (subject to constraints which we describe below). We also propose that this syntax be supplemented with a more versatile syntax for gate declarations, allowing somewhat more complex gate subroutines to be defined, as follows.

We propose a supplemental declaration syntax for gate subroutines, along the following lines:

    // a gate with a single register of size 8 as an operand
    gate subr1 : qubit[8] q { /* ... body ... */ }

    // a gate two registers as operands
    gate subr2 : qubit[5] x, qubit[3] y { /* ... body ... */ }

    // a gate with a register as an operand, and some classical parameters
    gate subr3 (int n, angle theta) : qubit[9] q { /* ... body ... */ }

These declarations differ from the existing gate syntax in two significant ways: the specification of types of the parameters / operands, and the presence of the delimiter : separating the quantum operands from the rest of the declaration. The purpose is to allow for the possibility of quantum operands which are not of type qubit, e.g., allowing for registers of qubits to be operands, and classical parameters which are not of type angle. (We suggest the introduction of the : delimiter to visually separate the type signature of the first quantum operand, from the identifier of the gate, in the case that there are no classical parameters.)

We propose that if the type of any classical parameter or quantum operand is specified, that the types of all classical parameters and quantum operands must be specified. Thus, only two forms of declaration syntax would exist for gate subroutines: the OpenQASM2 style, with no type specifications (and no : delimiter), and one with a complete type specification (including a : delimiter).

This declaration style, as with the existing syntax for gate declarations, separates the classical parameters from the quantum operands by grouping the former together in parentheses, and leaving the latter out. This is motivated by ways in which these subroutines may be invoked, with the ctrl @ gate modifier, as described further below.

An extended syntax for gate body definitions

We propose that the body of a gate subroutine be extended in the following ways:

• We allow for the declaration of local identifiers, albeit with the requirement that they are immutable after initialisation. (Their initial value may depend on other identifiers, and in particular complicated expressions of them.)

• We allow the gate body to include program logic, i.e. if statements and for loops (but not while loops), to deterministically specify the gate via a terminating sequence of invocations of other gates. (The iterator of the for loop is also treated as immutable, in the sense that their values are only modifiable by the for loop construct itself.)

The above constraints allow for more complicated unitary operations to be specified as gate definitions (see the QFT example below), while also allowing the compiler to easily describe inverse gates or coherently-controlled gates which may be invoked through the inv @ and ctrl @ gate modifiers.

We suggest that OpenQASM3 support invocations of such gates, where any expression of the program logic (i.e., the conditions of if statements and the iterator range of for loops) can be interpreted at compile time. This would allow the possibility of an initial implementation of this extension, which would allow each individual invocation to be compiled to a single basic block at compile-time. In particular, this would allow the compiler to solve the scheduling problem for such gate invocations.

In addition to the above, we propose for a gate to be allowed to recursively call itself, or to be involved in a mutually recursive family of gate subroutines. This feature was not previously useful when gate definitions could not involve program logic, but may have practical benefits if gate definitions can include program logic. We comment on the practical importance of allowing recursive gate definitions further below.

Invocation

We propose that the syntax to invoke a gate be left unchanged. That is: gate subroutines, however defined, should be invoked using the existing syntax, including the possibility of being invoked using a gate modifier such as inv @ or ctrl @. In particular, when a gate is invoked using the ctrl @ modifier, an additional (single-qubit) operand is added to the front of the list of quantum operands which are expected at invocation.

For reasons of backwards compatibility, we propose that invocations of a gate subroutine support broadcasting in the usual way, if it is invoked on an operand which is a qubit register (i.e., of type qubit[n]) when an argument of type qubit is expected. For instance,

   gate myGate : qubit q, qubit[5] rs { /* ... */ }

   qubit[3] qs;
   qubit[5] rs;
   myGate qs, rs; // equivalent to myGate q[0], rs; myGate q[1], rs; myGate q[2], rs;

would involve broadcasting over the register qs, which is provided on an argument where myGate expects an argument of a single qubit. (The broadcasting behaviour of OpenQASM2-style gate declarations are consistent with this, understanding all of the operands of such gate subroutines to be of type qubit.) However, we do not propose that broadcasting should be extended to any other type of operands to gate subroutines, as we suppose that this is likely to lead to confusion. Instead, for any operand of a gate which is not of type qubit, we require that the type of the operand match precisely the type which is expected on the basis of the gate declaration. For instance, extending the above example,

  qubit[15] rs2;
  array[qubit[5], 3] rs3;

  myGate qs, rs2; // invalid
  myGate qs, rs3; // invalid

the two invocations would fail to type-check at compile time, as in both cases we require that the second operand have type qubit[5].

Examples of use

We present a number of examples below. For the sake of brevity, most of these are 'toy' examples which may be more typical of an educational setting rather than application.

Simple unitary subroutine declarations and invocations

The following snippet relies on declarations of a Pauli x gate, a Z-rotation gate rz, and a controlled-NOT cx gate, to define operations acting on a register of two qubits. In this case, similar functionality could be described as a gate with two separate, one-qubit operands: we present it as using a single register of two qubits, to suggest a use-case in which one describes a register as a logical unit.

    // define a cyclic shift operation on a three-dimensional subspace
    // spanned by |00>, |01>, |10> of a two-qubit state, representing
    // addition of one (mod 3) on an encoded qutrit
    gate qutritX : qubit[2] a {
      x a[1];
      cx a[1], a[0];
      cx a[0], a[1];
    }

    // define a ‘clock’ operator on a three-dimensional subspace
    // spanned by |00>, |01>, |10>, a two-qubit state
    gate qutritZ : qubit[2] a {
      rz(2*pi/3) a[0];
      rz(-2*pi/3) a[1];
    }

In both cases the operand is a single register a consisting of two qubits.

Using gate modifiers

We may use these subroutines, to define further gate subroutines which apply gate modifiers to them:

    // define a controlled-addition gate on two qutrits,
    // where each qutrit is encoded in two qubits
    gate qutritCX : qubit[2] c, qubit[2] t {
      ctrl @ qutritX c[0], t;
      ctrl @ inv @ qutritX c[1], t;
    }

In this example, we define a gate subroutine acting on two operands, each of which is a register of two qubits. The unitaries are defined by modifications of the qutritX subroutine, in each case using the ctrl @ modifier. Applying a ctrl @ modifier adds a single qubit to the beginning of the list of quantum operands.

Using declarations as above, we may invoke qutritCX on the top level of an OpenQASM3 program as follows (relying on a h gate to realise a Hadamard operation):

    qubit[2] a;
    qubit[2] b;
    h a[0];
    qutritCX a, b;
    qutritZ a;

Note that the invocations of qutritCX and qutritZ are in effect similar in style to invocations of gates. However, they do not involve any broadcast semantics. In particular, invocations of these subroutines are only well-typed if they are invoked on quantum registers whose widths match the operands described in the respective subroutine declarations.

Classical parameters, local variables, and program logic

The new syntax for gate declarations may involve parameters which do not have an angle type, for example:

    // define an operation which simulates adding an integer (mod 3) to
    // the state of a qutrit, encoded in two qubits
    gate qutritPlus (int b) : qubit[2] a {
      if (b % 3 == 1) qutritX a;
      else if (b % 3 == 2) inv @ qutritX a;
    }

Note that, once the value of b is fixed, the definition of the gate above can in principle be reduced to a sequence of further gate invocations. The program logic allowed in the declaration of a gate subroutine cannot involve any measurements, so that it can be inverted and coherently controlled. For similar reasons, all parameters in the subroutine are immutable. Thus, using the above subroutine qutritPlus, one may write a subroutine invocation as follows:

    int s = 5001; // fixed parameter defined for a hypothetical numerical experiment
    qubit[2] t;
    qubit c;

    h c;

    ctrl @ qutritPlus(s) c, t;

Again, note that the additional quantum operand (a single qubit) introduced by the ctrl @ modifier, occurs after the classical argument s to the subroutine qutritPlus, as it would for a controlled gate invocation. As the parameter s is known at compile time, the conditionals in the body of qutritPlus(s) can be compiled to the presence or absence of a gate invocation; the ctrl @ modifier can then be applied to each gate which is actually invoked as a result.

We allow declarations of local variables within the scope of a gate subroutine as a convenience, but these too are immutable once initialised. This behaviour extends also to the iterators of for loops, which may be used in the definition of a gate subroutine:

    gate QFT256 : qubit[8] q {
      uint n = 8;
      for j in [0 : n-1] {
        h q[j];
        for k in [j+1 : n-1]
          ctrl @ Rz(pi / 2**(k-j+1)) q[j], q[k];
        }
      for uint j in [0:n-1]
        if (j != n-1-j)
          swap q[j], q[n-1-j]
    }

While the iterators j and k above change their values in the course of their loops, we treat them as run-time constants. This allows the inverse or a coherently controlled version of this same circuit to be easily computable from the subroutine definition. Compare this with the following equivalent gate subroutine declaration using the pre-existing declaration syntax:

    gate QFT256_OpenQASM2_style  q0, q1, q2, q3, q4, q5, q6, q7 {
      h q0;
      ctrl @ Rz(pi / 2) q0, q1;
      ctrl @ Rz(pi / 4) q0, q2;
      ctrl @ Rz(pi / 8) q0, q3;
      ctrl @ Rz(pi / 16) q0, q4;
      ctrl @ Rz(pi / 32) q0, q5;
      ctrl @ Rz(pi / 64) q0, q6;
      ctrl @ Rz(pi / 128) q0, q7;
      h q1;
      ctrl @ Rz(pi / 2) q1, q2;
      ctrl @ Rz(pi / 4) q1, q3;
      ctrl @ Rz(pi / 8) q1, q4;
      ctrl @ Rz(pi / 16) q1, q5;
      ctrl @ Rz(pi / 32) q1, q6;
      ctrl @ Rz(pi / 64) q1, q7;
      h q2;
      ctrl @ Rz(pi / 2) q2, q3;
      ctrl @ Rz(pi / 4) q2, q4;
      ctrl @ Rz(pi / 8) q2, q5;
      ctrl @ Rz(pi / 16) q2, q6;
      ctrl @ Rz(pi / 32) q2, q7;
      h q3;
      ctrl @ Rz(pi / 2) q3, q4;
      ctrl @ Rz(pi / 4) q3, q5;
      ctrl @ Rz(pi / 8) q3, q6;
      ctrl @ Rz(pi / 16) q3, q7;
      h q4;
      ctrl @ Rz(pi / 2) q4, q5;
      ctrl @ Rz(pi / 4) q4, q6;
      ctrl @ Rz(pi / 8) q4, q7;
      h q5;
      ctrl @ Rz(pi / 2) q5, q6;
      ctrl @ Rz(pi / 4) q5, q7;
      h q6;
      ctrl @ Rz(pi / 2) q6, q7;
      h q7;
      swap q0, q7;
      swap q1, q6;
      swap q2, q5;
      swap q3, q4;
    }

This definition is repetitive, and scales quadratically in the number of qubits on which it acts (where those qubits must tehmselves be described as separate operands to the subroutine). To modify this QFT256_OpenQASM2_style to represent a quantum Fourier transform which acts on a different number of qubits, would require the programmer to modify many lines of code, and provides opportunities for errors in the specifications of the angles and the operands. In contrast, we may modify the program logic of the shorter QFT256 declaration to represent a quantum Fourier transform acting on a different number of qubits, by modifying two lines of code: the specification of the quantum operand q, and the value of the identifier n.

Approaches to implementation

In the first instance, it would be practical to support invocations of gate subroutines which can be resolved to a single basic blocks at compile time (before execution). The motivation for this is to allow the duration of the gate to also be determined at compile-time, to facilitate scheduling. This represents a constraint on the arguments which one may use in the invocation of a gate subroutine, and also the functions which may be involved in the specification of a gate as a part of the program logic to describe its implementation in terms of simpler gate subroutines. Except for recursive gate declarations, this would be easy to do in principle; for recursive gate declarations, a limit to the recursive depth performed at compile time may be a useful expedient.

Context / related concepts

It is possible that gate subroutines can be usefully extended to allow operands which are neither qubits nor registers of qubits. For instance, on a hardware platform which natively supports a qutrit type (a three-level system), one might wish to define gate subroutines on qutrits which are not realised by two-qubit registers. This feature would allow gate definitions to be easily extended to accomodate such subroutines.

It is expected that the extended syntax for gate subroutines — in particular, recursive gate definitions — would be useful in combination with a capacity to define 'generic' subroutines, a template-like declaration which would allow the size of quantum operands to be determined by some 'meta-parameter'. (Such a notion of 'generic' subroutines could also be applied to def subroutines). Such generic subroutines would naturally allow for the possibility of subroutines to act on registers of many qubits, in a way which could be written in such a way to define useful higher-lvevel application libraries.

By supporting gate invocations whose program logic can be evaluated at compile-time, one would avoid introducing problems as a result either of dynamical dereferencing, or difficulty determining the duration of a gate invocation on a just-in-time basis. As approaches to dynamic dereferencing are resolved, and as techniques to bound the duration are developed (or support for operations of non-deterministic duration: e.g., certain procedures on error corrected memories), it may become practical to extend support to gate invocations whose program logic depends on values known only at run-time, so that the program logic may be realised in practise through control flow. For these reasons, it seems likely that there will be a time when gate invocations could be supported, in which the program logic depends on values known only at run-time. However, we do not propose that such invocations be supported in the near term.

Summary

In the medium to long term, complex unitary subroutines are likely to play an important role in the practise of quantum computation, whether these are coherently-performed reversible computations on registers, or subroutines to simulate Hamiltonian dynamics by performing a diagonalising unitary, simulating a diagonal operator, and then performing the inverse of that diagonalising unitary. Supporting such subroutines natively will improve the versatility of OpenQASM, and the portability of subroutines to perform such operations.

[ajavadia]

I chatted with @stevenheidel about this proposal. It seems like this proposal is basically a restriction on subroutines, i.e. a subroutine built out of unitary components and control-flow that is statically resolvable. So my main question is whether we can leverage most of what the subroutine syntax already gives us, rather than define a new language construct. In particular, can we "tag" a unitary subroutine as a special case of subroutine, something like:

unitary def qutritPlus (int b) : qubit[2] a {
      if (b % 3 == 1) qutritX a;
      else if (b % 3 == 2) inv @ qutritX a;
    }

The compiler should raise an error if there is any usage of measure or reset in the body, or if there is an assignment to b. Otherwise we would be free to invoke ctrl and inverse on unitary subroutine types.

(Side note: initially I thought about extending gate, but I decided against that. Gate declarations in QASM are for defining unitary matrices (hierarchically from a basic universal set of u/ctrl/gphase). The body is not prescriptive for how that gate is implemented. In contrast this proposal is much closer to subroutines where there is a prescription of the instructions that should happen to implement that subroutine)

Last question: when you say classical variables have to be immutable, doesn't that mean they should be defined as const? That seems like a good way of enforcing this.

[ndebeaudrap]

My main concern about regarding these as def subroutines, can be summarised by saying that I don't believe that the syntax for declaring (and similarly, invoking) def subroutines is as you describe it above. Aren't all of the quantum operands of a def subroutine, passed along with the other classical parameters? The issue with this is: if you then apply a ctrl @ modifier to this subroutine, you have to decide where to put the additional quantum operand. One could simply add it to the front of the list of parameters, but then the syntax for how ctrl @ modifies the invocation of unitary def subroutines would be distinct from the syntax for how it modifies the invocation of gate subroutines.

In my opinion at least, it would be better to maintain consistency with the syntax of gate invocations: even if unitary subroutines are distinct from gate subroutines, the way that they are used has a certain similarity. (Also: as with gate subroutines, the fact that the classical parameters are immutable motivates regarding the quantum operands as being quite different from the classical parameters. This motivates separating the classical parameters from the quantum operands, again as one does for gate subroutines.)

It is possible that, 'under the hood', the compiler might think of a unitary subroutine as a special variety of def subroutine: that the way that it is represented in intermediate stages is a minor elaboration of that case. I see no obvious obstacles to that, provided that the unitary subroutine body is consistent with the constraints described above on unitary declarations. If treating them this way makes them easier to implement, so much the better. However, the similarities to the way that gate subroutines are used motivates having a different syntax from def subroutines, unless we aim to extend or modify the syntax of def subroutines in general.

[ndebeaudrap]

Regarding declaring classical variables as const: I see an argument for requiring the programmer to declare each of them explicitly as const, if in the end it is decided to extend/modify the def subroutine syntax to accomodate unitary subroutines (or modify the proposed syntax for unitary subroutines to fit the existing def syntax).

Also: even if unitary subroutines are defined with a distinct syntax from def subroutines, I can still see an argument for requiring the programmer to explicitly indicate that classical variables are const, though in this case I think it would be less clear-cut. There would be a trade-off between requiring the programmer to do the bookwork of explicitly applying a type modifier which is in fact mandatory (making them jump through hoops to a small extent), versus the clarity of having the cosntraints of the variable being explicitly reinforced (even if from context it should be very easy for the programmer to infer those constraints). I think this would warrant some discussion with the Types and Casting WG.

[meamy]

Re: the question of gate versus def, can't unitary declarations be viewed as defining a family of unitary matrices indexed by classical parameters? This makes the feature strictly more powerful than unitary defs. Without generics the gate version effectively allows the definition of larger gates than are reasonably possible with the OPENQASM 2.0 gate syntax, something I think the QFT example points out.

My hunch is that a gate-style unitary should also be cleaner to spec formally in syntax, immutable classical parameters notwithstanding.

[stevenheidel]

In my conversation with Ali, one thing we agreed on is that "gate declarations in QASM are for defining unitary matrices".

Let's assume that we disallow conditionals within a gate declaration (more on that later). Something like "QFT256gate" can still be represented as a unitary matrix. But, as you point out, it leads to a lot of typing in both the declaration and the invocation.

Declaration

On declaration, the issue that we have is two-fold:

1. "The arguments in qargs cannot be indexed within the body of the gate definition."
2. For loops are not allowed within the body of a gate statement

Assuming we allowed both, the QFT256gate could be written as follows (with no local variable definitions and a strawman syntax):

gate QFT256 q[8] {
    for j in [0:8] {
        h q[j];
        for k in [j+1:8] {
            ctrl @ Rz(pi / 2**(k-j+1)) q[j], q[k];
        }
    }
    for j in [0:4]
        swap q[j], q[7-j];
}

This would be equivalent the the ~40 line statement listed above. At this point, we'd just be introducing a new shorthand syntax for defining large gates. The idea of the gate, and its possible representation as a unitary matrix, are still valid here.

Invocation

In the qutrit example, we have the gate:

gate qutritX a[2] {
    x a[1];
    cx a[1], a[0];
    cx a[0], a[1];
}

But when you try to call it, you have to unpack each qutrit:

qubit[2] myQutrit;
qutritX myQutrit[0] myQutrit[1];

This is because in OpenQASM "for convenience, gates automatically broadcast over registers." To solve this issue, we'd need a syntax to turn off the broadcasting and send each qubit in a register to a separate qubit in the list of qargs. (Perhaps the unpacking syntax from Python: qutritX *myQutrit.

On conditionals

I'm not convinced by the above example that conditionals are worth adding to gate definitions, and breaking the representation as a unitary matrix. The above example could be two gates: qutritAddOne and qutritAddTwo.

Summary

In summary, I believe we have three high level strategies to tackled this proposal:

1. Extend the gate declaration and invocation to support shorthand syntax (what I'm advocating for above)
2. Treat these as a subset of subroutines (unitary def), but deal with the issue at invocation of the ctrl modifier
3. Introduce a new structure (this proposal)

I'm very hesitant to do 3, because it makes it much harder to process gate invocations. Previously when we encountered a gate invocation that's all it could be, but now we'll need to determine whether it's instead a unitary, which completely changes the semantics.

[ndebeaudrap]

Thanks, Steven, I have a few thoughts on your proposal.

Regarding the issues with 'Strategy 3'

I would like to understand a bit more about the issues underlying what you call 'Strategy 3' for implementing more complex unitary subroutines.

Suppose you have an invocation of a subroutine, which could be a gate or could be a distinct unitary subroutine. It is clear that, at present, anything which has a 'gate-like' invocation (with separate classical prameters and quantum operands) must be a gate, and that 'Strategy 3' would change this, as unitary subroutines would also have gate-like invocation. So it is clear that some additional work would have to be done to determine the operation to be performed.

How much additional work would this involve? Naively, I would expect that upon reading a 'gate-like' invocation, one might consult a symbol table in any case to see whether the subroutine being invoked has been defined. One piece of information that the symbol table could include, is whether the identifier is a gate or a different sort of subroutine. Having identified that it is a gate, the compiler could presumably carry on as it currently does; having identified that it is a different sort of subroutine, it does something else. This information regarding whether the identifier is a gate or something else, could be recorded when the subroutine has been defined.

So: assuming that the above is correct, the question appears to boil down, to how much added work is required to modify the structure of the symbol table. Do I understand correctly that this is likely to be quite a lot of work? Is it possible to explain what the issues are there? Or is there some other problem that I have missed above?

Issues that I foresee with 'Strategy 1'

I have no objections, in general, with regarding so-called unitary subroutines as 'a way of specifying unitary matrices', in the sense that the compiler does not necessarily have to promise to implement the operation by performing the operations described by the programmer. (I assume here that the compiler would not necessarily attempt to compute an explicit matrix, but would use the declaration as a guide to obtaining some suitable representation for the matrix.)

—— Regarding 'if' statements

It's not clear to me why it is possible to accomodate for loops as a way of extending gate definitions, but not if statements. If there is any intention of allowing gate definitions to have arguments which might not be angles, then a for loop may have a bound which depends on an input parameter; an if statement could be treated similarly. In either case, depending on the value of some parameter (or perhaps some compile-time expression), an equivalent OpenQASM2-style gate definition could be determined at compile time and put in place.

Of course, if the intent is not to allow gate subroutines to have parameters which are not angles, then this is a functionality where the proposed functionality extends beyond what gate subroutines can support. It would also likely lead to problems when we consider how this functionality could be extended by allowing meta-parameters (defining not just a single unitary operator, but a family of unitary operators — such as the QFT on registers of various sizes).

Is there some difficulty involving if statements, or in allowing non-angle parameters, that I am missing?

—— Regarding broadcasting

If we provisionally consider the possibility that gate subroutines could be defined with some control flow (such as for loops, whether or not we allow if statements), then the main issue I see with interpreting these subroutines as gates is precisely the issue of broadcasting. It is indeed possible that we could overcome this by defining syntax for 'non-broadcastable' registers. (Indeed, this is an issue that the Types and Casting WG mused about some months ago in the context of def subroutines and arrays, but to no definite conclusion.)

I think that defining a special syntax for 'non-broadcastable registers', with 'broadcastable registers' being the default, is undesirable. Naturally I think that it is important to maintain backward compatibility with OpenQASM2, regarding broadcasting, at least for the time being. But requiring an explicit definition or indication that a register is 'non-broadcasting', is likely to arise frequently when we use these more complex unitary subroutines; and in particular we would have to address how this would be done when the 'register' is actually a slice or an alias. I think that this is likely to lead to cruft in the way OpenQASM is written, in the long run, and so I think this approach should be avoided. I think that this motivates giving 'Strategy 3' serious consideration, as a means of representing complicated unitary transformations which have different semantics when invoked on registers.

Summary

I appreciate that there may have to be some significant changes to how the compiler works, to accomodate this functionality. I would like to understand better why the things you would like to avoid, would be difficult to implement.

It is concievable that we can implement some interesing subset of my proposal, by trying to interpret these unitary subroutines as an extension of gate subroutines. My concern is that in doing so, we will end up making OpenQASM3 more complicated for programmers to write in practise, and furthermore make it difficult to support any of the other desirable features of this proposal. As this proposal is ultimately about a forward-looking feature (which will become more important with time), it seems important to me to make sure that we don't paint ourselves into a corner in how it is implemented.

[meamy]

So long as the parameters of a gate are (implicitly or explicitly) typed, I see no need for explicit syntax to "turn off" broadcasting with strategy 1. Unless there are conflicts I'm missing, qubit registers could be broadcasted when given to gates expecting an individual qubit. E.g.,

gate foo a { ... }
gate bar b[32] { ... }
gate baz a, b[32] { ... }

qubit[32] q;
qubit[16] r;

foo q[0];    // not broadcasted
foo q;       // broadcasted

bar q[0];    // type error
bar q;       // not broadcasted

baz r[0] q;  // not broadcasted
baz r q;     // broadcasted on r

You could write some very confusing code, like the last line above, but with implicit broadcasting IMO this is always going to be an issue regardless of whether the gate syntax is extended in this way.

[stevenheidel]

How much additional work would this involve? Naively, I would expect that upon reading a 'gate-like' invocation, one might consult a symbol table in any case to see whether the subroutine being invoked has been defined.

This is exactly how it would be implemented and it is not that much additional work for a reasonably sophisticated compiler. However we would lose an advantage that we have right now: that gate calls can be distinguished at parse time prior to doing any further compiler passes. The gate calls resolve to a separate AST node. This makes it very simple to manipulate programs involving lists of gate invocations. I would guesstimate that 95%+ of OpenQASM programs "in the wild" are merely a list of gate invocations, followed by measurement statements.

My other concern with around invocation looking the same between gates and unitaries is that one call is broadcasted and the other isn't. We had the same problem with subroutines while writing the paper. It would be unclear to the reader whether registers were broadcast or not. This is why we moved qubit arguments, which were originally outside the parenthesis like gates, to inside the parenthesis.

I have no objections, in general, with regarding so-called unitary subroutines as 'a way of specifying unitary matrices'
Is there some difficulty involving if statements, or in allowing non-angle parameters, that I am missing?

You're not missing anything involving if statements. It's really a question of runtime vs compile-time resolvable parameters.

Imagine we only allow angle parameters, and all gates must resolve to a unitary matrix at compile-time. Then there would still be a use for an if statement. For instance, while iterating through a loop variable I imagine the statement if i % 2 == 0 could be useful for performing a gate every other time. Therefore ignore my opposition to if statements in general.

For strategy 1 to work, the problem is not with if statements but rather with non-angle parameters. If non-angle parameters are introduced, then gates would become "a family of unitary matrices indexed by classical parameters" rather than a unitary matrix, as they are now. Strategy 1 in my mind relies on keeping the purpose of gates the same, while adding some additional syntax to add structure and reduce repetition.

It would also likely lead to problems when we consider how this functionality could be extended by allowing meta-parameters (defining not just a single unitary operator, but a family of unitary operators — such as the QFT on registers of various sizes).

This is what I'm interesting in learning more about tomorrow. I'd like to explore whether we can restrict classical parameters to only this purpose (defining sizes of registers) and how that would look for both strategies 1 and 3.

[stevenheidel]

I reviewed the revised proposal and support it (up to some minor details). I would like to ensure a majority of the TSC supports the high-level direction of the revised proposal before we jump into the finer points.

@ajavadia @bettinaheim @blakejohnson @levbishop @pschindler

[blakejohnson]

I support the proposal.