論文の概要: 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$であり、完全に厳密な正当性証明を持つ。
両アルゴリズムを非偏極雑音の存在下で解析し,アート振幅推定アルゴリズムの状態との比較を行った。
関連論文リスト
- 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) - Classical algorithms and quantum limitations for maximum cut on
high-girth graphs [6.262125516926276]
すべての(量子または古典的な)一局所アルゴリズムが$D$正規グラフに対して$5$の最大カットが1/2 + C/sqrtD$ for $C=1/sqrt2 approx 0.7071$であることを示す。
1/2 + C/sqrtD - O (1/sqrtk)$ for $D$-regular graphs of $> 2k+1$,
論文 参考訳(メタデータ) (2021-06-10T16:28:23Z) - Non-Boolean Quantum Amplitude Amplification and Quantum Mean Estimation [0.0]
本稿では, 量子振幅増幅と振幅推定アルゴリズムを非ブールオラクルで動作するように一般化する。
非ブールオラクルの固有値 $exp(ivarphi(x)$ は$pm 1$ に制限されない。
このような非ブールオラクルに基づく2つの新しい分子アルゴリズムが導入された。
論文 参考訳(メタデータ) (2021-02-09T17:48:38Z) - Enhancing the Quantum Linear Systems Algorithm using Richardson
Extrapolation [0.8057006406834467]
Amathbfx=mathbfb$という形の線形方程式の系を解く量子アルゴリズムを提案する。
このアルゴリズムは古典的手法に対して$N$に対して指数関数的に改善する。
論文 参考訳(メタデータ) (2020-09-09T18:00:09Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳(メタデータ) (2020-07-07T17:10:00Z) - Second-order Conditional Gradient Sliding [79.66739383117232]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。
SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。
実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文 参考訳(メタデータ) (2020-02-20T17:52:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。