Seminarium: Efekty kwantowe w informatyce

---

Poniewaz najbardziej fundamentalne teorie fizyki podlegaja prawom mechaniki kwantowej to naturalne sie wydaje, aby najbardziej podstawowe teorie obliczeniowe takze uwzglednialy te prawa. Motywacja ta stala sie podstawa nowego dzialu informatyki: kwantowej teorii informacji, kryptografii i obliczen. Dział ten ma na swoim koncie kilka spektakularnych sukcesow m.in. mozliwosc faktoryzacji liczb pierwszych w wielomianowym czasie oraz protokol Key Distribution calkowicie odporny na podsluchiwanie. Seminarium poswiecone bedzie wprowadzeniu do tego dzialu oraz przedstawieniu najwazniejszych wynikow.

Staly termin seminarium: piatek 12:15 sala 105
Termin dodatkowy: czwartek 16:15 sala 4

---

Informacje:

• Seminarium rozpocznie sie dwoma wykladami wygloszonymi przez prowadzacego, bedacymi wprowadzeniem w tematyke. Nie wymaga sie zadnych szczegolnych wiadomosci na wstepie. Jednakze na pewno ulatwieniem bedzie znajomosc podstaw algebry liniowej oraz fizyki na poziomie szkoly sredniej. Takze znajomosc podstawowych konceptow zlozonosci obliczeniowej i kryptografii pomoze w lepszym zrozumieniu kontekstu niektorych zagadnien.
• Uwaga: Spotkania 27 kwietnia i 4 maja sie NIE odbeda, gdyz w pierwszym z tych terminow wyjezdzam, a drugi jest dniem rektorskim.

---

Materialy:

Internet

• Wyklady Umesha Vaziraniego (bardzo dobry - prezentowany z punktu widzenia informatykow)
• Wyklady Johna Preskilla (doskonaly i wyczerpujacy, ale material jest prezentowany z bardziej fizycznego punktu widzenia)
• Opis notacja Diraca autorstwa Stanislawa Kryszewskiego (krotkie i jasne wyjasnienie notacji Diraca)

Slajdy

• Wyklad pierwszy
• Wyklad drugi (poprawiony)

---

Tematy wystapien:

Pierwsze dwa wyklady - prowadzacy

• Wprowadzenie historyczne
• Model: qubity, pomiary w mechanice kwantowej, ewolucje unitarne, kwantowe bramki logiczne, notacja Diraca
• Fenomeny: splatanie, nierownosci Bella, supergeste kodowanie, teleportacja (wstep)

Tematy do opracowania przez studentow (literatura zostanie podana w najblizszym czasie):

1. transformata Fouriera w ujeciu kwantowym - wielomianowy kwantowy algorytm faktoryzacji liczb pierwszych, znajdowania logarytmu dyskretnego oraz ukrytej podgrupy (Maciej Sobczak Slajdy)
2. szybkie przeszukiwanie baz danych (Maciej Koch-Janusz - slajdy wkrotce)
3. obliczenia kwantowe, a zlozonosc obliczeniowa (Piotr Gogol Slajdy)
4. elementy kwantowej teorii informacji (Przemyslaw Uznanski)
5. kwantowe kody korekcyjne (Patryk Obara Slajdy + Jan Dudulski Slajdy)
6. podejscia do realizacji modelu obliczen kwantowych (Krzysztof Drys + Pawel Laskos-Grabowski - Slajdy)
7. wprowadzenie do kwantowej kryptografii, protokol Quantum Key Distribution BB84 (Grzegorz Byrka + Jakub Michaliszyn Slajdy)
8. kwantowe implementacje kryptograficznych prymitywow: kwantowe zobowiazanie bitowe; kwantowy Oblivious transfer; Oblivious Transfer, a kwantowe zobowiazanie bitowe (Michal Staskiewicz)
9. kwantowe spacery w grafie, rzucanie moneta (Bartosz Kalinczuk)
10. kwantowe automaty skonczone (Krzysztof Skrzetnicki)

---