Quantum key distribution rates from semidefinite programming

Mateus Araújo1, Marcus Huber1,2, Miguel Navascués1, Matej Pivoluska2,3,4, and Armin Tavakoli1,2

1Institute for Quantum Optics and Quantum Information (IQOQI), Austrian Academy of Sciences, Boltzmanngasse 3, 1090 Vienna, Austria
2Vienna Center for Quantum Science and Technology, Atominstitut, TU Wien, 1020 Vienna, Austria
3Institute of Computer Science, Masaryk University, 602 00 Brno, Czech Republic
4Institute of Physics, Slovak Academy of Sciences, 845 11 Bratislava, Slovakia

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

Abstract

Computing the key rate in quantum key distribution (QKD) protocols is a long standing challenge. Analytical methods are limited to a handful of protocols with highly symmetric measurement bases. Numerical methods can handle arbitrary measurement bases, but either use the min-entropy, which gives a loose lower bound to the von Neumann entropy, or rely on cumbersome dedicated algorithms. Based on a recently discovered semidefinite programming (SDP) hierarchy converging to the conditional von Neumann entropy, used for computing the asymptotic key rates in the device independent case, we introduce an SDP hierarchy that converges to the asymptotic secret key rate in the case of characterised devices. The resulting algorithm is efficient, easy to implement and easy to use. We illustrate its performance by recovering known bounds on the key rate and extending high-dimensional QKD protocols to previously intractable cases. We also use it to reanalyse experimental data to demonstrate how higher key rates can be achieved when the full statistics are taken into account.

► BibTeX data

► References

[1] Nicolas Gisin, Grégoire Ribordy, Wolfgang Tittel, and Hugo Zbinden, ``Quantum cryptography'' Reviews of Modern Physics 74, 145-195 (2002).
https:/​/​doi.org/​10.1103/​RevModPhys.74.145

[2] Valerio Scarani, Helle Bechmann-Pasquinucci, Nicolas J. Cerf, Miloslav Dušek, Norbert Lütkenhaus, and Momtchil Peev, ``The security of practical quantum key distribution'' Reviews of Modern Physics 81, 1301–1350 (2009).
https:/​/​doi.org/​10.1103/​RevModPhys.81.1301
arXiv:0802.4155

[3] Feihu Xu, Xiongfeng Ma, Qiang Zhang, Hoi-Kwong Lo, and Jian-Wei Pan, ``Secure quantum key distribution with realistic devices'' Reviews of Modern Physics 92, 025002 (2020).
https:/​/​doi.org/​10.1103/​RevModPhys.92.025002
arXiv:1903.09051

[4] S. Pirandola, U. L. Andersen, L. Banchi, M. Berta, D. Bunandar, R. Colbeck, D. Englund, T. Gehring, C. Lupo, C. Ottaviani, J. L. Pereira, M. Razavi, J. Shamsul Shaari, M. Tomamichel, V. C. Usenko, G. Vallone, P. Villoresi, and P. Wallden, ``Advances in quantum cryptography'' Advances in Optics and Photonics 12, 1012 (2020).
https:/​/​doi.org/​10.1364/​AOP.361502
arXiv:1906.01645

[5] Charles H. Bennettand Gilles Brassard ``Quantum cryptography: Public key distribution and coin tossing'' Theoretical Computer Science 560, 7–11 (1984) (reprint).
https:/​/​doi.org/​10.1016/​j.tcs.2014.05.025

[6] Dagmar Bruß ``Optimal Eavesdropping in Quantum Cryptography with Six States'' Physical Review Letters 81, 3018–3021 (1998).
https:/​/​doi.org/​10.1103/​PhysRevLett.81.3018

[7] Nicolas J. Cerf, Mohamed Bourennane, Anders Karlsson, and Nicolas Gisin, ``Security of Quantum Key Distribution Using $d$-Level Systems'' Physical Review Letters 88, 127902 (2002).
https:/​/​doi.org/​10.1103/​PhysRevLett.88.127902

