量子カウントアルゴリズム

量子計数アルゴリズムは、与えられた探索問題に対する解の数を効率的に数える量子アルゴリズムです。このアルゴリズムは、量子位相推定アルゴリズムとグローバーの探索アルゴリズムに基づいています。

計数問題は、統計的推定、統計物理学、ネットワークなど、さまざまな分野で一般的です。量子コンピューティングに関しては、グローバーの探索アルゴリズムを使用するために、量子計数を効率的に実行する機能が必要です（グローバーの探索アルゴリズムを実行するには、解がいくつ存在するかを知る必要があるため）。さらに、このアルゴリズムは、量子存在問題（つまり、解が存在するかどうかを判断する問題）を特別なケースとして解決します。

このアルゴリズムは、 1998 年にGilles Brassard、Peter Høyer、Alain Tapp によって考案されました。

サイズの有限集合と「解」の集合（つまり のサブセット）を考えます。定義: ${\displaystyle \{0,1\}^{n}}$${\displaystyle N=2^{n}}$${\displaystyle B}$${\displaystyle \{0,1\}^{n}}$

${\displaystyle {\begin{cases}f:\left\{0,1\right\}^{n}\to \{0,1\}\\f(x)={\begin{cases}1&x\in B\\0&x\notin B\end{cases}}\end{cases}}}$

つまり、は の指示関数です。 ${\displaystyle f}$${\displaystyle B}$

解の数を計算します。^[1]${\displaystyle M=\left\vert f^{-1}(1)\right\vert =\vert B\vert }$

解の集合（または関数 の構造）に関する事前の知識がなければ、古典的な決定論的解は よりも優れたパフォーマンスを発揮することはできません。これは、のすべての要素を検査する必要があるためです（検査される最後の要素が解である場合を考えてみましょう）。 ${\displaystyle B}$${\displaystyle f}$${\displaystyle \オメガ (N)}$${\displaystyle N}$${\displaystyle \{0,1\}^{n}}$

入力は 2 つのレジスタ(つまり 2 つの部分) で構成されます。上位の量子ビットは最初のレジスタを構成し、下位の量子ビットは2 番目のレジスタを構成します。 ${\displaystyle p}$${\displaystyle n}$

システムの初期状態は です。各レジスタに複数ビットのアダマールゲート演算を個別に適用した後、最初のレジスタの状態は次のようになります。 ${\displaystyle |0\rangle ^{\otimes p}|0\rangle ^{\otimes n}}$

${\displaystyle {\frac {1}{2^{p/2}}}(|0\rangle +|1\rangle )^{\otimes p}}$

2番目のレジスタの状態は

${\displaystyle {\frac {1}{2^{n/2}}}(|0\rangle +|1\rangle )^{\otimes n}={\frac {1}{\sqrt {N}} }\sum _{x=0}^{N-1}|x\rangle }$

計算基底における 等しい重ね合わせ状態。

空間の大きさは であり、解の数は であるため、正規化された状態を次のように定義できる: ^{[2] : 252}${\displaystyle \left\vert \{0,1\}^{n}\right\vert =2^{n}=N}$${\displaystyle \left\vert B\right\vert =M}$

${\displaystyle |\alpha \rangle ={\frac {1}{\sqrt {N-M}}}\sum _{x\notin B}{|x\rangle },\qquad {\text{and}}\qquad |\beta \rangle ={\frac {1}{\sqrt {M}}}\sum _{x\in B}{|x\rangle }.}$

ご了承ください

${\displaystyle {\sqrt {\frac {N-M}{N}}}|\alpha \rangle +{\sqrt {\frac {M}{N}}}|\beta \rangle ={\frac {1}{\sqrt {N}}}\sum _{x=0}^{N-1}{|x\rangle },}$

これは、アダマール変換後の 2 番目のレジスタの状態です。

グローバーのアルゴリズムの幾何学的視覚化は、とによって張られる2次元空間において、グローバー演算子が反時計回りの回転であることを示す。したがって、次のように表すことができる。 ${\displaystyle |\alpha \rangle }$${\displaystyle |\beta \rangle }$

${\displaystyle G={\begin{bmatrix}\cos \theta &-\sin \theta \\\sin \theta &\cos \theta \end{bmatrix}}}$

正規直交基底 で。^{[2] ：252  [3] ：149}${\displaystyle \{|\alpha \rangle ,|\beta \rangle \}}$

回転行列の性質から、は2つの固有値を持つユニタリ行列であることがわかります。^{[2] ：253}${\displaystyle G}$ ${\displaystyle e^{\pm i\theta }}$

