Informatyka kwantowaŚrednieZadanie nr 1191

Obwód Deutscha–Jozsy dla funkcji spoza obietnicy: prawdopodobieństwo wyniku 111

Algorytm Deutscha–Jozsy Przygotowanie do Olimpiady Kwantowej

Obwód Deutscha–Jozsy dla trzech bitów: trzy kubity wejściowe w stanie \(|000\rangle\), kubit pomocniczy w stanie \(|1\rangle\); najpierw bramka Hadamarda na wszystkich czterech kubitach (\(H|0\rangle=\tfrac{1}{\sqrt2}(|0\rangle+|1\rangle)\), \(H|1\rangle=\tfrac{1}{\sqrt2}(|0\rangle-|1\rangle)\)), potem wyrocznia \(U_f|x\rangle|y\rangle=|x\rangle|y\oplus f(x)\rangle\), potem bramka \(H\) na trzech kubitach wejściowych i ich pomiar w bazie obliczeniowej.

Funkcja \(f:\{0,1\}^3\to\{0,1\}\) przyjmuje wartość 1 dokładnie dla trzech ciągów z jedną jedynką (001, 010, 100), a dla pozostałych pięciu ciągów wartość 0 — nie jest więc ani stała, ani zrównoważona (nie spełnia obietnicy algorytmu). Oblicz prawdopodobieństwo, że pomiar trzech kubitów wejściowych da wynik 111.

+10 pkt za pierwsze rozwiązanie na koncie

Zapis: ułamki (3/4), pierwiastki (2sqrt(3)), pi/6.

Jak rozwiązać to zadanie?

Potrzebujesz pomocy? Pokaż wskazówkę

Amplituda wyniku \(y\) po drugiej warstwie bramek Hadamarda wynosi \(\frac{1}{2^n}\sum_x(-1)^{f(x)+x\cdot y}\), gdzie \(x\cdot y\) to suma modulo 2 iloczynów odpowiadających sobie bitów. Dla \(y=111\) liczba \(x\cdot y\) to parzystość liczby jedynek w \(x\).

Chcesz poznać sposób? Rozwiązanie krok po kroku
  1. Kubit pomocniczy po bramce \(H\) jest w stanie \(|-\rangle\), więc wyrocznia działa jak \(|x\rangle\mapsto(-1)^{f(x)}|x\rangle\). Przed drugą warstwą bramek Hadamarda rejestr wejściowy jest w stanie \(\frac{1}{\sqrt8}\sum_x(-1)^{f(x)}|x\rangle\).
  2. Ponieważ \(H^{\otimes3}|x\rangle=\frac{1}{\sqrt8}\sum_y(-1)^{x\cdot y}|y\rangle\), amplituda wyniku \(y\) wynosi \(a_y=\frac18\sum_x(-1)^{f(x)+x\cdot y}\).
  3. Dla \(y=111\) mamy \(x\cdot y=\) parzystość liczby jedynek w \(x\). Sumujemy: \(x=000\): \(f=0\), parzystość 0, składnik \(+1\); trzy ciągi z jedną jedynką: \(f=1\), parzystość 1, składniki \((-1)^{2}=+1\), razem \(+3\); trzy ciągi z dwiema jedynkami: \(f=0\), parzystość 0, razem \(+3\); \(x=111\): \(f=0\), parzystość 1, składnik \(-1\).
  4. Suma wynosi \(1+3+3-1=6\), więc \(a_{111}=\frac68=\frac34\), a prawdopodobieństwo to \(\left(\frac34\right)^2=\frac{9}{16}\).
  5. Dla porównania \(a_{000}=\frac18(8-2\cdot3)=\frac14\), czyli wynik 000 („stała”) pojawia się tylko z prawdopodobieństwem \(\frac{1}{16}\). Odpowiedź: \(\frac{9}{16}\).

Odpowiedź: \(\frac{9}{16}\)

Czego warto się nauczyć?

Informatyka kwantowa to matematyka w działaniu: stan kubitu to wektor zespolony, bramka to macierz unitarna, a wynik pomiaru to prawdopodobieństwo z reguły Borna. Zadania prowadzą od polaryzacji światła do algorytmów, kryptografii i korekcji błędów.

Więcej zadań z informatyki kwantowej →

Podobne zadania