Document Open Access Logo

Quantum Hedging in Two-Round Prover-Verifier Interactions

Authors Srinivasan Arunachalam, Abel Molina, Vincent Russo

PDF
Thumbnail PDF

File

LIPIcs.TQC.2017.5.pdf
  • Filesize: 0.66 MB
  • 30 pages

Document Identifiers

Author Details

Srinivasan Arunachalam
Abel Molina
Vincent Russo

Cite AsGet BibTex

Srinivasan Arunachalam, Abel Molina, and Vincent Russo. Quantum Hedging in Two-Round Prover-Verifier Interactions. In 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 73, pp. 5:1-5:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.TQC.2017.5

Abstract

We consider the problem of a particular kind of quantum correlation that arises in some two-party games. In these games, one player is presented with a question they must answer, yielding an outcome of either "win" or "lose". Molina and Watrous previously studied such a game that exhibited a perfect form of hedging, where the risk of losing a first game can completely offset the corresponding risk for a second game. This is a non-classical quantum phenomenon, and establishes the impossibility of performing strong error-reduction for quantum interactive proof systems by parallel repetition, unlike for classical interactive proof systems. We take a step in this article towards a better understanding of the hedging phenomenon by giving a complete characterization of when perfect hedging is possible for a natural generalization of the game in the prior work of Molina and Watrous. Exploring in a different direction the subject of quantum hedging, and motivated by implementation concerns regarding loss-tolerance, we also consider a variation of the protocol where the player who receives the question can choose to restart the game rather than return an answer. We show that in this setting there is no possible hedging for any game played with state spaces corresponding to finite-dimensional complex Euclidean spaces.
Keywords
  • prover-verifier interactions
  • parallel repetition
  • quantum information

Metrics

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

