Jones Polynomial

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 $U$dans la variante DQC-1, ou tout simplement le circuit entier dans la variante complète BQP)?

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.$\sigma$$k$$U_\sigma$$\sigma$$B_{2n}$$U_\sigma$$U_\sigma$

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 $\sigma$$2n$$m$ , où a 1 , a 2 , … , a m ∈ { 1 , 2 , … , 2 n - 1 } , ϵ 1 , ϵ 2$\sigma = \sigma_{a_1}^{\epsilon_1} \sigma_{a_2}^{\epsilon_2} \cdots \sigma_{a_m}^{\epsilon_m}$$a_1, a_2, \ldots, a_m \in \{1, 2, \ldots, 2n - 1\}$ i + 1 ) st. Il suffit de décrire U σ i , puisque U σ = U ϵ 1 σ a 1 ⋯ U ϵ m σ a m .$\epsilon_1, \epsilon_2, \ldots, \epsilon_m \in \{\pm 1\}$$\sigma_i$$B_{2n}$$i$$(i + 1)$$U_{\sigma_i}$$U_\sigma = U_{\sigma_{a_1}}^{\epsilon_1} \cdots U_{\sigma_{a_m}}^{\epsilon_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 2 ⋯ b 2 n ⟩ , laisser ℓ i ' ( ψ ) = 1 + Σ i ' j = 1 ( - 1 ) 1 - b j . Appelons $U_{\sigma_i}$$\mathbb{C}^{2^{2n}}$$U_{\sigma_i}$$\psi = \lvert b_1 b_2 \cdots b_{2n} \rangle$$\ell_{i'}(\psi) = 1 + \sum_{j = 1}^{i'} (-1)^{1-b_j}$$\psi$ 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 $1 \leq \ell_{i'}(\psi) \leq k - 1$$i' \in \{1, 2, \ldots, 2n\}$$\psi$$2n$$G_k$SoitA=ie-πi/2k(ceci est mal tapé dans l'article AJL; notez également qu'ici et seulement ici,i=

$$\lambda_r = \begin{cases}\sin(\pi r / k) & \textrm{if $1 \leq r \leq k - 1$},\\ 0 & \textrm{otherwise.}\end{cases}$$ $A = ie^{-\pi i/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 ⋯ ⟩ $i = \sqrt{-1}$$i$$\psi = \lvert \psi_i b_i b_{i+1} \cdots\rangle$$\psi_i$$i - 1$$\psi$$z_i = \ell_{i-1}(\psi_i)$ On définitU σ i (ψ)=ψpour les éléments de base non admissiblesψ. $$\begin{align} U_{\sigma_i}(\lvert\psi_i 00 \cdots\rangle) & = A^{-1}\lvert\psi_i 00 \cdots\rangle\\ U_{\sigma_i}(\lvert\psi_i 01 \cdots \rangle) & = \left( A\frac{\lambda_{z_i-1}}{\lambda_{z_i}} + A^{-1}\right)\lvert\psi_i 01 \cdots\rangle + A\frac{\sqrt{\lambda_{z_i+1}\lambda_{z_i-1}}}{\lambda_{z_i}}\lvert\psi_i 10 \cdots\rangle\\ U_{\sigma_i}(\lvert\psi_i 10 \cdots \rangle) & = A\frac{\sqrt{\lambda_{z_i+1}\lambda_{z_i-1}}}{\lambda_{z_i}}\lvert\psi_i 01 \cdots\rangle + \left(A\frac{\lambda_{z_i+1}}{\lambda_{z_i}} + A^{-1}\right)\lvert\psi_i 10 \cdots\rangle\\ U_{\sigma_i}(\lvert\psi_i 11 \cdots\rangle) & = A^{-1}\lvert\psi_i 11 \cdots\rangle \end{align}$$ $U_{\sigma_i}(\psi) = \psi$$\psi$

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 σ $U_{\sigma_i}$$n$$k$$U_{\sigma_i}$$i - 1$$z_i$$z_i$$k$ qubits ancilla ), et nous pouvons donc appliquer l' algorithme Solovay-Kitaev$U_{\sigma_i}$utilisant 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 i ≤ k - $U_{\sigma_i}$$1 \leq z_i \leq k - 1$ )

Donc, pour récapituler:

1. Commencez par une tresse avec $\sigma \in B_{2n}$$m$ croisements.
2. Écrivez .$\sigma = \sigma_{a_1}^{\epsilon_1} \sigma_{a_2}^{\epsilon_2} \cdots \sigma_{a_m}^{\epsilon_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 ).$i \in \{1, 2, \ldots, m\}$$U_{\sigma_{a_i}}$$\epsilon_i = -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_{\sigma}$
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 $\lvert 1010 \cdots 10\rangle$ .
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 .$\sigma$$e^{2\pi i/k}$

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:

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 .