Lehr- und Forschungseinheit für Theoretische Informatik,
Institut für Informatik
der Ludwig-Maximilians-Universität München
Seminar im Hauptstudium (SS 03):
Quantencomputer
Raumänderung: Ab sofort (16.4.) findet das Seminar im Hörsaal 1.43 in der
Oettingenstr. 67 statt. (Ausnahme: 9.7.)
Zum Erstellen der Ausarbeitung und des Vortrages
können diese LaTeX-Skelette verwendet werden.
- Veranstalter:
- M. Lange, Oettingenstr. 67, D1.07
- Termine:
- Zeit: Mi 12 - 14
- Ort: Raum 1.43, Oettingenstr. 67
- Beginn: 9.4.03
- Zuordnung:
- PG
- Vorkenntnisse:
- Vordiplom
- Hörerkreis: :
- Studierende der Informatik im Hauptstudium
- Studierende mit Nebenfach Informatik
- Schein:
- Schein gilt für Diplomprüfung in
Haupt- und Nebenfach Informatik
- Scheinerwerb durch Ausarbeitung, Vortrag und Teilnahme am Seminar
Mit immer kleiner werdenden elektronischen Schaltelementen in Computern sind quantenmechanische Effekte
bei Berechnungsprozessen irgendwann einmal nicht zu vernachlässigen. Umgekehrt stellt sich die
auf Feynman zurückgehende Frage, ob diese Effekte für Berechnungen nicht im positiven Sinne
ausgenutzt werden können.
Ein Quantencomputer, wie er von Deutsch und anderen formuliert wurde, lässt sich auf einem
klassischen Computer simulieren. Daher können Quantencomputer nicht die Church-Turing-These
widerlegen. Die Simulation erfordert jedoch exponentiellen Aufwand. Daher ist es denkbar, dass
ein Quantencomputer im komplexitätstheoretischen Sinne ein stärkeres Berechnungsmodell als ein
klassischer ist.
Dieses Seminar behandelt die für die theoretische Informatik relevanten Aspekte, im speziellen
Quantencomputer als Berechnungsmodelle, Algorithmen, Komplexität, Kryptographie und
Programmiersprachen.
Vorträge:
| | Datum | Thema | Literatur | Vortragender | Betreuer |
|---|
| 1 | 9.4. | Einführung |
[BV97] Kap. 1-2, [Bac96] Kap. 1-6, [Sal98] Kap. 1-3 | M. Lange | |
| 2 | 16.4. | Die universelle Quanten-Turing-Maschine |
[BV97] Kap. 3-7, [Deu83] | M. Schmeißer | M. Lange |
| 3 | 23.4. | Die Berechnungsstärke von QTMs
(Anhang) | [BV97] Kap. 8 |
T. Singhammer | M. Lange |
| 4 | 30.4. | Orakel-Quanten-Turing-Maschinen |
[BB92], [Sim97] |
M. Latte | M. Lange |
| 5 | 7.5. | Quanten-NP und die polynomielle Hierarchie |
[FGHP98b], [FGHP98a] |
M. Latte | M. Lange |
| 6 | 14.5. | Quanten-Schaltkreise | [Yao93] |
M. Ratajczak | M. Lange |
| 7 | 21.5. | Suche in Datenbanken |
[Gro96], [Mey00], [BBHT96] | T. Reinberger | M. Lange |
| 8 | 28.5. | Endliche Quanten-Automaten | [KW97], [Wat97] |
M. Ratajczak | M. Lange |
| 9 | 4.6. | Kryptographie I | [Sal98], [Cré] |
S. Iliopoulos | S. Jost |
| 10 | 11.6. | Kryptographie II | [Sal98], [Cré] |
S. Iliopoulos | S. Jost |
| 11 | 18.6. | Quanten-Flussdiagramme | [Sel02] Kap. 1-4 |
A. Schroeder | A. Abel |
| 12 | 25.6. | Die Quanten-Programmiersprache QPL |
[Sel02] Kap. 5-7 | A. Schroeder | A. Abel |
| 13 | 2.7. | fällt voraussichtlich aus | |
| |
| 14 | 9.7. | Quantum error correction | [Sho95], [Ste96] |
B. Stein | M. Lange |
Zusätzlich zu der angegebenen Literatur empfiehlt es sich, grundsätzliches über Quantencomputer zu lesen.
Dafür bieten sich die Vorlesungsskripte [Pre00] und [Vaz97], sowie die Bücher [NC00], [Gru99] und [WC98] an.
- [Bac96]
- D. Bacon.
Quantum computation and
np-completeness.
(unpublished), 1996.
- [BB92]
- A. Berthiaume and
G. Brassard.
Oracle quantum computing.
In Proc. of the Workshop on Physics of Computation,
PhysComp'92, pages 195-199, Los Alamitos, CA, 1992. Institute of
Electrical and Electronic Engineers Computer Society Press.
- [BBB+92]
- C. H. Bennett, F. Bessette, G. Brassard,
L. Salvail, and J. Smolin.
Experimental quantum cryptography.
Journal of Cryptology, 5(1):3-28, 1992.
- [BBHT96]
- M. Boyer, G. Brassard, P. Høyer, and
A. Tapp.
Tight bounds on quantum searching.
Technical Report PP-1996-11, Department of Mathematics and Computer Science,
Odense University, May 30 1996.
- [BCS01]
- S. Bettelli, T. Calarco, and
L. Serafini.
Toward an architecture for quantum programming.
(unpublished), 2001.
- [BHT98]
- G. Brassard, P. Høyer, and A. Tapp.
Quantum counting.
In Proc. Annual Int. Coll. on Automata, Languages and Programming,
ICALP'98, volume 1443 of LNCS, pages 820--??, 1998.
- [BV97]
- E. Bernstein and
U. Vazirani.
Quantum complexity theory.
SIAM Journal on Computing, 26(5):1411-1473, October 1997.
- [CEMM97]
- R. Cleve, A. Ekert,
C. Macchiavello, and M. Mosca.
Quantum algorithms revisited.
Proc. Royal Society of London, A, 1997.
- [Cré]
- C. Crépeau.
Cryptographic primitives and quantum theory.
- [Deu85]
- D. Deutsch.
Quantum theory, the Church-Turing principle and the universal quantum computer.
Proc. Royal Society of London, A400:97-117, 1985.
- [FGHP98a]
- S. Fenner, F. Green, S. Homer, and
R. Pruim.
Determining
acceptance possibility for a quantum computation is hard for PH.
Technical Report 1998-008, CS Department, Boston University, April 1998.
- [FGHP98b]
- S. Fenner, F. Green, S. Homer, and
R. Pruim.
Quantum np is hard for ph.
In Proc. 6th Italian Conf. on Theoretical Computer Science,
pages 241-252. World-Scientific, 1998.
- [Gro96]
- L. K. Grover.
A fast quantum mechanical algorithm for database search.
In Proc. 28th Annual ACM Symp. on the Theory of Computing,
STOC'96, pages 212-219, New York, NY, USA, May 1996. ACM.
- [Gru99]
- J. Gruska.
Quantum Computing.
McGraw-Hill, 1999.
(In Mathematik-Bibliothek).
- [JHL93]
- L. P. Jones,
J. Hughes, and J. Launchbury.
How to give a good research talk.
ACM SIGPLAN Notices, 28(11):9-12, November 1993.
- [KW97]
- A. Kondacs and J. Watrous.
On the power of quantum finite state automata.
In Proc. 38th Annual Symp. on Foundations of Computer Science,
FOCS'97, pages 66-75. IEEE, October 1997.
- [Mey00]
- D. A. Meyer.
Sophisticated quantum search without entanglement.
Physical Review Letters, 85(9):2014-2017, August 2000.
- [NC00]
- M. A. Nielsen and I. L. Chuang.
Quantum Computation and Quantum Information.
Cambridge University Press, 2000.
(In Mathematik-Bibliothek).
- [Oem02]
- B. Oemer.
Classical concepts in quantum programming.
submitted, 2002.
- [Pre00]
- J. Preskill.
Quantum computation.
lecture notes, 2000
- [Sal98]
- L. Salvail.
The search for the holy grail in quantum cryptography.
In I. Damgård, editor, Lectures on data security: modern cryptology
in theory and practise, volume 1561 of LNCS, pages
183-216. Springer, 1998.
- [Sel02]
- P. Selinger.
Towards a quantum programming language.
submitted, 2002.
- [Sho97]
- P. W. Shor.
Polynomial-time algorithms for prime factorization and discrete logarithms on a
quantum computer.
SIAM Journal on Computing, 26(5):1484-1509, October 1997.
- [Sho95]
- P. W. Shor.
Scheme for reducing decoherence in quantum computer memory.
Phys. Rev. A 52, R2493-R2496, 1995.
- [Sim97]
- D. R. Simon.
On the power of quantum computation.
SIAM Journal on Computing, 26(5):1474-1483, October 1997.
- [Sin99]
- Simon Singh.
The code book: the evolution of secrecy from Mary, Queen of Scots, to
quantum cryptography.
Doubleday, New York, NY, USA, 1999.
(In Mathematik-Bibliothek).
- [Ste96]]
- A. Steane.
Multiple Particle Interference and Quantum Error Correction.
Proc.Roy.Soc.Lond. A452:2551, 1996
- [Vaz97]]
- U. Vazirani.
Quantum computation.
lecture notes, 1997
- [Wat97]
- J. Watrous.
On the power of 2-way quantum finite state automata.
Technical Report CS-TR-1997-1350, University of Wisconsin, Madison, April 1997.
- [WC98]
- C. P. Williams and S. H.
Clearwater.
Explorations in quantum computing.
TELOS division of Springer-Verlag, Santa Clara, CA, USA and New York, NY, USA,
1998.
Includes CD-ROM. (In Mathematik-Bibliothek).
- [Yao93]
- A. C.-C. Yao.
Quantum circuit complexity.
In Proc. 34th Annual Symp. on Foundations of Computer Science,
FOCS'93, pages 352-361. IEEE, 1993.
zurück zum
Inhaltsverzeichnis dieser Seite