Informatyka kwantowaŚrednieZadanie nr 1225

QFT na ośmiu kubitach po kompilacji: liczba bramek CNOT razem z zamianami SWAP

Oprogramowanie i kompilacja obwodów Przygotowanie do Olimpiady Kwantowej

Standardowy obwód kwantowej transformaty Fouriera na \(n\) kubitach \(q_1,\dots,q_n\) wygląda tak: dla \(k=1,2,\dots,n\) wykonujemy bramkę \(H\) na \(q_k\), a potem kontrolowane bramki fazowe (kontrola na \(q_j\), cel \(q_k\)) dla każdego \(j>k\); na końcu odwracamy kolejność kubitów bramkami SWAP (\(q_1\leftrightarrow q_n\), \(q_2\leftrightarrow q_{n-1}\), …).

Kompilator rozkłada każdą kontrolowaną bramkę fazową na 2 bramki CNOT i 3 bramki jednokubitowe, a każdą bramkę SWAP na 3 bramki CNOT. Ile bramek CNOT zawiera skompilowany obwód QFT dla \(n=8\)?

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

Policz osobno kontrolowane bramki fazowe (ile jest par \(j>k\)?) i bramki SWAP (ile par kubitów trzeba zamienić?).

Chcesz poznać sposób? Rozwiązanie krok po kroku
  1. Kubit \(q_k\) jest celem \(n-k\) bramek kontrolowanych, więc ich łączna liczba to \(\sum_{k=1}^{n}(n-k)=\frac{n(n-1)}{2}=\frac{8\cdot7}{2}=28\).
  2. Daje to \(2\cdot28=56\) bramek CNOT.
  3. Odwrócenie kolejności ośmiu kubitów wymaga \(\lfloor n/2\rfloor=4\) bramek SWAP, czyli \(4\cdot3=12\) bramek CNOT.
  4. Razem \(56+12=68\) bramek CNOT (oraz \(8+3\cdot28=92\) bramek jednokubitowych).

Odpowiedź: \(68\)

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