Robust Interior Point Method for Quantum Key Distribution Rate Computation

Hao Hu1,2, Jiyoung Im1, Jie Lin3,4, Norbert Lütkenhaus3, and Henry Wolkowicz1

1Department of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1
2Department of Mathematical Sciences, Clemson University, Clemson, SC, United States 29634
3Institute for Quantum Computing and Department of Physics and Astronomy, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1
4Department of Electrical & Computer Engineering, University of Toronto, Toronto, Ontario, Canada M5S 3G4

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


Security proof methods for quantum key distribution, QKD, that are based on the numerical key rate calculation problem, are powerful in principle. However, the practicality of the methods are limited by computational resources and the efficiency and accuracy of the underlying algorithms for convex optimization. We derive a stable reformulation of the convex nonlinear semidefinite programming, SDP, model for the key rate calculation problems. We use this to develop an efficient, accurate algorithm. The stable reformulation is based on novel forms of facial reduction, FR, for both the linear constraints and nonlinear quantum relative entropy objective function. This allows for a Gauss-Newton type interior-point approach that avoids the need for perturbations to obtain strict feasibility, a technique currently used in the literature. The result is high accuracy solutions with theoretically proven lower bounds for the original QKD from the FR stable reformulation. This provides novel contributions for FR for general SDP. We report on empirical results that dramatically improve on speed and accuracy, as well as solving previously intractable problems.

Quantum key distribution (QKD) is a provably secure key establishment protocol that can help safeguard important confidential information from the emerging threats of quantum computers. The core of a security proof of any QKD protocol is to calculate the secret key rate. This task that was once challenging even for experts has become more accessible to non-experts thanks to the development of numerical security proof methods. Specifically, the key rate calculation problem has been recast as a convex optimization problem. Consequently, many great tools developed by the convex optimization community can be applied to vastly extend the applicability and practicality of the proof methods. In this work, we apply and extend one of these tools, the facial reduction technique. We use this to reduce the dimension of the numerical problem size, and also improve stability by identifying and removing implicit redundant constraints and parts of the matrices of the objective function. The resulting algorithm is efficient and highly accurate. This allows us to solve previously intractable problems.

► BibTeX data

► References

[1] V. Scarani, H. Bechmann-Pasquinucci, N. J. Cerf, M. Dušek, N. Lütkenhaus, and M. Peev. The security of practical quantum key distribution. Rev. Mod. Phys., 81: 1301, 2009. 10.1103/​RevModPhys.81.1301.

[2] F. Xu, X. Ma, Q. Zhang, H.-K. Lo, and J.-W. Pan. Secure quantum key distribution with realistic devices. Rev. Mod. Phys., 92: 025002, 2020. 10.1103/​RevModPhys.92.025002.

[3] C. H. Bennett and G. Brassard. Quantum cryptography: Public key distribution and coin tossing. In International Conference on Computers, Systems & Signal Processing, Bangalore, India, Dec 9-12, 1984, pages 175–179, 1984. 10.1016/​j.tcs.2014.05.025. Reprint of the 1984 original.

[4] P. J. Coles, E. M. Metodiev, and N. Lütkenhaus. Numerical approach for unstructured quantum key distribution. Nat. Commun., 7: 11712, 2016. 10.1038/​ncomms11712.

[5] A. Winick, N. Lütkenhaus, and P. J. Coles. Reliable numerical key rates for quantum key distribution. Quantum, 2: 77, 2018. 10.22331/​q-2018-07-26-77.

[6] I. George, J. Lin, and N. Lütkenhaus. Numerical calculations of the finite key rate for general quantum key distribution protocols. Physical Review Research, 3: 013274, 2021. 10.1103/​PhysRevResearch.3.013274.

[7] Y. Zhang, P. J. Coles, A. Winick, J. Lin, and N. Lütkenhaus. Security proof of practical quantum key distribution with detection-efficiency mismatch. Phys. Rev. Research, 3: 013076, 2021. 10.1103/​PhysRevResearch.3.013076.

