Certifying optimality for convex quantum channel optimization problems

Bryan Coutts1,2, Mark Girard1, and John Watrous1,2,3

1Institute for Quantum Computing, University of Waterloo, Canada
2School of Computer Science, University of Waterloo, Canada
3Canadian Institute for Advanced Research, Toronto, Canada

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


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

► 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.

[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.

[3] Stephen Barnett and Sarah Croke. Quantum state discrimination. Advances in Optics and Photonics, 1 (2): 238–278, 2009. 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.

[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.

[6] Rajendra Bhatia. Matrix Analysis, volume 169 of Graduate Texts in Mathematics. Springer, 1997. 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.

[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.

[9] Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004. 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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[19] Alexander Holevo. Statistical decision theory for quantum systems. Journal of Multivariate Analysis, 3: 337–394, 1973b. 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.

[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.

[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.

[23] Kenneth Lange. Optimization, volume 95 of Springer Texts in Statistics. Springer, 2013. 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.

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

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

[27] R. Tyrell Rockafellar. Convex Analysis. Princeton University Press, 1970. 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.

[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.

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

[31] John Watrous. Theory of Quantum Information. Cambridge University Press, 2018. 10.1017/​9781316848142.

[32] Mark Wilde. Quantum Information Theory. Cambridge University Press, second edition, 2017. 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.

[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.

Cited by

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

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

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

[4] Álvaro M. Alhambra, Georgios Styliaris, Nayeli A. Rodriguez-Briones, Jamie Sikora, and Eduardo Martin-Martinez, "Fundamental limitations to local energy extraction in quantum systems", arXiv:1902.02357.

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

[6] Samuel S. Cree and Jonathan Sorce, "Geometric conditions for saturating the data processing inequality", arXiv:2011.03473.

The above citations are from SAO/NASA ADS (last updated successfully 2021-05-06 19:41:26). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2021-05-06 19:41:24).