BULLETIN OF THE POLISH ACADEMY OF SCIENCES

TECHNICAL SCIENCES

VOL. 58, NO. 1, 2010

1

Extending scientific computing system with
structural quantum programming capabilities
Piotr Gawron

Jerzy Klamka

Jarosław Adam Miszczak

Ryszard Winiarczyk

The Institute of Theoretical and Applied Informatics
of the Polish Academy of Sciences
Bałtycka 5, 44-100 Gliwice, Poland

arXiv:1006.1549v1 [cs.PL] 8 Jun 2010

November 12, 2009

Abstract—We present a basic high-level structures
used for developing quantum programming languages.
The presented structures are commonly used in many
existing quantum programming languages and we use
quantum pseudo-code based on QCL quantum programming language to describe them.
We also present the implementation of introduced
structures in GNU Octave language for scientific computing. Procedures used in the implementation are available
as a package quantum-octave, providing a library of
functions, which facilitates the simulation of quantum
computing. This package allows also to incorporate highlevel programming concepts into the simulation in GNU
Octave and Matlab. As such it connects features unique
for high-level quantum programming languages, with the
full palette of efficient computational routines commonly
available in modern scientific computing systems.
To present the major features of the described package
we provide the implementation of selected quantum
algorithms. We also show how quantum errors can be
taken into account during the simulation of quantum
algorithms using quantum-octave package. This is
possible thanks to the ability to operate on density
matrices.
Index Terms—quantum information, quantum programming, models of quantum computation

I. I NTRODUCTION
Quantum information theory aims to harness the
quantum nature of information carriers in order to
develop more efficient algorithms and more secure
communication protocols [1], [2], [3], [4]. Unfortunately, counterintuitive laws of quantum mechanics
make the development of new quantum information
processing procedures highly non-trivial task. This can
be seen as one of the reasons why only few truly
quantum algorithms were proposed [5], [6].
The laws of quantum mechanics are in many cases
very different from those we know from the classical
world. That is why one needs to seek for the novel
methods for describing information processing which
involves quantum elements. To this day several formal
E-mail address: gawron@iitis.pl (Corresponding author)

models were proposed for the description of quantum
computation process [7], [8], [9], [10], [11], [12].
The most popular of them is the quantum circuit
model [7], which is tightly connected to the physical
operations implemented in a laboratory. It allows to
operate with the basic ingredients of quantum information processing – namely qubits, unitary evolution
operators and measurements. However, it does not
provide too much flexibility concerning operations on
more sophisticated elements required to develop scalable algorithms and protocols eg. quantum registers or
classical controlling operations.
Another model widely used in the study of theoretical aspects of quantum information processing is the
quantum Turing machine [7]. This model is mainly
used in the analysis of quantum complexity problems [13]. Its main advantage it that it provides method
of comparing efficiency of classical and quantum algorithms. Unfortunately quantum Turing machine, in
analogy to its classical counterpart, operates on very
basic data and thus it cannot be easily used to construct
quantum algorithms.
Both quantum circuit model and quantum Turing
machine share some serious drawbacks concerning
lack of support for high-level programming and very
limited flexibility. These problems were addressed in
the recent research in the area of quantum programming languages [14], [15], [16].
Quantum programming languages are based on the
Quantum Random Access Machine (QRAM) model.
QRAM is equivalent, with respect to its computational
power, to the quantum circuit model or quantum
Turing machine. However, it has strictly distinguished
two parts: quantum and classical. The quantum part
is responsible for performing parts of a algorithm
which cannot be computed efficient by a classical
machine. The classical part is used to control quantum
computation. This model is used as a basis for most
quantum programming languages [14].
Among high-level programming languages designed
for quantum computers we can distinguish imperative

and functional languages. The later are seen by many
researchers as a means of providing robust and scalable methods for developing quantum algorithms [17].
We, however, focus on the imperative paradigm as it
provides more straightforward way of implementing
high-level quantum programming concepts.
This paper is organized as follows. In Section II we
briefly describe the QRAM model of quantum computer and introduce the quantum pseudocode, which
was designed to describe this model. In Section III
we introduce high-level programming structures used
in quantum programming languages. These structure
are based on the QRAM model of quantum computer.
In Section IV the implementation of presented concepts is described and quantum-octave package
is presented. In Section V implementation of quantum algorithms using quantum-octave package
is presented. Also the analysis of quantum errors is
provided in the case of quantum search algorithm.
Finally Section VI summarize the presented work and
provides reader with some concluding remarks.

of the RAM models is its resemblance with the realworld computers.
B. Quantum RAM model and quantum pseudocode
Quantum Random Access Machine (QRAM) model
is build as an extension of the classical RAM model.
Its main goal is to provide the ability to exploit quantum resources. Moreover, it can be used to perform any
kind of classical computation. The QRAM allows us
to control operations performed on quantum registers
and provides the set of instructions for defining them.
Schematic presentation of such architecture is provided
in Figure 1.
the sequence of elementary gates

the description of algorithm in
abstract model

QC L Qu a n tu m C o mp u ta ti o n La n g u a g e (3 2 q u b i ts, se e d
1 1 5 6 3 2 2 5 9 0 )[0 /3 2 ] 1 |0 >
q cl > q u re g a [1 0 ];
q cl > H(a );
[1 0 /3 2 ] 0 .0 3 1 2 5 |0 > + ... + 0 .0 3 1 2 5 |1 0 2 3 > (1 0 2 4
te rms)
q cl > C No t(a [2 ],a [5 ]);
[1 0 /3 2 ] 0 .0 3 1 2 5 |0 > + ... + 0 .0 3 1 2 5 |1 0 2 3 > (1 0 2 4
te rms)
q cl > l i st a ;
: g l o b a l a = <0 ,1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 >
q u re g a [1 0 ]
q cl > d u mp a [1 ];
: S P E C T R UM a [1 ]: <1 >
0 .5 |0 >, 0 .5 |1 >
q cl >

Quantium III

probability distribution for
futher analysis

classical controlling device

quantum memory

the outcome of measurement

II. QRAM MODEL OF QUANTUM COMPUTATION
Quantum random access machine is interesting for
us since it provides convenient model for developing
quantum programming languages. However, these languages and basic concepts used to develop them are
our main area of interest. For this reason here we
provide only the very basic introduction to the QRAM
model. Detailed description of this model is given in
[18] and [19] together with the description of hybrid
architecture used in quantum programming.

Fig. 1. The model of classically controlled quantum machine [19].
Classical computer is responsible for performing unitary operations
on quantum memory. The results of quantum computation are
received in the form of measurement results.

