論文の概要: A near-term quantum algorithm for solving linear systems of equations
based on the Woodbury identity
- arxiv url: http://arxiv.org/abs/2205.00645v1
- Date: Mon, 2 May 2022 04:32:01 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-14 20:50:40.504596
- Title: A near-term quantum algorithm for solving linear systems of equations
based on the Woodbury identity
- Title（参考訳）: ウッドベリー恒等式に基づく方程式の線形系解のための短期量子アルゴリズム
- Authors: Daniel O'Malley and Yigit Subasi and John Golden and Robert Lowrie and
Stephan Eidenbenz
- Abstract要約: 本稿では,不規則高原や局所最適解などの問題を回避し,方程式の線形系を解くための量子アルゴリズムについて述べる。
このアルゴリズムは、他の(容易に可逆な)行列の低ランクな修正である行列の逆を解析的に記述するウッドベリー恒等式に基づいている。
我々は、IBMのオークランド量子コンピュータを用いて、2%の誤差で1600万以上の方程式を解いたシステムの内部積を推定する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quantum algorithms for solving linear systems of equations have generated
excitement because of the potential speed-ups involved and the importance of
solving linear equations in many applications. However, applying these
algorithms can be challenging. The Harrow-Hassidim-Lloyd algorithm and
improvements thereof require complex subroutines suitable for fault-tolerant
hardware such as Hamiltonian simulation, making it ill-suited to current
hardware. Variational algorithms, on the other hand, involve expensive
optimization loops, which can be prone to barren plateaus and local optima. We
describe a quantum algorithm for solving linear systems of equations that
avoids these problems. Our algorithm is based on the Woodbury identity, which
analytically describes the inverse of a matrix that is a low-rank modification
of another (easily-invertible) matrix. This approach only utilizes basic
quantum subroutines like the Hadamard test or the swap test, so it is
well-suited to current hardware. There is no optimization loop, so barren
plateaus and local optima do not present a problem. The low-rank aspect of the
identity enables us to efficiently transfer information to and from the quantum
computer. This approach can produce accurate results on current hardware. As
evidence of this, we estimate an inner product involving the solution of a
system of more than 16 million equations with 2% error using IBM's Auckland
quantum computer. To our knowledge, no system of equations this large has
previously been solved to this level of accuracy on a quantum computer.
- Abstract（参考訳）: 方程式の線形系を解くための量子アルゴリズムは、潜在的なスピードアップと多くの応用において線形方程式を解くことの重要性から興奮を引き起こしている。
しかし、これらのアルゴリズムを適用することは難しい。
harrow-hassidim-lloydアルゴリズムとその改善には、ハミルトンシミュレーションのようなフォールトトレラントなハードウェアに適した複雑なサブルーチンが必要である。
一方、変分アルゴリズムは高価な最適化ループを伴い、不毛の台地や局所的なオプティマが引き起こされる可能性がある。
これらの問題を回避する線形方程式系を解くための量子アルゴリズムについて述べる。
このアルゴリズムは、他の(容易に可逆な)行列の低ランクな修正である行列の逆を解析的に記述するウッドベリー恒等式に基づいている。
このアプローチは、Hadamardテストやスワップテストのような基本的な量子サブルーチンのみを使用するため、現在のハードウェアに適している。
最適化ループがないため、不毛の台地や局所的なオプティマは問題を示しない。
アイデンティティの低ランクな側面により、量子コンピュータへの情報転送を効率的に行うことができる。
このアプローチは、現在のハードウェアで正確な結果を生み出すことができる。
これの証拠として、IBMのオークランド量子コンピュータを用いて、2%の誤差で1600万以上の方程式からなるシステムの解を含む内部積を推定する。
我々の知る限り、この大きな方程式系は量子コンピュータ上のこのレベルの精度で以前に解かれていない。
関連論文リスト
- Shadow Quantum Linear Solver: A Resource Efficient Quantum Algorithm for Linear Systems of Equations [0.8437187555622164]
本稿では,デジタル量子デバイス上での量子線形システム問題(QLSP)の解法を提案する。
その結果、大きな制御されたユニタリの必要性を回避し、システムサイズで対数的な多くの量子ビットを必要とする量子アルゴリズムが実現した。
これを、線形代数の分解定理を利用して、2次元格子における離散化されたラプラス方程式を解くことで、実用的妥当性の物理問題に適用する。
論文 参考訳（メタデータ） (2024-09-13T15:46:32Z) - Hybrid quantum-classical and quantum-inspired classical algorithms for
solving banded circulant linear systems [0.8192907805418583]
帯状循環系に対する量子状態の組み合わせの凸最適化に基づく効率的なアルゴリズムを提案する。
帯状循環行列を巡回置換に分解することにより, 量子状態の組み合わせによる近似解を$K$とする。
我々は,従来のシミュレーションと実際のIBM量子コンピュータ実装を用いて本手法を検証し,熱伝達などの物理問題への適用性を示した。
論文 参考訳（メタデータ） (2023-09-20T16:27:16Z) - An Inexact Feasible Quantum Interior Point Method for Linearly
Constrained Quadratic Optimization [0.0]
量子線形システムアルゴリズム(QLSA)は、線形システムの解法に依存するアルゴリズムを高速化する可能性がある。
本研究では, 線形制約付き2次最適化問題の解法において, 実効性のないQIPM(Inexact-Feasible QIPM)を提案する。
論文 参考訳（メタデータ） (2023-01-13T01:36:13Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Accelerating the training of single-layer binary neural networks using
the HHL quantum algorithm [58.720142291102135]
Harrow-Hassidim-Lloyd (HHL) の量子力学的実装から有用な情報が抽出可能であることを示す。
しかし,本論文では,HHLの量子力学的実装から有用な情報を抽出し,古典的側面における解を見つける際の複雑性を低減することを目的としている。
論文 参考訳（メタデータ） (2022-10-23T11:58:05Z) - Quantum algorithms for matrix operations and linear systems of equations [65.62256987706128]
本稿では,「Sender-Receiver」モデルを用いた行列演算のための量子アルゴリズムを提案する。
これらの量子プロトコルは、他の量子スキームのサブルーチンとして使用できる。
論文 参考訳（メタデータ） (2022-02-10T08:12:20Z) - A Hybrid Quantum-Classical Algorithm for Robust Fitting [47.42391857319388]
本稿では,ロバストフィッティングのためのハイブリッド量子古典アルゴリズムを提案する。
私たちのコアコントリビューションは、整数プログラムの列を解く、新しい堅牢な適合式である。
実際の量子コンピュータを用いて得られた結果について述べる。
論文 参考訳（メタデータ） (2022-01-25T05:59:24Z) - Quantum Algorithm for Solving a Quadratic Nonlinear System of Equations [0.22940141855172036]
アルゴリズムの複雑さは$O(rm polylog(n/epsilon))$であり、これは次元$n$の最適古典アルゴリズムよりも指数関数的に改善される。
我々のアルゴリズムは指数関数的にQNSEの解を加速し、あらゆる非線形問題に適用できる。
論文 参考訳（メタデータ） (2021-12-03T00:27:16Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳（メタデータ） (2021-07-08T17:59:55Z) - QUBO formulations for numerical quantum computing [0.0]
Harrow-Hassidim-Lloydアルゴリズムは、ゲートモデル量子コンピュータ上の線形システムを解くための重要な量子アルゴリズムである。
Ax=b を満たすベクトル x に対する非制約バイナリ最適化 (QUBO) モデルを見つける。
我々は,これらのQUBOモデルをD-Waveシステム上で検証し,その結果について考察する。
論文 参考訳（メタデータ） (2021-06-21T02:49:59Z) - Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
我々は、リコメンダシステムと最小二乗回帰のためのクエリをサポートする古典的な(量子でない)動的データ構造を作成する。
これらの問題に対する以前の量子インスパイアされたアルゴリズムは、レバレッジやリッジレベレッジスコアを偽装してサンプリングしていると我々は主張する。
論文 参考訳（メタデータ） (2020-11-09T01:13:07Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。