0

チェスのゲーム ツリーの複雑さが少なくとも 10 123であり、量子コンピューターは最終的に従来のコンピューターよりも数百万倍高速になる可能性があることを考えると、量子アルゴリズムは、一生のうちに可能な動きの組み合わせをすべて処理することができるでしょうか?

4

2 に答える 2

2

たぶん、しかしポイントは何ですか - すでに調査された移動パスを何らかの方法で保存する必要があり、可能なパスが膨大な量であることを考えると、それは不可能です (既知の宇宙に存在するアトムよりもはるかに多くのパスがあることを思い出してください)

于 2011-10-06T21:19:47.303 に答える
1

これは、量子マシンを使用して NP 問題を解決することについての私の理解です。

cost function量子マシンを使用する効率は、問題のモデリングの実装に依存します。

コスト関数を定義したいと思います-多項式には、動きの可能なすべての組み合わせが含まれます-そして量子マシンに渡します。そして、各動きはブール変数です。

量子マシンを使用して NP 完全問題または NP 困難問題を解くには、いくつかの要件 (制約) があります。

  1. 問題の変数の数が、量子マシン チップの量子ビット (量子ビット) の数以下です
  2. 多項式はQUBO問題 (2 次の制約のないバイナリ最適化) である必要があります - 2 つの量子ビットに力を適用することによって (現在の量子マシン技術に基づいて、できれば HOBO (高次バイナリ最適化 - この論文) 多項式が将来的に量子チップで受け入れられるようになります)

これらの制約が満たされている場合、NP 問題の複雑さをより低い程度に変換できます。(例: O(N^3) から O(N^2))

現在の量子マシンは最大 512 量子ビット ( D-Wave Two System ) を持ち、最大 2^512 の複雑さの問題を解決できます。

于 2014-08-27T17:39:46.950 に答える