Metraipolis › archive › dc_2de1acdebd42
Quantum Query Complexity of Tournament Solutions — arXiv:2610.39702
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.39702
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-01T02:48:03.206Z
- SHA-256 of the archived text
c6a249d51af05f6a81313c1c71459761a58fd4debec49a267876d8050c73494a- Stable URL of this page
https://metraipolis.com/documento/dc_2de1acdebd42
How to cite
Quantum Query Complexity of Tournament Solutions — arXiv:2610.39702 — arXiv (en), https://arxiv.org/abs/2610.39702 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_2de1acdebd42 (Metraipolis archive dc_2de1acdebd42, sha256 c6a249d51af05f6a81313c1c71459761a58fd4debec49a267876d8050c73494a)
BibTeX
@misc{dc2de1acdebd42,
title = {Quantum Query Complexity of Tournament Solutions — arXiv:2610.39702},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.39702},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_2de1acdebd42; sha256 c6a249d51af05f6a81313c1c71459761a58fd4debec49a267876d8050c73494a},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.39702. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 $\Theta(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\Theta(N)$ queries, and a Condorcet winner can be found with $\tilde \Theta(\sqrt N)$ queries. Finding a strong king requires $\Theta(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 $\Theta(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.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.CC, nuovi lavori del giorno).
Categorie arXiv: Quantum Physics (quant-ph) ; Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2610.39702 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-01T02:18:28.508Z dalla pagina https://arxiv.org/list/cs.CC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).