Quantum computation: Difference between revisions
imported>Charles Blackham (gates beginning) |
imported>Charles Blackham (deutsch alg begun) |
||
Line 15: | Line 15: | ||
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. | 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').<br/> | 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').<br/> | ||
===Dynamics of quantum gates in Schrödinger picture=== | |||
NB In the Schrödinger picture the state vector evolves in the following manner:<br/> | |||
<math>\left | \psi(t+1) \right \rangle = U \left | \psi(t) \right \rangle</math><br/> | |||
where <math>U</math> is the characteristic unitary matrix of the gate. | |||
====NOT==== | |||
<math>\left | a \right \rangle \to \left | -a \right \rangle, \qquad a=\pm 1</math><br/> | |||
So if <math> \left | a \right \rangle = \left | \psi(0) \right \rangle </math> then <math> \left | -a \right \rangle = \left | \psi(1) \right \rangle</math> | |||
====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.<br/> | |||
<math>\left | x \right \rangle \left | y \right \rangle \equiv \left | x,y \right \rangle \to \left | x,xy \right \rangle</math> | |||
====Hadamard gate, H==== | |||
The Hadamard gate, normally denoted as H, creates an equally weighted superposition of the <math>\left | 1 \right \rangle</math> and <math>\left | -1 \right \rangle</math> states. There is no classical analogue of it.<br/><br/> | |||
<math>\left | 1 \right \rangle \to \frac{1}{\sqrt{2}}(\left | 1 \right \rangle + \left | -1 \right \rangle)</math><br/> | |||
<math>\left | -1 \right \rangle \to \frac{1}{\sqrt{2}}(\left | 1 \right \rangle - \left | -1 \right \rangle)</math><br/> | |||
<math>H^2=I</math> i.e the Hadamard gate is self-inverse. | |||
====Oracle==== | |||
An oracle which performs the function <math>f(x)</math> has the following dynamics in the Schrödinger picture. The value of y is normally set to one so that the output is <math>x</math> and <math>f(x)</math>.<br/> | |||
<math>\left | x,y \right \rangle \to \left | x, yf(x) \right \rangle</math> | |||
===Deutsch algorithm=== | ===Deutsch algorithm=== | ||
Let us create an oracle which performs the following function: <math>f: \{-1,1\} \mapsto \{-1,1\}</math> | Let us create an oracle which performs the following function: <math>f: \{-1,1\} \mapsto \{-1,1\}</math><br/> | ||
There are four possiblities for this function:<br/> | There are four possiblities for this function:<br/> | ||
# identity: <math>x \mapsto x</math> | # identity: <math>x \mapsto x</math> | ||
Line 28: | Line 52: | ||
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.<br/> | 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.<br/> | ||
(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].<br/> | (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]].<br/> | ||
'''DIAGRAM OF DEUTSCH ALGORITHM'''<br/> | |||
<math>\left | \psi(0) \right \rangle = \left | 1,1 \right \rangle</math><br/> | |||
<math>\left | \psi(1) \right \rangle = \left | 1,-1\right \rangle</math><br/> | |||
<math>\left | 1 \right \rangle \ | <math> | ||
<math>\left | | \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) | |||
</math><br/> | |||
<math>\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)</math><br/> | |||
===Grover's algorithm=== | ===Grover's algorithm=== |
Revision as of 10:57, 9 June 2007
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.[1]
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.
Interference & a simple computation
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').
Dynamics of quantum gates in Schrödinger picture
NB In the Schrödinger picture the state vector evolves in the following manner:
where is the characteristic unitary matrix of the gate.
NOT
So if then
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.
Hadamard gate, H
The Hadamard gate, normally denoted as H, creates an equally weighted superposition of the and states. There is no classical analogue of it.
i.e the Hadamard gate is self-inverse.
Oracle
An oracle which performs the function has the following dynamics in the Schrödinger picture. The value of y is normally set to one so that the output is and .
Deutsch algorithm
Let us create an oracle which performs the following function:
There are four possiblities for this function:
- identity:
- not:
- output -1:
- output 1:
Computational task: To determine if .
This is equivalant to trying to determine 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.
DIAGRAM OF DEUTSCH ALGORITHM
Grover's algorithm
Shor's algorithm
References
Based on a talk given by Charles Blackham to 6P at Winchester College, UK on 7/3/07
- Lectures on Quantum Computation by David Deutsch
- Cambridge Centre for Quantum Computation
- ↑ R.P. Feynman International Journal of Theoretical Physics 21(6/7) 1982