Quantum Query Complexity of Tournament Solutions

@misc{arora2026quantum,
  title = {{Quantum Query Complexity of Tournament Solutions}},
  author = {Pragya Arora and Udit Kumar},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.39702},
  eprint = {2610.39702},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.39702},
  note = {CC BY 4.0},
}

TY  - UNPB
TI  - Quantum Query Complexity of Tournament Solutions
AU  - Pragya Arora
AU  - Udit Kumar
PY  - 2026
DA  - 2026/10/29
PB  - arXiv
DO  - 10.48550/arxiv.2610.39702
UR  - https://arxiv.org/abs/2610.39702
AB  - 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 Θ̃(N) queries, and a Condorcet winner can be found with Θ̃(√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.
ER  -