Tutorial

Over the last decade a new way to compute has been defined which, unlike conventional methods, is based on quantum mechanics rather than classical physics. This fundamental change in paradigm can, in principle, solve some important and hitherto intractable problems such as prime factorization of large numbers. This tutorial presentation will review the basics of quantum computation and the design of circuits to implement quantum algorithms. The starting point is the notion of a quantum bit or qubit. Because of the superposition property of quantum states, n qubits can store 2n numbers simultaneously, implying a type of massive parallelism. Furthermore, quantum states allow powerful forms of interaction such as entanglement that have no classical counterparts. Qubits are fragile, however, and are altered by measurement; hence quantum circuits must follow very different rules from classical ones. The differences between quantum and classical logic circuits will be discussed and illustrated. Finally, the physical implementation of quantum devices will be considered, along with the prospects for practical quantum computers.