論文の概要: The Adversary Bound Revisited: From Optimal Query Algorithms to Optimal Control

• arxiv url: http://arxiv.org/abs/2211.16293v3
• Date: Wed, 22 Feb 2023 17:29:09 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-25 03:45:59.259051
• Title: The Adversary Bound Revisited: From Optimal Query Algorithms to Optimal Control
• Title（参考訳）: 逆境界再考:最適なクエリアルゴリズムから最適制御へ
• Authors: Duyal Yolcu
• Abstract要約: このノートは"One-Way Ticket to Las Vegas and the Quantum Adversary"という論文を補完している。 私は、Barnum-Saks-Szegedyと同じ視点で、逆境界-普遍アルゴリズムの双対性を異なる形で開発する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: This note complements the paper "One-Way Ticket to Las Vegas and the Quantum Adversary" (arxiv:2301.02003). I develop the ideas behind the adversary bound - universal algorithm duality therein in a different form, using the same perspective as Barnum-Saks-Szegedy in which query algorithms are defined as sequences of feasible reduced density matrices rather than sequences of unitaries. This form may be faster to understand for a general quantum information audience: It avoids defining the "unidirectional relative $\gamma_{2}$-bound" and relating it to query algorithms explicitly. This proof is also more general because the lower bound (and universal query algorithm) apply to a class of optimal control problems rather than just query problems. That is in addition to the advantages to be discussed in Belovs-Yolcu, namely the more elementary algorithm and correctness proof that avoids phase estimation and spectral analysis, allows for limited treatment of noise, and removes another $\Theta(\log(1/\epsilon))$ factor from the runtime compared to the previous discrete-time algorithm.
• Abstract（参考訳）: このノートは"One-Way Ticket to Las Vegas and the Quantum Adversary" (arxiv:2301.02003)を補完している。 逆ユニバーサルアルゴリズムの双対性は,バーナム・サクス=セゲディと同様の視点で,クエリアルゴリズムをユニタリーの列ではなく,実現可能な縮小密度行列の列として定義する。 一般の量子情報オーディエンスにとって、この形式はより高速に理解できるかもしれない: これは"一方向の相対的な$\gamma_{2}$-bound"を定義することを避け、クエリアルゴリズムを明示的に関連付ける。 この証明は、下界(および普遍的なクエリアルゴリズム)が単なるクエリ問題ではなく、最適制御問題のクラスに適用されるため、より一般的なものである。 これに加えて、belovs-yolcuでは、位相推定やスペクトル分析を回避し、ノイズの扱いを制限し、以前の離散時間アルゴリズムと比較してランタイムから$\theta(\log(1/\epsilon))$ factorを削除できるという、より基本的なアルゴリズムと正確性証明について論じるべき利点もある。

関連論文リスト

• Bregman-divergence-based Arimoto-Blahut algorithm [53.64687146666141]
  本稿では,Arimoto-BlahutアルゴリズムをBregman-Diversergenceシステム上で定義された一般関数に一般化する。 本稿では,古典的および量子速度歪み理論に適用可能な凸最適化自由アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-08-10T06:16:24Z)
• Optimal Coherent Quantum Phase Estimation via Tapering [0.0]
  量子位相推定は、多くの量子アルゴリズムを支える基本的なプリミティブの1つである。 我々は,テープ型量子位相推定アルゴリズムと呼ばれる標準アルゴリズムの改良版を提案する。 提案アルゴリズムは,高コストなコヒーレント中央値手法を必要とせず,最適なクエリ複雑性を実現する。
  論文  参考訳（メタデータ） (2024-03-27T18:17:23Z)
• Robust and Space-Efficient Dual Adversary Quantum Query Algorithms [0.0]
  一般逆双対は量子コンピューティングの強力なツールである。 ブール関数を決定するクェリ最適境界エラー量子補題を与える。 ほぼ満足のいく制約を処理できる頑健な二重対向アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-06-26T19:59:30Z)
• An adaptive Bayesian quantum algorithm for phase estimation [0.0]
  平均絶対誤差と平均二乗誤差の最適2次スケーリングを実現するためのコヒーレンスに基づく位相推定アルゴリズムを提案する。 ノイズの存在下で、我々のアルゴリズムは理論的な下界に近づく誤差を生成する。
  論文  参考訳（メタデータ） (2023-03-02T19:00:01Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。 補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。 各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
  論文  参考訳（メタデータ） (2022-06-30T03:15:23Z)
• Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit Optimization [63.8557841188626]
  期待されている改善(EI)アルゴリズムは、不確実性の下で最適化するための最も一般的な戦略の1つである。 本稿では,GP予測平均を通した標準既存値を持つEIの変種を提案する。 我々のアルゴリズムは収束し、$mathcal O(gamma_TsqrtT)$の累積後悔境界を達成することを示す。
  論文  参考訳（メタデータ） (2022-03-15T13:17:53Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。 この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。 古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
  論文  参考訳（メタデータ） (2020-07-01T18:43:32Z)
• An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits [34.06611065493047]
  本稿では、信頼度と予算設定の固定化において、純探索線形帯域問題に対する近似アルゴリズムを提案する。 サンプルの複雑性がインスタンスの幾何でスケールし、アームの数に縛られた明示的な結合を避けるアルゴリズムを提供する。 また,固定予算設定における線形帯域幅に対する最初のアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-21T00:56:33Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。 ラグランジアン分解に基づく新しい手法を提案する。 ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2020-02-24T17:55:10Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。