Glossary

This is a glossary of terms and variables used throughout this paper.

$\lambda$: In the context of Shor's algorithm in integer such that $m = \frac{\lambda q}{r}$.

$a$: An argument to the function $\mathcal{F}(a) = x^{a} \bmod n$. It may be a single integer, or it may denote a superposition of states.

Binary: The base two number system. For more information see Appendix A.

Bit: A thing which can store one item of information, either a 1 or a 0.

Church-Turing Thesis, the hypothesis that:

Every 'function which would naturally be regarded as computable' can be computed by the universal Turing machine.

Classical computer: A computer whose internal workings behave in manner consistent with classical physics. Data registers in a classical computer can not exist in a superposition of states.

Classical physics: The model that was used to describe physical phenomenon before the advent of quantum physics. The predictions of classical physics with regard to the behavior of fundamental particles are incorrect.

Collapse: How the state vector of a quantum mechanical system changes when that system is observed or measured. Since the system can only be measured to be in one of its base states, the state vector will collapse from some superposition of base states into the measured state only.

Complex number: A number of the form $a + i*b$, where $a$ and $b$ are real numbers and $i$ is defined to be the square root of negative one.

Complex vector space: A vector space in which the coordinates of a vector are complex numbers.

Complexity class: A grouping of algorithms based on how their memory usage and number of operations scale with the size of the input.

Coprime: Integers $a$ and $b$ are coprime if their greatest common denominator is one.

Discrete Fourier Transform: In Shor's algorithm this numerical method is used to calculate the multiple of the inverse period, which enables Shor's algorithm to find factors of a number $n$.

Exponential: A function which grows as: $\mathcal{F}(x) = a^{x}$, where $a$ is some constant.

Exponential time: This is an attribute of an algorithm which means the number of operations required to compute the answer grows exponentially with the size of the input.

$\gcd$: This is an abbreviation for the mathematical function which calculates the greatest common denominator of two integers. The greatest common denominator of two integers $a$ and $b$ is the largest integer $c$ such that $a / c$ and $b / c$ are integers.

Grover's Search Algorithm: A algorithm designed by L. K. Grover of Bell Labs which finds a element in an unsorted database of size $n$ in $O(\sqrt{n})$ operations on a quantum computer.

Hilbert Space: A complex linear vector space. The complete state of a $n$ state quantum mechanical system can be represented by a vector in an $n$ dimensional Hilbert Space.

$i$: The square root of $-1$.

Linear vector space: A vector space in which a vector which is added to or multiplied by another vector results in a vector which lies within the vector space.

Memory register: A array of memory bits, a register of size $n$ may store one of $2^{n}$ values.

Mutually perpendicular: In the context of vector spaces mutually perpendicular vectors are vectors such that no one can be decomposed into components of the others.

$n$: In the context of Shor's algorithm, a number to be factored.

Periodic function: A function with a period $r$ such that $\mathcal{F}(x) = \mathcal{F}(x + r) = \mathcal{F}(x + 2r)$ and so on. Sine and Cosine are periodic functions.

Polynomial time: This is an attribute of an algorithm meaning that the number of operations required to compute the answer grows polynomially with the size of the input.

$q$: In the context of Shor's algorithm the power of 2 such that $n^{2} \leq q < 2n^{2}$.

Quantum memory register: A array of $n$ qubits which can exist in any superposition of its $2^{n}$ base states.

Quantum parallelism: The ability of a quantum computer to perform an operation on a quantum memory register which results in the simultaneous calculation of a function on all superposed values in the quantum memory register.

Quantum physics: Currently the most complete model for describing the behavior of physical systems.

Qubit: A two state quantum mechanical system, which can exist in any superposition of the 0 and 1 state. In this paper I have considered a spin-1/2 particle as a possible candidate for a qubit's physical implementation.

$r$: In the context of Shor's algorithm the period of the periodic function $x^{a} \bmod n$.

Shor's Algorithm: An algorithm designed by Peter Shor of Bell Labs which finds factors of a number $n$ in polynomial time on a quantum computer.

Spin-1/2 particle: A fundamental particle, by which I mean it has no components, which can be characterized as having a spin of +1/2 or -1/2.

State vector: The vector in a Hilbert Space which completely describes a quantum mechanical state vector.

Superposition: A mixture of base states. The state vector for a quantum mechanical systems, which can be measured in one of $n$ base states, can in general exist in any combination of components of the base states.

Turing machine: A theoretical computing device consisting of an infinite tape divided into cells which can hold a 1, a 0, or a blank and a head which can move around the tape, read and write bits, and change its own internal state. The Church-Turing Thesis hypothesizes that any computation which can be done on a classical computer can be done on a Turing machine.

Unit vector: A vector whose length is $1$.

$x$: In the context of Shor's algorithm a integer which is coprime to $n$ and used in the function $\mathcal{F}(a) = x^{a} \bmod n$.