Components of a Quantum Computer

A classical, as well as a quantum computer, essentially consists of 3 parts: a memory, which holds the current machine state, a processor, which performs elementary operations on the machine state, and some sort of input/output which allows to set the initial state and extract the final state of the computation.

Quantum Memory

The Qubit

The quantum analogy to the classical bit is the quantum bit or qubit. Just as a classical bit is represented by a system which can adopt one of two distinct states ``0'' and ``1'' we can define a quantum bit as follows:

Definition 1 (Qubit)   A qubit or quantum bit is a quantum system whose state can be fully described by a superposition of two orthonormal eigenstates labeled ${\vert \rangle}$ and ${\vert 1 \rangle}$.

The general state ${\vert\psi \rangle}\in\mathcal{H}$ of a qubit is given by

$${\vert\psi \rangle}=\alpha {\vert \rangle}+\beta {\vert 1 \r... ...\quad\mathrm{with}\quad \vert\alpha\vert^2+\vert\beta\vert^2=1$$ (2.2)

The value of a qubit is the observable $\mathcal{N}$ with the Hermitian operator $N {\vert i \rangle}=i {\vert i \rangle}$ over the Hilbert space $\mathcal{H}=\mathbf{C}^2$, or in matrix representation

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

The expectation value of $N$ is given by

$${\langle N \rangle}={\langle \psi\vert}N{\vert\psi \rangle}... ...ay}{c} \alpha \beta \end{array}\right) =\vert\beta\vert^2$$ (2.4)

thus, ${\langle N \rangle}$ gives the probability to find the system in state ${\vert 1 \rangle}$ if a measurement is performed on the qubit.

Combination of Qubits

If we combine 2 qubits, the general state of the resulting system is

$${\vert\Psi \rangle}=\alpha {\vert0 \rangle}+\beta {\vert 10 ... ...rt^2+\vert\beta\vert^2+\vert\gamma\vert^2+\vert\delta\vert^2=1$$ (2.5)

While we still can define distinct observables $\mathcal{N}^{(1)}$ and $\mathcal{N}^{(2)}$ for the value of each qubit with the operators $N^{(1)} {\vert ij \rangle}=i {\vert ij \rangle}$ and $N^{(2)} {\vert ij \rangle}=j {\vert ij \rangle}$, their expectation values

$${\langle N^{(1)} \rangle}=\vert\beta\vert^2+\vert\delta\vert... ...\langle N^{(2)} \rangle}=\vert\gamma\vert^2+\vert\delta\vert^2$$ (2.6)

don't allow us to reconstruct the actual probability distribution among the eigenvalues. To illustrate this, consider the states

