Quantum Computing

SS 2015

News

  • The second exam will be an oral exam. Please send an e-mail to Erich Grädel to fix a date for the exam.
  • Preliminary exam results can be found here.
  • There is a new version of the script where some minor errors are corrected.
  • There will be a post-exam review (Klausureinsicht) Thursday, 3rd of September 2015, 11:00 to 12:00, in the seminar room 4116 at Lehrstuhl Informatik 7 (Computer Science Building, E1, 1st floor).
  • The exam will take place on 1st of September 2015 [AH V (2356|050)] between 14:00 and 16:00.
  • On sheet 7 exercise 3a) an error in the definition of the function f has been corrected.
  • The definition of universal has been added to Assignment 4 and Chapter 2 of the lecture notes.
  • If you cannot register for the lecture in Campus Office, please register by sending an e-mail to Faried Abu Zaid or Svenja Schalthöfer.
  • Update of Assignment 3: In Exercise 2, Bob's measurement has to be completely determined by Alice's, it does not have to be the same.
  • Update of Assignment 3: In Exercise 1 (b), you can use c-V and c-V*.
  • Because of the Fachschaftsvollversammlung there will be no lecture on May 5th. On May 6th, no assignemnt is published, and the exercise class on May 13th is cancelled as well.
  • Lecture notes from the winter term 09/10 are available. However, the contents do not necessarily correspond to this lecture. Thus, the lecture notes are still subject to change.
  • Learning Materials and exercises for this lecture will be published on this website. There is no L2P room for this lecture.

Schedule

TypeDateLocation Organizer
V2Di. 10.15 - 11.45AH IIBeginn 14. April E. Grädel
Ü2Mi. 14.15 - 15.45AH IBeginn 22. AprilF. Abu-Zaid, S. Schalthöfer

Exercises

On Wednesdays, an exercise sheet is available on this website. You should work on the exercises in groups of three students and hand in your solutions the following Wednesday by 14:15. Solutions can be put in the box at our chair or handed in at the beginning of the exercise class. In order to participate in the exam, you need to get 50 percent of the points in the assignments.

Content

You have nothing to do but mention the quantum theory, and people will take your voice for the voice of science, and believe anything. (George Bernard Shaw)

Ziel der Entwicklung von Quanten-Computern ist es, quantenmechanische Effekte auszunutzen um nicht-klassische Rechnersysteme zu bauen. Es ist zwar noch nicht sicher, ob Quanten-Computer mit mehr als ein paar wenigen Qubits überhaupt je gebaut werden konnen, aber in der Theorie zumindest erlauben Quanten-Phänomene fundamental neue Formen von Berechnungen. So hat die in den letzten Jahren entwickelte Theorie interessante und zum Teil sehr überraschende Resultate ergeben.

Formale Modelle fur Quanten-Computer sind Quanten-Turingmaschinen und ‘Quantum Gate Arrays’. Es handelt sich hier um probabilistische Berechnungsmodelle jedoch mit Interferenz von Konfigurationen sowie Übergangsregeln, die durch Wahrscheinlichkeitsamplituden anstelle von Wahrscheinlichkeiten spezifiziert werden. Wir werden diese Modelle analysieren und verschiedene Algorithmen fur Quanten-Computer behandeln. Speziell werden wir das aufsehenerregende Resultat von P. Shor zeigen, dass mit Quanten-Computern beliebig große Zahlen in polynomialer Zeit in ihre Primfaktoren zerlegt werden können, ein Problem, das im klassischen Fall offen ist und auf dessen Schwierigkeit die heutigen Public-Key-Kryptosysteme basieren. Quanten-Computer könnten also solche Kryptosysteme brechen.

Because nature isn't classical, dammit... (Richard P. Feynman)

Coursework

Literature

[1]J. Gruska. Quantum Computing. McGraw-Hill, 1999.
[2]M. Hirvensalo. Quantum Computing. Springer, 2001.
[3]N. D. Mermin. Quantum computer science: an introduction. Cambridge University Press, 2007.
[4]M. Nielsen and I. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000.

Lecture Notes

Classification

  • Informatik (B.Sc./M.Sc.): Wahlpflichtmodul Theoretische Informatik
  • Mathematik (B.Sc.): 4.,5.,6. Semester
  • Mathematik (M.Sc.): Reine Mathematik

Prerequisites

  • Lineare Algebra

Contact

Erich Grädel, Faried Abu Zaid, Svenja Schalthöfer