Informatyka kwantowaŚrednieZadanie nr 1194
Grover z restartami dla N = 8: minimalna oczekiwana liczba zapytań do wyroczni
W zbiorze \(N=8\) elementów jest dokładnie jeden oznaczony. Stosujemy strategię: (1) przygotuj równomierną superpozycję; (2) wykonaj \(k\) iteracji Grovera (każda zużywa jedno zapytanie do wyroczni); (3) zmierz rejestr; (4) sprawdź otrzymany element jednym dodatkowym zapytaniem do wyroczni — jeśli nie jest oznaczony, zacznij od nowa z tym samym \(k\).
Po \(k\) iteracjach pomiar daje element oznaczony z prawdopodobieństwem \(P_k=\sin^2\big((2k+1)\theta\big)\), gdzie \(\sin\theta=\frac{1}{\sqrt8}\); kolejne próby są niezależne. Liczbę \(k\ge0\) wybieramy raz, przed rozpoczęciem. Jaka jest najmniejsza (po wszystkich \(k\ge0\)) oczekiwana łączna liczba zapytań do wyroczni potrzebna do znalezienia elementu oznaczonego?
Świetnie.
Jak rozwiązać to zadanie?
Potrzebujesz pomocy? Pokaż wskazówkę
Liczba prób do pierwszego sukcesu ma rozkład geometryczny o średniej \(1/P_k\), a każda próba kosztuje \(k+1\) zapytań. Wyraź \(\sin((2k+1)\theta)\) przez \(\sin\theta\) (np. \(\sin3\theta=3\sin\theta-4\sin^3\theta\)) i porównaj kilka pierwszych \(k\); dla dużych \(k\) wystarczy oszacowanie \(P_k\le1\).
Chcesz poznać sposób? Rozwiązanie krok po kroku
- Próby są niezależne i każda kończy się sukcesem z prawdopodobieństwem \(P_k\), więc oczekiwana liczba prób to \(\frac{1}{P_k}\), a oczekiwana liczba zapytań \(E_k=\frac{k+1}{P_k}\).
- \(k=0\): \(P_0=\sin^2\theta=\frac18\), \(E_0=8\).
- \(k=1\): \(\sin3\theta=\sin\theta\,(3-4\sin^2\theta)=\frac52\sin\theta\), więc \(P_1=\frac{25}{4}\cdot\frac18=\frac{25}{32}\) i \(E_1=\frac{2}{25/32}=\frac{64}{25}=2{,}56\).
- \(k=2\): \(\sin5\theta=\sin\theta\,(5-20\sin^2\theta+16\sin^4\theta)=\frac{11}{4}\sin\theta\), więc \(P_2=\frac{121}{128}\) i \(E_2=\frac{3\cdot128}{121}=\frac{384}{121}\approx3{,}17\).
- Dla \(k\ge3\) mamy \(E_k=\frac{k+1}{P_k}\ge k+1\ge4>2{,}56\), bo \(P_k\le1\). Zatem minimum osiąga się dla \(k=1\): choć dwie iteracje dają większą szansę sukcesu, koszt kolejnego zapytania się nie opłaca.
- Odpowiedź: \(\frac{64}{25}\).
Odpowiedź: \(\frac{64}{25}\)
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