Topics in quantum computing

There are a variety of topics that "traditionally" are covered in a quantum computing course. I list some of this on this website to give a first impression of what is required of a quantum computing course. There is a significant portion of the course that deals with the quantum mechanics of quantum computers. In addition, complexity theory and linear algebra are used to build the idea of a quantum computer.

The following two outlines give a general idea about the topics covered in a quantum computing course. A significant amount of time is spent building the theoretical foundations of a quantum computing. Once the foundations have been built, quantum algorithms and feasibility are covered.

Outline

• Ieneral Introduction.
• Postulates of Quantum Mechanics.
• Church-Turing thesis.
• Quantum Bits, Gates and Registers.
• Quantum Circuits.
• Quantum Teleportation.
• Quantum Fourier Transform and Applications (including integer factorization).
• Physical Realizations.
• Fault Tolerant Quantum Error Correction.

Another outline:

• Fundamentals of Quantum Theory: This will introduce the student to the basic principles of quantum mechanics needed to follow the course. By confining attention to the two-level "spin" systems important in quantum computation, much of the confusion surrounding observables (such as position and momentum) with continuous spectrum rather than eigenvalues can be avoided. Emphasis will be on the basic concepts of state, observable, measurement and superposition.
• Principles of Quantum Computation: Historically, quantum computers and quantum gates arose from efforts to understand questions about the reversibility of computation. This led to the realization that quantum computers (which are not Turing machines) could be designed which are more powerful than classical computers. The course will explain the differences between idealized classical and quantum computers. The emphasis will be on those aspects which seem important for understanding recent developments.
• Shor's Algorithm: In addition to solving an important problem, Shor' algorithm for factoring large numbers has several features which merit attention. These include (i) conversion of the factoring problem to one of finding the period of a function and (ii) the quantum Fourier transform.
• Entanglement and Error-Correction: Real quantum computation will have errors and quantum communication will have noise. It was once thought that the "no-cloning" principle of quantum states precluded the possibility of error-correction. However, in 1996, R. Calderbank and P. Shor showed that quantum error correcting codes exist which do not violate the principles of quantum mechanics. These are based on the notion of "entangled" states, i.e., multi-bit states which are non-trivial linear combinations of product states rather than simple products. The course will cover the basics of entanglement and quantum error correction.
• Quantum Communication: Encoding and decoding quantum messages requires only that the sender and receiver agree on a direction. Interception in another direction is effectively encrypted. However, in addition to the usual sources of noise, interception can also generate noise. Quantum entanglement can also be used to enhance transmission, detect, errors etc. The course will include discussion of models of quantum communication and noise.
• Quantum Information Theory: In noisy systems, mixtures, as well as pure states, can occur. (Superpositions, although probabilistic, are pure states rather than mixtures.) This leads to questions about entropy, channel capacity, etc. similar to those in Shannon's classical information theory.