Introducing QCL

Features

As pointed out in section 1.1.4, QCL is a high level language for quantum programming. Its main features are:

• a classical control language with functions, flow-control, interactive i/o and various classical data types (int, real, complex, boolean, string)
• 2 quantum operator types: general unitarian (operator) and reversible pseudo-classic gates (qufunct)
• inverse execution, allowing for on-the-fly determination of the inverse operator though caching of operator calls
• various quantum data types (qubit registers) for compile time information on access modes (qureg, quconst, quvoid, quscratch)
• convenient functions to manipulate quantum registers (q[n] - qubit, q[n:m] - substring, q&p - combined register
• Quantum memory management (quheap) allowing for local quantum variables
• Transparent integration of Bennet-style scratch space management
• Easy adaption to individual sets of elementary operators

The interpreter qcl additionally integrates a numeric simulator and a shell environment for interactive use.

Example: Discrete Fourier Transform in QCL

Table 2.1 shows the QCL implementation of Coppersmith's algorithm [7] of fast quantum discrete Fourier Transform for quantum registers of arbitrary length (see section 3.2.3 for details).

Table 2.1: dft.qcl Discrete Fourier Transform in QCL

Basically, dft.qcl contains of two loops: The outer loop performs a Hadamard transformations (see section 3.1.1.3) from the highest to the lowest qubit (Mix), while the inner loop performs conditional phase shifts (CPhase) between the qubits.

The dft operator takes a quantum register (qureg) q as argument. As pointed out in section 1.3.2, quantum register is not a quantum state by itself, but a pointer indicating the target qubits in the overall machine state, just like input and output lines in the gate model. To allow register size independent operator definitions, the number of qubits of a register can be determined at run time by the size operator #.

Inside the operator definition, sub-operators can be called just as sub-procedures in classic procedural languages. This means that the actual sequence of operators (either built in or user defined) can be fully determined at runtime, including the use of loops (in this case for-loops), conditional statements, etc.

Other then most classic languages, QCL has a strict mathematical semantics of functions and operators, meaning that two subsequent calls with the same parameters have to result in exactly the same operation. This requires the operators to be free from side-effects and forbids the use of global variables.

This allows for context dependent execution: DFT(q) called from toplevel works a expected, however if called as !DFT(q) (adjungation, thus inversion for unitary operators), all operators within DFT are also inverted and applied in reverse order. Inverse execution can also take place implicitly, when local quantum registers and Bennet-style scratch-space management is used.

To demonstrate the use of the new operator, let's start the QCL interpreter and prepare a test state:

$ qcl -b5 -i dft.qcl 
[0/5] 1 |00000>
qcl> qureg q[5];          // allocate a 5 qubit register 
qcl> Mix(q[3:4]);         // rotate qubits 3 and 4 
[5/5] 0.5 |00000> + 0.5 |10000> + 0.5 |01000> + 0.5 |11000>
qcl> Not(q[0]);           // invert first qubit
[5/5] 0.5 |00001> + 0.5 |10001> + 0.5 |01001> + 0.5 |11001>

We now have a periodic state with period $2^3=8$ and an offset of $1$ composed of $4$ basevectors to which we can apply the DFT.

qcl> dft(q);
[5/5] 0.353553 |00000> + -0.353553 |10000> + 0.353553i |01000> + 
-0.353553i |11000> + (0.25,0.25) |00100> + (-0.25,-0.25) |10100> +
(-0.25,0.25) |01100> + (0.25,-0.25) |11100>

The discrete Fourier transform ``inverts'' the period to $2^5/8=4$ and results in a periodic distribution with offset $0$. The information about the original offset is in the phase factors, and has no influence on the probability distribution:

qcl> dump q;
: SPECTRUM q: |43210>
0.125 |00000> + 0.125 |00100> + 0.125 |01000> + 0.125 |01100> + 
0.125 |10000> + 0.125 |10100> + 0.125 |11000> + 0.125 |11100>

``Uncomputing'' the DFT brings back the initial configuration:

qcl> !dft(q);
[5/5] 0.5 |00001> + 0.5 |10001> + 0.5 |01001> + 0.5 |11001>
qcl> exit;

The QCL Interpreter

The interpreter qcl simulates a quantum computer with an arbitrary number of qubits (default is the system word length) and is called with the following syntax:

$$\mbox{\tt qcl}\;[{\mbox{\it options}}]\; [{\mbox{\it QCL-file}] \ldots}$$

Options

qcl takes the following command-line options (defaults are given in parantheses):

Startup Options:
-h, --help                      display this message
-V, --version                   display version information
-i, --interactive               force interactive mode
-n, --no-default-include        don't read default.qcl on startup
-o, --logfile                   specify a logfile
-b, --bits=n:                   set number of qubits (32)
Dynamic Options (can be changed with the set statement):
-s, --seed=<seed-value>         set random seed value (system time)
-I, --include-path=<path>       QCL include path (.)
-p, --dump-prefix=<file-prefix> set dump-file prefix
-f, --dump-format=b,a,x         list base vectors as hex, auto or binary (a)
-d, --debug=<y|n>               open debug-shell on error (n)
-a, --auto-dump=<y|n>           allways dump quantum state in shell mode (n)
-l, --log==<y|n>                log external operator calls (n)
-L, --log-state==<y|n>          log state after each transformation (n)
-T, --trace==<y|n>              trace mode (very verbose) (n)
-S, --syntax=<y|n>              check only the syntax, no interpretation (n)
-E, --echo=<y|n>                echo parsed input (n)
-t, --test=<y|n>                test programm, ignore quantum operations (n)
-e, --shell-escape=<y|n>        honor shell-escapes (y)
-r, --allow-redefines=<y|n>     ignore redefines instead of error (n)

Logical values can be given in any common format including y[es]/n[o], 0/1 and t[rue]/f[alse]. Dynamic options can also be invoked from the shell or by QCL-Programs via the set command.

Default Include

Unless disabled with -no-default-include, qcl interprets the default include file default.qcl at startup. If no files are given at the command line, qcl starts in interactive mode, otherwise the files are executed in the given order and qcl exits.

Interactive Use

If started in interactive mode (no files given or option -i), qcl enters the top level shell and prompts for user input (qcl>). Subshells with private scope (see section 2.2.4.4) can be opened by the command shell; the prompt in this case is qcln>, where $n$ indicates the zero-based nesting depth. Subshells are also opened in case of errors when -debug=yes and prompt with qcln$.

qcl> set debug true;     // turn on debuging
qcl> real inv(real x) { return 1/x; }
qcl> print inv(0.0);     // trigger an error
! in function inv: math error: division by zero
qcl1$ list x;            // this is the argument to fac
: local symbol x = 0.000000:
real x
qcl1$ exit;              // close the debug shell
qcl> list x;             // no global x defined
: symbol x is undefined.

A shell is closed by EOF (usually Ctrl-d) or by the exit command. Closing the top level shell terminates the program.

Structure of a QCL Program

Notation

The syntactic structure of a QCL program is described by a context free LALR(1) grammar (see appendix B.1). For the formal definition of syntactic expressions, the following notation is used:

$$\begin{eqnarray*} \nonumber\,\mbox{\it expression-name}\,&\leftarrow &\,\mbox{\... ...w &\,\mbox{\it expression-def}\,_2 \\ \nonumber &\cdots&\cdots \end{eqnarray*}$$

Within expression definitions, the following conventions apply

Keywords

and other litteral text is set in courier

Subexpressions

are set in italic

Optional

expressions are put in $[$ square brakets $]$ Optional expressions can be repeated $0$ or $1$ times.

Multiple

expressions are put in $\{$ braces $\}$. Multiple expression can be repeated $0$, $1$ or $n$ times.

Alternatives

are written as $\,\mbox{\it alt}\,_1\vert\,\mbox{\it alt}\,_2\vert\ldots$ Exactly one alternative has to be chosen.

Grouping

of expressions can be forced by $($ round brackets $)$.

To simplify the notation of literals, the following character classes are defined:

• $\,\mbox{\it digit}\,\leftarrow$ decimal digit from 0 to 9.
• $\,\mbox{\it letter}\,\leftarrow$ alphabetic letter form a to z or A to Z. Case is significant.
• $\,\mbox{\it char}\,\leftarrow$ printable character except `"'.

A QCL Program is basically a sequence of statements and definitions either read from a file or directly from the shell prompt. (In the latter case, input is restricted to one line which is implicitly terminated by `;'.)

$$\begin{eqnarray*}\,\mbox{\it qcl-input}\,\leftarrow \left\{ \,\mbox{\it stmt}\,\vert\,\mbox{\it def}\, \right\}\end{eqnarray*}$$

Statements

Statements range from simple commands, over procedure-calls to complex control-structures and are executed when they are encountered.

qcl> if random()>=0.5 { print "red"; } else { print "black"; }
: red

Definitions

Definitions are not executed but bind a value (variable- or constant-definition) or a block of code (routine-definition) to a symbol (identifier).

qcl> int counter=5;
qcl> int fac(int n) { if n<=0 {return 1;} else {return n*fac(n-1);} }

Consequently, each symbol has an associated type, which can either be a data type or a routine type and defines whether the symbol is accessed by reference or call.

Expressions

Many statements and routines take arguments of certain data types. These expressions can be composed of literals, variable references and sub-expressions combined by operators and function calls.

qcl> print "5 out of 10:",fac(10)/fac(5)^2,"combinations."
: 5 out of 10: 252 combinations.

Comments

As C++, QCL supports two ways of commenting code. All comments are simply discarded by the scanner.

Line comments

are started with // and last until the end of the current line

C-style comments

are started with /* and terminated with */ and may continue over several lines. C-style comments may not be nested.

Include Files

The command include "filename" tells the interpreter, to process the file filename.qcl, before continuing with the current input file or command line. qcl looks for the file in the current directory and in the default include directory, which can be changed with the option include-path.

In interactive use include "filename" can be abbreviated by «filename.