Fidelity of quantum strategies with applications to cryptography

Gus Gutoski1, Ansis Rosmanis2,3, and Jamie Sikora2,4

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

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

► 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 (beta)

Crossref's cited-by service has no data on citing works. Unfortunately not all publishers provide suitable citation data.