Qual é a justificativa matemática para a "universalidade" do conjunto universal de portas quânticas (CNOT, H, Z, X e π / 8)?

Em esta resposta que mencionado que o CNOT, H, X, Z e portas formar um conjunto universal de portas, que dada em número suficiente de portas pode obter arbitrariamente perto de replicar qualquer portão quântico unitária (vim a saber sobre esta fato das palestras EdX do professor Umesh Vazirani). Mas, existe alguma justificativa matemática para isso? Deve haver! Tentei procurar documentos relevantes, mas não consegui encontrar muita coisa.$\pi/8$

A resposta que você menciona faz referência ao livro de Michael Nielsen e Isaac Chuang, Quantum Computation and Quantum Information (Cambridge University Press), que contém uma prova da universalidade desses portões. (Na minha edição de 2000, isso pode ser encontrado na pág. 194.) O insight principal é que o portão (ou portão π / 8 ), junto com o $T$$\pi/8$$H$ portão , gera duas rotações diferentes na esfera de Bloch com ângulos que são múltiplos irracionais de . Isso permite combinações de T e $2\pi$$T$$H$ portas preencham densamente a superfície da esfera de Bloch e, assim, se aproximem de qualquer operador unitário de um qubit.

Que isso pode ser feito com eficiência é mostrado pelo teorema de Solovay-Kitaev . Aqui, "eficientemente" significa polinômio no , onde ϵ é a precisão desejada. Isso também é comprovado no livro de Nielsen e Chuang (apêndice 3 na edição de 2000). Uma construção explícita pode ser encontrada em https://arxiv.org/abs/quant-ph/0505030 .$\log(1/\epsilon)$$\epsilon$

A combinação de portões CNOT permite aproximar unidades arbitrárias de vários qubit, como mostrado por Barenco et al. em Phys. Rev. A 52 3457 (1995). (Uma pré-impressão deste artigo pode ser encontrada em https://arxiv.org/abs/quant-ph/9503016 .) Isso também é discutido em Nielsen e Chuang (p. 191 na edição de 2000).

Você não precisa mesmo de e X . C N O T , H e T = π / 8 são suficientes.$Z$$X$
$\rm{CNOT}$$H$$T=\pi/8$

1) e T são suficientes para fazer qualquer transformação unitária possível em um qubit. 2) Adicionando C N O T , você pode sintetizar uma transformação unitária geral em qualquer erro ϵ > 0 usando apenas portas O ( log 2 ( 1 / ϵ ) ) .$H$$T$
$\rm{CNOT}$$\epsilon>0$$\mathcal{O}(\log^2(1/\epsilon))$

Se você deseja que o erro seja e só deseja adicionar a porta de fase π / 2 , ainda é possível , se e somente se os elementos da unidade que você deseja criar forem da forma: a + $\epsilon=0$$\pi/2$$\frac{a+ib}{2^n} + \frac{c+id}{2^{n+1/2}}$

Outro conjunto de portão universal é $\{{\rm{CCNOT}},H\}$ ${D(\theta)}$ .