Informatyka kwantowaŚrednieZadanie nr 1192
Algorytm Grovera dla N = 4096 i M = 4 oznaczonych: optymalna liczba iteracji
Algorytm Grovera przeszukuje \(N=4096\) elementów, z których \(M=4\) jest oznaczonych. Startujemy od stanu równomiernej superpozycji. Po \(k\) iteracjach Grovera prawdopodobieństwo zmierzenia któregokolwiek z oznaczonych elementów wynosi \(P_k=\sin^2\big((2k+1)\theta\big)\), gdzie kąt \(\theta\in\left(0,\frac{\pi}{2}\right)\) spełnia \(\sin\theta=\sqrt{M/N}\).
Optymalną liczbą iteracji nazywamy liczbę całkowitą \(k\ge0\) najbliższą wartości \(\frac{\pi}{4\theta}-\frac12\) (dla niej kąt \((2k+1)\theta\) jest najbliższy \(\frac{\pi}{2}\)). Ile wynosi optymalna liczba iteracji?
Świetnie.
Jak rozwiązać to zadanie?
Potrzebujesz pomocy? Pokaż wskazówkę
Oblicz \(\sin\theta\). Dla tak małego kąta \(\theta\approx\sin\theta\); błąd tego przybliżenia jest dużo mniejszy niż odległość wyniku od najbliższej połówki.
Chcesz poznać sposób? Rozwiązanie krok po kroku
- \(\sin\theta=\sqrt{\frac{4}{4096}}=\sqrt{\frac{1}{1024}}=\frac{1}{32}\).
- Stąd \(\theta=\arcsin\frac{1}{32}\approx0{,}031255\) (prawie dokładnie \(\frac{1}{32}=0{,}03125\)).
- \(\frac{\pi}{4\theta}-\frac12\approx25{,}129-0{,}5=24{,}63\), więc najbliższą liczbą całkowitą jest 25.
- Sprawdzenie: \((2\cdot25+1)\theta=51\theta\approx1{,}594\), blisko \(\frac{\pi}{2}\approx1{,}571\), i \(P_{25}\approx0{,}9995\); dla \(k=24\) i \(k=26\) wychodzi odpowiednio ok. \(0{,}9985\) i \(0{,}9927\). Zgadza się to z oszacowaniem \(k\approx\frac{\pi}{4}\sqrt{N/M}=8\pi\approx25{,}1\).
- Odpowiedź: 25 iteracji.
Odpowiedź: \(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