Quantum Operations

Non-unitary Operations

As pointed out in 3.1.3, any quantum computation must be a composition of initializations, unitary operators and measurements. A typical probabilistic quantum algorithm usually runs an evaluation loop like this:

{
  reset;            // R: |Psi> -> |0>
  myoperator(q);    // U: |0> -> |Psi'>
  measure q,m;      // M: |Psi'> -> |m>
} until ok(m);      // picked the right m ?

The reset command resets the machine-state ${\vert\Psi \rangle}$ to ${\vert \rangle}$, which is also the initial state when qcl is started. The quantum heap and the binding of quantum variables are unaffected.

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

The measure command measures the quantum register $\mbox{\it expr}$ and assigns the measured bit-string to the int variable $\mbox{\it identifier}$. If no variable is given, the value is discarded.

The outcome of the measurement is determined by a random number generator, which -- by default -- is initialized with the current system time. For reproducible behavior of the simulation, a seed value can be given with the option -seed.

Since reset and measure operations are irreversible, they must not occur within operator definitions.

Subroutines

Hierarchy of Subroutines

Besides the classical subroutine type procedure and function, QCL provides two quantum routine types for general unitary operators (operator) and pseudo-classic operators (qufunct). QCL allows to invert operators and can perform scratch-space management for quantum functions, thus allowed side effects on the classical program state as well as on the quantum machine state have to be strictly specified.

Table 3.6: hierarchy of QCL Subroutines and allowed side-effects

routine type	program state	machine state	recursion
procedure	all	all	yes
operator	none	unitary	no
qufunct	none	pseudo-classic	no
functions	none	none	yes

The 4 QCL routine types form a call hierarchy, which means that a routine may invoke only subroutines of the same or a lower level (see table 3.6).

The mathematical semantic of QCL operators and functions requires that every call is reproducible. This means, that not only the program state must not be changed by these routines, but also that their execution may in no way depend on the global program state which includes global variables, options and the state of the internal random number generator.

External Routines

While QCL incorporates a classical programming language, to provides all the necessary means to change the program state, there is no hardwired set of elementary operators to manipulate the quantum machine state, since this would require assumptions about the architecture of the simulated quantum computer.

An elementary operator or qufunct can be incorporated by declaring it as extern.

