技術要約：トーナメント解の量子クエリ計算量

問題の定義

本論文は、様々なトーナメント解を計算するための量子クエリ計算量を調査している。トーナメントとは、すべての異なる頂点のペアが正確に1つの弧（アーク）で結ばれた有向グラフであり、総当たり戦やペアごとの多数決関係をモデル化している。トーナメント解は、トーナメントを非空の「勝者」頂点の集合へと写像するものである。

クエリモデルにおいて、トーナメントは暗黙的に与えられる。アルゴリズムは、エッジ $(u, v)$ をクエリすることによってのみ、その向きを知ることができる。コストはクエリ数である。これらの問題における古典的なクエリ計算量は、多くの場合一様（典型的には $\Theta(N^2)$）であるが、本研究では、量子アルゴリズム（重ね合わせやグローバー探索を利用したもの）が大幅な高速化を実現できるかどうかを探求している。

研究対象となっている具体的な解は以下の通りである：

• コンドルセ勝者 (Condorcet Winner): 他のすべての頂点を破る頂点。
• コープレランド集合 (Copeland Set, $CO(T)$): 最大の出次数を持つ頂点の集合。
• アンカバード集合 (Uncovered Set, $UC(T)$): 「キング（王）」の集合（2ステップ以内で他のすべての頂点に到達できる頂点）。
• ストロング・キング (Strong King): すべての $u$ が $v$ を破る場合において、$v$ が $u$ が $v$ を破るよりも多くの頂点を破る（具体的には $p(v,u) > p(u,v)$）ような頂点 $v$。
• トップサイクル (Top Cycle, $TC(T)$): 唯一の最小の支配的集合（集合内のすべてのメンバーが集合外のすべての頂点を破るような集合）。

手法

著者らは、量子アルゴリズム設計と下界技法の組み合わせを用いている：

