Certifying optimality for convex quantum channel optimization problems

Bryan Coutts; Mark Girard; John Watrous

doi:10.22331/q-2021-05-01-448

Certifying optimality for convex quantum channel optimization problems

Bryan Coutts^1,2, Mark Girard¹, and John Watrous^1,2,3

¹Institute for Quantum Computing, University of Waterloo, Canada
²School of Computer Science, University of Waterloo, Canada
³Canadian Institute for Advanced Research, Toronto, Canada

Published:	2021-05-01, volume 5, page 448
Eprint:	arXiv:1810.13295v4
Doi:	https://doi.org/10.22331/q-2021-05-01-448
Citation:	Quantum 5, 448 (2021).

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

Abstract

We identify necessary and sufficient conditions for a quantum channel to be optimal for any convex optimization problem in which the optimization is taken over the set of all quantum channels of a fixed size. Optimality conditions for convex optimization problems over the set of all quantum measurements of a given system having a fixed number of measurement outcomes are obtained as a special case. In the case of linear objective functions for measurement optimization problems, our conditions reduce to the well-known Holevo-Yuen-Kennedy-Lax measurement optimality conditions. We illustrate how our conditions can be applied to various state transformation problems having non-linear objective functions based on the fidelity, trace distance, and quantum relative entropy.

► BibTeX data

