Comment écrire une version classique de l'algorithme de Shor

Question

À des fins d' apprentissage , j'aimerais écrire une version classique de l'algorithme de Shor. D'après ce que j'ai lu, ce qui rend cet algorithme rapide est la FFT quantique, qui est utilisée pour trouver la période de la fonction$a^k \bmod N$ dans le but ultime de trouver le k qui résout $a^k \bmod N = 1$.

Reconnaissant que ce serait trop lent, j'aimerais écrire une version qui utilise la FFT classique. Un tel algorithme pourrait certainement factoriser de petits nombres.

Ce qui me trouble, c'est que lorsque je calcule les valeurs de $a^k \bmod N$ pour alimenter la FFT, il n'est pas si difficile de sauter la FFT et de trouver $a^k \bmod N = 1$par la force brute ( similaire à cette question ).

Qu'est-ce que j'oublie ici? Sinon, si j'avais une boîte noire qui pouvait calculer instantanément les FFT, comment cela changerait-il l'algorithme de Shor?

Answer 1

Dans l'algorithme (quantique) de Shor, vous ne calculez l'exposant modulaire qu'un petit nombre de fois - bien plus petit que $N$. L'algorithme est probabiliste, et si vous avez de la chance, vous ne pouvez le calculer qu'une seule fois.

Après l'étape d'exponentiation modulaire, les qubits codent en principe la valeur de $a^k\text{ mod }N$ pour chaque $k$, mais vous ne pouvez pas simplement rechercher dans la fonction d'onde une valeur de $1$. Si vous pouviez faire cela (parfois appelé «post-sélection»), vous pourriez faire des choses bien plus impressionnantes que la factorisation des nombres, comme résoudre le Circuit SAT en temps linéaire en post-sélectionnant sur la sortie du circuit étant$1$. Le problème est que vous ne pouvez pas choisir le résultat de votre mesure, et avec une probabilité écrasante, vous obtiendrez un résultat que vous ne vouliez pas.

Lorsque vous simulez classiquement l'algorithme de Shor (ou ma tentative de solveur Circuit SAT), il n'y a probablement pas de moyen beaucoup plus efficace de le faire que de calculer réellement chaque terme de la fonction d'onde dans la base de calcul. Puisque vous faites tout ce travail, vous pouvez vérifier la sortie que vous vouliez en même temps, mais si vous faites cela, vous ne simulez plus un algorithme quantique, car cette opération n'est pas autorisée par les règles du calcul quantique (et n'est pas autorisé par les lois de la physique pour autant que nous puissions le dire).