Pouvons-nous accélérer l'algorithme de Grover en exécutant des processus parallèles?

En informatique classique, nous pouvons exécuter la recherche de clé (par exemple AES) en exécutant autant de nœuds de calcul parallèles que possible.

Il est clair que nous pouvons également exécuter de nombreux algorithmes de Grover.

Ma question est ; -il possible d'avoir une accélération en utilisant plus d'un algorithme de Grover comme en informatique classique?

classical-computing grovers-algorithm cryptography kelalaka
la source

Réponses:

Certainement! Imaginez que vous ayez $K=2^k$ copies de l'oracle de recherche $U_S$ que vous pouvez utiliser. Normalement, vous chercheriez par itérer l'action

H^{\otimes n} (I_{n} - 2 | 0 ⟩ ⟨ 0 |^{\otimes n}) H^{\otimes n} U_{S},

$H^{\otimes n}(\mathbb{I}_n-2|0\rangle\langle 0|^{\otimes n})H^{\otimes n}U_S,$ à partir d'un état initial

(H | 0 ⟩)^{\otimes n}

$(H|0\rangle)^{\otimes n}$ . Cela prend du temps

Θ (\sqrt{N})

$\Theta(\sqrt{N})$ . (J'utilise

I_{n}

$\mathbb{I}_n$ pour désigner lamatrice d'identité

2^{n} \times 2^{n}

$2^n\times 2^n$ .)

Vous pouvez le remplacer par $2^k$ copies parallèles, indexées chacune par un $x\in\{0,1\}^k$ , en utilisant

(I_{k} \otimes H^{\otimes (n - k)}) I_{k} \otimes (I_{n - k} - 2 | 0 ⟩ ⟨ 0 |^{\otimes (n - k)}) (I_{k} \otimes H^{\otimes (n - k)}) U_{S}

$\left(\mathbb{I}_k\otimes H^{\otimes (n-k)}\right)\mathbb{I}_k\otimes(\mathbb{I}_{n-k}-2|0\rangle\langle 0|^{\otimes (n-k)})\left(\mathbb{I}_k\otimes H^{\otimes (n-k)}\right)U_S$ et à partir d'un état

| x ⟩ (H | 0 ⟩)^{\otimes (n - k)}

$|x\rangle(H|0\rangle)^{\otimes(n-k)}$ Le temps nécessaire pourexécutioncellesci serait réduite à

O (\sqrt{N / K})

$O(\sqrt{N/K})$ , au prix d'exiger

K

$K$ fois plus d'espace.

Dans un sens de mise à l'échelle, on pourrait considérer cela comme un résultat non pertinent. Si vous avez un nombre fixe d'oracles, $K$ , alors vous obtenez un fixe ( $\sqrt{K}$ ) amélioration (tout comme si vous avez $K$ cœurs classiques parallèles, la meilleure amélioration que vous pouvez obtenir est un facteur de $K$ ), et cela ne change pas l'échelle. Mais cela change le temps de fonctionnement fondamental. Nous savons que l'algorithme de Grover est exactement optimal. Cela prend le temps minimum absolu possible avec un seul oracle. Donc, sachant que vous obtenez un $\sqrt{K}$ amélioration du temps est utile en ce qui concerne ce pointréférence d'une durée spécifique à une valeur spécifique de $N$ .

DaftWullie
la source

mais si vous faites cela, la comparaison avec la performance classique perd une partie de son sens, n'est-ce pas? Après tout, vous pouvez également accélérer la recherche classique en exécutant l'opération qui vérifie si un

donné est la cible en parallèle sur toutes les entrées. Cela nécessite clairement des hypothèses supplémentaires sur les ressources disponibles, mais le même type d'hypothèses que celles avancées dans votre argument

x

$x$

glS

va àinfinimais

nepas. Votre problème s'aggrave mais vos ressources restent peu nombreuses.

N

$N$

K

$K$

AHusain

Cette réponse est correcte (bien qu'elle ne soit pas optimale, comme DaftWullie le met en garde). C'est la même attitude envers la parallélisation que l'on prend dans la complexité d'un circuit classique. Si vous voulez une accélération en raison de la parallélisation, alors vous regardez la profondeur du circuit (car la coordination de plusieurs processus ne va pas réduire le travail total). Peu importe que

soit constant --- soit vous êtes intéressé par l'amélioration de la profondeur de la parallélisation, soit vous ne l'êtes pas. Comme pour le calcul quantique lui-même, le simple fait de lancer plus d'ordinateurs à un problème ne rend pas tout magique comme par magie!

K

$K$

Niel de Beaudrap

Dans un sens, si nous le faisions en parallèle sur différents nœuds, vous gagneriez du temps pour l'exécution. Mais si nous parlons de complexité (c'est ce que nous appelons l'accélération en général), nous avons besoin d'un peu d'analyse.

Vous convenez que nous avons besoin d'environ $\sqrt{N}$ opérations pour le cas non parallèle. Disons que nous avons deux nœuds, et nous séparons la liste des N éléments en deux listes de taille $N_1,N_2$ . La recherche dans les sous-listes dure environ $\sqrt{N_1},\sqrt{N_2}$ .

Cependant, nous avons cela

\sqrt{N} = \sqrt{N_{1} + N_{2}} \leq \sqrt{N_{1}} + \sqrt{N_{2}}

$\sqrt{N} = \sqrt{N_1+N_2} \le \sqrt{N_1} + \sqrt{N_2}$

$O$

Cependant, cela serait toujours intéressant, surtout si nous devons regrouper le matériel car nous sommes limités en nombre de qubits ou autres limitations.

cnada
la source

Pour N1 = N2, c'est toujours une inégalité: sqrt (2) * sqrt (N1) <2 * sqrt (N1)

Mariia Mykhailova

Oh en effet. Dans ma tête $ \ sqrt {a b} = \ sqrt {a} \ sqrt {b} $ je pensais. Je devrais arrêter de répondre aux réponses ici à minuit et lorsque je suis fatigué. Merci d'avoir fait remarquer cela.

cnada

@cnada: Il existe au moins deux notions différentes de complexité, toutes deux pertinentes pour l'accélération. L'un est la complexité de la taille et l'autre la complexité de la profondeur. Sauf indication contraire, nous préférons souvent considérer la complexité de la taille, mais la complexité de la profondeur est toujours quelque chose qui intéresse beaucoup la complexité de calcul quantique, par exemple dans MBQC [arXiv: quant-ph / 0301052 , arXiv: 0704.1736 ] et les résultats récents sur séparations de profondeur inconditionnelles [arXiv: 1704.00690 ].

Niel de Beaudrap

@NieldeBeaudrap Je pensais que les gens regardaient davantage la complexité en profondeur. Mais pour Grover, la complexité de la taille et de la profondeur sont à peu près du même ordre. C'est quadratique dans la taille du problème (généralement considéré comme la taille d'une liste de N éléments). Pensez-vous que mon approche ici n'est pas correcte?

cnada

k \in O (1)

$k \in O(1)$

\sqrt{N}

$\sqrt N$

\log (k) \sqrt{N / k}

$\log(k) \sqrt{N/k}$

k (N) \in Ω (1)

$k(N) \in \Omega(1)$

\sqrt{k} / \log (k)

$\sqrt{k}/\!\!\;\log(k)$