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

: A variable that when used in the context of Shor's algorithm is an argument to the function $\mathcal {F}$(a) = x^a mod n. It may be a single integer, or it may denote a superposition of states.

Algorithm

: A method for producing some answer given some inputs.

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 Church-Turing Thesis can be thought of as defining the class of functions which are effectively calculable as those which can be computed by a 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. By definition (e.g. the Church-Turing Thesis) a classical computer can only compute functions that a Turing machine can compute.

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

: A collapse in the context of this paper is what happens to the state vector of a quantum mechanical system 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.

Complexity-Theoretic Church-Turing Thesis

: The hypothesis that a Turing machine can efficiently simulate any realistic model of computation. Here efficiently means with polynomial time overhead. It should be noted that this is a hypothesis only, however the advent of a physically realizable computing device which violates this thesis would be a major breakthrough, and there are arguments as to why such a breakthrough may never occur.

Coprime

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

Discrete Fourier Transform

: A transformation converts a finite list of equally spaced samples of a function into a list of coefficients of finite combinations of circles, ordered by their frequencies, that have the same values. In Shor's algorithm it is used to calculate and multiple of the inverse period, where the period is the quantity which enables Shor's algorithm to find factors of a number n.

Exponential

: A function which goes as: $\mathcal {F}$(x) = a^x, where a is some constant greater than 1.

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

: An 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. The lowest known running time for this problem on a classical computer is O(n).

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 such that vectors within the space which are added or multiplied together result in vectors that also lie within the same space.

Memory register

: A array of bits on a classical computer. A memory register of size n may store one of 2ⁿ values.

Mutually perpendicular

: In the context of vector spaces mutually perpendicular items are items 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 typical examples of periodic functions.

Polynomial time

: This is an attribute of an algorithm which means the number of operations required to compute the answer grows polynomially with the size of the input n (E.g. like n^c for some constant c).

q

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

Quantum memory register

: A array of n qubits which can exist in any superposition of its 2ⁿ 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 function of 2ⁿ different values where n is the size of the quantum memory register.

Quantum physics

: Currently the most complete model for describing the behavior of small 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 in a physical implementation of a qubit.

r

: In the context of Shor's algorithm the period of the periodic function x^a mod n.

Shor's Algorithm

: A algorithm designed by Peter Shor of Bell Labs which finds factors of a number n in polynomial time relative to the number of bits in n's binary representation on a quantum computer. The fastest published algorithm on a classical computer is slower than polynomial time, and the presumed intractability of this problem is the basis for many cryptographic systems.

Spin-1/2 particle

: A particle which can be characterized as having a spin of +1/2 or -1/2. Examples include the proton, neutron, and electron.

State vector

: In the context of this paper, the state vector in a Hilbert Space which completely describes a quantum mechanical state vector - such as the state of quantum memory register.

Superposition of states

: A mixture of base states. The state vector for a quantum mechanical systems which can be measured in one of n base states can exist as 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 defines effectively computable functions as those which can be computed by 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 mod n.