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$ の連分数展開から求める。
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$ である。
$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$ の多項式の個数の門で作れる。
この記事の結論が成り立つ条件は次のとおりである。
| 量 | 式・内容 | 条件 | 根拠 |
|---|---|---|---|
| 帰着の成功確率 | $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$ の連分数展開の収束子 | 条件 2 | lem-sh-cf |
| 1 回の成功確率 | $\frac{3\varphi(r)}{10r}\ge\frac3{10(1+\log_2N)}$ 以上 | 条件 2 | thm-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)$ とする。
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$ がすでに自明でない約数である。
$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}$ 倍し、それ以外は動かさない対角行列である。
$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)にある。
位数を求める回路は次のとおりである。
$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 の互除法で展開した連分数の収束子である。
$\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$
$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:$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 である。
$N$ の自明でない約数を 1 つ求めるには、次のようにする。
使う公式: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$ なので帰着も成功する。
使う公式: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$ が復元されるためである。
使う公式: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$ であることも全数で確かめた。
使う公式: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問題 |
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する