論文の概要: Explicit Solution Equation for Every Combinatorial Problem via Tensor Networks: MeLoCoToN

• arxiv url: http://arxiv.org/abs/2502.05981v1
• Date: Sun, 09 Feb 2025 18:16:53 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-11 14:29:53.925062
• Title: Explicit Solution Equation for Every Combinatorial Problem via Tensor Networks: MeLoCoToN
• Title（参考訳）: テンソルネットワークによるすべての組合せ問題の明示的解式:MeLoCoToN
• Authors: Alejandro Mata Ali,
• Abstract要約: 計算問題はすべて、解を返却する厳密な明示的な方程式を持つことを示す。 本稿では, インバージョン, 制約満足度, 最適化の両面から, 正確に任意の問題を解く方程式を得る方法を提案する。
• 参考スコア（独自算出の注目度）: 55.2480439325792
• License:
• Abstract: In this paper we show that every combinatorial problem has an exact explicit equation that returns its solution. We present a method to obtain an equation that solves exactly any combinatorial problem, both inversion, constraint satisfaction and optimization, by obtaining its equivalent tensor network. This formulation only requires a basic knowledge of classical logical operators, at a first year level of any computer science degree. These equations are not necessarily computable in a reasonable time, nor do they allow to surpass the state of the art in computational complexity, but they allow to have a new perspective for the mathematical analysis of these problems. These equations computation can be approximated by different methods such as Matrix Product State compression. We also present the equations for numerous combinatorial problems. This work proves that, if there is a physical system capable of contracting in polynomial time the tensor networks presented, every NP-Hard problem can be solved in polynomial time.
• Abstract（参考訳）: 本稿では,任意の組合せ問題に対して,解を返却する厳密な明示方程式が成立することを示す。 本稿では,その等価テンソルネットワークを得ることにより,インバージョン,制約満足度,最適化の両面において,任意の組合せ問題を正確に解く方法を提案する。 この定式化は、古典的論理演算子の基本的な知識を、コンピュータ科学の学位の初年度レベルでのみ必要とする。 これらの方程式は必ずしも合理的な時間で計算可能ではなく、計算複雑性の最先端を超越することも許していないが、これらの問題の数学的解析に新たな視点を持つことができる。 これらの方程式計算は、行列積状態圧縮のような異なる方法によって近似することができる。 また、多くの組合せ問題に対する方程式も提示する。 この研究は、テンソルネットワークが提示された多項式時間で収縮できる物理系が存在する場合、すべてのNP-ハード問題は多項式時間で解けることを証明している。

関連論文リスト

• 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)
• Towards Quantum Computational Mechanics [1.530480694206666]
  本稿では、量子コンピューティングを用いて、計算ホモジェナイゼーションにおける代表要素体積(RVE)問題を解く方法について述べる。 我々の量子RVE解法は古典解法に対して指数加速度を得る。
  論文  参考訳（メタデータ） (2023-12-06T12:53:02Z)
• Fast quantum algorithm for differential equations [0.5895819801677125]
  我々は、数値複雑性を持つ量子アルゴリズムを、$N$で多対数であるが、大規模なPDEに対して$kappa$とは独立に提示する。 提案アルゴリズムは,解の特徴を抽出する量子状態を生成する。
  論文  参考訳（メタデータ） (2023-06-20T18:01:07Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。 これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。 本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
  論文  参考訳（メタデータ） (2022-11-16T18:59:54Z)
• Tunable Complexity Benchmarks for Evaluating Physics-Informed Neural Networks on Coupled Ordinary Differential Equations [64.78260098263489]
  本研究では,より複雑に結合した常微分方程式(ODE)を解く物理インフォームドニューラルネットワーク(PINN)の能力を評価する。 PINNの複雑性が増大するにつれて,これらのベンチマークに対する正しい解が得られないことが示される。 PINN損失のラプラシアンは,ネットワーク容量の不足,ODEの条件の低下,局所曲率の高さなど,いくつかの理由を明らかにした。
  論文  参考訳（メタデータ） (2022-10-14T15:01:32Z)
• A quantum-inspired tensor network method for constrained combinatorial optimization problems [5.904219009974901]
  本稿では,一般に局所的に制約された最適化問題に対する量子インスパイアされたテンソルネットワークに基づくアルゴリズムを提案する。 我々のアルゴリズムは、興味のある問題に対してハミルトニアンを構築し、量子問題に効果的にマッピングする。 本研究は,本手法の有効性と応用の可能性を示すものである。
  論文  参考訳（メタデータ） (2022-03-29T05:44:07Z)
• The Separation Capacity of Random Neural Networks [78.25060223808936]
  標準ガウス重みと一様分布バイアスを持つ十分に大きな2層ReLUネットワークは、この問題を高い確率で解くことができることを示す。 我々は、相互複雑性という新しい概念の観点から、データの関連構造を定量化する。
  論文  参考訳（メタデータ） (2021-07-31T10:25:26Z)
• Power of human-algorithm collaboration in solving combinatorial optimization problems [0.0]
  最適化問題のクラスは、$epsilon$ が任意の定数であるような乗法係数 $epsilon$ を期待して、効率的に解けることを示す。 提案手法は単に理論的なものであるに過ぎないが、通常は難解であると考えられるこれらの問題を解決する方法に新たな光を当てた。
  論文  参考訳（メタデータ） (2021-07-25T11:21:59Z)
• Efficient Solution of Boolean Satisfiability Problems with Digital MemComputing [0.0]
  メモリアシスト物理系はSAT問題を連続的に効率的に解くことができることを示す。 シミュレーションの効率は、元の物理系の集合力学特性と関係している。 我々は、物理学に着想を得た計算パラダイムの研究の方向性を広げることを期待している。
  論文  参考訳（メタデータ） (2020-11-12T18:13:46Z)
• Multipole Graph Neural Operator for Parametric Partial Differential Equations [57.90284928158383]
  物理系をシミュレーションするためのディープラーニングベースの手法を使用する際の大きな課題の1つは、物理ベースのデータの定式化である。 線形複雑度のみを用いて、あらゆる範囲の相互作用をキャプチャする、新しいマルチレベルグラフニューラルネットワークフレームワークを提案する。 実験により, 離散化不変解演算子をPDEに学習し, 線形時間で評価できることを確認した。
  論文  参考訳（メタデータ） (2020-06-16T21:56:22Z)

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

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