論文の概要: A Note on Quantum Phase Estimation
- arxiv url: http://arxiv.org/abs/2304.02241v1
- Date: Wed, 5 Apr 2023 06:05:42 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-06 13:18:52.247164
- Title: A Note on Quantum Phase Estimation
- Title（参考訳）: 量子位相推定に関する一考察
- Authors: Yao-Ting Lin
- Abstract要約: より単純で自己完結したクエリローバウンドの証明を示す。
具体的には,ブール関数解析や逆法の知識を使わずに,基本線型代数から成り立つ。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this work, we study the phase estimation problem. We show an alternative,
simpler and self-contained proof of query lower bounds. Technically, compared
to the previous proofs [NW99, Bes05], our proof is considerably elementary.
Specifically, our proof consists of basic linear algebra without using the
knowledge of Boolean function analysis and adversary methods. Qualitatively,
our bound is tight in the low success probability regime and offers a more
fine-grained trade-off. In particular, we prove that for any $\epsilon > 0, p
\geq 0$, every algorithm requires at least $\Omega(p/{\epsilon})$ queries to
obtain an ${\epsilon}$-approximation for the phase with probability at least p.
However, the existing bounds hold only when $p > 1/2$. Quantitatively, our
bound is tight since it matches the well-known phase estimation algorithm of
Cleve, Ekert, Macchiavello, and Mosca [CEMM98] which requires $O(1/{\epsilon})$
queries to obtain an ${\epsilon}$-approximation with a constant probability.
Following the derivation of the lower bound in our framework, we give a new and
intuitive interpretation of the phase estimation algorithm of [CEMM98], which
might be of independent interest.
- Abstract（参考訳）: 本研究では,位相推定問題について検討する。
より単純で自己完結したクエリ下限の証明を示す。
技術的には、以前の証明 [NW99, Bes05] と比較して、我々の証明はかなり初等的である。
具体的には,ブール関数解析や逆解析の知識を使わずに,基本的な線形代数からなる。
定性的には、私たちの境界は低い成功確率体制に密着しており、よりきめ細かいトレードオフを提供する。
特に、任意の$\epsilon > 0, p \geq 0$に対して、すべてのアルゴリズムは少なくとも p の確率の位相に対して${\epsilon}$近似を得るために少なくとも $\omega(p/{\epsilon})$クエリを必要とすることを証明する。
しかし、既存の境界は$p > 1/2$ の場合のみ保持する。
定量的には、我々の境界はCleve, Ekert, Macchiavello, Mosca [CEMM98]のよく知られた位相推定アルゴリズムと一致するので、一定の確率で${\epsilon}$-approximationを得るには$O(1/{\epsilon})$クエリが必要である。
我々のフレームワークの下位境界の導出に続いて、我々は[CEMM98]の位相推定アルゴリズムを新しく直感的に解釈する。
関連論文リスト
- Outlier-robust Mean Estimation near the Breakdown Point via Sum-of-Squares [4.335413713700667]
我々は citekothari2018robust で導入された正準平方和プログラムを新たに解析する。
このプログラムは,すべての $varepsilon に対して[0,frac12)$ の誤差率を効率よく達成できることを示す。
論文 参考訳（メタデータ） (2024-11-21T16:57:05Z) - Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。
我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
論文 参考訳（メタデータ） (2024-06-18T08:54:04Z) - Convergence of AdaGrad for Non-convex Objectives: Simple Proofs and
Relaxed Assumptions [33.49807210207286]
新しい補助関数$xi$は、AdaGradsイテレーションの数値と分母の間の相関を扱う複雑さを取り除くのに役立つ。
AdaGradは,学習率がしきい値より低い限り,$(L_0)$smooth条件下での収束に成功していることを示す。
論文 参考訳（メタデータ） (2023-05-29T09:33:04Z) - Tight Bounds for Quantum Phase Estimation and Related Problems [0.90238471756546]
精度$delta$と誤差確率$epsilon$は$Omegaleft(frac1deltalog1epsilonright)$であることを示す。
また、多くのアドバイス(アドバイス準備ユニタリの応用)を持つことは、コストを大幅に削減することはなく、また、$U$の固有値に関する知識も少なくないことも示している。
論文 参考訳（メタデータ） (2023-05-08T17:46:01Z) - Breaking the Lower Bound with (Little) Structure: Acceleration in
Non-Convex Stochastic Optimization with Heavy-Tailed Noise [28.780192812703948]
重み付き雑音状態において、滑らかだが必ずしも凸な目標を持つ最適化問題を考察する。
簡単な構造しか持たない低境界の$Omega(Tfrac1-p3p-2)$よりも高速な速度が得られることを示す。
また、軽度条件下では、高い確率収束率が$O(log(T/delta)Tfrac1-p3p-2)$であることを保証する。
論文 参考訳（メタデータ） (2023-02-14T00:23:42Z) - Unitarity estimation for quantum channels [7.323367190336826]
ユニタリティ推定は、量子デバイス認証とベンチマークにおいて基礎的で重要な問題である。
我々は、アンシラ効率のアルゴリズムを誘導するユニタリティ推定のための統一的なフレームワークを提供する。
アルゴリズムの$d$-dependenceと$epsilon$-dependenceの両方が最適であることを示す。
論文 参考訳（メタデータ） (2022-12-19T09:36:33Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad
Stepsize [55.0090961425708]
本研究では,AdaGradのスムーズな非確率問題に対する簡易な高確率解析法を提案する。
我々はモジュラーな方法で解析を行い、決定論的設定において相補的な$mathcal O (1 / TT)$収束率を得る。
我々の知る限りでは、これは真に適応的なスキームを持つAdaGradにとって初めての高い確率である。
論文 参考訳（メタデータ） (2022-04-06T13:50:33Z) - Improved Sample Complexity for Incremental Autonomous Exploration in
MDPs [132.88757893161699]
我々は $epsilon$-optimal 目標条件付きポリシーのセットを学び、$ L$ ステップ内で段階的に到達可能なすべての状態を達成します。
DisCoは、コストに敏感な最短経路問題に対して$epsilon/c_min$-optimalポリシーを返すことができる最初のアルゴリズムです。
論文 参考訳（メタデータ） (2020-12-29T14:06:09Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳（メタデータ） (2020-06-19T14:11:26Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳（メタデータ） (2020-06-04T17:51:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。