Difference between revisions of "Quantum computation"
(New page: == Quantum computation and encryption ...) |
m (Quantum computer moved to Quantum computation) |
(No difference)
|
Revision as of 08:04, 29 July 2008
Quantum computation and encryption
Determining the prime factors of a number is an example of a problem frequently used to ensure cryptographic security in encryption systems; this problem is believed to require superpolynomial time in the number of digits - it is relatively easy to construct a problem that would take longer than the known age of the Universe to calculate on current computers using current algorithms.
Shor's algorithm is a quantum algorithm for integer factorization. On a quantum computer, Shor's algorithm takes time O((log N)3) to factor an integer N. This is exponentially faster than the best-known classical factoring algorithm, which works in time about [math]O(2^{{(\log N)}^{1/3}})[/math]. Peter Shor discovered the eponymous algorithm in 1994.
Shor's algorithm is important because it breaks a widely used public-key cryptography scheme known as RSA. RSA is based on the assumption that factoring large numbers is computationally infeasible. So far as is known, this assumption is valid for classical computers. No classical algorithm is known that can factor in time polynomial in log N. However, Shor's algorithm shows that factoring is efficient on a quantum computer, so a quantum computer could "break" RSA.
A way out of this dilemma would be to use some kind of quantum cryptography. There are also some digital signature schemes that are believed to be secure against quantum computers. See for instance Lamport signatures.
Grover's algorithm can also be used to obtain a quadratic speed-up [over a brute-force search] for the NP-complete class of problems.