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

• The lecture notes are online as slides in several formats.

Here are some useful links to papers about quantum computing.