Special Purpose Factoring Devices

   A journey from Bicycle to Quantum Computers

Computational Number Theory Project
Math 583e, University of Washington
Spring 2009

Quantum Computers

Reference: Wikipedia [The links open in Wikipedia]

A quantum computer is a device for computation that makes direct use of quantum mechanical phenomena, such as superposition and entanglement, to perform operations on data. The basic principle behind quantum computation is that quantum properties can be used to represent data and perform operations on these data. A classical computer has a memory made up of bits, where each bit holds either a one or a zero. A quantum computer maintains a sequence of qubits. A single qubit can hold a one, a zero, or, crucially, any quantum superposition of these. In general a quantum computer with n qubits can be in an arbitrary superposition of up to 2n different states simultaneously (this compares to a normal computer that can only be in one of these 2n states at any one time). A quantum computer operates by manipulating those qubits with a fixed sequence of quantum logic gates. The sequence of gates to be applied is called a quantum algorithm.

 

Shor's Algorithm for Factorization

Reference: Matthew Hayward's webpage and Wikipedia [Links open in Wikipedia]

Shor's algorithm, first introduced by mathematician Peter Shor in 1994, is a quantum algorithm for integer factorization. On a quantum computer, to factor an integer N, Shor's algorithm takes polynomial time in log N, specifically O((log N)3), demonstrating that integer factorization is in the complexity class BQP. This is exponentially faster than the best-known classical factoring algorithm, the general number field sieve, which works in sub-exponential time.

Shor's algorithm consists of two parts:

  1. A reduction of the factoring problem to the problem of order-finding. [can be done efficiently on a classical computer]
  2. A quantum algorithm to solve the order-finding problem. [hard on classical computers, but efficient in case of a quantum machine]

For further reading, please visit Matthew Hayward's page as mentioned above. To find a simulation of the Shor's algorithm (by Matthew Hayward) on a classical computer, click here.

 

Quantum Hardware

Reference: Wikipedia [The links open in Wikipedia]

There are a number of quantum computing candidates, among those:

The large number of candidates shows explicitly that the topic, in spite of rapid progress, is still in its infancy. But at the same time there is also a vast amount of flexibility.

In 2005, researchers at the University of Michigan built a semiconductor chip which functioned as an ion trap. Such devices, produced by standard lithography techniques, may point the way to scalable quantum computing tools.[22] An improved version was made in 2006.

 

<< Prev: Modern Day SPDs Next: Summary >>