The quantum part of QRAM model is used to
generate probability distribution. This is achieved by
performing measurement on quantum registers. The
obtained probability distribution has to be analysed
using a classical computer.
Quantum algorithms are, in most of the cases,
described using the mixture of quantum gates, mathematical formulas and classical algorithms. The first
attempt to provide a uniform method of describing
quantum algorithms was made in [23], where the
author introduces a high-level notation based on the
notation known from computer science textbooks [24],
[25].
In [18] Knill introduced the first formalized language for description of quantum algorithms. Moreover, it was tightly connected with the model of
Quantum Random Access Machine.
Quantum pseudocode proposed by Knill [18] is
based on conventions for classical pseudocode proposed in [24, Chapter 1]. Classical pseudocode was
designed to be readable by professional programmers,
as well as people who had done a little programming. Quantum pseudocode introduces operations on
quantum registers. It also allows to distinguish between classical and quantum registers. In quantum
pseudocode quantum registers are distinguished with
an underline. They can be introduced by applying
quantum operations to classical registers or by calling

A. Classical RAM model
As in many situations in quantum information science, the QRAM models is based on the concepts
developed to describe classical computational process
– in this case on the Random Access Machine (RAM)
model. The classical model of random access machine
(RAM) is the example of more general register machines [20], [21], [22].
The Random Access Machine consists of an unbounded sequence of memory registers and finite number of arithmetic registers. Each register may hold an
arbitrary integer number. The programme for the RAM
is a finite sequence of instructions Π = (π1 , . . . , πn ).
At each step of execution register i holds an integer
ri and the machine executes instruction πκ , where
κ is the value of the programme counter. Arithmetic
operations are allowed to compute the address of a
memory register.
Despite the difference in the construction between
Turing machine and RAM, it can be easily shown that
Turing machine can simulate any RAM machine with
polynomial slow-down only [21]. The main advantage
2

a subroutine which returns a quantum state. In order
to convert a quantum register into a classical register
measurement operation has to be performed.
The example of quantum pseudocode is presented
in Listing 1. It shows the main advantage of QRAM
model over quantum circuits model – the ability to
incorporate classical control into the description of
quantum algorithm.

|q0 i

H

S

×

T

•

|q1 i

H
•

|q2 i

C. Requirements for quantum programming language
Taking into account QRAM model we can formulate
basic requirements which have to be fulfilled by any
quantum programming language [9], [26], [15].
• Completeness: Language must allow to express
any quantum circuit and thus enable the programmer to code every valid quantum programme
written as a quantum circuit.
• Extensibility: Language must include, as its subset, the language implementing some high level
classical computing paradigm. This is important
since some parts of quantum algorithms (for example Shor’s algorithm) require non-trivial classical computation.
• Separability: Quantum and classical parts of the
language should be separated. This allows to execute any classical computation on purely classical
machine without using any quantum resources.
• Expressivity: Language has to provide high level
elements for facilitating the quantum algorithms
coding.
• Independence: The language must be independent from any particular physical implementation
of a quantum machine. It should be possible to
compile a given programme for different architectures without introducing any changes in its
source code.

S
•

H ×

Fig. 2. Quantum circuit representing quantum Fourier transform
for three qubits. Elementary gates used in this circuit are described
in [1].

Procedure: F OURIER(a, d)
Input: A quantum register a with d qubits. Qubits arenumbered
form 0 to d − 1.
Output: The amplitudes of a are Fourier transformed over Z2d .
C: a s s i g n v a l u e t o c l a s s i c a l v a r i a b l e
d

ω ← ei2π/2
C: p e r f o r m s e q u e n c e o f g a t e s
for i = d − 1 to i = 0
for j = d − 1 to j = i + 1
if aj then R 2d−i−1+j (ai )
ω
C: number o f l o o p s e x e c u t i n g p h a s e d e p e n d s on
C: t h e r e q u i r e d a c c u r a c y o f t h e p r o c e d u r e
H(ai )

III. H IGH - LEVEL PROGRAMMING STRUCTURES
A. Quantum memory
Quantum memory is a set of qubits indexed by
integer numbers. Quantum register is a set of indices pointing to distinct qubits. We will denote those
registers as r1 , r2 , . . . or in case of single qubits
as q1 , q2 , . . .. The state of a quantum memory is a
quantum state of size equal to the number of qubits. In
the case of quantum-octave we operate on density
matrices (although some operations on state vectors
are allowed). We will denote the state of the quantum
memory by ρ.
Following operations on quantum memory are allowed:
• Allocation of new register of size n:

C: c h a n g e t h e o r d e r o f q u b i t s
for j = 0 to j = d
2 −1
SWAP(aj , ad−a−j )

Listing 1. Quantum pseudoceode for quantum Fourier transform on
d qubits. Quantum circuit for this operation with d = 3 is presented
in Figure 2.

Operation H(ai ) executes a quantum Hadamard
gate on a quantum register ai and SWAP(ai , aj )
performs SWAP gate between ai and aj . Operation
Rφ (ai ) executes a quantum gate R(φ) is defined as


1 0
R(φ) =
,
(1)
0 eiφ

. . 0}|,
ρt+1 = ρt ⊗ |0| .{z
. . 0}ih0| .{z

on the quantum register ai . Using conditional construction

n

if aj then Rφ (ai )

it is easy to define controlled phase shift gate. Similar
construction exists in QCL quantum programming language [19]. In Section IV we describe implementation
of this construction in quantum-octave.
The measurement of a quantum register can be
indicated using an assignment

•

where ⊗ denotes tensor product, |·i the column
vector and h·| the dual vector.
Deallocation of a register indexed by register r:
ρt+1 = Trr (ρt ) ,

•

aj ← aj .

(3)

where Trr (ρ) denotes partial trace of ρ with
regard to the subsystem indexed by r.
Unitary evolution U of the quantum memory:
ρt+1 = U ρt U † .

3

(2)

n

(4)

•

Application of quantum channel Ki on the quantum memory:
X
ρt+1 =
Ki ρt Ki † .
(5)

1) Condition on quantum variable: The if-then-else
structure controlled by a quantum variable and acting
on a quantum variable was introduced in QCL [28],
[19].
In Figure 3 the realisation of this concept is presented. If qubit q0 is in the state |1i the G1 gate is
applied to qubit q1 , otherwise the gate G2 is applied.
We may write this circuit in the following way:

i
•

Measurement in the computational basis:
X
ρt+1 =
|iihi|ρt |iihi|,

(6)

i

P (i) = Tr (|iihi|ρt ) ,

(7)

IFq0 (G1 q1 )ELSE(G2 q1 ) = N otq0 G2q1 |q0 N otq0 G1q1 |q0 .
(10)

where i enumerates the states of computational
basis.
For a solid introduction to quantum computation the
reader may refer to book by Nielsen and Chuang [1],
where all the needed notions are explained in detail.
In quantum computation, construction of the unitary gate is the essential part of quantum algorithm
(program) design process. It is a difficult task to
write a quantum program using only elementary set
of gates ie. CNot and one qubit rotations. Therefore it
is desirable to introduce some techniques that facilitate
the process of composition of complex quantum gates.
Some of those techniques are presented below. We
will refer to implementation of those techniques in
quantum-octave which is described in details in
section IV.

