Zajęcia z Alg. Kwantowych

Przedmioty
#41

Ma Pan rację. W punkcie 4 opisu SARG04 słowo „losowa” powinno być zamienione na „odwrotna”.

Nie rozumiem tego, co Pan napisał w ogóle. W zadaniu chodzi o to, że Ewa przejmuje jeden z tych qubitów, które Alicja przesyła do Boba i dokonuje pomiaru. Nie ma żadnych „dodatkowych” qubitów. Nie rozumiem, czym jest „sukces” w Pana wypowiedzi, i nie rozumiem, do kogo odnosi się „Jej”.

#42

Załóżmy, że Alicja wysłała bit 0 w bazie pierwszej. Wtedy musiała wysłać o tym bicie informację 01 (0 w pierwszej oraz 1 w drugiej bazie).

  1. Żeby Bob mógł wydedukować wartość tego bitu, musiał zmierzyć qubit w bazie drugiej i otrzymać wynik 0.
  2. Jeśli laser wysłał n qubitów, Ewa może dokonać n-1 pomiarów, bo jeden qubit musi wysłać do Boba, aby uniknąć wykrycia.
  3. Ewa może poznać wartość qubitu tylko tak, jak Bob w punkcie 1 (nie ma dodatkowych informacji). Wobec tego ma n-1 prób, w których jeden pomiar musi być w drugiej bazie i dać wynik 0. Jednak nawet jeśli Ewa wie, że właśnie w drugiej bazie powinna mierzyć, prawdopodobieństwo otrzymania wyniku 0 to 1/2 (qubit jest w stanie bazowym pierwszej bazy). Wobec tego prawdopodobieństwo, że Ewa pozna wartość bitu to 1 - (1/2)^k, gdzie k to liczba pomiarów dokonanych w drugiej bazie.
  4. Z punktu 3. wynika, że im większe n, tym większe prawdopodobieństwo, że Ewa pozna wartość bitu.
    Treść zadania 9. nie rozróżnia pomiędzy różnymi wartościami n, o ile n>2, jednak z punktu 4. wynika, że np. dla n=5 Ewa ma większe szanse na poznanie wartości bitu niż n=4. Dlatego wydaje mi się, że źle rozumiem protokół, ale nie wiem, na czym polega mój błąd.

Czy w zadaniu 9. chodzi o obliczenie wartości oczekiwanej części klucza, którą przejmie Ewa?

#43

Aaaa. Bardzo mnie zmyliło, że napisał Pan, że mówi o zadaniu 5.

Faktycznie, jak układałem to zadanie, to wydawało mi się, że wystarczy dokonać dwóch pomiarów, a Pan ma rację, że trzeba dokonać czterech. Czyli powinny tam być wartości p_1, p_2,\dots,p_5. I w dziesiątym zadaniu też.

No i tak, oczywiście chodzi o wartość oczekiwaną.

#44

Czy jest możliwość, aby w zadaniu 2 dodać bramkę SWAP? Myślałem nad tym dość długo, nawet napisałem prostego bruta, ale nie udało się bez bramki SWAP znaleźć wyniku.

Chyba, że można korzystać z dodatkowych qubitów skoro jest bramka CCNOT?

#45

Można korzystać z dodatkowych bitów.
Sorry. Myślałem, że to już jest dla nas oczywiste.

EDIT: To zadanie nie ma być trudne ani sprytne. Ono ma na celu jedynie przećwiczenie budowania takiego obwodu, który odpowiada jakiejś arbitralnej macierzy.

#46

n = 4 to był tylko przykład. Ze wzoru, do którego doszedłem w punkcie trzecim wynika, że prawdopodobieństwo poznania wartości bitu przez Ewę jest ściśle rosnącą funkcją k, a więc i n.
Chodzi mi o to, że możliwość dokonania k+1 pomiarów zamiast k zawsze zwiększa pradopodobieństwo na poznanie wartości bitu, gdzie k jest dowolną liczbą całkowitą dodatnią.

