Qu'est-ce que l'algorithme Shore? Est-il vrai qu'un ordinateur quantique peut effectuer une factorisation première en temps polynomial? Je l'ai cherché!

introduction

Pour effectuer la factorisation des nombres premiers sur un ordinateur classique, il faut $ O (\ sqrt {N}) $ pour calculer, et même l'algorithme le plus efficace actuellement développé prend environ un temps exponentiel de chiffres. Il semble que cela finira. Mais quand j'essaie de faire une factorisation de niveau premier à 300 chiffres, il faut beaucoup de temps pour mourir. e? Décomposition des facteurs premiers en temps polynomial? Je peux le faire! C'est l'algorithme de Shore. Dans cet article, le but de cet article est d'implémenter cet algorithme de rivage dans qiskit et de l'exécuter sur un véritable ordinateur quantique. Cette fois, nous réduirons le facteur 15. Je pense qu'il y a probablement (ou certainement) des erreurs et des fautes d'impression dans cet article, donc si vous en trouvez une, merci de bien vouloir me le faire savoir ...

couler

Pour expliquer l'algorithme du rivage, diverses préparations sont nécessaires, mais je voudrais d'abord écrire le flux global.

Tout d'abord, considérons un nombre naturel $ N $ que vous voulez factoriser en un facteur premier et un nombre naturel $ x $ qui est mutuellement premier (vous pouvez déterminer s'ils sont premiers ou non par division mutuelle euclidienne). Pensons-y dans le monde de modN ci-dessous. Le plus petit r tel que $ x ^ r = 1 $ est appelé un chiffre. On sait que trouver ce chiffre est efficace pour la factorisation des nombres premiers. Cependant, avec un ordinateur classique, ce calcul prend également un temps exponentiel. L'algorithme d'estimation de phase résout ce problème. L'algorithme d'estimation de phase donne une phase approximative de la valeur propre (la valeur absolue est 1) de la matrice unitaire. Considérant U tel que $ U ^ r = I $ dans le monde de $ \ mod N $, r peut être obtenu à partir de sa valeur unique. Le test Adamar et la transformée quantique de Fourier décrits ci-dessous sont nécessaires comme sous-programmes pour cet algorithme d'estimation de phase.

Test d'Adamar

Tout d'abord, j'expliquerai un algorithme appelé le test d'Adamal.

Le test Adamal est réalisé par le circuit suivant ($ U $ est une porte arbitraire). スクリーンショット 2020-02-22 17.26.58.png

Dans ce circuitq_0 = \left|0\right>, q_1 = \left|\varphi\right>Pensons à ce qui se passe lorsque vous le passez. pourtant\left|\varphi\right>EstUEst le vecteur propre dee^{i\lambda}ça ira. $ \left|0\right>\left|\varphi\right>\rightarrow \frac{1}{\sqrt{2}}(\left|0\right>\left|\varphi\right>+\left|1\right>\left|\varphi\right>)\rightarrow \frac{1}{\sqrt{2}}(\left|0\right>\left|\varphi\right>+e^{i\lambda}\left|1\right>\left|\varphi\right>)\rightarrow \left(\frac{1+e^{i\lambda}}{2}\left|0\right>+\frac{1-e^{i\lambda}}{2}\left|1\right>\right)\otimes\left|\varphi\right> $

control-Le bit quantique après avoir traversé la porte U\frac{1}{\sqrt{2}}(\left|0\right>+e^{i\lambda}\left|1\right>)\otimes \left|\varphi\right>Ce sera dans l'état. Vous pouvez voir que la phase de la valeur propre de U sort comme la phase avant (le premier bit quantique). En lui appliquant en outre la porte Adamal, la phase de la valeur propre de U peut être obtenue comme probabilité d'observation du premier bit quantique. Il est étrange que la probabilité d'observation change comme si la phase avait changé à partir du deuxième bit quantique, même si aucune opération n'a été effectuée sur le bit de contrôle. Cependant, si vous voulez connaître la phase de la valeur propre par cette méthode, vous devez la mesurer plusieurs fois. Un algorithme d'estimation de phase sortira comme algorithme pour résoudre ce problème.

Transformée quantique de Fourier