@article{Coutts2021certifying,
  doi = {10.22331/q-2021-05-01-448},
  url = {https://doi.org/10.22331/q-2021-05-01-448},
  title = {Certifying optimality for convex quantum channel optimization problems},
  author = {Coutts, Bryan and Girard, Mark and Watrous, John},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {5},
  pages = {448},
  month = may,
  year = {2021}
}

► References

[1] Scott Aaronson, Edward Farhi, David Gosset, Avinatan Hassidim, Jonathan Kelner, and Andrew Lutomirski. Quantum money. Communications of the ACM, 55 (8): 84–92, 2012. 10.1145/2240236.2240258.
https://doi.org/10.1145/2240236.2240258

[2] Dave Bacon, Andrew Childs, and Wim van Dam. From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, pages 469–478, 2005. 10.1109/SFCS.2005.38.
https://doi.org/10.1109/SFCS.2005.38

[3] Stephen Barnett and Sarah Croke. Quantum state discrimination. Advances in Optics and Photonics, 1 (2): 238–278, 2009. 10.1364/AOP.1.000238.
https://doi.org/10.1364/AOP.1.000238

[4] Mario Berta and Marco Tomamichel. The fidelity of recovery is multiplicative. IEEE Transactions on Information Theory, 62 (4): 1758–1763, 2016. 10.1109/TIT.2016.2527683.
https://doi.org/10.1109/TIT.2016.2527683

[5] Mario Berta, Omar Fawzi, and Marco Tomamichel. On variational expressions for quantum relative entropies. Letters in Mathematical Physics, 107 (12): 2239–2265, 2017. 10.1007/s11005-017-0990-7.
https://doi.org/10.1007/s11005-017-0990-7

[6] Rajendra Bhatia. Matrix Analysis, volume 169 of Graduate Texts in Mathematics. Springer, 1997. 10.1007/978-1-4612-0653-8.
https://doi.org/10.1007/978-1-4612-0653-8

[7] Rajendra Bhatia. Positive Definite Matrices, volume 24 of Princeton Series in Applied Mathematics. Princeton University Press, 2007. 10.1515/9781400827787.
https://doi.org/10.1515/9781400827787

[8] Jonathan Borwein and Adrian Lewis. Convex Analysis and Nonlinear Optimization: Theory and Examples. Springer–Verlag, second edition, 2006. 10.1007/978-0-387-31256-9.
https://doi.org/10.1007/978-0-387-31256-9

[9] Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004. 10.1017/CBO9780511804441.
https://doi.org/10.1017/CBO9780511804441

[10] Fernando Brandão, Aram Harrow, Jonathan Oppenheim, and Sergii Strelchuk. Quantum conditional mutual information, reconstructed states, and state redistribution. Physical Review Letters, 115 (5): 050501, 2015. 10.1103/PhysRevLett.115.050501.
https://doi.org/10.1103/PhysRevLett.115.050501

[11] Dagmar Bruß, David DiVincenzo, Artur Ekert, Christopher Fuchs, Chiara Macchiavello, and John Smolin. Optimal universal and state-dependent quantum cloning. Physical Review A, 57: 2368–2378, 1998. 10.1103/PhysRevA.57.2368.
https://doi.org/10.1103/PhysRevA.57.2368

[12] Tom Cooney, Christoph Hirche, Ciara Morgan, Jonathan Olson, Kaushik Seshadreesan, John Watrous, and Mark Wilde. Operational meaning of quantum measures of recovery. Physical Review A, 94 (2): 022310, 2016. 10.1103/PhysRevA.94.022310.
https://doi.org/10.1103/PhysRevA.94.022310

[13] Yonina Eldar, Alexandre Megretski, and George Verghese. Designing optimal quantum detectors via semidefinite programming. IEEE Transactions on Information Theory, 49 (4): 1007–1012, 2003. 10.1109/TIT.2003.809510.
https://doi.org/10.1109/TIT.2003.809510

[14] Hamza Fawzi and Omar Fawzi. Efficient optimization of the quantum relative entropy. Journal of Physics A: Mathematical and Theoretical, 51 (15): 154003, 2018. 10.1088/1751-8121/aab285.
https://doi.org/10.1088/1751-8121/aab285

[15] Hamza Fawzi, James Saunderson, and Pablo Parrilo. Semidefinite approximations of the matrix logarithm. Foundations of Computational Mathematics, 19: 259–296, 2019. 10.1007/s10208-018-9385-0.
https://doi.org/10.1007/s10208-018-9385-0

[16] Omar Fawzi and Renato Renner. Quantum conditional mutual information and approximate Markov chains. Communications in Mathematical Physics, 340 (2): 575–611, 2015. 10.1007/s00220-015-2466-x.
https://doi.org/10.1007/s00220-015-2466-x

[17] Fumio Hiai and Dénes Petz. Introduction to Matrix Analysis and Applications. Universitext. Springer International Publishing, 2014. 10.1007/978-3-319-04150-6.
https://doi.org/10.1007/978-3-319-04150-6

[18] Alexander Holevo. Statistical problems in quantum physics. In Proceedings of the Second Japan–USSR Symposium on Probability Theory, volume 330 of Lecture Notes in Mathematics, pages 104–119. Springer, 1973a. 10.1007/BFb0061483.
https://doi.org/10.1007/BFb0061483

[19] Alexander Holevo. Statistical decision theory for quantum systems. Journal of Multivariate Analysis, 3: 337–394, 1973b. 10.1016/0047-259X(73)90028-6.
https://doi.org/10.1016/0047-259X(73)90028-6

[20] Lawrence Ip. Shor's algorithm is optimal. Unpublished manuscript, available from http://www.lawrenceip.com/papers/hspsdp.pdf, 2003.
http://www.lawrenceip.com/papers/hspsdp.pdf

[21] Rahul Jain, Sarvagya Upadhyay, and John Watrous. Two-message quantum interactive proofs are in PSPACE. In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, pages 534–543, 2009. 10.1109/FOCS.2009.30.
https://doi.org/10.1109/FOCS.2009.30

[22] Miroslav Ježek, Jaroslav Řeháček, and Jaromír Fiurášek. Finding optimal strategies for minimum-error quantum-state discrimination. Physical Review A, 65 (6): 060301, 2002. 10.1103/PhysRevA.65.060301.
https://doi.org/10.1103/PhysRevA.65.060301

[23] Kenneth Lange. Optimization, volume 95 of Springer Texts in Statistics. Springer, 2013. 10.1007/978-1-4614-5838-8.
https://doi.org/10.1007/978-1-4614-5838-8

[24] Boris Mordukhovich and Nguyen Mau Nam. Geometric approach to convex subdifferential calculus. Optimization, 66 (6): 839–873, 2017. 10.1080/02331934.2015.1105225.
https://doi.org/10.1080/02331934.2015.1105225

[25] Boris Mordukhovich and Nguyen Mau Nam. An Easy Path to Convex Analysis and Applications. Morgan & Claypool Publishers, 2013. 10.2200/S00554ED1V01Y201312MAS014.
https://doi.org/10.2200/S00554ED1V01Y201312MAS014

[26] Michael Nielsen and Isaac Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000. 10.1017/CBO9780511976667.
https://doi.org/10.1017/CBO9780511976667

[27] R. Tyrell Rockafellar. Convex Analysis. Princeton University Press, 1970. 10.1137/1013042.
https://doi.org/10.1137/1013042

[28] Valerio Scarani, Sofyan Iblisdir, Nicolas Gisin, and Antonio Acín. Quantum cloning. Reviews of Modern Physics, 77 (4): 1225–1256, 2005. 10.1103/RevModPhys.77.1225.
https://doi.org/10.1103/RevModPhys.77.1225

[29] Kaushik Seshadreesan and Mark Wilde. Fidelity of recovery, squashed entanglement, and measurement recoverability. Physical Review A, 92 (4): 042321, 2015. 10.1103/PhysRevA.92.042321.
https://doi.org/10.1103/PhysRevA.92.042321

[30] David Sutter. Approximate Quantum Markov Chains, volume 28 of SpringerBriefs in Mathematical Physics. Springer, 2018. 10.1007/978-3-319-78732-9.
https://doi.org/10.1007/978-3-319-78732-9

[31] John Watrous. Theory of Quantum Information. Cambridge University Press, 2018. 10.1017/9781316848142.
https://doi.org/10.1017/9781316848142

[32] Mark Wilde. Quantum Information Theory. Cambridge University Press, second edition, 2017. 10.1017/CBO9781139525343.
https://doi.org/10.1017/CBO9781139525343

[33] Horace Yuen, Robert Kennedy, and Melvin Lax. On optimal quantum receivers for digital signal detection. Proceedings of the IEEE, 58 (10): 1770–1773, 1970. 10.1109/PROC.1970.8004.
https://doi.org/10.1109/PROC.1970.8004

[34] Horace Yuen, Robert Kennedy, and Melvin Lax. Optimum testing of multiple hypotheses in quantum detection theory. IEEE Transactions on Information Theory, 21 (2): 125–134, 1975. 10.1109/TIT.1975.1055351.
https://doi.org/10.1109/TIT.1975.1055351

Cited by

[1] Sam Cree and Jonathan Sorce, "Geometric conditions for saturating the data processing inequality", Journal of Physics A: Mathematical and Theoretical 55 13, 135202 (2022).

[2] Leonardo Banchi, Jason Pereira, Seth Lloyd, and Stefano Pirandola, "Convex optimization of programmable quantum computers", npj Quantum Information 6, 42 (2020).

[3] Álvaro M. Alhambra, Georgios Styliaris, Nayeli A. Rodríguez-Briones, Jamie Sikora, and Eduardo Martín-Martínez, "Fundamental Limitations to Local Energy Extraction in Quantum Systems", Physical Review Letters 123 19, 190601 (2019).

[4] Sam Cree and Jamie Sikora, "A fidelity measure for quantum states based on the matrix geometric mean", arXiv:2006.06918, (2020).

[5] Leonardo Banchi, Jason Pereira, Seth Lloyd, and Stefano Pirandola, "Optimization and learning of quantum programs", arXiv:1905.01318, (2019).

[6] Leonid Faybusovich and Cunlu Zhou, "Long-Step Path-Following Algorithm for Quantum Information Theory: Some Numerical Aspects and Applications", arXiv:1906.00037, (2019).

[7] Sam Cree and Jonathan Sorce, "Geometric conditions for saturating the data processing inequality", arXiv:2011.03473, (2020).

The above citations are from Crossref's cited-by service (last updated successfully 2023-06-08 07:46:34) and SAO/NASA ADS (last updated successfully 2023-06-08 07:46:35). 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.