helmut g. katzgraber
Proseminar in Theoretical Physics:
Quantum Computing

#### general information

 General information about the proseminar will be posted in this section. Be sure to check back periodically as most announcements will be made here. If you have any questions, please send us an email. The proseminar is mondays from 10:00 - 14:00 in the Pauli room (HPZ E9). News The topic distribution will take place December 14, 13:00h in the Pauli room (HPZ E9). The workshop on how to give a presentation will be Monday 18/02 from 10-12 and from 13-15 (1h lunch break). There are no more open slots for FS08. Sorry. On April 14 the Seminar will be in HPV G5. On March 17 the Seminar will be in HPT B71. No Seminar on April 07

#### supervisors

 Prof. Dr. Helmut Katzgraber HPZ E8 3 3580 Prof. Dr. Renato Renner HPZ G1 3 3458 Dr. Johan Aaberg HPZ XX 3 xxxx Dr. Mert Aybat HPZ G5 3 2565 Dr. Roger Colbeck HPZ F10.3 3 4768 Dr. Alejandro Daleo HPZ G12 3 6907 Dr. Oscar Dahlsten HPZ F10.3 3 4768 Dr. Wojciech De Roeck HPZ G6 3 2566 Fabian Hassler HPZ E8 3 3103 Sebastian Huber HPZ E8 3 3664 Dr. Stefan Hohenegger HPZ G11 3 2577 Dr. Christian Iniotakis HPZ G15 3 2575 Dr. Sergey Isakov HPZ E4 3 4209 Dr. Ingo Kirsch HPZ G16 3 2576 Dr. Evgeny Kozik HPZ E1 3 2562 Dr. Andrey Lebedev HPZ G8 3 3274 Dr. Jean-David Picon HPZ E3.2 3 2592 Dr. Lode Pollet HPZ E3.2 3 2592

