Comment prouver / réfuter l'universalité d'un ensemble de portes?

Un ensemble universel de portes est capable d'imiter le fonctionnement de tout autre type de porte, avec suffisamment de portes. Par exemple, un ensemble universel de portes quantiques sont le Hadamard (   ), le déphasage (   ) et la porte . Comment pourrait-on réfuter ou prouver l'universalité d'un ensemble de portes telles que , , ou ?$H$$\pi/8$$T$$\mathrm{CNOT}$$\{H,T\}$$\{\mathrm{CNOT},T\}$$\{\mathrm{CNOT}, H\}$

L'universalité peut être une chose très subtile qui est assez difficile à prouver. Il existe généralement deux options pour le prouver:

• montrer directement, en utilisant les portes que vous avez choisies, comment construire n'importe quelle unité arbitraire de taille arbitraire (il n'y a pas de contrainte sur la taille de la construction, juste que cela peut être fait) avec une précision arbitraire (sur un sous-espace non trivial du Hilbert complet espace).

• montrer comment votre ensemble de portes choisi peut être utilisé pour recréer (avec une précision arbitraire) un ensemble universel existant.

Inversement, si vous souhaitez le réfuter, vous montrez que l'effet de votre ensemble de portes peut toujours être simulé par un modèle de calcul moindre (supposé), généralement un calcul classique.

Il existe quelques heuristiques que vous pouvez utiliser pour vous guider:

• vous devez avoir une porte multi-qubit dans votre ensemble. Si vous ne disposez que de portes à qubit unique, vous pouvez simuler chaque qubit indépendamment sur un ordinateur classique. Donc, si nous pensons que les ordinateurs quantiques sont plus puissants que les portes classiques à qubit unique, elles ne sont pas à elles seules universelles pour le calcul quantique. Cela exclut {H, T}.

• vous devez avoir une porte qui crée des superpositions. Cela exclut {CNOT, T}. Encore une fois, il s'agit d'un calcul classique avec l'ajout d'une phase globale non pertinente.

Bien sûr, ce ne sont pas des conditions suffisantes: l'ensemble {H, S, CNOT} peut également être simulé efficacement (voir le théorème de Gottesman-Knill). Cela doit également être vrai de {H, CNOT} car ils sont un sous-ensemble et donc les opérations qu'ils peuvent créer ne sont pas plus que celles de l'ensemble d'origine.

L'un des ensembles universels que je trouve les plus intéressants est {Toffoli, H} . Cela me semble toujours surprenant que cela soit suffisant (surtout quand on compare avec le set précédent). Notez qu'il n'implique aucun nombre complexe.

Il est également possible d'obtenir l'universalité à partir d'une seule porte à deux qubits telle que

$$\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 et Chuang, p. 191 de l'édition du 10e anniversaire:

Nous venons de montrer qu'une matrice unitaire arbitraire sur un espace de Hilbert dimensionnel peut être écrite comme un produit de matrices unitaires à deux niveaux. Nous montrons maintenant que les portes qubit unique et CNOT peuvent être utilisées ensemble pour implémenter une opération unitaire arbitraire à deux niveaux sur l'espace d'état de qubits. En combinant ces résultats, nous voyons que les portes à qubit unique et CNOT peuvent être utilisées pour implémenter une opération unitaire arbitraire sur qubits et sont donc universelles pour le calcul quantique.$d$$n$$n$

La première phrase contient un résultat accepté, vous devez donc simplement montrer que la combinaison de votre ensemble de portes peut implémenter "une opération unitaire arbitraire à deux niveaux". Pour citer Wikipedia:

Techniquement, cela est impossible car le nombre de portes quantiques possibles est indénombrable, tandis que le nombre de séquences finies d'un ensemble fini est dénombrable. Pour résoudre ce problème, nous demandons seulement que toute opération quantique puisse être approximée par une séquence de portes de cet ensemble fini.

Voir aussi cet article .