Quantum Algorithms

An operator taking a register in a superposition of states as an input performs a ``computation'' on each of the components of the superposition simultaneously. Since the number of possible superposed states is 2^N for an N-qubit register, in some sense a quantum computer can perform in one operation what would take an exponential number of operations on a classical computer. Unfortunately, the more superposed states, the smaller the probability that we will measure the value of our function for any particular one. Some clever algorithms, most notably by Peter Shor and L. K. Grover, succeed by considering a function for which some property of all the inputs is useful.

A quantum memory register is just a state machine whose state transitions are defined by the operators we apply. A reversible deterministic state machine with 2^N states can be modeled by an N-bit register and operators which are 2^N x 2^N permutation matrices. A classical probabilistic state machine can be modeled in a similar manner, as an N-bit register with a normalized state vector in $\Real^{{2^{N}}}_{}$ and operators that are doubly stochastic matrices. The difference between the quantum computer and the probabilistic computer is that the projection of the quantum state vector onto any eigenstate is a complex number: it has both a magnitude and a phase. The classical probabilistic state vector's projection onto its eigenstates has only a positive real magnitude. The amplitude of the quantum state vector allows for operators which cause wave-like interference of the eigenstates, enforcing correct solutions and diminishing incorrect ones [11].

A quantum algorithm is described by an initial normalized state and a sequence of unitary matrices representing linear transformations of the state vector. These unitary matrices should increase the probability that the state vector collapses into a correct solution state when measured.