Next: Components of a Quantum Up: Quantum Computers Previous: Quantum Computers   Contents

Subsections

# Introduction

## The Church-Turing Thesis

The basic idea of modern computing science is the view of computation as a mechanical, rather than a purely mental process. A method, or procedure for achieving some desired result is called effective or mechanical just in case [17]

1. is set out in terms of a finite number of exact instructions (each instruction being expressed by means of a finite number of symbols);
2. will, if carried out without error, always produce the desired result in a finite number of steps;
3. can (in practice or in principle) be carried out by a human being unaided by any machinery save paper and pencil;
4. demands no insight or ingenuity on the part of the human being carrying it out.

Alan Turing and Alonzo Church both formalized the above definition by introducing the concept of computability by Turing machine and the mathematically equivalent concept of recursive functions with the following conclusions:

#### Turing's thesis

LCMs [logical computing machines i.e. Turing machines] can do anything that could be described as "rule of thumb" or "purely mechanical". [19]

#### Church's thesis

A function of positive integers is effectively calculable only if recursive. [18]

#### .

As the above statements are equivalent, they are commonly referred to as the Church-Turing Thesis which defines the scope of classical computing science.

## Computing Machines

Despite its operationalistic approach, the above computability concept doesn't have much in common with the continuous nature of physics, so in order to build a computing machine , we have to introduce a labeling function which maps the analog physical states (e.g. the tension of a capacitor) to digital computational states (e.g. the value of a bit) The digital states have to be strings over some finite alphabet .

Since the above definition of computability requires a finite number of both, symbols and instructions, the labeling function only needs to apply on discrete intermediate machine states so the temporal evolution of the machine state is mapped onto a sequence of computational states where each transition corresponds to one function from a enumerable set of (simple) instructions.2.1The sequence is called program.

The states and are called the input- and the output-state. The machine thus implements the function

 (2.1)

## Computation as a Physical Process

The above definition of a computing machine poses severe restrictions on the interpretation of physical states. If we consider computation as a physical process, rather than a mechanical'' manipulation of symbols as defined in 2.1.1, we can drop all restrictions in the above definition which don't have a physical equivalent.

### Indeterminism

As we have showed in 1.3.2.3, the measurement of an observable with the according operator is only deterministic, if a system is in an eigenstate of . To account for the stochastic nature of quantum measurement, we have to replace the labeling function by a probabilistic operator which randomly chooses a string according to some probability distribution with .

### Temporal Evolution

Since it is not possible to non-destructively measure a quantum system and we are only interested in the result of a computation, anyway, it is not necessary that a labeling is defined for the intermediate steps to of a computation i.e. it is not required to watch'' the temporal evolution of the system, as long as a labeling for the input- and output-state and is given.

While the transitions still have to correspond to (simple) operations from a enumerable instruction set of quantum transformations, the operators , don't have to directly correspond to functions in .2.2

In 1.3.2.6 we have shown that the temporal evolution of a quantum system is mathematically described by unitary operators, so a quantum program is a composition of elementary unitary transformations.

#### Footnotes

... instructions.2.1
For hypothetical machines with unlimited memory, the instruction set might also be infinitely which is not in accordance with Turing's original definition of computability.

The Turing Machine avoids this problem by extending the computational states with an integer and using this head position'' as an additional parameter to the generated instructions. As (which can get arbitrary large) would be stored'' in the physical position of the head and not in the state of the head itself, it can still be claimed that the TM operates by finite means''.

Even with our simpler model, we could avoid an infinitely instruction set, e.g. by interpreting a state with as the pair , and define the instructions as .

As we are discussing physical computers, which usually don't have unlimited memory, we can ignore this problem, and use the simpler and more general computer definition given above.

....2.2
Because of the reversibility of unitary operators, a direct correspondence would only be possible for bijective functions

Next: Components of a Quantum Up: Quantum Computers Previous: Quantum Computers   Contents

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