  Studying the computational complexity and designing fast algorithms for
determining winners under voting rules are classical and fundamental questions
in computational social choice. In this paper, we accelerate voting by
leveraging quantum computation: we propose a quantum-accelerated voting
algorithm that can be applied to any anonymous voting rule. We show that our
algorithm can be quadratically faster than any classical algorithm (based on
sampling with replacement) under a wide range of common voting rules, including
positional scoring rules, Copeland, and single transferable voting (STV).
Precisely, our quantum-accelerated voting algorithm outputs the correct winner
with high probability in $\Theta\left(\frac{n}{\text{MOV}}\right)$ time, where
$n$ is the number of votes and $\text{MOV}$ is {\em margin of victory}, the
smallest number of voters to change the winner. In contrast, any classical
voting algorithm based on sampling with replacement requires
$\Omega\left(\frac{n^2}{\text{MOV}^2}\right)$ time under a large class of
voting rules. Our theoretical results are supported by experiments under
plurality, Borda, Copeland, and STV.

Computers and Society;Quantum Physics