Shorのアルゴリズム

同義語:Shor's algorithm

概要

Shorのアルゴリズム(Shor's algorithm)とは、整数 $N$ の素因数分解を、$N$ の桁数の多項式の個数の量子門で高い確率で行う量子計算の算法である。因数分解を、無作為に選んだ $a$ の $N$ を法とする位数 $r$ を求める問題に帰着し、$r$ が偶数かつ $a^{r/2}\not\equiv-1$ なら $\gcd(a^{r/2}-1,N)$ が約数になる。位数は、関数 $x\mapsto a^x\bmod N$ に量子 Fourier 変換を施した測定値 $y$ の分布が $Q/r$ の倍数の近くに山をもつことを使い、$y/Q$ の連分数展開から求める。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 量子計算, 中国剰余定理, 連分数, 位数(群)

Shor のアルゴリズム(Shor's algorithm)は、整数 $N$ の素因数分解を、$N$ の桁数の多項式の個数の量子門で、高い確率で行う量子計算の算法である(Sho97)。古典の計算機で知られている最良の方法は桁数の多項式時間ではないので、RSA暗号 のように素因数分解の難しさに頼る 公開鍵暗号 に大きな影響を与えた。
算法は 2 つの部分に分かれる。第 1 の部分は古典の初等整数論で、$N$ の因数分解を「$a$ の $N$ を法とする位数 $r$ を求める問題」に帰着する。第 2 の部分が量子計算で、関数 $x\mapsto a^x\bmod N$ の周期 $r$ を、量子 Fourier 変換 で測定値の分布の山として取り出し、連分数 で復元する。
この記事では、帰着の確率の評価、量子 Fourier 変換の回路、位数を求める回路の成功確率の下界を完全に証明する。べき乗の剰余を計算する回路は、古典の回路を可逆にする一般論(量子計算 の補題「可逆な模倣」)に任せる。量子ビット・量子門・測定の定義は 量子計算 に従う。

定義と使える条件

位数を求める問題

$N\ge2$、$\gcd(a,N)=1$ とする。$a^r\equiv1\pmod N$ となる最小の正の整数 $r$ を $a$ の $N$ を法とする 位数 といい、$\operatorname{ord}_N(a)$ と書く。$N$ と $a$ から $r$ を求める問題を 位数を求める問題 という。

$a^x\equiv a^{x'}\pmod N$ となるのは $r\mid x-x'$ のときに限るので、$r$ は関数 $x\mapsto a^x\bmod N$ の最小の周期である(位数(群))。また $r$ は既約剰余類の群の位数 $\varphi(N)$ を割り切るので $r< N$ である。

量子 Fourier 変換

$m\ge1$、$Q:=2^m$、$\omega:=e^{2\pi i/Q}$ とし、$0\le x< Q$ を $m$ 量子ビットの計算基底 $|x\rangle$ と同一視する($x=\sum_{j=0}^{m-1}x_j2^j$、$x_j\in\{0,1\}$)。
$$ F_Q|x\rangle:=\frac1{\sqrt Q}\sum_{y=0}^{Q-1}\omega^{xy}|y\rangle $$
で定まる線形変換 $F_Q$ を 量子 Fourier 変換 という。$F_Q$ はユニタリである。

$F_Q$ の行列は 離散Fourier変換 の行列を $\sqrt Q$ で割ったものである。ユニタリであることは、$\sum_{z=0}^{Q-1}\omega^{(x-x')z}$ が $x=x'$ なら $Q$、そうでなければ等比数列の和で $0$ になることから従う。
位数を求める回路では、第 1 のレジスタ($m$ 量子ビット)と第 2 のレジスタ($\lceil\log_2N\rceil$ 量子ビット)に、作業用の量子ビットを加えて使う。

べき乗の剰余の変換

$U_a$ を、作業用の量子ビットを $0$ に戻したうえで
$$ U_a|x\rangle|0\rangle=|x\rangle|a^x\bmod N\rangle\qquad(0\le x< Q) $$
となる量子回路とする。

$a^x\bmod N$ の各ビットは、2 乗をくり返す古典の計算で桁数の多項式の大きさの論理回路で計算できるので、量子計算 の補題「可逆な模倣」をビットごとに使えば、$U_a$ は $m$ と $\log N$ の多項式の個数の門で作れる。
この記事の結論が成り立つ条件は次のとおりである。

  1. 帰着:$N$ は奇数で、相異なる素因数を $2$ 個以上もつ(素数の累乗ではない)。$a$ は $\{1,\dots,N-1\}$ の $N$ と互いに素な元から一様に選ぶ。
  2. 量子の部分:$\gcd(a,N)=1$、$N\ge15$ で、$Q=2^m$ は $N^2\le Q< 2N^2$ をみたす。

公式の表

量式・内容条件根拠
帰着の成功確率$r$ が偶数かつ $a^{r/2}\not\equiv-1\pmod N$ となる確率は $1-2^{1-k}$ 以上条件 1、$k$ は素因数の個数thm-sh-reduction
因数そのとき $\gcd(a^{r/2}-1,N)$ は $N$ の自明でない約数同上thm-sh-reduction
量子 Fourier 変換の積の形$F_Q\lvert x\rangle=\bigotimes_{k=0}^{m-1}\frac{\lvert0\rangle+e^{2\pi ix/2^{m-k}}\lvert1\rangle}{\sqrt2}$($k$ 番目が出力のビット $y_k$)$Q=2^m$thm-sh-qft
量子 Fourier 変換の門の数Hadamard 門と制御位相門が $m(m+1)/2$ 個、入れ替えが $\lfloor m/2\rfloor$ 個同上thm-sh-qft
測定値の分布$P(y)=\frac1{Q^2}\sum_{x_0=0}^{r-1}\Big\lvert\sum_{j=0}^{L_{x_0}-1}e^{2\pi ijry/Q}\Big\rvert^2$$L_{x_0}$ は $[0,Q)$ の $x_0$ と合同な整数の個数prf-sh-order
$r\mid Q$ のとき$y$ は $Q/r$ の倍数の上で一様ex-sh-15
山の高さ$y_d:=\lfloor dQ/r\rceil$(最も近い整数)について $P(y_d)\ge\frac3{10r}$条件 2、$0\le d< r$thm-sh-order
分数の復元$\gcd(d,r)=1$ なら $d/r$ は $y_d/Q$ の連分数展開の収束子条件 2lem-sh-cf
1 回の成功確率$\frac{3\varphi(r)}{10r}\ge\frac3{10(1+\log_2N)}$ 以上条件 2thm-sh-order、lem-sh-phi

因数分解から位数を求める問題へ

帰着

$N$ を奇数とし、$N=p_1^{e_1}\cdots p_k^{e_k}$($p_i$ は相異なる素数、$k\ge2$)とする。$a$ を $\{1,\dots,N-1\}$ の $N$ と互いに素な元から一様に選び、$r:=\operatorname{ord}_N(a)$ とする。

  1. $r$ が偶数かつ $a^{r/2}\not\equiv-1\pmod N$ となる確率は $1-2^{1-k}\ge1/2$ 以上である。
  2. そのとき $g:=\gcd(a^{r/2}-1,N)$ は $1< g< N$ をみたす。
2 進の付値を比べる

2 から示す。$b:=a^{r/2}$ とおくと $(b-1)(b+1)=a^r-1\equiv0\pmod N$ である。$r/2< r$ なので $b\not\equiv1$、仮定より $b\not\equiv-1\pmod N$ である。$g=1$ なら $N$ は $b-1$ と互いに素なので $N\mid b+1$ となり矛盾し、$g=N$ なら $N\mid b-1$ となり矛盾する。
1 を示す。中国剰余定理 により、$a$ を一様に選ぶことは、各 $i$ について $a_i\in(\mathbb Z/p_i^{e_i}\mathbb Z)^\times$ を独立に一様に選ぶことと同じである。$r_i:=\operatorname{ord}_{p_i^{e_i}}(a_i)$ とおくと $r=\operatorname{lcm}(r_1,\dots,r_k)$ である。整数 $s\ne0$ について、$s$ を割り切る $2$ の最大のべきの指数を $v(s)$ と書く。
(i) $v(r_1),\dots,v(r_k)$ がすべて等しくなければ成功することを示す。$t:=\max_iv(r_i)$ とすると $t\ge1$ で、$v(r)=t$ だから $r$ は偶数である。$v(r_j)< t$ となる $j$ をとると、$r_j\mid r/2$ なので $a^{r/2}\equiv1\pmod{p_j^{e_j}}$ である。$p_j$ は奇数なので $1\not\equiv-1\pmod{p_j^{e_j}}$ であり、$a^{r/2}\not\equiv-1\pmod N$ である。
(ii) 各 $i$ と各整数 $c$ について $\Pr[v(r_i)=c]\le1/2$ を示す。$p_i$ は奇素数なので $G:=(\mathbb Z/p_i^{e_i}\mathbb Z)^\times$ は位数 $n:=p_i^{e_i-1}(p_i-1)$ の巡回群である(原始根 の定理「原始根が存在する法」)。$n$ は偶数なので $v(n)=:s\ge1$ である。生成元 $g_0$ をとると $G$ の元は $g_0^j$($0\le j< n$)で、その位数は $n/\gcd(j,n)$ である。$j$ が奇数なら $\gcd(j,n)$ は奇数で $v(\text{位数})=s$、$j$ が偶数なら $v(\text{位数})\le s-1$ である。$j$ が奇数の元はちょうど半分なので、$c=s$ の確率は $1/2$、$c\ne s$ の確率の合計も $1/2$ で、どの $c$ についても $1/2$ 以下である。
(i) より、失敗するのは $v(r_1)=\cdots=v(r_k)$ のときに限られる。$a_1,\dots,a_k$ の独立性と (ii) から
$$ \Pr[v(r_1)=\cdots=v(r_k)]=\sum_c\Pr[v(r_1)=c]\prod_{i=2}^k\Pr[v(r_i)=c]\le\sum_c\Pr[v(r_1)=c]\cdot2^{1-k}=2^{1-k} $$
である。$k\ge2$ なので $1-2^{1-k}\ge1/2$ である。$\square$

この帰着の筋は Sho97 §5(pp. 15–16)に述べられている。$\gcd(a,N)>1$ となる $a$ を引いたときは、その $\gcd$ がすでに自明でない約数である。

量子 Fourier 変換の回路

$k\ge1$ について、1 量子ビットの位相門を $R_k:=\begin{pmatrix}1&0\\0&e^{2\pi i/2^k}\end{pmatrix}$ とし、量子ビット $c$ が $1$ のときだけ量子ビット $t$ に $R_k$ を施す 2 量子ビットの門を 制御 $R_k$ という。これは計算基底 $|z\rangle$ を、$z_c=z_t=1$ のとき $e^{2\pi i/2^k}$ 倍し、それ以外は動かさない対角行列である。

量子 Fourier 変換の回路

$m$ 量子ビットの状態 $|x\rangle$ に対し、$t=m-1,m-2,\dots,0$ の順に次を行う:量子ビット $t$ に Hadamard 門 $H$ を施し、続いて $c=t-1,t-2,\dots,0$ について、量子ビット $c$ を制御として量子ビット $t$ に $R_{t-c+1}$ を施す。最後に量子ビット $j$ と $m-1-j$ を入れ替える($0\le j< m/2$)。この回路は $F_Q$ に等しく、Hadamard 門と制御位相門を合わせて $m(m+1)/2$ 個、入れ替えを $\lfloor m/2\rfloor$ 個使う。

出力のビットごとの積に分ける

$y=\sum_{k=0}^{m-1}y_k2^k$ と書くと $\omega^{xy}=\prod_k e^{2\pi ixy_k2^k/2^m}=\prod_ke^{2\pi ixy_k/2^{m-k}}$ なので、
$$ F_Q|x\rangle=\bigotimes_{k=0}^{m-1}\frac{|0\rangle+e^{2\pi ix/2^{m-k}}|1\rangle}{\sqrt2}\qquad(\ast) $$
である。ここで $k$ 番目の因子は出力のビット $y_k$ の量子ビットにあたる。$e^{2\pi ix/2^{m-k}}$ は $x$ を $2^{m-k}$ で割った余り、すなわち $x_0,\dots,x_{m-k-1}$ だけで決まる。
回路を追う。量子ビット $t$ を処理するとき、量子ビット $t-1,\dots,0$ はまだ処理されておらず、入力の $x_{t-1},\dots,x_0$ のままである。量子ビット $t$ に $H$ を施すと、$H|x_t\rangle=(|0\rangle+e^{2\pi ix_t/2}|1\rangle)/\sqrt2$ になる。続く制御 $R_{t-c+1}$ は、$x_c=1$ のとき $|1\rangle$ の成分に $e^{2\pi ix_c/2^{t-c+1}}$ を掛けるので、処理の後の量子ビット $t$ は
$$ \frac{|0\rangle+e^{2\pi i\left(x_t/2+x_{t-1}/2^2+\cdots+x_0/2^{t+1}\right)}|1\rangle}{\sqrt2}=\frac{|0\rangle+e^{2\pi i(x\bmod2^{t+1})/2^{t+1}}|1\rangle}{\sqrt2} $$
である。$x$ と $x\bmod2^{t+1}$ の差は $2^{t+1}$ の倍数なので、これは $(\ast)$ の $k=m-1-t$ の因子に等しい。量子ビット $t$ の処理は、それより上の量子ビット(すでに処理済みのもの)に触れず、制御に使う量子ビットの値も変えない。よって全部を処理した後、量子ビット $t$ には出力のビット $y_{m-1-t}$ の因子が入っている。最後の入れ替えで量子ビット $t$ と $m-1-t$ を交換すると、状態は $(\ast)$ に一致する。
門の数は、量子ビット $t$ について $H$ が $1$ 個、制御位相門が $t$ 個なので、合計 $\sum_{t=0}^{m-1}(t+1)=m(m+1)/2$ である。$\square$

古典の 高速Fourier変換 は $Q$ 個の係数をすべて計算するのに $O(Q\log Q)$ 回の演算を要する。量子 Fourier 変換は $O(m^2)=O((\log Q)^2)$ 個の門で済むが、出力は状態であり、係数を全部読み出すことはできない。読めるのは、測定による $1$ 個の標本だけである。この構成は Sho97 §4(pp. 13–15)にある。

位数を求める回路

位数を求める回路は次のとおりである。

  1. 第 1 のレジスタの各量子ビットに $H$ を施して $\frac1{\sqrt Q}\sum_{x=0}^{Q-1}|x\rangle|0\rangle$ を作る。
  2. $U_a$ を施して $\frac1{\sqrt Q}\sum_x|x\rangle|a^x\bmod N\rangle$ を作る。
  3. 第 1 のレジスタに $F_Q$ を施し、第 1 のレジスタを測定して $y$ を得る。
    続く 2 つの補題は、測定値 $y$ から $r$ を取り出す古典の部分で使う。
連分数による分数の復元

$Q\ge N^2$、$1\le r< N$ とし、整数 $y,d$ が $\lvert y/Q-d/r\rvert\le1/(2Q)$、$\gcd(d,r)=1$ をみたすとする。このとき $d/r$ は、$y/Q$ を Euclid の互除法で展開した連分数の収束子である。

Legendre の判定法を使う

$\lvert y/Q-d/r\rvert\le1/(2Q)\le1/(2N^2)< 1/(2r^2)$ である。HW60 §10.15 Theorem 184(p. 153)により、既約分数 $p/q$ と実数 $\xi$ が $\lvert\xi-p/q\rvert< 1/(2q^2)$ をみたせば、$p/q$ は $\xi$ の連分数展開の収束子である(連分数)。
$\xi$ が整数なら、既約分数 $p/q$ で $q\ge2$ のものは $\lvert\xi-p/q\rvert\ge1/q>1/(2q^2)$ をみたすので $p/q=\xi/1$ であり、これは展開 $[\xi]$ の収束子である。$\xi$ が整数でない有理数のときは展開が 2 通りあるので、Euclid の互除法の展開(最後の部分商が $2$ 以上)の収束子であることを確かめる。$\xi=[a_0;a_1,\dots,a_n]$($n\ge1$、$a_n\ge2$)の収束子を $p_j/q_j$ とすると、もう一つの展開 $[a_0;\dots,a_n-1,1]$ の収束子は、それに $p'/q':=(p_n-p_{n-1})/(q_n-q_{n-1})$ を加えたものである。$\lvert\xi-p'/q'\rvert=1/(q_nq')$ である。$q_n=a_nq_{n-1}+q_{n-2}\ge2q_{n-1}$ なので $q'=q_n-q_{n-1}\ge q_n/2$、すなわち $q_n\le2q'$ であり、$1/(q_nq')\ge1/(2q'^2)$ となる。よって $p'/q'$ は不等式 $\lvert\xi-p/q\rvert< 1/(2q^2)$ をみたさず、$d/r$ は Euclid の互除法の展開の収束子である。$\square$

Euler 関数の下界

$r\ge1$ について $\varphi(r)/r\ge1/(1+\log_2r)$ である。ここで $\varphi$ は Euler関数 である。

小さい素数で抑える

$r$ の相異なる素因数を $p_1< \cdots< p_k$ とすると $\varphi(r)/r=\prod_{i=1}^k(1-1/p_i)$ である。$p_i\ge i+1$ なので、これは $\prod_{i=1}^k\frac i{i+1}=\frac1{k+1}$ 以上である。$2^k\le r$ より $k\le\log_2r$ である。$\square$

位数を求める回路の成功確率

$N\ge15$、$\gcd(a,N)=1$、$r:=\operatorname{ord}_N(a)$ とし、$Q=2^m$ は $N^2\le Q< 2N^2$ をみたすとする。

  1. 上の回路の測定値が $y$ である確率は $P(y)=\frac1{Q^2}\sum_{x_0=0}^{r-1}\Big\lvert\sum_{j=0}^{L_{x_0}-1}e^{2\pi ijry/Q}\Big\rvert^2$ である。ここで $L_{x_0}$ は $0\le x< Q$、$x\equiv x_0\pmod r$ となる $x$ の個数である。
  2. $0\le d< r$ について $y_d:=\lfloor dQ/r\rceil$($dQ/r$ に最も近い整数)とおくと、$P(y_d)\ge\frac3{10r}$ である。
  3. $y$ を測定し、$y/Q$ の連分数展開の収束子のうち分母 $q$ が $N$ 未満で $a^q\equiv1\pmod N$ となる最小の $q$ を出力すると、それが $r$ である確率は $\frac{3\varphi(r)}{10r}\ge\frac3{10(1+\log_2N)}$ 以上である。
等比数列の和を下から抑える

1:$F_Q$ を施した後の状態は $\frac1Q\sum_{x}\sum_y\omega^{xy}|y\rangle|a^x\bmod N\rangle$ である。$a^x\bmod N$ は $x\bmod r$ だけで決まり、$x_0=0,\dots,r-1$ に対する値 $a^{x_0}\bmod N$ は相異なる。よって測定値が $y$ で第 2 のレジスタが $a^{x_0}\bmod N$ である確率は、$x=x_0+jr$($0\le j< L_{x_0}$)とおいて
$$ \frac1{Q^2}\Big\lvert\sum_{j}\omega^{(x_0+jr)y}\Big\rvert^2=\frac1{Q^2}\Big\lvert\sum_{j=0}^{L_{x_0}-1}e^{2\pi ijry/Q}\Big\rvert^2 $$
であり、$x_0$ について足すと主張 1 の式を得る(第 2 のレジスタは測っても測らなくても $y$ の分布は同じである)。
2:$\delta:=ry_d/Q-d$ とおく。$\lvert y_d-dQ/r\rvert\le1/2$ より $\lvert\delta\rvert\le r/(2Q)$ である。$L:=L_{x_0}$ とする。$\delta=0$ なら内側の和は $L$ である。$\delta\ne0$ なら、等比数列の和の公式から内側の和の絶対値は
$$ \left\lvert\frac{\sin(\pi L\delta)}{\sin(\pi\delta)}\right\rvert\ge\frac{\sin s}{\pi\lvert\delta\rvert}=L\cdot\frac{\sin s}s,\qquad s:=\pi L\lvert\delta\rvert $$
である($\lvert\sin t\rvert\le\lvert t\rvert$ を分母に使った)。$L\le Q/r+1$ と $r< N\le\sqrt Q$、$N\ge15$ から
$$ s\le\pi\Big(\frac Qr+1\Big)\frac r{2Q}=\frac\pi2\Big(1+\frac rQ\Big)\le\frac\pi2\cdot\frac{16}{15}=\frac{8\pi}{15} $$
である。$\sin t/t$ は $(0,\pi)$ で減少するので、$\sin s/s\ge\sin(8\pi/15)/(8\pi/15)> 0.5935$ である。また $L\ge\lfloor Q/r\rfloor> Q/r-1\ge\frac{14}{15}\cdot\frac Qr$($r/Q< 1/N\le1/15$ による)。以上を $r$ 個の $x_0$ について足すと
$$ P(y_d)\ge r\cdot\frac1{Q^2}\Big(\frac{14}{15}\cdot\frac Qr\Big)^2(0.5935)^2=\frac{0.3068\cdots}{r}\ge\frac3{10r}. $$
3:$Q/r> 1$ なので $y_0,\dots,y_{r-1}$ は相異なる。$\gcd(d,r)=1$ となる $d$ は $\varphi(r)$ 個ある。そのような $d$ について $y=y_d$ を測定すれば、$\lvert y_d/Q-d/r\rvert\le1/(2Q)$ なので、lem-sh-cf により $r$ は分母 $N$ 未満の収束子の分母に現れる。$q< r$ なら $a^q\not\equiv1$ であり、$a^q\equiv1$ となる $q$ は $r$ の倍数なので、出力される最小の $q$ は $r$ である。よって成功確率は $\varphi(r)\cdot\frac3{10r}$ 以上で、lem-sh-phi と $r< N$ から $\frac3{10(1+\log_2N)}$ 以上である。$\square$

Sho97 §5(pp. 16–19)は同じ回路を、第 1 と第 2 のレジスタを両方測る形で解析し、成功確率が $\log\log N$ 分の 1 の程度であることを示している。この記事の評価は $\log N$ 分の 1 で粗いが、繰り返しの回数を $O(\log N)$ 回にすれば十分である。
図: 横軸が測定値 y(0 から 511)、縦軸がその確率の棒グラフ。N=21、a=2、位数 6、Q=512 の場合で、y=0 と 256 に高さ約 0.167 の山、y=85、171、341、427 に高さ約 0.114 の山があり、どれも 512d/6 を示す破線の位置にある。山の間の確率はほぼ 0 である。 図: 横軸が測定値 y(0 から 511)、縦軸がその確率の棒グラフ。N=21、a=2、位数 6、Q=512 の場合で、y=0 と 256 に高さ約 0.167 の山、y=85、171、341、427 に高さ約 0.114 の山があり、どれも 512d/6 を示す破線の位置にある。山の間の確率はほぼ 0 である。

計算の手順

$N$ の自明でない約数を 1 つ求めるには、次のようにする。

  1. $N$ が偶数なら $2$ を出力する。$N$ が素数なら止める(素数判定は古典の多項式時間でできる。素数判定)。
  2. $2\le c\le\log_2N$ の各 $c$ について $N$ の整数の $c$ 乗根 $b$ を二分法で求め、$b^c=N$ なら $b$ を出力する。これで素数の累乗が除かれる。
  3. $a\in\{2,\dots,N-1\}$ を一様に選ぶ。$g=\gcd(a,N)>1$ なら $g$ を出力する。
  4. 位数を求める回路で $y$ を測定し、thm-sh-order の 3 の方法で $q$ を求める。$q$ が見つからなければ 4 を繰り返す($O(\log N)$ 回で高い確率で $r$ が得られる)。
  5. $q$ が偶数なら $g:=\gcd(a^{q/2}-1,N)$ を求め、$1< g< N$ なら $g$ を出力する。そうでなければ 3 に戻る。見つかった $q$ は $a^q\equiv1$ をみたすので $r$ の倍数だが、$r$ に等しいとは限らない。
    手順 3 で $a=1$ を除いても、$1$ はもともと thm-sh-reduction の失敗の側($r=1$ は奇数)なので、成功確率の下界は下がらない。$q=r$ のとき、手順 5 は thm-sh-reduction により確率 $1/2$ 以上で $g$ を出力する。

例題

$N=15$、$a=7$

使う公式:thm-sh-order、thm-sh-reduction。
答え:$r=4$。$Q=256$ で測定値は $0,64,128,192$ がそれぞれ確率 $1/4$。$y=64$ と $192$ から $r=4$ が得られ(成功確率 $1/2$)、$7^2\equiv4$ から $\gcd(3,15)=3$、$\gcd(5,15)=5$ である。

途中の計算を開く

$7,7^2=49\equiv4,7^3\equiv28\equiv13,7^4\equiv91\equiv1\pmod{15}$ で $r=4$。$225\le256< 450$ なので $Q=256$。$r=4$ は $Q$ を割り切るので、内側の和は $y$ が $Q/r=64$ の倍数のとき $L=64$、それ以外は $0$ になり、$P(y)=4\cdot64^2/256^2=1/4$。$64/256=1/4$ の収束子は $0/1,1/4$ で、$7^4\equiv1$ から $q=4$。$192/256=[0;1,3]$ の収束子は $0/1,1/1,3/4$ で $q=4$。$128/256=1/2$ からは $q=2$ が出るが $7^2\not\equiv1$ なので失敗、$y=0$ も失敗する。$a^{r/2}=4\not\equiv-1$ なので帰着も成功する。

$N=21$、$a=2$

使う公式:thm-sh-order、lem-sh-cf。
答え:$r=6$、$Q=512$。$y_1=85$、$y_5=427$ の確率はどちらも約 $0.113989$ で、$r\,P(y_d)\approx0.684\ge0.3$ である。$85/512$ の収束子 $1/6$ から $r=6$ が得られる。1 回の成功確率は約 $0.3282$ で、下界 $\frac{3\varphi(6)}{10\cdot6}=0.1$ を上回る。$2^3=8$ から $\gcd(7,21)=7$、$\gcd(9,21)=3$ である。

途中の計算を開く

$2^6=64\equiv1\pmod{21}$ で、それより小さい指数では $1$ にならないので $r=6$。$441\le512< 882$ なので $Q=512$。$y_0=0$、$y_3=256$ では $\delta=0$ で $P\approx0.166672$。$85/512=[0;6,42,2]$ の収束子は $0/1,1/6,42/253,85/512$ で、分母が $21$ 未満で $2^q\equiv1$ となるのは $q=6$。$427/512=[0;1,5,42,2]$ の収束子 $5/6$ からも $q=6$。$y_2=171$ からは $1/3$ が出て $2^3=8\not\equiv1$ なので失敗する。成功確率が $2\times0.114$ より大きいのは、山のすぐ隣の $y$ からも $r$ が復元されるためである。

帰着が成功する $a$ の割合

使う公式:thm-sh-reduction。
答え:$N=15$ では $8$ 個の単元のうち $2,4,7,8,11,13$ の $6$ 個($3/4$)、$N=21$ では $12$ 個中 $6$ 個($1/2$)、$N=105=3\cdot5\cdot7$ では $48$ 個中 $42$ 個($7/8\ge1-2^{-2}=3/4$)である。

途中の計算を開く

$N=15$ で $a=14$ は $r=2$、$a^{r/2}=14\equiv-1$ で失敗、$a=1$ は $r=1$ で失敗する。$N=21$ で $a=4$ は $4,16,64\equiv1$ で $r=3$(奇数)なので失敗する。成功する $a$ ではいつも $1< \gcd(a^{r/2}-1,N)< N$ であることも全数で確かめた。

$m=2$ の量子 Fourier 変換

使う公式:def-sh-qft、thm-sh-qft。
答え:$Q=4$、$\omega=i$ で、
$$ F_4=\frac12\begin{pmatrix}1&1&1&1\\1&i&-1&-i\\1&-1&1&-1\\1&-i&-1&i\end{pmatrix} $$
(第 $y$ 行第 $x$ 列が $\omega^{xy}/2$)。回路は量子ビット 1 に $H$、量子ビット 0 を制御とする制御 $R_2$($R_2=\mathrm{diag}(1,i)$)、量子ビット 0 に $H$、最後に 2 つを入れ替える。門は $3=2\cdot3/2$ 個である。

途中の計算を開く

$x=1$($x_0=1,x_1=0$)のとき、量子ビット 1 は $H$ で $(|0\rangle+|1\rangle)/\sqrt2$、制御 $R_2$ で $(|0\rangle+i|1\rangle)/\sqrt2$。量子ビット 0 は $H$ で $(|0\rangle-|1\rangle)/\sqrt2$。入れ替えると量子ビット 0 が $(|0\rangle+i|1\rangle)/\sqrt2$、量子ビット 1 が $(|0\rangle-|1\rangle)/\sqrt2$ で、展開すると $\frac12(|0\rangle+i|1\rangle-|2\rangle-i|3\rangle)$。これは $F_4$ の第 2 列 $(1,i,-1,-i)/2$ に一致する。

使える条件と反例

外す条件反例成り立たなくなること
$N$ が素数の累乗でない$N=9$単元 $6$ 個のどれでも帰着が失敗し、thm-sh-reduction の確率 $1/2$ 以上が成り立たない
$N$ が奇数$N=6$単元は $1,5$ だけで、どちらも失敗する
$Q\ge N^2$$N=21$、$a=2$ で $Q=16$1 回の成功確率が $0$ になり、thm-sh-order の 3 が成り立たない
$\gcd(d,r)=1$$N=21$、$a=2$ で $y_2=171$収束子 $1/3$ から位数の約数 $3$ しか出ない
反例の確かめ

各行で外した条件のほかは、記事の設定のままである。

各行の確かめを開く

1 行目:$(\mathbb Z/9\mathbb Z)^\times$ は位数 $6$ の巡回群で、$-1\equiv8$ がただ 1 つの位数 $2$ の元である。$r$ が偶数なら $a^{r/2}$ は位数 $2$ なので $-1$ になり、必ず失敗する。$N=25,27$ でも全数で $0$ 個だった。

2 行目:$5\equiv-1\pmod6$ で $r=2$、$a^{r/2}\equiv-1$。$N$ が偶数なら $2$ が約数なので量子の部分は要らない。

3 行目:$Q=16$ では $y_d/16$ と $d/6$ の差が $1/32$ まで許され、分母 $21$ 未満の別の分数と区別できない。全ての $y$ で $q=6$ が復元されなかった。$Q=32,64,\dots,512$ では成功確率は $0.2295,0.2858,0.3135,0.3229,0.3282$ と上がる。

4 行目:$171/512=[0;2,1,170]$ の収束子は $0/1,1/2,1/3,171/512$ で、$d/r=2/6$ が約分されて $1/3$ になる。複数回の測定で得た分母の最小公倍数をとると $r$ を回復できることがある。

よくある誤り

誤り正しくはなぜ
量子 Fourier 変換の出力から全ての Fourier 係数が読める測定で $y$ が 1 つ得られるだけ状態の振幅は測定で読み出せない(量子計算)
測定値 $y$ を $Q$ で割れば $1/r$ が得られる得られるのは $d/r$ の近似で、$d$ は一様に近い分布thm-sh-order
連分数で出た分母はいつも位数$\gcd(d,r)>1$ なら約数しか出ない。$a^q\equiv1$ を確かめる反例の表の 4 行目
どの $a$ でも $\gcd(a^{r/2}-1,N)$ が約数になる$r$ が奇数か $a^{r/2}\equiv-1$ なら失敗するthm-sh-reduction
Shor のアルゴリズムは NP 完全問題を解く解くのは因数分解と離散対数で、NP 完全とは知られていないP対NP問題

補足

  • 門の数.$U_a$ は $m$ 回の 2 乗と掛け算で作れるので、全体の門の数は $O((\log N)^3)$ である。高速な掛け算を使うと $O((\log N)^2(\log\log N)(\log\log\log N))$ になる(Sho97 p. 15)。
  • 離散対数.同じ考え方で、2 変数の関数 $(x_1,x_2)\mapsto g^{x_1}h^{-x_2}$ の周期を求めて 離散対数問題 も多項式時間で解ける(Sho97 §6)。
  • 周期の発見.帰着と量子 Fourier 変換を分けて考えると、Shor のアルゴリズムは「関数の周期を求める」問題を解く算法として述べられる(AB07 §20.7、pp. 422–428)。
  • 探索との違い.Groverのアルゴリズム は構造のない探索で、全探索の平方根の程度しか速くならない。Shor のアルゴリズムは関数の周期という構造を使うので、古典の既知の算法との差がはるかに大きい。

関連項目

参考文献

[1]
Peter W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Journal on Computing, 1997, pp. 1484–1509。頁は arXiv 版(quant-ph/9508027v2)による:§4(pp. 13–15)、p. 15、§5(pp. 15–19)、§6

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する