Introduction

Computers and Programming

As has been illustrated in 2.1.2, a computer is basically a device which

1. holds a physical machine state $S$
2. is capable of performing a set of well defined instructions $\mathbf{I}$ to transform between machine states
3. provides means to initialize and measure the machine state while interpreting $S$ as discrete symbolic computational states $s$

The sequence of instructions $\pi={\langle I_1,I_2,\ldots I_n \rangle}$ to transform the initial state $S$ into the final state $S_n$ is called a program.

The way $\pi$ is actually specified, depends on the computational model; possibilities vary from explicit enumeration, over feed forward networks (as in logical circuits) and decision trees up to finite automatons (as in the Turing machine).

A general requirement of any specification method is, that the mechanism used to produce $\pi$ must not be more powerful or complex than the machine it is executed on, which would defy the purpose of using a computer in the first place.

Complexity Requirements

As has been pointed out in 2.3.4, QPLs use a classical universal programming language to define the actual sequence $\pi$ of instructions for a quantum computer. According to the above criterion, this approach is useful, only if quantum computers are at least as powerful as universal classical computers.

If we consider a quantum computer with the Toffoli gate (see 2.2.2.4) as the only available instruction, then any transformation of the machine state has to be of the form

$${\vert\Psi \rangle}={\vert i \rangle}\longrightarrow{\vert ... ...angle} \quad\mathrm{with}\quad g: \mathbf{B}^n\to\mathbf{B}^n$$ (3.1)

Since the Toffoli gate is universal for reversible boolean logic, any bijective boolean function $g$ can directly be implemented on a quantum computer.

A general boolean function $f$ over $\mathbf{B}^n$, can be implemented by using a pseudo-classical operator $F$

$$F {\vert i,0 \rangle}={\vert i,f(i) \rangle}\quad\mathrm{with}\quad {F}^\dagger F=I$$ (3.2)

So any classically computable function $f$ can also be implemented on a quantum computer. Moreover, C. H. Bennet has shown that a reversible implementation of $f$ can be done with a maximal overhead of $O(2)$ in time and $O(\sqrt{n})$ in space complexity (see 3.5.2). [8]

On the other hand, as a general $n$-qubit quantum state consists of maximally $2^n$ eigenstates with a non-zero amplitude and unitary transformations take the form of linear operators and consequently can be described as

$$U: {\vert i \rangle}\to\sum_{j=0}^{2^n-1} u_{ij} {\vert j \rangle} \quad\mathrm{with}\quad i,j\in\mathbf{Z}^{2^n},$$ (3.3)

a classical computer can simulate any unitary operator with arbitrary precision by encoding the complex amplitudes as fixed point binary numbers. In the general case, however, this will require an exponential overhead in time as well as in space complexity.

Due to the stochastic nature of quantum measurements, the emulating computer will also need a source of true randomness (like e.g. the probabilistic Turing machine).

Hybrid Architecture

So QPLs can be regarded as a meta-programming languages, as a program isn't intended to run on a quantum computer itself, but on a (probabilistic) classical computer which in turn controls a quantum computer. In the terms of classical computer science, you can describe this setting as a universal computer with a quantum oracle. Figure 3.1 illustrates this hybrid architecture.

Figure 3.1: The hybrid architecture of QCL

From the perspective of the user, quantum programs behave exactly like any other classical program, in the sense that it takes classical input such as startup parameters or interactive data, and produces classical output. The state of the controlling computer (i.e. program counter, variable values, but also the mapping of quantum registers) is also strictly classical and referred to as program state.

The actual program $\pi$, i.e. the sequence of quantum instructions consisting of elementary gates, measurement- and initialization-instructions is passed over a well defined interface to the quantum computer, while the returned output of is restricted to binary measurements values. The quantum computer doesn't require any control logic, it's computational state can therefor be fully described by the common quantum state $\Psi$ of its qubits, also referred to as machine state.