Next: Models of Quantum Computation Up: Quantum Computers Previous: Introduction   Contents

Subsections

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 and .

The general state of a qubit is given by

 (2.2)

The value of a qubit is the observable with the Hermitian operator over the Hilbert space , or in matrix representation
 (2.3)

The expectation value of is given by
 (2.4)

thus, gives the probability to find the system in state if a measurement is performed on the qubit.

Combination of Qubits

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

 (2.5)

While we still can define distinct observables and for the value of each qubit with the operators and , their expectation values
 (2.6)

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

All of these states have the expectation values , i.e. if we measure a single qubit, we get either or with equal probability; we get, however, totally different post-measurement states.

If we measure in the first qubit, the resulting post-measurement states are

 (2.8)

and the expectation values for the second qubit are now given by
 (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 of an -qubit quantum computer is the current state of a combined system of identical qubit subsystems.

Generally, the machine state of an -qubit quantum computer is given by

 (2.10)

The combined Hilbert space is thus a composition of 1-qubit-Hilbert spaces , i.e.
 (2.11)

If we interpret the eigenvectors as binary digits, with as least significant bit, we can write this as
 (2.12)

The operator for value of the -th qubit is given by
 (2.13)

and has the expectation value
 (2.14)

Subsystems

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

 (2.15)

As the base vectors are product states , the Hilbert space can be written as a combination of
 (2.16)

Let and be unitary operators over and , then the commutator as
 (2.17)

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

A unitary transformation over the first qubits also doesn't affect a measurement of the remaining qubits since the probability to measure in the remaining qubits, i.e. to get a post-measurement state of the form , is invariant to , as

 (2.18)

Quantum Registers

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

Definition 3 (Quantum Register)   An qubit quantum Register is a sequence of mutually different zero-based qubit positions of some machine state with .

Reordering Operators

Let be an qubit register of the qubit state . Using an arbitrary permutation over elements with for , we can construct a unitary reordering operator by permutating the qubits.

 (2.19)

Note that there exist permutations which fit into the above definition, since is only defined for .

Unitary operators correspond to base transformations (see 1.3.2.6), so we can write as

 (2.20)

As above, the transformed Hilbert space can be written as a combination
 (2.21)

Unitary Operators

Let be a -qubit unitary operator over and with being the -qubit identity operator.

 (2.22)

For each permutation , we can define a back-transformed operator
 (2.23)

with the matrix elements
 (2.24)

Since the transformed base vectors are identical for all permutations and , it follows that the back-transformation is independent from the chosen permutation .

Register Observables

Just as with single qubits, we can define an observable for a given -qubit register with the operator

 (2.25)

or, if we interpret the binary vectors as integers,
 (2.26)

Processing Units

Unitary Operators

In a classical -bit computer, every computational step can be described by a transition function which takes the current state of all bits as input and returns the appropriate post-instruction state .

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 -qubit unitary operator over the Hilbert space is

 (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 , for every transformation there exists the inverse transformation . As a consequence, quantum computation is restricted to reversible functions.2.4

• Superposition: An eigenstate can be transformed into a superposition of eigenstates.
 (2.28)

The mathematical explanation of this feature lies in the fact that the requirement is weaker than the pseudo-classical (see 2.2.2.4) condition
 (2.29)

which requires transformed eigenstates not only to be orthonormal, but also to be of the form with some appropriate permutation (i.e. reversible function) over .
• Parallelism: If the machine state already is a superposition of several eigenstates, then a transformation is applied to all eigenstates simultaneously.
 (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 over the whole state space (in the case of an bit machine), but as parameterized functions over , where the vector only holds the bit-positions of the relevant arguments. Consequently we refer to the resulting instruction as applying f to the bits ''.

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 , which is the quantum analogon to the above argument vector , and a class of reordering operators which meet the condition

 (2.31)

Definition 4 (Register Operator)   The register operator for an -qubit unitary operator and a -qubit quantum register on an -qubit quantum computer is the -qubit operator
 (2.32)

with an arbitrary reordering operator

So is what we actually mean, by application of operator to quantum register ''. Since there are possible -qubit registers on an -qubit machine, a given -qubit operator can describe different transformations .

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 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 , or .

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

 (2.33)

If this operator could be applied to arbitrary 2-dimensional subspaces of , then any unitary transformation could be constructed by composition in at most steps [14], very much like a general rotation in can be decomposed into 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 -qubit quantum computer ( ), this leaves us with merely possible 1-qubit subspaces and the corresponding sets of register operators . Since , any composition of gates, would result in a transformation of the form

 (2.34)

So just as the 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 or in matrix notation:

 (2.35)

Deutsch [6] has shown that the set is in fact universal for unitary transformation. Furthermore, since is dense in for almost any2.6set of parameters, is universal for most in the sense that any unitary transformation can be approximated to arbitrary precision.

Deutsch also proposed a 3-qubit gate which is universal, while only requiring one parameter:

 (2.36)

Pseudo-classic Operators

The general form of a unitary operator over qubits is

 (2.37)

If the matrix elements are of the form with some permutation , then their effect on pure states (base-vectors) can be described in terms of classical reversible boolean logic.

Definition 5 (Pseudo-classic Operator)   A -qubit pseudo-classic operator is a unitary operator of the form with some permutation over .

For the universal Deutsch gate (2.36) degenerates into the pseudo-classic operator

 (2.38)

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

Let be a bijective function, then the corresponding pseudo-classic operator is given as

 (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 ( for even and for odd ). Clearly, this operation is non-reversible since , so no corresponding pseudo-classic operator exists.

However, if we use a second register with the initial value , then we can define an operator which matches the condition or respectively. The behavior of is undefined and can be set arbitrarily as long as remains pseudo-classic.2.7.

Definition 6 (Quantum Functions)   For any function (or equivalently ) there exists a class of pseudo-classic operators working on an -qubits input and an -qubits output register with . Operators of that kind are referred to as quantum functions.

For any boolean function there exist different quantum functions .

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 qubit operator to a quantum register by using an enable qubit and define an qubit operator

 (2.40)

So 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 with the enable register is a unitary operator of the form
 (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 , 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 is not directly accessible, any physically realizable labeling has to correspond to an observable . As has been shown in 1.3.2.2, in quantum physics, an observable is expressed by a Hermitian operator .

A natural choice for on an -qubit quantum computer would be the classical values of the singe qubits with the Hermitian operators

 (2.42)

As is only defined for eigenstates of (see 1.3.2.3), the labeling is only defined for states of the form
 (2.43)

Initialization

To set a quantum computer to a desired initial state corresponding to the boolean input string , it suffices to provide means to initially cool'' all qubits to and then apply any unitary transformation which matches the condition .

Definition 8   The reset operator is a constant operator over and defined as .

Measurement

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

 (2.44)

If we measure the binary values of an -qubit quantum computer in the state

 (2.45)

the probabilities to measure and the assorted post measurement states are consequently
 (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 and qubits in the state

 (2.47)

The probability to measure the number in the first register and the according post measurement state are given by
 (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.
... any2.6
basically, it is just required that the quotients between and are irrational.
...2.7
In this special case, just one additional qubit to hold the lowest bit of the argument would suffice to extend to a unitary operator.

Next: Models of Quantum Computation Up: Quantum Computers Previous: Introduction   Contents

(c) Bernhard Ömer - oemer@tph.tuwien.ac.at - http://tph.tuwien.ac.at/~oemer/