Global Sales Contact List

Contact   A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

RSA Laboratories

7.17 What is quantum computing?

Quantum computing [Ben82] [Fey82] [Fey86] [Deu92] is a new field in computer science that has been developed with our increased understanding of quantum mechanics. It holds the key to computers that are exponentially faster than conventional computers (for certain problems). A quantum computer is based on the idea of a quantum bit or qubit. In classical computers, a bit has a discrete range and can represent either a zero state or a one state. A qubit can be in a linear superposition of the two states. Hence, when a qubit is measured the result will be zero with a certain probability and one with the complementary probability. A quantum register consists of n qubits. Because of superposition, a phenomenon known as quantum parallelism allows exponentially many computations to take place simultaneously, thus vastly increasing the speed of computation.

Quantum interference, the analog of Young's double-slit experiment that demonstrated constructive and destructive interference phenomena of light, is one of the most significant characteristics of quantum computing. Quantum interference improves the probability of obtaining a desired result by constructive interference and diminishes the probability of obtaining an erroneous result by destructive interference.Thus, among the exponentially many computations, the correct answer can theoretically be identified with appropriate quantum ``algorithms.''

It has been proven [Sho94] that a quantum computer will be able to factor (see Question 2.3.3) and compute discrete logarithms (see Question 2.3.7) in polynomial time. Unfortunately, the development of a practical quantum computer still seems far away because of a phenomenon called quantum decoherence, which is due to the influence of the outside environment on the quantum computer. Brassard has written a number of helpful texts in this field [Bra95a] [Bra95b] [Bra95c].

Quantum cryptography (see Question 7.18) is quite different from, and currently more viable than, quantum computing.

Top of the page