La transformée de Fourier quantique est un algorithme qui effectue une transformée de Fourier discrète. En supposant que la longueur de la séquence est de $ 2 ^ n $, l'ordinateur classique peut effectuer la transformée de Fourier discrète avec $ O (n2 ^ n) $ dans la transformée de Fourier haute vitesse que tout le monde aime, mais la transformée quantique de Fourier peut effectuer la transformée de Fourier discrète avec $ O (n ^ n ^). 2) Il peut être résolu en $ n $ polypoly time appelé $!

Rappelons tout d'abord la formule de définition de la transformée de Fourier discrète. $ y_k = \frac{1}{\sqrt{2^n}} \sum_{j=0}^{2^n-1} x_j e^{i\frac{2\pi kj}{2^n}} $ Exprimant cela sur qubit, $ |x\rangle = \sum_{j=0}^{2^n-1} x_j |j\rangle \rightarrow |y\rangle = \sum_{k = 0}^{2^n-1} y_k |k\rangle \\\ |j\rangle \rightarrow \frac{1}{\sqrt{2^n}} \sum_{k=0}^{2^n-1} e^{i\frac{2\pi jk}{2^n}}|k\rangle $ Ce sera.

En fait, cette transformation est unitaire, et comme l'ordinateur quantique peut approximer n'importe quelle transformation unitaire avec l'ensemble de portes universel, cette transformation est réalisable sur l'ordinateur quantique. Cependant, je ne sais pas quel type de porte mordre tel quel, j'aimerais donc le transformer en une forme plus facile à utiliser. Si vous développez k en binaire et faites de votre mieux, ce sera comme suit. $ |j\rangle \rightarrow\otimes_{l = 1}^{2^n} (|0\rangle+e^{\frac{2\pi i}{2^l}}|1\rangle) $ Sous cette forme, il est multiplié comme le produit tensoriel de chaque q-bit, vous pouvez donc voir que la transformée de Fourier peut être réalisée par la porte Adamal et la porte de rotation (voir la figure ci-dessous). foruier2.png

En fait, l'algorithme de Shore utilise la transformée quantique de Fourier inverse, également illustrée ci-dessous. Cela a juste accroché la porte du côté opposé (mais la rotation est inverse).

fourier_transform.png

