Quantum key distribution rates from semidefinite programming

Mateus Araújo; Marcus Huber; Miguel Navascués; Matej Pivoluska; Armin Tavakoli

doi:10.22331/q-2023-05-24-1019

Quantum key distribution rates from semidefinite programming

Mateus Araújo¹, Marcus Huber^1,2, Miguel Navascués¹, Matej Pivoluska^2,3,4, and Armin Tavakoli^1,2

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

Published:	2023-05-24, volume 7, page 1019
Eprint:	arXiv:2211.05725v2
Doi:	https://doi.org/10.22331/q-2023-05-24-1019
Citation:	Quantum 7, 1019 (2023).

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.

Featured image: Asymptotic key rate in bits per round versus isotropic state visibility $v$, using a quantum key distribution protocol based on measuring mutually unbiased bases (MUBs). For dimension $d = 6$ we used a set of bases that is only approximately unbiased, as MUBs for this dimension are not known and thought unlikely to exist. Note that for dimensions $d = 2, 4, 8$ our numerical technique closely matches the exact result, while for $d = 6$ it is slightly below the rate that would be achievable with MUBs.

► BibTeX data

@article{Araujo2023quantumkey,
  doi = {10.22331/q-2023-05-24-1019},
  url = {https://doi.org/10.22331/q-2023-05-24-1019},
  title = {Quantum key distribution rates from semidefinite programming},
  author = {Ara{\'{u}}jo, Mateus and Huber, Marcus and Navascu{\'{e}}s, Miguel and Pivoluska, Matej and Tavakoli, Armin},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {7},
  pages = {1019},
  month = may,
  year = {2023}
}

► 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] Ohad Lib, Kfir Sulimany, Mateus Araújo, Michael Ben-Or, and Yaron Bromberg, "High-dimensional quantum key distribution using a multi-plane light converter", Optica Quantum 3 2, 182 (2025).

[2] Neha Sharma and Vikas Saxena, "A comparative analysis of error correction techniques used for QKD protocols", Journal of Optics (2025).

[3] Florian Kanitschar, Alexandra Bergmayr-Mann, Matej Pivoluska, and Marcus Huber, "Harnessing high-dimensional temporal entanglement using limited interferometric setups", Physical Review Applied 22 5, 054054 (2024).

[4] Fan Wu and Liang Tang, "Quantifying high-dimensional entanglement via classes of symmetric measurements", Physical Review A 113 2, 022440 (2026).

[5] Guillermo Currás-Lorenzo, Álvaro Navarrete, Javier Núñez-Bon, Margarida Pereira, and Marcos Curty, "Numerical security analysis for quantum key distribution with partial state characterization", Quantum Science and Technology 10 3, 035031 (2025).

[6] Keshav Das Agarwal, Debkanta Ghosh, Pritam Halder, and Aditi Sen(De), "Revealing effects of the local dimension on a variable-range interacting model by connecting Lieb-Robinson bounds and multipartite entanglement", Physical Review B 113 5, 054302 (2026).

[7] Gereon Koßmann and René Schwonnek, "Optimising the relative entropy under semidefinite constraints", npj Quantum Information 12 1, 23 (2026).

[8] Andrés González Lorente, Pablo V. Parellada, Miguel Castillo-Celeita, and Mateus Araújo, "Quantum key distribution rates from non-symmetric conic optimization", Quantum 9, 1657 (2025).

[9] Seyed Arash Ghoreishi, Giovanni Scala, Renato Renner, Letícia Lira Tacca, Jan Bouda, Stephen Patrick Walborn, and Marcin Pawłowski, "The future of secure communications: Device independence in quantum key distribution", Physics Reports 1149, 1 (2025).

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

[11] Florian Kanitschar and Marcus Huber, "Practical Framework for Analyzing High-Dimensional Quantum Key Distribution Setups", Physical Review Letters 135 1, 010802 (2025).

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

[13] Vladyslav C. Usenko, Antonio Acín, Romain Alléaume, Ulrik L. Andersen, Eleni Diamanti, Tobias Gehring, Adnan A. E. Hajomer, Florian Kanitschar, Christoph Pacher, Stefano Pirandola, and Valerio Pruneri, "Continuous-variable quantum communication", Reviews of Modern Physics 98 1, 015003 (2026).

[14] Martin Sandfuchs, Marcus Haberland, V. Vilasini, and Ramona Wolf, "Security of differential phase shift QKD from relativistic principles", Quantum 9, 1611 (2025).

[15] Armin Tavakoli, Alejandro Pozas-Kerstjens, Peter Brown, and Mateus Araújo, "Semidefinite programming relaxations for quantum correlations", Reviews of Modern Physics 96 4, 045006 (2024).

[16] Kfir Sulimany, Guy Pelc, Rom Dudkiewicz, Simcha Korenblit, Hagai S. Eisenberg, Yaron Bromberg, and Michael Ben-Or, "High-dimensional coherent one-way quantum key distribution", npj Quantum Information 11 1, 16 (2025).

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

[18] Mariia Gumberidze and Vladyslav C. Usenko, 2025 International Conference on Quantum Communications, Networking, and Computing (QCNC) 643 (2025) ISBN:979-8-3315-3159-1.

[19] Jie Wang, "A more efficient reformulation of complex SDP as real SDP", Computational Optimization and Applications (2026).

[20] Florian Kanitschar and Marcus Huber, "Composable finite-size security of high-dimensional quantum-key-distribution protocols", Physical Review Applied 24 5, 054028 (2025).

[21] Kerry He, James Saunderson, and Hamza Fawzi, "Interior Point Methods for Structured Quantum Relative Entropy Optimization Problems", Mathematical Programming Computation 18 2, 481 (2026).

[22] Patrick Andriolo, Esteban Vasquez, Elizabeth Agudelo, Max Riegler, Matej Pivoluska, and Gláucia Murta, "Quantum Key Distribution with Imperfections: Recent Advances in Security Proofs", Brazilian Journal of Physics 56 4, 157 (2026).

[23] 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).

[24] Andrew J. P. Garner and Mateus Araújo, "Introducing Moment: A toolkit for semi-definite programming with moment matrices", arXiv:2406.15559, (2024).

[25] Mariana Navarro, Andrés González Lorente, Pablo V. Parellada, Carlos Pascual-García, and Mateus Araújo, "Finite-size quantum key distribution rates from Rényi entropies using conic optimization", arXiv:2511.10584, (2025).

[26] 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).

[27] 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 2026-07-15 08:58:38) and SAO/NASA ADS (last updated successfully 2026-07-14 20:38:23). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch ADS cited-by data during last attempt 2026-07-15 08:58:38: Cannot retrieve data from ADS due to rate limitations.

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.