q b i t q1 , q2
i f ( q1 ) t h e n
G1 (q2 )
else
G2 (q2 )

Fig. 3.

|q0 i

•

|q1 i

G1

•

⊕

⊕

G2

Example of a simple quantum if-then-else structure.

For a given control register rc , target register rt
and two quantum gates G1 and G2 , we may define
quantum condition in the more general way, namely
Y

IFrc (G1 rt )ELSE(G2 rt ) =

N oti G2rt |rc N oti G1rt |rc ,

(11)

i∈P(rt )\{∅}

where P(·) denotes the power set.
2) Condition on mixture of classical and quantum
variables: One may consider the relation between the
state of quantum register and the value of the classical
variable. By [[x]]r we will denote a numerical value of
ordered (in ascending order) elements of the register
x in regard to register r, for example the value of
[[{4, 9}]]{2,4,7,9} is 10. By [r] we will denote the
value of the register in order to use it as argument for
arithmetic comparison. For example [r] < 4 means:
“all those values of r that are less than four.”
Code and circuit in Figure 4 show the idea and the
implementation of conditional operation controlled by
expression ‘less than’ operating on classical constant
and quantum register.

B. Composed and controlled gates
1) Composed gate: Given one-qubit unitary gate
G, quantum register r, and size of the gate s we can
construct composed gate Urs according to the formula:

s
O
G if i ∈ r,
s
Ur =
Xi , where Xi =
. (8)
I if i ∈
/r
i=1

2) Controlled gate with multiple controls: Given
one-qubit unitary gate G, quantum register rc we call
control, and quantum register rt we call target, and
size of the gate s we can construct controlled gate
Urst |rc according to the formula:
Ns
Ns
Urst |rc =
X + i=1 Yi , where
 i=1 i
|0ih0| if i ∈ rc ,
Xi =
if i ∈
/ rc ,
 I
. (9)
if i ∈ rt ,
 G
|1ih1| if i ∈ rc ,
Yi =

I
if i ∈
/ rc ∪ rt

Less than
quantum-octave

pseudocode

r=newregister (4) ;
q1= n e w r e g i s t e r ( 1 ) ;
q2= n e w r e g i s t e r ( 1 ) ;

qnibble r
q b i t q1 , q2
i f ( r < 4 ) then
G1 (q2 )
else
G2 (q1 )

We assume that rt ∩ rc = ∅. Sometimes we will omit
the size parameter s.

qif ( . . .
q r l t ( q u r e g ( q1 ) , 4 ) , . . .
{G1 , q u r e g ( q2 ) } , . . .
{G2 , q u r e g ( q1 ) } )

Quantum Circuit

C. Conditionals
One of high-level technique used in quantum programming are quantum conditions [27]. The main idea
behind quantum conditions is construction of quantum
gates controlled by predicates on control registers.

|r0 i ⊕

•

⊕

•

|r1 i ⊕

•

⊕⊕

•

⊕

•

|r2 i ⊕

•

⊕⊕

•

⊕⊕

•

⊕⊕

•

⊕

•

|r3 i ⊕

•

⊕⊕

•

⊕⊕

•

⊕⊕

•

⊕⊕

•

⊕

•

|q1 i
|q2 i

⊕

•

⊕

•

⊕

•

⊕

•

⊕

G2
G1

G1

G2

•
•
...

⊕

•
•
G2

G1

Fig. 4. Example of quantum conditional operation with inequality.

4

In the general case, gate implementing any relation
(marked as ~) can be constructed in the following way:
Y

IF[rc ]~N (G1 rt )ELSE(G2 rt ) = (12)
Y

N oti G2rt |rc N oti
N oti G1rt |rc N oti ,

i∈F

i f ( q1 and q2 ) t h e n
G1 (q3 )
else
G2 (q4 )

where sets T and F are defined as follows:
T = P(rc ) \ {x|x ∈ P(rc ) ∧ [[x]]rc ~ N }, (13)

Note that T ∪ F = P(rc ).
In quantum-octave standard arithmetic relations
=, 6=, <, >, ≤, ≥ are implemented.

|q1 i

•

|q2 i

•

|q3 i

G1

⊕

We may consider more complicated expression on
quantum registers. For example logical operators and
quantum pointers. Logical operators allow to apply
an controlled operation to the target register only if
a given logical expression on control registers is true.
A quantum pointer allows to apply controlled gate on
the target register selected by the state of the control
register.
1) Logical expressions on quantum variables: The
gate that implements logical expression (denoted here
by ) is constructed according to the following equation:

⊕
⊕

G2

•

⊕

•

⊕

•

⊕⊕

•

⊕

G2

G2

Or
quantum-octave

pseudocode

q1= n e w r e g i s t e r
q2= n e w r e g i s t e r
q3= n e w r e g i s t e r
q4= n e w r e g i s t e r

q b i t q1 , q2 , q3 , q4
i f ( q1 or q2 ) t h e n
G1 (q3 )
else
G2 (q4 )

(1)
(1)
(1)
(1)

;
;
;
;

qif ( . . .
qror ( . . .
q r e q ( q u r e g ( q1 ) , 1 ) , . . .
q r e q ( q u r e g ( q2 ) , 1 ) ) , . .
{G1 , q u r e g ( q3 ) } , . . .
{G2 , q u r e g ( q4 ) } )

Quantum Circuit
|q1 i

•

(15)

|q2 i

•

•

|q3 i

G1

G1

(16)

|q4 i

i∈T

where sets T and F are defined as follows:

F = P(rc ) \ {x1 ∪ x2 |x1 ⊆ rc1 , x2 ⊆ rc2

∧¬ [[x1 ]]rc1 ~1 N1  [[x2 ]]rc2 ~2 N2 }

•

Fig. 5. Example of quantum conditional operation with “and”
operator.

IF[rc1 ]~1 N1 [rc2 ]~2 N2 (G1 rt )ELSE(G2 rt ) =

Y
N oti G1rt |rc N oti ,
N oti G2rt |rc N oti

T = P(rc ) \ {x1 ∪ x2 |x1 ⊆ rc1 , x2 ⊆ rc2

∧ [[x1 ]]rc1 ~1 N1  [[x2 ]]rc2 ~2 N2 },

;
;
;
;

qif ( . . .
qrand ( . . .
q r e q ( q u r e g ( q1 ) , 1 ) , . . .
q r e q ( q u r e g ( q2 ) , 1 ) ) , . .
{G1 , q u r e g ( q3 ) } , . . .
{G2 , q u r e g ( q4 ) } )

