論文の概要: Quantum ordinal selection with two comparisons

• arxiv url: http://arxiv.org/abs/2610.34762v1
• Date: Mon, 26 Oct 2026 03:06:49 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-29 18:38:49.978002
• Title: Quantum ordinal selection with two comparisons
• Title（参考訳）: 2つの比較による量子順序選択
• Abstract要約: 我々は、未知の厳密な順序の少なくとも2つのノイズレスコヒーレントなペアワイズ比較を用いて、所定のランク閾値内で対象を選択する最適確率について検討した。 我々は、達成可能な成功を完全に特徴づける比較特化半定モデルを開発する。
• 参考スコア（独自算出の注目度）: 2.0752884602513832
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the optimal probability of selecting an object within a prescribed rank threshold using at most two noiseless coherent pairwise comparisons of an unknown strict order. Polynomial degree bounds alone can overestimate the success attainable with two comparisons. We develop a comparison-specific semidefinite model that completely characterizes attainable success. Computer-assisted proofs establish the exact optimum for every rank threshold at seven objects and for minimum selection at eight. For minimum selection, we construct an explicit algorithm family and determine its exact optimum. Bounds for all admissible two-comparison algorithms show that the family's asymptotic success is within 0.016% of the unrestricted optimum. We also prove that this relative gap has a strictly positive limit. The optimal quantum-to-classical success ratio for minimum selection converges to approximately 2.48 under the same two-comparison budget.
• Abstract（参考訳）: 我々は、未知の厳密な順序の少なくとも2つのノイズレスコヒーレントなペアワイズ比較を用いて、所定のランク閾値内で対象を選択する最適確率について検討した。 多項式次数境界だけでは、2つの比較で達成可能な成功を過大評価することができる。 我々は、達成可能な成功を完全に特徴づける比較特化半定モデルを開発する。 コンピュータ支援による証明は、7つのオブジェクトにおける各ランクしきい値、および8つのオブジェクトにおける最小選択に対する正確な最適値を確立する。 最小選択のために、明示的なアルゴリズムファミリを構築し、その正確な最適度を決定する。 すべての許容可能な2つの比較アルゴリズムの境界は、家族の漸近的成功が制限されない最適値の0.016%以内であることを示している。 また、この相対的ギャップが厳密な正の極限を持つことも証明する。 最小選択の最適量子-古典的成功比は、同じ2つの比較予算の下で約2.48に収束する。

関連論文リスト

• Resource Compatibility in Optimal Quantum Symmetry Testing [6.9022592726569085]
  我々は、型Iエラーをゼロとする全てのプロトコルに対して表現理論の逆を導出する。 次元$dgeq 2$の対角トーラスでは、一貫性のない最適なテストは単一のクエリでのみ可能である。
  論文  参考訳（メタデータ） (2026-09-29T17:54:30Z)
• Optimal Top-$k$ Identification from Pairwise Comparisons [0.0]
  雑音のあるペアワイズ比較から, 固定信頼トップ=k$識別の能動的学習問題について検討した。 この問題では、アイテムのペアを逐次選択して比較し、結果を観察し、エラー確率が最大$$$でトップ$k$アイテムのセットを返すことができる場合に停止する。
  論文  参考訳（メタデータ） (2026-07-09T22:55:16Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Explicit Second-Order Min-Max Optimization: Practical Algorithms and Complexity Analysis [71.05708939639537]
  本研究では,非制約問題に対するグローバルなサドル点を求めるために,不正確なNewton型手法をいくつか提案し,解析する。 提案手法は,Sur分解の必要回数の$O(log(1/eps)$因子をシェービングすることで,既存のライン検索に基づくmin-max最適化を改善する。
  論文  参考訳（メタデータ） (2022-10-23T21:24:37Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• On the Oracle Complexity of Higher-Order Smooth Non-Convex Finite-Sum Optimization [1.6973426830397942]
  平滑な非有限和最適化における高階法の下限を証明する。 pth-order regularized method は有限和の目的から利益を得ることができないことを示す。 新たな二階平滑性仮定は一階平均二乗平滑性に類似していると考えられる。
  論文  参考訳（メタデータ） (2021-03-08T23:33:58Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。 また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
  論文  参考訳（メタデータ） (2020-11-19T10:00:54Z)
• A New Randomized Primal-Dual Algorithm for Convex Optimization with Optimal Last Iterate Rates [16.54912614895861]
  我々は,非滑らかな制約付き凸最適化問題のクラスを解くために,新しいランダム化ブロック座標原始双対アルゴリズムを開発した。 我々は,一般凸性と強い凸性という2つのケースにおいて,アルゴリズムが最適収束率を達成することを証明した。 その結果,提案手法は異なる実験における性能向上に寄与していることがわかった。
  論文  参考訳（メタデータ） (2020-03-03T03:59:26Z)
• Ranking a set of objects: a graph based least-square approach [70.7866286425868]
  同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。 品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
  論文  参考訳（メタデータ） (2020-02-26T16:19:09Z)

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

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