プログラミング量子コンピューターのこのQFT後のグラフ(241ページ)の興味深いスパイクは何ですか?
ショアのアルゴリズムを理解しようとしているプログラミング量子コンピューターを読んでいます。そこで私たちは国家を準備することを学びました$|x^i \bmod N\rangle$、次にQFTをこの状態に適用します。QFTは、振幅を均一な重ね合わせから、次の周期で等間隔に配置された大きな振幅に変更します。$x^i \bmod N$。たとえば、QFTを適用した後の振幅のグラフは次のとおりです。$N = 35$。それは241ページにあります。

この本には、12個のスパイクが等間隔にあると書かれています。等間隔に12個以上のスパイクがあります。最高のものだけを数え、12を数えたら停止する必要がありますか?しかし、それは主観的ではありませんか?正しい答えがわからないままこのグラフを見ただけで、実際に12であることがどうやってわかりますか?(言い換えれば、どうすればこれから12を得ることができますか?)
回答
再現したグラフを見ると、左のグラフは $2^x\bmod 35$ にとって $x\in\{0,\dots 63\}$ 右のグラフは、の離散フーリエ変換の振幅を示しています。 $\hat{x}\in\{0,\dots 63\}$。「12個の等間隔のスパイクがある」というコメントは、右のグラフの極大値が毎回繰り返されることを示しています$64/12=5.33$ 値。
あなたは正しいです、あなたはにアクセスできません $\hat{x}$ この周期性を観察できるように $\hat{x}$すぐに; しかし、何をやるにアクセスすることができ、サンプルへの道であります$\hat{x}_i$ 複数の場合 $i$ 戻る方法で $\hat{x}_i$ それぞれの高さ(の二乗)によって与えられる確率で $\hat{x}_i$。
たとえば、べき乗剰余(左のグラフ)に続いてQFT(右のグラフ)を実行し、最初のレジスタをサンプリングすると、次のような値が得られる可能性があります。 $0$ より高い確率で $5$、より高い確率で $32$、より高い確率で $11$、より高い確率で $6$、など。
これらのそれぞれのサンプリングから $\hat{x}_i$、ショアのアルゴリズムの古典的な部分(連分数部分)を実行して、実際に、12個の等間隔のスパイクがあったことを推測できます。 $\hat{x}$、あなたに期間を与える $12$ に $2^x\bmod 35$。私が忘れている詳細はたくさんありますが、重要なのは、QFTからのサンプルをこの古典的な部分への入力として使用するということです。