•

|q4 i

D. Expressions

i∈F

(1)
(1)
(1)
(1)

Quantum Circuit

F = P(rc ) \ {x|x ∈ P(rc ) ∧ ¬([[x]]rc ~ N )}. (14)

=

q1= n e w r e g i s t e r
q2= n e w r e g i s t e r
q3= n e w r e g i s t e r
q4= n e w r e g i s t e r

q b i t q1 , q2 , q3 , q4

i∈T

Y

And
quantum-octave

pseudocode

Fig. 6.
operator.

⊕

•

⊕
⊕

•

⊕

•

⊕

•

⊕⊕

•

⊕

G1
G2

Example of quantum conditional operation with “or”

(17)
Formally, a quantum pointer controlled by register
rc with target rt is constructed in the following way:
Y

P OIN Trt (G[rc ] ) =
N otrc \i G[[i]]rc |rc N otrc \i .

and rc = rc1 ∪ rc2 .
An example of quantum conditional gate controlled
by logical expression defined on quantum registers is
presented in Figures 5 and 6.
2) Quantum pointers: In analogy to the concept of
pointers and indirect addressing in classical programming, one may introduce quantum pointers. The idea
is to use control register to control on which of the
target registers an operation should be applied.
Let us assume that one has the n-bit control register
and a set of 2n -bit target registers. The control register
stores the address of target register to which given
unitary operation shall be applied. In order to visualise
the use of a quantum pointer an example is shown in
Figure 7.

i∈P(rc )

(18)
IV. PACKAGE Q U A N T U M - O C T A V E
Package quantum-octave [29], [30], [31] provides a quantum programming, simulation and analysis
language implemented as a library of functions for
GNU Octave [32].
GNU Octave is computer algebra system (CAS) and
high level programming language designed primarily
to perform numerical calculations. The basic data
5

Pointer
quantum-octave

pseudocode
qreg [ 2 ] q1
q n i b b l e q2

q1= n e w r e g i s t e r ( 2 ) ;
q2= n e w r e g i s t e r ( 4 ) ;

i f (∗q1 ) t h e n
G(q2 )

q p o i n t e r (G, q u r e g ( q1 ) , q u r e g ( q2 ) )

Quantum Circuit
•
|q0 i ⊕ • ⊕ ⊕ • ⊕

|q1 i ⊕ • ⊕
|q2 i

of Quantum Fourier transform in quantum-octave.
It can be compared to pseudo code version of the same
procedure listed in Listing 1.

•

2

•

⊕ • ⊕ •

|q4 i
|q5 i

6

8

G

|q3 i

4

10

G

function r e t = dft ( gatesize )
n= g a t e s i z e ;
c i r =id ( n) ;
for i =[1: n ]
f o r j = [ 1 : i −1]
c i r = c i r c u i t ( c i r , c p h a s e ( p i / ( 2 ^ ( i−j ) ) , j , i ,
gatesize ) ) ;
endfor
cir = c i r c u i t ( cir , productgate (h , i , gatesize ) ) ;
endfor
ret = cir = c i r c u i t ( cir , f l i p (n) ) ;
endfunction

Listing 2.

G
G

Quantum Fourier transform in quantum-octave

Package quantum-octave can operate on sparse
and full matrices depending on users choice. Sparse
matrices need much less memory to store but operations on them may be slower. Full matrices tend to
consume huge memory space, but operations on them
are generally faster. In case of full matrices it should be
possible to operate on states of size up to ten qubits on
a contemporary workstation. Sparse matrices should
allow to simulate the quantum systems of up to 20
qubits.
Although quantum-octave is not, strictly speaking, a programming language ready to program real
quantum devices, with some effort it can be transformed in such a way that it would be able to compile
a high level programs to some sort of quantum assembler. One should note that broad range of functions
allowing the analysis of states is implemented in the
package. Those function are described in the following
section.

Fig. 7. Example of simple quantum conditional operation controlled
by quantum pointer.

structure in Octave is a matrix (integer, real or complex), therefore it is a natural choice as a basis for the
implementation of quantum programming language.
GNU Octave supports sparse matrices and distributed computing in shared and distributed memory
models. GNU Octave is a very flexible and easily
extendible tool. It is also free software and it can be
used in a wide range of operating systems.
A. Design choices
The main goal of the design of quantum-octave
is to provide a flexible and useful tool for simulation of
quantum information processing. Therefore it is based
on GNU Octave a high-level scientific programming
language. This allows for a seamless integration of
very efficient matrix operations and numerical procedures with the library of specialized functions provided
by quantum-octave. As GNU Octave is to large
extent compatible with Matlab, provided functions
can be also used to simulate and analyse quantum
algorithms in Matlab.
One of the unique features of quantum-octave
is its ability to operate on both pure and mixed quantum states. It allows to perform unitary as well as nonunitary evolution represented by quantum channels.
Quantum gates can be constructed by the user in
various ways: by calling provided subroutines, by
building their own subroutines, by using quantum
control structures. Additionally the user can build and
use quantum channels or use those already provided.
Most of the quantum-octave functions operate on
quantum registers and therefore the quantum operations build with their use are re-allocable.
A good illustration of those features is presented in
the following listing 2 that contains the implementation

B. Description
Package quantum-octave is designed to allow
the user to operate on different levels of abstraction.
User can prepare complex gates and quantum channels
from basic primitives such as single qubit rotations,
controlled gates, single qubit channels. Most of the
functions that form this library operate on quantum
registers, which makes the preparation of quantum
gates and channels very “natural”. The library is
implemented in such a way that depending of user’s
choice it may operate on full or sparse matrices.
quantum-octave can work in two modes: as a
library or as a programming language/simulator. Library mode is the default. To switch to language/simulator mode one has call quantum_octave_init()
function. In case of the second mode quantum-octave allocates and manages an internal
quantum state and maintains the quantum registers.
Such functions as evolve(), applychannel(),
6

