量子計数アルゴリズム

Quantum algorithm for counting solutions to search problems

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

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

このアルゴリズムは、 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 \Omega (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 完全な問題の解決を高速化するために使用できます。

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,>)}$

参照

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

参考文献

1. ジル・ブラッサール;ホイヤー、ピーター。タップ、アラン (1998)、ラーセン、キム G.スカイム、スヴェン。 Winskel、Glynn (編)、「量子計数」、Automata、Languages and Programming、vol. 1443 年、ベルリン、ハイデルベルク: Springer Berlin Heidelberg、pp.  820–831、arXiv : quant-ph/9805082、doi :10.1007/bfb0055105、ISBN 978-3-540-64781-2、 2024年10月16日取得
2. Chuang, Michael A. Nielsen & Isaac L. (2001).量子計算と量子情報（復刻版）. Cambridge [ua]: Cambridge Univ. Press. ISBN 978-0521635035。
3. Benenti, Guiliano; Strini, Giulio Casati, Giuliano (2004).量子計算と情報の原理（再版）. ニュージャージー州 [ua]: World Scientific. ISBN 978-9812388582。{{cite book}}: CS1 maint: multiple names: authors list (link)
4. Cleve, R.; Ekert, A.; Macchiavello, C.; Mosca, M. (1998年1月8日). 「量子アルゴリズムの再考」. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences . 454 (1969): 339– 354. arXiv : quant-ph/9708016 . Bibcode :1998RSPSA.454..339C. doi :10.1098/rspa.1998.0164. S2CID  16128238.
5. イムレ, サンドル; バラズ, フェレンツ (2005年1月).量子コンピューティングと通信 - 工学的アプローチ. Wiley. ISBN 978-0470869024。
6. Elgaily, Sara; Imre, Sandor (2021). 「リソース配分管理のための制約付き量子最適化」. International Journal of Advanced Computer Science and Applications . 12 (8).
7. イムレ、サンドール (2007). 「量子存在テストと未ソートデータベースにおける極値発見への応用」. IEEE Transactions on Computers . 56 (5): 706– 710. doi :10.1109/TC.2007.1032. S2CID  29588344.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Quantum_counting_algorithm&oldid=1306893115"