[8] T. Upadhyaya, T. van Himbeeck, J. Lin, and N. Lütkenhaus. Dimension reduction in quantum key distribution for continuous- and discrete-variable protocols. PRX Quantum, 2: 020325, 2021. 10.1103/​PRXQuantum.2.020325.

[9] N. K. H. Li and N. Lütkenhaus. Improving key rates of the unbalanced phase-encoded bb84 protocol using the flag-state squashing model. Phys. Rev. Research, 2: 043172, 2020. 10.1103/​PhysRevResearch.2.043172.

[10] L. Faybusovich and C. Zhou. Long-step path-following algorithm for solving symmetric programming problems with nonlinear objective functions. Computational Optimization and Applications, 72 (3): 769–795, 2019. ISSN 15732894. 10.1007/​s10589-018-0054-7.

[11] I. Devetak and A. Winter. Distillation of secret key and entanglement from quantum states. Proc. R. Soc. A, 461: 207–235, 2005. 10.1098/​rspa.2004.1372.

[12] M. A. Nielsen and I. L. Chuang, editors. Quantum Computation and Quantum Information. Cambridge University Press, Cambridge, UK, 2000. 10.1017/​CBO9780511976667.

[13] D. Drusvyatskiy and H. Wolkowicz. The many faces of degeneracy in conic optimization. Foundations and Trends® in Optimization, 3 (2): 77–170, 2017. ISSN 2167-3888. /​10.1561/​2400000011.

[14] J. Watrous. The Theory of Quantum Information. Cambridge University Press, Cambridge, UK, 2018. ISBN 1107180562. 10.1017/​9781316848142.

[15] P. J. Coles. Unification of different views of decoherence and discord. Phys. Rev. A, 85: 042103, 2012. 10.1103/​PhysRevA.85.042103.

[16] A. Ferenczi and N. Lütkenhaus. Symmetries in quantum key distribution and the connection between optimal attacks and optimal cloning. Phys. Rev. A, 85: 052310, 2012. 10.1103/​PhysRevA.85.052310.

[17] J. M. Borwein and H. Wolkowicz. Regularizing the abstract convex program. J. Math. Anal. Appl., 83 (2): 495–530, 1981. ISSN 0022-247X. 10.1017/​S1446788700017250.

[18] S. Sremac, H. J. Woerdeman, and H. Wolkowicz. Error bounds and singularity degree in semidefinite programming. SIAM J. Optim., 31 (1): 812–836, 2021. ISSN 1052-6234. 10.1137/​19M1289327.

[19] R. T. Rockafellar. Convex analysis. Princeton Mathematical Series, No. 28. Princeton University Press, Princeton, N.J., 1970. 10.1515/​9781400873173.

[20] D. G. Luenberger and Y. Ye. Linear and Nonlinear Programming, volume 116 of International series in operations research & management science. Springer, Boston, USA, 2008. ISBN 9781441945044. 10.1007/​978-0-387-74503-9.

[21] J. Nocedal and S. J. Wright. Numerical optimization. Springer Series in Operations Research and Financial Engineering. Springer, New York, NY, USA, second edition, 2006. ISBN 978-0387-30303-1; 0-387-30303-0. 10.1007/​978-0-387-40065-5.

[22] J. P. Dedieu and M. Shub. Newton's method for overdetermined systems of equations. Math. Comp., 69 (231): 1099–1115, 2000. ISSN 0025-5718. 10.1090/​S0025-5718-99-01115-1.

[23] J. E. Dennis Jr. and R. B. Schnabel. Numerical methods for unconstrained optimization and nonlinear equations, volume 16 of Classics in Applied Mathematics. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1996. ISBN 0-89871-364-1. 10.1137/​1.9781611971200. Corrected reprint of the 1983 original.

