Jak udowodnić / obalić uniwersalność dla zestawu bram?

Uniwersalny zestaw bram jest w stanie naśladować działanie dowolnego innego typu bramy, pod warunkiem wystarczającej liczby bram. Na przykład uniwersalnym zestawem bramek kwantowych są Hadamard (  $H$  ), przesunięcie fazowe $\pi/8$ (  $T$  ) i bramka $\mathrm{CNOT}$Jak obalić lub udowodnić uniwersalność zestawu bram, takich jak $\{H,T\}$ , $\{\mathrm{CNOT},T\}$ lub $\{\mathrm{CNOT}, H\}$ ?

Uniwersalność może być bardzo subtelną rzeczą, którą trudno jest udowodnić. Zazwyczaj istnieją dwie opcje, aby to udowodnić:

• pokaż bezpośrednio, korzystając z wybranych bram, jak skonstruować dowolną jednostkę o dowolnym rozmiarze (nie ma ograniczenia co do wielkości konstrukcji, wystarczy, że można to zrobić) z dowolną dokładnością (w jakiejś nietrywialnej podprzestrzeni pełnej Hilberta przestrzeń).

• pokaż, jak wybrany zestaw bramek można wykorzystać do odtworzenia (z dowolną dokładnością) istniejącego zestawu uniwersalnego.

I odwrotnie, jeśli chcesz to obalić, pokazujesz, że efekt twojego zestawu bramek zawsze może być symulowany przez (zakładany) mniejszy model obliczeń, zwykle obliczenia klasyczne.

Istnieje kilka heurystyk, których można użyć jako wskazówek:

• musisz mieć bramę z wieloma kubitami w swoim zestawie. Jeśli masz tylko pojedyncze kubity, możesz symulować każdy kubit niezależnie na klasycznym komputerze. Jeśli więc uważamy, że komputery kwantowe są potężniejsze niż klasyczne, same pojedyncze kubitowe bramki nie są uniwersalne do obliczeń kwantowych. To wyklucza {H, T}.

• musisz mieć bramę, która tworzy superpozycje. To wyklucza {CNOT, T}. Ponownie jest to klasyczne obliczenie z dodaniem nieistotnej fazy globalnej.

Oczywiście nie są to wystarczające warunki: zbiór {H, S, CNOT} można również skutecznie symulować (patrz twierdzenie Gottesmana-Knilla). Musi to również dotyczyć {H, CNOT}, ponieważ są one podzbiorem, więc operacje, które mogą utworzyć, nie są niczym więcej niż operacje z oryginalnego zestawu.

Jednym z uniwersalnych zestawów, które uważam za najbardziej interesujące, jest {Toffoli, H} . Zawsze wydaje mi się zaskakujące, że to wystarczy (zwłaszcza w porównaniu z poprzednim zestawem). Zauważ, że nie obejmuje żadnych liczb zespolonych.

$$\left(\begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \\ 0 & 0 & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \end{array}\right)$$

Nielsen i Chuang, str. 191 10. edycji jubileuszowej:

$d$$n$$n$

Pierwsze zdanie jest wynikiem akceptowanym, więc musisz po prostu pokazać, że kombinacja zestawu bramek może realizować „dowolną dwupoziomową operację jednostkową”. Cytując Wikipedię:

Technicznie jest to niemożliwe, ponieważ liczba możliwych bram kwantowych jest niepoliczalna, podczas gdy liczba skończonych sekwencji ze zbioru skończonego jest policzalna. Aby rozwiązać ten problem, wymagamy jedynie, aby każda operacja kwantowa mogła być aproksymowana przez sekwencję bramek z tego skończonego zbioru.

Zobacz także ten artykuł .