Fidelity of quantum strategies with applications to cryptography

Gus Gutoski; Ansis Rosmanis; Jamie Sikora

doi:10.22331/q-2018-09-03-89

Fidelity of quantum strategies with applications to cryptography

Gus Gutoski¹, Ansis Rosmanis^2,3, and Jamie Sikora^2,4

¹Perimeter Institute for Theoretical Physics, ON, Canada
²Centre for Quantum Technologies, National University of Singapore, Singapore
³School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore
⁴MajuLab, CNRS-UNS-NUS-NTU International Joint Research Unit, UMI 3654, Singapore

Published:	2018-09-03, volume 2, page 89
Eprint:	arXiv:1704.04033v2
Doi:	https://doi.org/10.22331/q-2018-09-03-89
Citation:	Quantum 2, 89 (2018).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

We introduce a definition of the fidelity function for multi-round quantum strategies, which we call the $\textit{strategy fidelity}$, that is a generalization of the fidelity function for quantum states. We provide many properties of the strategy fidelity including a Fuchs-van de Graaf relationship with the strategy norm. We also provide a general monotinicity result for both the strategy fidelity and strategy norm under the actions of strategy-to-strategy linear maps. We illustrate an operational interpretation of the strategy fidelity in the spirit of Uhlmann's Theorem and discuss its application to the security analysis of quantum protocols for interactive cryptographic tasks such as bit-commitment and oblivious string transfer. Our analysis is general in the sense that the actions of the protocol need not be fully specified, which is in stark contrast to most other security proofs. Lastly, we provide a semidefinite programming formulation of the strategy fidelity.

► BibTeX data

