next up previous contents
Next: Quantum Programming Up: Introduction Previous: Models of Quantum Computation   Contents


Principles of Quantum Computing


To implement a computational model as a physical device, the computer must be able to adept different internal states, provide means to perform the necessary transformations on them and to extract the output information. The correlation between the physical and the logical state of the machine is arbitrary (as long it is consistent with the desired transformations) and requires interpretation.

In an ordinary RAM module, the common quantum state of thousands of electrons is interpreted as only one bit. The logical state is determined by the expectation value of its register contents (e.g. tension of a capacitor) The interpretation as (classical) bits is performed by comparing the measured value to a defined threshold, while the great number of particles guarantees that the uncertainty of the measurement is small enough ($O(1/\sqrt{n})$) to make errors practically impossible.

In a quantum computer, information is represented directly as the common quantum state of many subsystems. Each subsystem is described by a combination of two ``pure'' states interpreted as ${\vert \rangle}$ and ${\vert 1 \rangle}$ (quantum bit, qubit). This can e.g. be realised by the spin of a particle, the polarisation of a photon or by the ground state and an excited state of an ion.

Entanglement of States

Due to the one-to-one relation between logical and physical state in a quantum computer, a quantum register containing more than one qubit can not be described by simply listing the states of each qubit. In fact, the ``state of a qubit'' becomes a meaningless term1.5

Given an isolated system of two qubits, its state can be described by four complex amplitudes $ a {\vert,0 \rangle} + b {\vert 1,0 \rangle} +
c {\vert,1 \rangle} + d {\vert 1,1 \rangle} $. You can define the expectation value for the first qubit, which is $\sqrt{b b^*+d d^*}$ but there is no isolated state for the first qubit anymore like e.g. $(a+c) {\vert \rangle} + (b+d) {\vert 1 \rangle}$ since $\vert a\vert^2+\vert b\vert^2+\vert c\vert^2+\vert d\vert^2=1$ does not implicate that $\vert a+c\vert^2+\vert b+d\vert^2=1$.

Therefore, manipulations on a single qubit effect the complex amplitudes of the overall state and have a global character. To describe the combined state ${\vert\psi \rangle}$ of $n$ entangled qubits, $2^n$ complex numbers are necessary.

{\vert\psi \rangle}=\sum_{i=0}^{2^n-1}c_i\,{\vert i \rangle...
...um_{i=0}^{2^n-1}c^*_ic_i=1 \quad{\rm and}\quad c_i \in {\bf C}
\end{displaymath} (1.4)


To keep the computation coherent, quantum registers must be kept isolated, to avoid entanglement with the environment. The entropy of such a system has to remain constant since no heat dissipation is possible, therefore state changes have to be adiabatic, which requires all computations to be reversible.

Every reversible operation can be described by a unitary operator $U$ which matches the condition $U^{-1}=U^\dagger$. Compositions of unitary operators are also unitary since $(UV)^{-1}=
V^\dagger U^\dagger$. The restriction to unitary operators can also be directly derived for the operator of temporal propagation $U=e^{-iHt/\hbar}$. Since the Hamilton operator $H$ is an observable it has only real eigenvalues and $(^\dagger U)=U^{-1}=e^{iHt/\hbar}$.

A general unitary transformation in the two dimensional Hilbert space ${\bf C}^2$ can be defined as follows:

U(\theta,\delta,\sigma,\tau)={\left(\begin{array}{c c}
...uad{\rm with}\quad \theta, \delta, \sigma, \tau
\in {\bf R}
\end{displaymath} (1.5)

If this operator can be applied to arbitrary 2-dimensional subspaces of ${\cal H}$, then any unitary transformation can be constructed by composition. If only subspaces corresponding to a subset of qubits are allowed, which is the case for many proposed architectures, among them also the linear ion trap (Cirac-Zoller gate [2]), then an additional 4-dimensional 2-qubit operator is needed to obtain a mixing between separate qubits [6].

One possibility for this operator is the 2-qubit XOR which is defined as $\mathit{XOR}: {\vert x,y \rangle} \to {\vert x,x \oplus y \rangle}$ or in matrix notation:

\mathit{XOR}={\left(\begin{array}{c c c c}1&0&0&0\\ 0&1&0&0\\ 0&0&0&1\\ 0&0&1&0\end{array}\right)}
\end{displaymath} (1.6)

A quantum computer which is capable of performing general single qubit and $\mathit{XOR}$ operations can therefore perform any possible operation and is in this sense universal.


To set a quantum computer to the desired input state ${\vert\psi \rangle}$, it suffices to provide means to initially ``cool'' all qubits to ${\vert \rangle}$ and then apply a unitary transformation $U$ which matches the condition $U {\vert \rangle} = {\vert\psi \rangle}$. One might think of $U$ as a base transformation which trivially exists for any desired ${\vert\psi \rangle}$.

Measuring States

Measuring $n$ qubits reduces the dimensionality of ${\cal H}$ by a factor of $2^n$. The outcome of the measurement is biased by the probability amplitude for a certain bit configuration.

Consider two quantum registers with $n$ and $m$ qubits in the state

{\vert\psi \rangle}=\sum_{i=0}^{2^n-1} \sum_{j=0}^{2^m-1} c...
\quad{\rm with}\quad \sum_{i,j} c^*_{i,j}c_{i,j} = 1
\end{displaymath} (1.7)

The base-vectors ${\vert i,j \rangle}$ are interpreted as a pair of binary numbers with $i<2^n$ and $j<2^m$. The probability $p(I)$ to measure the number $I$ in the first register and the according post measurement state ${\vert\psi_I' \rangle}$ are given by
p(I)=\sum_{j=0}^{2^m-1} c^*_{I,j} c_{I,j}, \quad{\rm and}\q...
...1}{\sqrt{p(I)}} \sum_{j=0}^{2^m-1} c_{I,j} {\vert I,j \rangle}
\end{displaymath} (1.8)

The measurement of qubits is the only non unitary operation, a quantum computer must be able to perform during calculation.


... term1.5
The occasionally found notation ${\vert\psi \rangle}{\vert\phi \rangle}$ for multiple quantum registers instead of mere product states is somewhat misleading in this respect. In this paper, ${\vert\psi \rangle}{\vert\phi \rangle}$ always denotes a vector product and registers are labelled with subscripts like ${\vert\cdot \rangle}_\mathbf{s}$ if necessary.

next up previous contents
Next: Quantum Programming Up: Introduction Previous: Models of Quantum Computation   Contents

(c) Bernhard Ömer - -