論文の概要: Enhancing the Harrow-Hassidim-Lloyd (HHL) algorithm in systems with large condition numbers
- arxiv url: http://arxiv.org/abs/2407.21641v4
- Date: Sun, 25 May 2025 15:27:56 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-27 16:58:41.821579
- 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要約: HHL(Harrow-Hassidim-Lloyd)アルゴリズムは、量子コンピュータ上の$Avecx=vecb$という形の線形方程式を扱うために、システムサイズを指数関数的に高速化する。
本稿では,選択後改善HHL(Psi-HHL)フレームワークについて紹介する。
- 参考スコア（独自算出の注目度）: 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) framework that operates on a simple yet effective premise: subtracting mixed and wrong signals to extract correct signals while providing the benefit of optimal scaling in the condition number of $A$ (denoted as $\mathcal{\kappa}$) for large $\mathcal{\kappa}$ scenarios. This approach, which leads to minimal increase in circuit depth, has the important practical implication of having to use substantially fewer shots relative to the traditional HHL algorithm. The term `signal' refers to a feature of $|x\rangle$. We design circuits for overlap and expectation value estimation in the Psi-HHL framework. We demonstrate performance of Psi-HHL via numerical simulations. We carry out two sets of computations, 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) application to quantum chemistry, where we consider matrices up to size $256 \times 256$ that reach $\mathcal{\kappa}$ of about 393. The molecular systems that we consider are Li$_{\mathrm{2}}$, KH, RbH, and CsH.
- Abstract（参考訳）: HHL (Harrow-Hassidim-Lloyd) アルゴリズムは、A$行列の条件数 (\mathcal{\kappa}$) のスケーリングに関連する問題に直面している。
本稿では,提案手法を応用したHHL (Psi-HHL) フレームワークを導入することでこの問題に対処する。大規模な$\mathcal{\kappa}$シナリオに対して,条件数$A$ ($\mathcal{\kappa}$と表記される) の最適スケーリングの利点を提供しながら,混合信号と誤信号の抽出を行う。
このアプローチは、回路深さの最小化につながるが、従来のHHLアルゴリズムと比較してかなり少ないショットを使用する必要があるという重要な実践的意味を持つ。
signal" は $|x\rangle$ の特徴を指す。
Psi-HHLフレームワークにおける重なりと期待値推定のための回路を設計する。
数値シミュレーションによりPsi-HHLの性能を示す。
2組の計算を行い、26量子ビットの計算を行い、Psi-HHLが大容量$\mathcal{\kappa}$行列を扱えることを示す。
(a)おもちゃの行列のセットで、64ドルと$\mathcal{\kappaの64ドルと$\mathcal{\kappaの値が最大$\approx$100M(100万ドル)になる。
b) 量子化学への応用では、行列が最大で256 \times 256$で、$\mathcal{\kappa} は約393である。
私たちが考える分子系は、Li$_{\mathrm{2}}$、KH、RbH、CsHである。
関連論文リスト
- Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability [85.07238533644636]
$Phi$-equilibriaは、オンライン学習とゲーム理論の中心にある、強力で柔軟なフレームワークだ。
効率的なオンラインアルゴリズムは、$textpoly(d, k)/epsilon2$ラウンドを使用して、平均$Phi$-regretを最大$epsilon$で生成することを示す。
また、オンライン設定において、ほぼ一致した下限を示し、その結果、$Phi$-regretの学習可能性を取得する偏差の族が初めて得られる。
論文 参考訳（メタデータ） (2025-02-25T19:08:26Z) - 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) - Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning [10.690769339903941]
我々は、$Ax = b$という形式の線形系を解くための、新しい条件付き反復法のクラスを示す。
提案手法は,低ランクなNystr"om近似をスパースランダムスケッチ行列を用いて$A$に構築することに基づいている。
我々は、我々の手法の収束が自然平均条件数$A$に依存することを証明し、Nystr"om近似のランクが増加するにつれて改善する。
論文 参考訳（メタデータ） (2024-05-09T15:53:43Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。