Quantum Computing Tutorial
Dr. Colin Williams
As NASA spacecraft explore deeper into the cosmos speed of light, limited signal delays make it impractical to command missions from Earth. Future spacecraft will need greater onboard computing capacity to mimic human-level intelligence and autonomy. One route to increasing such computing power is to turn to quantum computers. More than merely ultra-small computers, quantum computers can harness counter-intuitive physical effects not available to conventional computers to allow them to run entirely new kinds of algorithms and solve certain problems exponentially faster than is currently believed possible. This tutorial will cover the basics of quantum computing, review results in algorithmic quantum complexity theory, describe the operation of several quantum algorithms, and discuss possible applications for NASA in artificial intelligence and image processing. In addition, it will describe the progress being made to reduce abstract quantum computing concepts to practical hardware designs, including recent breakthroughs in quantum error correction, quantum compilers, and quantum computing hardware being built at JPL and elsewhere. Such breakthroughs may even have relevance to radiation hardening classical logic circuits. It will conclude by showing how quantum computing has inspired the design of new types of sensors and communication capabilities including teleportation and space-based quantum cryptography for securing command and control of orbital assets.
As miniaturization in our modern world deepens, and nano-technology and its machines become more prevalent in the real world, the need to consider using quantum mechanical concepts to perform various tasks in computation increases. Such tasks include: the teleporting of information, breaking heretofore "unbreakable" codes, communicating with messages that betray eavesdropping, and the generation of random numbers. This tutorial applies quantum physics to the basic operations of a computer, presenting us with the ideal vehicle for explaining the complexities of quantum mechanics to students, researchers and computer engineers, alike, as they prepare to design and create the computing and information delivery systems of the future. This tutorial evolved from a course taught by Colin Williams, to a group of students in theoretical computer science, and provides up-to-date reference material in the emerging interdisciplinary field of quantum computing. It presumes no background in quantum physics, or theoretical computer science, per se, but it does require knowledge of calculus and familiarity with the concept of the Turing machine. Also, included are visual imagery and graphics and Mathematica code to support their technical discussions in their examples.
Quantum mechanics gives a different kind of computational power, with superimposed states and entangled states having very different properties from classical zero or one states. Quantum computers can do (some) calculations exponentially faster than can their classical counterparts, such as factoring large numbers, by being able to explore many computations in parallel. Quantum computers aren't magic, and they are not all-powerful. For example, observing a quantum state "collapses the wave function" and destroys the crucial entangled state, changing the nature of any remaining computation -- so a quantum computation can be observed only at the end when it produces its result, not during the computation. (And only one result can be observed, so doing an exponential number of calculations in parallel does not give an exponential number of results -- one has to arrange the computation carefully so the answer observed is the one that is wanted.) One kind of activity that a quantum computer might do is to calculate a proof of a theorem. Quantum computers can also do things that classical computers cannot, such as generate genuine random (stochastic) numbers (as opposed to algorithmic pseudo-random numbers), communicate information so that eavesdroppers can be reliably detected, "teleport" information so that it never actually exists in any place other than at the sender and receiver.
About the speaker:
Dr. Colin Williams is a Senior Research Scientist in the Ultra Computing Technologies Group in the Exploration Systems Autonomy Section (367) at the Jet Propulsion Laboratory (JPL). He joined JPL in 1997 to start the Quantum Computing Technologies Group, after serving as a Visiting Scholar in the Knowledge Systems Laboratory at Stanford University from 1995-1996, and as a Research Scientist at Xerox PARC from 1990-1995. Williams earned his Ph.D. in Artificial Intelligence from the University of Edinburgh in 1989. He has published dozens of papers in peer reviewed journals on topics ranging from computational phase transitions in constraint satisfaction problems, to quantum neural networks, quantum tree search, quantum wavelet transforms, quantum computing hardware, quantum compilers, quantum repeaters, quantum lithography, and topological effects in physics. He is the co-author, along with Scott H. Clearwater, of two books on quantum computing -- Explorations in Quantum Computing and Ultimate Zero and One: Computing at the Quantum Frontier -- and editor for a third. He was the principal organizer of the first NASA International Conference in Quantum Computing and Quantum Communications. In addition, Williams was an Acting Associate Professor of Computer Science at Stanford University from 2000-2002.