fake tag heuer

Simulation of Quantum Computation on Intel-Based Architectures

Yan Pritzker
Gzipped Postscript

An excellent paper introducing both Quantum Mechanics and the simulation of it on computers. Written by the founder of the OpenQubit Quantum Computing Group.

Summary:
“…trying to find a computer simulation of physics, seems to me to be an excellent program to follow out…and I’m not happy with all the analyses that go with just the classical theory, because NATURE ISN’T CLASSICAL, dammit, and if you want to make a simulation of nature, you’d better MAKE IT QUANTUM MECHANICAL, and by golly it’s a wonderful problem because it doesn’t look so easy.”
– Richard P. Feynman (1981) (International Journal of Theoretical Physics, VOl. 21, p.486)

Quantum Physics and Computers

Adraino Barnco
Gzipped Postscript
PDF

Recent theoretical results confirm that quantum theory provides the possibility of new ways of performing efficient calculations.

Summary:
Recent theoretical results confirm that quantum theory provides the possibility of new ways of performing efficient calculations. The striking example is the factoring problem. It has recently been shown that computers that exploit quantum features coul d 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 e mploying 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 classi cal computation and is responsible for the “exponential” speed-up of computation.

Polynomial-Time Alorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer

Peter Shor
Gzipped Postscript
PDF

This paper considers factoring integers and finding discrete logarithms, two problems which are generally thought to be hard on classical computers and which have been used as the basis of several proposed cryptosystems.

Summary:
A digital computer is generally believed to be an efficient universal computing device; that is, it is believed able to simulate any physical computing device with an increase in computation time by at most a polynomial factor. This paper considers factoring integers and finding discrete logarithms, two problems which are generally thought to be hard on classical computers and which have been used as the basis of several proposed cryptosystems. Efficient randomized algorithms are given for these two problems on a hypothetical quantum computer. These algorithms take a number of steps polynomial in the input size, e.g., the number of digits of the integer to be factored.

Simulation of Quantum Computers

Bernhard Oemer
HTML (Online)
This paper gives a general introduction to quantum computing and deals with the problems of simluating quantum computers on classical hardware. As an example, a simulation of Shor’s factorization algorithm is presented.

Summary:
The steady process of computer miniaturization will soon come to a scale where quantum effects on computation can no longer be ignored. Hardware development will finally reach a point where boolean logic will no longer be applicable and the classical con cept of a universal deterministic computer wiht the Turing machine as a mathematical model will have to be replaced by a quantum theory of computation.