Quelle est la justification mathématique de «l'universalité» de l'ensemble universel de portes quantiques (CNOT, H, Z, X et π / 8)?

Dans cette réponse, j'ai mentionné que les portes CNOT, H, X, Z et forment un ensemble universel de portes, qui, en nombre suffisant de portes, peuvent se rapprocher arbitrairement de la réplication de toute porte quantique unitaire (j'ai appris cela fait des conférences EdX du professeur Umesh Vazirani). Mais y a-t-il une justification mathématique à cela? Il devrait y avoir! J'ai essayé de chercher des documents pertinents mais je n'ai pas trouvé grand-chose.$\pi/8$

La réponse que vous mentionnez fait référence au livre de Michael Nielsen et Isaac Chuang, Quantum Computation and Quantum Information (Cambridge University Press), qui contient une preuve de l'universalité de ces portes. (Dans mon édition 2000, cela se trouve à la p. 194.) L'idée clé est que la porte (ou porte π / 8 ), avec la porte H , génère deux rotations différentes sur la sphère Bloch avec des angles qui sont multiples irrationnels de 2 π . Cela permet à des combinaisons de portes T et H de remplir de manière dense la surface de la sphère de Bloch et d'approcher ainsi n'importe quel opérateur unitaire à un qubit.$T$$\pi/8$$H$$2\pi$$T$$H$

Le théorème de Solovay-Kitaev montre que cela peut être fait efficacement . Ici, "efficacement" signifie polynôme dans log ( 1 / ϵ ) , où ϵ est la précision souhaitée. Cela est également prouvé dans le livre de Nielsen et Chuang (annexe 3 dans l'édition 2000). Une construction explicite peut être trouvée dans https://arxiv.org/abs/quant-ph/0505030 .$\log(1/\epsilon)$$\epsilon$

La combinaison des portes CNOT permet d'approcher des unités arbitraires à plusieurs qubits, comme le montrent Barenco et al. dans Phys. Rev. A 52 3457 (1995). (Une préimpression de ce document peut être trouvée à https://arxiv.org/abs/quant-ph/9503016 .) Ceci est également discuté dans Nielsen et Chuang (p. 191 dans l'édition 2000).

Vous ne même pas besoin et X . C N O T , H et T = π / 8 suffisent.$Z$$X$
$\rm{CNOT}$$H$$T=\pi/8$

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

$\epsilon=0$$\pi/2$, il est toujours possible , si et seulement si les éléments de l'unité que vous souhaitez réaliser sont de la forme:$\frac{a+ib}{2^n} + \frac{c+id}{2^{n+1/2}}$, où toutes les variables sont des entiers. Remarquablement, au plus 1 qubit auxiliaire est requis pour cette synthèse exacte.

Un autre ensemble de portes universelles est $\{{\rm{CCNOT}},H\}$, and in fact there's a single gate that's uniersal: the 3-qubit Deutsch gate ${D(\theta)}$.