論文の概要: Low depth algorithms for quantum amplitude estimation
- arxiv url: http://arxiv.org/abs/2012.03348v2
- Date: Wed, 22 Jun 2022 05:59:27 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-21 22:58:59.841847
- Title: Low depth algorithms for quantum amplitude estimation
- Title（参考訳）: 量子振幅推定のための低深さアルゴリズム
- Authors: Tudor Giurgica-Tiron, Iordanis Kerenidis, Farrokh Labib, Anupam
Prakash and William Zeng
- Abstract要約: 振幅推定のための2つの新しい低深さアルゴリズムの設計と解析
これらのアルゴリズムはモンテカルロ法の量子スピードアップを実現に近づける。
- 参考スコア（独自算出の注目度）: 6.148105657815341
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We design and analyze two new low depth algorithms for amplitude estimation
(AE) achieving an optimal tradeoff between the quantum speedup and circuit
depth. For $\beta \in (0,1]$, our algorithms require $N= \tilde{O}( \frac{1}{
\epsilon^{1+\beta}})$ oracle calls and require the oracle to be called
sequentially $D= O( \frac{1}{ \epsilon^{1-\beta}})$ times to perform amplitude
estimation within additive error $\epsilon$. These algorithms interpolate
between the classical algorithm $(\beta=1)$ and the standard quantum algorithm
($\beta=0$) and achieve a tradeoff $ND= O(1/\epsilon^{2})$. These algorithms
bring quantum speedups for Monte Carlo methods closer to realization, as they
can provide speedups with shallower circuits.
The first algorithm (Power law AE) uses power law schedules in the framework
introduced by Suzuki et al \cite{S20}. The algorithm works for $\beta \in
(0,1]$ and has provable correctness guarantees when the log-likelihood function
satisfies regularity conditions required for the Bernstein Von-Mises theorem.
The second algorithm (QoPrime AE) uses the Chinese remainder theorem for
combining lower depth estimates to achieve higher accuracy. The algorithm works
for discrete $\beta =q/k$ where $k \geq 2$ is the number of distinct coprime
moduli used by the algorithm and $1 \leq q \leq k-1$, and has a fully rigorous
correctness proof. We analyze both algorithms in the presence of depolarizing
noise and provide numerical comparisons with the state of the art amplitude
estimation algorithms.
- Abstract（参考訳）: 量子速度アップと回路深度の最適トレードオフを実現する2つの新しい振幅推定アルゴリズム(ae)の設計と解析を行った。
n= \tilde{o}( \frac{1}{ \epsilon^{1+\beta}})$ oracle の呼び出しとoracle のシーケンシャルな $d= o( \frac{1}{ \epsilon^{1-\beta}})$ による加算誤差 $\epsilon$ での振幅推定。
これらのアルゴリズムは、古典的アルゴリズム$(\beta=1)$と標準量子アルゴリズム$(\beta=0$)の間を補間し、$nd= o(1/\epsilon^{2})$を得る。
これらのアルゴリズムは、より浅い回路でスピードアップを提供できるため、モンテカルロ法の量子スピードアップを実現に近づける。
最初のアルゴリズム(Power Law AE)は、Suzuki et al \cite{S20} によって導入されたフレームワークで電力法スケジュールを使用する。
このアルゴリズムは$\beta \in (0,1]$で動作し、ベルンシュタイン・フォン・ミセスの定理に必要な正規性条件を満たすと証明可能な正確性を保証する。
第2のアルゴリズム(QoPrime AE)は、中国の剰余定理を用いて、より高精度な深度推定を行う。
このアルゴリズムは離散$\beta =q/k$に対して作用し、$k \geq 2$はアルゴリズムが使用する異なるコリメモジュラーの数であり、$1 \leq q \leq k-1$であり、完全に厳密な正当性証明を持つ。
両アルゴリズムを非偏極雑音の存在下で解析し,アート振幅推定アルゴリズムの状態との比較を行った。
関連論文リスト
- Quantum spectral method for gradient and Hessian estimation [4.193480001271463]
勾配降下は連続最適化問題を解くための最も基本的なアルゴリズムの1つである。
本稿では、クエリの複雑さを$widetildeO (1/varepsilon)$とすることで、その勾配の$varepsilon$-approximationを返す量子アルゴリズムを提案する。
また、ニュートン法の量子アナログを改善することを目的としたヘッセン推定のための2つの量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-07-04T11:03:48Z) - Towards Optimal Circuit Size for Sparse Quantum State Preparation [10.386753939552872]
我々は、$s$非ゼロ振幅を持つ$n$量子ビットスパース量子状態の準備を検討し、2つのアルゴリズムを提案する。
最初のアルゴリズムは$O(ns/log n + n)$ gatesを使用し、以前のメソッドを$O(log n)$で改善する。
2番目のアルゴリズムは、短いハミルトニアンパスを示す二進弦向けに調整されている。
論文 参考訳（メタデータ） (2024-04-08T02:13:40Z) - Quantum Algorithms for the Pathwise Lasso [1.8058773918890538]
古典的LARS(Least Angle Regression)パスワイズアルゴリズムに基づく新しい量子高次元線形回帰アルゴリズムを提案する。
我々の量子アルゴリズムは、ペナルティ項が変化するにつれて、完全な正規化パスを提供するが、特定の条件下では、イテレーション毎に2次的に高速である。
我々は、KKT条件の近似バージョンと双対性ギャップにより、LARSアルゴリズムがエラーに対して堅牢であることを証明した。
論文 参考訳（メタデータ） (2023-12-21T18:57:54Z) - 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) - 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) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Quantum Algorithms for Sampling Log-Concave Distributions and Estimating
Normalizing Constants [8.453228628258778]
我々は,対数凹分布をサンプリングし,正規化定数を推定するための量子アルゴリズムを開発した。
我々はモンテカルロ法と量子ウォークの量子アナログを利用する。
また、正規化定数を推定するための1/epsilon1-o(1)$量子下界も証明する。
論文 参考訳（メタデータ） (2022-10-12T19:10:43Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - 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) - Second-order Conditional Gradient Sliding [79.66739383117232]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。
SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。
実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文 参考訳（メタデータ） (2020-02-20T17:52:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。