Quantum computation

Throughout this article The Many Worlds Interpretation(MWI) of quantum mechanics is used.

Differences with classical computation

In classical computation there is the concept of a discrete bit, taking only one of two values. However , the world which classical physics describes is that of continua. Thus this is obviously not an ideal way of attempting to describe or simulate the world in which we live. Feynman was the first to consider the idea of a quantum computer being necessary to simulate the quantum mechanical world in which we live.

Quantum computers & information theory

The quantum mechanical analogue of the classical bit is the qubit. A qubit is an actual physical system, all of whose observables are Boolean.

Quantum Algorithms

An algorithm is a hardware-independant recipe for performing a particular computation. A program is a way of preparing a specific computer to do such a task. Algorithms for quantum computers offer a wider range of computational tasks which may be solved by the use of interference. Some of the new possibilities which are opened up may prove to have drastic consequences for the future: e.g. Shor's algorithm relevance to cryptography.

Oracles

An oracle is a black box which it is impossible to look inside and performs a particular function f on the input qubits in a time which is independant of the particular input. It is not possible. They are used to simplify the analysis of algorithms as the specific nature of how a task is performed is irrelevant due to the criterion of hardware-independance. The oracle must of course be reversible as the laws of QM do not make a distinction between forwards and backwards time (i.e. time does not have 'an arrow').

Example

Let us create an oracle which performs the following function: $f:\{-1,1\}\mapsto \{-1,1\}$ !!!!!!DIAGRAM!!!!!!
There are four possiblities for this function:

1. identity: $x\mapsto x$
2. not: $x\mapsto -x$
3. output -1: $x\mapsto -1$
4. output 1: $x\mapsto 1$

Deutsch algorithm

Computational task: To determine if $f(1)=f(-1)$.
This is equivalant to trying to determine $f(1)f(-1)$ without looking inside the oracle above. Classically this may be done by consulting the oracle twice. [diagram of classical situation] However, using quantum computation the oracle need only be consulted twice.

References

Based on a talk given by Charles Blackham to 6P at Winchester College, UK on 7/3/07

1. Lectures on Quantum Computation by David Deutsch
2. Cambridge Centre for Quantum Computation