QCL as a Classical Language

Since the computational model of QPLs is that of a classical computer with a quantum oracle, QCL contains all features of a classical universal programming language, such as variables, loops, subroutines and conditional branching.

Structure of a QCL Program

The syntactic structure of a QCL program is described by a context free LALR(1) grammar (see appendix A) with statements and definitions as top symbols:

$$\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.

Data Types and Variables

The classic data-types of QCL are the arithmetic types int, real and complex and the general types boolean and string.

Table 3.1: classic types and literals

Type	Description	Examples
int	integer	1234, -1
real	real number	3.14, -0.001
complex	complex number	(0,-1), (0.5, 0.866)
boolean	logic value	true, false
string	character string	"hello world", ""

Constants

Frequently used values can be defined as symbolic constants. The syntax of a constant declaration is

$$\begin{eqnarray*} \mbox{\it const-def} \leftarrow \mbox{\tt const} \mbox{\it identifier} \mbox{\tt =} \mbox{\it expr} \mbox{\tt ;} \end{eqnarray*}$$

The definition of pi in the standard include file is e.g.

const pi=3.141592653589793238462643383279502884197;

Variables

The definition of variables in QCL is analogous to C:

$$\begin{eqnarray*} \mbox{\it var-def} \leftarrow \mbox{\it type} \mbox{\it... ...left[ \mbox{\tt =} \mbox{\it expr} \right] \mbox{\tt ;} \end{eqnarray*}$$

If no initial value is given, the new variable is initialized with zero, false or "", respectively. The value of a variable can be changed by an assignment, user input (see 3.2.4.3) and quantum measurement (see 3.4.1):

qcl> complex z;          // declare complex variable z
qcl> print z;            // z was initialized with 0
: (0.000000,0.000000) 
qcl> z=(0,1);            // setting z to i
qcl> print z;
: (0.000000,1.000000) 
qcl> z=exp(z*pi);        // assignment to z may contain z
qcl> print z;
: (-1.000000,0.000000) 
qcl> input z;            // ask for user input
? complex z [(Re,Im)] ? (0.8,0.6)
qcl> print z;
: (0.800000,0.600000)

Expressions

Operators

Table 3.2 shows all QCL operators ordered from high to low precedence.^3.1All binary operators are left associative, thus $a \circ b \circ c=(a \circ b) \circ c$. Explicit grouping can be achieved by using parentheses.

Table 3.2: QCL operators

Op	Description	Argument type
#	register size	quantum types
^	power	all arithmetic
	integer power	int
-	unary minus	all arithmetic
*	multiplication	all arithmetic
/	division	all arithmetic
	integer division	int
mod	integer modulus	int
+	addition	all arithmetic
-	subtraction	all arithmetic
&	concatenation	string, quantum types
==	equal	all arithmetic, string
!=	unequal	all arithmetic, string
<	less	integer, real
<=	less or equal	int, real
>	greater	int, real
>=	greater or equal	int, real
not	logic not	boolean
and	logic and	boolean
or	logic inclusive or	boolean
xor	logic exclusive or	boolean

Arithmetic operators generally work on all arithmetic data types and return the most general type (operator overloading), e.g.

qcl> print 2+2;          // evaluates to int
: 4 
qcl> print 2+2.0;        // evaluates to real
: 4.000000 
qcl> print 2+(2,0);      // evaluates to complex
: (4.000000,0.000000)

To allow for clean integer arithmetic there are two exceptions to avoid typecasts:

• The division operator / does integer division if both arguments are integer.
• The power operator ^ for integer bases is only defined for non-negative, integer exponents. For real exponents, the base must be non-negative.

Functions

QCL expressions may also contain calls to built-in or user defined functions. Table 3.3 shown all built-in unary arithmetic functions.

Table 3.3: QCL arithmetic functions

Trigonometric Funct.		Hyperbolic Funct.
sin(x)	sine of $x$	sinh(x)	hyperbolic sine of $x$
cos(x)	cosine of $x$	cosh(x)	hyperbolic cosine of $x$
tan(x)	tangent of $x$	tanh(x)	hyperbolic tangent of $x$
cot(x)	cotangent of $x$	coth(x)	hyperbolic cotangent of $x$
Complex Funct.		Exponential an related Funct.
Re(z)	real part of $z$	exp(x)	$e$ raised to the power of $x$
Im(z)	imaginary part of $z$	log(x)	natural logarithm of $x$
abs(z)	magnitude of $z$	log(x,n)	base-$n$ logarithm of $x$
conj(z)	conjugate of $z$	sqrt(x)	square root of $x$

In addition to the above, QCL also contains $n$-ary functions such as minimum or $\gcd$, conversion functions and the the pseudo function random() (table 3.4). As the latter is no function in the mathematical sense, it may not be used within the definition of user-functions and quantum operators.

Table 3.4: other QCL functions

Funct.	Description
ceil(x)	nearest integer to $x$ (rounded upwards)
floor(x)	nearest integer to $x$ (rounded downward)
max(x,...)	maximum
min(x,...)	minimum
gcd(n,...)	greatest common divisor
lcm(n,...)	least common multiple
random()	random value from $[0,1)$

Simple Statements

Assignment

The value of any classic variable can be set by the assignment operator =. The right-hand value must be of the same type as the variable. In contrast to arithmetic operators and built-in functions, no implicit typecasting is performed.

qcl> complex z;
qcl> z=pi;          // no typecast
! type mismatch: invalid assignment
qcl> z=conj(pi);    // implicit typecast

Call

The call of a procedure has the syntax

$$\begin{eqnarray*} \mbox{\it stmt} \leftarrow \mbox{\it identifier} \mbox{... ...mbox{\it expr} \right\} \right] \mbox{\tt )} \mbox{\tt ;} \end{eqnarray*}$$

