Décidabilité / algorithme pour vérifier l'universalité d'un ensemble de portes quantiques

Étant donné un ensemble fini de portes quantiques , est-il décidable (au sens théorique du calcul) si est un ensemble de portes universel? D'une part, "presque tous" les ensembles de portes sont universels, d'autre part, les ensembles de portes non universels ne sont toujours pas bien compris (en particulier, bien sûr, on ne sait pas si chaque ensemble de portes non universel est classiquement simulable) j'imagine donc que donner un algorithme explicite pour vérifier l'universalité pourrait être non trivial. $\mathcal{G} = \{G_1, \dots, G_n\}$ $\mathcal{G}$

quantum-computing Marcin Kotowski
la source

Pouvez-vous clarifier la question? La réponse de Joe suppose que vous avez un nombre fixe de qubits et que toutes les portes agissent sur ceux-ci, mais pour l'universalité, nous supposons souvent que les portes peuvent agir sur n'importe quel sous-ensemble de qubits. Par exemple, CNOT + toutes les portes à un qubit ne sont pas universelles si les portes à un qubit ne peuvent agir que sur le premier qubit, et CNOT est uniquement de qubit 1 à qubit 2. Dans ce dernier cas, nous pourrions vouloir extrapoler à de nombreux qubits pour obtenir l'universalité. Dans ce cas, je pense que la réponse peut être inconnue.

@DanielGottesman: Je suis d'accord sur les limites de ma réponse. En effet, je pense qu'il est indécidable dans ce dernier cas comme suit: Prenez un automate cellulaire sur un réseau infini de qubits et utilisez-le pour coder le problème d'arrêt (appelez cette mise à jour unitaire

). Ensuite, prenez un deuxième réseau avec un QCA universel (avec mise à jour

unitaire ). On peut définir un nouveau

unitaire

, où l'indice

U_{1}

$U_1$

U_{2}

$U_2$

C U_{2} = | 0 ⟩ ⟨ 0 |_{H} \otimes I + | 1 ⟩ ⟨ 1 | \otimes U_{2}

$CU_2 = |0\rangle\langle0|_H\otimes I + |1\rangle\langle1|\otimes U_2$

H

$H$ désigne un qubit qui est défini sur

ssi les premiers arrêts d'automates cellulaires.

| 1 ⟩

$|1\rangle$

Joe Fitzsimons

Ainsi la grille

est universelle si et seulement si la première machine de Turing s'arrête, et est donc indécidable.

C U_{2} \times U_{1}

$CU_2 \times U_1$

Joe Fitzsimons

Réponses:

Pour le cas des hamiltoniens, plutôt que des portes, la réponse est trivialement oui: vous énumérez simplement les éléments indépendants de l'algèbre de Lie. Puisque l'algèbre de Lie est un espace vectoriel avec l'ajout de l'opérateur de parenthèse de Lie. Puisque l'espace est fini, il a une base finie, et qui peut facilement être vérifié s'il est fermé ou ouvert dans le cadre de l'opération de parenthèse de Lie. La simple vérification de la parenthèse de Lie de toutes les paires d'opérateurs orthogonaux peut être effectuée en polynôme temporel dans la dimensionnalité de l'espace, et une base d'opérateur appropriée peut être trouvée par la méthode de Gram-Schmidt.

Pour les portes, vous n'avez pas vraiment la même option pour recourir immédiatement à des infinitésimaux, et vous devez construire des portes avec des valeurs propres irrationnelles afin de pouvoir arbitrairement bien approximer les générateurs infinitésimaux requis. Je suppose qu'il existe un moyen relativement simple de le faire, mais ce n'est pas immédiatement évident pour moi.

Dans tous les cas, prendre le journal des portes pour obtenir un ensemble d'opérateurs qui les génèrent une fois exponentiés et vérifier si ceux-ci ont généré l'algèbre de Lie complète fournirait un critère simple nécessaire mais pas suffisant pour l'universalité.

Joe Fitzsimons
la source

Pourquoi ne vérifier que les paires?

Alex 'qubeat'

@AlexV: Parce que le support Lie fonctionne sur 2 entrées. Chaque fois que vous produisez un nouvel opérateur linéairement indépendant, vous en produisez un orthogonal et répétez jusqu'à obtention de la fermeture.

Joe Fitzsimons

[\dots [H_{k}, H_{j}], H_{l}], \dots]

$[\ldots[H_k,H_j],H_l],\ldots]$

@AlexV: Vous n'en avez pas besoin. C'est un espace vectoriel, donc un vecteur est orthogonal à un sous-espace donné si et seulement s'il est orthogonal à une base pour ce sous-espace.

Joe Fitzsimons

Nous parlons probablement de différentes choses - de quel espace vectoriel vous parlez? Vous ne connaissez pas depuis le début la sous-algèbre générée par vos portes - vous devez la construire à partir d'hamiltoniens donnés pour vérifier si c'est toute l'algèbre de Lie.

Alex 'qubeat'