Fugu-MT 論文翻訳(概要): Quantum Query Complexity of Tournament Solutions

論文の概要: Quantum Query Complexity of Tournament Solutions

arxiv url: http://arxiv.org/abs/2610.39702v1
Date: Thu, 29 Oct 2026 09:37:22 GMT
ステータス: 翻訳完了
システム内更新日: 2026-11-02 22:55:56.407817
Title: Quantum Query Complexity of Tournament Solutions
Title（参考訳）: トーナメント解の量子クエリ複雑性
Abstract要約: トーナメントソリューションは、トーナメントの勝者の集合、すなわち、$N$の選択肢間の全てのペアワイズ比較の結果を記録する。トップサイクルの量子クエリの複雑さは$tilde(N)$クエリで計算可能であることを示す。
参考スコア（独自算出の注目度）: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: A tournament solution records a set of winners from a tournament, that is, from the outcomes of all pairwise comparisons among $N$ alternatives. We study the quantum query complexity of computing tournament solutions when the outcome of each comparison has to be learned by a query. Classically, the picture is uniform: the Copeland set, the uncovered set and the top cycle all require $Θ(N^2)$ queries, and so does finding a single vertex of maximum out-degree. We show that the quantum query complexity of the top cycle can be computed with $\tildeΘ(N)$ queries, and a Condorcet winner can be found with $\tilde Θ(\sqrt N)$ queries. Finding a strong king requires $Θ(N^{3/2})$ queries, the same as finding a vertex of maximum out-degree. We also give a self-contained alternative proof of the known $Θ(N^{3/2})$ bound for finding a vertex of maximum degree, established by Gilani, Mande, Patro, and Raja. Our lower bounds reduce counting problems to tournament problems using Ambainis's adversary method. For the top cycle, we find a Hamiltonian path and locate the prefix forming the top cycle by divide and conquer.
Abstract（参考訳）: トーナメントソリューションは、トーナメントの勝者の集合、すなわち、$N$の選択肢間の全てのペアワイズ比較の結果を記録する。本稿では,各比較の結果を問合せで学習する必要があるとき,計算トーナメントソリューションの量子クエリ複雑性について検討する。古典的には、この図形は一様である: コープランド集合、未発見集合、およびトップサイクルはすべて$(N^2)$クエリを必要とする。トップサイクルの量子クエリの複雑さは$\tilde(N)$クエリで計算でき、Condorcetの勝者は$\tilde sh(\sqrt N)$クエリで見つけることができる。強い王を見つけるには、最大アウトディグリーの頂点を見つけるのと同様に、$(N^{3/2})$クエリが必要である。また、Gillani, Mande, Patro, Raja によって確立された最大次数頂点を求めるために、既知の$ s(N^{3/2})$ の自己完備な代替証明を与える。我々の下位境界は、アンバイニスの逆法を用いて、トーナメント問題にカウント問題を還元する。トップサイクルでは、ハミルトンの経路を見つけ、分割して征服することでトップサイクルを形成する接頭辞を見つける。

関連論文リスト

Quantum Query Complexity of Maximum Degree and its Generalizations [0.26097841018267615]
いくつかの基本グラフ問題の量子クエリ複雑性について検討する。すべての定数$kgeq 1$に対して、$O(n2-1/(k+1))$-query量子アルゴリズムを与える。我々は、$k$-Graph Collisionを含む最大$(k,n-k)$-Cutへの還元を確立する。
論文参考訳（メタデータ） (2026-10-09T17:47:01Z)
Hiding, Shuffling, and Cycle Finding: Quantum Algorithms on Edge Lists [5.127310126394387]
三角形探索問題の3つの変種の量子クエリ複雑性について検討する。 Zhandryのレコードクエリフレームワークのバウンダリが低いことを証明します。我々はBelovsの学習グラフアルゴリズムを$k$-distinctnessに適応させる。
論文参考訳（メタデータ） (2024-12-23T18:43:41Z)
Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。 1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
論文参考訳（メタデータ） (2024-11-29T05:29:47Z)
On the communication complexity of finding a king in a tournament [0.5999777817331317]
エッジが2つのプレイヤー間で分割されるタスクの通信複雑性について検討する。トーナメントのソースを見つけることは、無向グラフ上のよく研究されているClique vs. Independent Set(CIS)問題と同等であることを示す。
論文参考訳（メタデータ） (2024-02-22T18:11:19Z)
Randomized and quantum query complexities of finding a king in a tournament [0.0]
決定論的クエリの複雑さについて、最もよく知られた上限と下限を示す。我々の貢献は、*randomized* および *quantum* クエリモデルにおける Theta(n) および Theta(sqrtn) の*tight* 境界(対数要素まで)を示すことである。
論文参考訳（メタデータ） (2023-08-04T17:21:11Z)
Accelerating Inexact HyperGradient Descent for Bilevel Optimization [84.00488779515206]
本稿では,一般的な非コンケーブ二段階最適化問題の解法を提案する。また,非コンケーブ問題における2次定常点を求める際の既存の複雑性も改善した。
論文参考訳（メタデータ） (2023-06-30T20:36:44Z)
QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
論文参考訳（メタデータ） (2022-05-24T03:49:10Z)
Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文参考訳（メタデータ） (2021-01-20T04:29:18Z)
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)
Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
論文参考訳（メタデータ） (2020-06-22T05:00:13Z)
Query Complexity of Tournament Solutions [12.192470787877594]
我々は、コペランド集合、スレーター集合、マルコフ集合、バイパルチザン集合、未発見集合、バンクス集合、および最上位サイクルを見つけるアルゴリズムが、最悪の場合、$Omega(n2)$ edgesを問う必要があることを示す。肯定的な面では、入力トーナメントの上位サイクルのサイズが最大で1kドルであれば、上記のすべてのトーナメントソリューションが見つかることを証明して、クエリの複雑さを低く抑えることができる。
論文参考訳（メタデータ） (2016-11-18T18:19:32Z)

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

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