論文の概要: Complexity continuum within Ising formulation of NP problems

• arxiv url: http://arxiv.org/abs/2008.00466v1
• Date: Sun, 2 Aug 2020 11:36:38 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-07 08:43:50.232625
• Title: Complexity continuum within Ising formulation of NP problems
• Title（参考訳）: NP問題のイジング定式化における複素性連続体
• Authors: Kirill P. Kalinin and Natalia G. Berloff
• Abstract要約: イジング・ハミルトニアンの最小化は、ある相互作用行列類に対するNPハード問題であることが知られている。 我々は、最適化単純度基準で計算学的に単純なインスタンスを特定することを提案する。 このような単純さはスピングラスからk規則の最大カット問題まで幅広いモデルで見られる。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A promising approach to achieve computational supremacy over the classical von Neumann architecture explores classical and quantum hardware as Ising machines. The minimisation of the Ising Hamiltonian is known to be NP-hard problem for certain interaction matrix classes, yet not all problem instances are equivalently hard to optimise. We propose to identify computationally simple instances with an `optimisation simplicity criterion'. Such optimisation simplicity can be found for a wide range of models from spin glasses to k-regular maximum cut problems. Many optical, photonic, and electronic systems are neuromorphic architectures that can naturally operate to optimise problems satisfying this criterion and, therefore, such problems are often chosen to illustrate the computational advantages of new Ising machines. We further probe an intermediate complexity for sparse and dense models by analysing circulant coupling matrices, that can be `rewired' to introduce greater complexity. A compelling approach for distinguishing easy and hard instances within the same NP-hard class of problems can be a starting point in developing a standardised procedure for the performance evaluation of emerging physical simulators and physics-inspired algorithms.
• Abstract（参考訳）: 古典的フォン・ノイマンアーキテクチャに対する計算上優位性を達成するための有望なアプローチは、古典的および量子ハードウェアをイジングマシンとして探索する。 イジングハミルトニアンの最小化は、ある相互作用行列類に対するnp-ハード問題として知られているが、すべての問題インスタンスが同値に最適化しにくいわけではない。 本稿では,計算的にシンプルなインスタンスを'最適化簡易基準'で識別する。 このような最適化の単純さは、スピングラスからk-正則最大カット問題まで幅広いモデルで見られる。 多くの光学系、フォトニック系、電子系は、この基準を満たす問題を最適化するために自然に操作できるニューロモルフィックアーキテクチャであるため、このような問題は、新しいイジングマシンの計算上の利点を説明するためにしばしば選択される。 さらに、より複雑な「再配線」可能な循環結合行列を解析することにより、スパースモデルと密度モデルの中間複雑性を探索する。 同じNP-hardクラス内の簡単で難しいインスタンスを区別するための魅力的なアプローチは、新しい物理シミュレータと物理に着想を得たアルゴリズムの性能評価のための標準化された手順を開発するための出発点となる。

関連論文リスト

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation [3.9857517408503567]
  量子近似最適化アルゴリズム (quantum Approximate optimization algorithm, Qaoa) は、最適化のための量子古典的反復法として広く研究されている。 インスタンスに依存しないが問題固有の非定型計算に基づく新しいアルゴリズム変種を導入する。 我々のアプローチは、カオの量子非依存構造に関する長年の予想を証明することに基づいている。
  論文  参考訳（メタデータ） (2024-08-12T21:02:58Z)
• Moderate Exponential-time Quantum Dynamic Programming Across the Subsets for Scheduling Problems [0.20971479389679337]
  量子最小探索と動的プログラミングの組み合わせは、NPハード問題の複雑さを改善するのに特に効果的であることが証明されている。 本稿では,NP-ハード単一マシンスケジューリング問題に対して,そのような改善を実現する境界付きエラーハイブリッドアルゴリズムを提案する。 我々のアルゴリズムは、よく知られた古典的アルゴリズムと比較して指数関数的な部分の複雑さを減らし、時には擬似多項式因子のコストがかかる。
  論文  参考訳（メタデータ） (2024-08-11T10:28:49Z)
• Quantum Vision Clustering [10.360126989185261]
  本稿では,Adiabatic quantum computing を用いた解法に適した最初のクラスタリング定式化を提案する。 提案手法は,最先端の最適化手法と比較して高い競合性を示す。 この研究は、現在世代の実量子コンピュータにおけるクラスタリング問題の解決可能性を示す。
  論文  参考訳（メタデータ） (2023-09-18T16:15:16Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。 これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。 本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
  論文  参考訳（メタデータ） (2022-11-16T18:59:54Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。 予測と高い確率で、新しい過剰なリスク境界を提供する。 我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
  論文  参考訳（メタデータ） (2022-11-03T12:40:24Z)
• Sparse Polynomial Optimization: Theory and Practice [5.27013884159732]
  本書は、この課題に重要な科学的意味を持って取り組むためのいくつかの取り組みを提示している。 これは計算複雑性の観点からうまくスケールする代替の最適化スキームを提供する。 制約のない問題や制約のない問題に対して、緩和の疎開的階層を提示する。
  論文  参考訳（メタデータ） (2022-08-23T18:56:05Z)
• A quantum-inspired tensor network method for constrained combinatorial optimization problems [5.904219009974901]
  本稿では,一般に局所的に制約された最適化問題に対する量子インスパイアされたテンソルネットワークに基づくアルゴリズムを提案する。 我々のアルゴリズムは、興味のある問題に対してハミルトニアンを構築し、量子問題に効果的にマッピングする。 本研究は,本手法の有効性と応用の可能性を示すものである。
  論文  参考訳（メタデータ） (2022-03-29T05:44:07Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。 これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。 本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
  論文  参考訳（メタデータ） (2022-02-17T18:59:20Z)
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
  定常点に収束する一般化外空間を提案する。 このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
  論文  参考訳（メタデータ） (2020-10-31T21:35:42Z)
• The limits of min-max optimization algorithms: convergence to spurious non-critical sets [82.74514886461257]
  min-max最適化アルゴリズムは周期サイクルや同様の現象が存在するため、はるかに大きな問題に遭遇する。 問題のどの点も引き付けないアルゴリズムが存在することを示す。 ほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほとんどである。
  論文  参考訳（メタデータ） (2020-06-16T10:49:27Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。