Algorytmy kwantowe 0800-ALGKW

http://fizyka.umk.pl/~milosz/WMon/index.htm

1. Klasyczne modele obliczeń i złożoność obliczeniowa
a. Maszyny Turinga
b. Klasyczne układy liczące, zupełne układy bramek
c. Złożoność obliczeniowa: klasy P i NP
d. Problemy decyzyjne a problemy obliczeniowe
e. Obliczenia probabilistyczne, klasa BPP (bounded error probabilistic polynomial time)
f. Przykład: faktoryzacja liczby
2. Klasyczne obliczenia odwracalne — bramki Fredkina i Toffoliego
3. Qubit
a. Przestrzeń stanów kwantowych
b. Reprezentacja stanów na sferze Blocha
c. Macierze Pauliego jako proste bramki kwantowe
d. Zupełny układ kwantowych bramek 1-qubitowych
e. Pomiar stanu qubitu
f. Twierdzenie o nieklonowaniu
4. Układy qubitów
a. Stany separowalne i splątane
b. Miara splątania
c. Bramki 2-qubitowe C-Not i C-U
d. Operacje n-qubitowe — kaskadowe konstrukcje sterujące i ich złożoność
e. Zupełność układu 1-qubitowych bramek kwantowych i C-Not
5. Komputer kwantowy w ujęciu R. Feynmana
6. Splątanie jako zasób obliczeniowy
a. Teleportacja
b. Gęste kodowanie
c. Problem Deutscha-Jozsy
7. Kwantowa transformata Fouriera i estymacja fazy
8. Algorytm faktoryzacji Shora
a. Klasyczny algorytm RSA — podstawy teorio-liczbowe
b. Wyznaczanie rzędu elementu w grupie metodami klasycznymi
c. Zastosowanie kwantowej estymacji fazy do wyznaczania rzędu
d. Złożoność kwantowego algorytmu Shora
9. Inne zastosowania kwantowej transformaty Fouriera
a. Określanie okresu funkcji
b. Dyskretne logarytmy
c. Problem ukrytej podgrupy jako prototypowy algorytm kwantowy
10. Algorytm wyszukiwania Grovera
11. Kwantowa korekcja błędów

Całkowity nakład pracy studenta

Godziny realizowane z udziałem nauczycieli (38 godz.): - udział w wykładach – 30 godz. - konsultacje z nauczycielem akademickim – 8 godz. Czas poświęcony na pracę indywidualną studenta (40 godz.): - przygotowanie do wykładu – 20 godz. - przygotowanie do egzaminu- 20 godz. Łącznie: 78 godz. (3 ECTS)

Efekty uczenia się - wiedza

W01: Ma pogłębioną wiedzę z matematyki przydatną do zaawansowanych aspektów informatyki. W02: Posiada rozszerzoną wiedzę w zakresie zaawansowanej konstrukcji i analizy algorytmów i metod optymalizacji. Przypisanie do kierunkowych efektów kształcenia: K_W01, K_W02 dla IS2, K_W01 dla Fizyki s2

Efekty uczenia się - umiejętności

U01: Potrafi efektywnie szukać niezbędnych informacji do rozwiązywania problemów informatycznych, posiada umiejętność samodzielnego wyszukiwania i wykorzystywania informacji z zakresu informatyki i powiązanych dziedzin. U02: Potrafi ocenić nowe technologie i ich potencjalne zastosowania. U03: Rozumie potrzebę uczenia się przez całe życie, potrafi inspirować proces uczenia się innych osób. Przypisanie do kierunkowych efektów kształcenia: K_U01, K_U05 dla IS2, K_U01, K_U02, K_U04, K_U11 dla Fizyki

Efekty uczenia się - kompetencje społeczne

K01: jest świadomy roli absolwenta kierunku informatyki stosowanej/fizyki, K02: posiada umiejętność dzielenia się swoją wiedzą i umiejętnościami przy wykorzystaniu nowoczesnych mediów upowszechniania wiedzy. K03: Potrafi przekazać informację o osiągnięciach informatyki/fizyki i różnych aspektach zawodu informatyka/fizyka w sposób powszechnie zrozumiały. Przypisanie do kierunkowych efektów kształcenia: K_K01, K_K05 dla IS2 K_K03 dla Fizyki

Metody dydaktyczne

wykład informacyjny (konwencjonalny)

Metody dydaktyczne podające

- wykład informacyjny (konwencjonalny)

Rodzaj przedmiotu

przedmiot fakultatywny

Wymagania wstępne

Elementy algebry liniowej i teorii macierzy, elementy rachunku prawdopodobieństwa, elementarna mechanika kwantowa.

Koordynatorzy przedmiotu

Miłosz Michalski

Kryteria oceniania

egzamin ustny – W01, W02, U01 – U03, K01 - K03

Kryteria oceniania:
Student losuje 3 pytania i po kilkuminutowym przygotowaniu omawia przy tablicy wylosowane zagadnienia. Materiał obejmuje zagadnienia omawiany na wykładzie, jak również wybrane zagadnienia z zalecanej literatury do przedmiotu. Odpowiedzi oceniane są wg następujących kryteriów:
- znajomość teoretycznych podstaw przedmiotu – 0-10 pkt
- zrozumienie omawianych zagadnień – 0-10 pkt
- znajomość literatury przedmiotowej 0-5 pkt.
Ocena ostateczna:
Ndst – 0-50% pkt.
Dst – 51-62% pkt.
Dst plus – 63-69% pkt.
Db – 70-81% pkt.
Db plus – 82-87% pkt
Bdb – 88-100% pkt.

Praktyki zawodowe

nie dotyczy

Literatura

M.A. Nielsen, I.L. Chuang, Quantum Computation & Quantum Information, Cambridge Univ. Press, 2000
M. Nakahara, T. Ohmi, Quantum Computing: From linear algebra to physical realizations, CRC Press 2008
M. Hirvensalo, Algorytmy Kwantowe, WSiP 2004

Więcej informacji

Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb:

Strona przedmiotu 0800-ALGKW w USOSweb