論文の概要: Increasing the dimension of linear systems solved by classical or quantum binary optimization: A new method to solve large linear equation systems

• arxiv url: http://arxiv.org/abs/2309.09933v1
• Date: Mon, 18 Sep 2023 16:51:03 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-19 12:08:14.717229
• Title: Increasing the dimension of linear systems solved by classical or quantum binary optimization: A new method to solve large linear equation systems
• Title（参考訳）: 古典的あるいは量子的二進最適化による線形系の次元の増大:大規模線形方程式系を解く新しい方法
• Authors: Erick R. Castro, Eldues O. Martins, Roberto S. Sarthour, Alexandre M. Souza, Ivan S. Oliveira
• Abstract要約: 本稿では,二進最適化問題として記述された線形システムの解法を提案する。 この手順は問題を効率的に解決し、大きな線形系を扱えるようにする。
• 参考スコア（独自算出の注目度）: 41.94295877935867
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recently, binary optimization has become an attractive research topic due to the development of quantum computing and specialized classical systems inspired by quantum computing. These hardware systems promise to speed up the computation significantly. In this work, we propose a new method to solve linear systems written as a binary optimization problem. The procedure solves the problem efficiently and allows it to handle large linear systems. Our approach is founded on the geometry of the original linear problem and resembles the gradient conjugate method. The conjugated directions used can significantly improve the algorithm's convergence rate. We also show that a partial knowledge of the intrinsic geometry of the problem can divide the original problem into independent sub-problems of smaller dimensions. These sub-problems can then be solved using quantum or classical solvers. Although determining the geometry of the problem has an additional computational cost, it can substantially improve the performance of our method compared to previous implementations.
• Abstract（参考訳）: 近年、量子コンピューティングと量子コンピューティングにインスパイアされた古典システムの開発により、バイナリ最適化は魅力的な研究トピックとなっている。 これらのハードウェアシステムは計算の高速化を約束している。 本研究では,バイナリ最適化問題として記述された線形系の解法を提案する。 この手順は問題を効率的に解き、大きな線形システムを扱うことができる。 本手法は元の線形問題の幾何学に基づいており,勾配共役法に類似している。 共役方向はアルゴリズムの収束率を大幅に向上させることができる。 また、問題の内在幾何学の部分的知識は、元の問題をより小さな次元の独立した部分確率に分割できることを示す。 これらの部分問題は、量子解または古典解法を用いて解くことができる。 問題の幾何を決定するには計算コストがかかるが,従来の実装と比較して,本手法の性能は大幅に向上する。

関連論文リスト

• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。 微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
  論文  参考訳（メタデータ） (2023-02-24T18:41:48Z)
• Efficient Use of Quantum Linear System Algorithms in Interior Point Methods for Linear Optimization [0.0]
  線形最適化問題を解くために、非現実的な量子内点法を開発した。 また、量子ソルバの過度な時間なしで、反復リファインメントによって正確な解を得る方法についても論じる。
  論文  参考訳（メタデータ） (2022-05-02T21:30:56Z)
• A near-term quantum algorithm for solving linear systems of equations based on the Woodbury identity [0.0]
  本稿では,不規則高原や局所最適解などの問題を回避し,方程式の線形系を解くための量子アルゴリズムについて述べる。 このアルゴリズムは、他の(容易に可逆な)行列の低ランクな修正である行列の逆を解析的に記述するウッドベリー恒等式に基づいている。 我々は、IBMのオークランド量子コンピュータを用いて、2%の誤差で1600万以上の方程式を解いたシステムの内部積を推定する。
  論文  参考訳（メタデータ） (2022-05-02T04:32:01Z)
• 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)

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

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