#### timetable

 DATE TOPIC/SPEAKER ADVISOR 18/02 Workshop: How to give a scientific presentation Eva Buff Keller [Didaktikzentrum ETH Zurich] 25/02[HPV G5] Classical computing [slides] Katarina Gromova Mert Aybat 03/03 Factorization and applications (cryptography, RSA, ...) [slides] Mauro Calderara Ingo Kirsch 10/03 Computational models for quantum computing [slides] Pascal Steger Stefan Hohenegger 17/03 Simple algorithms (Deutsch, Deutsch-Josza, ...) [slides] Thomas Strub Andrey Lebedev 17/03 The Grover algorithm [slides] Raffaele Solca Alejandro Daleo 24/03 Easter no seminar 31/03 Quantum error correction [slides] Junji Shimagaki Jean-David Picon 31/03 Fault-tolerant quantum computing [slides] Ralph Chati Christian IniotakisJohan Aaberg 07/04 no seminar 14/04[HPV G5] Quantum Fourier transform [slides] Markus Schmassmann Oscar Dahlsten 14/04[HPV G5] Shor's algorithm [slides] Roger Herrigel Wojciech De Roeck 21/04 Introduction to topologically-protected quantum computing (Kitaev's model) [slides] Andreas Goelzer Sebastian Huber 21/04 Quantum computer implementations (traditional approaches, Ioffe proposal) [slides] Markus Baden Fabian Hassler 28/04 One-way quantum computing [slides] Gregor Seiler Evgeny Kosik 05/05[HPV G5] Communication complexity problems [slides] Yves Delley Lode Pollet 12/05 Pfingsten no seminar 19/05 Coin flipping [slides] Philippe Labouchere Roger Colbeck 26/05 Non-Abelian quantum computing (braids) [slides] Fabio Pedrocchi Sergey Isakov

 25/02 Classical computing: - Sections 3.1 and 3.2 of Nielsen and Chuang "Quantum Computation and Quantum Information", Cambridge University Press, 2000. - standard textbook: M. Sipser, Introduction to the Theory of Computation, Course Technology, 2005. 03/03 Factorization and applications: - original article proposing the RSA cryptosystem: R. Rivest, A. Shamir, and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Comm. of the ACM, vol. 21, pp. 120-126, 1978. - Chapter 8 of A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone, Handbook of Applied Cryptography, CRC Press, 1996. 10/03 Computational models for quantum computing: - original paper introducing the circuit model: D. Deutsch, Quantum computational networks, Proc. R. Soc. London A, vol 425, pp. 73-90, 1989. - research article on quantum Turing machines: P. Benioff, Models of quantum Turing machines, Fortsch. Phys., vol. 46, pp. 423-442, 1998. - research article on the relation between the circuit model and quantum Turing machines: A. Yao, Quantum circuit complexity, Proc. of the 34th Ann. Symp. on Found. of Comp. Sc. (FOCS), pp. 352-361, 1993. - Chapter 4 of Nielsen and Chuang, "Quantum Computation and Quantum Information", Cambridge University Press, 2000. 17/03: Simple algorithms part I: e.g., Deutsch and Deutsch-Jozsa algorithm not including Grover's algorithm - original article proposing the Deutsch-Jozsa algorithm: D. Deutsch and R. Jozsa, Rapid solutions of problems by quantum computation, Proc. R. Soc. London A, vol. 439, pp. 553-558, 1992. - Chapter 6 of P. Kaye, R. Laflamme, and M. Mosca, An Introduction to Quantum Computing, Oxford University Press, 2007. 17/03: Simple algorithms part II: Grover's algorithm - original article: L.K. Grover, Quantum mechanics helps in searching for a needle in a haystack, Phys. Rev. Lett., vol. 79, p. 325-328, 1997. - Chapter 8 of P. Kaye, R. Laflamme, and M. Mosca, An Introduction to Quantum Computing, Oxford University Press, 2007. 31/03 Quantum error correction: - original article proposing quantum error correction: P. Shor, Scheme for reducing decoherence in quantum computer memory, Phys. Rev. A, vol. 52 pp. R2493-R2496, 1995. - Chapter 7 (until Section 9) of J. Preskill's lecture notes, http://www.theory.caltech.edu/people/preskill/ph229/ - Chapter 10 (Section 1-5) of P. Kaye, R. Laflamme, and M. Mosca, An Introduction to Quantum Computing, Oxford University Press, 2007. 31/03 Fault-tolerant quantum computation: - original article proposing fault-tolerant quantum computation: P. W. Shor, Fault-tolerant quantum computation, in Proc. of the 37th Ann. Symp. on Found. of Comp. Sc. (FOCS), pp. 56-65, 1996. - Chapter 10 (Section 6) of P. Kaye, R. Laflamme, and M. Mosca, An Introduction to Quantum Computing, Oxford University Press, 2007. 07/04 Quantum Fourier transform: - original article: P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Journal on Computing, vol. 26, pp. 1484-1509. 1997. - Chapter 7 (Section 1) of P. Kaye, R. Laflamme, and M. Mosca, An Introduction to Quantum Computing, Oxford University Press, 2007. - Chapter 5 (Sections 1 and 2) of Nielsen and Chuang, "Quantum Computation and Quantum Information", Cambridge University Press, 2000. 07/04 Shor's algorithm: - original article: P.W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Journal on Computing, vol. 26, pp. 1484-1509. 1997. - Chapter 5 (Sections 3 and 4) of Nielsen and Chuang, "Quantum Computation and Quantum Information", Cambridge University Press, 2000. - Chapter 7 (Section 3) of P. Kaye, R. Laflamme, and M. Mosca, An Introduction to Quantum Computing, Oxford University Press, 2007. 14/04 Introduction to topologically-protected quantum computing: - A. Kitaev, "Anyons in an exactly solved model and beyond," arXiv:cond-mat/0506438 - J. Preskill's lecture notes, http://www.theory.caltech.edu/people/preskill/ph229/ - Freedman, M. H. and Kitaev, A. Y. and Larsen, M. J. and Wang, Z., Topological quantum computation, Bull. Amer. Math. Soc. 40, 31 (2002). - J. Preskill, Fault-tolerant quantum computation, quant-ph/9712048 21/04 Quantum computer implementations (traditional approaches, Ioffe proposal): - A. Kitaev, "Anyons in an exactly solved model and beyond," arXiv:cond-mat/0506438 - J. Preskill's lecture notes, http://www.theory.caltech.edu/people/preskill/ph229/ - Moessner, R. and Sondhi, S. L., Phys. Rev. Lett. 86, 1881 (2001) - Ralko, A. and Ferrero, M. and Becca, F. and Ivanov, D. and Mila, F., Phys. Rev. B 71, 224109 (2005) - Rokhsar, D. S. and Kivelson, S. A, Phys. Rev. Lett. 61, 2376 (1988). - Ioffe, L. B., Feigel'man, M. V., Ioselevich, A., Ivanov, D., Troyer, M. and Blatter, G., Nature 415, 503 (2002). - A. Fabricio Albuquerque, H. G. Katzgraber, Matthias Troyer, and Gianni Blatter, "Engineering exotic phases for topologically-protected quantum computation by emulating quantum dimer models", arXiv:cond-mat/0708.0191. 28/04 One-way quantum computing: - original article: R. Raussendorf and H. J. Briegel, A one-way quantum computer, Phys. Rev. Lett., vol. 86, pp. 5188-5191, 2001. - more detailed article: R. Raussendorf and H. J. Briegel, Computational model underlying the one-way quantum computer, Quant. Inform. Comput., vol. 2, pp. 344-386, 2002. 05/05 Quantum communication complexity: - (not so recent) survey article: G. Brassard, Quantum communication complexity (a survey), arXiv:quant-ph/0101005, 2001. - recent research article: D. Gavinsky, J. Kempe, I. Kerenidis, R. Raz, R. de Wolf, Exponential separations for one-way quantum communication complexity, with applications to cryptography, arXiv:quant-ph/0611209, 2006. 19/05 Coin flipping: (Literature provided by Roger Colbeck directly) 26/05 Non-Abelian quantum computing - A. Kitaev, "Anyons in an exactly solved model and beyond," arXiv:cond-mat/0506438 - J. Preskill's lecture notes (Chapter 9), http://www.theory.caltech.edu/people/preskill/ph229/ - Freedman, M. H. and Kitaev, A. Y. and Larsen, M. J. and Wang, Z., Topological quantum computation, Bull. Amer. Math. Soc. 40, 31 (2002). - Freedman, M. H. and Larsen, M. J. and Wang Z., Comm. Math. Phys. 227, 587 (2002). - Freedman, M. H., talk given at MSRI http://www.msri.org/communications/\\ln/msri/2000/qcomputing/freedman/1/index.html - N. Boesteel, L. Hormozi and G. Zikos, Phys. Rev. Lett. 95, 140503 (2006) - N. Bonesteel, talk given at KITP http://online.kitp.ucsb.edu/online/qubit06/bonesteel/