インテージテクノスフィア技術ブログ

株式会社インテージテクノスフィアの社員達がシステム開発や仕事に関する技術情報を随時掲載いたします

トップ > 量子コンピュータ > Shor のアルゴリズムの概要

Shor のアルゴリズムの概要

量子コンピュータ 開発

こんにちはアイダです。インテージテクノスフィアでは「技術探究委員会」にて先端技術を含めたテクノロジーにおける基礎研究、および応用研究を行っています。「量子コンピュータ」の研究員T.Mさんに、「研修の成果として、世の中の技術者のみなさまに役に立つ情報を書いて！」とお願いしてみましたー。T.Mさん、自由に書いちゃってください。

はじめに

技術探究委員会の本題からは外れると分かりつつ、この blog では自分の好みに走らせてもらい、Shor のアルゴリズムの概要を（今更ではありますが、考 察の対象が具体的でもあるというところでお許しを乞う事にして）紹介します。 これは約数の知らされていない合成数を実際に非自明な約数の積に分解するためのアルゴリズムで、量子的計算を用います。

この問題は古典的計算のみで効率良く解くのはいちじるしくむつかしいと考えられているのですが、Shor のアルゴリズムの効率はこの問題に対する古典的 方法の限界を大きく超えていると思われていて、実際、現在知られている最良の古典的アルゴリズムの効率より漸近的に指数函数の大きさでまさっています。 （ただし、古典的計算機に勝てる範囲でこのアルゴリズムを走らせられる量子的計算機は、まだすぐにあらわれそうなものではありません。）

Shor のアルゴリズムは、実用性では、原論文 [Sh] でも指摘されてい る通り、（今は広く使われていますが）特殊な暗号を破るのにしか役に立たな いアルゴリズムかも知れませんが、しかし、Feynman が提示した 様な、量子物理的な背景を持つ問題ではなく、しかも明らかな応用のある問題 に対して、上に述べた様な効率の良さを達成した点で華々しく、専門家に限らない多くの人々の量子的計算に対する見方を決定的に変えた事ではないかと思 います。

一方で、その中心的なアイディアは、非凡でそれなりに深いにも拘わらず、自然で、また、分かり易くもあります。 この自然かつ分かり易いところを、量子的計算に特段の馴染みの無い方にも鑑賞して頂きたいというのが、この記事の動機です。 うまくいきますか、お立ち会い。

（以下、一部修正 2022/6/24.）

量子的並列処理

記法など

量子物理学に詳しくない読者向けの量子的計算への入門的な文献としては、古典的計算の理論や Shor のアルゴリズムも含めた解説 [Ma] や、量子 力学への入門と合わせ、数学的な背景にも触れた [Ku] などがある。 初等的な概念の解説はこれらの文献などに委ねる事にし（最後まで読まれる必要は無く、以下で使っている言葉が分かるくらいまでで大丈夫と思います）、 ここでは後で使う記法の導入などから始める。

量子的ビットは複素数体 \mathbb{C} の上の正規直交基底 |0\rangle,|1\rangle の与えられた量子的な状態空間を持ち、そこにおける状態を保持 する。 複数の量子的ビットをまとめて一つのレジスターと考え、そこに一まとまりの 情報を持たせたりする。 高々 n ビットの整数 x\ge 0 の 2 進法による表記が x_{n-1}\cdots x_0（上の方の桁が無い時は、その桁に 0 を置く事にする） のとき、レジスターの状態空間の元

\begin{equation*}
  |x_0\rangle\otimes\cdots\otimes|x_{n-1}\rangle
\end{equation*}

を |x\rangle と書く。

N=2^{n} と書くと、n 個の量子的ビットからなるレジスターの状態空間の一 般の元は、集合

\begin{equation*}
  \mathbb{Z}/N\mathbb{Z} = \{0, 1, \cdots, N-1\}
\end{equation*}

の上で定義された複素数値函数 \phi により、

\begin{equation*}
  |\phi\rangle := \sum_{x\in\mathbb{Z}/N\mathbb{Z}}\phi(x)|x\rangle
\end{equation*}

と書ける。 この対応で、状態空間は函数空間 \mathbb{C}^{\mathbb{Z}/N\mathbb{Z}} と同一視できる。

古典的計算から量子的計算へ

古典的計算は n ビットの情報から m ビットの情報を作り出す集合の写像

\begin{equation*}
  \{0, \ldots, N-1\}\longrightarrow \{0, \ldots, 2^m -1\}
\end{equation*}

を計算する論理回路であらわす事が出来る。 論理回路 f で入力値 x から得られる出力を f(x) と書く。 それに対し、長さ n+m の量子的レジスターの間の量子的回路（すなわち、 順に適用するための量子的操作またはその dilation の列）で、合成された dilation U が、各 0\le x ≨ N に対して

\begin{equation*}
  U|x, 0\rangle = |x, f(x)\rangle
\end{equation*}

を満たすものを作れる。 これは入力 x を入れる長さ n のレジスターと出力 f(x) の入る長さ m のレジスターに作用しているが、実際には、ここでは省いて書いたが、 U は他の幾つかの量子的ビットの状態空間にも合わせて作用する事を許し、 計算を実行するにはそのための余分な量子ビット（ancilla と呼ば れる）を用意し、ancilla らからなるレジスターを、約束として先に決めてお いた特定の状態（例えば単位 vector |0\rangle から定まる状態）に初期化 してから始めなければならない。 （そうしなかった時の結果がどうなるかは考えず、何も保証しない。）

その様な量子的回路で、dilation U_f が性質

\begin{equation*}
  U_f|x, 0, y\rangle = |x, 0, f(x)\oplus y\rangle
\end{equation*}

（ただし、\oplus はビットごとの和）を満たすものを、古典的計算 f の minimal unitary form と言う。 ここで、この計算は |0\rangle から定まる状態に初期化された ancilla を 幾つか使うとし、今回はそれもちゃんと表記に含めた。 （Ancilla らからなるレジスターは計算の過程には使われるが、|0\rangle から定まる状態から同じ状態に戻っている。） Ancilla がある事は諒解した上で、それを省いて U_f|x, 0\rangle = |x, f(x)\rangle などと書いてしまうのが楽な事もあるかも知れない。 論理回路 f の大きさ（回路を作る gate の出力の大きさの総和で、f の 出力に対応する m 個の分を含む）が L であるとき、L 個の ancilla を使い、高々 (n+L+m)^{2} に比例する程度の長さを持つ f の minimal unitary form を作れる Manin, 3.2.1.

量子的計算機の上での並列化

f の minimal unitary form を用いて量子的計算機の上ですべての 0 \le x\lneq 2^{n} に対する f(x) を同時に作れる。 すなわち、|+\rangle = \frac{1}{\sqrt{2}}(|0\rangle +|1\rangle) とす れば

\begin{equation*}
  |+^n\rangle :=|+\rangle^{\otimes n}
  = \frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}|x\rangle
\end{equation*}

なので、

\begin{equation*}
  U_f|+^n, 0\rangle
  = \frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}|x, f(x)\rangle
\end{equation*}

である。 単位 vector |+^n\rangle から定まる状態は、1 つの量子的ビットに作用 するアダマールの gate

\begin{align*}
  H\text{: }
  &|0\rangle
    \mapsto|+\rangle\\
  &|1\rangle
    \mapsto
    \frac{1}{\sqrt{2}}(|0\rangle -|1\rangle)
\end{align*}

を用いて初期状態 |0\rangle から

\begin{equation*}
  |+^n\rangle = H^{\otimes n}|0\rangle
\end{equation*}

と作れる。

単位 vector U_f|+^n, 0\rangle から定まる状態は、すべての f(x) を並 列に計算した結果に見える。 ただし、量子的な状態そのものを観測できるわけでないし、重ね合わさった状 態のそれぞれを任意に取り出せるわけではないので、古典的な並列計算とは違 うものである。 しかし、重ね合わされた状態からでも有用な古典的な情報を取り出せる時には、 並列に計算できたのに準じた効果が得られる事がある。

Shor のアルゴリズム

合成数の分解

合成数 M の非自明な約数を見つけたい。 ただし、M は素数の冪ではないとする。 また、M は奇数とする。 （偶数なら 2 が非自明な約数である。） Shor のアルゴリズムは、量子的計算機を用いてこれ を高々 \log M の多項式であらわされる程度の計算量で（M に依らない） 一定以上の確率で見つける。 （見つかれば終わりなので、繰り返しても見つからない確率は急激に下がる。） 古典的計算のみではそれより遥かに効率の悪い方法しかあり得ないと信じられ ている。 知られているもっとも効率的な古典的計算によるアルゴリズムでそれなりに複 雑な数体篩法でも、指数函数と多項式函数の違いの大きさで計算量に差がつけられる。 （こちらも結果は一定以上の確率で得られる。） すなわち、M が十分に大きくなる限り、数体篩法の方が Shor の方法より急激に圧倒的に長い計算時間が掛かる様になる。

1 ≨ t ≨ M を一つ選ぶ。 t と M の最大公約数が 1 でなければ、それが M の非自明な約数で ある。 最大公約数は、ユークリッドの互除法により、古典的計算機の上で 高々 \log M の多項式であらわされる程度の計算量で求まる。

最大公約数が 1 ならば、t^{r} \equiv 1\mod M となる最小の r\ge 1 を、 後で述べる方法により量子的計算機を使って見つける。 r は剰余環 \mathbb{Z}/M の乗法群（乗法に関する可逆元らのなす群） (\mathbb{Z}/M)^\times における t\mathbin{\mathrm{mod}} M の位数と呼ばれる。

r が偶数ならば、t^{\frac{r}{2}}-1 は M で割り切れないので、 (t^{\frac{r}{2}}-1)(t^{\frac{r}{2}}+1)\equiv 0\mod M より、 t^{\frac{r}{2}}+1 も M で割り切れなければ、t^{\frac{r}{2}}\pm 1 はそ れぞれ M の非自明な約数を約数に持つ。 例えば M との最大公約数がその一つであり、それは高々 \log M の多項 式であらわされる程度の計算量で求まる。

r がこの必要な条件を満たさない t は、M に依らず多くとも一定の比 率以下しか無い事が、中国剰余定理と初等整数論により群 (\mathbb{Z}/M)^\times の構造を考える事で分かる。 （[Ma] 参照。）

量子的計算の利用

r を量子的計算機を使って見つけるのに、整数 a に対する函数 f(a) = t^{a} \mathbin{\mathrm{mod}} M を考える。 r の倍数らがこの函数のすべての周期である。

先が分かりにくくならない様に、r は (\mathbb{Z}/M)^\times の元の個数以下な ので、r < M である事に注意しておく。 すなわち、函数 f は 1 から M-1 までのあたいしか取らないので、 f(1), ..., f(M-1) のどれかが 1 であるか、若しくはどれか二つは等 しいが、f(a)=f(b) すなわち t^{a} \equiv t^{b} \mod M となる a\gneq b があれば、t^{a-b}\equiv 1\mod M となるので、結局 r < M である。

十分に大きな n を取る。 n を大きくし過ぎれば計算がそれだけ大きくなってしまうが、Shor のアル ゴリズムには 2^{n} > M^{2} であれば十分である。 （詳しい解析にはここでは踏み込まないが。） 高々 2^{n} < 2M^{2} となる n があるので、それを用いれば良い。 整数 0\le \ell\le n に対し、 t^{2^\ell}\mathbin{\mathrm{mod}} M は（平方を取る操作を繰り返 す方法で）高々 n の多項式であらわされる程度の 長さの論理回路で計算できるので、f の定義 域を 0\le a ≨ 2^{n} に制限したものは高々 n の多項式であらわされ る程度の長さの論理回路で計算できる。 したがって、その minimal unitary form U_f を高々 n の多項式であら わされる程度の長さの量子的回路で計算できる事になる。

N=2^{n} とする。 一般に 0\le a ≨ N に対する函数 f が（例えば N より十分に小さ いと分かっている）ある r\ge 1 に対して

\begin{equation*}
  f(a+r) = f(a)
\end{equation*}

を、両辺が定義されている範囲のほぼすべての a に対して満たす事が分かっ ているとき（ここに曖昧さを残したが、Shor の状況では、一つの a に 対して満たせばすべての a に対して満たす）、その様な最小の r（f の最小周期と呼ぼう）を、Shorの方法は量子的計算機の上で U_f を一度もちいるだけで、後は高々 n の多項式であらわされ る程度の計算量で、高い確率で求めてしまう。 古典的計算で r を求めるには、遥かに大きなオーダーで多くの a に対し て f(a) を計算しなければならないところである。 （例えば、十分に多くの a に対して f(a) を決めなければ、f の最小 周期は決まらない。）

周期の見つけ方

Shor の方法では、まづ、f の量子的並列化によって単位 vector

\begin{equation*}
  U_f|+^n, 0\rangle
  = \frac{1}{\sqrt{N}}\sum_{a=0}^{N-1}|a, f(a)\rangle
\end{equation*}

から定まる状態を作る。 この状態から周期を求めるのに役に立つのはフーリエ変換である。 （これで分かってしまわれた方にはここから先はつまらなくて申しわけありま せんが、筆者はそこまでかしこくありませんでしたので）以下、その事を説明 する。

f が最小の周期 r を持つ事は、群 G := \mathbb{Z}/N\mathbb{Z} の元 r の集合 G への「ずらし」による作用 a\mapsto a+r\mathbin{\mathrm{mod}} N を用いた変換をはじめのレジスターの状態空 間 \mathbb{C}^G にほどこせば得られる

\begin{equation*}
  \frac{1}{\sqrt{N}}\sum_{a=0}^{N-1}|a+r \mathbin{\mathrm{mod}} N, f(a)\rangle
\end{equation*}

が、元の vector にほぼ等しい事と解釈できる。 ここで用いた G の \mathbb{C}^G への作用は、写像 \delta\text{: } G\to\mathbb{C}^G, s\mapsto\delta_s（デルタ函数）を通して畳み込み

\begin{equation*}
  *\text{: } \mathbb{C}^G\otimes\mathbb{C}^G\longrightarrow \mathbb{C}^G
\end{equation*}

を誘導しているものだが、フーリエ変換 \phi\mapsto\hat\phi は \phi*\psi を函数の（各点におけるあたいごとの）積 \hat\phi\hat\psi\text{: } c\mapsto \phi(c)\psi(c) の \sqrt{N}（= 函数環の単位元 1 の長さ）倍に変換する。 これは、フーリエ変換が、s\in G でのずらしによる作用 \mathbb{C}^G\to\mathbb{C}^G を、すべての s に対して同時に対角化す るという事を含意する。 （G の函数空間への作用がユニタリー変換によっているのはそうで、G は 可 換なので、作用をすべて同時に対角化する正規直交基底があるのは当然だが、 フーリエの基底はそれで、そうして G のすべての指標が丁度ひと通り出て いる。）

より具体的には、r による作用は |\phi\rangle\mapsto|\phi*\delta_r\rangle であり、フーリエ変換によっ てこれは |\hat\phi\rangle\mapsto\sqrt{N}|\hat\phi\hat\delta_r\rangle に変 わ るので、|c\rangle は、この変換の固有 vector で、固有値 \sqrt{N}\hat\delta_r(c) = \exp(2\pi irc/N) に属する。

周期 2^{n} のフーリエ変換は、量子的計算機の上では高々 n の多項式であ らわされる程度の個数の簡単な gate を組み合わせたユニタリー変換として作 る事が出来る。 （例えば [NCh].） f の周期を求めるアルゴリズムとしては、量子的並列化によって作った状態 からはじめのレジスターにフーリエ変換をほどこしてからそのレジスターを測 定する。

Vector

\begin{equation*}
  \frac{1}{\sqrt{N}}\sum_{a=0}^{N-1}|a, f(a)\rangle
\end{equation*}

が r\in G の作用によってほぼ不変であったという事は、はじめのレジスター の状態空間を r の作用の固有空間らの直和へ分解してその vector を見る と、おもな成分が、固有値 \exp(2\pi irc/N) が 1 に近い固有空間らか ら来る部分に集中している（長さで言って）という事である。 したがって、述べた過程を経て測定される 0\le c ≨ N は、N/r の整 数倍に近いものである確率が高い事になる。 したがって、観測された c/N を小さな分母の分数で近似する事で、その分数の分母として r の約数は得られ易くなっている。

これで、少なくとも、f(a)=t^{a}\mathbin{\mathrm{mod}} M の様に、 一周期のあいだ同じあたいを二度取る事が無い f については、例えば r^{2}\le N が保証されていれば、多くない回数の測定から高い確率で r を知れる事が、確率を見積もって分かるのである。 （合成数の分解ついて言えば、r の候補が得られれば、それから約数が見つ かるかはすぐに確かめられるのだった。） なお、この性質を持つ f については、U_f と少し違うユニタリー変換を 使う事も出来る [Ki]. Shor の f で言うと、minimal unitary form を考えた際のビットごとの足 し算を、modulo M での掛け算に変えるのに近い事が出来る。 可逆な元を掛ける操作は可逆なので、その f に対しては、可逆（そしてユ ニタリー）な変換が得られる。 Shor の f に対してそのユニタリー変換を V_f と書けば、f(a) = f(a)\cdot 1 なので、

\begin{equation*}
  V_f|+^{n}, 1\rangle
  = \frac{1}{\sqrt{N}}\sum_{a=0}^{N-1}|a, f(a)\rangle
\end{equation*}

となるのである。 （やはり ancilla らは省いて書いている。）

終わりに

アルゴリズムの概要という事にし、中心にあるアイディアに焦点を当ててみました。 函数の周期を見つけるのに量子的計算機を役立てる考えの自然で分かり易いと ころが伝わり、楽しんで頂けたなら良かったと思います。

参考文献

[Fe] Feynman, Richard, Simulating physics with computers, Int. J. of Theor. Phys., 21 (1982), 467--488.

[Ki] Kitaev, A. Yu., Quantum measurements and the Abelian Stabilizer Problem, arXiv:quant-ph/9511026, 1995.

[Ku] Kuperberg, Greg, A concise introduction to quantum probability, quantum mechanics, and quantum computation.

[Ma] Manin, Yuri I., Classical computing, quantum computing, and Shor's factoring algorithm, Astérisque, tome 266 (2000), Séminaire Bourbaki, exp. no 862, p. 375--404.

[NCh] Nielsen, Michael A. and Chuang, Isaac L., Quantum computation and quantum information, Cambridge University Press, Cambridge, 2000.

[Sh] Shor, P. W., Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput., 26:5 (1997), 1484--1509.