論文の概要: Enhancing the Quantum Linear Systems Algorithm using Richardson
Extrapolation
- arxiv url: http://arxiv.org/abs/2009.04484v4
- Date: Mon, 5 Jul 2021 08:57:23 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-03 02:55:21.861429
- Title: Enhancing the Quantum Linear Systems Algorithm using Richardson
Extrapolation
- Title（参考訳）: Richardson外挿を用いた量子線形システムアルゴリズムの高速化
- Authors: Almudena Carrera Vazquez, Ralf Hiptmair, Stefan Woerner
- Abstract要約: Amathbfx=mathbfb$という形の線形方程式の系を解く量子アルゴリズムを提案する。
このアルゴリズムは古典的手法に対して$N$に対して指数関数的に改善する。
- 参考スコア（独自算出の注目度）: 0.8057006406834467
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present a quantum algorithm to solve systems of linear equations of the
form $A\mathbf{x}=\mathbf{b}$, where $A$ is a tridiagonal Toeplitz matrix and
$\mathbf{b}$ results from discretizing an analytic function, with a circuit
complexity of $poly(\log(\kappa), 1/\sqrt{\epsilon}, \log(N))$, where $N$
denotes the number of equations, $\epsilon$ is the accuracy, and $\kappa$ the
condition number. The \emph{repeat-until-success} algorithm has to be run
$\mathcal{O}\left(\kappa/(1-\epsilon)\right)$ times to succeed, leveraging
amplitude amplification, and sampled $\mathcal{O}(1/\epsilon^2)$ times. Thus,
the algorithm achieves an exponential improvement with respect to $N$ over
classical methods. In particular, we present efficient oracles for state
preparation, Hamiltonian simulation and a set of observables together with the
corresponding error and complexity analyses. As the main result of this work,
we show how to use Richardson extrapolation to enhance Hamiltonian simulation,
resulting in an implementation of Quantum Phase Estimation (QPE) within the
algorithm with $1/\sqrt{\epsilon}$ circuit complexity instead of $1/\epsilon$
and which can be parallelized. Furthermore, we analyze necessary conditions for
the overall algorithm to achieve an exponential speedup compared to classical
methods. Our approach is not limited to the considered setting and can be
applied to more general problems where Hamiltonian simulation is approximated
via product formulae, although, our theoretical results would need to be
extended accordingly. All the procedures presented are implemented with Qiskit
and tested for small systems using classical simulation as well as using real
quantum devices available through the IBM Quantum Experience.
- Abstract（参考訳）: 解析関数の離散化の結果、$A\mathbf{x}=\mathbf{b}$、$A$は三対角トエプリッツ行列で$\mathbf{b}$、回路複雑性は$poly(\log(\kappa), 1/\sqrt{\epsilon}, \log(N)$、$N$は方程式の数を表し、$\epsilon$は精度、$\kappa$は条件数である。
emph{repeat-until-success} アルゴリズムは$\mathcal{o}\left(\kappa/(1-\epsilon)\right)$ times で成功し、振幅増幅を利用して $\mathcal{o}(1/\epsilon^2)$ をサンプリングする必要がある。
したがって、このアルゴリズムは古典的手法よりも$N$に対して指数関数的に改善する。
特に,状態生成,ハミルトニアンシミュレーション,観測可能な集合に対する効率的なオラクルと,対応する誤差解析と複雑性解析について述べる。
この研究の主な結果として、リチャードソン外挿法を用いてハミルトニアンシミュレーションを強化し、1/\sqrt{\epsilon}$回路複雑性を1/\epsilon$ではなく1/\sqrt{\epsilon}$回路複雑性でアルゴリズム内の量子位相推定(qpe)を実装する方法を示す。
さらに,従来の手法と比較して指数的高速化を実現するために,アルゴリズム全体に必要な条件を解析する。
我々のアプローチは検討された設定に限らず、ハミルトンシミュレーションが積公式によって近似されるようなより一般的な問題にも適用できるが、理論的な結果はそれに従って拡張する必要がある。
提示されたすべての手順はqiskitで実装され、古典的なシミュレーションとibm quantum experienceで利用可能な実際の量子デバイスを使用して、小さなシステムでテストされる。
関連論文リスト
- Quantum spectral method for gradient and Hessian estimation [4.193480001271463]
勾配降下は連続最適化問題を解くための最も基本的なアルゴリズムの1つである。
本稿では、クエリの複雑さを$widetildeO (1/varepsilon)$とすることで、その勾配の$varepsilon$-approximationを返す量子アルゴリズムを提案する。
また、ニュートン法の量子アナログを改善することを目的としたヘッセン推定のための2つの量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-07-04T11:03:48Z) - A shortcut to an optimal quantum linear system solver [55.2480439325792]
複雑で解析困難な手法を用いない、概念的にシンプルな量子線形システム解法(QLSS)を提案する。
ソリューションノルム$lVertboldsymbolxrVert$が正確に知られているなら、私たちのQLSSはカーネルの1つのアプリケーションだけを必要とします。
あるいは、断熱経路追従法から概念を再導入することにより、標準推定に$O(kappa)$複雑さを実現できることを示す。
論文 参考訳（メタデータ） (2024-06-17T20:54:11Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - Fast and Practical Quantum-Inspired Classical Algorithms for Solving
Linear Systems [11.929584800629673]
線形系を解くための高速で実用的な量子インスパイアされた古典的アルゴリズムを提案する。
我々の主な貢献は、線形系を解くために量子に着想を得た古典的アルゴリズムへの重球運動量法の適用である。
論文 参考訳（メタデータ） (2023-07-13T08:46:19Z) - Quantum Simulation of the First-Quantized Pauli-Fierz Hamiltonian [0.5097809301149342]
我々は、我々の分割と形式主義の征服を通じて、大きな$Lambda$の量子化よりも優れたスケーリングと量子化を得られることを示す。
また,マルチコントロールされたXゲート群を実装する新しい方法を含む,ゲート最適化のための新しいアルゴリズムおよび回路レベル技術も提供する。
論文 参考訳（メタデータ） (2023-06-19T23:20:30Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - Learning many-body Hamiltonians with Heisenberg-limited scaling [3.460138063155115]
N$-qubit 局所ハミルトニアンの相互作用を学習するためのハイゼンベルク限界を達成するアルゴリズムを提案する。
総進化時間$mathcalO(epsilon-1)$の後に、提案アルゴリズムは高い確率で$N$-qubit Hamiltonianのパラメータを$epsilon$-errorに効率的に推定することができる。
論文 参考訳（メタデータ） (2022-10-06T16:30:51Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - How to simulate quantum measurement without computing marginals [3.222802562733787]
量子状態$psi$を標準で計算するためのアルゴリズムを,古典的に記述し,解析する。
我々のアルゴリズムはサンプリングタスクを$n$-qubit状態のポリ(n)$振幅の計算に還元する。
論文 参考訳（メタデータ） (2021-12-15T21:44:05Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-12T16:29:45Z) - Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
NISQとフォールトトレラントの両方の設定で格子シュウィンガーモデルをシミュレートするために、スケーラブルで明示的なデジタル量子アルゴリズムを提供する。
格子単位において、結合定数$x-1/2$と電場カットオフ$x-1/2Lambda$を持つ$N/2$物理サイト上のシュウィンガーモデルを求める。
NISQと耐故障性の両方でコストがかかるオブザーバブルを、単純なオブザーバブルとして推定し、平均ペア密度を推定する。
論文 参考訳（メタデータ） (2020-02-25T19:18:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。