Jakie jest matematyczne uzasadnienie „uniwersalności” uniwersalnego zestawu bram kwantowych (CNOT, H, Z, X i π / 8)?

W tej odpowiedzi wspomniałem, że bramki CNOT, H, X, Z i tworzą uniwersalny zestaw bramek, który podany w wystarczającej liczbie bramek może dowolnie zbliżyć się do replikacji dowolnej jednolitej bramki kwantowej (dowiedziałem się o tym fakt z wykładów EdX profesora Umesh Vazirani). Ale czy jest na to matematyczne uzasadnienie? Powinno być! Próbowałem znaleźć odpowiednie dokumenty, ale nie znalazłem wiele. $\pi/8$

quantum-gate universal-gates gate-synthesis

— Sanchayan Dutta
źródło

Odpowiedzi:

Wspomniana odpowiedź odwołuje się do książki Michaela Nielsena i Izaaka Chuanga, Quantum Computation and Quantum Information (Cambridge University Press), która zawiera dowód uniwersalności tych bram. (W moim wydaniu z 2000 r. Można to znaleźć na s. 194.) Kluczowym spostrzeżeniem jest to, że brama (lub brama ), wraz z bramką , generuje dwa różne obroty na kuli Blocha o kątach, które są irracjonalne wielokrotności . Pozwala to kombinacjom bramek i gęsto wypełniać powierzchnię kuli Blocha, a tym samym przybliżać dowolny jednokubitowy operator jednostkowy. $T$ $\pi/8$ $H$ $2\pi$ $T$ $H$

$\log(1/\epsilon)$ $\epsilon$

Łączenie bramek CNOT umożliwia przybliżenie dowolnych unitarnych wielu kubitów, jak wykazali Barenco i in. w Phys. Rev A 52 3457 (1995). (Przedruk tego artykułu można znaleźć na stronie https://arxiv.org/abs/quant-ph/9503016 .) Jest to również omówione w Nielsen i Chuang (s. 191 w wydaniu 2000).

— Brian R. La Cour
źródło

Jeszcze silniejszy wynik można uzyskać za pomocą Kliuchnikova, Maslowa i Moscy udowodnionych w Gilesie Selingerze .

— AHusain

$Z$ $X$
$\rm{CNOT}$ $H$ $T=\pi/8$

$H$ $T$
$\rm{CNOT}$ $\epsilon>0$ $\mathcal{O}(\log^2(1/\epsilon))$

$\epsilon=0$ $\pi/2$ $\frac{a+ib}{2^n} + \frac{c+id}{2^{n+1/2}}$

$\{{\rm{CCNOT}},H\}$ ${D(\theta)}$

— użytkownik1271772
źródło

CCNOT + H jest jednak uniwersalny w innym znaczeniu: jest uniwersalny obliczeniowo, ale nie może zrealizować żadnej bramki.

— Norbert Schuch

ϵ > 0

$\epsilon>0$

ϵ > 0

$\epsilon>0$

Nie. Z oczywistych powodów nie może zrealizować żadnej bramki o złożonych (= nierzeczywistych) współczynnikach. Jest obliczeniowo uniwersalny, tzn. Może działać na dowolnym q. obliczenia, ale nie dzieje się tak przez implementację wspomnianych bramek jeden na jeden, ale przez równoważną realizację. Więc jeśli chcesz zrealizować unitaries (co wydaje się być punktem pytanie), to nie to uniwersalny zestaw bramy.

— Norbert Schuch,

@NorbertSchuch: Przykładem obliczeń kwantowych jest symulacja złożonej jednostki. Więc jeśli CCNOT + H może wykonać dowolne q. obliczenia, czy nie da się dowolnie zbliżyć do symulacji jakiejkolwiek jednostki?

— user1271772

Zarówno CCNOT, jak i H mają tylko prawdziwe wpisy. NIE MA ŻADNEGO sposobu, aby uzyskać JAKĄKOLWIEK bramę ze złożonymi wpisami. --- Mówiąc bardziej ogólnie, istnieją (co najmniej) 3 pojęcia „symulacji”: Uzyskaj dowolną jednostkę, uzyskaj statystyki pomiaru komputera kwantowego lub rozwiąż problem BQP. CCNOT + H jest uniwersalny w drugim (i trzecim) sensie, ale nie w pierwszym.

— Norbert Schuch,