Quantum Query Complexity of Tournament Solutions
quant-ph, cs.CC
Submitted: 2026-10-29
Updated: 2026-10-29
License: http://creativecommons.org/licenses/by/4.0/
The gist: A tournament solution records a set of winners from a tournament, that is, from the outcomes of all pairwise comparisons among N alternatives.
Terminology
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 Θ(N) queries, and a Condorcet winner can be found with Θ(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.
Related papers
- Computational regimes in matrix-product-state-based quantum trajectory simulations
- Toward chemically accurate quantum simulations on quantum hardware: A quantum-HPC hybrid approach
- Transversal surface-code game with reconfigurable qubits
- Fulqrum: a generalized framework for quantum subspace diagonalization
- Flux-Activated Resonant Control of a Bosonic Quantum Memory
- Machine learning the effects of many quantum measurements