References

  1. Scott Aaronson. Quantum computing, postselection, and probabilistic polynomial-time. In Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, volume 461, pages 3473-3482. The Royal Society, 2005. Google Scholar
  2. Nati Aharon, Serge Massar, and Jonathan Silman. Family of loss-tolerant quantum coin-flipping protocols. Physical Review A, 82(5):052307, 2010. Google Scholar
  3. Srinivasan Arunachalam, Abel Molina, and Vincent Russo. Software for implementing some of the semidefinite programs in this paper. Available at https://bitbucket.org/vprusso/quantum-hedging, 2013.
  4. Koenraad Audenaert and Bart De Moor. Optimizing completely positive maps using semidefinite programming. Physical Review A, 65(3):030302, 2002. Google Scholar
  5. Somshubhro Bandyopadhyay, Rahul Jain, Jonathan Oppenheim, and Christopher Perry. Conclusive exclusion of quantum states. Physical Review A, 89(2):022336, 2014. Google Scholar
  6. John Bell. On the Einstein-Podolsky-Rosen paradox. Physics, 1(3):195-200, 1964. Google Scholar
  7. Fernando GSL Brandão, Ravishankar Ramanathan, Andrzej Grudka, Karol Horodecki, Michał Horodecki, Paweł Horodecki, Tomasz Szarek, and Hanna Wojewódka. Realistic noise-tolerant randomness amplification using finite number of devices. Nature communications, 7, 2016. Google Scholar
  8. Mark Braverman and Ankit Garg. Small value parallel repetition for general games. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, pages 335-340. ACM, 2015. Google Scholar
  9. Harry Buhrman, Oded Regev, Giannicola Scarpa, and Ronald de Wolf. Near-optimal and explicit bell inequality violations. Theory of Computing, 8(1):623-645, 2012. Google Scholar
  10. Nicolas Cerf and Jaromir Fiurasek. Optical quantum cloning. Progress in Optics, 49:455, 2006. Google Scholar
  11. Andrew M Childs, Andrew J Landahl, and Pablo A Parrilo. Quantum algorithms for the ordered search problem via semidefinite programming. Physical Review A, 75(3):032335, 2007. Google Scholar
  12. Matthias Christandl, Norbert Schuch, and Andreas Winter. Highly entangled states with almost no secrecy. Physical Review Letters, 2010. Google Scholar
  13. John Clauser, Michael Horne, Abner Shimony, and Richard Holt. Proposed experiment to test local hidden-variable theories. Physical Review Letters, 1969. Google Scholar
  14. Richard Cleve, Peter Hoyer, Benjamin Toner, and John Watrous. Consequences and limits of nonlocal strategies. In Computational Complexity, 2004. Proceedings. 19th IEEE Annual Conference on, pages 236-249. IEEE, 2004. Google Scholar
  15. Tom Cooney, Marius Junge, Carlos Palazuelos, and David Pérez-García. Rank-one quantum games. Computational Complexity, 24(1):133-196, 2015. Google Scholar
  16. Uriel Feige. On the success probability of the two provers in one-round proof systems. In Structure in Complexity Theory Conference, 1991., Proceedings of the Sixth Annual, pages 116-123. IEEE, 1991. Google Scholar
  17. Jaromír Fiurášek. Optimal probabilistic cloning and purification of quantum states. Physical Review A, 70(3):032308, 2004. Google Scholar
  18. Lance Jeremy Fortnow. Complexity-theoretic aspects of interactive proof systems. PhD thesis, Massachusetts Institute of Technology, 1989. Google Scholar
  19. Karin Gatermann and Pablo A Parrilo. Symmetry groups, semidefinite programs, and sums of squares. Journal of Pure and Applied Algebra, 192(1):95-128, 2004. Google Scholar
  20. Michael Grant, Stephen Boyd, and Yinyu Ye. CVX: Matlab software for disciplined convex programming. http://cvxr.com/cvx/, 2008.
  21. Gus Gutoski. Quantum strategies and local operations. arXiv preprint arXiv:1003.0038, 2010. Google Scholar
  22. Gus Gutoski and John Watrous. Toward a general theory of quantum games. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 565-574. ACM, 2007. Google Scholar
  23. Patrick Hayden, Kevin Milner, and Mark Wilde. Two-message quantum interactive proofs and the quantum separability problem. Quantum Information & Computation, 14(5&6):384-416, 2014. Google Scholar
  24. Thomas Holenstein. Parallel repetition: simplifications and the no-signaling case. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 411-419. ACM, 2007. Google Scholar
  25. Rahul Jain, Sarvagya Upadhyay, and John Watrous. Two-message quantum interactive proofs are in PSPACE. In 50th Annual IEEE Symposium on Foundations of Computer Science, pages 534-543. IEEE, 2009. Google Scholar
  26. Nathaniel Johnston. QETLAB: MATLAB Software for quantum entanglement. Available at http://www.qetlab.com/, 2015.
  27. Hari Krovi, Saikat Guha, Zachary Dutton, and Marcus P da Silva. Optimal measurements for symmetric quantum states with applications to optical communication. Physical Review A, 92(6):062333, 2015. Google Scholar
  28. Urmila Mahadev and Ronald de Wolf. Rational approximations and quantum algorithms with postselection. Quantum Information &Computation, 15(3&4):295-307, 2015. Google Scholar
  29. N David Mermin. Simple unified form for the major no-hidden-variables theorems. Physical Review Letters, 65(27):3373, 1990. Google Scholar
  30. Abel Molina and John Watrous. Hedging bets with correlated quantum strategies. In Proc. R. Soc. A. The Royal Society, 2012. Google Scholar
  31. Fernando Pastawski, Norman Y Yao, Liang Jiang, Mikhail D Lukin, and J Ignacio Cirac. Unforgeable noise-tolerant quantum tokens. Proceedings of the National Academy of Sciences, 109(40):16079-16082, 2012. Google Scholar
  32. Asher Peres. Incompatible results of quantum measurements. Physics Letters A, 151(3-4):107-108, 1990. Google Scholar
  33. Matthew Pusey, Jonathan Barrett, and Terry Rudolph. On the reality of the quantum state. Nature Physics, 2012. Google Scholar
  34. Ran Raz. A parallel repetition theorem. SIAM Journal on Computing, 27(3):763-803, 1998. Google Scholar
  35. Ran Raz. Quantum information and the PCP theorem. In 46th Annual IEEE Symposium on Foundations of Computer Science., pages 459-468. IEEE, 2005. Google Scholar
  36. Oded Regev. Bell violations through independent bases games. Quantum Information &Computation, 12(1-2):9-20, 2012. Google Scholar
  37. Oksana Scegulnaja-Dubrovska, Lelde Lāce, and Rūsiņš Freivalds. Postselection finite quantum automata. In International Conference on Unconventional Computation, pages 115-126. Springer, 2010. Google Scholar
  38. Devin Smith. Personal communication, 2011. Google Scholar
  39. Kiyoshi Tamaki, Marcos Curty, Go Kato, Hoi-Kwong Lo, and Koji Azuma. Loss-tolerant quantum cryptography with imperfect sources. Physical Review A, 90(5):052314, 2014. Google Scholar
  40. John Watrous. URL: https://cs.uwaterloo.ca/~watrous/CS766/ProblemSets/solutions.2.pdf.
  41. John Watrous. Theory of quantum information lecture notes. https://cs.uwaterloo.ca/~watrous/LectureNotes.html, 2011.
  42. Stephanie Wehner. Entanglement in interactive proof systems with binary answers. In STACS 2006, pages 162-171. Springer, 2006. Google Scholar
  43. Abuzer Yakaryilmaz and AC Say. Probabilistic and quantum finite automata with postselection. arXiv preprint arXiv:1102.0666, 2011. Google Scholar
  44. Sheng Zhang and Yuexin Zhang. Quantum coin flipping secure against channel noises. Physical Review A, 92(2):022313, 2015. Google Scholar
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact