Shorのアルゴリズムを理解したい - 第1回 量子コンピュータとShorのアルゴリズムとは

突然ですが皆さん、映画『サマーウォーズ』は観たことありますか？

¹

自分はこの映画が好きすぎて、もう何十回も観てます。今年の15周年記念上映も最高でした。

さて、この映画の冒頭6:18のシーンで、主人公の小磯健二くんが電車内で数学誌を読んでいます。
そこで一瞬映る記事のタイトルが、『Shorの因数分解アルゴリズム』です。

サマーウォーズがわかる人向けのシーン説明

健二が『Shorの因数分解アルゴリズム』を読んでいるのは、上田に向かう最初のシーンです。
「募集人員、一名なの」→ タイトル → キングカズマのアクションシーン と続いた後、数秒だけ映ります。
その後、東京駅銀の鈴でナツキ先輩と合流し、新幹線のシーンへとつながっていきます。

Shorの因数分解アルゴリズムとは、現代の暗号化技術の多くで使用されている"RSA暗号"を高速に解くと言われている、量子コンピュータのアルゴリズムです。

RSA暗号とその安全性は、この映画でも重要な話でした。
それが高速に解けてしまうというこのアルゴリズム、もちろん理解したくなりますよね？
そんなShorのアルゴリズムの理解を目指して、全8回ほどで量子プログラミングを学んでいこうと思います。

量子コンピューターの基本概念

Shorのアルゴリズムは、量子コンピューター上での動作を前提とした、量子アルゴリズムです。
（正確には、Shorのアルゴリズムの一部が、量子コンピューター上で実行されます。）
ですのでまずは、量子コンピューターの基本概念がら確認しましょう。

古典コンピューターとの違い

現代のコンピュータ、私たちが普段使っているPCやスマートフォンは「古典コンピュータ」と呼ばれます。
古典コンピュータの基本単位は「ビット（bit）」で、0か1のどちらかの状態を持ちます。
しかし、量子コンピュータはこれとは異なり、「量子ビット（キュービット）」を基本単位として使用します。

量子ビットの紹介

量子ビットは、0と1の両方の状態を同時に持つことができる「重ね合わせ状態」になることができます。

例えば、$\frac{1}{2}$の確率で0、$\frac{1}{2}$の確率で1と振る舞う量子ビットの状態は、次のように書けます。

$$\left|\psi\right\rangle = \frac{1}{\sqrt{2}}\left|0\right\rangle + \frac{1}{\sqrt{2}}\left|1\right\rangle$$

ここで出てきた記号について説明します。
（今回のシリーズを理解するうえでの必要最低限の説明を目指すので、正確性に欠けることをお許しください）

まず、$\left|0\right\rangle$という括弧のようなものは、"ケット"と呼びます。
相方の"ブラ"$\left\langle0\right|$とセットでブラ-ケット記法という、量子状態を表すための記法となっています。
（呼び名は、括弧を表すbracketから）
ですが、量子プログラミングの文脈では"ケット"しか出てきませんし、量子力学の知識も不要です。

量子状態は、2次元の複素ベクトルとしても表現できることも、なんとなく覚えておくと良いかもです。
$$\left|0\right\rangle = \begin{bmatrix} 1 \\ 0 \end{bmatrix}, \left|1\right\rangle = \begin{bmatrix} 0 \\ 1 \end{bmatrix}$$

また、これらの係数 $\frac{1}{\sqrt{2}}$ は、確率振幅と呼ばれる複素数で、その二乗が確率となります。

1量子ビットの状態は、一般に以下のように表現できます。
$$\left|\psi\right\rangle = \alpha\left|0\right\rangle + \beta\left|1\right\rangle$$
ここで$\alpha$と$\beta$は複素数で、以下の条件を満たします：
$$|\alpha|^2 + |\beta|^2 = 1$$

詳細は以降の回で説明しますが、$\alpha$と$\beta$が複素数であることで、位相を持つことができます。

例えば、以下は全て有効な量子状態です。

• $\alpha = 1, \beta = 0$ → $\left|0\right\rangle$
• $\alpha = \frac{1}{\sqrt{2}}, \beta = \frac{1}{\sqrt{2}}$ → 等確率な重ね合わせ
• $\alpha = \frac{1}{\sqrt{3}}, \beta = \sqrt{\frac{2}{3}}$ → 確率が偏った重ね合わせ
• $\alpha = \frac{1}{\sqrt{2}}, \beta = \frac{i}{\sqrt{2}}$ → 位相差のある重ね合わせ

量子もつれ

量子もつれ（エンタングルメント）は、複数の量子ビットが互いに依存した状態になる現象です。
もつれた量子ビットは、個々の量子ビットの状態を独立して決めることができず、全体として一体的な状態を形成します。

2量子ビットの状態は、一般に以下のように表現できます。

$$\alpha\left|00\right\rangle + \beta\left|01\right\rangle + \gamma\left|10\right\rangle + \delta\left|11\right\rangle$$

ここで、$\alpha, \beta, \gamma, \delta$は複素数で、以下の条件を満たします。
$$|\alpha|^2 + |\beta|^2 + |\gamma|^2 + |\delta|^2 = 1$$

例えば、1ビット目と2ビット目がどちらも1と0を当確率で持つ状態は、以下のように表現できます。
$$\frac{1}{2}\left|00\right\rangle + \frac{1}{2}\left|01\right\rangle + \frac{1}{2}\left|10\right\rangle + \frac{1}{2}\left|11\right\rangle$$

量子コンピュータでは、2つの量子ビットをもつれさせて、例えば以下のような状態を作り出すことができます。
$$\frac{1}{\sqrt{2}}\left|00\right\rangle + \frac{1}{\sqrt{2}}\left|11\right\rangle$$
これは、1ビット目と2ビット目が同時に0か1のどちらかを持つ状態です。
2ビット目が1ビット目の状態に依存している、あるいはその逆の依存があるといえるため、2つの量子ビットがもつれていると言えます。

量子ゲート

量子コンピュータでは、量子ゲートと呼ばれる操作を使用して量子ビットの状態を変化させます。
これらのゲートは、古典コンピュータの論理ゲート（AND, OR, NOTなど）に相当しますが、量子重ね合わせやもつれを利用する点で異なります。
代表的な量子ゲートには、アダマールゲート（Hゲート）、Xゲート（パウリXゲート）、CNOTゲートなどがあります。

例えば、Xゲートは古典コンピュータのNOTゲートに相当し、以下のように状態を変化させます。

• $\left|0\right\rangle \xrightarrow{Xゲート} \left|1\right\rangle$
• $\left|1\right\rangle \xrightarrow{Xゲート} \left|0\right\rangle$

Shorのアルゴリズムの重要性

次回以降の詳しい説明へ入る前に、Shorのアルゴリズムがなぜ重要なのか、簡単に説明します。

素因数分解の古典的困難性

素因数分解とは、ある整数をその素因数の積として表現する問題です。
例えば、15の素因数分解は3と5です。簡単ですね。

ですが、以下のような大きな数の因数分解は簡単にできるでしょうか？
$$97139961312384239075080721131188244842051515305572003521287545456189235939577$$
この77桁の数は、$299681192390656691733849646142066664329$と$324144336644773773047359441106332937713$という2つの39桁の素数の積です。

このぞ因数分解の困難性は、暗号技術、特にRSA暗号の基盤となっています。
古典コンピュータでは、大きな数の素因数分解は非常に困難であり、現実的な時間内に解くことが難しいとされています。

（ちなみに映画の中では、健二くんは「2056桁の暗号」を解いていました。この暗号では1138桁の整数を素因数分解する必要があるらしいです...）

Shorのアルゴリズムの概要

1994年、ピーター・ショア（Peter Shor）は、量子コンピュータ上で動作するShorのアルゴリズムを提案しました。²

このアルゴリズムは、素因数分解問題を高速に（多項式時間で）解くことができます。

シリーズ各回の概要

このシリーズでは、Shorのアルゴリズムを理解し、Qiskitを使用して実際に実装するところまで紹介したいと考えています。
量子コンピュータや量子アルゴリズムに関する基礎知識がない方でも、順を追って学ぶことでShorのアルゴリズムを実装できるようになることを目指しています。

以下のような、全8回にわたるシリーズを考えています。

1. 量子コンピュータとShorのアルゴリズムとは
   • 量子コンピュータの基本概念とShorのアルゴリズムの重要性について紹介します
2. 環境構築とQiskit入門
   • 量子プログラミングのライブラリであるQiskitのインストール手順や基本的な使い方を紹介し、簡単な量子回路を作成します
3. 量子ビットと基本的な量子ゲート
   • キュービットの状態や主要な量子ゲート（X, H, CNOT）の使い方を解説します
4. 量子回路の設計とシミュレーション
   • 複雑な量子回路の設計方法とQiskitを用いたシミュレーションの方法を紹介します
5. Shorのアルゴリズムの数学的背景
   • 素因数分解問題の数学的基礎とShorのアルゴリズムの理論的背景について掘り下げます
6. 量子フーリエ変換（QFT）の実装
   • Shorのアルゴリズムの核心部分である量子フーリエ変換の理論と実装方法を紹介します
7. 周期探索と量子部分の統合
   • 周期探索アルゴリズムの詳細と、量子部分と古典部分の統合方法について解説します
8. Shorのアルゴリズムの完全実装と実行例
   • Shorのアルゴリズム全体をQiskitで実装し、具体的な例を通じて動作を確認します

細かい部分は自分も勉強しながらになるので、投稿頻度は不定期になるかもしれませんが、最後まで続けていきたいと思います！

1. スタジオ地図公式が配布している画像です！Shorのアルゴリズムを読んでいるシーンはなかった。 https://x.com/studio_chizu/status/1398084639848161282 ↩

2. P. W. Shor, "Algorithms for quantum computation: discrete logarithms and factoring," Proceedings 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM, USA, 1994, pp. 124-134, doi: 10.1109/SFCS.1994.365700. keywords: {Quantum computing;Quantum mechanics;Polynomials;Computational modeling;Physics computing;Computer simulation;Costs;Mechanical factors;Cryptography;Circuit simulation}, https://ieeexplore.ieee.org/document/365700 ↩