Strategies for Quantum Races

Authors Troy Lee, Maharshi Ray, Miklos Santha



PDF
Thumbnail PDF

File

LIPIcs.ITCS.2019.51.pdf
  • Filesize: 492 kB
  • 21 pages

Document Identifiers

Author Details

Troy Lee
  • Centre for Quantum Software and Information, School of Software, Faculty of Engineering and Information Technology, University of Technology Sydney, Australia
Maharshi Ray
  • Centre for Quantum Technologies, National University of Singapore, Singapore
Miklos Santha
  • IRIF, Univ. Paris Diderot, CNRS, 75205 Paris, France
  • and, Centre for Quantum Technologies and MajuLab, National University of Singapore, Singapore 117543

Cite AsGet BibTex

Troy Lee, Maharshi Ray, and Miklos Santha. Strategies for Quantum Races. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 51:1-51:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ITCS.2019.51

Abstract

We initiate the study of quantum races, games where two or more quantum computers compete to solve a computational problem. While the problem of dueling algorithms has been studied for classical deterministic algorithms [Immorlica et al., 2011], the quantum case presents additional sources of uncertainty for the players. The foremost among these is that players do not know if they have solved the problem until they measure their quantum state. This question of "when to measure?" presents a very interesting strategic problem. We develop a game-theoretic model of a multiplayer quantum race, and find an approximate Nash equilibrium where all players play the same strategy. In the two-party case, we further show that this strategy is nearly optimal in terms of payoff among all symmetric Nash equilibria. A key role in our analysis of quantum races is played by a more tractable version of the game where there is no payout on a tie; for such races we completely characterize the Nash equilibria in the two-party case. One application of our results is to the stability of the Bitcoin protocol when mining is done by quantum computers. Bitcoin mining is a race to solve a computational search problem, with the winner gaining the right to create a new block. Our results inform the strategies that eventual quantum miners should use, and also indicate that the collision probability - the probability that two miners find a new block at the same time - would not be too high in the case of quantum miners. Such collisions are undesirable as they lead to forking of the Bitcoin blockchain.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithmic game theory
Keywords
  • Game theory
  • Bitcoin mining
  • Quantum computing
  • Convex optimization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Divesh Aggarwal, Gavin Brennen, Troy Lee, Miklos Santha, and Marco Tomamichel. Quantum attacks on Bitcoin and how to prevent against them. Technical report, arXiv, 2017. URL: http://arxiv.org/abs/1710.10377.
  2. Adam Back. Hashcash - a denial of service counter-measure, 2002. Available at: URL: http://www.hashcash.org/papers/hashcash.pdf.
  3. Alex Biryukov and Dmitry Khovratovich. Equihash: Asymmetric proof-of-work based on the generalized birthday problem. Ledger, 2:1-30, 2017. Google Scholar
  4. Bitmain. Bitmain Antminer S9. https://shop.bitmain.com/antminer_s9_asic_bitcoin_miner.html, 2018. Accessed 2018-02-16.
  5. Vitalik Buterin. Bitcoin is not quantum safe, and how we can fix it when needed. https://bitcoinmagazine.com/articles/bitcoin-is-not-quantum-safe-and-how-we-can-fix-1375242150/, 2013.
  6. Miguel Castro and Barbara Liskov. Practical Byzantine Fault Tolerance. In Third Symposium on Operating Systems Design and Implementation, 1999. Google Scholar
  7. Catalin Dohotaru and Peter Høyer. Exact quantum lower bound for Grover’s problem. Technical report, arXiv, 2008. URL: http://arxiv.org/abs/0810.3647.
  8. William S. Dorn. Duality in quadratic programming. Quarterly of applied mathematics, 18(2):155-162, 1960. Google Scholar
  9. Ittay Eyal and Emin Gün Sirer. Majority is not enough: Bitcoin mining is vulnerable. In 18th International Conference on Financial Cryptography and Data Security, 2014. Google Scholar
  10. Arthur Gervais, Ghassan Karame, Karl Wüst, Vasileios Glykantzis, Hubert Ritzdorf, and Srdjan Capkun. On the security and performance of proof of work blockchains. In Proceedings of the 2016 ACM SIGSAC Conference on Compute and Communications Security (CCS'16), pages 3-16, 2016. Google Scholar
  11. Lov K. Grover. A Fast Quantum Mechanical Algorithm for Database Search. In Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing, STOC '96, pages 212-219, New York, NY, USA, 1996. ACM. URL: http://dx.doi.org/10.1145/237814.237866.
  12. Nicole Immorlica, Adam Tauman Kalai, Brendan Lucier, Ankur Moitra, Andrew Postlewaite, and Moshe Tennenholtz. Dueling algorithms. In Proceedings of the forty-third annual ACM symposium on theory of computing (STOC'11), pages 215-224, 2011. Google Scholar
  13. Aggelos Kiayias, Alexander Russell, Bernardo David, and Roman Oliynykov. Ouroboros: A provably secure proof-of-stake blockchain protocol. In CRYPTO, pages 357-388, 2017. Google Scholar
  14. T. Lee, M. Ray, and M. Santha. Strategies for quantum races. ArXiv e-prints, September 2018. URL: http://arxiv.org/abs/1809.03671.
  15. Olvi L. Mangasarian and H. Stone. Two-person nonzero-sum games and quadratic programming. Journal of mathematical analysis and applications, 9:348-355, 1964. Google Scholar
  16. Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system, 2009. Available at: URL: http://www.bitcoin.org/pdf.
  17. John F. Nash. Non-cooperative Games. Annals of Mathematics, 54(2):286-295, 1951. Google Scholar
  18. Or Sattath. On the insecurity of quantum Bitcoin mining. Technical report, arXiv, 2018. Appeared in QCRYPT 2018. URL: http://arxiv.org/abs/1804.08118.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail