Qu'est-ce qui rend les ordinateurs quantiques si bons à calculer les facteurs premiers?

L'une des affirmations courantes sur les ordinateurs quantiques est leur capacité à «casser» la cryptographie conventionnelle. C'est parce que la cryptographie conventionnelle est basée sur des facteurs premiers, quelque chose qui est coûteux en calcul pour les ordinateurs conventionnels à calculer, mais qui est un problème supposé trivial pour un ordinateur quantique.

Quelle propriété des ordinateurs quantiques les rend si capables de cette tâche où les ordinateurs conventionnels échouent et comment les qubits sont-ils appliqués au problème du calcul des facteurs premiers?

La réponse courte

$\newcommand{\modN}[1]{#1\,\operatorname{mod}\,N}\newcommand{\on}[1]{\operatorname{#1}}$Les ordinateurs quantiques sont capables d'exécuter des sous-programmes d'un algorithme pour l'affacturage, exponentiellement plus rapidement que tout homologue classique connu. Cela ne signifie pas que les ordinateurs classiques NE PEUVENT PAS le faire aussi rapidement, nous ne savons tout simplement pas aujourd'hui comment les algorithmes classiques fonctionnent aussi efficacement que les algorithmes quantiques.

La réponse longue

Les ordinateurs quantiques sont bons pour les transformations de Fourier discrètes. Il y a beaucoup de choses en jeu ici qui ne sont pas capturées par " c'est parallèle " ou " c'est rapide ", alors entrons dans le sang de la bête.

Le problème d'affacturage est le suivant: Étant donné un nombre où p , q sont des nombres premiers, comment récupérez-vous p et q ? Une approche consiste à noter les éléments suivants:$N = pq$$p,q$$p$$q$

Si je regarde un nombre , alors soit x partage un facteur commun avec N , soit il ne le fait pas.$\modN{x}$$x$$N$

Si partage un facteur commun et n'est pas un multiple de N lui-même, alors nous pouvons facilement demander quels sont les facteurs communs de x et N (via l'algorithme euclidien pour les plus grands facteurs communs).$x$$N$$x$$N$

Maintenant , un pas si évident fait: l'ensemble de tous les qui ne partagent pas un facteur commun avec N forme un groupe multiplicatif mod N . Qu'est-ce que ça veut dire? Vous pouvez consulter la définition d'un groupe dans Wikipedia ici . Que l'opération de groupe soit multipliée pour remplir les détails, mais tout ce qui nous intéresse vraiment ici est la conséquence suivante de cette théorie qui est: la séquence$x$$N$$\on{mod} N$

$$\modN{x^0}, \quad\modN{x^1}, \quad\modN{x^2}, ...$$

est périodique, lorsque ne partagent pas de facteurs communs (essayez x = 2 , N = 5 ) pour le voir directement:$x,N$$x = 2$$N = 5$

$$\newcommand{\mod}[1]{#1\,\operatorname{mod}\,5} \mod1 = 1,\quad \mod4 = 4,\quad \mod8 = 3,\quad \mod{16} = 1.$$

Maintenant, combien de nombres naturels inférieurs à N ne partagent aucun facteur commun avec N ? Cela est répondu par la fonction de totient d'Euler , c'est ( p - 1 ) ( q - 1 ) .$x$$N$$N$$(p-1)(q-1)$

Enfin, en tapant sur le sujet de la théorie des groupes, la longueur des chaînes répétitives

$$\modN{x^0}, \quad\modN{x^1}, \quad\modN{x^2}, ...$$

divise ce nombre . Donc, si vous connaissez la période des séquences de puissances de x $(p-1)(q-1)$ alors vous pouvez commencer à faire une supposition pour ce que ( p - 1 ) ( q - 1 ) est. De plus, si vous savez ce qu'est ( p - 1 ) ( q - 1 ) , et ce qu'est p q (c'est N ne l'oubliez pas!), Alors vous avez 2 équations avec 2 inconnues, qui peuvent être résolues par l'algèbre élémentaire pour p séparé , q .$x \mod N$$(p-1)(q-1)$$(p-1)(q-1)$$pq$$p,q$

Où les ordinateurs quantiques interviennent-ils? La découverte de la période. Il y a une opération appelée transformée de Fourier, qui prend une fonction écrite comme une somme de fonctions périodiques a 1 e 1 + a 2 e 2 . . . où un i sont des nombres, e i sont des fonctions périodiques avec la période p i et une carte , une nouvelle fonction f telle que f ( p i ) = a i .$g$$a_1 e_1 + a_2 e_2 ...$$a_i$$e_i$$p_i$$\hat{f}$$\hat{f}(p_i) = a_i$

Le calcul de la transformée de Fourier est généralement présenté comme une intégrale, mais lorsque vous souhaitez simplement l'appliquer à un tableau de données (le I ^ème élément du tableau est ), vous pouvez utiliser cet outil appelé une transformée de Fourier discrète qui équivaut à de multiplier votre "tableau" comme s'il s'agissait d'un vecteur, par une très grande matrice unitaire.$f(I)$

Accent sur le mot unitaire: c'est une propriété vraiment arbitraire décrite ici . Mais le principal point à retenir est le suivant:

Dans le monde de la physique, tous les opérateurs obéissent au même principe mathématique général: l' unité .

Cela signifie donc qu'il n'est pas déraisonnable de reproduire cette opération de matrice DFT en tant qu'opérateur quantique.

Maintenant, c'est là que ça s'approfondit un Qubit Array peut représenter 2 n éléments de tableau possibles (consultez n'importe où en ligne pour une explication ou déposez un commentaire).$n$$2^n$

De même, un opérateur quantique Qubit peut agir sur tout cet espace quantique 2 n et produire une réponse que nous pouvons interpréter.$n$$2^n$

Voir cet article Wikipedia pour plus de détails.

Si nous pouvons faire cette transformée de Fourier sur un ensemble de données exponentiellement grand, en utilisant seulement Qubits, alors nous pouvons trouver la période très rapidement.$n$

Si nous pouvons trouver la période très rapidement, nous pouvons rapidement assembler une estimation pour $(p-1)(q-1)$

Si nous pouvons le faire rapidement, étant donné notre connaissance de nous pouvons essayer de vérifier p , q .$N=pq$$p,q$

C'est ce qui se passe ici, à un niveau très élevé.

Ce qui rend les ordinateurs quantiques bons pour factoriser de grands nombres, c'est leur capacité à résoudre le problème de recherche de période (et un fait mathématique qui relie la recherche de facteurs premiers à la recherche de période). C'est essentiellement l'algorithme de Shor en bref. Pourtant, cela ne fait que poser la question de savoir ce qui rend les ordinateurs quantiques bons à la recherche de période.

Au cœur de la recherche de période se trouve la capacité de calculer la valeur d'une fonction sur l'ensemble de son domaine (c'est-à-dire pour chaque entrée imaginable). C'est ce qu'on appelle le parallélisme quantique. Cela n'est pas suffisant en soi, mais avec les interférences (la capacité de combiner les résultats du parallélisme quantique d'une certaine manière), c'est le cas.

Je suppose que cette réponse pourrait être un peu comme une falaise: comment utiliser ces capacités pour prendre en compte? Trouvez la réponse à cela sur wikipedia sur l'algorithme de Shor .

Tout d'abord, l'affacturage peut être effectué sur un ordinateur quantique (avec l'utilisation de portes quantiques «unitaires») au moyen de l'algorithme de Shor .

Une explication qui ne nécessite pas de mathématiques avancées ni aucune connaissance avancée de la physique est ce billet de blog de Scott Aaronson , intitulé "Shor, je vais le faire".

Un bref résumé de ses idées est le suivant:

Premièrement, nous représentons nos portes / qubits quantiques avec des horloges (en utilisant les «nombres complexes comme flèches (c'est-à-dire des éléments de $\mathbb{R}^2$ avec une étrange multiplication), représentation ')

Ensuite, nous notons qu'un chercheur CS a des périodes de sommeil très irrégulières. Pour retrouver cette étrange période, nous utilisons les horloges. Ensuite, nous notons que cette découverte de période peut être utilisée pour factoriser des entiers (en utilisant une construction similaire à celle du Pollard randomisé -$\rho$ algorithme)

Par conséquent, nos horloges quantiques étranges peuvent nous aider à factoriser efficacement!