Discrete Log(離散対数問題) 〜Quantum Zooやっていく〜

July 19, 2021, 3:14 p.m. edited July 22, 2021, 6:51 a.m.

#Quantum Zoo  #量子情報  #量子力学 

$$ \def\bra#1{\mathinner{\left\langle{#1}\right|}} \def\ket#1{\mathinner{\left|{#1}\right\rangle}} \def\braket#1#2{\mathinner{\left\langle{#1}\middle|#2\right\rangle}} $$

まさかの第二回。

背景

Shor のアルゴリズム における周期発見アルゴリズムの応用先の一つ。最速の古典アルゴリズムでは \(n\) (定義は次節の問題にて)に関する超多項式時間1かかるのに対し、 Peter Shor (またこの人)により \(\mathrm{poly}(n)\) 時間の計算量で解ける量子アルゴリズムが得られた。

問題

\(p\) を \(n\) ビットの素数とし2、 \(Z_p^\ast={1,\dots,p-1}\) とする。 \(\alpha\) を \(Z_p^\ast\) の生成子とし3、 \(\beta\in Z_p^\ast\) とする。 \(p\), \(\alpha\), \(\beta\) が与えられたとき、 \(\alpha^d=\beta\) を満たす \(d\in[0, p-1]\) を求める4

アルゴリズム

内容は基本的に Shor による周期発見アルゴリズムと同じである。ただし、二変数関数でそれぞれに周期が存在するというところが異なる。今回こそ [P. Shor, 1996] (p.20) に従いたかったが、よくわからなかったので、楕円曲線への適用をした [J. Proos and C. Zalka, 2004] のレビューにあった内容 (2章) に従う。

\(\alpha^q=1\) を満たすような素数 \(q\) を考えると、 \(0\leq d\leq q\) となる。そのうえで \(f(x,y)=\alpha^x\beta^y\) を整数 \(x\), \(y\) について定義する。この関数 \(f\) は 2 つの独立な周期をもつ。

$$f(x+q,y)=f(x,y),\ f(x+d,y-1)=f(x,y)$$

この関数 \(f\) を用いて、重ね合わせ状態

$$\frac{1}{q}\sum_{x=0}^{q-1}\sum_{y=0}^{q-1}\ket{x}\ket{y}\ket{0}$$

から

$$\frac{1}{q}\sum_{x=0}^{q-1}\sum_{y=0}^{q-1}\ket{x}\ket{y}\ket{\alpha^x\beta^y}$$

を得る。ここで、最後のレジスタ \(\ket{\alpha^x\beta^y}\) に測定をし、 \(\alpha^{x_0}\) が得られたとする。すると、

$$\alpha^x\beta^y=\alpha^x(\alpha^d)^y=\alpha^{x_0}$$

より、 \(x+dy\equiv x_0\bmod q\) 、つまり、 \(x=(x_0-dy)\bmod q\) となる。したがって、状態は

$$\frac{1}{\sqrt{q}}\sum_{y=0}^{q-1}\ket{x_0-dy}\ket{y}$$

となる。ここに量子フーリエ変換を適用し、

$$ \begin{align} &\frac{1}{\sqrt{q}}\frac{1}{q}\sum_{x',y'=0}^{q-1}\sum_{y=0}^{q-1}e^{2\pi i((x_0-dy)x'+yy')/q}\ket{x'}\ket{y'}\tag{1}\\ =&\frac{1}{\sqrt{q}}\sum_{x'=0}^{q-1}e^{2\pi ix_0 x'/q}\ket{x'}\ket{y'\equiv dx'\bmod q}\tag{2} \end{align} $$

を得る。これを測定し、得られた \(x'\neq 0\), \(y'\) を用いて

$$d=y'(x')^{-1}\bmod q$$

と求まる。

なぜ

雰囲気は素因数分解と似ているが、例えば式(1)から式(2)への変形でなぜ \(y'\equiv dx'\bmod q\) を満たさない項が消えるのか等、よくわからんことが多すぎる。


  1. 多項式時間ではできないという計算量 

  2. \(p\) と互いに素な \(p\) より小さい自然数が少ないと古典でも Pohlig–Hellman algorithm により簡単に解かれてしまう ので、ここでは素数に限定している 

  3. つまり、 \(\alpha^0, \alpha^1, \dots, \alpha^{p-1}\in Z_p^\ast\) 

  4. これと \(\alpha^d\equiv\beta\bmod p\) は等価らしい。また、より一般的な離散対数問題は群の言葉を使って表されるらしい