L'implémentation 2016 de l'algorithme de Shor est-elle vraiment évolutive?

23

Dans l'article scientifique de 2016 " Réalisation d'un algorithme de Shor évolutif " [ 1 ], les auteurs factorisent 15 avec seulement 5 qubits, ce qui est inférieur aux 8 qubits "requis" selon le tableau 1 de [ 2 ] et le tableau 5 de [ 3 ]. L'exigence de 8 qubits vient de la fin de [ 4 ] qui indique que le nombre de qubits nécessaires pour la factorisation d'un nombre à bits est de 1,5 n + 2, ce qui pour 15 est de 1,5 ⋅ 4 + 2 = 8 .n1.5n+21.5⋅4+2=8

Le document qui n'utilise que 5 qubits indique que leur algorithme "remplace un QFT agissant sur M qubits par un QFT semi-classique agissant à plusieurs reprises sur un seul qubit", mais les conséquences de cela sur la complexité de l'algorithme n'ont jamais été mentionnées dans le document.

Maintenant, il y a eu une critique sévère de l'article prétendant factoriser 15 de manière "évolutive", comme ils disent dans la section 2 que l'argument de complexité pour l'algorithme de Shor ne tient plus. Cependant, cette critique n'a été corroborée nulle part, et l'article scientifique continue d'être célébré comme une version "évolutive" de l'algorithme de Shor. Quelle est la complexité de l'algorithme Shor "évolutif"?

  • [ 1 ] Monz et al. (2016) Science . Vol. 351, numéro 6277, pp. 1068-1070
  • [ 2 ] Smolin et al. (2013) Nature . 499, 163–165
  • [ 3 ] Dattani et Bryans (2014) arXiv: 1411.6758
  • [ 4 ] Zalka (2008) arXiv: quant-ph / 0601097
  • [ 5 ] Cao & Luo "Commentaire sur: Réalisation d'un algorithme Shor évolutif"
cc.complexity-theory ds.algorithms quantum-computing factoring security user1271772
la source
5
Cela dépend de ce que vous entendez par «évolutif». Certaines critiques de Cao et Liu semblent assez pointilleuses. Par exemple, l'une de leurs critiques est que Kitaev n'a pas prétendu que vous ne pouviez utiliser qu'un seul qubit dans le document cité pour ce résultat. Ils ne semblent pas enquêter pour savoir si cette affirmation elle-même est réellement vraie ou fausse. L'algorithme de Kitaev peut en fait être modifié pour n'utiliser qu'un seul qubit, comme le prétend l'article scientifique, même si cette affirmation ne semble pas figurer dans l'article de Kitaev sur son algorithme.
Peter Shor
1
@PeterShor, quel honneur d'avoir de vos nouvelles! Ok donc les auteurs ont (correctement) étendu les résultats de l'article de Kitaev pour le rendre possible avec un qubit, et Cao & Liu se plaignent de l'appeler "l'algorithme de Kitaev" plutôt que "l'algorithme de Kitaev modifié ou quelque chose comme ça". Cependant, ils disent également que l'argument de complexité ne tient plus lorsque le QFT est transformé en "QFT semi-classique". Je suis encore étudiant en ce qui concerne ce type d'analyse, j'apprécierais donc vos commentaires. La complexité est-elle toujours O (log n) ^ 3? Est-il toujours "évolutif" en termes de polynôme, ou au moins <GNFS?
user1271772
4
Je laisserai quelqu'un d'autre répondre à cela, car les gens pourraient prétendre que je suis partial. Mais permettez-moi de souligner que les auteurs de l' article scientifique n'ont pas étendu l'algorithme de Kitaev ... c'est une extension bien connue. Ils n'ont tout simplement pas cité la bonne référence.
Peter Shor
5
Ces formules qui arrivent à 8 qubits prennent une implémentation spécifique de l'algorithme de Shor et calculent combien de qubits cette implémentation prend. Ils ne prétendent pas qu'il s'agit de la meilleure mise en œuvre possible.
Peter Shor
2
@ user1271772 Ceci a été signalé pour l'attention de modération sur la base du fait que vous êtes l'un des auteurs mentionnés dans votre propre article. Pas que ce soit mauvais, une auto-publicité est une partie inévitable de la science, mais peut-être qu'il vaut mieux être clair à ce sujet?
Bjørn Kjos-Hanssen

Réponses:

11

L'idée maîtresse de l'argument de Cao et Luo est que dans la variante de l'algorithme qui a été implémenté, le premier registre - qui contient finalement la sortie - ne contient qu'un bit. Et si vous n'obtenez qu'un bit de sortie de l'algorithme, cela ne suffit pas pour la factorisation. (D'une part, bien que ce ne soit pas leur argument, 1 bit ne contient clairement pas suffisamment d'informations pour déterminer les facteurs.)

cO(log3⁡N)

Pour essayer d'être juste envers Cao et Luo, ils disent qu'ils ne pensent pas que cet algorithme fonctionne, et s'il fonctionne, alors ce n'est pas l'algorithme de Shor car il ne correspond pas exactement à l'algorithme décrit dans le document d'affacturage original . Une citation de leur article:

Enfin, nous tenons à souligner que si la mise en œuvre est effectivement crédible, il s'agirait alors d'un nouvel algorithme de factorisation quantique, et non de l'algorithme Shor, car toutes les exigences de l'algorithme Shor d'origine ne sont pas satisfaites.

Et en effet, ce n'est pas l'algorithme de mon papier d'affacturage d'origine. Il utilise la procédure d'estimation de phase de l'algorithme de factorisation de Kitaev, et une variante de celle-ci, découverte par Griffiths et Niu (pas par Parker et Plenio, comme je l'ai dit dans une édition précédente de cette réponse) qui permet à l'algorithme de générer l'estimation de la phase un bit à la fois.

Peter Shor
la source
1
Veuillez me montrer où, dans l'article de Cao et Luo, ils disent que produire un bit à la fois affecte le coût de l'opération. Si je lis correctement leur article, ils ne le font pas. Je pense avoir réfuté adéquatement leurs critiques.
Peter Shor
2
cx⋅tt
2
Je ne vais pas passer par le circuit pour une estimation de phase de sortie à un qubit et expliquer pourquoi le changement relativement petit nécessaire pour accomplir cela n'affecte pas la complexité temporelle. Il est la modification « semi-classique » décrit à la page 2 de Parker et de Plenio papier , factorisation efficace avec un seul qubit pur et log N qubits mixtes .
Peter Shor
1
log⁡N+11log⁡N+1
1
Comme je l'ai dit, vous devez lire et comprendre le document. Comptez-les vous-même si vous ne me faites pas confiance. La structure de base de l'algorithme n'a pas changé.
Peter Shor