量子コンピュータにおける素因数分解(2): べき剰余

はじめに

この記事は量子コンピュータによる素因数分解のアルゴリズムである「Shorのアルゴリズム」の解説記事第2回目です。1回目は以下の記事です：

• 量子コンピュータにおける素因数分解(1): 加算器

今回の目標は「べき剰余 (Modular exponentiation):$a^x \text{ mod }N$を計算する量子回路を構成することです。後の記事で説明しますが、これが素因数分解に重要な回路です。

参考文献はVedralSamNです。基本的にはVedralに基づいて書かれています。SamNは大変わかりやすいShorのアルゴリズムの日本語による解説記事です。

剰余和 (Adder modulo $N$)

以下を計算する量子回路を組みます：

$0\le a+b < 2N$であることに注意すれば、$a+b-N$を計算して、overflowが起こらなければ、すなわち$a+b-N\ge 0$ならばこれそのものが$a+b\text{ mod }N$です（負になると最上位ビットが立つ。これをoverflowと呼ぶ）。もしoverflowが起これば$a+b\text{ mod }N=a+b$です。和・差を計算する量子回路は前回の加算器とそれを逆回ししたもので実現できるので、簡単に量子回路を組めるように思います。

ただし回路が可逆になるように組むので、そこが少し複雑です。Ref.Vedralでは以下のような量子回路を組んでいます：

剰余和（Adder mod）の量子回路。$\bar t$は$t$のビット反転を表す

Add, Subtractはそれぞれ「加算器」「減算器」を表します。加算器は 前回 説明しました。減算器は加算器の逆回し（"$\text{Add}^{-1}$"）で実現できます。

図に関し、2つほどコメントです：

1. $a+b-N$の最上位ビット（Vedralでは"most significant bit"と呼ばれる）は、$a+b-N<0$のとき$1$、$a+b-N\ge 0$のとき$0$です。この最上位ビットを$t$とします。すなわち
   \begin{align} \hspace{1.5cm} t=\begin{cases} 1 & a+b-N<0\\ 0 & a+b-N\ge 0 \end{cases} \end{align}
   です。図の$\bar t$とは$t$のビット反転を表します。
2. 最後のAddの左側で$(a+b \text{ mod }N)-a$の最上位ビットが$\bar t$となっています。これは以下のようにしてわかります：
   ・もし$a+b-N\ge 0$ならば$a+b-N$の最上位ビット$t$は0。このとき$(a+b \text{ mod }N)-a=a+b-N-a=b-N<0 \ (\because b< N)$であるからこの量の最上位ビットは1
   ・もし$a+b-N< 0$ならば$a+b-N$の最上位ビット$t$は1。このとき$(a+b \text{ mod }N)-a=a+b-a=b\ge0$であるからこの量の最上位ビットは0
   以上から$(a+b \text{ mod }N)-a$の最上位ビットは$\bar t$になります。

制御剰余乗算 (Control-Multiplier modulo$N$)

ゼロ以上の整数$a,x$および正の整数$N$が与えられたとき$a\times x\text{ mod }N$を計算する量子回路を作ります。ただし今後の目的のため、フラグとなる$c$なる数を用意して以下のような変換を行う回路を構成します（Ref.Vedral）：

これは前章のAdder Modを組み合わせて作られます。$x$を$x_{n-1}x_{n-2}\cdots x_1 x_0$のように2進数表示します。$ax$は
\begin{align} \hspace{1.5cm} ax=2^0a \times x_0+2^1a\times x_1+\cdots+2^{n-1}a\times x_{n-1} \end{align}
と表されるので、$c=1$のとき、かつ$x_i$が1の場合に$2^i a$を$\text{mod }N$で足していけば目的が達成されます。
Ref.Vedralではこの量子回路を以下のように組んでいます：

制御剰余乗算 (Control-multiplier modulo $N$)の量子回路。青い文字はすべて$\text{mod }N$であることに注意

茶色の太線は1 qubitではなくqubit群を表します。上から下に伸びる矢印は$c$と$x_i$両方が1のときに矢印の先のqubit群に$2^i a$をセットする操作を表します（論文では$a$は明示されていないですが、implicitにどこかに蓄えられています）。Adder Modは前章の回路です。これを通した直後の矢印は、セットされている（かもしれない）$2^i a$を消去する作業を表します。下の桁$2^0a$から再帰的に1桁ずつ$\text{mod }N$の和を計算し、それが一番下のqubit群に蓄えられます。最後の方の曲がった矢印は、$c$が0のときに$x$を一番下のqubit群にコピーする操作です。一番上のqubitの最後のほうで$c$に一時的にNOTをかけてビット反転しているのはそのためです。

べき剰余 (Modular exponentiation)

以下の計算を実現する回路を作ります：

上記しましたが、これが因数分解に重要な量子回路です。この回路を作るためにここまでその部品となる回路を構成してきました。

Ref.Vedralには以下のような回路が描かれています：
べき剰余 (Modular exponentiation)の量子回路。青い文字はすべて$\text{mod }N$であることに注意

これも行っていることは簡単です。まず
\begin{align} \hspace{1.5cm} a^x=a^{2^0\times x_0}\cdot a^{2^1\times x_1} \cdots a^{2^{m-1}\times x_{m-1}} \end{align}
です。ここで
\begin{align} \hspace{1.5cm} ab\text{ mod }N=((a\text{ mod }N)\times b)\text{ mod }N \end{align}
なので、
\begin{align} \hspace{1.5cm} &a^x \text{ mod }N = a^{2^0\times x_0}\cdot a^{2^1\times x_1} \cdots a^{2^{m-1}\times x_{m-1}} \text{ mod }N\\ &=(\cdots(((a^{2^0\times x_0}\text{ mod }N)\times a^{2^1\times x_1}\text{ mod }N)\times a^{2^2\times x_2} \text{ mod }N)\cdots )\times a^{2^{m-1}\times x_{m-1}}\text{ mod }N \end{align}
です。各桁の$a^{2^i\times x_i} \text{ mod }N$は前章のCtrl Mult Modを用いて$x_i=1$のとき$a\times a \text{ mod }N\rightarrow a^2\times a^2 \text{ mod }N\to \cdots$のように再帰的に計算して作れます（図3参照）。Ctrl Mult Modでそれらを掛け算していけば、最終的に$x^a \text{ mod }N$が計算できます。$(\text{Ctrl Mult Mod})^{-1}$はCtrl Mult Modを計算する前に片方のqubitを0にリセットするための操作です。もう片方のqubitにそれまで掛け算した数の情報が蓄えられます。

${}$

おしまい & つづく。${}_\blacksquare$