論文の概要: 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-10-01 06:54:23.971579
- 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:
- 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(参考訳): 量子コンピューティングと量子に触発されたアルゴリズムの最近の進歩は、バイナリ最適化に新たな関心を喚起している。
これらのハードウェアとソフトウェア革新は、複雑な問題に対するソリューションタイムに革命をもたらすことを約束する。
本研究では,線形システムの解法を提案する。
提案手法は二項最適化を利用しており,特に条件数の多い問題に適している。
線形系を二進最適化問題に変換し、元の問題の幾何学からインスピレーションを得て、共役勾配法に類似する。
このアプローチでは、アルゴリズムの収束率を著しく加速する共役方向を用いる。
さらに本研究では,問題の内在的幾何の部分的知識を活用することにより,元の問題をより小さく独立したサブプロブレムに分解できることを実証する。
これらのサブプロブレムは量子または古典的な解法を用いて効率的に取り組める。
問題の幾何を決定することは計算コストの増大をもたらすが、この投資は既存の手法に比べてかなりの性能向上に勝っている。
関連論文リスト
- A Catalyst Framework for the Quantum Linear System Problem via the Proximal Point Algorithm [9.804179673817574]
古典的近位点法(PPA)に着想を得た量子線形系問題(QLSP)に対する新しい量子アルゴリズムを提案する。
提案手法は,既存のtexttimattQLSP_solverを経由した修正行列の逆変換が可能なメタアルゴリズムとみなすことができる。
ステップサイズ$eta$を慎重に選択することにより、提案アルゴリズムは線形システムに対して、以前のアプローチの適用性を阻害する条件数への依存を軽減するために、効果的に事前条件を定めることができる。
論文 参考訳(メタデータ) (2024-06-19T23:15:35Z) - An Efficient Quantum Algorithm for Linear System Problem in Tensor Format [4.264200809234798]
本稿では,最近のアディバティック・インスパイアされたQLSAの進歩に基づく量子アルゴリズムを提案する。
実装の全体的な複雑さは、その次元において多対数的であることを厳密に示します。
論文 参考訳(メタデータ) (2024-03-28T20:37:32Z) - Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。
微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
論文 参考訳(メタデータ) (2023-02-24T18:41:48Z) - Quantum Algorithm for Solving a Quadratic Nonlinear System of Equations [0.22940141855172036]
アルゴリズムの複雑さは$O(rm polylog(n/epsilon))$であり、これは次元$n$の最適古典アルゴリズムよりも指数関数的に改善される。
我々のアルゴリズムは指数関数的にQNSEの解を加速し、あらゆる非線形問題に適用できる。
論文 参考訳(メタデータ) (2021-12-03T00:27:16Z) - 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) - Boosting Data Reduction for the Maximum Weight Independent Set Problem
Using Increasing Transformations [59.84561168501493]
最大重み独立集合問題に対する新しい一般化データ削減および変換規則を導入する。
驚くべきことに、これらのいわゆる増進変換は問題を単純化し、還元空間を開き、アルゴリズムの後にさらに小さな既約グラフが得られる。
提案アルゴリズムは, 1つのインスタンスを除くすべての既約グラフを計算し, 従来よりも多くのインスタンスを最適に解き, 最高の最先端解法よりも最大2桁高速に解き, 解法DynWVCやHILSよりも高品質な解を求める。
論文 参考訳(メタデータ) (2020-08-12T08:52:50Z) - Effective Dimension Adaptive Sketching Methods for Faster Regularized
Least-Squares Optimization [56.05635751529922]
スケッチに基づくL2正規化最小二乗問題の解法を提案する。
我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
論文 参考訳(メタデータ) (2020-06-10T15:00:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。