1 Search Results for "Ray, Maharshi"

Document

DOI: 10.4230/LIPIcs.ITCS.2019.51

Strategies for Quantum Races

Authors: Troy Lee, Maharshi Ray, and Miklos Santha

Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{lee_et_al:LIPIcs.ITCS.2019.51,
  author =	{Lee, Troy and Ray, Maharshi and Santha, Miklos},
  title =	{{Strategies for Quantum Races}},
  booktitle =	{10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
  pages =	{51:1--51:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{124},
  editor =	{Blum, Avrim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.51},
  URN =		{urn:nbn:de:0030-drops-101446},
  doi =		{10.4230/LIPIcs.ITCS.2019.51},
  annote =	{Keywords: Game theory, Bitcoin mining, Quantum computing, Convex optimization}
}

Refine by Author
1 Lee, Troy
1 Ray, Maharshi
1 Santha, Miklos

Refine by Classification
1 Theory of computation → Algorithmic game theory

Refine by Keyword
1 Bitcoin mining
1 Convex optimization
1 Game theory
1 Quantum computing

Refine by Type
1 document

Refine by Publication Year
1 2019

1 Search Results for "Ray, Maharshi"

Strategies for Quantum Races

Abstract

Cite as

Thanks for your feedback!

Could not send message