{
"cells": [
{
"cell_type": "markdown",
"id": "78090c95-8fea-4731-a74a-515150e4f899",
"metadata": {},
"source": [
"---\n",
"title: \"ショアのアルゴリズム\"\n",
"description: \"合成数を因数分解するためにショアのアルゴリズムを使用する方法を学びましょう。\"\n",
"---\n",
"\n",
"{/* cspell:ignore checkmark */}\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "64abf08d-8e69-41f9-b802-8c0fbbc37555",
"metadata": {},
"source": [
"\n",
"\n",
"# ショアのアルゴリズム\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "c257cbc3-7730-40cc-a240-19e57033d582",
"metadata": {},
"source": [
"このQiskit in Classroomsモジュールでは、学生は以下のパッケージがインストールされた動作 Python 環境を用意する必要があります：\n",
"\n",
"* v2.1.0`qiskit` またはそれ以降\n",
"* v0.40.1`qiskit-ibm-runtime` またはそれ以降\n",
"* v0.17.0`qiskit-aer` またはそれ以降\n",
"* `qiskit.visualization`\n",
"* `numpy`\n",
"* `pylatexenc`\n",
"\n",
"上記のパッケージを設定およびインストールするには、 [Qiskitのインストール](/docs/guides/install-qiskit)ガイドを参照してください。\n",
"実際の量子コンピュータでジョブを実行するには、学生は 「[アカウント IBM Cloud 設定](/docs/guides/cloud-setup)ガイド」の IBM Quantum® 手順に従ってアカウントを設定する必要があります。\n",
"\n",
"このモジュールはテストされ、3秒間のQPU時間を消費しました。 これはあくまで概算です。 実際の使用状況は異なる場合があります。\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "500d10c9-17ca-4787-90e0-4c57bf86c80d",
"metadata": {},
"outputs": [],
"source": [
"# Uncomment and modify this line as needed to install dependencies\n",
"#!pip install 'qiskit>=2.1.0' 'qiskit-ibm-runtime>=0.40.1' 'qiskit-aer>=0.17.0' 'numpy' 'pylatexenc'"
]
},
{
"attachments": {},
"cell_type": "markdown",
"id": "72231ac3-5b60-4bcb-a072-0c2ecdd176aa",
"metadata": {
"jp-MarkdownHeadingCollapsed": true
},
"source": [
"\n",
"\n",
"## 概要\n",
"\n",
"初期の頃 1990s、量子コンピュータが従来のコンピュータでは困難な問題を解決する可能性に、高まる期待が寄せられていた。 数人の有能な計算機科学者が、特定のニッチで人為的な問題に対して量子コンピューティングの威力を示すアルゴリズムを考案していたが、この分野に革命をもたらすこと間違いなしの、量子コンピューティングの単一の「キラーアプリ」を誰も発見していなかった。 それが、1994年にピーター・ショーが、現在「ショーのアルゴリズム」と呼ばれる大数の因数分解法を考案するまでは、そうだった。\n",
"\n",
"当時、大きな数の素因数を見つけることが古典的なコンピュータにとって極めて困難であることはよく知られていた。 実際、インターネットのセキュリティプロトコルはこの難しさに依存していた。 ショーは、より困難な手順の一部を理論上の将来の量子コンピューターに委ねることで、これらの要素を指数関数的に効率的に見つける方法を見出した。\n",
"\n",
"このモジュールでは、ショアのアルゴリズムについて探求します。 まず、アルゴリズムの背景をもう少し説明し、解決する問題を形式化し、サイバーセキュリティとの関連性を説明します。 次に、モジュラー数学の基礎と、それを因数分解問題に応用する方法を解説します。因数分解が「順序探索」と呼ばれる別の問題に還元されることを示します 前回のモジュールで学んだ量子フーリエ変換と量子位相推定がどのように活用されるかを示し、それらを用いて順序探索問題を解決する方法を説明します。\n",
"\n",
"ついに、実際の量子コンピュータでショアのアルゴリズムを実行します！ ただし、このアルゴリズムが真に有用となるのは、大規模で耐障害性のある量子コンピュータが実現した時であり、それはまだ数年先の話であることを念頭に置いておく必要がある。 では、アルゴリズムの動作を説明するために、小さな数を因数分解してみましょう。\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "22a38013-7bd5-46db-9a44-e89d66c2d06b",
"metadata": {},
"source": [
"\n",
"\n",
"## ファクタリング問題\n",
"\n",
"ファクタリング問題の目的は、数 $N$ の素因数を見つけることです。一部の数 $N$ については、これは非常に簡単です。 例えば、 $N$ が偶数の場合、その素因数の1つは2である。 $N$ が素数の冪乗、すなわち $N=p^k$ となる素数 $p$ が存在するならば、 $p$ を見つけるのも比較的容易である：単に $N$ の $k^{\\text{th}}$ 乗根を近似し、 $p$ となり得る近傍の素数を探すだけでよい。\n",
"\n",
"古典的なコンピュータが苦戦するのは、が奇数でありかつ素数の累乗 $N$\\* でない\\*場合である。 これがショアのアルゴリズムが扱うケースである。 アルゴリズムは、 と $q$ という $p$ 二つの因数を見つけ、 $N=pq$ それらが となるようにする。すべての因数が素数となるまで、再帰的に適用できる。 次のセクションでは、この問題がどのように解決されるかを見ていきます。\n",
"\n",
"\n",
"\n",
"### サイバーセキュリティへの関連性\n",
"\n",
"多くの暗号方式は、大きな数の因数分解が困難であるという事実に基づいて構築されており、今日広く使われているRSAと呼ばれる方式もその一つである。 RSAでは、2つの大きな素数を掛け合わせて生成した公開鍵が作成される。その後、誰でもこの $N = p\\cdot q$ 公開鍵を使ってデータを暗号化できる。 しかし、秘密鍵を所有する $p$ 者だけが、 $q$ そのデータを復号化できる。\n",
"\n",
"もし $N$ が簡単に因数分解できるなら、誰でも と $q$ が何 $p$ であるかを特定し、暗号を解読できるだろう。 しかし、そうではない。 これは有名な難問である。 実際、1024ビット（10進数で309桁） RSA1024 という長さの数と呼ばれる数の素因数は、1991年に10万ドルの懸賞金がかけられて以来、未だに発見されていない。\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "01a0c5d4-922b-47af-8a8b-d87df8d520b0",
"metadata": {},
"source": [
"\n",
"\n",
"## ショアの解法\n",
"\n",
"1994年、ピーター・ショーは量子コンピュータが古典コンピュータよりも指数関数的に効率的に大きな数の因数分解を行えることに気づいた。 彼の洞察は、 *この*因数分解問題と剰余算の関係に依拠していた。 モジュラー算術の簡単な基礎を解説した後、これを用いて を因数分解する方法を見て $N$ いきましょう。\n",
"\n",
"\n",
"\n",
"### 剰余算\n",
"\n",
"剰余算は循環的な数え上げの体系であり、つまり通常の方法、つまり整数0、1、2…から数え始めるものの、 ある時点で、一定期間を経た $N$ 後、カウントが再び開始される。 例でこれがどう機能するか見てみましょう。 例えば、期間が5だとします。 では、カウントしている最中に、通常なら5に到達するところで、代わりに0から再スタートします：\n",
"\n",
"$0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, ...$\n",
"\n",
"これは「 modulo-5 」の世界では、5が0に相当するからである。 私たちは言う。 $5\\bmod 5 \\ = 0$ 実際、5の倍数はすべてに等しい $0\\bmod 5$。\n",
"\n",
"\n",
"\n",
"#### 理解度チェック\n",
"\n",
"以下の質問を読み、答えを考えてから、三角形をクリックして解答を表示してください。\n",
"\n",
"\n",
" \n",
" 次の問題を剰余算を用いて解け：\n",
"\n",
" あなたは午前8時に大陸横断の長い列車の旅に出発します。 列車の旅は60時間かかります。 到着する時間はいつですか？\n",
"
\n",
"\n",
" **回答:**\n",
"\n",
" 1日は24時間であるため、その期間は24です。 したがって、この問題は剰余算として次のように表せます：\n",
"\n",
" $(8+60)\\text{mod}(24) = 20$\n",
"\n",
" では、目的地には20:00、つまり午後8時に到着することになります。\n",
" \n",
"\n",
"\n",
"\n",
"#### $\\mathbb{Z}_N$ および $\\mathbb{Z}_N^*$\n",
"\n",
"しばしば、二つの集合 $\\mathbb{Z}_N$ と を導入することが有用である。 $\\mathbb{Z}_N$ は単に $\\mathbb{Z}_N^*$ 「剰余 $N$ 」の世界に存在する数の集合である。 例えば、私たちが数えていたとき modulo-5、集合はとなる $\\mathbb{Z}_5=\\{0,1,2,3,4\\}$。別の例： $\\mathbb{Z}_{15} = \\{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14\\}$。の要素に対して加法と乗法（剰余法 $N$ ）を実行でき、 $\\mathbb{Z}_N$ これらの演算の結果もまたの要素となる $\\mathbb{Z}_N$ ため、 *は環*と呼ばれる数学的対象 $\\mathbb{Z}_N$ となる。\n",
"\n",
"ショアのアルゴリズムにおいて、我々が特に注目する特別な $\\mathbb{Z}_N$ 部分集合が存在する。 それは、各要素と の最大公約 $N$ 数が 1 となる $\\mathbb{Z}_N$ ような の部分集合であり、したがって各要素は と「互いに素」である。これらの数の集合を、剰余乗法演算 $N$ とともに取り上げると、これは*群*と呼ばれる別の数学的対象を形成する。 この群をと呼ぶ $\\mathbb{Z}_N^*$。実は（ $\\mathbb{Z}_N^*$ 一般に有限群において）、任意の要素を選び、を $a \\in \\mathbb{Z}_N^*$ 繰り返し自身 $a$ と乗算すると、最終的には必ず数を得る $1$。を得るために必要 $a$ となる最小 $1$ の乗算回数を、 $a$\\*\\* の\\*\\*位数と呼ぶ。この事実は、後述する因数分解の方法に関する議論において非常に重要となる。\n",
"\n",
"\n",
"\n",
"#### 理解度チェック\n",
"\n",
"以下の質問を読み、答えを考えてから、三角形をクリックして解答を表示してください。\n",
"\n",
"\n",
" \n",
" とは何ですか $\\mathbb{Z}_{15}^*$？\n",
"
\n",
"\n",
" **回答:**\n",
"\n",
" $\\mathbb{Z}_{15}^* = \\{1,2,4,7,8,11,13,14\\} $\n",
"\n",
" 以下の番号を除外しました：\n",
"\n",
" $$\n",
" \\begin{aligned}\n",
" 3: GCD(3,15)=3 \\\\\n",
" 5: GCD(5,15)=5 \\\\\n",
" 6: GCD(6,15)=3 \\\\\n",
" 9: GCD(9,15)=3 \\\\\n",
" 10: GCD(10,15)=5 \\\\\n",
" 12: GCD(12,15)=3 \\\\\n",
" \\end{aligned}\n",
" $$\n",
" \n",
"\n",
"\n",
" \n",
" の要素それぞれの順序 $\\mathbb{Z}_{15}^*$ は何ですか？\n",
"
\n",
"\n",
" **回答:**\n",
"\n",
" 順序とは、各要素 に対して $r$ $a^r\\text{mod}(15)=1$ となるような $a$ 最小の整数である。\n",
"\n",
" $$\n",
" \\begin{aligned}\n",
" 1^1\\text{mod}(15) = 1, r=1 \\\\\n",
" 2^4\\text{mod}(15) = 1, r=4 \\\\\n",
" 4^2\\text{mod}(15) = 1, r=2 \\\\\n",
" 7^4\\text{mod}(15) = 1, r=4 \\\\\n",
" 8^4\\text{mod}(15) = 1, r=4 \\\\\n",
" 11^2\\text{mod}(15) = 1, r=2 \\\\\n",
" 13^4\\text{mod}(15) = 1, r=4 \\\\\n",
" 14^2\\text{mod}(15) = 1, r=2 \\\\\n",
" \\end{aligned}\n",
" $$\n",
"\n",
" ただし、我々がの数字の順序を見つけられた一方で $\\mathbb{Z}_{15}^*$、より大きなでは $N$、これは一般的に容易な作業ではないことに注意されたい。これが因数分解問題の核心であり、量子コンピュータが必要とされる理由である。 ノートブックの残りの部分を進めていくうちに、その理由がわかるでしょう。\n",
" \n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "c19d2032-3c40-48ee-823b-607b1ed8b4f0",
"metadata": {},
"source": [
"\n",
"\n",
"### モジュラー算術を因数分解問題に適用する\n",
"\n",
"と $q$ を満たす因数を見つける鍵は、 *ある他の*整数 $p$ を見つける $x$ ことに帰着する $N=pq$\n",
"\n",
"$x^2 \\equiv 1 \\bmod N$ そして $x \\not\\equiv \\pm 1 \\bmod N.$\n",
"\n",
"を求めると、どのようにして因子 $p$ $x$ と を見つけるのに $q$ 役立つのか？ ここでその論証を順を追って見ていこう。 したがって $x^2 \\equiv 1 \\bmod N$、それはつまり、 $x^2 - 1 \\equiv 0 \\bmod N $ である $x^2 - 1$。言い換えれば、はの倍数である $N$。したがって、ある整数に対して $l$、\n",
"\n",
"$x^2 - 1 = l N$\n",
"\n",
"因数 $x^2 - 1$ 分解すると次の式が得られます：\n",
"\n",
"$(x+1)(x-1) = l N$\n",
"\n",
"初期の仮定から、$x \\not\\equiv \\pm 1 \\bmod N$であることがわかっています。したがって、$N$は$x+1$や$x-1$のいずれにも割り切れません。したがって、$N$の2つの因数である$p$と$q$は、それぞれ$x-1$および$x+1$に割り切れる必要があります。つまり、$p$が$x-1$の因数であり、$q$が$x+1$の因数であるか、その逆です。したがって、$N$と$x-1$および$x+1$との最大公約数（GCD）を計算すれば、因数$p$と$q$が得られます。2つの数値間のGCDを計算することは、例えば[ユークリッドのアルゴリズム](https://en.wikipedia.org/wiki/Euclidean_algorithm)を使って実行できる、古典的に簡単な作業である。\n",
"\n",
"\n",
"\n",
"#### 理解度チェック\n",
"\n",
"以下の質問を読み、答えを考えてから、三角形をクリックして解答を表示してください。\n",
"\n",
"\n",
" \n",
" 上記の論理の各ステップを理解するのは難しいかもしれないので、具体例を使って考えてみましょう。 と $N=15$ $x=11$ を使用する。まず、と $x^2 \\equiv 1 \\text{mod}(N)$ が成立することを確認する。 $x \\not\\equiv \\pm 1 \\bmod N$ その後、各ステップを順に検証を続ける。 最後に、 を計算し $\\text{GCD}(11\\pm1,15)$、それらが の因数 $15$ であることを確認する。\n",
"
\n",
"\n",
" **回答:**\n",
"\n",
" $11^2 = 121$、つまり $15*8 + 1$、したがって $11^2\\bmod 15 = 1$。 $\\checkmark$\n",
"\n",
" $ 11 - 1 = 10$ これはに等しくない $0\\bmod 15$。 $\\checkmark$\n",
"\n",
" $ 11 + 1 = 12$ これはに等しくない $0\\bmod 15$。 $\\checkmark$\n",
"\n",
" さて、ある整数 に対して $(x+1)(x-1) = l N$ が成り立つ $l$ ことがわかっている。これは と $x$ を代入することで $N$ 確認できる： $(12)(10) = l 15$ の場合 $l = 8$。 $\\checkmark$\n",
"\n",
" さて、と $\\text{GCD}(12,15)$ を計算する必要があります $\\text{GCD}(10,15)$。\n",
"\n",
" $$\n",
" \\begin{aligned}\n",
" \\text{GCD}(12,15) = 3 \\\\\n",
" \\text{GCD}(10,15) = 5\n",
" \\end{aligned}\n",
" $$\n",
"\n",
" では、私たちの因数 $15$ を見つけました！\n",
" \n",
"\n",
"\n",
"\n",
"### アルゴリズム\n",
"\n",
"整数 $x$ を見つけることが の因数分解に役立つ $x^2 \\equiv 1\\bmod N$ $N$ ことを確認したので、ショアのアルゴリズムを順を追って説明できる。 要するに、見つけることに帰着する $x$ ：\n",
"\n",
"1. **ランダムな整数を選ぶ**\n",
" ランダムな整数を選び、その整数が $a$ となるようにする $1 < a < N$。\n",
"\n",
"* 古典的に $\\text{GCD}(a, N)$ 計算する。\n",
" * もし $\\text{GCD}(a, N) > 1$、すでに因数を見つけているなら。 待ってください。\n",
" * その他の場合は、続行します。\n",
"\n",
"2. **剰余 $a$ の $r$ 順序を求める**\n",
" $N$ を満たす最小の $r$ 正の整数 $a^r \\equiv 1 \\pmod N$ を見つける。\n",
"\n",
"3. **注文が偶数かどうかを確認する**\n",
"\n",
"* が奇数 $r$ の場合、ステップ1に戻り、新しい $a$ を選択する。\n",
"* が偶数の場合 $r$、手順4に進む。\n",
"\n",
"4. **計算 $x = a^{r/2} \\bmod N$**\n",
"\n",
"* とを確認してください $x \\not\\equiv 1 \\pmod N$。 $x \\not\\equiv -1 \\pmod N$\n",
" * もし $x \\equiv \\pm 1 \\pmod N$、ステップ1に戻り、新しいを選択してください $a$。\n",
"* そうでない場合は、最大公約数（gcd）を計算して因数を抽出する：\n",
"\n",
"$$\n",
"p = \\text{GCD}(x-1, N), \\quad q = \\text{GCD}(x+1, N)\n",
"$$\n",
"\n",
"これらはの非自明な $N$ 因数となる。\n",
"\n",
"5. **必要に応じて再帰的に因数分解する**\n",
"\n",
"* および／または $q$ が素数でない $p$ 場合、それらを完全に因数分解するためにアルゴリズムを再帰的に適用する。\n",
"* すべての因子が素数になると、因数分解は完了する。\n",
"\n",
"この手順に基づけば、このタスクを完了するために量子コンピュータが必要である理由が明らかではないかもしれない。 ステップ2、つまり modulo $a$ における順序を見つけることは、従来 $N$ 非常に困難な問題であるため、それが必要なのです。 複雑さは数の増加に伴い指数 $N$ 関数的に拡大する。しかし量子コンピュータを用いれば、量子位相推定を活用するだけでこれを解決できる。 ステップ4、2つの整数の最大公約数を見つけることは、古典的には実はかなり簡単なことだ。 したがって、量子コンピュータの処理能力が実際に必要となるのは、順序探索のステップのみである。 ファクタリング問題は順序探索問題に「還元される」と言う。\n",
"\n"
]
},
{
"attachments": {},
"cell_type": "markdown",
"id": "d4771244-0604-4b2e-bd99-a52280456f43",
"metadata": {},
"source": [
"\n",
"\n",
"### 難しい部分：順序の特定\n",
"\n",
"それでは、量子コンピューターを用いて探索を行う方法について見ていきましょう。 まず、「順序」という言葉が何を意味するのかを明確にしましょう もちろん、この順序が数学的に何を意味するかは既に説明しました：それは を満たす $r$ 最初の非零整数です。 $a^r = 1 \\pmod N.$ しかし、この概念についてもう少し直感的に理解を深められないか考えてみましょう。\n",
"\n",
"十分小さい に対しては、各累乗を計算し、その数を $a$ で $N$ 割った余りを $N$ 求め、 を満たす累乗 $r$ が見つかった時点で停止することで $a^r = 1 \\text{mod}(N)$、その位数を決定できる。これが、上記の例 で私たちが実施した手法である $N=15$。 いくつかのサンプル値の $a$ と について $N$、これらのモジュラー乗のグラフを見てみましょう：\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"何か気づいた？ これらは周期関数です！ そして順序は $r$ 周期と同じだ！ **したがって、オーダー探索は周期探索と同等である。**\n",
"\n",
"量子コンピュータは関数の周期を求めるのに非常に適している。 このために、量子位相推定と呼ばれるアルゴリズム的サブルーチンを使用できます。 前回のモジュールでは、量子位相誤差（QPE）と量子フーリエ変換との関係について議論しました。 詳細な復習については、QFTモジュールまたはジョン・ワトラスの量子アルゴリズム講座における[量子位相推定](/learning/courses/fundamentals-of-quantum-algorithms/phase-estimation-and-factoring/shor-algorithm)の講義を参照してください。 手順の概要を説明します：\n",
"\n",
"量子位相推定（QPE）では、ユニタリ演算子 $U$ とその固有状態 から始める。次に、QPEを用いて $|\\psi\\rangle$ 対応する固有値を近似する。演算子がユニタリであるため $e^{2\\pi i \\theta}$、この固有値は の形で表される。したがって、固有値を求めることは、周期関数における $\\theta$ の値を求めることに等しい。 回路は次のようになります：\n",
"\n",
"\n",
"\n",
"制御量子ビットの数（上図の上位 $m$ 量子ビット）が近似の精度を決定する。\n",
"\n",
"Shorのアルゴリズムでは、ユニタリー演算子に対して量子位相誤差 $M_a$ （QPE）を用いる：\n",
"\n",
"$ M_a|y\\rangle \\equiv |ay \\mod N \\rangle .$\n",
"\n",
"ここで、 $|y\\rangle$ は多量子ビットレジスタの計算基底状態を表し、量子ビットの二進値は整数 に対応 $y$ する。例えば、 かつ $N=15$ の場合、 $|y\\rangle$ は4量子ビット $y = 2$ 基底状態 で表される。なぜなら、15までの数値を符号 $|0010\\rangle$ 化するには4量子ビットが必要だからである。 （この概念が不慣れな場合は、量子状態の二進符号化に関する復習として、 [入門モジュール「教室でのQiskit」](/learning/modules/quantum-mechanics/get-started-with-qiskit) を参照してください。）\n",
"\n",
"さて、このユニタリ演算子の固有状態を求めなければなりません。 状態から開始した場合 $|1\\rangle$、を順次適用する $U$ たびにレジスタの状態が倍増し $a \\pmod N$、回 $r$ 適用後には再び $|1\\rangle$ 状態に到達することがわかる。 例えば、と $N = 35$ $a = 3$ ：\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
"M_3|1\\rangle &= |3\\rangle & \\\\\n",
"M_3^2|1\\rangle &= |9\\rangle \\\\\n",
"M_3^3|1\\rangle &= |27\\rangle \\\\\n",
"& \\vdots \\\\\n",
"M_3^{(r-1)}|1\\rangle &= |12\\rangle \\\\\n",
"M_3^r|1\\rangle &= |1\\rangle\n",
"\\end{aligned}\n",
"$$\n",
"\n",
"したがって、このサイクル（ $|\\psi_j\\rangle$ ）における状態の重ね合わせは、次の形式をとる：\n",
"\n",
"$|\\psi_j\\rangle = \\tfrac{1}{\\sqrt{r}}\\sum_{k=0}^{r-1}{e^{\\frac{2 \\pi i j k}{r}} |a^k \\rangle} $\n",
"\n",
"はすべて の固有状態 $M_a$ である。 （これ以外にも固有状態は存在する。） ただし、我々が関心を持つのは上記の形式のものに限られる\n",
"\n",
"\n",
"\n",
"#### 理解度チェック\n",
"\n",
"以下の質問を読み、答えを考えてから、三角形をクリックして解答を表示してください。\n",
"\n",
"\n",
" \n",
" と $a=2$ に対応するユニタリ演算子の固有状態を求めよ。 $N = 15$\n",
"
\n",
"\n",
" **回答:**\n",
"\n",
" $$\n",
" \\begin{aligned}\n",
" M_2|1\\rangle &= |2\\rangle & \\\\\n",
" M_2^2|1\\rangle &= |4\\rangle \\\\\n",
" M_2^3|1\\rangle &= |8\\rangle \\\\\n",
" M_2^4|1\\rangle &= |1\\rangle \\\\\n",
" \\end{aligned}\n",
" $$\n",
"\n",
" したがって、順序は次の $r=4$ 通りです。私たちが関心を持つ固有状態は、上記で巡った全ての状態の等しい重ね合わせとなり、様々な位相を持ちます：\n",
"\n",
" $$\n",
" \\begin{aligned}\n",
" |\\psi_0\\rangle &= \\frac{1}{2}(|1\\rangle+|2\\rangle+|4\\rangle+|8\\rangle) \\\\\n",
" |\\psi_1\\rangle &= \\frac{1}{2}(e^{2 \\pi i \\frac{0}{4}}|1\\rangle+e^{2 \\pi i \\frac{1}{4}}|2\\rangle+e^{2 \\pi i \\frac{2}{4}}|4\\rangle+e^{2 \\pi i \\frac{3}{4}}|8\\rangle) \\\\\n",
" &= \\frac{1}{2}(|1\\rangle+i|2\\rangle-|4\\rangle-i|8\\rangle) \\\\\n",
" |\\psi_2\\rangle &= \\frac{1}{2}(e^{2 \\pi i \\frac{0}{4}}|1\\rangle+e^{2 \\pi i \\frac{2}{4}}|2\\rangle+e^{2 \\pi i \\frac{4}{4}}|4\\rangle+e^{2 \\pi i \\frac{6}{4}}|8\\rangle) \\\\\n",
" &= \\frac{1}{2}(|1\\rangle-|2\\rangle+|4\\rangle-|8\\rangle) \\\\\n",
" |\\psi_3\\rangle &= \\frac{1}{2}(e^{2 \\pi i \\frac{0}{4}}|1\\rangle+e^{2 \\pi i \\frac{3}{4}}|2\\rangle+e^{2 \\pi i \\frac{6}{4}}|4\\rangle+e^{2 \\pi i \\frac{9}{4}}|8\\rangle) \\\\\n",
" &= \\frac{1}{2}(|1\\rangle-i|2\\rangle-|4\\rangle+i|8\\rangle) \\\\\n",
" \\end{aligned}\n",
" $$\n",
" \n",
"\n",
"仮に量子ビットの状態をこれらの固有状態のいずれかに初期化できたとしよう（ネタバレ：実際にはできない）。 少なくとも、簡単には。 その理由と代わりにできることを、後ほど説明します。 次に、QPEを用いて対応する固有値を推定できる。 $\\theta_j = \\frac{j}{r}$ $\\omega_j = e^{2 \\pi i \\theta_j}$ ここで。その後、単純な式によって $r$ 次数を決定できる：\n",
"\n",
"$r = \\frac{j}{\\theta_j}.$\n",
"\n",
"ただし覚えておいてほしいのは、QPEは*推定値に過ぎない*$\\theta_j$ ということだ——正確な値を与えてくれるわけではない。 推定値は と $r$ を区別できるほど十分に正確である必要がある。制御量子 $r+1$ ビット数 が多ければ $m$ 多いほど、推定値はより正確になる。 授業の最後にある問題では、ある数を因数分解するために必要な $m$ $N$ 最小の数を求めます。\n",
"\n",
"さて、問題を解決しなければなりません。 上記の固有状態の求め方に関する説明はすべて、 $|\\psi_j\\rangle = \\tfrac{1}{\\sqrt{r}}\\sum_{k=0}^{r-1}{e^{\\frac{2 \\pi i j k}{r}} |a^k \\rangle}$ $r$ 固有状態の準備から始まります。しかし、固有 $r$ 状態が何であるかを知らなければ、その準備の仕方もわからないのです。 論理は循環している。 固有状態を*初期化せずに*固有値を推定する方法が必要です。\n",
"\n",
"の固有状態から始める $M_a$ 代わりに、初期状態を2進法 $|1\\rangle$ でに対応する- $n$ 量子ビット状態（つまり、 $|000...01\\rangle$ ）に準備できる。この状態自体は明らかにの固有状態ではない $M_a$ が、全ての固有状態に対する $|\\psi_k\\rangle$ 重ね合わせである：\n",
"\n",
"$|1\\rangle = \\frac{1}{\\sqrt{r}} \\sum\\limits_{k=0}^{r-1}{|\\psi_k\\rangle}$\n",
"\n",
"\n",
"\n",
"#### 理解度チェック\n",
"\n",
"以下の質問を読み、答えを考えてから、三角形をクリックして解答を表示してください。\n",
"\n",
"\n",
" \n",
" が $|1\\rangle$、前回のチェックイン問題で $a=2$ 求めた と $N=15$ の固有状態に対する重ね合わせと等価であることを確認せよ。\n",
"
\n",
"\n",
" **回答:**\n",
"\n",
" 四つの固有状態は次の通りであった：\n",
"\n",
" $$\n",
" \\begin{aligned}\n",
" |\\psi_0\\rangle &= \\frac{1}{2}(|1\\rangle+|2\\rangle+|4\\rangle+|8\\rangle) \\\\\n",
" |\\psi_1\\rangle &= \\frac{1}{2}(|1\\rangle+i|2\\rangle-|4\\rangle-i|8\\rangle) \\\\\n",
" |\\psi_2\\rangle &= \\frac{1}{2}(|1\\rangle-|2\\rangle+|4\\rangle-|8\\rangle) \\\\\n",
" |\\psi_3\\rangle &= \\frac{1}{2}(|1\\rangle-i|2\\rangle-|4\\rangle+i|8\\rangle) \\\\\n",
" \\end{aligned}\n",
" $$\n",
"\n",
" さて\n",
"\n",
" $$\n",
" \\begin{aligned}\n",
" \\frac{1}{\\sqrt{r}} \\sum\\limits_{k=0}^{r-1}{|\\psi_k\\rangle} &= \\frac{1}{2}(|\\psi_0\\rangle + |\\psi_1\\rangle + |\\psi_2\\rangle + |\\psi_3\\rangle ) \\\\\n",
" &= \\frac{1}{4}(|1\\rangle+|2\\rangle+|4\\rangle+|8\\rangle+|1\\rangle+i|2\\rangle-|4\\rangle-i|8\\rangle+|1\\rangle-|2\\rangle+|4\\rangle-|8\\rangle + |1\\rangle-i|2\\rangle-|4\\rangle+i|8\\rangle) \\\\\n",
" &= \\frac{1}{4}(4|1\\rangle) = |1\\rangle\n",
" \\end{aligned}\n",
" $$\n",
" \n",
"\n",
"これはどのように順序を見つける $r$ ことを可能にするのか？ 初期状態が上記の形式のすべての固有状態に対する重ね合わせであるため、QPEアルゴリズムはこれらの固有状態 $\\theta_k$ に対応する各を同時に推定する。 したがって、最終段階での制御 $m$ 量子ビットの測定は、値の近似値を与えることになる。 $k/r$ ここで $k \\in \\{0,1,2,...,r-1\\}$ は、ランダムに選ばれた固有値の一つである。 この回路を数回繰り返し、異なる値のサンプルをいくつか取得 $k$ すれば、すぐにを $r$ 導き出せるだろう。\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "099389d1-1370-472c-af29-a642532beff4",
"metadata": {},
"source": [
"\n",
"\n",
"## Qiskitで実装する\n",
"\n",
"先ほど述べたように、当社のハードウェアは、のような巨大な数を因数分解できる段階 RSA1024 にはまだ至っていません。 アルゴリズムの動作を示すために、小さな数を因数分解してみましょう。 このデモでは、 [ショアのアルゴリズムチュートリアル](/docs/tutorials/shors-algorithm)で紹介されたコードの簡略版を使用します。 詳細を知りたい場合は、チュートリアルをご覧ください。\n",
"\n",
"量子問題を解くための標準的なフレームワークであるQiskitパターンズフレームワークを用いて、アルゴリズムを実行します。 これは4つのステップで構成されています：\n",
"\n",
"1. 問題を量子回路にマッピングする\n",
"2. 量子ハードウェア上で実行される回路を最適化する\n",
"3. 量子コンピュータ上で回路を実行する\n",
"4. 測定値の後処理\n",
"\n",
"\n",
"\n",
"### 1. 地図\n",
"\n",
"を因数分解しましょう $N=15$。互いに素な整数として $a=2$ を選びます。\n",
"\n",
"まず、モジュラー乗算ユニタリを実装する回路を構築する必要があります。 $M_a$ これは実際、実装全体の中で最も難しい部分であり、その方法によっては非常に計算コストがかかる可能性があります。 このため、少しごまかします：私たちは状態から始まっていることを $|1\\rangle$ 知っており、以前のチェックイン質問から、\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
"M_2|1\\rangle &= |2\\rangle & \\\\\n",
"M_2|2\\rangle &= |4\\rangle \\\\\n",
"M_2|4\\rangle &= |8\\rangle \\\\\n",
"M_2|8\\rangle &= |1\\rangle \\\\\n",
"\\end{aligned}\n",
"$$\n",
"\n",
"したがって、これら4つの状態に対して正しい操作を行い、他のすべての状態には手を加えないユニタリを構築する。 これは不正行為です。なぜなら、ユニタリ演算子を簡略化するために $2\\bmod 15$、の順序に関する知識を利用しているからです。 もし私たちが実際に因数が未知の数を因数分解しようとしていたなら、これは不可能だったでしょう。\n",
"\n",
"\n",
"\n",
"#### 理解度チェック\n",
"\n",
"以下の質問を読み、答えを考えてから、三角形をクリックして解答を表示してください。\n",
"\n",
"\n",
" \n",
" 上記の状態をオペレータ $M_2$ がどのように変換するかについての知識を用いて、2つの量子ビットの状態を交換する一連のSWAPゲートから構成されるオペレータを構築せよ。 (ヒント: 各状態 $|i\\rangle$ を二進数で書くことが助けになる。)\n",
"
\n",
"\n",
" **回答:**\n",
"\n",
" 状態に対する作用 $M_2$ を二進法で書き直そう：\n",
"\n",
" $$\n",
" \\begin{aligned}\n",
" M_2|0001\\rangle &= |0010\\rangle \\\\\n",
" M_2|0010\\rangle &= |0100\\rangle \\\\\n",
" M_2|0100\\rangle &= |1000\\rangle \\\\\n",
" M_2|1000\\rangle &= |0001\\rangle \\\\\n",
" \\end{aligned}\n",
" $$\n",
"\n",
" これらの操作はそれぞれ単純なSWAPで実現できる。状態 $0$ $M_2|0001\\rangle$ は量子ビットと状態を交換することで達成される。 $M_2|0010\\rangle$ $1$ 状態は $1$ 量子ビットと状態を交換することで達成 $2$ される。以下同様である。 したがって、行列 $M_2$ を以下のSWAPゲート列に分解できます：\n",
"\n",
" $$\n",
" M_2 = SWAP(0,1)SWAP(1,2)SWAP(2,3)\n",
" $$\n",
"\n",
" 演算子が右から左へ作用することを念頭に置き、各状態においてこれが意図した効果をもたらすことを確認しましょう：\n",
"\n",
" $$\n",
" \\begin{aligned}\n",
" M_2|0001\\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|0001\\rangle \\\\\n",
" &= SWAP(0,1)SWAP(1,2)|0001\\rangle \\\\\n",
" &= SWAP(0,1)|0001\\rangle \\\\\n",
" &=|0010\\rangle \\checkmark \\\\\n",
" M_2|0010\\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|0010\\rangle \\\\\n",
" &= SWAP(0,1)SWAP(1,2)|0010\\rangle \\\\\n",
" &= SWAP(0,1)|0100\\rangle \\\\\n",
" &=|0100\\rangle \\checkmark \\\\\n",
" M_2|0100\\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|0100\\rangle \\\\\n",
" &= SWAP(0,1)SWAP(1,2)|1000\\rangle \\\\\n",
" &= SWAP(0,1)|1000\\rangle \\\\\n",
" &=|1000\\rangle \\checkmark \\\\\n",
" M_2|1000\\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|1000\\rangle \\\\\n",
" &= SWAP(0,1)SWAP(1,2)|0100\\rangle \\\\\n",
" &= SWAP(0,1)|0010\\rangle \\\\\n",
" &=|0001\\rangle \\checkmark \\\\\n",
" \\end{aligned}\n",
" $$\n",
" \n",
"\n",
"この演算子に相当する回路をQiskitでコーディングできるようになりました。\n",
"\n",
"まず、必要なパッケージをインポートします：\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 29,
"id": "95c8d21b-d2e6-45c3-a2d2-a7288db4171f",
"metadata": {},
"outputs": [],
"source": [
"# Import necessary packages\n",
"\n",
"import numpy as np\n",
"from fractions import Fraction\n",
"from math import floor, gcd, log\n",
"\n",
"from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister\n",
"from qiskit.circuit.library import QFTGate\n",
"from qiskit.transpiler import generate_preset_pass_manager\n",
"from qiskit.visualization import plot_histogram\n",
"\n",
"from qiskit_ibm_runtime import QiskitRuntimeService\n",
"from qiskit_ibm_runtime import SamplerV2 as Sampler"
]
},