Informatyka kwantowaŚrednieZadanie nr 1191
Obwód Deutscha–Jozsy dla funkcji spoza obietnicy: prawdopodobieństwo wyniku 111
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.
Świetnie.
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
- 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\).
- 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}\).
- 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\).
- Suma wynosi \(1+3+3-1=6\), więc \(a_{111}=\frac68=\frac34\), a prawdopodobieństwo to \(\left(\frac34\right)^2=\frac{9}{16}\).
- 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.
Podobne zadania
- Ile pomiarów, by przedział ±2σ dla ⟨Z⟩ ≈ 0,6 miał połowę szerokości 0,02
- QFT na ośmiu kubitach po kompilacji: liczba bramek CNOT razem z zamianami SWAP
- Mitygacja błędów odczytu dwóch kubitów macierzą pomyłek: ⟨Z⊗Z⟩ z 8000 pomiarów
- Ekstrapolacja Richardsona z czynników szumu 1, 3, 5: wartość przy zerowym szumie