{"id":"arxiv/2610.39702","url":"https://arxiv.org/abs/2610.39702","tags":["quant-ph","cs.CC"],"score":0,"title":"Quantum Query Complexity of Tournament Solutions","domain":"quant-ph","source":"arxiv","authors":["Pragya Arora","Udit Kumar"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-10-29","reactions":{}}