Challenge2021の第二問「ショアのアルゴリズム」を解説します。問題はこちらから入手できます。日本語翻訳もしていただいているのでチャレンジできなかった方も気軽にご覧下さい。GitHub.github.comスポンサーリンク目次ショアのアルゴリズムとは問題の前提を理解する問題を解いていく量子回路を実行して位数を求めるショアのアルゴリズムとはショアのアルゴリズムとは素因数分解を量子コンピューターで効率的に解くためのアルゴリズムで、おそらく社会的には最も注目されているかもしれません。いうのも量子コンピューターが実現すると暗号が破られるとよく言われていますが、実はその主役となっているのがこのショアのアルゴリズムだからです。現在のRSA暗号は大きな数の素因数分解が古典コンピューターでは計算が困難であるという特性を利用しているため、素因数分解が効率的に解くことが出来るとRSA暗号は破られてしまう可能性があるのです。問題の前提を理解する第二問では35を因数分解するアルゴリズムの作成をゴールとしていますが、ショアのアルゴリズムをゼロから作り上げることを目的にはしていないことに注意が必要です。問題文に「ズル(cheat)」とあるように、今回の問題は位数という素因数分解にあたって最も重要な要素を既に与えられた状態からスタートしています。今回の問題は量子回路を作ってショアのアルゴリズムが正しく動作するか検証することが問題となっています。前提として与えられた位数とはそもそも何か説明します。位数とは整数$N$を法とする共通の因数を持たない整数$x$に対して以下の式を満たす最小の整数$r$を指します。1$素因数分解は一般的に位数発見問題に帰着され、位数を発見することが最重要課題となります。位数さえ発見さえしてしまえば素因数分解は簡単です。0$であるか、$x^{r/2}\pm1$が$N$の因数を持つかということを表します。$x^{r/2}\pm1$と$N$との公約数を求めることで$N$の因数を得ることができ、これを繰り返すことで最終的に素因数へと分解することが出来ます。Challengeの問題ではこの位数$r$が前提として与えられているため「ズル」と表現しているのです。今回は35の位数として$r=4$が与えられていますね。問題では位数を発見するためのサブルーチンとなるユニタリ演算を考えることが求められています。is/r)$と与えられます。この演算を満たすような量子回路を作成しましょうという話です。問題を解いていくでは実際に問題に取り組みます。最初は次のような位数4の下、35の法として13倍する演算を実現する量子回路を作成します。アウトプットは入力を13倍して35で割った余りとなっています。|27\rangle→|11\rangle$)すると、最終的に満たすべき式は下のようになります。|00\rangle\end{aligned}$$状態変化を見ると、右の量子ビットは必ず反転し、左の量子ビットは右の量子ビットが1だと反転して0だと何もしないです。以上を踏まえると次のような回路が一例として考えられます。35")cu.ccx(0,1,2)cu.cx(0,1)基本的にはこのような考え方で問題は解き進めることが出来ます。続いてまた量子回路を作っている理由は、位数発見サブルーチンの固有値を求める際に、一定の精度を出すために$n$個の量子ビットを使って固有値を推定しようとした場合、$U^{2^n}$を実行する回路を作る必要があるためです。詳しくはユニタリ演算の固有値を推定する位相推定アルゴリズムで調べてみてください。問題文中で位相推定という言葉が使われているのはそのためです。今回使用を想定している量子コンピューター実機は5量子ビット存在していて、2つは状態のエンコーディングに使用しているため、残りの3量子ビットを使用して位数(固有値)を推定しようというわけです。いうことで同様に$U^2$と$U^4$を実行する回路を作ればいいということになります。次の問題では同じように考えて以下の演算を満たす量子回路を考えます。|01\rangle\end{aligned}$$と言っても求める回路は$U^2$なので先ほどの回路を2つ続ければよいはずですね。t)cu2.ccx(0,1,2)cu2.cx(0,1)cu2.ccx(0,1,2)cu2.cx(0,1)最後は$U^4$です。|11\rangle\end{aligned}$$こちらも同じように$U$を4回続けても問題ありませんが、問題文のヒントにあるようによく見ると全てのインプットとアウトプットで状態の変化が起きていません。これは何もゲート操作をしていないのと同等です。こんな風に書いても正解になるはずですね。t)以上の回路を組み合わせて位数を発見するサブルーチンの量子回路を組み立てます。一般に量子位相推定の回路は下のように作られます。従って今回の回路は下のように作ることが出来ます。$U^4$はゲート操作を含まないため回路上では表現されません。量子回路を実行して位数を求めるでは作成したこの回路を実際の実機(santiego)で実行してみましょう。qasm_sim.run(tqc).result().get_counts()plot_histogram(counts)実行結果はノイズが乗っているものの0,2,4,8の観測確率が大きく、ほぼ等確率で観測されました。is/r)$を位相推定アルゴリズムを通して$2^n\cdot\frac{s}{r}$が観測されています。今回は$n=3$です。1/2$が当てはまるので$r$は4であろうと推定することが出来ます。このように問題で与えられていた位数$r$が正しいことを確かめることが出来ました。量子コンピュータ【初心者向け】量子コンピュータはどんな分野に応用されるのか量子コンピュータが登場すると色々世界が変わるというけど、一体何が変わるの?私の仕事の業界も影響が出るんでしょうか?以上の...2021.09.22量子コンピュータ量子コンピュータ【Qiskit】グローバーのアルゴリズムをゼロから実装する量子アルゴリズムとしてよく登場するグローバーのアルゴリズムをQiskitを使ってゼロから実装する方法を紹介します。世界中で様々なアプローチで研究・開発が進められている日進月歩の先端技術、量子コンピュータ。この記事では位相キックバックとは何か、そしてなぜ重要なのかを5分で理解出来る分量で紹介します。コメントをキャンセルメールアドレスが公開されることはありません。※サイト上に表示された文字を入力してください。Advocate量子コンピュータのコミュニティ運営・イベント登壇にて活動中。本ブログの内容は個人の意見であり、会社を代表するものではありません。量子コンピュータお問い合わせ。