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 and 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-independent 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 independent 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-independence. 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').

Dynamics of quantum gates in Schrödinger picture

NB In the Schrödinger picture the state vector evolves in the following manner:
$\left|\psi (t+1)\right\rangle =U\left|\psi (t)\right\rangle$
where $U$ is the characteristic unitary matrix of the gate.

NOT

$\left|a\right\rangle \to \left|-a\right\rangle ,\qquad a=\pm 1$
So if $\left|a\right\rangle =\left|\psi (0)\right\rangle$ then $\left|-a\right\rangle =\left|\psi (1)\right\rangle$

Controlled Not, CNOT

This i a two input gate where whether the NOT operation is performed on the second is dependant (i.e. controlled) by the value of the first input bit which is unchanged.
$\left|x\right\rangle \left|y\right\rangle \equiv \left|x,y\right\rangle \to \left|x,xy\right\rangle$

Hadamard gate, H

The Hadamard gate, normally denoted as H, creates an equally weighted superposition of the $\left|1\right\rangle$ and $\left|-1\right\rangle$ states. There is no classical analogue of it.

$\left|1\right\rangle \to {\frac {1}{\sqrt {2}}}(\left|1\right\rangle +\left|-1\right\rangle )$
$\left|-1\right\rangle \to {\frac {1}{\sqrt {2}}}(\left|1\right\rangle -\left|-1\right\rangle )$
$H^{2}=I$ i.e the Hadamard gate is self-inverse.

Oracle

An oracle which performs the function $f(x)$ has the following dynamics in the Schrödinger picture. The value of y is normally set to one so that the output is $x$ and $f(x)$.

$\left|x,y\right\rangle \to \left|x,yf(x)\right\rangle$

Deutsch algorithm

Let us create an oracle which performs the following function: $f:\{-1,1\}\mapsto \{-1,1\}$
There are four possibilities 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$

Computational task: To determine if $f(1)=f(-1)$.
This is equivalent 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 once.

(N.B. For the analysis of algorithms, the Schrödinger picture is often preferable and thus shall be used here. It is of course still possible to use the Heisenberg picture.

$\left|\psi (0)\right\rangle =\left|1,1\right\rangle$
$\left|\psi (1)\right\rangle =\left|1,-1\right\rangle$
$\left|\psi (2)\right\rangle ={\frac {1}{2}}(\left|1\right\rangle +\left|-1\right\rangle )(\left|1\right\rangle -\left|-1\right\rangle )={\frac {1}{2}}(\left|1,1\right\rangle +\left|-1,1\right\rangle -\left|1,-1\right\rangle -\left|-1,-1\right\rangle )$
$\left|\psi (3)\right\rangle ={\frac {1}{2}}(\left|1,f(1)\right\rangle +\left|-1,f(1)\right\rangle -\left|1,-f(-1)\right\rangle -\left|-1,-f(-1)\right\rangle )$

Now we must examine the two possibilities 1) $f(1)=f(-1)$ and 2) $f(1)=-f(-1)$
1. Let $f(1)=f(-1)=f$
$\Rightarrow \left|\psi (3)\right\rangle ={\frac {1}{2}}(\left|1,f\right\rangle +\left|-1,f\right\rangle -\left|1,-f\right\rangle -\left|-1,-f\right\rangle )={\frac {1}{2}}(\left|1\right\rangle +\left|-1\right\rangle )(\left|f\right\rangle -\left|-f\right\rangle )$
2. Let $f(1)=-f(-1)=f$
$\Rightarrow \left|\psi (3)\right\rangle ={\frac {1}{2}}(\left|1\right\rangle -\left|-1\right\rangle )(\left|f\right\rangle -\left|-f\right\rangle )$

In each of these cases the state vector when t=3 is a superposition of two pure states: ${\frac {1}{\sqrt {2}}}(\left|1\right\rangle \pm \left|-1\right\rangle )$ and ${\frac {1}{\sqrt {2}}}(\left|f\right\rangle \pm \left|-f\right\rangle )$. The purpose of the final Hadamard gate is to differentiate between the states ${\frac {1}{\sqrt {2}}}(\left|1\right\rangle \pm \left|-1\right\rangle )$ and thus determine whether $f(1)=f(-1)$ or not.

$H{\frac {1}{\sqrt {2}}}(\left|1\right\rangle +\left|-1\right\rangle )=\left|1\right\rangle$
$H{\frac {1}{\sqrt {2}}}(\left|1\right\rangle -\left|-1\right\rangle )=\left|-1\right\rangle$

Thus $\left|\psi (4)\right\rangle ={\frac {1}{\sqrt {2}}}\left|f(1)f(-1)\right\rangle (\left|f\right\rangle -\left|-f\right\rangle$

Shor's algorithm

Shor's algorithm is used to find the factors of a number. It is particularly important because of the use in cryptography of multiplying together two large prime numbers. Factoring this number into its prime factors allows the cracking of the code.

The algorithm itself has two parts: one quantum and one classical. The latter can be done in $O(x^{n})$ time. The use of a quantum algorithm makes this true for the former part as well.

Let us wish to factor a number n. The first part of the algorithm wishes to find the period, r, of the function:

$\scriptstyle F(a)=x^{a}{\pmod {n}}$, i.e. find $r$ such that $\scriptstyle F(a)=F(a+r)\,$

Once $r$ has been found by use of quantum parallelism, the second part of the algorithm may be performed:

$x^{0}{\pmod {n}}=1$

$\Rightarrow x^{r}mod\,n=1,x^{2r}{\pmod {n}}=1$ etc.

$\Rightarrow x^{r}\equiv 1{\pmod {n}}$

$\Rightarrow (x^{\frac {r}{2}})^{2}=x^{r}\equiv 1{\pmod {n}}$

$\Rightarrow (x^{\frac {r}{2}})^{2}-1\equiv 0{\pmod {n}}$

$\Rightarrow (x^{\frac {r}{2}}-1)(x^{\frac {r}{2}}+1)\equiv 0{\pmod {n}}$ if $r$ is even.

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