
{
"cell_type": "markdown",
"id": "f8d46443-d3d3-4d27-8026-27974f5d6702",
"metadata": {},
"source": [
"次に、演算子 $M_2$ を作成します：\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 30,
"id": "1396a7ff-718a-4169-9c63-85ae218b58a4",
"metadata": {},
"outputs": [],
"source": [
"def M2mod15():\n",
" \"\"\"\n",
" M2 (mod 15)\n",
" \"\"\"\n",
" b = 2\n",
" U = QuantumCircuit(4)\n",
"\n",
" U.swap(2, 3)\n",
" U.swap(1, 2)\n",
" U.swap(0, 1)\n",
"\n",
" U = U.to_gate()\n",
" U.name = f\"M_{b}\"\n",
"\n",
" return U"
]
},
{
"cell_type": "code",
"execution_count": 31,
"id": "e7521fba-fe3e-45bc-b9ce-fe876bddad33",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
""
]
},
"execution_count": 31,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Get the M2 operator\n",
"M2 = M2mod15()\n",
"\n",
"# Add it to a circuit and plot\n",
"circ = QuantumCircuit(4)\n",
"circ.compose(M2, inplace=True)\n",
"circ.decompose(reps=2).draw(output=\"mpl\", fold=-1)"
]
},
{
"cell_type": "markdown",
"id": "6f1e1a5d-bd34-4379-9237-d91ecba9d435",
"metadata": {},
"source": [
"QPEアルゴリズムは制御 $U$ ゲートを使用する。 では、 *制御*$M_2$ 回路を構築するには、まず $M_2$ 回路を制御対象とする必要があります：\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 32,
"id": "36d1020c-c0af-4211-bd50-be865d057f75",
"metadata": {},
"outputs": [],
"source": [
"def controlled_M2mod15():\n",
" \"\"\"\n",
" Controlled M2 (mod 15)\n",
" \"\"\"\n",
" b = 2\n",
" U = QuantumCircuit(4)\n",
"\n",
" U.swap(2, 3)\n",
" U.swap(1, 2)\n",
" U.swap(0, 1)\n",
"\n",
" U = U.to_gate()\n",
" U.name = f\"M_{b}\"\n",
" c_U = U.control()\n",
"\n",
" return c_U"
]
},