論文の概要: One Weird Trick Tightens the Quantum Adversary Bound, Especially for
Success Probability Close to $1/2$
- arxiv url: http://arxiv.org/abs/2303.10244v1
- Date: Fri, 17 Mar 2023 20:48:33 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-21 20:31:43.920690
- Title: One Weird Trick Tightens the Quantum Adversary Bound, Especially for
Success Probability Close to $1/2$
- Title（参考訳）: 1つの奇妙なトリックは、特に1/2ドルに近い成功確率のために、量子敵境界を締め付ける。
- Authors: Duyal Yolcu
- Abstract要約: 同じクエリ数で不完全な入力非依存の初期状態から完全に区別可能な最終状態に変換するアルゴリズムを構築する。
最初のグラマー行列に対する$delta$-dependent条件は、最終グラマー行列における元のアルゴリズムの条件と比較して、強化プレファクターを導出することができる。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: The textbook adversary bound for function evaluation states that to evaluate
a function $f\colon D\to C$ with success probability $\frac{1}{2}+\delta$ in
the quantum query model, one needs at least $\left( 2\delta -\sqrt{1-4\delta^2}
\right) Adv(f)$ queries, where $Adv(f)$ is the optimal value of a certain
optimization problem. For $\delta \ll 1$, this only allows for a bound of
$\Theta\left(\delta^2 Adv(f)\right)$ even after a
repetition-and-majority-voting argument. In contrast, the polynomial method can
sometimes prove a bound that doesn't converge to $0$ as $\delta \to 0$. We
improve the $\delta$-dependent prefactor and achieve a bound of $2\delta
Adv(f)$. The proof idea is to "turn the output condition into an input
condition": From an algorithm that transforms perfectly input-independent
initial to imperfectly distinguishable final states, we construct one that
transforms imperfectly input-independent initial to perfectly distinguishable
final states in the same number of queries by projecting onto the "correct"
final subspaces and uncomputing. The resulting $\delta$-dependent condition on
initial Gram matrices, compared to the original algorithm's condition on final
Gram matrices, allows deriving the tightened prefactor.
- Abstract（参考訳）: 関数評価のための教科書の逆境は、成功確率を持つ関数$f\colon d\to c$を量子クエリモデルで評価するには、少なくとも$\left(2\delta -\sqrt{1-4\delta^2} \right) adv(f)$クエリが必要であり、ここで$adv(f)$は最適化問題の最適値である。
これは$\delta \ll 1$ に対して、繰り返しと多数の引数の後にも$\theta\left(\delta^2 adv(f)\right)$ のバウンドしか許さない。
対照的に多項式法は、$0$ に収束しない境界を $\delta \to 0$ として証明することができる。
我々は$\delta$-dependentプレファクタを改善し、$2\delta Adv(f)$のバウンドを達成する。
完全入力非依存初期状態から不完全な識別可能な最終状態へ変換するアルゴリズムから、不完全入力非依存初期状態から完全識別可能な最終状態まで、同じ数のクエリで「正しい」最終部分空間に投影して計算不能な状態に変換するアルゴリズムを構築する。
初期グラム行列に対する$\delta$-依存条件は、最終グラム行列における元のアルゴリズムの条件と比較して、引き締められた前因子を導出することができる。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Tight Bounds for Quantum Phase Estimation and Related Problems [0.90238471756546]
精度$delta$と誤差確率$epsilon$は$Omegaleft(frac1deltalog1epsilonright)$であることを示す。
また、多くのアドバイス(アドバイス準備ユニタリの応用)を持つことは、コストを大幅に削減することはなく、また、$U$の固有値に関する知識も少なくないことも示している。
論文 参考訳（メタデータ） (2023-05-08T17:46:01Z) - Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。
我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。
我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
論文 参考訳（メタデータ） (2022-09-30T04:15:44Z) - The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。
すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
論文 参考訳（メタデータ） (2022-09-04T10:01:39Z) - Tractability from overparametrization: The example of the negative
perceptron [9.077560551700163]
我々は線形プログラミングアルゴリズムを解析し、対応するしきい値である$delta_textlin(kappa)$を特徴付ける。
閾値$delta_textlin(kappa)$間のギャップを観察し、他のアルゴリズムの振る舞いに関する疑問を提起する。
論文 参考訳（メタデータ） (2021-10-28T01:00:13Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z) - On Efficient Low Distortion Ultrametric Embedding [18.227854382422112]
データの基盤となる階層構造を保存するために広く用いられる方法は、データを木や超音波に埋め込む方法を見つけることである。
本稿では,$mathbbRd2(ユニバーサル定数$rho>1$)の点集合を入力として,超測度$Deltaを出力する新しいアルゴリズムを提案する。
我々のアルゴリズムの出力はリンクアルゴリズムの出力に匹敵するが、より高速な実行時間を実現する。
論文 参考訳（メタデータ） (2020-08-15T11:06:45Z) - Agnostic Q-learning with Function Approximation in Deterministic
Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。
もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文 参考訳（メタデータ） (2020-02-17T18:41:49Z) - Backtracking Gradient Descent allowing unbounded learning rates [0.0]
ユークリッド空間上の非制約最適化では、勾配 Descent process (GD) $x_n+1=x_n-delta _n nabla f(x_n)$ の収束を証明するために、通常、学習レート $delta _n$'s が有界であることが要求される。
本稿では,学習率$delta _n$を非有界にする。
この$h$の成長率は、シーケンスの$x_n$の収束を望んでいれば最善であることが示される。
論文 参考訳（メタデータ） (2020-01-07T12:52:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。