ショアの素因数分解をデモするためのスマホアプリの開発

【要旨】量子アルゴリズムの頂点の一つ、ショアの素因数分解については、何度か記事を書いてきた。今回開発したスマホアプリは、その古典的処理と量子アルゴリズムの両方を包含したall-in-oneとなっている。ただし、量子アルゴリズム部分は自作ではなく、量子回路シミュレータQuirkを利用した。QuirkではAPIが提供されていないため、古典的部分と量子部分の連携では、必要なパラメータは人手で授受した。このアプリにより、（対象は小さな整数に限定されるが）一つの画面でショアのアルゴリズム全体の実行を完結できることに意味がある。実際に行ってみると、量子回路シミュレーション結果を確認しながら、人手で必要なパラメータを渡す（完全自動処理ではない）この方法は、理解を深める上で有用な面がある。以下に、それを具体的に示したい。

🔴Shor's Factoring Algorithmの詳細

　ショアのアルゴリズムの理論と計算の詳細はこの記事に書いた。また、その最も重要な部分である位数発見（finding order）は、量子位相推定の応用であるが、これに関してもこちらの記事に詳細を示した。従って、本記事では、今回開発のアプリの概要と使い方についてのみ述べる。

🔴ショアのアルゴリズムのAll-in-oneアプリ

　まず、開発したアプリの全体像をFig.1に示す。この画面は、２つの素数13と17の積として与えた221を、元の２つの素数に分解した例である。古典的計算部分と量子計算部分から成る。

　このアプリはMIT App Inventorで作られた。古典的部分では、量子部分から得た位数（周期）の候補を検証し、妥当であれば、直ちに素因数分解を行うことができる。そうでなければパラメータ（ここではAという名称）を適宜変更して再試行する。

　一方、量子部分では、位数の候補を得るため、量子回路シミュレータQuirkが呼び出される。Quirkの画面は込み入っているが、必要な箇所を指で拡大して見ることができる。
　

🔴アプリの操作手順

　下図のFig.2をご覧いただきたい。２つの素数p,qを与えて、青いボタン「setup R」を押すと目的の整数Rが得られる。次に、赤字のスイッチ「Quirk Q Sim」をonにする。そして、この整数Rを、表示されたQuirkシミュレータへの入力として（手動で）与える。もう一つの（ランダムに選んだ）整数Aも同様にQuirkに与える。このQuirkの量子回路は、f(x) = A^x mod Rの位数（すなわち、周期）の候補を見つけるように作られている。全部で14-qubitの構成（問題設定用に8-qubit、解答用に6-qubit）である。

　次に、Fig.3に示すように、Quirkシミュレーションの結果（測定結果）として、2⁸= 256個の基底のうち、4個だけがそれぞれ25%の確率で出現した。画面を拡大して見ると、その一つの基底 |010000⟩が、位数を与える候補であることが分かる。それを２進ビット列"010000"として、画面上部の窓に設定する。

　続けて、Fig.4に示すように丸い「Shor」ボタンを押す。するとこの２進ビット列が10進小数に変換され、さらに、連分数近似法により有理数（分数s/r）に変換される。その分母rが位数の候補となる。この例（N=221, A=18）では、s=1、r=4であった。位数としての妥当性が確認できるので、すでに述べた通り、 GCD(A^r/2+1, R)=13とGCD(A^r/2-1, R)=17が得られて、素因数分解完了！

　完全自動処理ではないが、このアプリの一つの画面だけで、ショアの素因数分解の全体をデモできることは意味があるのではないか！

🔴Shor's Algorithmは確率的

　ここまでにショアのアルゴリズムの全貌を見た。これは確率的アルゴリズムである。実際、上記の条件で実行された別の結果は、妥当な位数を与えず、最終的に素因数分解が失敗した。そのような例をFig.5に示す。

　しかし、完全な量子コンピュータを使った実行においては、十分に少ない試行で正解が得られるという事実がある。その詳細は、Nielsen & Chuang [1]に叙述されている。

【補足】

　今回もMIT App Inventorをとても有効に利用できた。外部の量子回路シミュレータQuirkをWebViewerから簡単に呼び出せることは素晴らしい。一方、f(x) = A^x mod R に関係する処理を全てApp Inventorで作るとブロック数が増えて見通しが悪くなる。計算がオーバーフローしないように、Modular Exponentiation Methodを使う必要もある。そこで、今回は、これらの大部分をJavascripで作成し、それをApp Inventorから呼び出している。このような、Javascriptとの連携機能も有用である。

　このアプリの作成にあたっては、Wong[2]の第７章「Quantum Algorithms」とBurd[3]の第９章を参考にさせていただいた。感謝申し上げる。

References

[1] Michael A. Nielsen and Isaac L. Chuang: Quantum Computation and Quantum Information - 10th Anniversary Edition, Cambridge University Press, 2010 (First published 2000).

[2] Thomas G. Wong: Introduction to Classical and Quantum Computing, Rooted Grove, 2022.

[3] Barry Burd: Quantum Computing Algorithms -Discover how a little math goes a long way, Packt Publishing, 2023.

https://users.drew.edu/bburd/quantum/