À propos, vous devez faire attention au sens de lecture du bit quantique. Ici, nous allons lire dans l'ordre de q0q1q2q3. Autrement dit, si $ q0 = 1, q1 = q2 = q3 = 0 $, alors $ x = 1000 (2) = 8 $. Pour le moment, H est le même que la porte Adamal, U1 est le même que la porte Rz, et seulement $ | 1 \ rangle $ est la porte qui met la phase de $ e ^ {i \ theta} $. Pour plus d'informations, cliquez ici (https://quantum-computing.ibm.com/support/guides/gate-overview?section=5d00d964853ef8003c6d6820#)

Algorithme d'estimation de phase

L'algorithme de phase est une version améliorée du test Adamar.

Soit la valeur propre de la matrice unitaire $ U $ de taille $ 2 ^ n $ $ e ^ {2 \ pi i \ lambda} $, et le vecteur propre correspondant $ | \ varphi \ rangle $. Si $ \ lambda $ peut être représenté en binaire comme une fraction du chiffre $ m , $ |y\rangle = \frac{1}{\sqrt{2^n}}\sum_{k = 0}^{2^m-1}e^{2\pi ij\lambda}|j\rangle $$ Si vous pouvez créer l'état, vous pouvez trouver $ \ lambda $ dans le développement de Fourier discret inverse (à comparer avec la formule de définition du chapitre précédent).

M pour l'algorithme d'estimation de phase+Utilise n bits quantiques pour l'entrée|0\rangle|\varphi\rangleJe vais mettre. Premièrement, en appliquant la porte Adamal aux m premiers bits quantiques|0\rangleDe|2^m-1\rangleCréez un état superposé jusqu'à. prochainidek桁目が1ならば後ろde|\varphi\rangleÀU^kPostuler. Ensuite, sur le même principe que le test Adamal|i\rangle\rightarrow e^{2\pi ik\lambda}|i\rangleÀなります。これをk = 1, 2, \cdots mで繰り返すことで、上位mビットÀ上de状態を実現することができます！（jを二進数で考えてみてください）回路図は下deようÀなります。回路図を見た方がわかりやすいかもしれません。

スクリーンショット 2020-02-22 17.37.55.png

Application à la factorisation prime

Pourquoi est-il possible d'effectuer une factorisation première une fois le chiffre r obtenu? Tout d'abord, supposons que r est pair (il semble que si vous le prenez au hasard, ce sera pair). Ensuite, les transformations suivantes peuvent être effectuées. $ x^r = 1 \mod N\\ (x^{r/2}-1)(x^{r/2}+1) = 0\mod N $ En d'autres termes(x^{r/2}-1)Quand(x^{r/2}+1)のどちらかはNQuand非自明な公約数を持つこQuandになります。どちらもがN　の倍数Quandなってしまう確率は低いです。公約数はユークリッドの互助法によって、古典計算機で高速に計算できます。そこでU^r = IJe veux faire une matrice qui soit facile,U|i\rangle = |i\cdot x \mod N\rangleQuandなるように定義すれば良いです。ただしi\geq Nについては何もしないこQuandにします。実はこれもユニタリ行列であるこQuandが示せます。これに位相推定アルゴリズムを用いれば位数rが十分な確率で求まります。一つ問題があるのは、位相推定アルゴリズムでは、固有ベクトルを利用していましたが、今回はわかりません。しかし、入力Quandしては\left|1\right>Est suffisant. Parce que, si elle est développée avec un vecteur propre, la valeur obtenue par l'algorithme d'estimation de phase est l'une des valeurs propres, et l'une d'entre elless/r (s = 0, 1, \dots r-1)Quandいう形で表せるため、連分数アルゴリズムによってrを高速に求められるからです(s = 0Ignorer si)。連分数アルゴリズムは小数を連分数で近似するこQuandでもっQuandもらしい分数Quandしての形を推定します。詳しいこQuandはcontinued fraction algorithmでググりましょう。一応実装は後に載せてあります。

Implémentation dans Qiskit

Eh bien, voici la production. Exécutons l'algorithme que nous avons vu ci-dessus dans un simulateur et factorisons $ N = 15 $ en $ x = 4 $. Cette fois, nous utiliserons une bibliothèque de calcul quantique appelée qiskit. Pour plus d'informations sur qiskit, consultez la Documentation officielle. Toute exécution est effectuée sur le notebook jupyter.

La partie informatique quantique est la suivante. L'implémentation de U mentionnée dans le chapitre précédent, mais comme il est difficile d'implémenter l'arithmétique générale des restes, nous avons profité du fait que $ N = 15, x = 4 $ ($ {U} ^ {2 ^). Pour i} $, j'ai également utilisé le fait que le chiffre est 2, donc je l'ai omis ...)

from qiskit import *
from qiskit.providers.ibmq import least_busy
from qiskit.visualization import plot_histogram
from qiskit.tools.monitor import job_monitor
import math

q = QuantumRegister(8, "q")
c = ClassicalRegister(4, "c")
circuit = QuantumCircuit(q, c)
circuit.x(7)
#Hadamard transform
for i in range(4):
    circuit.h(i)
#U4^1 gate
circuit.cswap(3, 4, 6)
circuit.cswap(3, 5, 7)
circuit.barrier()
#U4^2 gate
#U4^4 gate
#U4^8 gate
circuit.barrier()
#inverse quantum Fourier transform
circuit.swap(0, 3)
circuit.swap(1, 2)
circuit.h(3)
circuit.cu1(-np.pi/2, 3, 2)
circuit.h(2)
circuit.barrier()
circuit.cu1(-np.pi/4, 3, 1)
circuit.cu1(-np.pi/2, 2, 1)
circuit.h(1)
circuit.barrier()
circuit.cu1(-np.pi/8, 3, 0)
circuit.cu1(-np.pi/4, 2, 0)
circuit.cu1(-np.pi/2, 1, 0)
circuit.h(0)
circuit.barrier()
#measure
for i in range(4):
    circuit.measure(q[i], c[3-i])#X en binaire=J'essaye d'être q1q2q3q4
circuit.draw(output='mpl')

shor_algorithm.png

Maintenant, le reste est la partie de calcul classique. J'ai implémenté l'expansion continue de la fraction comme suit (je suis assez méfiant parce que je l'ai juste écrit correctement et essayé un petit échantillon ...). J'essaie de terminer lorsque l'erreur relative est inférieure à eps.

eps = 0.01
def continued_fractions_algorithm(x):
    res = [int(x)]
    x-=int(x)
    if x/(res[0]+0.1)>eps:
        a = continued_fractions_algorithm(1/x)
        res+=a
    return res

Maintenant, estimons la quantité de calcul (en tant qu'ordinateur quantique). En supposant que le nombre naturel dont vous voulez faire le facteur premier est $ n $ bit, la partie transformée de Fourier discrète est $ O (n ^ 2) $ et la partie algorithme d'estimation de phase est $ O (n ^ 3) $. La partie classique ne devient pas un goulot d'étranglement, j'ai donc pu la résoudre en un temps polypole de $ O (n ^ 3) $ au total! Après cela, si vous exécutez le code suivant,

def shor_algorithm(use_simulator):
    if use_simulator:
        backend = BasicAer.get_backend('qasm_simulator')
    else:
        backend = IBMQ.get_provider().get_backend('ibmq_16_melbourne')
    flag = False
    job = execute(circuit, backend, shots = N)
    job_monitor(job)
    result = job.result()
    counts = result.get_counts(circuit)
    measures = np.array(list(map(lambda x:int(x, 2), counts.keys())), dtype = np.int64)
    probs = np.array(list(counts.values()))/N
    for i in range(5):
        output = np.random.choice(measures, p = probs)
        a = continued_fractions_algorithm(output/2**4)
        r , s =1,  a[-1]
        for i in range(len(a)-1)[::-1]:
            r, s = s, a[i]*s+r 
        if r % 15 == 0 or s == 0:
            continue
        d = math.gcd(15, 4**(r-1)-1)
        if d != 1:
            flag = True
            break
    plot_histogram(result.get_counts())
    if flag:
        print('{0} devides 15 with r = {1}'.format(d, r))
    else:
        print('the algorithm failed')    
    return result
 
%matplotlib inline
use_simulator = True
result = shor_algorithm(use_simulator)
plot_histogram(result.get_counts())
スクリーンショット 2020-02-21 23.16.59.png

Et réussi l'affacturage!

Calcul sur la machine réelle

Vous pouvez utiliser IBM Q, un ordinateur quantique gratuit, à partir de qiskit. La page officielle est ici. Vous devez créer un compte pour l'opération.

Tout d'abord, exécutez le code suivant.

from qiskit import IBMQ
my_token = ""
IBMQ.save_account(my_token)
provider = IBMQ.load_account()

Dans my_token, saisissez le token obtenu depuis Mon compte sur la page officielle.

Puisque j'utilise 8qubit cette fois, j'utiliserai ibmq_16_melbourne. Cela prendra un certain temps, mais si vous l'exécutez avec use_simulator = False dans le code ci-dessus,

スクリーンショット 2020-02-21 23.24.04.png

Quoi?

Résumé

Comment était-ce? J'ai essayé l'affacturage avec un ordinateur quantique cette fois, mais comme nous l'avons vu dans le chapitre précédent, il y a une erreur considérable dans la machine réelle. Bien sûr, cette fois, j'essaie avec un modèle simple que tout le monde peut utiliser, mais si même la factorisation de 15 est difficile, il semble qu'il faudra du temps pour que l'ordinateur quantique soit mis en pratique.

référence

Quantum Native Dojo https://dojo.qulacs.org/ja/latest/ Kenjiro Miyano, Akira Furusawa, Introduction aux ordinateurs quantiques Japan Critics 2016 Michael A. Nilsen,Isaac L. Chuang Quantum Computation and Quantum Information 10th Anniversary Edition 2010

Recommended Posts

Qu'est-ce que l'algorithme Shore? Est-il vrai qu'un ordinateur quantique peut effectuer une factorisation première en temps polynomial? Je l'ai cherché!
J'ai pensé "Qu'est-ce que Linux?", Alors je l'ai recherché.
J'ai enregistré PyQCheck, une bibliothèque qui peut effectuer QuickCheck avec Python, dans PyPI.