As with assignments, no typecasting is performed for classical argument types.

Due to the potential side-effects on the program state, procedure-call may not occur within the definition of functions or operators.

Input

The input command prompts for user input and assigns the value to the variable $\mbox{\it identifier}$. Optionally a prompt string $\mbox{\it expr}$ can be given instead of the standard prompt which indicates the type and the name of the variable.

qcl> real n;
qcl> input "Enter Number of iterations:",n;
? Enter Number of iterations: 1000

Output

The print command takes a comma separated list of expressions and prints them to the console. Each output is prepended by a colon and terminated with newline.

qcl> int i=3; real x=pi; complex z=(0,1); boolean b;
qcl> print i,x,z,b;
: 3 3.141593 (0.000000,1.000000) false

Flow Control

Blocks

All flow control statements operate on blocks of code. A block is a list of statements enclosed in braces:

$$\begin{eqnarray*} \mbox{\it block} \leftarrow {\tt\verb*={=} \mbox{\it stmt} \left\{ \mbox{\it stmt} \right\}{\tt\verb*=}=} \end{eqnarray*}$$

Blocks may only contain executable statements, no definitions. Unlike C, a block is not a compound statement and always part of a control structure. To avoid ambiguities with nesting, the braces are obligatory, even for single commands.

Conditional Branching

The if and if-else statements allow for the conditional execution of blocks, depending on the value of a boolean expression.

$$\begin{eqnarray*} \mbox{\it stmt} \leftarrow \mbox{\tt if} \mbox{\it expr... ...it block} \left[ \mbox{\tt else} \mbox{\it block} \right]\end{eqnarray*}$$

If expr evaluates to true, the if-block is executed. If expr evaluates to false, the else-block is executed if defined.

Counting Loops

for-loops take a counter $\mbox{\it identifier}$ of type integer which is incremented from $\mbox{\it expr} _\mathit{from}$ to $\mbox{\it expr} _\mathit{to}$. The loop body is executed for each value of $\mbox{\it identifier}$.

$$\begin{eqnarray*} \mbox{\it stmt} \leftarrow \mbox{\tt for} \mbox{\it ide... ...p} \mbox{\it expr} _\mathit{step} \right] \mbox{\it block} \end{eqnarray*}$$

Inside the body, the counter is treated as a constant.

qcl> int i;
qcl> for i=10 to 2 step -2 {  print i^2; }
: 100 
: 64 
: 36 
: 16 
: 4 
qcl> for i=1 to 10 {  i=i^2; }          // i is constant in body
! unknown symbol: Unknown variable i

When the loop is finished, $\mbox{\it identifier}$ is set to $\mbox{\it expr} _\mathit{to}$.

Conditional Loops

QCL supports two types of conditional loops:

$$\begin{eqnarray*} \mbox{\it stmt} &\leftarrow & \mbox{\tt while} \mbox... ... block} \mbox{\tt until} \mbox{\it expr} \mbox{\tt ;} \end{eqnarray*}$$

A while-loop is iterated as long as a the condition $\mbox{\it expr}$ is satisfied. When $\mbox{\it expr}$ evaluates to false, the loop terminates. An until-loop is executed at least once and iterated until the condition $\mbox{\it expr}$ is satisfied.

Classical Subroutines

Functions

User defined functions may be of any classical type and may take an arbitrary number of classical parameters. The value of the function is passed to the invoking expression by the return statement. Local variables can be defined at the top of the function body.

int Fibonacci(int n) {        // calculate the n-th
  int i;                      // Fibonacci number
  int f;                      // by iteration
  for i = 1 to n {
    f = 2*f+i;
  }
  return f;
}

QCL requires functions to have mathematical semantics, so their value has to be deterministic and their execution must not have any side-effects on the program state.

qcl> int randint(int n) { return floor(n*random()); }
! in function randint: illegal scope: function random is not allowed 
in this scope
qcl> int foo=4711;
qcl> int bar(int n) { foo=foo+n; return foo; }
! in function bar: unknown symbol: Unknown local variable foo

Functions can call other functions within their body. Recursive calls are also allowed.

int fac(int n) {              // calculate n!
  if n<2 {                    // by recursion
    return 1;
  } else {
    return n*fac(n-1);
  }
}

Procedures

Procedures are the most general routine type and used to implement the classical control structures of quantum algorithms which generally involve evaluation loops, the choice of applied operators, the interpretation of measurements and classical probabilistic elements.

With the exception of routine declarations, procedures allow the same operations as are available in global scope (e.g. at the shell prompt) allowing arbitrary changes to both the program and the machine state. Operations exclusive to procedures are

• Access to global variables
• (Pseudo) Random numbers by using the pseudo-function random()
• Non-unitary operations on the machine state by using the reset and measure commands (see 3.4.1)
• User input by using the input command (see 3.2.4.3)

Procedures can take any number of classical or quantum arguments and may call all types of subroutines.

Footnotes

... precedence.^3.1

For the sake of completeness, table 3.2 also includes the operators # and &, which take quantum registers as arguments, see 3.4.3.1 and 3.3.3.2