Jones Polynomial

12

Il existe de nombreux algorithmes quantiques assez standard qui peuvent tous être compris dans un cadre très similaire, à partir du problème de Simon de l'algorithme de Deutsch, de la recherche de Grover, de l'algorithme de Shor, etc.

Un algorithme qui semble être complètement différent est l'algorithme d'évaluation du polynôme de Jones . De plus, il semble que ce soit un algorithme crucial à comprendre en ce sens qu'il s'agit d'un problème complet BQP : il présente toute la puissance d'un ordinateur quantique. De plus, pour une variante du problème, c'est DQC-1 complet , c'est-à-dire qu'il présente la pleine puissance d' un qubit propre .

Le papier de l'algorithme Jones Polynomial présente l'algorithme d'une manière très différente des autres algorithmes quantiques. Y a-t-il une manière plus similaire / familière que je peux comprendre l'algorithme (en particulier, le unitaire Udans la variante DQC-1, ou tout simplement le circuit entier dans la variante complète BQP)?

DaftWullie
la source

Réponses:

5

Cette réponse est plus ou moins un résumé du document Aharonov-Jones-Landau auquel vous avez lié, mais avec tout ce qui n'est pas directement lié à la définition de l'algorithme supprimé. J'espère que cela est utile.

L'algorithme Aharonov-Jones-Landau se rapproche du polynôme de Jones de la fermeture plate d'une tresse à une k ème racine d'unité en le réalisant comme (une certaine mise à l'échelle de) un élément de matrice d'une certaine matrice unitaire U σ , l'image de σ sous une certaine représentation unitaire du groupe de tresses B 2 n . Étant donné une implémentation de U σ en tant que circuit quantique, l'approximation de ses éléments de matrice est simple à l'aide du test de Hadamard . La partie non triviale est approximativement U σ comme un circuit quantique.σkUσσB2nUσUσ

Si est une tresse sur 2 n brins avec m croisements, on peut écrire σ = σ ϵ 1 a 1 σ ϵ 2 a 2 , ϵ m{ ± 1 } , et σ i est le générateur de B 2 n qui correspond à traversant le i ème brin sur le (σ2nm , où a 1 , a 2 , , a m{ 1 , 2 , , 2 n - 1 } , ϵ 1 , ϵ 2 ,σ=σune1ϵ1σune2ϵ2σunemϵmune1,une2,,unem{1,2,,2n-1} i + 1 ) st. Il suffit de décrire U σ i , puisque U σ = U ϵ 1 σ a 1U ϵ m σ a m .ϵ1,ϵ2,,ϵm{±1}σjeB2nje(je+1)UσjeUσ=Uσune1ϵ1Uσunemϵm

