Syllabus academic year 2011/2012
(Created 2011-09-01.)
QUANTUM COMPUTINGFMAN05
Credits: 6. Grading scale: TH. Cycle: A (Second Cycle). Main field: Technology. Language of instruction: The course will be given in English on demand. Optional for: D4, F4, F4tf, N4, Pi4. Course coordinator: Victor Ufnarovski, Victor.Ufnarovski@math.lth.se and Anders Holst, ah@maths.lth.se, Mathematics. Recommended prerequisits: FMAF05 or FMAF10. The course might be cancelled if the number of applicants is less than 10. Assessment: Written and/or oral test, to be decided by the examiner. A miniproject should be completed before the exam. Home page: http://www.maths.lth.se/matematiklth/personal/ssilvest/QuantumComputing/.

Aim
The main goal of the course is to give knowledge about, and ability to apply, notions and methods from quantum computations, i.e., computations with algorithms based on the mathematical principles of quantum mechanics and information theory, matrix theory and linear algebra; important in applications in a many subjects within technology and science. Moreover, the course should develop the student's ability to understand and communicate mathematical theory and to apply it in interplay with other subjects -- for example physics, information technology and computer science -- for the construction of a new generation of effective algorithms and for solving problems both theoretically and on the computer. Moreover, the course will strengthen the student’s knowledge of mathematical programming and scientific computing.

Knowledge and understanding
For a passing grade the student must

independently be able to characterize and use different types of quantum gates. Their input-output signal system presentation and matrix representation. Construction and presentation of quantum circuits and quantum algorithms in matrix and system forms.

be able to understand and independently explain the main examples and basics of the theory of quantum operations, and the applications of linear algebra, geometry of linear transformations and factorizations of matrices as the main tools for computations of more complex quantum operations from simpler ones.

be able to understand and explain the difference in complexity between quantum algorithms and classical algorithms, as well as explain the most important quantum algorithms, which are significantly more efficient than the classical ones.

be able to explain the basic ideas as well as the logical and the mathematical principles behind quantum cryptography algorithms, and describe the most important applications of quantum cryptography.

Skills and abilities
For a passing grade the student must

with the help of literature be able to integrate the methods and view points from different parts in the course in order to solve problems and answer questions within the framework of the course.

with the help of literature be able to use Matlab or Maple to solve mathematical problems within the course.

orally or in writing, in a logically connected manner and with appropriate terminology, be able to explain solutions of mathematical problems in the course.

with the help of library resources independently be able to assimilate and summarize the contents of technical texts in which quantum algorithms are used

Contents
Qubits and quantum gates as input-output signal systems, as vectors and matrices and as geometric objects and transformations in 2-dimensional and multi dimensional space. Quantum operations as linear transformations of density matrices, as matrices acting on vectors in a Hilbert space and as a mathematical description of quantum systems. Elementary quantum circuits and quantum operations. Their matrix representations and geometric interpretation.

Quantum circuits: construction from the elementary quantum gates as input-output signal systems with control and as matrix factorizations. The Kronecker tensor product of matrices and vectors, and its application in the construction of quantum circuits.

Matrix norms. Error estimates and error minimization in the construction of quantum circuits.

Universal and error correcting codes in matrix and in circuit form.

The most famous quantum algorithms and their mathematical content: Shor’s factorization algorithm, the quantum Fourier transform and its computation with classical and quantum algorithms, algorithms for finding the period, subgroup search problem and algorithms. Grovers search algorithm.

The notion of mathematical complexity of an algorithm. Comparison of classical and quantum algorithms with respect to their complexity.

Simulation of quantum circuits and quantum algorithms. The mathematical and information theoretical principles for quantum cryptography and quantum cryptography algorithms.

Literature
Nielsen, M.A. and Isaac L.Chuang, I.L. Quantum Computation and Quantum Information. Cambridge University Press, 9th edition, 2007. ISBN 978-0521635035.
A. Yu Kitaev, A. H. Shen, et M. N. Vyalyi. Classical and Quantum Computation. American Mathematical Society, 2002. ISBN 9780821832295.
David McMahon. Quantum Computing Explained. John Wiley & Sons, Inc., 2008.ISBN 9780470096994.