Restreindre les entrées d'opérateurs unitaires aux nombres réels et aux ensembles de portes universelles

10

Dans l'article fondateur de Bernstein et Vazirani "Théorie de la complexité quantique", ils montrent qu'une transformation unitaire en dimensions peut être efficacement approchée par un produit de ce qu'ils appellent des "rotations quasi-triviales" et des "décalages de phases quasi-triviaux".d

Les «rotations quasi triviales» sont des matrices unitaires dimensionnelles qui agissent comme l'identité sur toutes les dimensions sauf 2, mais agissent comme une rotation dans le plan couvert par ces deux dimensions (c'est-à-dire a une sous-matrice 2x2 de la forme:d

(cosθsinθsinθcosθ)

pour certains ).θ

Les "déphasages presque triviaux" sont des matrices unitaires dimensionnelles qui agissent comme l'identité sur toutes les dimensions sauf une, mais appliquent un facteur pour certains à cette seule dimension.deiθθ

De plus, ils montrent qu'un seul angle de rotation est nécessaire (pour les unités de rotation et de décalage de phase), étant donné que l'angle est un multiple irrationnel de (BV définit l'angle à .2π2πj=122j

Des articles ultérieurs sur la théorie de la complexité quantique (comme celui d'Adleman et al ou Fortnow et Rogers) affirment que le résultat BV implique que le calcul quantique universel peut être accompli avec des opérateurs unitaires dont les entrées sont dans .R

Comment cela se passe-t-il? Je peux comprendre qu'un produit de matrices de rotation quasi triviales vous donnera une matrice unitaire avec des entrées réelles, mais qu'en est-il des matrices de déphasage?

C'est-à-dire: si vous ne pouvez effectuer que des rotations presque triviales et des matrices de déphasage où les entrées de la matrice sont soit , pouvons-nous approximer efficacement toutes les autres matrices de déphasage?0,±1

Je soupçonne que cette implication n'est pas immédiatement évidente, et la preuve appropriée ressemblerait à la preuve que la porte de Toffoli de Deutsch est universelle - ou est-ce que je manque quelque chose de très évident?

Henry Yuen
la source

Réponses:

13

Il y a une preuve simple que Toffoli et Hadamard sont Quantum Universal par Dorit Aharonov qui montre d'abord comment des amplitudes complexes peuvent être simulées par des amplitudes réelles sur un espace Hilbert plus grand avec un qubit de plus.

"Cela se fait en ajoutant un qubit supplémentaire au circuit, dont l'état indique si l'état du système est dans la partie réelle ou imaginaire de l'espace Hilbert, et en remplaçant chaque porte complexe fonctionnant sur qubits par sa version réelle , notée , qui fonctionne sur les mêmes qubits plus le qubit supplémentaire. est défini par:UkU~kU~

U~|i|0=[Re(U)|i]|0+[Im(U)|i]|1
U~|i|1=[Im(U)|i]|0+[Re(U)|i]|1 "

Deuxièmement, elle prouve l'universalité de l'ensemble de portes {Hadamard, Toffoli}, qui n'a que des amplitudes réelles .{0,1,±12}

Martin Schwarz
la source
Merci Martin! Cependant, il me semble que la technique d'Aharonov pour remplacer les unitaires complexes par de véritables unitaires n'est pas la même que celle qu'Adleman / BV a envisagée (car je ne trouve aucune preuve qu'ils pensaient de cette façon). Mais le résultat d'Aharanov est intéressant et très agréable.
Henry Yuen
1
Je suis assez sûr qu'Adleman / BV a utilisé une construction qui a doublé le nombre de qubits plutôt que d'en ajouter un, mais cela a fonctionné de la même manière.
Peter Shor
@Peter: La construction de Rudolph et Grover fonctionne de cette façon, en utilisant deux rebits pour encoder un seul qubit: quant-ph / 0210187.
Joe Fitzsimons
9

En plus de l'article que Martin vous a montré, il y avait un article antérieur de Terry Rudolph et Lov Grover montrant qu'une porte à 2 rebits est universelle pour l'informatique quantique (voir quant-ph / 0210187 ). La porte a toutes les entrées réelles, et au cas où vous ne seriez pas au courant, les rebits sont des qubits où les amplitudes sont limitées aux nombres réels. Cela peut être à l'origine de la réclamation. La porte en question décrite dans l'article est une rotation Y contrôlée.

Il convient de noter qu'une telle porte Y contrôlée peut être créée à partir des rotations Y et des portes Z contrôlées comme suit: . Notez qu'une rotation Y est exactement le type de rotation décrit dans votre question, tandis que les portes Z contrôlées n'ont que des entrées +1 et -1.G(θ)=Y2(θ2)CZ12Y2(θ2)CZ12

Joe Fitzsimons
la source