Quels entiers ont été pris en compte avec l'algorithme de Shor?

La factorisation principale de 21 (7x3) semble être la plus importante réalisée à ce jour avec l'algorithme de Shor; cela a été fait en 2012 comme détaillé dans cet article . Il convient toutefois de noter que des nombres beaucoup plus importants, tels que 56 153 en 2014, ont été pris en compte à l'aide d'un algorithme de minimisation, comme détaillé ici . Pour une référence pratique, voir le tableau 5 de ce document :

{\begin{matrix} Table 5: Quantum factorization records \\ \begin{array}{cccccc} Number & # of factors & \begin{matrix} # of qubits \\ needed \end{matrix} & Algorithm & \begin{matrix} Year \\ implemented \end{matrix} & \begin{matrix} Implemented \\ without prior \\ knowledge of \\ solution \end{matrix} \\ 15 & 2 & 8 & Shor & 2001 [2] & χ \\ 2 & 8 & Shor & 2007 [3] & χ \\ 2 & 8 & Shor & 2007 [3] & χ \\ 2 & 8 & Shor & 2009 [5] & χ \\ 2 & 8 & Shor & 2012 [6] & χ \\ 21 & 2 & 10 & Shor & 2012 [7] & χ \\ 143 & 2 & 4 & minimization & 2012 [1] & ✓ \\ 56153 & 2 & 4 & minimization & 2012 [1] & ✓ \\ 291311 & 2 & 6 & minimization & not yet & ✓ \\ 175 & 3 & 3 & minimization & not yet & ✓ \end{array} \end{matrix}}_{.}

$\begin{array}{c} \textbf{Table 5:}~\text{Quantum factorization records} \\ \hline \small{ \begin{array}{cccccc} \text{Number} & \text{# of factors} & \begin{array}{c}\text{# of qubits} \\ \text{needed} \end{array} & \text{Algorithm} & \begin{array}{c}\text{Year} \\ \text{implemented} \end{array} & \begin{array}{c}\text{Implemented} \\ \text{without prior} \\ \text{knowledge of} \\ \text{solution} \end{array} \\ \hline 15 & 2 & 8 & \text{Shor} & 2001~\left[2\right] & \chi \\ & 2 & 8 & \text{Shor} & 2007~\left[3\right] & \chi \\ & 2 & 8 & \text{Shor} & 2007~\left[3\right] & \chi \\ & 2 & 8 & \text{Shor} & 2009~\left[5\right] & \chi \\ & 2 & 8 & \text{Shor} & 2012~\left[6\right] & \chi \\ 21 & 2 & 10 & \text{Shor} & 2012~\left[7\right] & \chi \\ 143 & 2 & 4 & \text{minimization} & 2012~\left[1\right] & \checkmark \\ 56153 & 2 & 4 & \text{minimization} & 2012~\left[1\right] & \checkmark \\ \hline 291311 & 2 & 6 & \text{minimization} & \text{not yet} & \checkmark \\ 175 & 3 & 3 & \text{minimization} & \text{not yet} & \checkmark \end{array}} \end{array}_{\Large{.}}$

bruyère
la source

@SqueamishOssifrage: Où est-il dit que l'algorithme de minimisation est "limité aux nombres dont les facteurs ont des relations connues qui rendent l'espace de recherche beaucoup plus petit, comme différer dans seulement quelques positions de bits ou différer dans toutes sauf quelques positions"?

user1271772

@ user1271772 Si je comprends bien, la technique repose sur la réduction du problème pour ne nécessiter qu'un nombre traitable de qubits en éliminant les variables par des relations connues entre les bits des facteurs. Bien que le nombre de qubits du facteur

puisse évoluer avec seulement

, aucun des articles que j'ai lus ne semblait tenter d'estimer la croissance du temps de résolution en fonction du nombre de qubits ou du

N

$N$

O (\log^{2} N)

$O(\log^2 N)$

\log N

$\log N$

Squeamish Ossifrage

@SqueamishOssifrage: "en éliminant les variables par des relations connues entre les bits des facteurs" Seriez-vous d'accord pour dire que l'Eq. 1 de arxiv.org/pdf/1411.6758.pdf implique que z12 = 0, sans aucune relation "connue" entre les bits? Seriez-vous d'accord que vous pouvez déduire que z12 = 0 pour arbitraire p1, p2, q1, q2? Next: Le nombre de variables (qubits) dans la méthode de la table est

non

. Le problème peut être résolu sur un recuiteur avec

qubits

si des interactions arbitraires à 4 qubits sont autorisées. Si seulement les interactions 2 qubits sont autorisés, vous devez

\log (N)

$\log(N)$

\log^{2} N

$\log^2 N$

\log (N)

$\log(N)$

\log^{2} N

$\log^2 N$

user1271772

@SqueamishOssifrage: "aucun des articles que j'ai lus ne semblait tenter d'estimer la croissance du temps de résolution en fonction du nombre de qubits". Celui-ci a fait une tentative: journals.aps.org/prl/abstract/10.1103/PhysRevLett.101.220405 Mais «le temps de la solution» n'est pas ce qui est important, c'est l'effort requis. Le tamisage GNF est facile mais l'étape de la matrice est horriblement lourde. L'exécution de l'algorithme de Shor d'une manière raisonnablement optimale est lourde. L'algorithme de minimisation est simple.

user1271772

@SqueamishOssifrage: Enfin: "Notez que l'algorithme de minimisation est limité aux nombres dont les facteurs ont des relations connues" .. aucune partie de l'algorithme n'est limitée aux relations "connues". L'algorithme ne suppose rien sur les facteurs. Pas de relations. Les bits sont toutes des variables inconnues qui sont déterminées par minimisation. La minimisation peut être effectuée avec moins de qubits pour certains nombres que pour d'autres. Il en va de même pour l'algorithme de Shor. Il en va de même pour GNFS. En fait, si le nombre que vous souhaitez factoriser est pair, il est plutôt facile de le factoriser.

user1271772

La taille du nombre factorisé n'est pas une bonne mesure de la complexité du problème de factorisation, et en conséquence de la puissance d'un algorithme quantique. La mesure pertinente devrait plutôt être la périodicité de la fonction résultante qui apparaît dans l'algorithme.

Ceci est discuté dans J. Smolin, G. Smith, A. Vargo: Pretending to factor large numbers on a quantum computer , Nature 499, 163-165 (2013) . En particulier, les auteurs donnent également un exemple d'un nombre avec 20000 chiffres binaires qui peut être factorisé avec un ordinateur quantique à deux qubits, avec exactement la même implémentation qui avait été utilisée précédemment pour factoriser d'autres nombres.

Il convient de noter que les «simplifications manuelles» que les auteurs effectuent pour arriver à cet algorithme quantique est quelque chose qui a également été fait, par exemple, pour la factorisation de l'expérience originale 15.

Norbert Schuch
la source

Quels entiers ont été pris en compte avec l'algorithme de Shor?

Réponses: