pipette
ENEnglish

Quantum Query Complexity of Tournament Solutions

Pragya Arora, Udit Kumar

Preprint

En palabras de los autores

A tournament solution records a set of winners from a tournament, that is, from the outcomes of all pairwise comparisons among 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 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 queries, and a Condorcet winner can be found with queries. Finding a strong king requires queries, the same as finding a vertex of maximum out-degree. We also give a self-contained alternative proof of the known 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.

Resultado principalEl resumen no menciona limitaciones.

Apareció: viernes, 30 de octubre. arXiv. Preprint, todavía sin revisión por pares.