論文の概要: Knapsack and Shortest Path Problems Generalizations From A Quantum-Inspired Tensor Network Perspective
- arxiv url: http://arxiv.org/abs/2506.11711v1
- Date: Fri, 13 Jun 2025 12:27:34 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-16 17:50:49.778601
- Title: Knapsack and Shortest Path Problems Generalizations From A Quantum-Inspired Tensor Network Perspective
- Title（参考訳）: 量子インスパイアされたテンソルネットワークから見たKnapsackと最短経路問題の一般化
- Authors: Sergio Muñiz Subiñas, Jorge Martínez Martín, Alejandro Mata Ali, Javier Sedano, Ángel Miguel García-Vico,
- Abstract要約: 我々は、knapsackと最短経路問題を解くために、2つの量子インスピレーション付きアルゴリズムを提案する。
この方法は問題の最適解を返す正確な方程式を与える。
- 参考スコア（独自算出の注目度）: 40.5694560588179
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we present two tensor network quantum-inspired algorithms to solve the knapsack and the shortest path problems, and enables to solve some of its variations. These methods provide an exact equation which returns the optimal solution of the problems. As in other tensor network algorithms for combinatorial optimization problems, the method is based on imaginary time evolution and the implementation of restrictions in the tensor network. In addition, we introduce the use of symmetries and the reutilization of intermediate calculations, reducing the computational complexity for both problems. To show the efficiency of our implementations, we carry out some performance experiments and compare the results with those obtained by other classical algorithms.
- Abstract（参考訳）: 本稿では,knapsackと最短経路問題を解くために,2つのテンソルネットワーク量子インスピレーション付きアルゴリズムを提案する。
これらの方法は問題の最適解を返す正確な方程式を与える。
組合せ最適化問題に対する他のテンソルネットワークアルゴリズムと同様に、この手法は想像上の時間進化とテンソルネットワークにおける制限の実装に基づいている。
さらに,対称性と中間計算の再利用を導入し,両問題の計算複雑性を低減した。
実装の効率性を示すため、いくつかの性能実験を行い、その結果を他の古典的アルゴリズムと比較する。
関連論文リスト
- Multi-level Neural Networks for high-dimensional parametric obstacle problems [0.0]
挑戦的(ランダムな)パラメトリック障害物問題の解法を開発し,解析した。
障害物問題の高次元解は、特別に構築された畳み込みニューラルネットワーク(CNN)によって近似される
数値実験は、この挑戦的な問題に対する最先端のパフォーマンスを示している。
論文 参考訳（メタデータ） (2025-04-07T12:50:56Z) - Explicit Solution Equation for Every Combinatorial Problem via Tensor Networks: MeLoCoToN [55.2480439325792]
計算問題はすべて、解を返却する厳密な明示的な方程式を持つことを示す。
本稿では, インバージョン, 制約満足度, 最適化の両面から, 正確に任意の問題を解く方程式を得る方法を提案する。
論文 参考訳（メタデータ） (2025-02-09T18:16:53Z) - A Primal-dual algorithm for image reconstruction with ICNNs [3.4797100095791706]
我々は、正規化器が入力ニューラルネットワーク(ICNN)によってパラメータ化されるデータ駆動変分フレームワークにおける最適化問題に対処する。
勾配に基づく手法はそのような問題を解決するのに一般的に用いられるが、非滑らかさを効果的に扱うのに苦労する。
提案手法は, 速度と安定性の両方の観点から, 下位段階の手法よりも優れていることを示す。
論文 参考訳（メタデータ） (2024-10-16T10:36:29Z) - Quick design of feasible tensor networks for constrained combinatorial optimization [1.8775413720750924]
近年,実用化のための制約付き最適化問題に対して,テンソルネットワークが適用されている。
1つのアプローチは、nilpotent-matrix操作でテンソルネットワークを構築することである。
提案手法は,制約付き最適化問題に対する実現可能なテンソルネットワークの発見を容易にすることが期待されている。
論文 参考訳（メタデータ） (2024-09-03T08:36:23Z) - Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。
微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
論文 参考訳（メタデータ） (2023-02-24T18:41:48Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳（メタデータ） (2023-01-30T15:46:39Z) - A quantum-inspired tensor network method for constrained combinatorial
optimization problems [5.904219009974901]
本稿では,一般に局所的に制約された最適化問題に対する量子インスパイアされたテンソルネットワークに基づくアルゴリズムを提案する。
我々のアルゴリズムは、興味のある問題に対してハミルトニアンを構築し、量子問題に効果的にマッピングする。
本研究は,本手法の有効性と応用の可能性を示すものである。
論文 参考訳（メタデータ） (2022-03-29T05:44:07Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳（メタデータ） (2021-06-08T15:54:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。