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$

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 π / 8 ), wraz z bramką H , generuje dwa różne obroty na kuli Blocha o kątach, które są irracjonalne wielokrotności 2 π . Pozwala to kombinacjom bramek T i H 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).

$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)}$