Quantum methods speed up finding winners in pairwise tournaments
Quantum Query Complexity of Tournament Solutions
Computational Complexity
Summary
When you have many options and compare them in pairs to find the best ones, it can take a lot of time to check all pairs. This paper shows that using quantum computing ideas can reduce the number of comparisons needed for certain ways to choose winners. For some winner sets, quantum algorithms need much fewer checks than classical methods. The authors also prove limits on how efficient these quantum approaches can be for different types of winners.
What this means in practice
- •For quantum algorithm designers: Design quantum algorithms that find specific winners in tournaments more efficiently than classical methods.
- •For decision support system developers: Reduce the complexity of identifying top alternatives in large pairwise comparison datasets using quantum-inspired approaches.
A theory result. No direct application yet.
Authors
Pragya Arora, Udit Kumar
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.