Accelerating Voting by Quantum Computation

• URL: http://arxiv.org/abs/2301.02995v4
• Date: Thu, 8 Jun 2023 21:42:21 GMT
• Title: Accelerating Voting by Quantum Computation
• Authors: Ao Liu, Qishen Han, Lirong Xia, Nengkun Yu
• Abstract summary: We propose a quantum-accelerated voting algorithm that can be applied to any anonymous voting rule. Our algorithm outputs the correct winner with high probability in $Thetaleft(fracntextMOVright)$ time.
• Score: 35.03314687289671
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 $\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.

Related papers

• Space-Efficient Quantum Error Reduction without log Factors [50.10645865330582]
  We present a new highly simplified construction of a purifier, that can be understood as a weighted walk on a line similar to a random walk interpretation of majority voting. Our purifier has exponentially better space complexity than the previous one, and quadratically better dependence on the soundness-completeness gap of the algorithm being purified.
  arXiv  Detail & Related papers  (2025-02-13T12:04:39Z)
• Efficient Lower Bounding of Single Transferable Vote Election Margins [56.12949230611067]
  Single transferable vote (STV) is a system of preferential proportional voting employed in multi-seat elections. The margin of victory, or simply margin, is the smallest number of ballots that, if manipulated, can alter the set of winners. Lower bounds on the margin can also be used for this purpose, in cases where exact margins are difficult to compute.
  arXiv  Detail & Related papers  (2025-01-24T13:39:23Z)
• Simple and Provable Scaling Laws for the Test-Time Compute of Large Language Models [70.07661254213181]
  We propose two principled algorithms for the test-time compute of large language models. We prove theoretically that the failure probability of one algorithm decays to zero exponentially as its test-time compute grows.
  arXiv  Detail & Related papers  (2024-11-29T05:29:47Z)
• Quantum-Enhanced Secure Approval Voting Protocol [0.0]
  This paper introduces a quantum voting protocol, a blend of quantum principles (entanglement and superposition), blockchain technology, and digital signatures. The protocol is tested on IBM quantum hardware, achieving impressively low error rates of just 1.17% in a four-candidate election.
  arXiv  Detail & Related papers  (2024-06-28T08:20:25Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Obvious Manipulability of Voting Rules [105.35249497503527]
  The Gibbard-Satterthwaite theorem states that no unanimous and non-dictatorial voting rule is strategyproof. We revisit voting rules and consider a weaker notion of strategyproofness called not obvious manipulability.
  arXiv  Detail & Related papers  (2021-11-03T02:41:48Z)
• An algorithm for a fairer and better voting system [0.0]
  This article is about a novel, better ranked voting system that aims to solve the problem of finding the best candidate to represent the voters. We have the source code on GitHub, for making realistic simulations of elections, based on artificial intelligence. We have convincing evidence that our algorithm is better than Instant-Runoff Voting, Preferential Block Voting, Single Transferable Vote, and First Past The Post.
  arXiv  Detail & Related papers  (2021-10-13T22:34:49Z)
• Fine-Grained Complexity and Algorithms for the Schulze Voting Method [9.399840807973545]
  We study computational aspects of a well-known single-winner voting rule called the Schulze method. Our paper is the first to bring fine-grained complexity into the field of computational social choice.
  arXiv  Detail & Related papers  (2021-03-05T22:27:36Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.