論文の概要: A shortcut to an optimal quantum linear system solver

• arxiv url: http://arxiv.org/abs/2406.12086v1
• Date: Mon, 17 Jun 2024 20:54:11 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-19 23:47:35.833887
• Title: A shortcut to an optimal quantum linear system solver
• Title（参考訳）: 最適量子線形系解法への近道
• Authors: Alexander M. Dalzell,
• Abstract要約: 複雑で解析困難な手法を用いない、概念的にシンプルな量子線形システム解法(QLSS)を提案する。 ソリューションノルム$lVertboldsymbolxrVert$が正確に知られているなら、私たちのQLSSはカーネルの1つのアプリケーションだけを必要とします。 あるいは、断熱経路追従法から概念を再導入することにより、標準推定に$O(kappa)$複雑さを実現できることを示す。
• 参考スコア（独自算出の注目度）: 55.2480439325792
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Given a linear system of equations $A\boldsymbol{x}=\boldsymbol{b}$, quantum linear system solvers (QLSSs) approximately prepare a quantum state $|\boldsymbol{x}\rangle$ for which the amplitudes are proportional to the solution vector $\boldsymbol{x}$. Asymptotically optimal QLSSs have query complexity $O(\kappa \log(1/\varepsilon))$, where $\kappa$ is the condition number of $A$, and $\varepsilon$ is the approximation error. However, runtime guarantees for existing optimal and near-optimal QLSSs do not have favorable constant prefactors, in part because they rely on complex or difficult-to-analyze techniques like variable-time amplitude amplification and adiabatic path-following. Here, we give a conceptually simple QLSS that does not use these techniques. If the solution norm $\lVert\boldsymbol{x}\rVert$ is known exactly, our QLSS requires only a single application of kernel reflection (a straightforward extension of the eigenstate filtering (EF) technique of previous work) and the query complexity of the QLSS is $(1+O(\varepsilon))\kappa \ln(2\sqrt{2}/\varepsilon)$. If the norm is unknown, our method allows it to be estimated up to a constant factor using $O(\log\log(\kappa))$ applications of kernel projection (a direct generalization of EF) yielding a straightforward QLSS with near-optimal $O(\kappa \log\log(\kappa)\log\log\log(\kappa)+\kappa\log(1/\varepsilon))$ total complexity. Alternatively, by reintroducing a concept from the adiabatic path-following technique, we show that $O(\kappa)$ complexity can be achieved for norm estimation, yielding an optimal QLSS with $O(\kappa\log(1/\varepsilon))$ complexity while still avoiding the need to invoke the adiabatic theorem. Finally, we compute an explicit upper bound of $56\kappa+1.05\kappa \ln(1/\varepsilon)+o(\kappa)$ for the complexity of our optimal QLSS.
• Abstract（参考訳）: A\boldsymbol{x}=\boldsymbol{b}$ 方程式の線形系が与えられたとき、量子線型系ソルバ (QLSSs) は量子状態 $|\boldsymbol{x}\rangle$ をおよそ準備し、振幅は解ベクトル $\boldsymbol{x}$ に比例する。 漸近的に最適なQLSSはクエリ複雑性が$O(\kappa \log(1/\varepsilon))$で、$\kappa$は$A$の条件番号、$\varepsilon$は近似エラーである。 しかしながら、既存の最適かつほぼ最適なQLSSのランタイム保証には、一定の事前ファクタが適していない。 ここでは、これらのテクニックを使用しない概念的にシンプルなQLSSを提供します。 ソリューションノルム $\lVert\boldsymbol{x}\rVert$ が正確に知られている場合、我々の QLSS はカーネルリフレクションの1つのアプリケーションしか必要とせず、QLSS のクエリ複雑性は $(1+O(\varepsilon))\kappa \ln(2\sqrt{2}/\varepsilon)$ である。 ノルムが不明な場合、我々の手法は、$O(\log\log(\kappa))$カーネルプロジェクションの応用(EFの直接一般化)を用いて定数係数まで推定することができ、ほぼ最適の$O(\kappa \log(\kappa)\log\log(\kappa)+\kappa\log(1/\varepsilon))$トータル複雑性を持つ単純なQLSSが得られる。 あるいは、adiabatic path-following 法から概念を再導入することにより、$O(\kappa)$ complexity がノルム推定のために達成され、$O(\kappa\log(1/\varepsilon))$ complexity で最適な QLSS が得られるが、それでもadiabatic theorem を呼び出す必要はない。 最後に、最適QLSSの複雑さに対して、56\kappa+1.05\kappa \ln(1/\varepsilon)+o(\kappa)$の明示的な上限を計算する。

関連論文リスト

• Quantum linear system algorithm with optimal queries to initial state preparation [0.0]
  線形システムの量子アルゴリズムは、2つのオラクルを問合せして解状態$A-1|brangle$を生成する。 本稿では,$mathbfThetaleft (1/sqrtpright)$クエリを$O_b$に変換する量子線形系アルゴリズムを提案する。 微分方程式の解法のような様々な応用において、ブロックプレコンディショニングスキームを用いて$p$への依存をさらに改善することができる。
  論文  参考訳（メタデータ） (2024-10-23T18:00:01Z)
• Fast and Practical Quantum-Inspired Classical Algorithms for Solving Linear Systems [11.929584800629673]
  線形系を解くための高速で実用的な量子インスパイアされた古典的アルゴリズムを提案する。 我々の主な貢献は、線形系を解くために量子に着想を得た古典的アルゴリズムへの重球運動量法の適用である。
  論文  参考訳（メタデータ） (2023-07-13T08:46:19Z)
• The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimization [88.91190483500932]
  本稿では,スムーズで強靭なミニマックス最適化問題を再考する。 既存の最先端メソッドは、下限の$Omegaleft(sqrtkappa_xkappa_ylog3 (kappa_xkappa_y)logfrac1epsilonright)$にマッチしない。 我々は、$mathcalOleft( sqrtkappa_xkappa_ylog)で最初のアルゴリズムを提供することで、この根本的な問題を解決する。
  論文  参考訳（メタデータ） (2022-05-11T17:33:07Z)
• Faster quantum-inspired algorithms for solving linear systems [0.05076419064097732]
  そこで本研究では,データ構造を$x$で出力する古典的アルゴリズムにより,エントリへのサンプリングとクエリが可能であることを示す。 この出力は、量子線型解法の出力の古典的なアナログと見なすことができる。
  論文  参考訳（メタデータ） (2021-03-18T15:12:44Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications [28.54236118020831]
  本稿では,最適な$O(n log (kappa))$オアラーク評価を用いた新しい切削平面アルゴリズムを提案する。 また、評価毎に$n2$の時間を改善できないため、実行時間が最適であることを示す。
  論文  参考訳（メタデータ） (2020-04-08T20:56:40Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
  論文  参考訳（メタデータ） (2020-02-17T18:41:49Z)
• Variational Quantum Linear Solver [0.3774866290142281]
  本稿では,線形系を線形に解くための量子古典的ハイブリッドアルゴリズムを提案する。 リゲッティの量子コンピュータを用いて,250Times250$までの大きさの非自明な問題を数値的に解く。
  論文  参考訳（メタデータ） (2019-09-12T17:28:09Z)

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

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