I066 Quantum algorithms and automata

Faculty of Informatics
Autumn 2001
Extent and Intensity
2/0. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: k (colloquium), z (credit).
Teacher(s)
prof. RNDr. Jozef Gruska, DrSc. (lecturer)
Guaranteed by
prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Jozef Gruska, DrSc.
Timetable
Wed 14:00–15:50 B411
Prerequisites (in Czech)
I005 Formal Languages and Automata I && I012 Complexity && M011 Statistics I
Course Enrolment Limitations
The course is also offered to the students of the fields other than those the course is directly associated with.
fields of study / plans the course is directly associated with
Course objectives
Lecture contains an introduction to quantum computers and quantum information processing and communication. This is anew, rapidly developing area of informatics (and quantum physics) that shows potential and limitations of computation and communication systems based on principles and limitations of quantum mechanics. No preliminary knowledge of quantum physics is necessary.
Introduction (Comparison of classical and quantum computing. Basic principles and experiments of quantum mechanics, reversible gates and Turing machines.
Basics of Hilbert spaces.
Quantum computing elements (Qubits, quantum registers, quantum entanglement, quantum gates and circuits)
Quantum teleportation and Bell theorem.
Algorithms (Examples of quantum algorithms for simple promise problems, Shor's and Grover's algorithms, methodologies to design quantum algorithms, lower bounds methods).
Quantum automata (quantum finite auromata, quantum Turing machines, quantum cellular automata)
Quantum complexity (Quantum computational and communicational complexity)
Syllabus
  • Lecture contains an introduction to quantum computers and quantum information processing and communication. This is anew, rapidly developing area of informatics (and quantum physics) that shows potential and limitations of computation and communication systems based on principles and limitations of quantum mechanics. No preliminary knowledge of quantum physics is necessary.
  • Introduction (Comparison of classical and quantum computing. Basic principles and experiments of quantum mechanics, reversible gates and Turing machines.
  • Basics of Hilbert spaces.
  • Quantum computing elements (Qubits, quantum registers, quantum entanglement, quantum gates and circuits)
  • Quantum teleportation and Bell theorem.
  • Algorithms (Examples of quantum algorithms for simple promise problems, Shor's and Grover's algorithms, methodologies to design quantum algorithms, lower bounds methods).
  • Quantum automata (quantum finite auromata, quantum Turing machines, quantum cellular automata)
  • Quantum complexity (Quantum computational and communicational complexity)
Literature
  • GRUSKA, Jozef. Quantum computing. London: McGraw-Hill Companies, 1999, xv, 439. ISBN 0077095030. info
Language of instruction
Slovak
Further Comments
The course is taught annually.
The course is also listed under the following terms Autumn 1998, Autumn 1999, Autumn 2000.
  • Enrolment Statistics (recent)
  • Permalink: https://is.muni.cz/course/fi/autumn2001/I066