A quantum computer is a device for computation that makes direct use of distinctively quantum mechanical phenomena, such as superposition and entanglement, to perform operations on data. In a classical (or conventional) computer, information is stored as bits; in a quantum computer, it is stored as qubits (quantum bits).

The
basic principle of quantum computation is that the quantum properties
can be used to represent and structure data, and that quantum
mechanisms can be devised and built to perform operations with this
data. Although quantum computing
is still in its infancy, experiments have been carried out in which
quantum computational operations were executed on a very small number
of qubits. Research in both theoretical and practical areas continues
at a frantic pace, and many national government and military funding
agencies support quantum computing research to develop quantum
computers for both civilian and national security purposes, such as cryptanalysis.
If large-scale quantum computers can be built, they will be able to
solve certain problems exponentially faster than any of our current
classical computers (for example Shor’s algorithm).

Quantum computers are different from other computers such as DNA computers and traditional computers based on transistors.

Some
computing architectures such as optical computers may use classical
superposition of electromagnetic waves, but without some specifically quantum mechanical resources such as entanglement,
they have less potential for computational speed-up than quantum
computers. The power of quantum computers Integer factorization is
believed to be computationally infeasible with an ordinary computer for
large integers that are the product of only a few prime numbers (e.g.,
products of two 300-digit primes). By comparison, a quantum computer
could solve this problem more efficiently than a classical computer
using Shor’s algorithm to find its factors.

This ability would allow a quantum computer to “break” many of the cryptographic systems
in use today, in the sense that there would be a polynomial time (in
the number of bits of the integer) algorithm for solving the problem.

In particular, most of the popular public key ciphers are based on the difficulty of factoring integers, including forms of RSA.

These are used to protect secure Web pages,
encrypted email, and many other types of data. Breaking these would
have significant ramifications for electronic privacy and security. The
only way to increase the security of an algorithm like RSA
would be to increase the key size and hope that an adversary does not
have the resources to build and use a powerful enough quantum computer.
It seems plausible that it will always be possible to build classical
computers that have more bits than the number of qubits in the largest quantum computer.