1. 下界 (アドバーサリ法):

   • 下界を証明するための主要なツールは、アンベインスのアドバーサリ法 (Ambainis's adversary method) (定理 2.13) である。
   • これを適用するために、著者らはヘビーロウ (Heavy-Row) という新しいプロミス問題を導入している。これは、$m \times m$ のブール行列において、ある1つの行を除いてすべての行の重みが $k$ であり、その1つの行だけが重み $k+1$ であるとき、ヘビーな行が存在するかどうかを判定する問題である。
   • 著者らは、アドバーサリ法を用いて $Q(\text{Heavy-Row}) = \Omega(m^{3/2})$ を直接証明し、先行研究 [14] で用いられていた合成定理の使用を回避している。
   • この問題は、出次数や構造的特性（ストロング・キングなどの）がヘビーな行の存在に依存する特定のトーナメントを構成することによって、トーナメントの問題へと帰着される。
   • コープレランド集合については、複数の行がヘビーになり得る Heavy-Rows$_k$ へと一般化し、$\Omega(N^2)$ の下界を確立している。
   • アンカバード集合については、「タイト（tight）」な行列と「デフィシェント（deficient）」な行列を数える問題である Tight-Count を定義し、$\Omega(N^{3/2})$ の下界を確立している。

2. 上界 (アルゴリズム設計):

   • トップサイクル: アルゴリズムは、まず挿入ソートを用いて $O(N \log N)$ クエリでハミルトン路を見つける。トップサイクルはこのパスの接頭辞（プレフィックス）に対応する。この接頭辞の終端を見つける問題は、バックエッジを効率的に特定するために、分割統治法と量子最小値探索 (Dürr-Høyer) を組み合わせた区間被覆問題へと帰着される。
   • コンドルセ勝者: アルゴリズムは、キングを見つけ（[25] の $O(\sqrt{N} \text{polylog } N)$ アルゴリズムを使用）、その後、グローバー探索を行って、そのキングを破る頂点が存在するかどうかを確認する。
   • ストロング・キング: 最大出次数頂点を見つけることが可能であるという事実から、上界は直ちに導かれる。これには最大次数頂点を見つけるための $\Theta(N^{3/2})$ のアルゴリズムが利用される。

主な貢献と結果

本論文は、以下の量子クエリ計算量を確立している（ここで $N$ は頂点数であり、$\tilde{O}$ は対数因子を隠蔽している）：

問題	古典的計算量	量子計算量	主要な結果
コンドルセ勝者	$\Theta(N)$	$\tilde{\Theta}(\sqrt{N})$	大幅な高速化。King + Grover によって発見される。
トップサイクル	$\Theta(N^2)$	$\tilde{\Theta}(N)$	大幅な高速化。 トップサイクルは、入れ子になった3つの集合 ($CO \subseteq UC \subseteq TC$) の中で、量子的に計算するのが最も「容易」である。
最大出次数頂点	$\Theta(N^2)$	$\Theta(N^{3/2})$	先行研究 [14] と一致。著者らは、Heavy-Row への帰着による自己完結的な証明を提供している。
ストロング・キング	$\Theta(N^2)$	$\Theta(N^{3/2})$	古典に対して多項式的な高速化を実現するが、単一のキングを見つけること ($\tilde{O}(\sqrt{N})$) よりは遅い。
アンカバード集合 (Kings)	$\Theta(N^2)$	$\Omega(N^{3/2}), O(N^2)$	「集合の問題」と「単一要素の問題」を分離している。すべてのキングを見つけることは、1つを見つけることよりも難しい。
コープレランド集合	$\Theta(N^2)$	$\Theta(N^2)$	高速化なし。 最大次数頂点の集合全体を計算するには、エッジの定数割合を読み取る必要があり、古典的な境界と一致する。

具体的な技術的知見:

• コープレランド集合の困難性: 著者らは、単一のコープレランド勝者（最大次数頂点）を見つけるには $\Theta(N^{3/2})$ かかる一方で、そのような頂点の集合全体を計算するには $\Theta(N^2)$ クエリが必要であることを示している。これは、トップサイクルにおいて、集合が個々の最大次数頂点よりも速く計算されることと対照的である。
• ストロング・キング: ストロング・キングを見つけるには $\Theta(N^{3/2})$ クエリが必要である。これは古典的な $\Theta(N^2)$ に対する多項式的な高速化であるが、一般的なキングを見つける場合の $\tilde{O}(\sqrt{N})$ よりは大幅に遅い。
• トップサイクル・アルゴリズム: アルゴリズムは $O(N \log^2 N)$ クエリを達成する。これは、$\Theta(N^2)$ ビット上の OR 関数を埋め込むことから導かれる下界 $\Omega(N)$ に対して、対数因子を除いて最適である。
• 代替証明: 本論文は、合成定理 [14] をバイパスし、アドバーサリ法を介して Heavy-Row 問題から直接帰着させることで、最大次数頂点の $\Theta(N^{3/2})$ 境界に対する自己完結的な証明を提供している。

意義と主張

本論文は、トーナメント解の量子クエリ計算量は、古典的な場合とは異なり、一様ではないと主張している。

• 困難さの階層: 量子設定においては、最大の解集合（トップサイクル）が最も計算しやすく（$\tilde{\Theta}(N)$）、最小の集合（コープレランド集合）が最も難しい（$\Theta(N^2)$）。
• 集合 vs 要素: 「集合全体を計算することは、その中の単一の要素を見つけることよりも厳密に難しい場合がある」という点が中心的なテーマである。
  • キングの場合：1つを見つけるのは $\tilde{O}(\sqrt{N})$ だが、集合全体（アンカバード集合）を見つけるのは $\Omega(N^{3/2})$ である。
  • コープレランドの場合：1つを見つけるのは $\Theta(N^{3/2})$ だが、集合全体を見つけるのは $\Theta(N^2)$ である。
• 構造的洞察: 著者らは、これらの問題の困難さが、探索（searching）よりも計数（counting）（次数や特定の構造のカウントを決定すること）に起因していることを強調している。グローバー探索は特定の要素を見つけるのには役立つが、計数の問題はしばしば高い計算量を維持するか、あるいは入力の大部分を読み取ることを要求する。

著者らは、これらの結果がトーナメント解の再評価を必要とすることを結論付けており、量子的な高速化が、トーナメントの具体的な定義および基礎となる構造的特性に強く依存していることを示している。