$${\vert\Psi_A \rangle}=\frac{1}{\sqrt{2}}({\vert0 \rangle}+{... ...angle}=\frac{1}{\sqrt{2}}({\vert 10 \rangle}+{\vert1 \rangle})$$ (2.7)

$$\quad\mathrm{and}\quad {\vert\Psi_C \rangle}=\frac{1}{2}({\... ...angle}+{\vert 10 \rangle}+{\vert1 \rangle}+{\vert 11 \rangle})$$

All of these states have the expectation values ${\langle N^{(1)} \rangle}={\langle N^{(2)} \rangle}=1/2$, i.e. if we measure a single qubit, we get either ${\vert \rangle}$ or ${\vert 1 \rangle}$ with equal probability; we get, however, totally different post-measurement states.

If we measure ${\vert 1 \rangle}$ in the first qubit, the resulting post-measurement states are

$${\vert\Psi_A' \rangle}={\vert 11 \rangle}, \quad {\vert\Psi... ...gle}=\frac{1}{\sqrt{2}}({\vert 10 \rangle}+{\vert 11 \rangle})$$ (2.8)

and the expectation values for the second qubit are now given by

$${\langle N^{(2)}_A \rangle}=1, \quad {\langle N^{(2)}_B \r... ...uad\mathrm{and}\quad {\langle N^{(2)}_C \rangle}=\frac{1}{2}$$ (2.9)

Machine State

While the state of a classical computer can be given as the distinct states of all bits in memory and processor registers, the ``state of a qubit'' is a meaningless term, if the machine state is the combined state of more than one system.^2.3

Definition 2 (Machine State)   The machine state $\Psi$ of an $n$-qubit quantum computer is the current state of a combined system of $n$ identical qubit subsystems.

Generally, the machine state $\Psi$ of an $n$-qubit quantum computer is given by

$${\vert\Psi \rangle}=\sum_{(d_0\ldots d_{n-1})\in \mathbf{B}... ...\mathrm{with}\quad \sum \vert c_{d_0\ldots d_{n-1}}\vert^2=1$$ (2.10)

The combined Hilbert space $\mathcal{H}$ is thus a composition of $n$ 1-qubit-Hilbert spaces $\mathcal{H}_i=\mathbf{C}^2$, i.e.

$$\mathcal{H}=\mathcal{H}_1\times\mathcal{H}_2\times\ldots\times\mathcal{H}_n= \mathbf{C}^{2^n}$$ (2.11)

If we interpret the eigenvectors ${\vert d_0\ldots d_{n-1} \rangle}$ as binary digits, with $d_0$ as least significant bit, we can write this as

$${\vert\Psi \rangle}=\sum_{i=0}^{2^n-1}c_i {\vert i \rangle} ... ...{n-1}d_{n-1} \rangle}\equiv {\vert d_0\ldots d_{n-1} \rangle}$$ (2.12)

The operator $N_i$ for value $\mathcal{N}_i$ of the $i$-th qubit is given by

$$N_i {\vert d_0\ldots d_{n-1} \rangle}=d_i {\vert d_0\ldots d_{n-1} \rangle}$$ (2.13)

and has the expectation value

$${\langle N_i \rangle}=\sum_{(d_0\ldots d_{n-1})\in \mathbf{B}^n} d_i \vert c_{d_0\ldots d_{n-1}}\vert^2$$ (2.14)

Subsystems

As we have shown above, the memory of an $n$-qubit quantum computer is a combined system of $n$ identical qubit-subsystems. Since the partition into subsystems is merely methodical, we can consider the first $m$ qubits ($m<n$) as a single subsystem and write $\Psi$ as

$${\vert\Psi \rangle}=\sum_{i=0}^{2^m-1}\sum_{j=0}^{2^{n-m}-1... ...{with}\quad {\vert\Psi \rangle}\in\mathcal{H}=\mathbf{C}^{2^n}$$ (2.15)

As the base vectors ${\vert i,j \rangle}$ are product states ${\vert i,j \rangle}={\vert i \rangle}{\vert j \rangle}$, the Hilbert space $\mathcal{H}$ can be written as a combination of

$$\mathcal{H}=\mathcal{H}'\times\mathcal{H}''\quad\mathrm{with... ...{2^m}\quad\mathrm{and}\quad \mathcal{H}''=\mathbf{C}^{2^{n-m}}$$ (2.16)

Let $U'$ and $U''$ be unitary operators over $\mathcal{H}'$ and $\mathcal{H}''$, then the commutator $[U',U'']=0$ as

$$[U',U''] {\vert\Psi \rangle}= \sum_{i,j} c_{ij} \left[U'{... ... \rangle})-U''(U'{\vert i \rangle}){\vert j \rangle}\right]=0$$ (2.17)

This means that unitary transformations applied to distinct subsets of qubits are independent.

A unitary transformation $U'$ over the first $m$ qubits also doesn't affect a measurement of the remaining qubits since the probability $p_j''$ to measure $j$ in the remaining $n-m$ qubits, i.e. to get a post-measurement state of the form ${\vert\Psi' \rangle}={\vert\psi_j \rangle}{\vert j \rangle}$, is invariant to $U'$, as

$$p_j''=\sum_i {c}^*_{ij}c_{ij} {\langle i\vert i \rangle}{\l... ...ert}{U'}^\dagger U'{\vert i \rangle}{\langle j\vert j \rangle}$$ (2.18)

Quantum Registers

The above notion of $m$-qubit subsystems can easily be extended to arbitrary sequences of qubits.

Definition 3 (Quantum Register)   An $m$ qubit quantum Register $\mathbf{s}$ is a sequence of mutually different zero-based qubit positions ${\langle s_0, s_1 \ldots s_{m-1} \rangle}$ of some machine state ${\vert\Psi \rangle}\in\mathbf{C}^{2^m}$ with $n\geq m$.

Reordering Operators

Let $\mathbf{s}$ be an $m$ qubit register of the $n$ qubit state ${\vert\Psi \rangle}$. Using an arbitrary permutation $\pi$ over $n$ elements with $\pi_i=s_i$ for $i<m$, we can construct a unitary reordering operator $\Pi_{\mathbf{s}}$ by permutating the qubits.

$$\Pi_{\mathbf{s}} {\vert d_0,d_1\ldots d_{n-1} \rangle}= {\vert d_{\pi_0},d_{\pi_1}\ldots d_{\pi_{n-1}} \rangle}$$ (2.19)

Note that there exist $(n-m)!$ permutations $\Pi_{\mathbf{s}}^{(k)}$ which fit into the above definition, since $\pi_i$ is only defined for $i<m$.

Unitary operators correspond to base transformations (see 1.3.2.6), so we can write ${\vert\tilde{\Psi} \rangle}=\Pi_{\mathbf{s}} {\vert\Psi \rangle}$ as

$${\vert\tilde{\Psi} \rangle}= \sum_{i=0}^{2^m-1} \sum_{j=0}... ...},\tilde{\jmath} \rangle}=\Pi_{\mathbf{s}} {\vert i,j \rangle}$$ (2.20)

As above, the transformed Hilbert space $\tilde{\mathcal{H}}$ can be written as a combination

$$\tilde{\mathcal{H}}=\tilde{\mathcal{H}}'\times\tilde{\mathca... ...ad\mathrm{and}\quad \tilde{\mathcal{H}}''=\mathbf{C}^{2^{n-m}}$$ (2.21)

Unitary Operators

Let $\tilde{U}'$ be a $m$-qubit unitary operator over $\tilde{\mathcal{H}}'$ and $\tilde{U}=\tilde{U}'\times I(n-m)$ with $I(k)$ being the $k$-qubit identity operator.

$$\tilde{U} {\vert\tilde{\Psi} \rangle}= \sum_{i,j} \tilde{c}_{ij} (\tilde{U}'{\vert i \rangle}){\vert j \rangle}$$ (2.22)

For each permutation $\Pi_{\mathbf{s}}^{(k)}$, we can define a back-transformed operator

$$U^{(k)}={\Pi_{\mathbf{s}}^{(k)}}^\dagger \tilde{U} \Pi_{\m... ...\vert i',j' \rangle} u^{(k)}_{i'j'ij} {\langle i,j\vert}$$ (2.23)

with the matrix elements

$$u^{(k)}_{i'j'ij}= {\langle \tilde{\imath}'^{(k)}\vert}\ti... ...h}^{(k)} \rangle}= \Pi_{\mathbf{s}}^{(k)} {\vert i,j \rangle}$$ (2.24)

Since the transformed base vectors $\tilde{\imath}^{(k)}$ are identical for all permutations $\Pi_{\mathbf{s}}^{(k)}$ and ${\langle \tilde{\jmath}'^{(k)}\vert\tilde{\jmath}^{(k)} \rangle}=\delta_{j'j}$, it follows that the back-transformation $\tilde{U}'\times I\to U$ is independent from the chosen permutation $\Pi_{\mathbf{s}}^{(k)}$.

Register Observables

Just as with single qubits, we can define an observable $\mathcal{S}$ for a given $m$-qubit register $\mathbf{s}$ with the operator

$$S=(N_{\pi_0},N_{\pi_1},\ldots N_{\pi_{m-1}}) \quad\mathrm{... ...\ldots d_{n-1} \rangle}=d_i {\vert d_0\ldots d_{n-1} \rangle}$$ (2.25)

or, if we interpret the binary vectors as integers,

$$S=\sum_{i,j} {\Pi_{\mathbf{s}}}^\dagger {\vert i,j \rang... ...\sum_{i,j} {\vert i,j \rangle}\tilde{\imath}{\langle i,j\vert}$$ (2.26)

Processing Units

Unitary Operators

In a classical $n$-bit computer, every computational step can be described by a transition function $I: \mathbf{B}^n\to\mathbf{B}^n$ which takes the current state $S$ of all bits as input and returns the appropriate post-instruction state $S'$.

As we have shown in 1.3.2.6, the temporal evolution of a quantum system can be described by unitary operators. The general form of a $n$-qubit unitary operator $U$ over the Hilbert space $\mathcal{H}=\mathbf{C}^{2^n}$ is

$$U=\sum_{i=0}^{2^n-1} \sum_{j=0}^{2^n-1} {\vert i \rangle}... ...rm{with}\quad \sum_{k=0}^{2^n-1} {u}^*_{ki} u_{kj}=\delta_{ij}$$ (2.27)

If we compare boolean functions to unitary operators from a strictly functional point of view we can identify three major differences between classical and quantum operations:

• Reversibility: Since unitary operators, by definition, match the condition ${U}^\dagger U=I$, for every transformation $U$ there exists the inverse transformation ${U}^\dagger$. As a consequence, quantum computation is restricted to reversible functions.^2.4

• Superposition: An eigenstate ${\vert\Psi \rangle}={\vert k \rangle}$ can be transformed into a superposition of eigenstates.
  

  $${\vert\Psi' \rangle}=U {\vert k \rangle}=\sum_{k'} U_{k'k} {\vert k \rangle}$$ (2.28)

  
  
  The mathematical explanation of this feature lies in the fact that the requirement ${\langle i\vert}{U}^\dagger U{\vert j \rangle}=\delta_{ij}$ is weaker than the pseudo-classical (see 2.2.2.4) condition
  

  $${\langle i\vert}{U}^\dagger {\vert\pi_i \rangle}{\langle \p... ...j \rangle}{\langle \pi_j\vert}U{\vert j \rangle}= \delta_{ij}$$ (2.29)

  
  
  which requires transformed eigenstates not only to be orthonormal, but also to be of the form $U {\vert k \rangle}={\vert\pi_k \rangle}$ with some appropriate permutation (i.e. reversible function) $\pi$ over $\mathbf{Z}_{2^n}$.
• Parallelism: If the machine state ${\vert\Psi \rangle}$ already is a superposition of several eigenstates, then a transformation $U$ is applied to all eigenstates simultaneously.
  

  $$U \sum_i c_i {\vert i \rangle} = \sum_i c_i U {\vert i \rangle}$$ (2.30)

  
  
  This feature of quantum computing is called quantum parallelism and is a consequence of the linearity of unitary transformations.

Register Operators

The basic instructions of a classical computer usually operate only on a very small number of bits and are typically independent from the total amount of available memory. Therefor it is more useful to describe those instructions not as boolean functions $F$ over the whole state space $\mathbf{B}^n$ (in the case of an $n$ bit machine), but as parameterized functions $f_{\mathbf{x}}$ over $\mathbf{B}^m$, where the vector $\mathbf{x}\in \mathbf{Z}^n$ only holds the bit-positions of the relevant arguments. Consequently we refer to the resulting instruction $F$ as ``applying f to the bits $x_0, x_1 \ldots x_{n-1}$''.

While it is clear what we mean by e.g. ``swapping the bits 3 and 5'' on a classical computer, we cannot blindly adopt this concept to quantum computing, because unitary operators operate on states and a single qubit doesn't have a state.^2.5

In 2.2.1.5 we have defined a quantum register as a sequence of (mutually different) qubit-positions $\mathbf{s}={\langle s_0,s_1\ldots s_{m-1} \rangle}$, which is the quantum analogon to the above argument vector $\mathbf{v}$, and a class of $(n-m)!$ reordering operators $\Pi^{(k)}_{\mathbf{s}}$ which meet the condition

$$\Pi^{(k)}_{\mathbf{s}} {\vert d_0,d_1\ldots d_{n-1} \rangl... ...dots d_{s_{m-1}} \rangle} {\vert\tilde{\jmath}^{(k)} \rangle}$$ (2.31)

Definition 4 (Register Operator)   The register operator $U(\mathbf{s})$ for an $m$-qubit unitary operator $U:\mathbf{C}^{2^m}\to\mathbf{C}^{2^m}$ and a $m$-qubit quantum register $\mathbf{s}$ on an $n$-qubit quantum computer is the $n$-qubit operator

$$U(\mathbf{s})={\Pi}^\dagger _{\mathbf{s}} (U \times I(n-m)) \Pi_s$$ (2.32)

with an arbitrary reordering operator $\Pi_{\mathbf{s}}$

So $U(\mathbf{s}) {\vert\Psi \rangle}$ is what we actually mean, by ``application of operator $U$ to quantum register $\mathbf{s}$''. Since there are $\frac{n!}{(n-m)!}$ possible $m$-qubit registers on an $n$-qubit machine, a given $m$-qubit operator $U$ can describe $\frac{n!}{(n-m)!}$ different transformations $U(\mathbf{s})$.

In analogy to boolean networks, unitary operators which can be applied to arbitrary sets of qubits are also referred to as quantum gates.

Universal Quantum Gates

A well known result from classical boolean logic, is that any possible function $f: \mathbf{B}^n \to \mathbf{B}^m$ can be constructed as a composition from a small universal set of operators if we can ``wire'' the inputs and outputs to arbitrary bits in a feed-forward network. Examples for universal sets of logical gates are $\{\vee,\neg\}$, $\{\to,\neg\}$ or $\{ \bar{\wedge} \}$.

As mentioned in 1.3.2.6, unitary operations can be described as abstract ``rotations'' in the Hilbert space. A complex rotation of a single qubit has the general form

$$U2(\omega,\alpha,\beta,\phi)= \mathrm{e}^{-\mathrm{i}\phi}... ...thrm{e}^{-\mathrm{i}\alpha} \cos\omega \end{array}\right)$$ (2.33)

If this operator could be applied to arbitrary 2-dimensional subspaces $\mathcal{H}'=\mathbf{C}^2$ of $\mathcal{H}=\mathcal{H}'\times\mathcal{H}''$, then any unitary transformation could be constructed by composition in at most ${\dim\mathcal{H}\choose 2}$ steps [14], very much like a general rotation in $\mathbf{R}^n$ can be decomposed into ${n \choose 2}$ simple rotations in the coordinate planes.

In our definition of quantum gates, however, we are restricted to subspaces corresponding to quantum registers (see 2.2.1.5), so in the case of an $n$-qubit quantum computer ( $\dim\mathcal{H}=2^n$), this leaves us with merely $n$ possible 1-qubit subspaces $\mathcal{H}'$ and the corresponding sets of register operators $U2^{(i)}(\omega,\alpha,\beta,\phi)$. Since $[U2^{(i)},U2^{(j)}]=0$, any composition $U$ of $U2$ gates, would result in a transformation of the form

$$U {\vert d_0,d_1,\ldots d_{n-1} \rangle}= (U_1 {\vert d_0 ... ...2 {\vert d_2 \rangle})\ldots (U_{n-1} {\vert d_{n-1} \rangle})$$ (2.34)

So just as the $\mathrm{NOT}$ gate itself is not universal for boolean logic, to construct a universal set of quantum gates, we require an additional 2-qubit operation, to create entangled multi-qubit states.

One possibility for a nontrivial 2-qubit operator is 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)$$ (2.35)

Deutsch [6] has shown that the set $\{ U2(\omega,\alpha,\beta,\phi),\mathit{XOR}\}$ is in fact universal for unitary transformation. Furthermore, since $\{ U2(\omega',\alpha',\beta',\phi')^n \}$ is dense in $\{ U2(\omega,\alpha,\beta,\phi) \}$ for almost any^2.6set of parameters, $\{ U2, \mathit{XOR}\}$ is universal for most $U2$ in the sense that any unitary transformation $U$ can be approximated to arbitrary precision.

Deutsch also proposed a 3-qubit gate $D(\theta)$ which is universal, while only requiring one parameter:

$$D(\theta):{\vert i,j,k \rangle} \to \left\{ \begin{array}... ...vert i,j,k \rangle} & \;\mbox{otherwise} \end{array}\right.$$ (2.36)

Pseudo-classic Operators

The general form of a unitary operator $U$ over $n$ qubits is

$$U=\sum_{i=0}^{2^n-1} \sum_{j=0}^{2^n-1} {\vert i \rangle}... ...rm{with}\quad \sum_{k=0}^{2^n-1} {u}^*_{ki} u_{kj}=\delta_{ij}$$ (2.37)

If the matrix elements $u_{ij}$ are of the form $u_{ij}=\delta_{i\pi_j}$ with some permutation $\pi$, then their effect on pure states (base-vectors) can be described in terms of classical reversible boolean logic.

Definition 5 (Pseudo-classic Operator)   A $n$-qubit pseudo-classic operator is a unitary operator of the form $U:{\vert i \rangle}\to{\vert\pi_i \rangle}$ with some permutation $\pi$ over $\mathbf{Z}^{2^n}$.

For $\theta=\pi/2$ the universal Deutsch gate $D(\theta)$ (2.36) degenerates into the pseudo-classic operator

$$T=D(\frac{\pi}{2})={\vert i,j,(i\wedge j)\oplus k \rangle}{\langle i,j,k\vert} \quad\mathrm{with}\quad i,j,k\in\mathbf{B}$$ (2.38)

$T$ is the 3-bit controlled-not or Toffoli gate, which is a universal gate for reversible boolean logic.

Let $f: {\bf Z}_{2^n} \to {\bf Z}_{2^n}$ be a bijective function, then the corresponding pseudo-classic operator $F$ is given as

$$F=\sum_{i=0}^{2^n-1} {\vert f(i) \rangle}{\langle i\vert} ... ...agger =\sum_{i=0}^{2^n-1} {\vert i \rangle}{\langle f(i)\vert}$$ (2.39)

Quantum Functions

One obvious problem of quantum computing is its restriction to reversible computations. Consider a simple arithmetical operation like integer division by 2 ( $\mathit{DIV2}' {\vert i \rangle} = {\vert i/2 \rangle}$ for even $i$ and ${\vert(i-1)/2 \rangle}$ for odd $i$). Clearly, this operation is non-reversible since $\mathit{DIV2}' {\vert \rangle}=\mathit{DIV2}' {\vert 1 \rangle}$, so no corresponding pseudo-classic operator exists.

However, if we use a second register with the initial value ${\vert \rangle}$, then we can define an operator $\mathit{DIV2}$ which matches the condition $\mathit{DIV2}{\vert x,0 \rangle} = {\vert x,x/2 \rangle}$ or ${\vert x,(x-1)/2 \rangle}$ respectively. The behavior of $\mathit{DIV2}{\vert x,y \neq 0 \rangle}$ is undefined and can be set arbitrarily as long as $\mathit{DIV2}$ remains pseudo-classic.^2.7.

Definition 6 (Quantum Functions)   For any function $f: {\bf B}^n \to {\bf B}^m$ (or equivalently $f: {\bf Z}_{2^n} \to {\bf Z}_{2^m}$) there exists a class of pseudo-classic operators $F: \mathbf{C}^{2^{n+m}} \to \mathbf{C}^{2^{n+m}}$ working on an $n$-qubits input and an $m$-qubits output register with $F {\vert x,0 \rangle} = {\vert x,f(x) \rangle}$. Operators of that kind are referred to as quantum functions.

For any boolean function $f: {\bf B}^n \to {\bf B}^m$ there exist $(2^{n+m}-2^n)!$ different quantum functions $F$.

Conditional Operators

Classical programs allow the conditional execution of code in dependence on the content of a boolean variable (conditional branching).

A unitary operator, on the other hand, is static and has no internal flow-control. Nevertheless, we can conditionally apply an $n$ qubit operator $U$ to a quantum register by using an enable qubit and define an $n+1$ qubit operator $U'$

$$U'= \left(\begin{array}{cc} I(n) & 0 0 & U \end{array}\right)$$ (2.40)

So $U$ is only applied to base-vectors where the enable bit is set. This can be easily extended to enable-registers of arbitrary length.

Definition 7 (Conditional Operator)   A conditional operator $U_{[[\mathbf{e}]]}$ with the enable register $\mathbf{e}$ is a unitary operator of the form

$$U_{[[\mathbf{e}]]}:{\vert i,\epsilon \rangle}={\vert i \ran... ...\rangle}_\mathbf{e} & \;\mbox{otherwise} \end{array}\right.$$ (2.41)

Conditional operators a frequently used in arithmetic quantum functions and other pseudo-classic operators.

If the architecture allows the efficient implementation of the controlled-not gate $C:{\vert x,y_1,y_2\ldots \rangle}\to {\vert(x\oplus\bigwedge_i y_i),y_1,y_2\ldots \rangle}$, then conditional pseudo-classic operators can be realized by simply adding the enable string to the control register of all controlled-not operations.

Input and Output

Quantum Computing and Information Processing

In 2.1.3 we have shown that the interpretation of computing as a physical process, rather than the abstract manipulation of symbols, leads to an extended notion of computability. We have also identified the the concept of unitary transformations as an adequate paradigm for ``physical computability''.

Unitary transformations describe the transition between machine states and thereby the temporal evolution of a quantum system. The very notion of a (quantum) computer as a ``computing machine'' requires, however, that the evolution of the physical system corresponds to a processing of information.

Classical information theory requires that any ``reasonable'' information can be expressed as a series of answers to yes-no questions, i.e. a string of bits. But unlike classical symbolic computation, where every single step of a computation can be mapped onto a bit-string, physical computation requires such a labeling only for the initial and the final machine state (see 2.1.3.2), the labels of which make up the input and output of the computation.

This requirement is in full accordance with the Copenhagen interpretation of quantum physics, which states that the setup and the outcome of any experiment has to be described in classical terms.

Labeling of States

As the machine state $\Psi$ is not directly accessible, any physically realizable labeling has to correspond to an observable $\mathcal{O}$. As has been shown in 1.3.2.2, in quantum physics, an observable $\mathcal{O}$ is expressed by a Hermitian operator $O$.

A natural choice for $\mathcal{O}$ on an $n$-qubit quantum computer would be the classical values $\mathcal{N}=(\mathcal{N}_0,\mathcal{N}_1,\ldots \mathcal{N}_{n-1})$ of the singe qubits with the Hermitian operators

$$N=(N_0,N_1, \ldots N_{n_1})= N_0+2 N_1+\ldots+2^{n-1} N_{n-1}$$ (2.42)

$$N_i {\vert d_0\ldots d_{n-1} \rangle}=d_i {\vert d_0\ldots d_{n-1} \rangle}$$

As $\mathcal{N}$ is only defined for eigenstates of $N$ (see 1.3.2.3), the labeling $m:\mathcal{H}\to\mathbf{B}^n$ is only defined for states $\Psi\in\mathcal{H}$ of the form

$${\vert\Psi \rangle}=\mathrm{e}^{\mathrm{i}\phi}{\vert d_0\ldots d_{n-1} \rangle}$$ (2.43)

Initialization

To set a quantum computer to a desired initial state ${\vert\Psi_0 \rangle}={\vert s_0 \rangle}$ corresponding to the boolean input string $s_0$, it suffices to provide means to initially ``cool'' all qubits to ${\vert \rangle}$ and then apply any unitary transformation $U$ which matches the condition $U {\vert \rangle} = {\vert s_0 \rangle}$.

Definition 8   The reset operator $\mathit{R}$ is a constant operator over $\mathcal{H}$ and defined as $\mathit{R}{\vert\Psi \rangle}={\vert \rangle}$.

Measurement

As has been described in 1.3.2.3, it is impossible to observe a quantum state $\psi$ without, at the same time, forcing the system to adopt a state $\psi'$ which is an eigenstate of the Hermitian operator $O$ corresponding to the observed quantity $\mathcal{O}$. The transition probability is thereby given as

$$p_{\psi\to\psi'}=\left\vert{\langle \psi'\vert\psi \rangle}\right\vert^2$$ (2.44)

If we measure the binary values $\mathcal{N}$ of an $n$-qubit quantum computer in the state

$${\vert\Psi \rangle}=\sum_{i=0}^{2^n-1} c_i {\vert i \rangle}$$ (2.45)

the probabilities to measure $i$ and the assorted post measurement states are consequently

$$p_i=\vert c_i\vert^2 \quad\mathrm{and}\quad {\vert\psi_i' \rangle}={\vert i \rangle}$$ (2.46)

Partial Measurement

Measurements don't have to cover the whole machine state, but can also be restricted to single qubits or quantum registers.

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... ...gle} \quad\mathrm{with}\quad \sum_{i,j} c^*_{i,j}c_{i,j} = 1$$ (2.47)

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\mathrm{and}... ...}{\sqrt{p_i}} \sum_{j=0}^{2^m-1} c_{i,j} {\vert i,j \rangle}$$ (2.48)

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

Footnotes

...^2.3

Unless the machine state happens to be a product state, that is (see 1.3.3.2).

... functions.^2.4

A classical analogon would be the class of reversible boolean functions

...^2.5

unless it's the only qubit in the quantum computer at which point the whole question of addressed instructions becomes moot, anyway.

... any^2.6

basically, it is just required that the quotients between $\omega',\alpha',\beta',\phi'$ and $\pi$ are irrational.

...^2.7

In this special case, just one additional qubit to hold the lowest bit of the argument would suffice to extend $\mathit{DIV2}'$ to a unitary operator.