[8] Lana Sheridanand Valerio Scarani ``Security proof for quantum key distribution using qudit systems'' Physical Review A 82, 030301(R) (2010).
https:/​/​doi.org/​10.1103/​physreva.82.030301
arXiv:1003.5464

[9] Robert König, Renato Renner, and Christian Schaffner, ``The operational meaning of min- and max-entropy'' IEEE Transactions on Information Theory 55, 4337–4347 (2009).
https:/​/​doi.org/​10.1109/​TIT.2009.2025545
arXiv:0807.1338

[10] Jean-Daniel Bancal, Lana Sheridan, and Valerio Scarani, ``More randomness from the same data'' New Journal of Physics 16, 033011 (2014).
https:/​/​doi.org/​10.1088/​1367-2630/​16/​3/​033011
arXiv:1309.3894

[11] O. Nieto-Silleras, S. Pironio, and J. Silman, ``Using complete measurement statistics for optimal device-independent randomness evaluation'' New Journal of Physics 16, 013035 (2014).
https:/​/​doi.org/​10.1088/​1367-2630/​16/​1/​013035
arXiv:1309.3930

[12] Mirdit Doda, Marcus Huber, Gláucia Murta, Matej Pivoluska, Martin Plesch, and Chrysoula Vlachou, ``Quantum Key Distribution Overcoming Extreme Noise: Simultaneous Subspace Coding Using High-Dimensional Entanglement'' Physical Review Applied 15, 034003 (2021).
https:/​/​doi.org/​10.1103/​physrevapplied.15.034003
arXiv:2004.12824

[13] Yukun Wang, Ignatius William Primaatmaja, Emilien Lavie, Antonios Varvitsiotis, and Charles Ci Wen Lim, ``Characterising the correlations of prepare-and-measure quantum networks'' npj Quantum Information 5, 17 (2019).
https:/​/​doi.org/​10.1038/​s41534-019-0133-3
arXiv:1803.04796

[14] Ernest Y. Z. Tan, René Schwonnek, Koon Tong Goh, Ignatius William Primaatmaja, and Charles C. W. Lim, ``Computing secure key rates for quantum cryptography with untrusted devices'' npj Quantum Information 7, 158 (2021).
https:/​/​doi.org/​10.1038/​s41534-021-00494-z
arXiv:1908.11372

[15] Adam Winick, Norbert Lütkenhaus, and Patrick J. Coles, ``Reliable numerical key rates for quantum key distribution'' Quantum 2, 77 (2018).
https:/​/​doi.org/​10.22331/​q-2018-07-26-77
arXiv:1710.05511

[16] Hao Hu, Jiyoung Im, Jie Lin, Norbert Lütkenhaus, and Henry Wolkowicz, ``Robust Interior Point Method for Quantum Key Distribution Rate Computation'' Quantum 6, 792 (2022).
https:/​/​doi.org/​10.22331/​q-2022-09-08-792
arXiv:2104.03847

[17] Peter Brown, Hamza Fawzi, and Omar Fawzi, ``Device-independent lower bounds on the conditional von Neumann entropy'' (2021).
arXiv:2106.13692

[18] Miguel Navascués, Stefano Pironio, and Antonio Acín, ``A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations'' New Journal of Physics 10, 073013 (2008).
https:/​/​doi.org/​10.1088/​1367-2630/​10/​7/​073013
arXiv:0803.4290

[19] Hoi-Kwong Lo, H. F. Chau, and M. Ardehali, ``Efficient Quantum Key Distribution Scheme and a Proof of Its Unconditional Security'' Journal of Cryptology 18, 113–165 (2005).
https:/​/​doi.org/​10.1007/​s00145-004-0142-y

