Accelerating Voting by Quantum Computation

Liu, A; Han, Q; Xia, L; Yu, N

Accelerating Voting by Quantum Computation

Liu, A Han, Q Xia, L Yu, N

Permalink

Publication Type:: Conference Proceeding
Citation:: Proceedings of Machine Learning Research, 2023, 216, pp. 1274-1283
Issue Date:: 2023-01-01

Closed Access

	Filename	Description	Size
	liu23a.pdf	Published version	326.75 kB		View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Liu, A
dc.contributor.author	Han, Q
dc.contributor.author	Xia, L
dc.contributor.author	Yu, N https://orcid.org/0000-0003-1188-3032
dc.date.accessioned	2024-06-06T03:50:41Z
dc.date.available	2024-06-06T03:50:41Z
dc.date.issued	2023-01-01
dc.identifier.citation	Proceedings of Machine Learning Research, 2023, 216, pp. 1274-1283
dc.identifier.issn	2640-3498
dc.identifier.uri	http://hdl.handle.net/10453/179439
dc.description.abstract	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 (Equation presented) time, where n is the number of votes and MoV is margin of victory, the smallest number of voters to change the winner. In contrast, any classical voting algorithm based on sampling with replacement requires (Equation presented) time under a large class of voting rules. Our theoretical results are supported by experiments under plurality, Borda, Copeland, and STV.
dc.language	en
dc.relation.ispartof	Proceedings of Machine Learning Research
dc.rights	info:eu-repo/semantics/closedAccess
dc.title	Accelerating Voting by Quantum Computation
dc.type	Conference Proceeding
utslib.citation.volume	216
pubs.organisational-group	University of Technology Sydney
pubs.organisational-group	University of Technology Sydney/Faculty of Engineering and Information Technology
utslib.copyright.status	closed_access	*
dc.date.updated	2024-06-06T03:50:40Z
pubs.publication-status	Published
pubs.volume	216

Abstract:

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 (Equation presented) time, where n is the number of votes and MoV is margin of victory, the smallest number of voters to change the winner. In contrast, any classical voting algorithm based on sampling with replacement requires (Equation presented) time under a large class of voting rules. Our theoretical results are supported by experiments under plurality, Borda, Copeland, and STV.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/179439