（未完）Pell's Equation（ペル方程式）〜Quantum Zooやっていく〜 実装編

Jan. 3, 2023, 3:24 p.m. edited June 5, 2023, 1:56 p.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}} $$

（未完）230605 時点。理由：オラクルの実装難しい……

Pell's Equation（ペル方程式）〜Quantum Zooやっていく〜 準備編 の続き。今回で Qiskit による実装までおこない完成させる。引き続き [R. Jozsa, 2003] にしたがう。

周期関数 \(h\) の離散化

前回最後に導入した周期関数 \(h\) は第二成分が実数なので、これを量子計算機で実装するために離散化する必要がある。表記として、 principle cycle を \(\mathcal{PI}_\text{red}=\{J_0=\mathcal{O},J_1,\dots,J_{k_0-1}\}\) と表すことにする（任意の principle reduced ideal は principle cycle に含まれるので、 \(\mathcal{PI}_\text{red}\) という名前となっている）と、周期関数 \(h\) は

$$h:\mathbb{R}\to\mathcal{PI}_\text{red}\times\mathbb{R}\qquad h(x)=(I_x,\tilde{x}-\delta(I_x))$$

となる。これを離散化したものを \(\tilde{h}_N\) とすると、

$$\tilde{h}_N:\mathbb{R}\to\mathcal{PI}_\text{red}\times\frac{1}{N}\mathbb{Z}\qquad \tilde{h}_N(k)=(I_{k/N},\left\lfloor k/N-\delta(I_{k/N})\right\rfloor_N)$$

と表される。ただし、 \(N\) は十分大きな整数で、実数を \(k/N\) で表している。その大きさとしては、 \(d_\mathit{min}=3/(32D)\) とすると \(1/N<d_\mathit{min}/\log d\) である。

なお、 \(\tilde{h}_N\) は weakly periodic な関数である。これは通常の periodic な関数（周期関数）と異なり、以下の定義となっている：

関数 \(f\) について、 \(S\in \mathbb{R}\) を用いてそれぞれの \(0\leq k\leq \lfloor S\rfloor\) および \(l\in\mathbb{Z}\) にて

$$f(k+\lfloor lS\rfloor)=f(k)$$

もしくは

$$f(k+\lceil lS\rceil)=f(k)$$

が成り立つならば、その関数を weakly periodic という。ここで、 \([lS]\) で \(\lfloor lS\rfloor\) もしくは \(\lceil lS\rceil\) を表すとする（どちらを表すかはそのときの \(k\) や \(l\) により変わって良い）と、上の条件式は \(f(k+[lS])=f(k)\) と書ける。

量子アルゴリズム

ここからようやく量子アルゴリズムの節となる。ここでは上で用いた weakly periodic な関数である \(f\) を用いた一般的な記述をする。それから、追加の表記として \(\lfloor x\rceil\) を \(x\) に最も近い整数とする（ゆえに \(|x-\lfloor x\rceil|\leq1/2\)）。また、 \(f(x)\) を \(\text{poly}(\log S)\) で計算できるとする。

まず、 \(2\) のべき乗となるような \(q\geq 3S^2\) について以下の状態を作る。

$$\frac{1}{\sqrt{q}}\sum_{m=0}^{q-1}\ket{m}\ket{f(m)}\tag{1}$$

ここまでにかかる時間は \(\text{poly}(\log S)\)。ここで

$$q=pS+r\qquad p,r\in\mathbb{Z}\quad 0\leq r<S$$

とおいて、状態 (1) の 2 番目のレジスタを測定すると 1 番目のレジスタは、

$$\ket{\psi_0}=\frac{1}{\sqrt{p}}\sum_{i=0}^{p-1}\ket{k+[iS]}$$

となる。ただし、 \(k\) は \(0\leq k\leq\lfloor S\rfloor\) の中で一様ランダムに選ばれる。ここに量子フーリエ変換をおこなうと、

$$ \begin{align} &\frac{1}{\sqrt{pq}}\sum_{l=0}^{p-1}\sum_{j=0}^{q-1}\exp\left(2\pi i\frac{j(k+[lS])}{q}\right)\ket{j} \\ =&\sum_{j=0}^{q-1}a_j\ket{j} \end{align} $$

が得られる。ここで、必要とするのは \(|a_j|^2\) であり \(k\) には依存しないので、

$$a_j=\frac{1}{\sqrt{pq}}\sum_{l=0}^{p-1}e^{2\pi i\frac{j[lS]}{q}}$$

とする。さて、\(j\) のうち、 \(q/S\) の倍数に最も近い整数である \(j\) に着目すると、それらは

$$j=\left\lfloor\frac{kq}{S}\right\rceil=\frac{kq}{S}+\epsilon\quad 0\leq k\leq S\ \text{and}\ -\frac{1}{2}\leq\epsilon\leq\frac{1}{2}$$

と表される。そしてこれらの \(j\) は \(j<q/\log S\) とする。すると、そのような \(\ket{j}\) が測定で得られる確率である \(|a_j|^2\) は、定数 \(c\) を用いて

$$|a_j|^2\geq \frac{c}{S}$$

と表される（証明は文献 p.27 参考）。

ここまでのアルゴリズムを 2 度実行すると、 \(1/\text{poly}(\log S)\) の確率で次の 2 つの \(j\) が得られる。それらを \(c\), \(d\) とすると（この \(c\) はつい先ほどの定数 \(c\) とは異なることに注意）、

$$c=\left\lfloor\frac{kq}{S}\right\rceil\quad d=\left\lfloor\frac{lq}{S}\right\rceil$$

と表される。ただし、 \(\gcd(k,l)=1\)。ここから \(k\) を得るためやはり連分数展開を用いる。 \(k/l\) は \(c/d\) の連分数展開における近似分数として得られるので、その分子から \(k\) が求まる。 \(\frac{c_n}{d_n}\) を \(\frac{c}{d}\) の convergents とする。

ここで前提として、ある \(m\in\mathbb{Z}\) が与えられたとき、ある \(j\in\mathbb{Z}\) について \(|jS-m|<1\) が成り立つか否かを \(\text{poly}(\log S)\) の時間計算量で判定可能とする。

この前提をもとに、 \(m=\left\lfloor\frac{c_n q}{c}\right\rceil\) として、 \(|jS-m|<1\) が成り立てば、その最小の \(m\) が本アルゴリズムの出力となる。