[20] Igor Devetakand Andreas Winter ``Distillation of secret key and entanglement from quantum states'' Proceedings of the Royal Society of London Series A 461, 207–235 (2005).
https:/​/​doi.org/​10.1098/​rspa.2004.1372

[21] Gene H. Golub ``Some Modified Matrix Eigenvalue Problems'' SIAM Review 15, 318–334 (1973).
https:/​/​doi.org/​10.1137/​1015032

[22] Miguel Navascués, Gonzalo de la Torre, and Tamás Vértesi, ``Characterization of Quantum Correlations with Local Dimension Constraints and Its Device-Independent Applications'' Physical Review X 4, 011011 (2014).
https:/​/​doi.org/​10.1103/​PhysRevX.4.011011
arXiv:1308.3410

[23] Dmitriy Drusvyatskiyand Henry Wolkowicz ``The many faces of degeneracy in conic optimization'' Foundations and Trends in Optimization 3, 77–170 (2017).
https:/​/​doi.org/​10.1561/​2400000011
arXiv:1706.03705

[24] Karin Gatermannand Pablo A. Parrilo ``Symmetry groups, semidefinite programs, and sums of squares'' Journal of Pure and Applied Algebra 192, 95–128 (2004).
https:/​/​doi.org/​10.1016/​j.jpaa.2003.12.011

[25] Jos F. Sturm ``Using SeDuMi 1.02, A MATLAB toolbox for optimization over symmetric cones'' Optimization Methods and Software 11, 625–653 (1999).
https:/​/​doi.org/​10.1080/​10556789908805766
https:/​/​github.com/​sqlp/​sedumi

[26] Chris Coey, Lea Kapelevich, and Juan Pablo Vielma, ``Solving natural conic formulations with Hypatia.jl'' INFORMS Journal on Computing 34, 2686–2699 (2022) https:/​/​github.com/​chriscoey/​Hypatia.jl.
https:/​/​doi.org/​10.1287/​ijoc.2022.1202
arXiv:2005.01136
https:/​/​github.com/​chriscoey/​Hypatia.jl

[27] MOSEK ApS ``The MOSEK Optimization Suite 10.0.40'' manual (2023) https:/​/​docs.mosek.com/​latest/​intro/​index.html.
https:/​/​docs.mosek.com/​latest/​intro/​index.html

[28] J. Löfberg ``YALMIP : a toolbox for modeling and optimization in MATLAB'' Proceedings of the CACSD Conference 284–289 (2004).
https:/​/​doi.org/​10.1109/​CACSD.2004.1393890

[29] William K Woottersand Brian D Fields ``Optimal state-determination by mutually unbiased measurements'' Annals of Physics 191, 363–381 (1989).
https:/​/​doi.org/​10.1016/​0003-4916(89)90322-9

[30] Ingemar Bengtsson, Wojciech Bruzda, Åsa Ericsson, Jan-Åke Larsson, Wojciech Tadej, and Karol Å»yczkowski, ``Mutually unbiased bases and Hadamard matrices of order six'' Journal of Mathematical Physics 48, 052106 (2007).
https:/​/​doi.org/​10.1063/​1.2716990

[31] Ingemar Bengtsson ``Three Ways to Look at Mutually Unbiased Bases'' AIP Conference Proceedings 889, 40–51 (2007).
https:/​/​doi.org/​10.1063/​1.2713445

[32] Jessica Bavaresco, Natalia Herrera Valencia, Claude Klöckl, Matej Pivoluska, Paul Erker, Nicolai Friis, Mehul Malik, and Marcus Huber, ``Measurements in two bases are sufficient for certifying high-dimensional entanglement'' Nature Physics 14, 1032–1037 (2018).
https:/​/​doi.org/​10.1038/​s41567-018-0203-z
arXiv:1709.07344

[33] Yeong Cherng Liang, Dagomir Kaszlikowski, Berthold-Georg Englert, Leong Chuan Kwek, and C. H. Oh, ``Tomographic quantum cryptography'' Physical Review A 68, 022324 (2003).
https:/​/​doi.org/​10.1103/​PhysRevA.68.022324

[34] Yongtao Zhanand Hoi-Kwong Lo ``Tomography-based Quantum Key Distribution'' (2020).
arXiv:2008.11628

[35] Alexey Tiranov, Sébastien Designolle, Emmanuel Zambrini Cruzeiro, Jonathan Lavoie, Nicolas Brunner, Mikael Afzelius, Marcus Huber, and Nicolas Gisin, ``Quantification of multidimensional entanglement stored in a crystal'' Physical Review A 96, 040303 (2017).
https:/​/​doi.org/​10.1103/​PhysRevA.96.040303
arXiv:1609.05033

[36] Sebastian Ecker, Frédéric Bouchard, Lukas Bulla, Florian Brandt, Oskar Kohout, Fabian Steinlechner, Robert Fickler, Mehul Malik, Yelena Guryanova, Rupert Ursin, and Marcus Huber, ``Overcoming Noise in Entanglement Distribution'' Physical Review X 9, 041042 (2019).
https:/​/​doi.org/​10.1103/​PhysRevX.9.041042
arXiv:1904.01552

[37] Lukas Bulla, Matej Pivoluska, Kristian Hjorth, Oskar Kohout, Jan Lang, Sebastian Ecker, Sebastian P. Neumann, Julius Bittermann, Robert Kindler, Marcus Huber, Martin Bohmann, and Rupert Ursin, ``Nonlocal Temporal Interferometry for Highly Resilient Free-Space Quantum Communication'' Physical Review X 13, 021001 (2023).
https:/​/​doi.org/​10.1103/​physrevx.13.021001
arXiv:2204.07536

[38] Zdenek Hradil ``Quantum-state estimation'' Physical Review A 55, R1561–R1564 (1997).
https:/​/​doi.org/​10.1103/​PhysRevA.55.R1561

[39] V. Bužek, R. Derka, G. Adam, and P.L. Knight, ``Reconstruction of Quantum States of Spin Systems: From Quantum Bayesian Inference to Quantum Tomography'' Annals of Physics 266, 454–496 (1998).
https:/​/​doi.org/​10.1006/​aphy.1998.5802

[40] Rüdiger Schack, Todd A. Brun, and Carlton M. Caves, ``Quantum Bayes rule'' Physical Review A 64, 014305 (2001).
https:/​/​doi.org/​10.1103/​PhysRevA.64.014305

[41] Robin Blume-Kohout ``Optimal, reliable estimation of quantum states'' New Journal of Physics 12, 043034 (2010).
https:/​/​doi.org/​10.1088/​1367-2630/​12/​4/​043034

[42] Robin Blume-Kohout ``Robust error bars for quantum tomography'' (2012).
arXiv:1202.5270

[43] Jiangwei Shang, Hui Khoon Ng, Arun Sehrawat, Xikun Li, and Berthold-Georg Englert, ``Optimal error regions for quantum state estimation'' New Journal of Physics 15, 123026 (2013).
https:/​/​doi.org/​10.1088/​1367-2630/​15/​12/​123026
arXiv:1302.4081

[44] Christopher Ferrie ``High posterior density ellipsoids of quantum states'' New Journal of Physics 16, 023006 (2014).
https:/​/​doi.org/​10.1088/​1367-2630/​16/​2/​023006
arXiv:1310.1903

[45] Christopher Granade, Joshua Combes, and D G Cory, ``Practical Bayesian tomography'' New Journal of Physics 18, 033024 (2016).
https:/​/​doi.org/​10.1088/​1367-2630/​18/​3/​033024
arXiv:1509.03770