[24] R. D. C. Monteiro and M. J. Todd. Path-following methods. In Handbook of Semidefinite Programming, volume 27 of International Series in Operations Research & Management Science, pages 267–306. Springer, Boston, MA, 2000. 10.1007/​978-1-4615-4381-7_10.

[25] J. W. Demmel. Applied numerical linear algebra. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. ISBN 0-89871-389-7. 10.1137/​1.9781611971446.

[26] J. Lin, T. Upadhyaya, and N. Lütkenhaus. Asymptotic security analysis of discrete-modulated continuous-variable quantum key distribution. Phys. Rev. X, 9: 041064, 2019. 10.1103/​PhysRevX.9.041064.

[27] H. Fawzi, J. Saunderson, and P. A. Parrilo. Semidefinite approximations of the matrix logarithm. Foundations of Computational Mathematics, 19: 259–296, 2019. 10.1007/​s10208-018-9385-0. Package cvxquad at https:/​/​​hfawzi/​cvxquad.

[28] S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, Cambridge, UK, 2004. 10.1017/​CBO9780511804441.

[29] D. G. Luenberger. Optimization by Vector Space Methods. John Wiley & Sons, New York, USA, 1969.

[30] J. E. Dennis Jr. and H. Wolkowicz. Sizing and least-change secant methods. SIAM J. Numer. Anal., 30 (5): 1291–1314, 1993. ISSN 0036-1429. 10.1137/​0730067.

[31] H.-K. Lo, M. Curty, and B. Qi. Measurement-device-independent quantum key distribution. Phys. Rev. Lett., 108: 130503, 2012. 10.1103/​PhysRevLett.108.130503.

[32] Z. Cao, Z. Zhang, H.-K. Lo, and X. Ma. Discrete-phase-randomized coherent state source and its application in quantum key distribution. New J. Phys., 17: 053014, 2015. 10.1088/​1367-2630/​17/​5/​053014.

[33] M. Lucamarini, Z. L. Yuan, J. F. Dynes, and A. J. Shields. Overcoming the rate-distance limit of quantum key distribution without quantum repeaters. Nature, 557: 400–403, 2018. 10.1038/​s41586-018-0066-6.

[34] M. Curty, K. Azuma, and H.-K. Lo. Simple security proof of twin-field type quantum key distribution protocol. npj. Quantum Inf., 5: 64, 2019. 10.1038/​s41534-019-0175-6.

Cited by

[1] Tony Metger and Renato Renner, "Security of quantum key distribution from generalised entropy accumulation", arXiv:2203.04993.

[2] Min-Gang Zhou, Zhi-Ping Liu, Wen-Bo Liu, Chen-Long Li, Jun-Lin Bai, Yi-Ran Xue, Yao Fu, Hua-Lei Yin, and Zeng-Bing Chen, "Neural network-based prediction of the secret-key rate of quantum key distribution", Scientific Reports 12, 8879 (2022).

[3] Wen-Bo Liu, Chen-Long Li, Yuan-Mei Xie, Chen-Xun Weng, Jie Gu, Xiao-Yu Cao, Yu-Shuo Lu, Bing-Hong Li, Hua-Lei Yin, and Zeng-Bing Chen, "Homodyne Detection Quadrature Phase Shift Keying Continuous-Variable Quantum key Distribution with High Excess Noise Tolerance", PRX Quantum 2 4, 040334 (2021).

[4] Zhi-Ping Liu, Min-Gang Zhou, Wen-Bo Liu, Chen-Long Li, Jie Gu, Hua-Lei Yin, and Zeng-Bing Chen, "Automated machine learning for secure key rate in discrete-modulated continuous-variable quantum key distribution", Optics Express 30 9, 15024 (2022).

[5] Hamza Fawzi and James Saunderson, "Optimal self-concordant barriers for quantum relative entropies", arXiv:2205.04581.

The above citations are from SAO/NASA ADS (last updated successfully 2022-10-01 14:48:23). 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 2022-10-01 14:48:21).