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.
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left | 1 \right \rangle} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left | -1 \right \rangle} states. There is no classical analogue of it.

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left | 1 \right \rangle \to \frac{1}{\sqrt{2}}(\left | 1 \right \rangle + \left | -1 \right \rangle)}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left | -1 \right \rangle \to \frac{1}{\sqrt{2}}(\left | 1 \right \rangle - \left | -1 \right \rangle)}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H^2=I} i.e the Hadamard gate is self-inverse.

Oracle

An oracle which performs the function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)} .

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left | x,y \right \rangle \to \left | x, yf(x) \right \rangle}

Deutsch algorithm

Let us create an oracle which performs the following function: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f: \{-1,1\} \mapsto \{-1,1\}}
There are four possibilities for this function:

1. identity: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \mapsto x}
2. not: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \mapsto -x}
3. output -1: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \mapsto -1}
4. output 1: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \mapsto 1}

Computational task: To determine if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(1)=f(-1)} .
This is equivalent to trying to determine Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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.

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left | \psi(0) \right \rangle = \left | 1,1 \right \rangle}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left | \psi(1) \right \rangle = \left | 1,-1\right \rangle}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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) }
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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) Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(1)=f(-1)} and 2) Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(1)=-f(-1)}
1. Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(1)=f(-1)=f}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(1)=-f(-1)=f}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{1}{\sqrt{2}}(\left | 1 \right \rangle \pm \left | -1 \right \rangle)} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{1}{\sqrt{2}}(\left | 1 \right \rangle \pm \left | -1 \right \rangle)} and thus determine whether Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(1)=f(-1)} or not.

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H\frac{1}{\sqrt{2}}(\left | 1 \right \rangle + \left | -1 \right \rangle)= \left | 1 \right \rangle}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H\frac{1}{\sqrt{2}}(\left | 1 \right \rangle - \left | -1 \right \rangle)= \left | -1 \right \rangle}

Thus Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle F(a)=x^a \pmod n} , i.e. find Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r} such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle F(a)=F(a+r)\,}

Once Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r} has been found by use of quantum parallelism, the second part of the algorithm may be performed:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^0 \pmod n=1}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Rightarrow x^r mod\,n=1, x^{2r} \pmod n=1} etc.

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Rightarrow x^r \equiv 1 \pmod n}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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