
{
"cell_type": "code",
"execution_count": 33,
"id": "5bf4f10d-5d52-406d-b62d-ad4a8d366c02",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
""
]
},
"execution_count": 33,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Get the controlled-M2 operator\n",
"controlled_M2 = controlled_M2mod15()\n",
"\n",
"# Add it to a circuit and plot\n",
"circ = QuantumCircuit(5)\n",
"circ.compose(controlled_M2, inplace=True)\n",
"circ.decompose(reps=1).draw(output=\"mpl\", fold=-1)"
]
},
{
"cell_type": "markdown",
"id": "fd98c560-530f-424f-b8f8-0f9fe9615c5e",
"metadata": {},
"source": [
"これで制御 $U$ ゲートが完成した。 しかし量子位相推定アルゴリズムを実行するには、制御子 $U^2$、制御子 $U^4$、… $U^{2^{m-1}}$、制御子までが必要となる。ここで $m$ は位相推定に使用される量子ビットの数である。 量子ビット数が多いほど、位相推定の精度が高くなる。 位相推定手順には制御量子ビット $m=8$ を使用します。 では、必要なのは：\n",
"\n",
"$$\n",
"M_{a^{2^k}}|y\\rangle \\equiv |a^{2^k} y \\bmod N \\rangle\n",
"$$\n",
"\n",
"ここで、 $k$ インデックスは制御量子ビットに対応する。 $0 \\le k \\le m-1 = 7$ では、のそれぞれの値について $a^{2^k}\\bmod N $ $k$ 計算しましょう：\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 34,
"id": "1463f000-c7ab-4e09-b111-5cb3d279e06b",
"metadata": {},
"outputs": [],
"source": [
"def a2kmodN(a, k, N):\n",
" \"\"\"Compute a^{2^k} (mod N) by repeated squaring\"\"\"\n",
" for _ in range(k):\n",
" a = int(np.mod(a**2, N))\n",
" return a"
]
},
{
"cell_type": "code",
"execution_count": 35,
"id": "ac0f44f1-e5fa-46b8-a1d2-5255ed63e3b9",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[2, 4, 1, 1, 1, 1, 1, 1]\n"
]
}
],
"source": [
"k_list = range(8)\n",
"b_list = [a2kmodN(2, k, 15) for k in k_list]\n",
"\n",
"print(b_list)"
]
},
{
"cell_type": "markdown",
"id": "a2654cb9-a2ad-4947-8441-a1e2799501b8",
"metadata": {},
"source": [
"したがって $a^{2^k} \\bmod N = 1$、 $k \\ge 2$ に対応するすべての演算子（ $M_8$ およびそれ以上）は恒等演算子と同値である。 したがって、もう1つの行列を構築するだけでよい。 $M_4.$\n",
"\n",
"**注：** この簡略化が成立するのは、の順序が $2 \\bmod 15 $ である場合 $4$ に限られる。が成立する $k=2$ （すなわち $2^k = 4$ ）と、その後の演算子の累乗はすべて恒等演算子となる。 一般的に、より大きな数値 $N$ や異なるの選択の場合 $a$、より高い累乗の構築を省略することはできない。 これがこの*例*が玩具例と見なされる理由の一つである：小さな数値だからこそ、より大きなケースでは通用しない近道が可能になるのだ。\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 36,
"id": "29bc2fb5-511d-4593-8c48-7b1c7c7eeed0",
"metadata": {},
"outputs": [],
"source": [
"def M4mod15():\n",
" \"\"\"\n",
" M4 (mod 15)\n",
" \"\"\"\n",
" b = 4\n",
" U = QuantumCircuit(4)\n",
"\n",
" U.swap(1, 3)\n",
" U.swap(0, 2)\n",
"\n",
" U = U.to_gate()\n",
" U.name = f\"M_{b}\"\n",
"\n",
" return U"
]
},
{
"cell_type": "code",
"execution_count": 37,
"id": "ea4fc641-e97c-400d-a761-5f67a0b7d65e",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
""
]
},
"execution_count": 37,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Get the M4 operator\n",
"M4 = M4mod15()\n",
"\n",
"# Add it to a circuit and plot\n",
"circ = QuantumCircuit(4)\n",
"circ.compose(M4, inplace=True)\n",
"circ.decompose(reps=2).draw(output=\"mpl\", fold=-1)"
]
},
{
"cell_type": "markdown",
"id": "f6712a0c-a695-4c1d-a99a-a9fd67a95c92",
"metadata": {},
"source": [
"そして以前と同様に、これを*制御された*$M_4$ 演算子とします：\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 38,
"id": "c8ec99c7-5e03-4623-b6f7-22dae558de04",
"metadata": {},
"outputs": [],
"source": [
"def controlled_M4mod15():\n",
" \"\"\"\n",
" Controlled M4 (mod 15)\n",
" \"\"\"\n",
" b = 4\n",
" U = QuantumCircuit(4)\n",
"\n",
" U.swap(1, 3)\n",
" U.swap(0, 2)\n",
"\n",
" U = U.to_gate()\n",
" U.name = f\"M_{b}\"\n",
" c_U = U.control()\n",
"\n",
" return c_U"
]
},
{
"cell_type": "code",
"execution_count": 39,
"id": "37caf888-276e-4f19-a0d0-59517c5ee44e",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
""
]
},
"execution_count": 39,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Get the controlled-M4 operator\n",
"controlled_M4 = controlled_M4mod15()\n",
"\n",
"# Add it to a circuit and plot\n",
"circ = QuantumCircuit(5)\n",
"circ.compose(controlled_M4, inplace=True)\n",
"circ.decompose(reps=1).draw(output=\"mpl\", fold=-1)"
]
},
{
"cell_type": "markdown",
"id": "db3f989d-ef17-48af-99c6-aae08eb59001",
"metadata": {},
"source": [
"さて、位相推定を用いて量子回路 $2\\bmod 15$ で の位相を特定するために、これらをすべて組み合わせてみましょう：\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 48,
"id": "d1b111c8-1a12-420b-bbc2-4ecdd1ac5a97",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
""
]
},
"execution_count": 48,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Order finding problem for N = 15 with a = 2\n",
"N = 15\n",
"a = 2\n",
"\n",
"# Number of qubits\n",
"num_target = floor(log(N - 1, 2)) + 1 # for modular exponentiation operators\n",
"num_control = 2 * num_target # for enough precision of estimation\n",
"\n",
"# List of M_b operators in order\n",
"k_list = range(num_control)\n",
"b_list = [a2kmodN(2, k, 15) for k in k_list]\n",
"\n",
"# Initialize the circuit\n",
"control = QuantumRegister(num_control, name=\"C\")\n",
"target = QuantumRegister(num_target, name=\"T\")\n",
"output = ClassicalRegister(num_control, name=\"out\")\n",
"circuit = QuantumCircuit(control, target, output)\n",
"\n",
"# Initialize the target register to the state |1>\n",
"circuit.x(num_control)\n",
"\n",
"# Add the Hadamard gates and controlled versions of the\n",
"# multiplication gates\n",
"for k, qubit in enumerate(control):\n",
" circuit.h(k)\n",
" b = b_list[k]\n",
" if b == 2:\n",
" circuit.compose(\n",
" M2mod15().control(), qubits=[qubit] + list(target), inplace=True\n",
" )\n",
" elif b == 4:\n",
" circuit.compose(\n",
" M4mod15().control(), qubits=[qubit] + list(target), inplace=True\n",
" )\n",
" else:\n",
" continue # M1 is the identity operator\n",
"\n",
"# Apply the inverse QFT to the control register\n",
"circuit.compose(QFTGate(num_control).inverse(), qubits=control, inplace=True)\n",
"\n",
"# Measure the control register\n",
"circuit.measure(control, output)\n",
"\n",
"circuit.draw(\"mpl\", fold=-1)"
]
},
{
"cell_type": "markdown",
"id": "b3659616-39b4-4544-8def-54012b40dbfa",
"metadata": {},
"source": [
"\n",
"\n",
"### 2. 最適化\n",
"\n",
"回路を設計したところで、次のステップは特定の量子コンピュータ上で実行するために回路を最適化することです。 まず、バックエンドを読み込む必要があります。\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 49,
"id": "92b92fd3-0dca-43db-a304-0a933f293d8f",
"metadata": {},
"outputs": [],
"source": [
"service = QiskitRuntimeService()\n",
"\n",
"backend = service.backend(\"ibm_marrakesh\")"
]
},
{
"cell_type": "markdown",
"id": "a4e27bee-66de-4ffc-b1e3-40a458840e7a",
"metadata": {},
"source": [
"アカウントに利用可能な時間が不足している場合や、何らかの理由でシミュレータを使用したい場合は、以下のセルを実行して、上記で選択した量子デバイスを模倣するシミュレータを設定できます：\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 50,
"id": "4aa86bd6-1240-49cb-aad0-c3dbc64602c5",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"2q-depth: 188\n",
"2q-size: 281\n",
"Operator counts: OrderedDict({'sx': 548, 'rz': 380, 'cz': 281, 'measure': 8, 'x': 6})\n"
]
},
{
"data": {
"text/plain": [
""
]
},
"execution_count": 50,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"pm = generate_preset_pass_manager(optimization_level=2, backend=backend)\n",
"\n",
"transpiled_circuit = pm.run(circuit)\n",
"\n",
"print(f\"2q-depth: {transpiled_circuit.depth(lambda x: x.operation.num_qubits==2)}\")\n",
"print(f\"2q-size: {transpiled_circuit.size(lambda x: x.operation.num_qubits==2)}\")\n",
"print(f\"Operator counts: {transpiled_circuit.count_ops()}\")\n",
"transpiled_circuit.draw(output=\"mpl\", fold=-1, style=\"clifford\", idle_wires=False)"
]
},
{
"cell_type": "markdown",
"id": "b0425c46-2f2e-436f-9d37-a29fbc3a0006",
"metadata": {},
"source": [
"\n",
"\n",
"### 3. 実行\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 51,
"id": "6ee53841-d7e0-4a23-a3eb-bed31465374f",
"metadata": {},
"outputs": [],
"source": [
"# Sampler primitive to obtain the probability distribution\n",
"sampler = Sampler(backend)\n",
"\n",
"# Turn on dynamical decoupling with sequence XpXm\n",
"sampler.options.dynamical_decoupling.enable = True\n",
"sampler.options.dynamical_decoupling.sequence_type = \"XpXm\"\n",
"# Enable gate twirling\n",
"sampler.options.twirling.enable_gates = True\n",
"\n",
"pub = transpiled_circuit\n",
"job = sampler.run([pub], shots=1024)"
]
},
{
"cell_type": "code",
"execution_count": 52,
"id": "7fb6178e-76bd-4067-9607-1d7e0ac051f3",
"metadata": {},
"outputs": [],
"source": [
"result = job.result()[0]\n",
"counts = result.data[\"out\"].get_counts()"
]
},
{
"cell_type": "code",
"execution_count": 53,
"id": "6744e165-6929-46c6-9cad-55e78fe21f07",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
""
]
},
"execution_count": 53,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"plot_histogram(counts, figsize=(35, 5))"
]
},
{
"cell_type": "markdown",
"id": "2eae47e9-1161-44e5-9e00-7b0d225bcf5f",
"metadata": {},
"source": [
"量子コンピュータのノイズにより他のビット列にも若干のカウントが見られるものの `11000000`、 `00000000`、 `10000000``01000000`、、 において4つの明確なピークが確認できる。 閾値を設定することでこれらを無視し、支配的な4つだけを残します：この閾値を超えるカウントのみが、ノイズを超えた真の信号と見なされます。\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "948f404b-a2a9-4645-a034-31b696ba24b7",
"metadata": {},
"outputs": [],
"source": [
"# Dictionary of bitstrings and their counts to keep\n",
"counts_keep = {}\n",
"# Threshold to filter\n",
"threshold = np.max(list(counts.values())) / 2\n",
"\n",
"for key, value in counts.items():\n",
" if value > threshold:\n",
" counts_keep[key] = value\n",
"\n",
"print(counts_keep)"
]
},
{
"cell_type": "markdown",
"id": "f9bac651-2d89-4b4e-9930-ea585a4c042e",
"metadata": {},
"source": [
"\n",
"\n",
"### 4. 後処理\n",
"\n",
"ショアのアルゴリズムでは、かなりの部分が古典的に実行される。 では、残りの処理は「後処理」ステップに組み込みます。量子コンピュータから測定値を取得した後の段階です。 上記の各測定値は整数に変換でき、これを で割った値が の近似値となる。 $2^m$ $\\frac{k}{r}$ ここで $k$ は毎回ランダムに設定される。\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 55,
"id": "aad78e69-adb8-416f-bc68-c2086f900bef",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"\n",
"ATTEMPT 0:\n",
"Phase: theta = 0.0\n",
"Order of 2 modulo 15 estimated as: r = 1\n",
"\n",
"ATTEMPT 1:\n",
"Phase: theta = 0.75\n",
"Order of 2 modulo 15 estimated as: r = 4\n",
"*** Non-trivial factor found: 3 ***\n"
]
}
],
"source": [
"a = 2\n",
"N = 15\n",
"\n",
"FACTOR_FOUND = False\n",
"num_attempt = 0\n",
"\n",
"while not FACTOR_FOUND:\n",
" print(f\"\\nATTEMPT {num_attempt}:\")\n",
" # Here, we get the bitstring by iterating over outcomes\n",
" # of a previous hardware run with multiple shots.\n",
" # Instead, we can also perform a single-shot measurement\n",
" # here in the loop.\n",
" bitstring = list(counts_keep.keys())[num_attempt]\n",
" num_attempt += 1\n",
" # Find the phase from measurement\n",
" decimal = int(bitstring, 2)\n",
" phase = decimal / (2**num_control) # phase = k / r\n",
" print(f\"Phase: theta = {phase}\")\n",
"\n",
" # Guess the order from phase\n",
" frac = Fraction(phase).limit_denominator(N)\n",
" r = frac.denominator # order = r\n",
" print(f\"Order of {a} modulo {N} estimated as: r = {r}\")\n",
"\n",
" if phase != 0:\n",
" # Guesses for factors are gcd(a^{r / 2} ± 1, 15)\n",
" if r % 2 == 0:\n",
" x = pow(a, r // 2, N) - 1\n",
" d = gcd(x, N)\n",
" if d > 1:\n",
" FACTOR_FOUND = True\n",
" print(f\"*** Non-trivial factor found: {x} ***\")"
]
},
{
"cell_type": "markdown",
"id": "c88c65c3-2dfb-47fd-bef9-59f02440f418",
"metadata": {},
"source": [
"\n",
"\n",
"## おわりに\n",
"\n",
"このモジュールを学んだ後、ピーター・ショーがこれほど巧妙なアルゴリズムを考案した英知に、新たな感銘を受けるかもしれません。 しかし、その一見単純に見えるものの、実はそうではないという本質について、新たな理解の段階に到達していることを願っています。 このアルゴリズムは一見すると驚くほど（あるいは圧倒的に）複雑に見えるかもしれませんが、論理的な各ステップに分解し、ゆっくりと追っていくことで、あなたもショアのアルゴリズムを実行できるようになるでしょう。\n",
"\n",
"このアルゴリズムを用いてのような数を因数分解するには RSA1024 程遠いものの、量子コンピュータは日々進化を続けており、 *耐故障性*と呼ばれる閾値に達すれば、こうしたアルゴリズムの実現も間近となるだろう。 量子コンピューティングについて学ぶには、まさにワクワクする時代です！\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "9f1e3bb2-9732-406f-9f17-862178724285",
"metadata": {},
"source": [
"\n",
"\n",
"## 問題\n",
"\n",
"\n",
"\n",
"### 重要な概念：\n",
"\n",
"* 現代の暗号システムは、大きな整数の因数分解が古典的に困難であることに依存している。\n",
"* モジュラー算術（構造 $\\mathbb{Z}_N$ $\\mathbb{Z}_N^*$ および を含む）は、ショーアアルゴリズムの数学的基盤を提供する。\n",
"* 整数の因数分解の問題は、ある数の $N$ 剰余類の位数を求める問題 $N$ に還元できる。\n",
"* 量子オーダー探索は、量子位相推定技術を用いて関数 の周期を $a^x \\mod N$ 決定する。\n",
"* Shorのアルゴリズムは、基底を選択し、量子順序探索を実行し、その結果から因子を古典的に計算する古典-量子ハイブリッドワークフローで構成される。\n",
"\n",
"\n",
"\n",
"### 真偽問題：\n",
"\n",
"1. 真偽問題：Shorのアルゴリズムの効率性は、RSA暗号の安全性を脅かす。\n",
"2. T/F ショアのアルゴリズムは、現代の量子コンピュータ上で効率的に実行できる。\n",
"3. T/F ショアのアルゴリズムは量子位相推定（QPE）を主要なサブルーチンとして使用する。\n",
"4. 正誤問題：ショーのアルゴリズムの古典的部分は、最大公約数（GCD）の計算を含む。\n",
"5. T/F ショアのアルゴリズムは偶数の因数分解にのみ有効である。\n",
"6. T/F ショアのアルゴリズムの実行が成功すれば、常に正しい因数が保証される。\n",
"\n",
"\n",
"\n",
"### 簡潔な回答：\n",
"\n",
"1. なぜショアのアルゴリズムはRSA暗号に対する将来的な脅威と見なされているのか？\n",
"2. なぜ、モジュラー指数関数の周期（または順序）を見つけることが、ショーアアルゴリズムにおける数の因数分解に役立つのか？\n",
"\n",
"\n",
"\n",
"### 課題問題：\n",
"\n",
"1. 与えられた $N$ 数を因数分解し、その次数（オーダー）の正しい値を導出するために必要なQPE $r$ （量子位相誤差）の精度を得るには、いくつの制御量子ビット $m$ が必要か？\n",
"\n",
"2. ここで示した手順に従って15を因数分解した後、今度は21を因数分解してみてください。\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"id": "a1b8767d",
"source": "© IBM Corp., 2017-2026"
}
],
"metadata": {
"in_page_toc_max_heading_level": 2,
"in_page_toc_min_heading_level": 2,
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3"
},
"widgets": {
"application/vnd.jupyter.widget-state+json": {
"state": {},
"version_major": 2,
"version_minor": 0
}
}
},
"nbformat": 4,
"nbformat_minor": 5
}