$$\begin{eqnarray*} \mbox{\it def} &\leftarrow & \mbox{\tt extern} \mbox{... ... \mbox{\it identifier} \mbox{\it arg-list} \mbox{\tt ;} \end{eqnarray*}$$

External operators have no body since they are not executed within QCL, but merely serve as a hook for a binary function which implements the desired operation directly by using the numeric QC-library and is linked to the interpreter.

Section 3.4.4 and 3.4.7 describe the elementary unitary and pseudo classic gates which are provided by the integrated simulator of qcl.

General Operators

The routine type operator is used for general unitary operators. Conforming to the mathematical notion of an operator, a call with the same parameters has to result in exactly the same transformation, so no global variable references, random elements or dependencies on input are allowed.

Since the type operator is restricted to reversible transformations of the machine state, reset and measure commands are also forbidden.

Operator Arguments

Operators work on one or more quantum registers so a call of an $m$ qubit operator with a total quantum heap of $n$ qubits can result in $\frac{n!}{(n-m)!}$ different unitary transformations.

In QCL, this polymorphism is even further extended by the fact, that quantum registers can be of different sizes, so for every quantum parameter $\mathbf{s}$, the register size $\mathtt{\char93 }\mathbf{s}=\vert\mathbf{s}\vert$ is an implicit extra parameter of type int. An addition to that, operators can take an arbitrary number of explicit classical arguments.

If more than one argument register is given, their qubits may not overlap.

qcl> qureg q[4];
qcl> qureg p=q[2:3];
qcl> CNot(q[1\2],p);
! runtime error: quantum arguments overlapping

Inverse Operators

Operator calls can be inverted by the adjungation prefix `!'. The adjoint operator to a composition of unitary operators is^3.3

$${\left( \prod_{i=1}^{n}U_i\right)}^\dagger = \prod_{i=n}^1{U}^\dagger _i$$ (3.15)

Since the sequence of applied suboperators is specified using a procedural classical language which cannot be executed in reverse, the inversion of the composition, is is achieved by the delayed execution of operator calls.

When the adjungation flag is set, the operator body is executed and all calls of suboperators are pushed on a stack which is then processed in reverse order with inverted adjungation flags.

Local Registers

As opposed to pseudo-classic operators, it is in general impossible to uncompute a unitary operator in order to free a local register again without also destroying the intended result of the computation. This is a fundamental limitation of QC known as the non cloning theorem which results from the fact that a cloning operation i.e. a transformation with meets the condition

$$U: {\vert\psi \rangle}{\vert \rangle}\to{\vert\psi \rangle}{\vert\psi \rangle}$$ (3.16)

for an arbitrary^3.4 ${\vert\psi \rangle}$ cannot be unitary if ${\vert\psi \rangle}$ is a composed state because

$$U ( a{\vert,0 \rangle}+b{\vert 1,0 \rangle})= a^2{\vert,0 \rangle}+ab {\vert,1 \rangle}+ba {\vert 1,0 \rangle})+b^2{\vert 1,1 \rangle}$$ (3.17)

$$\neq a U {\vert,0 \rangle}+b U {\vert 1,0 \rangle}= a^2{\vert,0 \rangle}+b^2{\vert 1,1 \rangle}$$ (3.18)

$U$ can only be unitary if ${\vert\psi \rangle}$ is in a pure state, i.e. ${\vert\psi \rangle}={\vert i \rangle}$, in which case $U=\mathit{Fanout}$.

Due to the lack of a unitary copy operation for quantum states, Bennet-style scratch space management is impossible for general operators since it is based on cloning the result register.

Despite this limitation, it is possible in QCL to allocate temporary quantum registers but it is up to the programmer to properly uncompute them again. If the option -check is set, proper cleanup is verified by the simulator.

qcl> set check 1 
qcl> operator foo(qureg q) { qureg p[1]; CNot(p,q); }
qcl> qureg q[1];
qcl> Mix(q);
[1/4] 0.707107 |0000> + 0.707107 |0001>
qcl> foo(q);
! in operator foo: memory error: quantum heap is corrupted
[1/4] 0.707107 |0000> + 0.707107 |0011>

Local registers are useful if an operator contains some intermediary pseudo-classic operations which require scratch space.

Unitary Gates

Unitary Matrices

The most general form for specifying a unitary operator (or any other linear transformation) is by defining it's matrix elements: An $n$ qubit unitary operator $U$ describes a transformation $U:\mathbf{C}^{2^n}\to\mathbf{C}^{2^n}$ and therefore corresponds to a $2^n \times 2^n$ matrix in $\mathbf{C}$

$$U=\sum_{i,j=0}^{2^n} {\vert i \rangle} u_{ij} {\langle j\ve... ... u_{2^n-1,0} & \cdots & u_{2^n-1,2^n-1} \end{array}\right)$$ (3.19)

Since for a unitary transformation ${U}^\dagger U={(U^*)}^\mathrm{T}U=I(n)$, the Matrix $U$ unitary if and only if

$$\bigwedge_{i,j=0}^{2^n-1}\: \sum_{k=0}^{2^n-1} u^*_{ki} u_{kj}=\delta_{ij}$$ (3.20)

QCL provides external operators for general unitary $2\times 2$, $4\times 4$ and $8\times 8$ matrices, which the programmer can use to directly implement a custom set of 1, 2 and 3 qubit gates.

extern operator Matrix2x2(
  complex u00,complex u01,
  complex u10,complex u11,
qureg q);
extern operator Matrix4x4(...,qureg q);
extern operator Matrix8x8(...,qureg q);

Matrix operators are checked for unitarity before they are applied:

qcl> const i=(0,1);       
qcl> qureg q[1];
qcl> Matrix2x2(i*cos(pi/6),i*sin(pi/6),(0,0),(1,0),q);
! external error: matrix operator is not unitary

Qubit Rotation

The rotation of a single qubit is defined by the transformation matrix $U(\theta)$

$$U(\theta)= \left(\begin{array}{cc} \cos\frac{\theta}{2}... ...n\frac{\theta}{2} & \cos\frac{\theta}{2} \end{array}\right)$$ (3.21)

The factor $-\frac{1}{2}$ to $\theta$ is set in analogy to spin rotations, which can be shown to be of the form $\mathcal{D}=\mathrm{e}^{-\frac{\mathrm{i}}{2}\delta_j \sigma_j}$ and thus have a period of $4\pi$.

extern operator Rot(real theta,qureg q);

In contrast to most other external Operators, Rot is not generalized to work with arbitrary register sizes.

qcl> Rot(pi/2,q);
! external error: Only single qubits can be rotated

Hadamard Gate

The Hadamard Gate is a special case of a generalized qubit Rotation and defined by the transformation matrix $H$

$$H=\frac{1}{\sqrt 2} \left(\begin{array}{cc} 1 & 1 1 & -1 \end{array}\right)$$ (3.22)

For the case of $n$-qubit registers, $H$ can be generalized to

$$H:{\vert i \rangle}\to 2^{-\frac{n}{2}} \sum_{j\in\mathbf{B}^n} (-1)^{(i,j)} {\vert j \rangle}$$ (3.23)

The vectors $\mathcal{B'}=\{i\in\mathbf{B}^n \vert {\vert i' \rangle}=H {\vert i \rangle}\}$ form the Hadamard base or dual base or parity base to $\mathcal{B}=\{i\in\mathbf{B}^n \vert {\vert i \rangle}\}$.

The Hadamard Transformation is self adjoint (i.e. ${H}^\dagger =H$), which, for unitary operators, implies that $H^2=I$.

Since $\mathcal{B'}$ only contains uniform superpositions that just differ by the signs of the base-vectors, the external implementation of $H$ is called ${\tt Mix}$.

extern operator Mix(qureg q);

Conditional Phase Gate

The conditional phase gate is a pathological case of a conditional operator (see 2.2.2.6), for the zero-qubit phase operator $\mathrm{e}^{\mathrm{i}\phi}$.

$$V(\phi):{\vert\epsilon \rangle} \to \left\{ \begin{array... ...ert\epsilon \rangle} & \;\mbox{otherwise} \end{array}\right.$$ (3.24)

The conditional phase gate is used in the quantum Fourier transform (see 4.2.3).

extern operator CPhase(real phi,qureg q);

Pseudo-classic Operators

The routine type qufunct is used for pseudo-classic operators and quantum functions, so all transformations have to be of the form

$${\vert\Psi \rangle}=\sum_i c_i {\vert i \rangle} \to \sum_{i,j} c_i \delta_{j\pi_i} {\vert j \rangle}={\vert\Psi' \rangle}$$ (3.25)

with some permutation $\pi$. All $n$-qubit pseudo-classic operators $F$ therefore have the common eigenstate

$${\vert\Psi \rangle}=2^{-\frac{n}{2}} \sum_{i=0}^{2^n-1}{\ve... ...ongleftrightarrow F {\vert\Psi \rangle}={\vert\Psi \rangle}$$ (3.26)

Bijective Functions

The most straightforward application for pseudo-classic operators is the direct implementation of bijective functions (see 2.2.2.4)

qufunct inc(qureg x) {
  int i;
  for i = #x-1 to 1 {
    CNot(x[i],x[0:i-1]);
  }
  Not(x[0]);
}

The operator inc shifts the base-vectors of it's argument. In analogy to boson states, where the increment of the eigenstate corresponds to the generation of a particle, inc is a creation operator.^3.5

qcl> qureg q[4];
qcl> inc(q);
[4/4] 1 |0001>
qcl> inc(q);
[4/4] 1 |0010>
qcl> inc(q);
[4/4] 1 |0011>
qcl> inc(q);
[4/4] 1 |0100>

Conditional Operators

When it comes to more complicated arithmetic operations, it is often required to apply a transformation to a register $\mathbf{a}$ in dependence on the content of another register $\mathbf{e}$.

If all qubits of $\mathbf{e}$ are required to be set, for the transformation to take place, the operator is a conditional operator with the invariant (quconst) enable register $\mathbf{e}$ (see 2.2.2.6).

A simple example for a conditional operator is the Toffoli gate

$$T:{\vert x,y,z \rangle}\to{\vert x\oplus (y\wedge z),y,z \rangle}$$ (3.27)

or it's generalization, the controlled not gate (see 3.4.7.4). A conditional version of the above increment operator is also easy to implement:

qufunct cinc(qureg x,quconst e) {
  int i;
  for i = #x-1 to 1 step -1 {
    CNot(x[i],x[0:i-1] & e);
  }
  CNot(x[0],e);
}

Now, only base-vectors of the form ${\vert i \rangle}{\vert 11\ldots \rangle}_\mathbf{s}$ are incremented:

qcl> qureg q[4]; qureg e[2]; Mix(e);
[6/6] 0.5 |000000> + 0.5 |100000> + 0.5 |010000> + 0.5 |110000>
qcl> cinc(q,e);
[6/6] 0.5 |000000> + 0.5 |100000> + 0.5 |010000> + 0.5 |110001>
qcl> cinc(q,e);
[6/6] 0.5 |000000> + 0.5 |100000> + 0.5 |010000> + 0.5 |110010>
qcl> cinc(q,e);
[6/6] 0.5 |000000> + 0.5 |100000> + 0.5 |010000> + 0.5 |110011>

Quantum Functions

As defined in 2.2.2.5, a quantum function $F$ is a pseudo-classic operator with the characteristic

$$F:{\vert x \rangle}_\mathbf{x}{\vert \rangle}_\mathbf{y}\to... ...\mathbf{y} \quad\mathrm{with}\quad f:{\bf B}^n \to {\bf B}^m$$ (3.28)

If we require the argument register $\mathbf{x}$ to be invariant to $F$ by declaring $\mathbf{x}$ as quconst, this leaves us with $\left((2^m-1)!\right)^{2^n}$ possible pseudo-classic implementations of $F$ for any given $f$. To reflect the fact that $F {\vert x,y\neq 0 \rangle}$ is undefined, the target register has to be of type quvoid. (see 3.3.2.3).

Since, according to the above definition, quantum functions are merely ordinary pseudo-classic operators, whose specification is restricted to certain types of input states, they also use the same QCL routine type qufunct.

The following example calculates the parity of $\mathbf{x}$ and stores it to $\mathbf{y}$:

qufunct parity(quconst x,quvoid y) {
  int i;
  for i = 0 to #x-1 {
    CNot(y,x[i]);
  }
}

qcl> qureg x[2]; qureg y[1]; Mix(x);
[3/3] 0.5 |000> + 0.5 |010> + 0.5 |001> + 0.5 |011>
qcl> parity(x,y);
[3/3] 0.5 |000> + 0.5 |110> + 0.5 |101> + 0.5 |011>

Scratch parameters

We can extend the notion of quantum functions, by also allowing an explicit scratch register $\mathbf{s}$ (see 3.3.2.4) as an optional parameter to $F$, so we end up with an operator $F(\mathbf{x},\mathbf{y},\mathbf{s})$ with the characteristic

$$F:{\vert x \rangle}_\mathbf{x}{\vert \rangle}_\mathbf{y}{\v... ...bf{x}{\vert f(x) \rangle}_\mathbf{y}{\vert \rangle}_\mathbf{s}$$ (3.29)

Using the parity and the cinc operator form the above examples, we can implement an ``add parity'' function $f(x)=x+\mathrm{parity}(x)$ by providing a scratch qubit:

qufunct addparity(quconst x,quvoid y,quscratch s) {
  parity(x,s);      // write parity to scratch
  x -> y;           // Fanout x to y
  cinc(y,s);        // increment y if parity is odd
  parity(x,s);      // clear scratch
}

qcl2> qureg x[2]; qureg y[2]; qureg s[1]; Mix(x);
[5/8] 0.5 |00000> + 0.5 |00010> + 0.5 |00001> + 0.5 |00011>
qcl2> addparity(x,y,s);
[5/8] 0.5 |00000> + 0.5 |01110> + 0.5 |01001> + 0.5 |01111>

Instead of providing a explicit scratch parameter, we can, of course, also use a local register of type qureg, which is functionally equivalent:

qufunct addparity2(quconst x,quvoid y) {
  qureg s[1];
  parity(x,s);
  x -> y;
  cinc(y,s);
  parity(x,s);
}

qcl2> qureg x[2]; qureg y[2]; Mix(x);
[4/8] 0.5 |00000> + 0.5 |00010> + 0.5 |00001> + 0.5 |00011>
qcl2> addparity2(x,y);
[4/8] 0.5 |00000> + 0.5 |01110> + 0.5 |01001> + 0.5 |01111>

Explicit scratch parameters are useful to save memory, if a quantum function $F$ is to be used by another operator $U$, which still has empty scratch registers at the moment, the suboperator is called, which would e.g. be the case if $U$ is of the form

$$U(\mathbf{x},\mathbf{y},\mathbf{s},\ldots)= \left(\prod_{i... ...f{x},\mathbf{y},\mathbf{s}) U_1(\mathbf{x},\mathbf{y},\ldots)$$ (3.30)

Since both, explicit scratch parameters of type quscratch and local registers of type qureg, have to be uncomputed manually, they are especially useful for quantum functions $U:{\vert x,0,0 \rangle}\to {\vert x,f(s(x),x),0 \rangle}$ of the form

$$U(\mathbf{x},\mathbf{y},\mathbf{s})=S(\mathbf{x},\mathbf{s}... ...f{x},\mathbf{s},\mathbf{y}){S}^\dagger (\mathbf{x},\mathbf{s})$$ (3.31)

if $S$ is invariant to $\mathbf{x}$ and $F$ is invariant to $\mathbf{x}$ and $\mathbf{s}$, because the uncomputation of $\mathbf{s}$ doesn't require an additional register to temporarily save $\mathbf{y}$ (see 3.3.1.5) as would be the case, if a managed local scratch register of type quscratch would be used instead (see below).

Pseudo-classic Gates

Base Permutation

The most general form for specifying an $n$ qubit pseudo-classic operator $U$, is by explicitly defining the underlying permutation $\pi$ of base-vectors:

$$U_{\mathit{pc.}}=\sum_{i=0}^{2^n-1} {\vert\pi_i \rangle}{\langle i\vert} = {\langle \pi_0,\pi_1 \ldots \pi_{2^n-1} \rangle}$$ (3.32)

QCL provides external operators for vector permutations for $\vert\pi\vert=2$, 4, 8, 16, 32 and 64 which the programmer can use to directly implement a custom set of $1$ to $6$ qubit pseudo-classical operators:

extern qufunct Perm2(int p0 ,int p1 ,qureg q);
extern qufunct Perm4(int p0 ,int p1 ,int p2 ,int p3 ,qureg q);
extern qufunct Perm8(...,qureg q);
extern qufunct Perm16(...,qureg q);
extern qufunct Perm32(...,qureg q);
extern qufunct Perm64(...,qureg q);

Base permutations are checked for unitarity before they are applied (i.e. it is verified that the given integer sequence is in fact a permutation)

qcl> qureg q[3];
qcl> Perm8(0,0,1,2,3,4,5,6,q);
! external error: no permutation

Fanout

The $\mathit{Fanout}$ operation is a quantum function (see 2.2.2.5) and stands for a class of transformations with the characteristic $\mathit{Fanout}: {\vert x,0 \rangle}\to{\vert x,x \rangle}$

The external fanout operator of QCL is defined as

$$\mathit{Fanout}: {\vert x,y \rangle} \to {\vert x,x \oplus y \rangle},$$ (3.33)

however, it is considered bad programming style to rely on this particular implementation.

extern qufunct Fanout(quconst a,quvoid b);

QCL also provides the special syntax a->b and a<-b as abbreviations for Fanout(a,b) and !Fanout(a,b).

Swap

The $\mathit{Swap}$ operator exchanges the qubits of two equal sized registers ( $\mathit{Swap}:{\vert x,y \rangle}\to{\vert y,x \rangle}$). A one to one qubit $\mathit{Swap}$ operator has the transformation matrix

$$\mathit{Swap}= \left(\begin{array}{cccc} 1 & 0 & 0 & 0 ... ... 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{array}\right)$$ (3.34)

extern qufunct Swap(qureg a,qureg b);

As with the fanout operator, a<->b is syntactic sugar for Swap(a,b).

Not and Controlled Not

The not operator $C$ inverts a qubit. Its transformation matrix is

$$C= \left(\begin{array}{cc} 0 & 1 1 & 0 \end{array}\right)$$ (3.35)

The controlled-not operator $C_{[[\mathbf{e}]]}$ is the conditional operator (see 2.2.2.6) to $C$ with the enable register $\mathbf{e}$:

$$C_{[[\mathbf{e}]]}:{\vert b \rangle}{\vert\epsilon \rangle}... ...\rangle}_\mathbf{e} & \;\mbox{otherwise} \end{array}\right.$$ (3.36)

extern qufunct Not(qureg q);
extern qufunct CNot(qureg q,quconst c);

The QCL versions of Not and CNot also work on target registers, in which case $C_{[[\mathbf{e}]]}$ is applied to all qubits:

qcl> qureg q[4]; qureg p[4];
qcl> Not(q);
[8/8] 1 |00001111>
qcl> CNot(p,q);
[8/8] 1 |11111111>

Footnotes

... is^3.3

To avoid ambiguities with non-commutative matrix products, we use the convention $\prod_{i=1}^n f_i=f_nf_{n-1}\ldots f_1$

... arbitrary^3.4

For any particular ${\vert\psi \rangle}$ an infinite number of unitary ``cloning'' operators trivially exists, as e.g. $U_\psi=\sum_{i,j,k} {\vert i,j\oplus k \rangle}{\langle k\vert\psi \rangle}{\langle i,j\vert}$

... operator.^3.5

In fact, this is not quite correct, since other than bosons, an $n$ qubit register is limited to $2^n$ states, so $\mathtt{inc} {\vert 2^n-1 \rangle}={\vert \rangle}$ whereas ${a}^\dagger {\vert 2^n-1 \rangle}={\vert 2^n \rangle}$