Pour définir , nous donnons d'abord un certain sous-ensemble de la base standard de C 2 2 n sur laquelle U σ i agit de manière non triviale. Pour ψ = | b 1 b 2b 2 n , laisser i ' ( ψ ) = 1 + Σ i ' j = 1 ( - 1 ) 1 - b j . Appelons ψUσjeC22nUσjeψ=|b1b2b2ni(ψ)=1+j=1i(1)1bjψ admissible si pour tout i { 1 , 2 , , 2 n } . (Cela correspond à ψ décrivant un chemin de longueur 2 n sur le graphe G k défini dans l'article AJL.) Soit λ r = { sin ( π r / k ) si  1 r 1i(ψ)k1i{1,2,,2n}ψ2nGkSoitA=ie-πi/2k(ceci est mal tapé dans l'article AJL; notez également qu'ici et seulement ici,i=

λr={péché(πr/k)si 1rk-1,0autrement.
UNE=jee-πje/2k n'est pas l'indicei). Écrivezψ=| ψibib i + 1, oùψiest les premiersi-1bits deψ, et soitzi= i - 1 (ψi). Alors U σ i ( | ψ i 00 )je=-1jeψ=|ψjebjebje+1ψjeje-1ψzje=je-1(ψje) On définitU σ i (ψ)=ψpour les éléments de base non admissiblesψ.
Uσje(|ψje00)=UNE-1|ψje00Uσje(|ψje01)=(UNEλzje-1λzje+UNE-1)|ψje01+UNEλzje+1λzje-1λzje|ψjedixUσje(|ψjedix)=UNEλzje+1λzje-1λzje|ψje01+(UNEλzje+1λzje+UNE-1)|ψjedixUσje(|ψje11)=UNE-1|ψje11
Uσje(ψ)=ψψ

Nous voudrions maintenant décrire comme un circuit quantique avec de nombreuses portes polynomiales (en n et k ). Notez que si U σ i ne change que deux qubits, il dépend également des premiers i - 1 qubits en fonction de la dépendance à z i (et en effet, il dépend de tous les qubits pour l'exigence de recevabilité). Cependant, nous pouvons exécuter un compteur pour calculer et stocker z i (et également déterminer l'admissibilité de l'entrée) en nombre logarithmique (en k pour obtenir une bonne approximation de U σ iUσjenkUσjeje-1zjezjek qubits ancilla ), et nous pouvons donc appliquer l' algorithme Solovay-KitaevUσjeutilisant uniquement de nombreuses portes polynomiales. (Le document fait appel à Solovay-Kitaev deux fois: une fois pour incrémenter le compteur à chaque étape, et une fois pour appliquer ; je ne sais pas s'il existe un moyen plus direct de décrire l'un ou l'autre comme des circuits quantiques avec des portes standard Le document ne mentionne pas non plus la nécessité de vérifier l'admissibilité ici; je ne sais pas si cela est important, mais nous avons certainement besoin d'au moins 1 z ik - 1Uσje1zjek-1 )

Donc, pour récapituler:

  1. Commencez par une tresse avec mσB2nm croisements.
  2. Écrivez .σ=σune1ϵ1σune2ϵ2σunemϵm
  3. Pour chaque , appliquer l'algorithme de Solovay-Kitaev pour obtenir une approximation de la matrice unitaire U σ a i (ou son inverse si ϵ i = - 1 ).je{1,2,,m}Uσunejeϵje=-1
  4. Composez toutes les approximations de l'étape 3 pour obtenir un circuit quantique avec de nombreuses portes polynomiales qui se rapproche de .Uσ
  5. Appliquer les tests Hadamard réels et imaginaires plusieurs fois de manière polynomiale avec le circuit de l'étape 4 et l'état |1010dix .
  6. Faites la moyenne des résultats de l'étape 5 et multipliez par un facteur d'échelle pour obtenir une approximation des parties réelles et imaginaires du polynôme de Jones de la fermeture plate de évaluée à e 2 π i / k .σe2πje/k
Evan Jenkins
la source
2

Vous avez mentionné cinq articles dans la question, mais un article qui reste non mentionné est la mise en œuvre expérimentale en 2009 . Vous trouverez ici le circuit réel qui a été utilisé pour évaluer un polynôme de Jones:

entrez la description de l'image ici

Cela pourrait être le plus proche d'une présentation "plus familière" de l'algorithme, car l'intérêt pour le polynôme de Jones et le DQC-1 s'est un peu dégradé depuis 2009.

Plus de détails sur cette expérience peuvent être trouvés dans la thèse de Gina Passante .

user1271772
la source
1
Je n'étais pas au courant de ce document, merci, bien que j'étais plus spécifiquement intéressé par la version complète de BQP. De même, dans mon bref survol, je ne vois pas beaucoup d'explications sur ce que l'unité Un
De rien. Oui, il s'agissait d'un PRL de 4 pages avec des détails qui ne sont pas expliqués aussi complètement que je le voudrais - peut-être qu'il y a un "matériel supplémentaire" sur la page Web du journal qui explique mieux le U. Le polynôme de Jones et le DQC-1 étaient populaires vers 2008-2009, mais je n'ai plus entendu parler depuis.
user1271772