next up previous contents
Next: Quantum States and Variables Up: Quantum Programming Previous: Introduction   Contents

Subsections


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:


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

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

next up previous contents
Next: Quantum States and Variables Up: Quantum Programming Previous: Introduction   Contents

(c) Bernhard Ömer - oemer@tph.tuwien.ac.at - http://tph.tuwien.ac.at/~oemer/