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.
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:
The general state
of a qubit is given by
If we combine 2 qubits, the general state of the resulting system
If we measure in the first qubit, the resulting
post-measurement states are
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
Generally, the machine state of an -qubit quantum
computer is given by
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
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
, is invariant to
The above notion of -qubit subsystems can easily be extended to arbitrary sequences of qubits.
Let be an qubit register of the qubit state
Using an arbitrary permutation over elements with
for , we can construct a unitary
by permutating the qubits.
Unitary operators correspond to base transformations (see
18.104.22.168), so we can write
Let be a -qubit unitary operator over
with being the -qubit identity operator.
Just as with single qubits, we can define an observable
for a given -qubit register with the operator
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 22.214.171.124, the temporal evolution of a
quantum system can be described by unitary operators.
The general form of a -qubit unitary operator over the
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:
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 126.96.36.199 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
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.
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 188.8.131.52, unitary operations can
be described as abstract ``rotations'' in the Hilbert space.
A complex rotation of a single qubit has the general form
In our definition of quantum gates, however, we are restricted
to subspaces corresponding to quantum registers (see 184.108.40.206),
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
, any composition of gates,
would result in a transformation of the form
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
or in matrix
Deutsch  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:
The general form of a unitary operator over qubits is
For the universal Deutsch gate
(2.36) degenerates into the pseudo-classic operator
be a bijective function,
then the corresponding pseudo-classic operator is given as
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.
For any boolean function there exist different quantum functions .
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
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.
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 220.127.116.11), 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.
As the machine state is not directly accessible, any physically realizable labeling has to correspond to an observable . As has been shown in 18.104.22.168, 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
singe qubits with the Hermitian operators
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 .
As has been described in 22.214.171.124, 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
If we measure the binary values of an -qubit
quantum computer in the state
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