論文の概要: Enhancing the Harrow-Hassidim-Lloyd (HHL) algorithm in systems with large condition numbers
- arxiv url: http://arxiv.org/abs/2407.21641v3
- Date: Wed, 9 Oct 2024 04:46:09 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-08 13:40:32.871155
- Title: Enhancing the Harrow-Hassidim-Lloyd (HHL) algorithm in systems with large condition numbers
- Title（参考訳）: 大きな条件数を持つシステムにおけるHHLアルゴリズムの強化
- Authors: Peniel Bertrand Tsemo, Akshaya Jayashankar, K. Sugisaki, Nishanth Baskaran, Sayan Chakraborty, V. S. Prasannaa,
- Abstract要約: 我々はPsi-HHLが$mathcalkappa$行列を含む状況に対処できることを実証する。
行列は最大で256倍256$で、mathcalkappa$は約466である。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Although the Harrow-Hassidim-Lloyd (HHL) algorithm offers an exponential speedup in system size for treating linear equations of the form $A\vec{x}=\vec{b}$ on quantum computers when compared to their traditional counterparts, it faces a challenge related to the condition number ($\mathcal{\kappa}$) scaling of the $A$ matrix. In this work, we address the issue by introducing the post-selection-improved HHL (Psi-HHL) approach that involves a simple yet effective modification of the HHL algorithm to extract a feature of $|x\rangle$, and which leads to achieving optimal behaviour in $\mathcal{\kappa}$ (linear scaling) for large condition number situations. This has the important practical implication of having to use substantially fewer shots relative to the traditional HHL algorithm. We carry out two sets of simulations, where we go up to 26-qubit calculations, to demonstrate the ability of Psi-HHL to handle situations involving large $\mathcal{\kappa}$ matrices via: (a) a set of toy matrices, for which we go up to size $64 \times 64$ and $\mathcal{\kappa}$ values of up to $\approx$ 1 million, and (b) a deep-dive into quantum chemistry, where we consider matrices up to size $256 \times 256$ that reach $\mathcal{\kappa}$ of about 466. The molecular systems that we consider are Li$_{\mathrm{2}}$, RbH, and CsH. Although the feature of $|x\rangle$ considered in our examples is an overlap between the input and output states of the HHL algorithm, our approach is general and can be applied in principle to any transition matrix element involving $|x\rangle$.
- Abstract（参考訳）: HHL (Harrow-Hassidim-Lloyd) アルゴリズムは、A$行列の条件数 (\mathcal{\kappa}$) のスケーリングに関連する問題に直面している。
本研究では,HHLアルゴリズムの単純かつ効果的な修正を伴い,|x\rangle$という特徴を抽出し,大条件条件条件に対して$\mathcal{\kappa$(線形スケーリング)の最適動作を実現する,ポストセレクション改良HHL(Psi-HHL)アプローチを導入することでこの問題に対処する。
これは、従来のHHLアルゴリズムと比較してかなり少ないショットを使用する必要があるという重要な実践的意味を持っている。
2組のシミュレーションを行い、26量子ビットの計算を行い、Psi-HHLが大きな$\mathcal{\kappa}$行列を扱えることを示す。
(a)おもちゃの行列のセットで、64ドルと$\mathcal{\kappaの64ドルと$\mathcal{\kappaの値が最大$\approx$100M(100万ドル)になる。
b) 量子化学の深い研究で、行列は最大で256 \times 256$で、$\mathcal{\kappa} は約466である。
私たちが考える分子系は、Li$_{\mathrm{2}}$, RbH, CsHである。
私たちの例では、|x\rangle$ の特徴は HHL アルゴリズムの入力状態と出力状態の重複であるが、我々のアプローチは一般的であり、|x\rangle$ を含む任意の遷移行列要素に原理的に適用することができる。
関連論文リスト
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Fast and Practical Quantum-Inspired Classical Algorithms for Solving
Linear Systems [11.929584800629673]
線形系を解くための高速で実用的な量子インスパイアされた古典的アルゴリズムを提案する。
我々の主な貢献は、線形系を解くために量子に着想を得た古典的アルゴリズムへの重球運動量法の適用である。
論文 参考訳（メタデータ） (2023-07-13T08:46:19Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。
この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。
本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文 参考訳（メタデータ） (2022-02-23T02:39:04Z) - Sublinear classical and quantum algorithms for general matrix games [11.339580074756189]
行列ゲームに対する線形古典的および量子的アルゴリズムについて検討する。
任意の固定 $qin (1,2) に対して、$mathcalX$ が$ell_q$-norm 単位球である行列ゲームが加法誤差内で解決される。
同じタスクを時間内に解く、対応する部分線形量子アルゴリズムも提供する。
論文 参考訳（メタデータ） (2020-12-11T17:36:33Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-12T16:29:45Z) - Hutch++: Optimal Stochastic Trace Estimation [75.45968495410048]
我々は、任意の正半定値(PSD)$A$に対して、$(1 pm epsilon)$を$tr(A)$に近似する新しいランダム化アルゴリズムであるHutch++を導入する。
実験ではハッチンソン法を著しく上回る結果を得た。
論文 参考訳（メタデータ） (2020-10-19T16:45:37Z) - Quantum-classical algorithms for skewed linear systems with optimized
Hadamard test [10.386115383285288]
我々は、過度に決定された場合と過度に決定された場合のスキュード線形系に対するハイブリッド量子古典アルゴリズムについて論じる。
我々の入力モデルは、線形系を定義する行列の列または行が多対数深さの量子回路によって与えられるようなものである。
本稿では,各次元における実時間多対数性を持つ分解線形系の特殊ケースに対するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-09-28T12:59:27Z) - An improved quantum-inspired algorithm for linear regression [15.090593955414137]
量子行列反転アルゴリズムに類似した線形回帰の古典的アルゴリズムを提案する。
量子コンピュータは、このQRAMデータ構造設定において、線形回帰の最大12倍の高速化を達成できることを示す。
論文 参考訳（メタデータ） (2020-09-15T17:58:25Z) - Enhancing the Quantum Linear Systems Algorithm using Richardson
Extrapolation [0.8057006406834467]
Amathbfx=mathbfb$という形の線形方程式の系を解く量子アルゴリズムを提案する。
このアルゴリズムは古典的手法に対して$N$に対して指数関数的に改善する。
論文 参考訳（メタデータ） (2020-09-09T18:00:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。