The election, a cornerstone of democracy, is one of the best-recognizable symbols of democratic governance. Voters' confidence in elections is essential, and these days, we can watch practically in live broadcast what consequences distrust in the fairness of elections may have. From the times of the celebrated Gibbard-Satterthwaite theorem, it is well-known in the social-choice community that most voting systems are vulnerable to the efforts of various players to influence elections. Luckily for us, computing such influence to affect election outcomes is a hard problem from the computational complexity perspective. This intractability is regarded as a ``complexity shield'' that secures voting rules against this malicious behavior.In this work, we consider quantum computers to be a new threat to the complexity shield described above, as they break out of standard computing paradigms and unlock additional computational resources. To this end, we provide an overview of possible attacks on election, discuss the abilities of quantum computing, and chart possible directions for future research in this area.
Robert Bredereck, Jiehua Chen, and Gerhard J. Woeginger. 2016. Are there any nicely structured preference proles nearby? Mathematical Social Sciences 79 (2016), 6173. Eric Brelsford, Piotr Faliszewski, Edith Hemaspaandra, Henning Schnoor, and Ilka Schnoor. 2008. Approximability of Manipulating Elections. In Proceedings of the 23rd AAAI Conference on Articial Intelligence, AAAI 08. AAAI Press, Palo Alto, CA, USA, 4449. Dvid Burka, Clemens Puppe, Lszl Szepesvry, and Attila Tasndi. 2022. Voting: A machine learning approach. European Journal of Operational Research 299, 3 (2022), 10031017.
id: cebf2dd875700de5c110846803680803 - page: 5
Costin Badescu and Ryan ODonnell. 2021. Improved Quantum data analysis. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 21. ACM, 13981411. Single transferable vote Social Choice and Welfare 8, 4 (1991), 341354. John J. Bartholdi III and James B. Orlin. 1991. resists strategic voting. Davide Castelvecchi. 2024. The AIquantum computing mash-up: will it revolutionize science? Nature (2024). Nested Applicable Algebra in 311338.
id: f7a80e4b3f42e21b11648c39870e2b76 - page: 5
Nicolas J. Cerf, Lov K. Grover, and Colin P. Williams. 2000. Quantum Search and NP-Hard Problems. Engineering, Communication and Computing 10, 4 (2000), John J. Bartholdi III, Craig A. Tovey, and Michael A. Trick. 1989. The Computational Diculty of Manipulating an Election. Social Choice and Welfare 6, 3 (1989), 227241. Jiehua Chen, Piotr Faliszewski, Rolf Niedermeier, and Nimrod Talmon. 2017. Elections with Few Voters: Candidate Control Can Be Easy. Journal of Articial Intelligence Research 60 (2017), 9371002. John J. Bartholdi III, Craig A. Tovey, and Michael A. Trick. 1989. Voting schemes for which it can be dicult to tell who won the election. Social Choice and Welfare 6, 2 (1989), 157165.
id: 224cdac22e4da6748783bccd0c58e085 - page: 5
Zo Christo and Davide Grossi. 2017. Binary Voting with Delegable Proxy: An Analysis of Liquid Democracy. In Proceedings of the 16th Conference on Theoretical Aspects of Rationality and Knowledge, TARK 17 (Electronic Proceedings in Theoretical Computer Science, Vol. 251). Open Publishing Association, Waterloo, Australia, 134150. John J. Bartholdi III, Craig A. Tovey, and Michael A. Trick. 1992. How hard is it to control an election? Mathematical and Computer Modelling 16, 8 (1992), 2740. 2020. Vincent Conitzer, Tuomas Sandholm, and Jrme Lang. 2007. When Are Elections with Few Candidates Hard to Manipulate? Journal of the ACM 54, 3, Article 14 (2007), 33 pages. Recurrent Quantum Neural NetInon Neural Curran Associates. Johannes works. formation
id: 91a25e8c9c31d703c452b70028aa4fdd - page: 5