論文の概要: Optimal scaling quantum linear systems solver via discrete adiabatic
theorem
- arxiv url: http://arxiv.org/abs/2111.08152v1
- Date: Tue, 16 Nov 2021 00:21:37 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-08 00:16:35.530330
- Title: Optimal scaling quantum linear systems solver via discrete adiabatic
theorem
- Title（参考訳）: 離散断熱定理による最適スケーリング量子線形系解法
- Authors: Pedro C. S. Costa, Dong An, Yuval R. Sanders, Yuan Su, Ryan Babbush,
and Dominic W. Berry
- Abstract要約: 離散的に最適となる線形系を解くための量子アルゴリズムを開発した。
既存の最適化手法と比較して,本アルゴリズムはよりシンプルで実装が容易である。
- 参考スコア（独自算出の注目度）: 0.9846257338039974
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recently, several approaches to solving linear systems on a quantum computer
have been formulated in terms of the quantum adiabatic theorem for a
continuously varying Hamiltonian. Such approaches enabled near-linear scaling
in the condition number $\kappa$ of the linear system, without requiring a
complicated variable-time amplitude amplification procedure. However, the most
efficient of those procedures is still asymptotically sub-optimal by a factor
of $\log(\kappa)$. Here, we prove a rigorous form of the adiabatic theorem that
bounds the error in terms of the spectral gap for intrinsically discrete time
evolutions. We use this discrete adiabatic theorem to develop a quantum
algorithm for solving linear systems that is asymptotically optimal, in the
sense that the complexity is strictly linear in $\kappa$, matching a known
lower bound on the complexity. Our $\mathcal{O}(\kappa\log(1/\epsilon))$
complexity is also optimal in terms of the combined scaling in $\kappa$ and the
precision $\epsilon$. Compared to existing suboptimal methods, our algorithm is
simpler and easier to implement. Moreover, we determine the constant factors in
the algorithm, which would be suitable for determining the complexity in terms
of gate counts for specific applications.
- Abstract（参考訳）: 近年、量子コンピュータ上の線形系を解くためのいくつかのアプローチが、連続的に変化するハミルトニアンに対する量子断熱定理の観点で定式化されている。
このようなアプローチは、複雑な可変時間振幅増幅手順を必要とせず、線形システムの条件番号$\kappa$でニア線形スケーリングを可能にした。
しかし、これらの手順の最も効率的な部分は、いまだ漸近的に$\log(\kappa)$である。
ここでは、本質的な離散時間発展のスペクトルギャップの観点から誤差を限定する断熱定理の厳密な形式を証明する。
この離散断熱定理を用いて漸近的に最適である線形系を解くための量子アルゴリズムを開発し、複雑性は$\kappa$ で厳密に線形であり、複雑性の既知の下界に一致する。
我々の$\mathcal{o}(\kappa\log(1/\epsilon))$複雑性もまた、$\kappa$のスケーリングと精度の$\epsilon$という点で最適である。
既存の最適化手法と比較して,我々のアルゴリズムはシンプルで実装が容易である。
さらに, 特定のアプリケーションに対するゲート数の観点から, 複雑度を決定するのに適した定数因子をアルゴリズムで決定する。
関連論文リスト
- A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Halving the Cost of Quantum Algorithms with Randomization [0.138120109831448]
量子信号処理(QSP)は、線形演算子の変換を実装するための体系的なフレームワークを提供する。
近年の研究では、量子チャネルへのユニタリゲートを促進する技術であるランダム化コンパイルが開発されている。
提案アルゴリズムは, 平均進化が対象関数に収束するように戦略的に選択されたランダム化の確率的混合を実装し, 誤差は等価個体よりも2次的に小さい。
論文 参考訳（メタデータ） (2024-09-05T17:56:51Z) - Eigenpath traversal by Poisson-distributed phase randomisation [0.08192907805418585]
本稿では,AQC(Adiabatic Quantum Computation)と同様,量子計算のためのフレームワークを提案する。
ポアソン過程によって決定された間隔でランダムデファーズ演算を行うことにより、特定の固有値に関連する固有空間を追跡することができる。
有限性に対する単純な微分方程式を導出し、アルゴリズムのクラスの時間複雑性を境界とする一般定理を導出する。
論文 参考訳（メタデータ） (2024-06-06T11:33:29Z) - The discrete adiabatic quantum linear system solver has lower constant factors than the randomized adiabatic solver [2.350508194508073]
複雑性上の上界に対する明示的な定数係数は、上界から直観的に予想されるよりもはるかに効率的であることを示す。
特に、より効率的であると主張する[arXiv:2305.11352]からのランダム化アプローチよりも、桁違いに効率的である。
論文 参考訳（メタデータ） (2023-12-12T19:36:41Z) - GRAPE optimization for open quantum systems with time-dependent
decoherence rates driven by coherent and incoherent controls [77.34726150561087]
グラディエントアセンセントパルス工学(GRAPE)法は量子制御の最適化に広く用いられている。
我々は、コヒーレント制御と非コヒーレント制御の両方によって駆動されるオープン量子系の目的関数を最適化するために、GRAPE法を採用する。
状態-状態遷移問題に対する数値シミュレーションによりアルゴリズムの効率を実証する。
論文 参考訳（メタデータ） (2023-07-17T13:37:18Z) - Fast quantum algorithm for differential equations [0.5895819801677125]
我々は、数値複雑性を持つ量子アルゴリズムを、$N$で多対数であるが、大規模なPDEに対して$kappa$とは独立に提示する。
提案アルゴリズムは,解の特徴を抽出する量子状態を生成する。
論文 参考訳（メタデータ） (2023-06-20T18:01:07Z) - Efficient quantum linear solver algorithm with detailed running costs [0.0]
量子信号処理に基づくフィルタリング手法を用いて,アイデアダイアバティックな量子コンピューティングを組み合わせた量子線形解法アルゴリズムを提案する。
我々のプロトコルは、初期実装において、最先端技術に対する量子線形解決器のコストを桁違いに削減する。
論文 参考訳（メタデータ） (2023-05-19T00:07:32Z) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-16T13:57:19Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳（メタデータ） (2023-01-10T20:43:29Z) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。
また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
論文 参考訳（メタデータ） (2020-11-19T10:00:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。