measurecompbasis() operate directly on the internal state. Listings of Deustch’s 3 and Grover’s 4
algorithms show use of language/simulation mode.
1) Convention: Following conventions are used in
quantum-octave.
– Quantum register is horizontal integer vector containing indices of qubits starting from one.
– Ket is vertical complex vector.
– Bra is horizontal complex vector.
– Density matrix is complex square matrix always
of dimension n-th power of two by n-th power
of two.
– Binary string is 0,1-horizontal vector, that encodes a binary number. Order of bits is from MSB
to LSB.
– Size of the gate or channel is always given in
terms of a number of qubits it acts on. If size is
written in square brackets it means that it can be
omitted if the gate or channel acts on the whole
system and quantum-octave was initialised.
2) Quantum gates: Package quantum-octave
supplies set of elementary gates known in quantum
computation.
– sx, sy, sz – return one-qubit Pauli operators sx
– σx , sy – σy , sz – σz .
– id(n) – returns identity matrix: In .
– roty(a), rotz(a), rotx(a) – return rotation matrix by angle a around appropriate axis.
– qft(n) – returns quantum Fourier transform on
n qubits.
– swap(size, qubits) – returns swap gate of
a given size that swaps qubits given as twoelement vector.
– qubitpermutation(permutation)
– returns unitary gate that performs given
permutation.
– h – returns one-qubit Hadamard gate.
– phase(p0,p1) – returns one-qubit phase gate,
with p0, p1 phase parameters.
3) Basic functions: Following functions are essential to prepare a quantum state and to implement
a quantum algorithm, protocol or game.
– ket(binvec) – returns ket for given binary
string.
– ketn(int,size) – returns a ket of size 2size
for given integer number.
– state(pure_state) – returns density matrix
for a given ket.
– mixstates(a1,mixed_state1,[a2,
mixed_state2,...]) – returns convex
combination of density matrices with coefficients
a1, a2, ....
– productgate(gate,targetreg[,size])
– returns a controlled gate of a given size that
applies given gate on target register. See
7

Eq. 8.
– controlledgate(gate,controlreg,
targetreg[,size]) – returns a controlled
gate of given size that applies gate on specified target register and is controlled by
control register. See Eq. 9.
4) Quantum conditional operations: The functions
listed below implement quantum conditional operations, quantum expressions and pointers. They are
useful to simplify the implementation.
– qif(expression,ifpart,elsepart,
size) – returns quantum gate of given
size, controlled by expression that applies ifpart if expression is true and
elsepart if expression is false. ifpart and
elsepart are cellarrays in the form: {gate,
target_register}. See Eq. 11.
– qreq(register,integer) – returns expression: [register] equals integer. See
Eq. 12.
– qrne(register,integer) – returns expression: [register] not equal integer.
– qrge(register,integer) – returns expression: [register] is greater or equal to
integer.
– qrgt(register,integer) – returns expression: [register] is greater than integer.
– qrle(register,integer) – returns expression: [register] is lesser or equal to
integer.
– qrlt(register,integer) – returns expression: [register] is lesser than integer.
– qrin(register,set) – returns expression:
[register] is in set.
– qror(expr1,expr2) – returns logical or on
expressions expr1 and expr2. See Eq. 15.
– qrand(expr1,expr2) – returns logical and
on expressions expr1 and expr2.
– qpointer(gate,contrregister,
targteregister[,size])
–
returns
quantum gate of given size, controlled by
controll register that applies gate on
target register. See Eq. 18.
5) Evolution, channels and measurement: The following group of functions allows to control the evolution of quantum states and introduces the application
of channels and measurement.
– evolve(evolution[,state]) – applies
unitary evolution to the state, returns the
result of the evolution. See Eq. 4.
– channel(name,p) – returns Kraus operators
acting on one qubit, parametrised by p
allowed names are: "depolarizing",
"amplitudedamping", "phasedamping",
"bitflip",
"phaseflip"
and

– wernersinglet(a) – returns 2-qubit Werner
state: a(|00i − |11i)(h00| − h11|) + (1 − a) 4I .
8) Analysis: Package quantum-octave provides standard functions for analysis of quantum states,
widely used in quantum information literature. Among
them the most important are:
– negativity(state, qubits) – computes
negativity of the state in respect to qubits.
– entropy(state) – computes Von Neuman
entropy of the state.
– concurrence(state) – computes concurrence of the state.
– fidelity(rho, sigma) – computes fidelity
between density matrices rho and sigma.
– fidelitypuremixed(psi, rho) – computes fidelity between ket psi and density matrix
sigma.
– tracenorm(state) – computes trace norm of
the state.
– partialtranspose(state,
targetreg) – returns matrix being partial
transposition of state matrix in regard
to target register.
The next section presents the applications of quantum-octave and various programming techniques
for solutions of quantum programming problems.

"bitphaseflip".
– localchannel(kraus, targetreg[,
chsize]) – returns a channel being the
extension of defined by kraus operators
channel, acting on target register.
– applychannel(elements[,state])
–
applies on the state non unitary evolution
defined by set of Kraus operators (elements),
returns the result of the evolution. See Eq. 5.
– ptrace(state, targetreg) – returns reduced density matrix for the state with
target register traced out. See Eq. 3.
– circuit(gate[, gate]) – returns circuit
composed of the sequence of gates.
– measurecompbasis([state]) – returns
the probability distribution of the σz measurement
on the given state.
– isunitary(gate) – returns true if the
gate is unitary, otherwise returns false.
– ischannel(operators) – returns true if
the operators form valid quantum channel,
otherwise returns false.
– collapse(distribution) – chooses and
returns a basis state at random according to
distribution.
6) Computation and control: Following functions
allows to control the quantum heap and configure the
behaviour of the library.
– quantum_octave_init() – initialises the
simulated system, creates quantum state with zero
qubits allocated and empty list of registers.
– set_quantum_octave_sparse([true |
false]) – switches on or off use of sparse
matrices by all quantum-octave functions.
– newregister(size) – creates new register
of given size, allocates qubits on quantum heap,
returns register id.
– clearregister(regid) – removes regid
register from quantum heap. Traces out appropriate qubits from the internal state.
– qureg(regid) – returns quantum register
to which regid points.
– getstate() – returns the internal quantum
state.
7) Well known states: Some of the states commonly
used in quantum algorithms are implemented in the
library as separate functions.
– ghz(n) – returns Greenberger-Horne-Zeilinger
state for n qubits: √12 (|0i⊗n + |1i)⊗n .
– phip – returns Bell |Φ+ i state: √12 (|00i + |11i).
– phim – returns Bell |Φ− i state: √12 (|00i − |11i).
– psip – returns Bell |Ψ+ i state: √12 (|01i + |10i).
– psim – returns Bell |Ψ− i state: √12 (|01i − |10i).
– maximallymixed(n) – return density matrix
maximally mixed state: n1 In .

V. E XAMPLES AND APPLICATIONS
In what follows the applications of quantum-octave and various high-level programming
techniques are discussed . It is shown how quantum
processes, such as algorithms may be implemented,
simulated and analysed with this tool.
A. Deutsch’s problem
One of the simplest quantum algorithms is
Deutsch’s algorithm. Although it may seem trivial,
this algorithm shows two very important features of
quantum computation. The first one is taht by taking
the advantage of a superposition one can compute any
binary function for all its arguments in one step. The
second features is is that it is only possible to retrieve
information about property of a function and not on
its values.
Let us assume that we have a black box that is
usually called the oracle. This box computes a function
f : {0, 1} → {0, 1}. We do not know if that function
is constant f (0) = f (1) or injective f (0) = f (1). In
classical case we have to ask the oracle twice to check
which kind the function f is. But in quantum case it is
possible to solve this problem asking the oracle only
once.
The algorithm goes as follows:
1) Prepare the state: |Ψi = |0i ⊗ |1i,.
8

