Informatyka kwantowaŚrednieZadanie nr 1192

Algorytm Grovera dla N = 4096 i M = 4 oznaczonych: optymalna liczba iteracji

Algorytm Grovera Przygotowanie do Olimpiady Kwantowej

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?

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

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
  1. \(\sin\theta=\sqrt{\frac{4}{4096}}=\sqrt{\frac{1}{1024}}=\frac{1}{32}\).
  2. Stąd \(\theta=\arcsin\frac{1}{32}\approx0{,}031255\) (prawie dokładnie \(\frac{1}{32}=0{,}03125\)).
  3. \(\frac{\pi}{4\theta}-\frac12\approx25{,}129-0{,}5=24{,}63\), więc najbliższą liczbą całkowitą jest 25.
  4. 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\).
  5. 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.

Więcej zadań z informatyki kwantowej →

Podobne zadania