ショアのアルゴリズム：QFTの結果を2回読んだ後はどうすればよいですか？
私は、フーリエ変換のプロットを見て時間を特定する方法について尋ねました。答えは、フーリエ変換を複数回実行して、グラフで示される高い確率に関連付けられた複数の値を取得することであるようです。したがって、同じ画像を引き続き使用して、それを2回読み、値| 5>と| 11>を取得したとします。これらは最も高いスパイクです（| 0>の最初の最も高い後）。5と11のうちの期間12をどのように把握しますか？計算例を教えてください。
試みられた解決策。Peter Shorの論文（320ページ）を読むと、彼の論文が$q$ です $q=64$この例では。ショールは分数を得ることができると言っています$d/r$ 最低条件で（ここで $r = 12$ ここで）丸めることによって $c/q$ 分母がより小さい最も近い分数に $n=35$ここに。私たちの可能性$c$ ここは $5$ そして $11$。
それを試してみましょう。QFTの後、$c = 5$ そして私達は持っています $q = 64$。だから私たちは得る$5/64 = 0.078125$ それを分母がより小さい最も近い分数に丸めたい $35$。にとって$5/64$、連分数を見つけます $[0,12,1,4]$。（私はそれをチェックしました$5/64 = 1/(12 + 1/(1 + 1/4))$、それは正しいです。）さて、この連分数（リスト形式）から、次の分数のシーケンスを取得します。 $1/4, 5/4, 64/5, 5/64$。（私が何をしているのかわかりません。）おそらく$5$運が悪いですか？しかし、いいえ、同じことを試してみてください$11$ も生成します $11/64$。したがって、連分数アルゴリズムの計算方法は知っていても、それをどうすればよいかわかりません。ハーディとライトの第X章を見る必要があります。
回答
これは、ウィキペディアのステップ5のアルゴリズムの連分数部分です。あなたが測定したのは$y$ そのような $\frac{yr}{Q}\approx c$、 どこ $c$ 未知の整数です、 $r$ は隠された期間（この場合は12）であり、 $Q=64$QFTのサイズです。この意味は$\frac{y}{Q}\approx \frac{c}{r}$。にとって$y=5$、 我々は持っています $\frac{5}{64}\approx \frac{1}{12}$、および $y=11$、 我々は持っています $\frac{11}{64}\approx \frac{2}{12}$。これが測定値と周期の関係です。
ただし、これらの値から実際に期間を見つけるにはどうすればよいですか（わからないため） $c$ または $r$）？連分数あり。数の連分数$x$ で再帰的に定義されます $a_0=x$、そして $b_n=\lfloor a_n\rfloor$、および $a_n=\frac{1}{a_{n-1}-b_{n-1}}$。この問題に適用されます$x=\frac{5}{64}$、 我々は持っています
$$ a = (\frac{5}{64},\frac{64}{5},\frac{5}{4},4,0,\dots)$$ $$ b = (0,12,1,4,0,\dots)$$
これから、近似を再構築することができ、これらの近似の分母はおそらく周期になります。連分数のウィキペディアのページでは、我々はおおよその分画のシリーズを取得することを説明し$\frac{h_n}{k_n}$、分子を設定します $h_n=b_nh_{n-1}+h_{n-2}$ と分母 $k_n=b_nk_{n-1}+k_{n-2}$、初期値付き $h_{-1}=1$、 $h_{-2}=0$、 $k_{-1}=0$、および $k_{-2}=1$。これにより、次の2つのシーケンスが得られます。
$$h = (0, 1, 0, 1, 1, 5)$$ $$ k = (1,0, 1, 12, 13, 64)$$
これは3つのおおよその分数を与えます： $\frac{1}{12}$、 $\frac{1}{13}$、および $\frac{5}{64}$。最後のものは私たちが始めたものであり、64が大きすぎるので役に立たない（結局のところ、期間は35未満でなければなりません）。1つ目は実際の期間です。
連分数についてはよくわかりませんが、これらの近似は元の分数に非常にすばやく収束すると思います。したがって、実際には、（a）近似分数はそれほど多くないはずであり、（b）Shorの最終ステップであるため、近似分数のシーケンス（この場合は12と13の両方）で各分母をチェックするだけだと思います。アルゴリズムはとても安価です。