論文の概要: Improving the convergence of an iterative algorithm for solving arbitrary linear equation systems using classical or quantum binary optimization

• arxiv url: http://arxiv.org/abs/2309.09933v3
• Date: Fri, 27 Sep 2024 15:32:28 GMT
• ステータス: 処理完了
• システム内更新日: 2024-11-09 14:28:50.433134
• Title: Improving the convergence of an iterative algorithm for solving arbitrary linear equation systems using classical or quantum binary optimization
• Title（参考訳）: 古典的あるいは量子二項最適化を用いた任意の線形方程式系を解く反復アルゴリズムの収束性の改善
• Authors: Erick R. Castro, Eldues O. Martins, Roberto S. Sarthour, Alexandre M. Souza, Ivan S. Oliveira,
• Abstract要約: 本稿では,線形システムの解法を提案する。 線形系を二進最適化問題に変換し、元の問題の幾何学からインスピレーションを得る。 問題固有の幾何学の部分的知識を活用することで、元の問題をより小さく独立したサブプロブレムに分解できることを実証する。
• 参考スコア（独自算出の注目度）: 39.58317527488534
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recent advancements in quantum computing and quantum-inspired algorithms have sparked renewed interest in binary optimization. These hardware and software innovations promise to revolutionize solution times for complex problems. In this work, we propose a novel method for solving linear systems. Our approach leverages binary optimization, making it particularly well-suited for problems with large condition numbers. We transform the linear system into a binary optimization problem, drawing inspiration from the geometry of the original problem and resembling the conjugate gradient method. This approach employs conjugate directions that significantly accelerate the algorithm's convergence rate. Furthermore, we demonstrate that by leveraging partial knowledge of the problem's intrinsic geometry, we can decompose the original problem into smaller, independent sub-problems. These sub-problems can be efficiently tackled using either quantum or classical solvers. While determining the problem's geometry introduces some additional computational cost, this investment is outweighed by the substantial performance gains compared to existing methods.
• Abstract（参考訳）: 量子コンピューティングと量子に触発されたアルゴリズムの最近の進歩は、バイナリ最適化に新たな関心を喚起している。 これらのハードウェアとソフトウェア革新は、複雑な問題に対するソリューションタイムに革命をもたらすことを約束する。 本研究では,線形システムの解法を提案する。 提案手法は二項最適化を利用しており,特に条件数の多い問題に適している。 線形系を二進最適化問題に変換し、元の問題の幾何学からインスピレーションを得て、共役勾配法に類似する。 このアプローチでは、アルゴリズムの収束率を著しく加速する共役方向を用いる。 さらに本研究では,問題の内在的幾何の部分的知識を活用することにより,元の問題をより小さく独立したサブプロブレムに分解できることを実証する。 これらのサブプロブレムは量子または古典的な解法を用いて効率的に取り組める。 問題の幾何を決定することは計算コストの増大をもたらすが、この投資は既存の手法に比べてかなりの性能向上に勝っている。

関連論文リスト

• Analyzing and Enhancing the Backward-Pass Convergence of Unrolled Optimization [50.38518771642365]
  ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。 この設定における中心的な課題は最適化問題の解によるバックプロパゲーションであり、しばしば閉形式を欠いている。 本稿では, 非線形最適化の後方通過に関する理論的知見を提供し, 特定の反復法による線形システムの解と等価であることを示す。 Folded Optimizationと呼ばれるシステムが提案され、非ローリングなソルバ実装からより効率的なバックプロパゲーションルールを構築する。
  論文  参考訳（メタデータ） (2023-12-28T23:15:18Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。 微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
  論文  参考訳（メタデータ） (2023-02-24T18:41:48Z)
• A Copositive Framework for Analysis of Hybrid Ising-Classical Algorithms [18.075115172621096]
  本稿では,Isingソルバを用いた混合二項二次プログラムの解法におけるハイブリッドアルゴリズムの形式解析について述べる。 本稿では,ハイブリッド量子古典的切削平面アルゴリズムを用いてこの問題を解決することを提案する。
  論文  参考訳（メタデータ） (2022-07-27T16:47:32Z)
• A quantum-inspired tensor network method for constrained combinatorial optimization problems [5.904219009974901]
  本稿では,一般に局所的に制約された最適化問題に対する量子インスパイアされたテンソルネットワークに基づくアルゴリズムを提案する。 我々のアルゴリズムは、興味のある問題に対してハミルトニアンを構築し、量子問題に効果的にマッピングする。 本研究は,本手法の有効性と応用の可能性を示すものである。
  論文  参考訳（メタデータ） (2022-03-29T05:44:07Z)
• Improving quantum linear system solvers via a gradient descent perspective [3.0969191504482247]
  我々は凸最適化の観点から量子線形系解法を再考する。 これにより、実行時にかなりの定数のイテレーションが発生します。 本研究では,子・子・子・ソマの最適量子線形系解法が勾配降下アルゴリズムとどのように関係しているかを示す。
  論文  参考訳（メタデータ） (2021-09-09T13:16:28Z)
• Quadratic Unconstrained Binary Optimisation via Quantum-Inspired Annealing [58.720142291102135]
  本稿では,2次非制約二項最適化の事例に対する近似解を求める古典的アルゴリズムを提案する。 我々は、チューニング可能な硬さと植え付けソリューションを備えた大規模問題インスタンスに対して、我々のアプローチをベンチマークする。
  論文  参考訳（メタデータ） (2021-08-18T09:26:17Z)
• Quantum variational optimization: The role of entanglement and problem hardness [0.0]
  本稿では, 絡み合いの役割, 変動量子回路の構造, 最適化問題の構造について検討する。 数値計算の結果,絡み合うゲートの分布を問題のトポロジに適応させる利点が示唆された。 リスク型コスト関数に条件値を適用することで最適化が向上し、最適解と重複する確率が増大することを示す。
  論文  参考訳（メタデータ） (2021-03-26T14:06:54Z)
• Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
  我々は、リコメンダシステムと最小二乗回帰のためのクエリをサポートする古典的な(量子でない)動的データ構造を作成する。 これらの問題に対する以前の量子インスパイアされたアルゴリズムは、レバレッジやリッジレベレッジスコアを偽装してサンプリングしていると我々は主張する。
  論文  参考訳（メタデータ） (2020-11-09T01:13:07Z)

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

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