1 polubienie
#47

Aaa. Słusznie. Bo nie wystarczy zmierzyć po 1 raz w każdej konfiguracji. To zadanie jest ciekawsze niż mi się wydawało :grin:

#48

Link dzisiaj ten sam. Zapraszam :slight_smile:

#49

Dziękuję bardzo za udział w ćwiczeniach.

Obiecałem napisać dokładniej, jak się robi ostatnie zadanie. W zasadzie jest tak, jak mówił Piotrek. Powiedzmy, że foton na banknocie jest w stanie |u\rangle \in \{|0\rangle, |1\rangle, |+\rangle, |-\rangle\}. My dokładamy sobie qubit c i stosujemy następującą procedurę:

c ← |0\rangle
Niech \varepsilon = \frac{\pi}{2N}. N razy powtarzamy:

  • Obracamy polaryzację c o kąt \varepsilon.
  • CNOT, gdzie c jest bitem kontrolnym, a u targetem.
  • Oddajemy u do weryfikacji.

Przeanalizujmy tę procedurę. Musimy rozważyć przypadki ze względu na |u\rangle.

  1. Jeśli |u\rangle = |+\rangle, CNOT za każdym razem zmienia |+\rangle na |+\rangle, więc po N rundach będziemy mieli stan |1\rangle\otimes|+\rangle.
  2. Jeśli |u\rangle = |0\rangle, bank dostaje do pomiaru drugi bit ze stanu \cos \varepsilon |00\rangle + \sin \varepsilon |11\rangle. Prawdopodobieństwo zmierzenia |1\rangle to \sin^2 \varepsilon < \varepsilon^2, a jeśli „bomba nie wybuchnie”, to stan zapada się za każdym razem do |00\rangle.
  3. Podobnie sytuacja się ma, jeśli |u\rangle = |0\rangle.
  4. Jeśli |u\rangle = |0\rangle (to jest najciekawszy przypadek), to wysyłamy do banku stan \cos\varepsilon |0\rangle |-\rangle - \sin\varepsilon |1\rangle |-\rangle (bo \mathsf{NOT}|-\rangle = -|-\rangle), czyli (\cos \varepsilon |0\rangle - \sin\varepsilon |1\rangle) \otimes |-\rangle. Bank mierzy w bazie Hadamarda, więc ze stanem nic się nie dzieje. No a czym jest \cos \varepsilon |0\rangle - \sin\varepsilon |1\rangle? Obrotem o -\varepsilon, więc jak zastosujemy obrót o \varepsilon to wrócimy do stanu |0\rangle|-\rangle.

Widzimy więc, że w trzech przypadkach ten bit kontrolny po N rundach komunikacji z bankiem będzie zerem, a w jednym jedynką. Potrzebujemy teraz analogicznych trzech algorytmów na odróżnienie pozostałych możliwych stanów |u\rangle.