@article{Gutoski2018fidelityofquantum,
  doi = {10.22331/q-2018-09-03-89},
  url = {https://doi.org/10.22331/q-2018-09-03-89},
  title = {Fidelity of quantum strategies with applications to cryptography},
  author = {Gutoski, Gus and Rosmanis, Ansis and Sikora, Jamie},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {2},
  pages = {89},
  month = sep,
  year = {2018}
}

► References

[1] Andris Ambainis, Harry Buhrman, Yevgeniy Dodis, and Hein Röhrig. Multiparty quantum coin flipping. In Proceedings of the 19th IEEE Annual Conference on Computational Complexity, pages 250–259. IEEE Computer Society, 2004. DOI: 10.1109/CCC.2004.1313848.
https://doi.org/10.1109/CCC.2004.1313848

[2] Andris Ambainis. A new protocol and lower bounds for quantum coin flipping. In Proceedings of 33rd Annual ACM Symposium on the Theory of Computing, pages 134 – 142. ACM, 2001. DOI: 10.1145/380752.380788.
https://doi.org/10.1145/380752.380788

[3] Charles Bennett and Gilles Brassard. Quantum cryptography: Public key distribution and coin tossing. In Proceedings of the IEEE International Conference on Computers, Systems, and Signal Processing, pages 175–179. IEEE Computer Society, 1984.

[4] Howard Barnum, Carlton M. Caves, Christopher A. Fuchs, Richard Jozsa, and Benjamin Schumacher. Noncommuting mixed states cannot be broadcast. Physical Review Letters, 76:2818–2821, 1996. DOI: 10.1103/PhysRevLett.76.2818. arXiv:quant-ph/9511010.
https://doi.org/10.1103/PhysRevLett.76.2818
arXiv:quant-ph/9511010

[5] Viacheslav P. Belavkin, Giacomo Mauro D'Ariano, and Maxim Raginsky. Operational distance and fidelity for quantum channels. Journal of Mathematical Physics, 46(6):062106, 2005. DOI: 10.1063/1.1904510. arXiv:quant-ph/0408159.
https://doi.org/10.1063/1.1904510
arXiv:quant-ph/0408159

[6] Giulio Chiribella, Giacomo Mauro D'Ariano, and Paolo Perinotti. Transforming quantum operations: Quantum supermaps. Europhysics Letters, 83(3):30004, 2008. DOI: 10.1209/0295-5075/83/30004. arXiv:0804.0180 [quant-ph].
https://doi.org/10.1209/0295-5075/83/30004
arXiv:0804.0180

[7] Giulio Chiribella, Giacomo Mauro D'Ariano, and Paolo Perinotti. Memory effects in quantum channel discrimination. Physical Review Letters, 101:180501, 2008. DOI: 10.1103/PhysRevLett.101.180501. arXiv:0803.3237 [quant-ph].
https://doi.org/10.1103/PhysRevLett.101.180501
arXiv:0803.3237

[8] Giulio Chiribella, Giacomo Mauro D'Ariano, and Paolo Perinotti. Theoretical framework for quantum networks. Physical Review A, 80(2):022339, 2009. DOI: 10.1103/PhysRevA.80.022339. arXiv:0904.4483 [quant-ph].
https://doi.org/10.1103/PhysRevA.80.022339
arXiv:0904.4483

[9] Giulio Chiribella, Giacomo Mauro D'Ariano, Paolo Perinotti, Dirk Schlingemann, and Reinhard F. Werner. A short impossibility proof of quantum bit commitment. Physics Letters A, 377(15):1076–1087, 2013. DOI: 10.1016/j.physleta.2013.02.045. arXiv:0905.3801v1 [quant-ph].
https://doi.org/10.1016/j.physleta.2013.02.045
arXiv:0905.3801v1

[10] André Chailloux, Gus Gutoski, and Jamie Sikora. Optimal bounds for semi-honest quantum oblivious transfer. Chicago Journal of Theoretical Computer Science, (13), 2016. DOI: 10.4086/cjtcs.2016.013.
https://doi.org/10.4086/cjtcs.2016.013

[11] André Chailloux and Iordanis Kerenidis. Optimal quantum strong coin flipping. In Proceedings of the 50th IEEE Symposium on Foundations of Computer Science, FOCS 2009, pages 527–533, 2009. DOI: 10.1109/FOCS.2009.71. arXiv:0904.1511 [quant-ph].
https://doi.org/10.1109/FOCS.2009.71
arXiv:0904.1511

[12] André Chailloux and Iordanis Kerenidis. Optimal bounds for quantum bit commitment. In Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2011, pages 354–362, 2011. DOI: 10.1109/FOCS.2011.42. arXiv:1102.1678 [quant-ph].
https://doi.org/10.1109/FOCS.2011.42
arXiv:1102.1678

[13] André Chailloux, Iordanis Kerenidis, and Jamie Sikora. Lower bounds for quantum oblivious transfer. Quantum Information and Computation, 13(1&2):158–177, 2013. arXiv:1007.1875 [quant-ph].
arXiv:1007.1875

[14] André Chailloux, Iordanis Kerenidis, and Jamie Sikora. Strong connections between quantum encodings, nonlocality, and quantum cryptography. Phys. Rev. A, 89:022334, 2014. DOI: 10.1103/PhysRevA.89.022334. arXiv:1304.0983 [quant-ph].
https://doi.org/10.1103/PhysRevA.89.022334
arXiv:1304.0983

[15] Giacomo Mauro D'Ariano, Dennis Kretschmann, Dirk Schlingemann, and Reinhard F. Werner. Reexamination of quantum bit commitment: The possible and the impossible. Phys. Rev. A, 76:032328, 2007. DOI: 10.1103/PhysRevA.76.032328 arXiv:0605224 [quant-ph].
https://doi.org/10.1103/PhysRevA.76.032328
arXiv:0605224

[16] Christopher A. Fuchs and Jeroen van de Graaf. Cryptographic distinguishability measures for quantum mechanical states. IEEE Transactions on Information Theory 45(4):1216–1227, 1999. DOI: 10.1109/18.761271.
https://doi.org/10.1109/18.761271

[17] Gus Gutoski. Quantum strategies and local operations. PhD thesis, University of Waterloo, 2009. arXiv:1003.0038 [quant-ph].
arXiv:1003.0038

[18] Gus Gutoski. On a measure of distance for quantum strategies. Journal of Mathematical Physics, 53(3):032202, 2012. DOI: 10.1063/1.3693621. arXiv:1008.4636 [quant-ph].
https://doi.org/10.1063/1.3693621
arXiv:1008.4636

[19] Gus Gutoski and John Watrous. Toward a general theory of quantum games. In Proceedings of the 39th ACM Symposium on Theory of Computing (STOC 2007), pages 565–574, 2007. DOI: 10.1145/1250790.1250873. arXiv:quant-ph/0611234.
https://doi.org/10.1145/1250790.1250873
arXiv:quant-ph/0611234

[20] Alexei Kitaev. Quantum coin-flipping. Presentation at the 6th Workshop on Quantum Information Processing (QIP 2003), 2002.

[21] Iordanis Kerenidis and Ashwin Nayak. Weak coin flipping with small bias. Information Processing Letters, 89(3):131–135, 2004. DOI: 10.1016/j.ipl.2003.07.007. arXiv:quant-ph/0206121.
https://doi.org/10.1016/j.ipl.2003.07.007
arXiv:quant-ph/0206121

[22] Hoi-Kwong Lo and Hoi Fung Chau. Is quantum bit commitment really possible? Physical Review Letters, 78(17):3410–3413, 1997. DOI: 10.1103/PhysRevLett.78.3410.
https://doi.org/10.1103/PhysRevLett.78.3410

[23] Hoi-Kwong Lo and Hoi Fung Chau. Why quantum bit commitment and ideal quantum coin tossing are impossible. Physica D: Nonlinear Phenomena, 120(1–2):177–187, September 1998. Proceedings of the Fourth Workshop on Physics and Consumption. DOI: 10.1016/S0167-2789(98)00053-0.
https://doi.org/10.1016/S0167-2789(98)00053-0

[24] Dominic Mayers. Unconditionally secure quantum bit commitment is impossible. Physical Review Letters, 78(17):3414–3417, 1997. DOI: 10.1103/PhysRevLett.78.3414.
https://doi.org/10.1103/PhysRevLett.78.3414

[25] Ashwin Nayak and Peter Shor. Bit-commitment based quantum coin flipping. Physical Review A, 67(1):012304, 2003. DOI: 10.1103/PhysRevA.67.012304. arXiv:quant-ph/0206123.
https://doi.org/10.1103/PhysRevA.67.012304
arXiv:quant-ph/0206123

[26] Ashwin Nayak, Jamie Sikora, and Levent Tunçel. Quantum and classical coin-flipping protocols based on bit-commitment and their point games. arXiv:1504.04217.
arXiv:1504.04217

[27] Ashwin Nayak, Jamie Sikora, and Levent Tunçel. A search for quantum coin-flipping protocols using optimization techniques. Mathematical Programming, 156(1):581–613, 2016. DOI: 10.1007/s10107-015-0909-y.
https://doi.org/10.1007/s10107-015-0909-y

[28] Michael A. Nielsen and Isaac Chuang. Quantum Computation and Quantum Information. Cambridge University Press, Cambridge, 2000.

[29] R. Tyrrell Rockafellar. Convex Analysis. Princeton University Press, 1970.

[30] M. B. Ruskai. Beyond strong subadditivity? Improved bounds on the contraction of generalized relative entropy. Reviews in Mathematical Physics, 6:1147–1161, 1994. DOI: 10.1142/S0129055X94000407.
https://doi.org/10.1142/S0129055X94000407

[31] Jamie Sikora. Simple, near-optimal quantum protocols for die-rolling. Cryptography, 1(2), 11, 2017. DOI: 10.3390/cryptography1020011.
https://doi.org/10.3390/cryptography1020011

[32] Robert W. Spekkens and Terence Rudolph. Degrees of concealment and bindingness in quantum bit commitment protocols. Physical Review A, 65:012310, 2001. DOI: 10.1103/PhysRevA.65.012310.
https://doi.org/10.1103/PhysRevA.65.012310

[33] A. Uhlmann. The ``transition probability'' in the state space of a *-algebra. Reports on Mathematical Physics, 9(2):273–279, 1976. DOI: 10.1016/0034-4877(76)90060-4.
https://doi.org/10.1016/0034-4877(76)90060-4

[34] John Watrous. Semidefinite programs for completely bounded norms. Theory of Computing, 5:217–238, 2009. DOI: 10.4086/toc.2009.v005a011. arXiv:0901.4709v2 [quant-ph].
https://doi.org/10.4086/toc.2009.v005a011
arXiv:0901.4709v2

[35] John Watrous. Simpler semidefinite programs for completely bounded norms. Chicago Journal of Theoretical Computer Science, (8), 2013. DOI: 10.4086/cjtcs.2013.008.
https://doi.org/10.4086/cjtcs.2013.008

[36] Stephen Wiesner. Conjugate coding. SIGACT News, 15(1):78–88, January 1983. DOI: 10.1145/1008908.1008920.
https://doi.org/10.1145/1008908.1008920

Cited by

[1] Guang Ping He, "An Optical Implementation of Quantum Bit Commitment Using Infinite-Dimensional Systems", Applied Sciences 13 13, 7692 (2023).

[2] Yuxiang Yang, Renato Renner, and Giulio Chiribella, "Energy requirement for implementing unitary gates on energy-unbounded systems", Journal of Physics A: Mathematical and Theoretical 55 49, 494003 (2022).

[3] Gilad Gour and Carlo Maria Scandolo, "Entanglement of a bipartite channel", Physical Review A 103 6, 062422 (2021).

[4] Vishal Katariya and Mark M. Wilde, "Evaluating the advantage of adaptive strategies for quantum channel distinguishability", Physical Review A 104 5, 052406 (2021).

[5] Gilad Gour and Carlo Maria Scandolo, "Dynamical Entanglement", Physical Review Letters 125 18, 180505 (2020).

[6] Mark Girard, Martin Plávala, and Jamie Sikora, "Jordan products of quantum channels and their compatibility", Nature Communications 12 1, 2129 (2021).

[7] Manuel B. Santos, Paulo Mateus, and Armando N. Pinto, "Quantum Oblivious Transfer: A Short Review", Entropy 24 7, 945 (2022).

[8] Graeme D. Berk, Andrew J. P. Garner, Benjamin Yadin, Kavan Modi, and Felix A. Pollock, "Resource theories of multi-time processes: A window into quantum non-Markovianity", Quantum 5, 435 (2021).

[9] Vikesh Siddhu and Sridhar Tayur, Tutorials in Operations Research: Emerging and Impactful Topics in Operations 59 (2022) ISBN:978-0-9906153-7-8.

[10] Xin Wang and Mark M. Wilde, "Resource theory of asymmetric distinguishability for quantum channels", Physical Review Research 1 3, 033169 (2019).

[11] Soorya Rethinasamy, Rochisha Agarwal, Kunal Sharma, and Mark M. Wilde, "Estimating distinguishability measures on quantum computers", Physical Review A 108 1, 012409 (2023).

[12] Simon Milz and Kavan Modi, "Quantum Stochastic Processes and Quantum non-Markovian Phenomena", PRX Quantum 2 3, 030201 (2021).

[13] Saiful Islam Salim, Adnan Quaium, Sriram Chellappan, and A. B. M. Alim Al Islam, GLOBECOM 2020 - 2020 IEEE Global Communications Conference 1 (2020) ISBN:978-1-7281-8298-8.

[14] Giulio Chiribella, Yuxiang Yang, and Renato Renner, "Fundamental Energy Requirement of Reversible Quantum Operations", Physical Review X 11 2, 021014 (2021).

[15] Graeme D. Berk, Andrew J. P. Garner, Benjamin Yadin, Kavan Modi, and Felix A. Pollock, "Resource theories of multi-time processes: A window into quantum non-Markovianity", arXiv:1907.07003, (2019).

[16] Qisheng Wang and Zhicheng Zhang, "Fast Quantum Algorithms for Trace Distance Estimation", arXiv:2301.06783, (2023).

[17] Guang Ping He, "Unconditionally secure quantum bit commitment based on the uncertainty principle", Proceedings of the Royal Society of London Series A 475 2222, 20180543 (2019).

The above citations are from Crossref's cited-by service (last updated successfully 2023-11-29 19:39:38) and SAO/NASA ADS (last updated successfully 2023-11-29 19:39:39). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.