Algorytmy kwantowe

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

przedmiot fakultatywny

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)

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

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

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

wykład informacyjny (konwencjonalny)

- wykład informacyjny (konwencjonalny)

Wykład wprowadza zagadnienie reprezentacji informacji na poziomie kwantowym i omawia podstawowe algorytmy kwantowe oraz analizę ich złożoności obliczeniowej w porównaniu z odpowiednikami klasycznymi.

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

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

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.

nie dotyczy