論文の概要: On solving classes of positive-definite quantum linear systems with
quadratically improved runtime in the condition number
- arxiv url: http://arxiv.org/abs/2101.11868v3
- Date: Mon, 1 Nov 2021 21:35:36 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-13 11:58:17.404417
- Title: On solving classes of positive-definite quantum linear systems with
quadratically improved runtime in the condition number
- Title（参考訳）: 条件数を2次的に改善した正定値量子線形系の解法について
- Authors: Davide Orsucci, Vedran Dunjko
- Abstract要約: 量子線形系を解くことは、$A$が正定値であるとき、$kappa$のランタイム線形を必要とすることを示す。
2つの新しい量子アルゴリズムで、$kappa$の2次スピードアップを特徴とする。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Quantum algorithms for solving the Quantum Linear System (QLS) problem are
among the most investigated quantum algorithms of recent times, with potential
applications including the solution of computationally intractable differential
equations and speed-ups in machine learning. A fundamental parameter governing
the efficiency of QLS solvers is $\kappa$, the condition number of the
coefficient matrix $A$, as it has been known since the inception of the QLS
problem that for worst-case instances the runtime scales at least linearly in
$\kappa$ [Harrow, Hassidim and Lloyd, PRL 103, 150502 (2009)]. However, for the
case of positive-definite matrices classical algorithms can solve linear
systems with a runtime scaling as $\sqrt{\kappa}$, a quadratic improvement
compared to the the indefinite case. It is then natural to ask whether QLS
solvers may hold an analogous improvement. In this work we answer the question
in the negative, showing that solving a QLS entails a runtime linear in
$\kappa$ also when $A$ is positive definite. We then identify broad classes of
positive-definite QLS where this lower bound can be circumvented and present
two new quantum algorithms featuring a quadratic speed-up in $\kappa$: the
first is based on efficiently implementing a matrix-block-encoding of $A^{-1}$,
the second constructs a decomposition of the form $A = L L^\dagger$ to
precondition the system. These methods are widely applicable and both allow to
efficiently solve BQP-complete problems.
- Abstract（参考訳）: 量子線形システム(QLS)問題を解く量子アルゴリズムは、計算に難解な微分方程式の解や機械学習の高速化など、近年最も研究されている量子アルゴリズムの一つである。
QLSソルバの効率を管理する基本的なパラメータは$\kappa$であり、QLS問題の発端から知られているように、ランタイムスケールは$\kappa$[Harrow, Hassidim and Lloyd, PRL 103, 150502 (2009)]で少なくとも線形である。
しかし、正定値行列の場合、古典的なアルゴリズムは$\sqrt{\kappa}$で実行時にスケーリングすることで線形システムを解くことができる。
したがって、QLSソルバが類似した改善を達成できるかどうかを問うことは自然である。
この研究では、QLSを解くことは、$A$が正定値であるときにも、$\kappa$のランタイム線型を伴っていることを示す。
次に、この下界を回避できる正定値QLSの広いクラスを特定し、$\kappa$の二次的スピードアップを特徴とする2つの新しい量子アルゴリズムを提示する: 1つは、A^{-1}$の行列ブロック符号化を効率的に実装することに基づいており、もう1つは、システムの事前条件を満たすために$A = L L^\dagger$という形式の分解を構成する。
これらの方法は広く適用でき、どちらもBQP完全問題を効率的に解くことができる。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Tight Quantum Depth Lower Bound for Solving Systems of Linear Equations [7.319050391449301]
時間複雑性を持つ線形方程式系を解くための量子アルゴリズムは、クエリの深さで$Omega(kappa)$が低いことを示す。
この問題の最先端の量子アルゴリズムは、Costa, An, Sanders, Su, Babbush, and Berry (2022) によるものであり、最適なクエリ複雑性は $Theta(kappa)$である。
論文 参考訳（メタデータ） (2024-07-08T15:05:46Z) - A shortcut to an optimal quantum linear system solver [55.2480439325792]
複雑で解析困難な手法を用いない、概念的にシンプルな量子線形システム解法(QLSS)を提案する。
ソリューションノルム$lVertboldsymbolxrVert$が正確に知られているなら、私たちのQLSSはカーネルの1つのアプリケーションだけを必要とします。
あるいは、断熱経路追従法から概念を再導入することにより、標準推定に$O(kappa)$複雑さを実現できることを示す。
論文 参考訳（メタデータ） (2024-06-17T20:54:11Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Efficient quantum linear solver algorithm with detailed running costs [0.0]
量子信号処理に基づくフィルタリング手法を用いて,アイデアダイアバティックな量子コンピューティングを組み合わせた量子線形解法アルゴリズムを提案する。
我々のプロトコルは、初期実装において、最先端技術に対する量子線形解決器のコストを桁違いに削減する。
論文 参考訳（メタデータ） (2023-05-19T00:07:32Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00: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) - Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。
本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。
Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
論文 参考訳（メタデータ） (2021-05-06T17:59:38Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-12T16:29:45Z) - Quantum-classical algorithms for skewed linear systems with optimized
Hadamard test [10.386115383285288]
我々は、過度に決定された場合と過度に決定された場合のスキュード線形系に対するハイブリッド量子古典アルゴリズムについて論じる。
我々の入力モデルは、線形系を定義する行列の列または行が多対数深さの量子回路によって与えられるようなものである。
本稿では,各次元における実時間多対数性を持つ分解線形系の特殊ケースに対するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-09-28T12:59:27Z) - Variational Quantum Linear Solver [0.3774866290142281]
本稿では,線形系を線形に解くための量子古典的ハイブリッドアルゴリズムを提案する。
リゲッティの量子コンピュータを用いて,250Times250$までの大きさの非自明な問題を数値的に解く。
論文 参考訳（メタデータ） (2019-09-12T17:28:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。