The best-known quantum algorithms

Shor’s algorithm

Shor’s algorithm is a polynomial-time quantum computer algorithm for integer factorization. It was invented in 1994 by the American mathematician Peter Shor.

Shor’s algorithms runs much (almost exponentially) faster than the best-known classical algorithm for factoring, the general number field sieve.

Shor’s algorithm was the first non-trivial quantum algorithm showing a potential of ‘exponential’ speed-up over classical algorithms, It captured the imagination of many researchers who took notice of quantum computing because of its promise of truly remarkable algorithmic acceleration. Therefore, to implement Shor’s algorithm is comparable to the ‘Hello, World’ of classical computing. (Mark Ritter, senior manager of physical sciences at IBM)

Peter Shor

Shor: I’ve been writing poetry occasionally since high school, but I never considered making a career of it.

If computers that you build are quantum,
Then spies of all factions will want ‘em.
Our codes will all fail,
And they’ll read our email,
Till we’ve crypto that’s quantum, and daunt ‘em.
(by Jennifer and Peter Shor)

You can see why I chose a career as a scientist rather than as a poet.(Shor’s joke)

There are several aspects of quantum mechanics that make quantum computers more powerful than digital computers. One of these is the superposition principle, which says that a quantum system can be in more than one state at the same time. Another one of these is interference; a third is the exponentially large size of the state space of a quantum mechanical system.

There are some problems that quantum computers seem to be exponentially faster than classical computers at, like factoring. There are other problems that quantum computers don’t speed up at all, like sorting. So asking “which is better, a classical computer or a quantum computer” is like asking “which is a better transportation device, a boat or a car.” It really depends on what you want to do with it.

Grover’s algorithm

Grover’s algorithm is a quantum algorithm for searching an unstructured database or an unordered list. It was devised by Lov Grover in 1996.

Grover’s algorithm runs quadratically faster than the best possible classical algorithm for the same task, a linear search.

Unlike other quantum algorithms, which may provide exponential speedup over their classical counterparts, Grover’s algorithm provides only a quadratic speedup. However, even quadratic speedup is considerable when N is large.

Grover’s algorithm demonstrate the power of quantum parallelism, in specific, making queries in parallel.