2) Apply the Hadamard H ⊗2 gate on the state |Ψi,
you will get
|Ψ1 i =

|0i + |1i |0i − |1i
√
⊗ √
.
2
2

9

(19)

3) Apply the gate Uf : |xi⊗|yi → |xi⊗|f (x) ⊕ yi
on the state |Ψ1 i; you will get:
( |0i+|1i |0i−|1i
± √2 ⊗ √2
for constant f ,
|Ψ2 i =
|0i−|1i
|0i−|1i
± √2 ⊗ √2
for injective f .
(20)
4) Apply H ⊗ I on the state |Ψ2 i; you will get:
(
√
±|0i ⊗ |0i−|1i
for constant f ,
2
|Ψ3 i =
|0i−|1i
±|1i ⊗ √2
for injective f .
(21)
5) Measure state of the first qubit, you will get
|0i in case of constant function, |1i for injective
function.
Quantum circuit representation of Deutsch’s algorithm is presented in Figure 8. The Uf gate provide
a reversible implementation of function f and the
denotes a measurement.
symbol

|0i

H

x
y

|1i
Fig. 8.

x
Uf

H

7

11
13
15
17
19
21
23
25
27

Listing 3.

3
5

Deutsch algorithm in quantum-octave

B. Grover’s algorithm
To illustrate more advanced usage of the presented
concepts we use the quantum algorithm for searching
a unordered database. The algorithms was proposed by
Grover [33], [34], [35] and its detailed description and
analysis can be found in [36], [37]. Here we present the
implementation of Grover’s algorithm which presents
the features of quantum-octave related to the observation of quantum errors. We show the propagation
of initial errors during the execution of the algorithm.
Grover’s search algorithm is one of the most important quantum algorithms. This is especially true
since many algorithmic problems can be reduced to
exhaustive search. However, like in the case of any
quantum procedure, the efficiency of the algorithm
depends on the ability to avoid errors during the
procedure. Thus, it is important how quantum errors
affect the executions of the algorithm.
1) Statement of the problem: Let X be a set and
let f : X → {0, 1}, such that

1 ⇔ x = x0
f (x) =
, x ∈ X,
(22)
0 ⇔ x 6= x0

FE

y ⊕ f (x)

H

Deutsch’s algorithm

The implementation of Deutsch’s algorithm presented in listing 3 is an introductory example of
application of quantum-octave for simulation of
a quantum algorithm with all basic steps of computation: initialization of the quantum computer, unitary
evolution and measurement.
Below we describe simulation steps (compare with
circuit in Figure 8). Numbers on the left refer to the
line numbers in Listing 3.
5
: initialisation of the simulator,
7, 8 : allocation of registers,
10-17 : definition of all four possible oracles,
19
: application of N ot on second qubit,
20
: application of H ⊗ H,
21
: application of the oracle,
22
: application of H ⊗ I,
24
: tracing out of second register,
26
: return the probability distribution of the
measurement outcome.
1

# d e c l a r e and a l l o c a t e r e g i s t e r s
r1= n e w r e g i s t e r ( 1) ;
r2= n e w r e g i s t e r ( 1) ;
# declare functions
f {1}= i d ( 2 ) ;
f {2}= p r o d u c t g a t e ( sx , q u r e g ( r 2 ) ) ;
f {3}= q i f ( q r e q ( q u r e g ( r 1 ) , 1 ) , . . .
{ sx , q u r e g ( r 2 ) } , . . .
{ id , qureg ( r2 ) }) ;
f {4}= q i f ( q r e q ( q u r e g ( r 1 ) , 0 ) , . . .
{ sx , q u r e g ( r 2 ) } , . . .
{ id , qureg ( r2 ) }) ;
# do t h e a l g o r i t h m
e v o l v e ( p r o d u c t g a t e ( sx , q u r e g ( r 2 ) ) ) ;
evolve ( p r o d u c t g a t e ( h , [ qureg ( r1 ) , qureg ( r2 ) ] ) ) ;
e v o l v e ( f {num } ) ;
evolve ( p r o d u c t g a t e ( h , qureg ( r1 ) ) ) ;
# t h r o w away s e c o n d r e g i s t e r
c l e a r r e g i s t e r ( qureg ( r2 ) ) ;
# r e t u r n t h e outcome
r e t =measurecompbasis ( ) ;
endfunction

for some marked x0 ∈ X.
For the simplicity we assume that X is a set of
binary strings of length n. Therefore |X| = 2n and
f : {0, 1}n → {0, 1}.
We can map the set X to the set of states over H⊗n
in the natural way as
x ↔ |xi.

(23)

The goal of the algorithm is to find the marked
element. This is achieved by the amplification of the
appropriate amplitude [36], [37].
2) The algorithm: The Grover’s algorithm is composed of two main procedures: the oracle and the
diffusion.

# input : i d e n t i f i e r of the function
# o u t p u t : s t a t e a f t e r e x e c u t i o n o f Deutsch ’ s
algorithm
f u n c t i o n r e t = d e u t s c h ( num )
# i n i t i a l i z e the simulation
quantum_octave_init () ;

9

with real coefficients:
1
αk = √
cos (2k + 1) θ,
N −1

a) Oracle: By oracle we understand a function
that marks one defined element. In the case of this
algorithm, the marking of the element is done by
negation of the amplitude of the state that we search
for.
With the use of elementary quantum gates the oracle
can be constructed using an ancilla |qi in the following
way:
O|xi|qi = |xi|q ⊗ f (x)i.
(24)
|0i − |1i
√
,
2

1
sin(θ) = √ .
N

|0i − |1i
|0i − |1i
√
= (−1)f (x) |xi √
,
2
2

(25)

(26)

and by tracing out the ancilla we get:
O|xi = −(−1)f (x) |xi.

(27)

Thus the oracle marks a given state by inverting its
amplitude.
b) Diffusion: The operator D rotates any state
around the state

√
Iterate N π4 times
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 






1
|ψi = √
2n

x=0

|xi,




|0i

(28)

Oracle
|xi→(−1)f (x) |xi




..
.

Fig. 9.

c) Grover iteration: The first step of the algorithm is to apply Hadamard gate H ⊗n on all the qubits.
Then we apply gate G = DO several times.
d) Number of iterations: Application of diffusion
operator on the base state |ni gives
2 X
− H ⊗n I0 H ⊗n |ni = −|x0 i +
|yi.
(30)
N y

H ⊗n

Diffusion
|0i→|0i
|xi→−|xi
forx>0

FE


H ⊗n 

..
.


FE







|0i

D = −H ⊗n (2|0ih0| − I)H ⊗n = 2|ψihψ| − I. (29)




_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _



The circuit for Grover’s algorithm.

3) Graphical interpretation: There a exists very
nice graphical interpretation of Grover’s algorithm.
Let |αi denotes the sum of states orthogonal to the
state we are searching for |x0 i
X
1
|αi = √ n
|xi,
(35)
2 − 1 x6=x
0

Application of this operator on any state gives
X
2 X
D|xi =
αx (−|xi + y
|yi)
N y
x
X
=
(−αx + 2s)|xi,

and for consistence we will write |βi = |x0 i. Then,
on the plane spanned by |αi and |βi, we can observe
of evolution of the state vector.
By putting values from equation 33 into equation
32 we get following relation:

x

1 X
s=
αx
N x



H ⊗n

D may written in the following form:

where

FE



|0i

n

2X
−1

(34)

Therefore the coefficients αk , βk are periodic functions
of k. After several iterations amplitude of βk rises and
others drop. The influence of the marked state |x0 i
on the state of the register is that the initial state |si
evolves towards the marked state.
The βk attains its maximum after approximately
√
π
4 N steps. Then it begins to fall. Thus, the number
of steps needed to transfer
√ the initial state towards the
marked state is of O( n). In the classical case the
number of steps is of O(n).
e) Measurement: The last step of the Grover’s
algorithm is the measurement. Probability of obtaining
of the proper result is |βk |2 .

then by substitution, equation 24 is re-transformed to:
O|xi

(33)

where θ is an angle that fulfils the relation:

If the register |qi is prepared in the state:
|qi = H|1i =

βk = sin (2k + 1) θ,

Gk |si = cos((2k + 1)θ)|αi + sin((2k + 1)θ)|βi. (36)

(31)

Exemplar behaviour of this equation for 23 states is
presented in Figure 10.
4) Implementation: Listing 4 presents the implementation of function grover. We will apply quantum noise at the end of each Grover iteration and
observe its influence on its efficiency.
To simulate this behaviour we will insert the code
from Listing 5 after line 21 of the implementation.

is arithmetic mean of coefficients αx , x = 0, . . . , 2n −
1.
k-fold application of Grover’s iteration G on initial
state |si leads to [36]:
X
Gk |si = αk
|xi + βk |x0 i,
(32)
x6=x0

10

43
45

(2∗ k e t n ( 0 , l ) ∗ b r a n ( 0 , l ) − i d ( l ) ) , . . .
productgate (h , register , l ) . . .
);
endfunction

Listing 4.

2
4

Grover’s algorithm in quantum-octave

applychannel (
localchannel (
c h a n n e l ( channelname , p ) , qureg ( r1 )
)
);

Listing 5.

Adding noise to Grover’s algorithm

a) Simulation results: The results of the simulation of noisy Grover’s algorithm acting on system of
size from three to six qubits when system is affected by
noise modelled with depolarizing channel are shown
in Figure 11. One may observe that rate of successful
application of the algorithm drops quickly with raising
amount of noise. This effect is more significant for
larger systems. This result clearly indicates that it
is not possible to successfully implement Grover’s
algorithm in presence of large amounts of noise if no
error correction scheme is applied.

Fig. 10. Visualisation of Grover’s algorithm [1]. Projection on
plane spanned by |αi and |βi. Vector |ψi is flat superposition of
all the possible states.

depolarizing channel
1
3-qubit state
4-qubit state
5-qubit state
6-qubit state

1

3
5
7
9
11
13

15
17
19
21
23
25
27
29
31
33

probability of finding of sought element

0.9

# f u n c t i o n i m p l e m e n t i n g Grover ’ s a l g o r i t h m
# i n p u t : number we a r e l o o k i n g f o r , s i z e o f t h e
system
# output : probability d i s t r i b u t i o n after
#
execution of the algorithm
f u n c t i o n r e t = g r o v e r ( num , S )
# i n i t i a l i z e the simulation
quantum_octave_init () ;
# allocate register
r1= n e w r e g i s t e r (S) ;
# number o f e l e m e n t s
N=2^ l e n g t h ( q u r e g ( r 1 ) )
# c a l c u l a t e number o f i t e r a t i o n s
k = f l o o r ( ( p i / 4 ) ∗ s q r t (N) ) ;
# prepare the system in f l a t s u p e r p o s i t i o n of base
states
evolve ( p ro d uc tg a te ( h , qureg ( r1 ) ) ) ;
# Grover i t e r a t i o n s
for i = 1: k
# ask the oracle
e v o l v e ( o r a c l e ( num , q u r e g ( r 1 ) ) ) ;
# diffuse
evolve ( d i f f u s e ( qureg ( r1 ) ) ) ;
endfor
# r e t u r n p r o b a b i l i t y d i s t r i b u t i o n of base s t a t e s
r e t =measurecompbasis ( ) ;
endfunction

39
41

0.7
0.6
0.5
0.4
0.3
0.2
0.1

0

0.2

0.4

0.6

0.8

1

noise amount α

Fig. 11. Influence of depolarizing channel parametrized by single
real number α on probability of successful finding of sought element
in Grover’s algorithm implemented with 3, 4, 5 and 6 qubits.

VI. S UMMARY
We have introduced an original solution to the
problem of simulation of quantum processes. This
solution is provided by quantum-octave, a library
that is build upon GNU Octave high level programming language, which provides high-level quantum
programming structures.
Although strictly speaking, quantum-octave is
not a programming language but a library, together
with GNU Octave, it is very convenient and flexible
tool. Programs written in quantum programming languages, such as QCL, can be easily rewritten using
this library, thanks to the use of quantum memory,

# function implementing oracle
# i n p u t : number t o mark , s i z e o f t h e s y s t e m
# o u t p u t : g a t e i m p l e m e n t i n g o r a c l e o f t h e s i z e 2^ l
f u n c t i o n r e t = o r a c l e ( num , r e g i s t e r )
l =length ( r e g i s t e r ) ;
r e t = id ( l ) ;
r e t ( num +1 , num + 1 ) = −1;
endfunction

35
37

0.8

