Informatyka kwantowaŚrednieZadanie nr 1194

Grover z restartami dla N = 8: minimalna oczekiwana liczba zapytań do wyroczni

Algorytm Grovera Zadania konkursowePrzygotowanie do Olimpiady Kwantowej

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?

+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ę

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
  1. 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}\).
  2. \(k=0\): \(P_0=\sin^2\theta=\frac18\), \(E_0=8\).
  3. \(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\).
  4. \(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\).
  5. 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.
  6. 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.

Więcej zadań z informatyki kwantowej →

Podobne zadania