arXiv preprint ·
Quantum Query Complexity of Tournament Solutions
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Quantum Physics
Quantum query complexity of Hurwitz stability testing
Retrieval Sequencing in a Compact Storage System with Side Access
Lowered crossover points of Anthropic's subexponential 3-SAT algorithm
Half-Optimal Induced Matchings in Random Graphs: Online and Low-Degree Algorithms
Exponential quantum-classical query separations for cyclic Forrelation
Get the few papers worth your time in Quantum Physics every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.