(Also lomonster.com and clomont.com)

Quantum computing resources

A quantum computing overview

A quantum computing seminar I gave in 2003-2004

Useful papers in quantum computing (circa 2004)

Quantum Computing Overview

Quantum computing is a new approach to computation that has the possibility to revolutionize the field of computer science. The late Nobel Prize winning physicist Richard Feynman, who was interested in using a computer to simulate quantum systems, first investigated using quantum systems to do computation in 1982. He realized that the classical storage requirements for quantum systems grows exponentially in the number of particles, so while simulating twenty quantum particles only requires storing a million values, doubling this to a forty particle simulation would require a trillion values. Interesting simulations, say using a hundred or thousand particles, would not be possible, even using every computer on the planet. Thus he suggested making computers that utilized quantum particles as a computational resource that could simulate general quantum systems in order to do large simulations, and the idea of using quantum mechanical effects to do computation was born. The exponential storage capacity, coupled with some spooky effects like quantum entanglement, has led researchers to probe deeper into the computing power of quantum systems. Quantum computing has blossomed over the past 20 years, demonstrating the ability to solve some problems exponentially faster than any current computer could ever do. The most famous algorithm, the integer-factoring algorithm of Peter Shor, would allow the most popular encryption methods in use today to be cracked easily, if large enough quantum computers can be constructed. Thus the race is on to develop the theory and hardware that would enable quantum computing to become as widespread as PCs are today.

Classical computers, which include all current mainstream computers, work on discrete pieces of information, and manipulate them according to rules laid out by John Von Neumann in the 1940's. In honor of his groundbreaking work, current computers are said to run on a "Von Neumann architecture", which is modeled on an abstraction of discrete pieces of information. However, in recent years, scientists have changed from this abstraction of computing, to realizing that since a computer must ultimately be a physical device, the rules governing computation should be derived from physical law. Quantum mechanics is one of the most fundamental physical theories, and thus was a good choice to study what computational tasks could be physically achieved. This study led to the profound discovery that quantum mechanics allows much more powerful machines than the Von Neumann abstraction.

Another amazing quantum algorithm, besides the factoring algorithm of Shor, is Lov Grover's search algorithm, which greatly reduces the work needed to search for a specific item. For example, to search through one million unsorted names for a specific name averages about 500,000 compares with a classical computer, and there is no better way to do it under the Von Neumann model of computing. However, the same name can be found with only 1,000 compares using Grover's algorithm under the quantum model, which exploits the parallel nature of quantum mechanics. For bigger lists Grover's algorithm beats the classical one by an even greater amount!

Quantum computing today is a vast and varied field. There researchers working on areas ranging from making physical devices, using numerous technologies such as trapped ions and quantum dots, to people working on the theory side, solving thorny algorithm questions and trying to determine the exact power of quantum computation. It has been proven that quantum computers are be strictly more powerful than classical ones, but how far that power reaches is still an open question. And how to build a big quantum computer is a hard technological problem.

So quantum computation is just in it's infancy, much like classical computing with the vacuum tube computers like ENIAC and the Harvard MARK I computers of the 1940's. If the technological hurdles are overcome, in the same manner that many decades of work refined the classical computer from the slow lumbering vacuum-tube behemoths of the 1940's to the sleek, speedy transistorized computers that are currently widespread, then perhaps quantum computation will one day replace all current computation methods with a superior form of computation. All this from quantum mechanics, with weird rules and methods rooted in the weirdness of Nature Herself. Only time can tell what computers will be derived from deeper physical theories like quantum field theory or superstring theory!

Quantum Computing Seminar - 2003-2004

Here are some useful links to papers about quantum computing.

Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer xxx.lanl.gov/abs/quant-ph/9508027 Peter Shor's famous paper on factoring and the discrete log problem. This is the paper that really brought attention to quantum computing.
Introduction to Quantum Algorithms
A good introduction to quantum algorithms by Peter Shor.
Quantum Computation and Quantum Information

Quantum Computation

Two very good collections of papers by many authors, collected at Sam Lomonaco's website, and published by the AMS.
Elementary gates for quantum computation
Numerous authors - this paper shows how to construct many types of quantum circuits.
Good Quantum Error-Correcting Codes Exist
Calderbank and Shor's paper on quantum error correcting codes, removing one of the last obstacles to the theory of quantum computing.
Equivalence of Additivity Questions in Quantum Information Theory xxx.lanl.gov/abs/quant-ph/0305035 A 2003 overview of many open questions in quantum information theory, by Peter Shor.
Hidden Subgroup States are Almost Orthogonal
Ettinger, Hoyer, and Knill's paper showing that the hidden subgroup problem (HSP) can be solved for all finite groups, at least information theoretically. It is a major open problem if this can be done efficiently.
The Hidden Subgroup Problem in Affine Groups: Basis Selection in Fourier Sampling
A very good overview of state of the art for the HSP, as of 2002. It references other papers, and sums up current knowledge in a nice, concise manner.