Est-il possible d'accélérer la génération de la matrice de pondération à l'aide d'un algorithme quantique?

Dans cet article ^[1] , à la page 2, ils mentionnent qu'ils génèrent la matrice de pondération comme suit:

où sont les échantillons d'apprentissage aux dimensions (ie où ) et il y a échantillons d'apprentissage au total. Cette génération de matrice de pondération utilisant la multiplication matricielle suivie d'une somme sur termes semble être une opération coûteuse en termes de complexité temporelle c'est à dire je suppose autour de (?). d x :={ x 1 , x 2 ,. . . , X d } T x i ∈{1,-1}∀i∈{1,2,. . . ,d}MMO(Md$\mathbf{x}^{(m)}$$d$$\mathbf{x} := \{x_1,x_2,...,x_d\}^{T}$$x_i \in \{1,-1\} \ \forall \ i\in \{1,2,...,d\}$$M$$M$$O(Md)$

Existe-t-il un algorithme quantique pouvant offrir une accélération substantielle pour la génération de la matrice de pondération? Je pense que dans le document, leur accélération principale provient de l'algorithme d'inversion de matrice quantique (qui est mentionné plus loin dans l'article), mais ils ne semblent pas avoir pris en compte cet aspect de la génération de la matrice de pondération.

[1]: Un réseau neuronal Quantum Hopfield Lloyd et al. (2018)

En prenant la matrice de densité plupart des détails sont tous contenus dans le paragraphe suivant à la page 2:

Pour les adaptations quantiques des réseaux de neurones, la lecture classique des signaux quantiques des modèles d'activation est cruciale. Dans notre contexte, la lecture d'un motif d'activation revient à préparer l'état quantique . Cela pourrait en principe être réalisé en utilisant les techniques de développement de la mémoire à accès aléatoire quantique (qRAM) [33] ou une préparation d'état quantique efficace, pour laquelle des résultats restreints, basés sur Oracle, existent [34]. Dans les deux cas, la surcharge de calcul est logarithmique en termes de . On peut alternativement adapter une perspective entièrement quantique et prendre les schémas d'activation| x 〉d | x $x$$|x〉$$d$$|x〉$directement à partir d'un appareil quantique ou comme sortie d'un canal quantique. Pour les premiers, notre temps d'exécution de préparation est efficace chaque fois que le dispositif quantique est composé d'un certain nombre de portes évoluant au plus polynomialement avec le nombre de qubits. Au lieu de cela, pour ce dernier, nous considérons généralement le canal comme une forme d'interaction système-environnement fixe qui ne nécessite pas de surcharge de calcul pour être implémentée.

Les références ci-dessus sont:

[33]: V. Giovannetti, S. Lloyd, L. Maccone, mémoire à accès aléatoire Quantum, Physical Review Letters 100, 160501 (2008) [ lien PRL , lien arXiv ]

[34]: AN Soklakov, R. Schack, Préparation efficace de l'état pour un registre de bits quantiques, Physical Review A 73, 012307 (2006). [ Lien PRA , lien arXiv ]

Sans entrer dans les détails de la façon dont, les deux ci-dessus sont en effet des schémas pour respectivement, la mise en œuvre d'une qRAM efficace; et une préparation d'état efficace qui recrée l'état dans le temps .O ( log 2 d $\left|x\right>$$\mathcal O\left(\log_2 d\right)$

Cependant, cela ne nous amène qu'à ce stade: cela peut être utilisé pour créer l'état, alors que nous voulons une somme sur tous les possibles .$\rho^{\left(m\right)} = \left|x^{\left(m\right)}\rangle\langle x^{\left(m\right)}\right|$$m$

Fondamentalement, est mélangé, donc ne peut pas être représenté par un seul état pur, donc la deuxième des deux références ci-dessus sur la recréation d'états purs ne s'applique pas et le premier requiert que l'état soit déjà en qRAM.$\rho = \sum_m\rho^{\left(m\right)}/M$

À ce titre, les auteurs font l'une des trois hypothèses possibles:

1. Ils ont un appareil qui leur donne le bon état d'entrée

2. Ils ont soit les états dans qRAM,$\rho^{\left(m\right)}$

3. Ils sont capables de créer ces états à volonté, en utilisant la seconde des références ci-dessus. L'état mixte est ensuite créé à l'aide d'un canal quantique (c'est-à-dire une carte CPTP (complètement positive, préservant les traces)).

Oubliant pour le moment les deux premières des options ci-dessus (la première résout par magie le problème de toute façon), le canal pourrait être:

• un système d'ingénierie, en ce qu'il serait créé pour une instance spécifique dans quelque chose qui ressemble à une simulation analogique. En d'autres termes, vous avez un canal physique qui prend une durée physique (par opposition à une certaine complexité temporelle). Il s'agit de «l'interaction système-environnement fixe qui ne nécessite pas de surcharge de calcul pour être mise en œuvre».$t$

• Le canal est lui-même simulé. Il y a quelques articles à ce sujet, tels que la simulation approximative des canaux quantiques de Bény et Oreshkov ( lien arXiv - cela ressemble à un article complet, mais je n'ai trouvé aucun énoncé de complexité temporelle), Lu et. al. de la simulation de canal quantique expérimentale (pas de version arXiv semble exister) et Wei, Xin et arXiv Long prePrint simulation efficace du canal quantique universel dans l'ordinateur quantique nuage d'IBM , qui (pour le nombre de qubits ) donne une complexité temporelle de . La dilatation Stinespring peut également être utilisée, avec une complexité de$n=\lceil\log_2 d\rceil$$\mathcal O\left(\left(8n^3+n+1\right)4^{2n}\right)$$\mathcal O\left(27n^34^{3n}\right)$.

En examinant maintenant l'option 2 ¹ , une méthode plus efficace possible serait de transférer les états du registre d'adresses vers le registre de données dans la méthode habituelle: pour les adresses dans le registre , , le transférer dans le registre de données donne l'état dans le registre de données comme . Il devrait être possible de décohérer simplement l'adresse et le registre de données pour en faire un état mixte, ce qui donne une petite surcharge de temps, mais pas de surcharge de complexité de calcul supplémentaire, ce qui améliore considérablement la complexité de production de , étant donné une qRAM avec les états , de∑ j ψ j | j ⟩ a d Σ j ψ j | j ⟩ un | D j ⟩ d p | x ( m ) ⟩ O ( n ) | x ( m ) ⟩ ρ O ( n $a$$\sum_j\psi_j\left|j\right>_a$$d$$\sum_j\psi_j\left|j\right>_a\left|D_j\right>_d$$\rho$$\left|x^{\left(m\right)}\right>$$\mathcal O\left(n\right)$ . C'est également la complexité de créer les états en premier lieu, ce qui donne une complexité potentielle (bien améliorée) de production de of .$\left|x^{\left(m\right)}\right>$$\rho$$\mathcal O\left(n\right)$

^{1 Merci à @glS d'avoir signalé cette possibilité dans le chat}

Cette matrice de densité est ensuite introduite dans «qHop» (Hopfield quantique), où elle est utilisée pour simuler pour conformément à la sous-section « Simulation hamiltonienne efficace de A » à la page 8. A = ( W - γ I $e^{-iAt}$