Było też zadanie, które mi zryło banię, a niektórym nie. Tutaj jest wpis Scotta Aaronsona (https://www.scottaaronson.com/blog/?p=3975) wywołał on wiele różnych dyskusji (co widać po wpisaniu jego tytułu w Google’a).

Było też zadanie o kopiowaniu pieniędzy i liczbie 3/4. Pytanie na StackExchange, które doprowadziło do udowodnienia, że 3/4 jest najlepszym możliwym wynikiem jest tu: https://cstheory.stackexchange.com/questions/11363/rigorous-security-proof-for-wiesners-quantum-money

Tymczasem, zapraszam do oglądania kolejnego wykładu i rozwiązywania zadań.

#50

Jak dokładnie działa CNOT na kubitach?
Rozmiem, że CNOT działa na bitach tak, że dla pary (kontrolny, target) zwraca (kontrolny, target^kontrolny). Czy w tym wypadku po prostu mierzymy kubity w jakieś bazie (w jakiej?), wykonujemy CNOT, a potem emitujemy odpowiednie kubity?

#51

Broń Boże!

CNOT na qubitach jest liniową interpolacją CNOT-a na bitach. To znaczy na stanach bazowych działa tak, jak klasycznie, a na superpozycji (kombinacji liniowej) stanów bazowych zwraca taką samą kombinację liniową odpowiednich wyników.

#52

Wrzuciłem poprawioną listę zadań z drobną zmianą w zadaniu 11. Zadanie w poprzedniej wersji było poprawne, ale trochę mi nie pasowało do następnego wykładu.

#53

Jak to się ma do no-cloning theorem? Za pomocą CNOT-a można przeprowadzić kopiowanie bitów. Czy w takim razie za pomocą CNOT-a na qubitach można z jednego qubitu uzyskać dwa o takiej samej polaryzacji (kombinacji liniowej stanów bazowych, czyli rozkładzie prawdopodobieństwa na wynikach pomiaru w jakiejś bazie)?

EDIT:

na superpozycji (kombinacji liniowej) stanów bazowych zwraca taką samą kombinację liniową odpowiednich wyników.

Jak należy rozumieć kombinację liniową w tym kontekście? To jest po prostu kombinacja linowa rozkładów prawdopodobieństwa otrzymania odpowiednich wyników dla pomiaru czy odpowiednia polaryzacja? Tzn. qubit wynikowy rzeczywiście ma taką polaryzację, czy to tylko pewien rozkład prawdopodobieństwa na wynikach wynikający z rozkładu prawdopodobieństwa na wynikach przed CNOTem?

#54

Czy w zadaniu pierwszym z listy 4 nie powinno być Unambiguous-SAT, zamiast Unique-SAT? Z tego co znalazłem w internecie Unique-SAT to problem, w którym musimy określić czy istnieje dokładnie jedno wartościowanie spełniające daną formułę, natomiast tutaj mamy informację, że istnieje 1 albo żadne, co bardziej pasuje do definicji Unambiguous-SAT.

#55

@309671 O tym, jak się ma CNOT do No-cloning Theorem mówi zadanie 6 z listy 3 (omawialiśmy je na ostatnich ćwiczeniach). W szczególności

\mathsf{CNOT} (|-\rangle \otimes |0\rangle) = \frac{|00\rangle - |11\rangle}{\sqrt{2}} \neq \frac{|00\rangle - |01\rangle - |10\rangle + |11\rangle}{2} = |-\rangle \otimes |-\rangle.

Co do dalszej części pytania — musimy wrócić do definicji stanu kwantowego. Stan kwantowy jest (jak pamiętamy z wykładu pierwszego) superpozycją, czyli kombinacją liniową, stanów kwantowych (taką szczególną kombinacją liniową, której norma {\|\cdot\|}_2 jest równa 1). Jak mamy jakąś operację liniową, która jest zdefiniowana na stanach bazowych, to wiemy, jak ją stosować na dowolnym stanie.

@309016 Faktycznie, na Wikipedii on się nazywa Unambiguous SAT. Może dlatego miałem takie trudności ze znalezieniem dobrych notatek o tym twierdzeniu. :rofl:

#56

Czy w zadaniu 2 nie powinno być B=\{x | f(x) = 0\} zamiast B = \{ x| f(x)=1\}?

1 polubienie
#57

Dziękuję, wydaje mi się, że rozumiem.

1 polubienie
#58

Czy w zadaniach 5-6 mogę założyć, że mam możliwość weryfikowania, czy dany element należy do zbioru A za pomocą jednego zapytania?

EDIT: Jeśli nie mogę tego założyć, to czy algorytmy mogą z pewnym prawdopodobieństwem zwrócić element nienależący do A?

#59

Tak. Powiedzmy, że tak naprawdę mamy dostęp do obwodu f^\text{flip}, który umiemy przerobić na O^\pm_f.

#60

Wnioskując z zadań 3, 4:
Czy nie powinno być \alpha_t = sin(\theta_t),\, \beta_t = cos(\theta_t) ?

1 polubienie