Pewnie wszyscy bardzo nerwowo już oczekują na materiały na przyszły tydzień. A więc są!
Czy w zadaniu 9 nie brakuje jakiegoś warunku (np. liczby pierwsze są duże)? Sprawdziłem, że dla małych liczb pierwszych teza niekoniecznie zachodzi, np. dla 3 i 7 (ogólnie dla 3 i dowolnej liczby pierwszej postaci p = 4k + 3 teza nie zachodzi). Wydaje mi się, że powinien być dodatkowy warunek postaci np. p, q \geq 10.
Ok, umówmy się, że losujemy tylko takie reszty z N, które są z nią względnie pierwsze. Jak trafimy w resztę dzielącą się przez p albo q to mieliśmy mega farta i rozłożyliśmy N.
Miałbym pytanie do wykładu piątego. W okolicach 32 minuty mamy zdefiniowany stan kwantowy |\psi>, który podstawiamy do H^n*|\psi> i w tym podstawieniu, pojawia się 1/\sqrt{N} moje pytanie brzmi skąd bierze się ten pierwiastek? Jeśli zakładamy, że stan |\psi> jest poprawny, czyli kwadraty modułów sumują się do jedynki to nie ma potrzeby normalizacji go dodatkowo po podstawieniu, a macierz bramki Hadamarda jest jeszcze nie rozpisana, więc nie może być częścią tego przekształcenia.
Edycja0: W wykładzie szóstym wyprowadzamy bazę funkcji \chi i dochodzimy do wniosku, że dla Z_n bazę będą generowały kolejne pierwiastki n-tego stopnia z jedynki. Jak ma się więc to do tego, co robiliśmy na wykładzie piątym, gdzie funkcje \chi_s przyjmowały wektor \{0,1\}^n i zwracały wartość -1 lub 1? Można przecież próbować traktować \{0,1\}^n jako liczby z Z_n.
Edycja1: Czy w zadaniu 2 z listy 7 przyjmujemy (tak jak na wykładzie), że w okresie znajduje się dokładnie jeden element danego koloru?
Dziękuję za pytania!
Z błędu wykładowcy. 
Jak wyjaśniamy w tym wykładzie, Transformata Fouriera służy do analizowania funkcji, których argumentem są elementy jakiejś grupy G (a wynikiem liczby zespolone). To, jakie będą funkcje bazowe tej transformaty zależy od tego, jaka jest ta grupa. Z jakiegoś powodu te funkcje bazowe zawsze się nazywają \chi, ale są różne w zależności od tego, jakie funkcje badamy. Ja znam trzy takie użyteczne transformaty: dla funkcji Boole’owskich (czyli grupa to \{0, 1\}^n z operacją XOR), DFT (czyli grupa Z_N) i Ciągła Transformata Fouriera (która jest bardzo ważna w zasadzie całym świecie poza informatyką, szczególnie w analizowaniu fal, bo te funkcje bazowe to dowolnie przesunięte i zagęszczone sinusy).
Na tym wykładzie pokazaliśmy, że wybór tych funkcji bazowych nie jest przypadkowy, tylko są to funkcje posiadające określoną własność (na marginesie: o to, czemu te funkcje bazowe są akurat takie pytałem kiedyś, podczas jego wykładu, obecnego kandydata na rektora Uniwersytetu Warszawskiego i nie uzyskałem przekonującej odpowiedzi).
Tak!
Zapraszam na ćwiczenia!
Aby zapisać się na egzamin trzeba kliknąć w ten link:
https://calendar.google.com/calendar/selfsched?sstoken=UU1LUE1XUHR4aTRCfGRlZmF1bHR8NjQxM2U3Zjg5ZjY5MjJjNmExN2RkZmI1M2MzOGNjYzc
Jeśli komuś żaden termin nie będzie pasował, proszę o e-mail, będziemy się jakoś dogadywać.
Spotkania są krótkie, dlatego zależy mi na tym, aby każdy był przed spotkaniem technicznie przygotowany (żeby nie tracić czasu na „halo halo, słyszymy się?”). To znaczy, muszę widzieć jego gębę oraz musi mi być w stanie pokazywać, co akurat pisze i rysuje (można to zrealizować np. za pomocą smartfona i kartki — jak to robiłem z wykładami; albo jakimś narzędziem typu tablica online; albo jakimś e-rysikiem; …). Proszę mieć to wcześniej przetestowane.
Poza tym, wrzuciłem na Youtube’a ósmy wykład:
1 polubienie
Mam pytanie do problemu Simona nad \mathbb{Z}_n. Na liście 7. zakładamy, że z obwodu kwantowego dostajemy wielokrotności \frac{N}{s} ze zbliżonymi prawdopodobieństwami. W zadaniu 1. mówiliśmy, że z dużym pradopodobieństwem wystarczą nam dwie takie liczby, aby otrzymać s.
Jednak na wyjściu obwodu mamy k * \frac{N}{s} + x, gdzie x zależy od koloru. Na wykładzie pokazał Pan, że to x w zasadzie nie nic nie zmienia. Rozumiem jednak, że tak jest tylko dla ustalonego koloru (gdy x jest stałe). Z tego wynika, że aby otrzymać dwie wielokrotności \frac{N}{s} w musimy otrzymać dwa razy ten sam kolor z funkcji f, czyli trzeba wykonać nieco więcej (pesymistycznie \frac{N}{s}) zapytań do funkcji f.
Czy powyższe rozumowanie jest poprawne? Jeżeli tak, to rozumiem, że algorytm do period finding jest wolniejszy o czynnik zależny od liczby różnych wyjść f związany z tym, że w algorytmie potrzebujemy wyników dla tych samych kolorów.
EDIT: Prześledziłem ponownie wykład i już zrozumiałem błąd.