Accelerating Voting by Quantum Computation

Studying the computational complexity of determining winners under voting rules and designing fast algorithms are classical and fundamental questions in computational social choice. In this paper, we accelerate voting by leveraging quantum computing. We propose a quantum-accelerated voting algorithm that can be applied to any anonymous voting rule. We further 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 output the correct winner with runtime $\Theta\left(\frac{n}{\text{MOV}}\right)$, where $n$ is the number of votes and $\text{MOV}$ is margin of victory, the smallest number of voters to change the winner. On the other hand, any classical voting algorithm based on sampling with replacement requires runtime $\Omega\left(\frac{n^2}{\text{MOV}^2}\right)$ under a large subset of voting rules. Our theoretical results are supported by experiments under plurality, Borda, Copeland, and STV.