Obliczenia Klasyczne i Kwantowe
Institute of Mathematics
University of Wrocław
Pl. Grunwaldzki 2/4
50-384 Wrocław, Poland
e-mail: ivanov@math.uni.wroc.pl 
tel.: -48-71-375 74 05, fax.: -48-71-375 74 29 
http://www.math.uni.wroc.pl/`ivanov

Wykład, semestr letni




Wymagania: Algebra, Algebra liniowa

OPIS: Planuję przedstawić podstawy obliczeń klasycznych: maszyny Turinga, nierozstrzygalność, klasy złożoności. Rozpatrzymy konkretne przykłady klasy BPP, probabilistycznego odpowiednika klasy P. Algorytmy kwantowe są definiowane przez obwody kwantowe w pełnej analogii do obwodów logicznych. Listy 3 i 4 tworzą niezbędny wstęp do Listy 8. Listy 9 i 10 zawierają najważniejsze przykłady obliczeń kwantowych. Zbadamy miejsce kwantowych odpowiedników klas P i NP w ogólnej hierarchii klas złożoności (Lista 11). Poniższy program przewiduje 45 godzin wykładu. W r.a. 2015/16 program będzie skrócony do 30 g.


Program

  1. Lista 1 MASZYNY TURINGA I FUNKCJE REKURENCYJNE. NIEROZSTRZYGALNOŚĆ "pdf"

  2. Lista 2 KLASY ZŁOŻONOŚCI OBLICZENIOWEJ "pdf"

  3. Lista 3 OBWODY LOGICZNE I KLASA P/poly "pdf"

  4. Lista 4 PODSTAWY MECHANIKI KWANTOWEJ "pdf"

  5. Lista 5 PROTOKÓŁ BB84 "pdf"

  6. Lista 6 ZREDUKOWANY OPERATOR STANU "pdf"

  7. Lista 7 NIERÓWNOŚCI BELLA. SPLĄTANIE "pdf"

  8. Lista 8 OBWODY KWANTOWE I ZUPEŁNOŚĆ ZBIORÓW BRAMEK KWANTOWYCH "pdf"

  9. Lista 9 ALGORYTMY DEUTSCHA I SIMONA "pdf"

  10. Lista 10 ALGORYTM SHOR'A "pdf"

  11. M. Le Bellac, Rozdziały 5.7 - 5.9 "pdf"

  12. Lista 11 KLASY ZŁOŻONOŚCI BQP, BQNP "pdf"



Literatura:
  • M. Le Bellac, Wstęp do informatyki kwantowej, Warszawa, 2011
  • J.Gruska, Quantum Computing, McGraw-Hill, London, 1999
  • M.A.Nielsen, I.L.Chuang, Quantum Computation and Quantum Information, Cambridge University Press, 2000
  • A.Yu.Kitaev, A.H.Shen, M.N.Vyalyi, "Classical and Quantum Computations", AMS, Providence, Rhode Island, 2002.
  • S.W.Jablonski, "Matematyka Dyskretna", PWN, Warszawa
  • N.Koblitz, "Algebraiczne Aspekty Kryptografii"

Tematy na egzamin w r.2014: Algorytm Simona (ukryta podgrupa), Algorytm Kitaeva (okres funkcji), Realizacja kwantowej transformaty Fouriera, Algorytm Shora (okres funkcji).

IWANOW