Abstract
Recent theoretical results confirm that quantum theory provides the possibility of new ways of performing efficient calculations. The most striking example is the factoring problem. It has recently been shown that computers that exploit quantum features could factor large composite integers. This task is believed to be out of reach of classical computers as soon as the number of digits in the number to factor exceeds a certain limit. The additional power of quantum computers comes from the possibility of employing a superposition of states, of following many distinct computation paths and of producing a final output that depends on the interference of all of them. This ``quantum parallelism'' outstrips by far any parallelism that can be thought of in classical computation and is responsible for the ``exponential'' speed-up of computation. This is a non-technical (or at least not too technical) introduction to the field of quantum computation. It does not cover very recent topics, such as error-correction.
Affiliated Institutions
Related Publications
Quantum Computation
If the bits of computers are someday scaled down to the size of individual atoms, quantum mechanical effects may profoundly change the nature of computation itself. The wave fun...
Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
A digital computer is generally believed to be an efficient universal computing device; that is, it is believed to be able to simulate any physical computing device with an incr...
Algorithms for quantum computation: discrete logarithms and factoring
A computer is generally considered to be a universal computational device; i.e., it is believed able to simulate any physical computational device with a cost in computation tim...
Quantum Computers, Factoring, and Decoherence
It is known that quantum computers can dramatically speed up the task of finding factors of large numbers, a problem of practical significance for cryptographic applications. Fa...
Strengths and Weaknesses of Quantum Computing
Recently a great deal of attention has focused on quantum computation following a sequence of results suggesting that quantum computers are more powerful than classical probabil...
Publication Info
- Year
- 1996
- Type
- article
- Volume
- 37
- Issue
- 5
- Pages
- 375-389
- Citations
- 115
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
115
OpenAlex
Cite This
Adriano Barenco,
Adriano Barenco
(1996).
Quantum physics and computers.
Contemporary Physics
, 37
(5)
, 375-389.
https://doi.org/10.1080/00107519608217543
Identifiers
- DOI
- 10.1080/00107519608217543