# function implementing oracle
# i n p u t : r e g i s t e r on w h i c h i m p l e m e n t d i f f u s i o n
# o u t p u t : d i f f u s i o n g a t e o f t h e s i z e 2^ l
function r e t = diffuse ( r e g i s t e r )
l =length ( r e g i s t e r ) ;
ret = circuit ( . . .
productgate (h , register , l ) , . . .

11

registers and routines. Scalable programs can be easily implemented in quantum-octave, so the programmer does not have to think about details of the
implementation.

[18] E. Knill, “Conventions for quantum pseudocode,” Los Alamos
National Laboratory, Tech. Rep. LAUR-96-2724, 1996.
[19] B. Oemer, “Structured quantum programming,” Ph.D. dissertation, Technical University of Vienna, 2003.
[20] S. A. Cook and R. A. Reckhow, “Time-bounded random
access machines,” in Proceeedings of the forth Annual ACM
Symposium on Theory of Computing, 1973, pp. 73–80.
[21] C. H. Papadimitriou, Computational complexity. AddisonWesley Publishing Company, 1994.
[22] J. C. Shepherdson and H. E. Strugis, “Computability of
recursive functions,” Journal of the ACM, vol. 10, no. 2, pp.
217–255, April 1963.
[23] R. Cleve and D. P. DiVincenzo, “Schumacher’s quantum data
compression as a quantum computation,” Phys. Rev. A, vol. 54,
no. 4, pp. 2636–2650, Oct 1996.
[24] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein,
Introduction to Algorithms, 2nd ed. The MIT Press, 2001.
[25] J. E. Hopcroft and J. D. Ullman, Wprowadzenie do teorii
automatów, j˛ezyków i obliczeń.
Wydawnictwo Naukowe
PWN, 2003.
[26] S. Bettelli, “Toward an architecture for quantum programming,” Ph.D. dissertation, Università di Trento, February 2002.
[27] P. Gawron, “High level programming in quantum computer
science,” Ph.D. dissertation, The Institute of Theoretical and
Applied Informatics of the Polish Academy of Sciences, 2008.
[28] B. Oemer, “Quantum programming in QCL,” Master’s thesis,
TU Viena, 2000.
[29] P. Gawron and J. A. Miszczak, “Didactic tools for teaching
quantum informatics,” Annales UMCS Informatica AI, vol. 1,
no. 2, 2004.
[30] ——, “Simulations of quantum systems evolution with
quantum-octave package,” Annales UMCS Informatica AI,
vol. 1, no. 2, 2004.
[31] ——, “Numerical simulations of mixed states quantum
computation,” Int. J. Quan. Inf., vol. 3, no. 1, pp. 195–199,
2005. [Online]. Available: doi:10.1142/S0219749905000748
[32] J. W. Eaton, GNU Octave Manual. Network Theory Limited,
2002.
[33] L. Grover, “A fast quantum mechanical algorithm for database
search,” in Proc. 28th Annual ACM Symposium on the Theory
of Computation. New York, NY: ACM Press, New York,
1996, pp. 212–219.
[34] L. K. Grover, “Quantum mechanics helps in searching for a
needle in a haystack,” Phys. Rev. Lett., vol. 79, p. 325, 1997,
arXiv:quant-ph/9706033.
[35] ——, “A framework for fast quantum mechanical algorithms,”
in Proceedings of 30th Annual ACM Symposium on Theory of Computing (STOC), 1998, pp. 53–62, arXiv:quantph/9711043.
[36] S. Bugajski, “Quantum search,” Archiwum Informatyki Teoretycznej i Stosowanej, vol. Tom 13, no. z. 2, pp. 143–150,
2001.
[37] S. J. Lomonaco, “Grover’s quantum search algorithm,” Proceedings of Symposia in Applied Mathematics, vol. 58, pp.
181–192, 2002.
[38] “Project
quantum-octave,”
web-page
http://quantumoctave.sf.net/.

ACKNOWLEDGEMENTS
We acknowledge the financial support by the Polish
Ministry of Science and Higher Education under the
grant number N519 012 31/1957 and by the Polish
research network LFPPI. The numerical calculations
presented in this work were performed on the Leming
server of The Institute of Theoretical and Applied
Informatics of the Polish Academy of Sciences.
Package quantum-octave is distributed as free
software and it can be downloaded from the project
web-page [38].
R EFERENCES
[1] M. A. Nielsen and I. L. Chuang, Quantum Computation and
Quantum Information. Cambridge University Press, 2000.
[2] M. Hirvensalo, Quantum computing. Springer, 2001.
[3] S. Bugajski, J. Klamka, and S. Wegrzyn, “Foudations of quantum computing. Part I,” Archiwum Informatyki Teoretycznej i
Stosowanej, vol. 13, no. 1, pp. 97–142, 2001.
[4] ——, “Foudations of quantum computing. Part II,” Archiwum
Informatyki Teoretycznej i Stosowanej, vol. 13, no. 1, pp. 137–
149, 2001.
[5] P. W. Shor, “Why haven’t more quantum algorithms been
found?” Journal of the ACM, vol. 50, no. 1, pp. 87–90, 2003.
[6] ——, “Progress in quantum algorithms,” Quantum Information
Processing, vol. 3, no. 1-5, 2004.
[7] D. Deutsch, “Quantum theory, the Church-Turing
principle
and
the
universal
quantum
computer,”
Proc. Roy. Soc. Lond., vol. A 400, p. 97, 1985,
http://www.qubit.org/people/david/David.html.
[8] ——, “Quantum computational networks,” Proc. Roy. Soc.
Lond., vol. A 425, p. 73, 1989.
[9] S. Bettelli, L. Serafini, and T. Calarco, “Toward an architecture
for quantum programming,” Eur. Phys. J. D, vol. 25, no. 2, pp.
181–200, 2003.
[10] S. Gudder, “Quantum computational logic,” International
Journal of Theoretical Physics, vol. 1, no. 42, pp. 39–47, 2003.
[11] A. van Tonder, “A lambda calculus for quantum computation,”
SIAM J.COMPUT., vol. 33, p. 1109, 2004. [Online]. Available:
doi:10.1137/S0097539703432165
[12] C. Moore and J. P. Crutchfield, “Quantum automata and
quantum grammars,” Theoretical Computer Science, vol. 237,
no. 1-2, pp. 275 – 306, 2000. [Online]. Available: http://
www.sciencedirect.com/science/article/B6V1G-43FWYP1-H/
2/201e1de6cd57eb5d309d61622092bd1d
[13] E. Bernstein and U. Vazirani, “Quantum complexity theory,”
SIAM Journal on Computing, vol. 26, no. 5, pp. 1411–
1473, 1997. [Online]. Available: http://www.cs.berkeley.edu/
~vazirani
[14] S. Gay, “Quantum programming languages: Survey and bibliography,” Bulletin of the European Association for Theoretical
Computer Science, 2005.
[15] J. A. Miszczak, “Probabilistic aspects of quantum programming languages,” Ph.D. dissertation, The Institute of Theoretical and Applied Informatics of the Polish Academy of
Sciences, 2008.
[16] S. Gay, “Bibliography on quantum programming languages,”
2007, web-page http://www.dcs.gla.ac.uk/˜simon/quantum/.
[17] T. Altenkirch and J. Grattage, “A functional quantum programming language,” in Proceedings. 20th Annual IEEE Symposium on Logic in Computer Science. IEEE Computer Society,
2005, pp. 249–258.

12