ここからは、量子位相推定アルゴリズムのスキームに従います。制御されたグローバー演算を適用し、続いて逆量子フーリエ変換を適用します。解析によれば、 （グローバー演算子の固有値に属する）実数への最良の ビット近似が より高い確率で見つかります。^{[4] : 348  [3] : 157}${\displaystyle p}$ ${\displaystyle \theta }$${\displaystyle e^{\pm i\theta }}$${\displaystyle {\frac {4}{\pi ^{2}}}}$

2番目のレジスタは実際にはグローバー演算子の固有ベクトルの重ね合わせになっていることに注意してください（元の量子位相推定アルゴリズムでは、2番目のレジスタは必要な固有ベクトルです）。これは、ある確率で を近似し、ある確率で を近似することを意味します。これら2つの近似は同等です。^{[2] : 224–225}${\displaystyle \theta }$${\displaystyle 2\pi -\theta }$

空間の大きさが解の数の少なくとも2倍であると仮定すると（すなわち、と仮定すると）、グローバーのアルゴリズムの解析結果は次のようになる：^{[2] : 254}${\displaystyle N}$${\displaystyle M\leq {\tfrac {N}{2}}}$

${\displaystyle \sin {\frac {\theta }{2}}={\sqrt {\frac {M}{N}}}.}$

したがって、 がわかれば、 の値もわかります(は既知であるため)。 ${\displaystyle \theta }$${\displaystyle M}$${\displaystyle N}$

エラー

${\displaystyle {\frac {\vert \Delta M\vert }{N}}=\left\vert \sin ^{2}\left({\frac {\theta +\Delta \theta }{2}}\right)-\sin ^{2}\left({\frac {\theta }{2}}\right)\right\vert }$

は、 の値の推定値内の誤差によって決まります。量子位相推定アルゴリズムは、の最良の ビット近似値を高い確率で見つけます。つまり、が十分に大きい場合、 が得られるということです。したがって となります。^{[2] : 263}${\displaystyle \theta }$${\displaystyle p}$${\displaystyle \theta }$${\displaystyle p}$${\displaystyle \Delta \theta \approx 0}$${\displaystyle \vert \Delta M\vert \approx 0}$

グローバーの探索アルゴリズムでは、実行すべき反復回数は^{[2] ：254  [3] ：150}である。${\displaystyle {\frac {\pi }{4}}{\sqrt {\frac {N}{M}}}}$

したがって、が既知であり、量子カウントアルゴリズムによって計算される場合、グローバーのアルゴリズムの反復回数は簡単に計算されます。 ${\displaystyle N}$${\displaystyle M}$

量子カウントアルゴリズムは、NP 完全な問題の解決を高速化するために使用できます。

NP完全問題の例としては、グラフにハミルトン閉路があるかどうかを判断する問題であるハミルトン閉路問題があります。 ${\displaystyle G=(V,E)}$

ハミルトン閉路問題の簡単な解決法は、 の頂点の各順序について、それがハミルトン閉路であるかどうかを調べることです。グラフの頂点のすべての可能な順序を検索するには、量子カウンティングの後にグローバーのアルゴリズムを適用し、グローバーのアルゴリズムと同様に平方根の高速化を実現できます。^{[2] : 264}このアプローチは、ハミルトン閉路（存在する場合）を見つけます。ハミルトン閉路が存在するかどうかを判断するには、量子カウンティングアルゴリズム自体で十分です（後述する量子存在アルゴリズムでも十分です）。 ${\displaystyle G}$

量子存在問題は量子計数の特殊なケースであり、の値を計算するのではなく、かどうかだけを知りたいというものである。^{[5] : 147}${\displaystyle M}$${\displaystyle M\neq 0}$

この問題の簡単な解決法は、量子計数アルゴリズムを直接使用することです。このアルゴリズムは を生成するので、 かどうかを確認することで存在問題の答えが得られます。このアプローチでは の値には興味がないため、オーバーヘッド情報が含まれます。量子位相推定を最適化することで、このオーバーヘッドを排除できます。^{[5] : 148}${\displaystyle M}$${\displaystyle M\neq 0}$${\displaystyle M}$

エラー確率の制御に興味がない場合は、上位レジスタの量子ビットの数が少ないセットアップを使用すると、の値の正確な推定は得られませんが、がゼロであるかどうかを判断するのに十分です。^{[2] ：263}${\displaystyle \theta }$${\displaystyle M}$

量子関係検定は量子存在検定の拡張であり、データベース内に特定の参照値との関係を満たすエントリが少なくとも1つ見つかるかどうかを判定します。^[6]たとえば、データベースに5より大きい値が含まれている場合はYESを返し、そうでない場合はNOを返します。量子関係検定と古典的な対数探索を組み合わせると、効率的な量子最小/最大探索アルゴリズムが形成されます。^{[5] : 152  [7]}${\displaystyle QRT(value,relation)}$${\displaystyle QRT(5,>)}$

• 量子位相推定アルゴリズム
• グローバーのアルゴリズム
• 数え上げ問題（複雑さ）