[46] Lukas Bulla, Kristian Hjorth, Oskar Kohout, Jan Lang, Sebastian Ecker, Sebastian P. Neumann, Julius Bittermann, Robert Kindler, Marcus Huber, Martin Bohmann, Rupert Ursin, and Matej Pivoluska, ``Distribution of genuine high-dimensional entanglement over 10.2 km of noisy metropolitan atmosphere'' (2023).
arXiv:2301.05724

[47] Natalia Herrera Valencia, Vatshal Srivastav, Matej Pivoluska, Marcus Huber, Nicolai Friis, Will McCutcheon, and Mehul Malik, ``High-Dimensional Pixel Entanglement: Efficient Generation and Certification'' Quantum 4, 376 (2020).
https:/​/​doi.org/​10.22331/​q-2020-12-24-376
arXiv:2004.04994

[48] Jessica Bavaresco, Mio Murao, and Marco Túlio Quintino, ``Strict Hierarchy between Parallel, Sequential, and Indefinite-Causal-Order Strategies for Channel Discrimination'' Physical Review Letters 127, 200504 (2021).
https:/​/​doi.org/​10.1103/​PhysRevLett.127.200504
arXiv:2011.08300

[49] Hoi-Kwong Lo, Marcos Curty, and Bing Qi, ``Measurement-Device-Independent Quantum Key Distribution'' Physical Review Letters 108, 130503 (2012).
https:/​/​doi.org/​10.1103/​PhysRevLett.108.130503
arXiv:1109.1473

[50] 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).
https:/​/​doi.org/​10.1038/​s41586-018-0066-6
arXiv:1811.06826

[51] Won-Young Hwang ``Quantum Key Distribution with High Loss: Toward Global Secure Communication'' Physical Review Letters 91, 057901 (2003).
https:/​/​doi.org/​10.1103/​PhysRevLett.91.057901

[52] Frederic Dupuis, Omar Fawzi, and Renato Renner, ``Entropy accumulation'' Communications in Mathematical Physics 379, 867–913 (2020).
https:/​/​doi.org/​10.1007/​s00220-020-03839-5
arXiv:1607.01796

[53] Ian George, Jie Lin, Thomas van Himbeeck, Kun Fang, and Norbert Lütkenhaus, ``Finite-Key Analysis of Quantum Key Distribution with Characterized Devices Using Entropy Accumulation'' (2022).
arXiv:2203.06554

Cited by

[1] Simon Morelli, Marcus Huber, and Armin Tavakoli, "Resource-Efficient High-Dimensional Entanglement Detection via Symmetric Projections", Physical Review Letters 131 17, 170201 (2023).

[2] Yazi Wang, Xiaosong Yu, Zihao Wang, Yuan Cao, Yongli Zhao, and Jie Zhang, 2023 21st International Conference on Optical Communications and Networks (ICOCN) 1 (2023) ISBN:979-8-3503-4350-2.

[3] Tony Metger and Renato Renner, "Security of quantum key distribution from generalised entropy accumulation", Nature Communications 14 1, 5272 (2023).

[4] Martin Sandfuchs, Marcus Haberland, V. Vilasini, and Ramona Wolf, "Security of differential phase shift QKD from relativistic principles", arXiv:2301.11340, (2023).

[5] Eva M. González-Ruiz, Javier Rivera-Dean, Marina F. B. Cenni, Anders S. Sørensen, Antonio Acín, and Enky Oudot, "Device-independent quantum key distribution with realistic single-photon source implementations", Optics Express 32 8, 13181 (2024).

[6] Jessica O. de Almeida, Matthias Kleinmann, and Gael Sentís, "Comparison of confidence regions for quantum state tomography", New Journal of Physics 25 11, 113018 (2023).

[7] Oisín Faust and Hamza Fawzi, "Rational approximations of operator monotone and operator convex functions", arXiv:2305.12405, (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2024-04-15 09:27:27) and SAO/NASA ADS (last updated successfully 2024-04-15 09:27:28). The list may be incomplete as not all publishers provide suitable and complete citation data.