Optimization of quantum key distribution networks using clustering algorithms

This paper is devoted to the problem of optimizing a quantum key distribution (QKD) network by combining an initial set of end nodes into small access networks with star-type topology using clustering algorithms. The study presents a modified version of the k-medoids algorithm that takes into account the constraint on the maximum quantum link length between a pair of nodes. A new non-Euclidean metric for link quality assessment based on the quantum capacitance value calculated based on the physical properties and length of the optical fiber link was also presented. The performance of the presented algorithm using two metrics, the Euclidean norm and the presented estimation metric, was then compared. A series of experiments were conducted to solve the clustering problem for multiple sets of nodes randomly distributed on the plane. It is found that the application of the presented non-Euclidean metric reduces the number of clusters by 11.7% compared to the Euclidean norm, and using multiple attempts at each iteration can improve the result by even more than 20%. The clustering method and the new metric presented in this paper allow us to reduce the number of subnets, reducing the cost of organizing central nodes, and also allows us to further solve the simplified problem of building a backbone network, combining the obtained subnets into a single QKD network.

1. Bennett Ch.H., Brassard G. Quantum Cryptography: Public Key Distribution and Coin Tossing. Theoretical Computer Science. 2014;560:7–11. https://doi.org/10.1016/j.tcs.2014.05.025

2. Razd'yakonov E.S., Korchagin S.A. Primenenie matematicheskogo modelirovaniya dlya otsenki topologii setei kvantovogo raspredeleniya klyuchei. In: Tsifrovaya transformatsiya upravleniya: problemy i resheniya: materialy VI Vserossiiskoi nauchno-prakticheskoi konferentsii, 18 April 2024, Moscow, Russia. Moscow: State University of Management; 2024. P. 137–140. (In Russ.).

3. Mehic M., Niemiec M., Rass S., et al. Quantum Key Distribution: A Networking Perspective. ACM Computing Surveys (CSUR). 2020;53(5). https://doi.org/10.1145/3402192

4. Peev M., Pacher Ch., Alléaume R., et al. The SECOQC Quantum Key Distribution Network in Vienna. New Journal of Physics. 2009;11. https://doi.org/10.1088/1367-2630/11/7/075001

5. Razdyakonov E.S. Survey of Topology Optimization Methods for Quantum Key Distribution Networks. Engineering Journal of Don. 2024;(7). (In Russ.). URL: http://www.ivdon.ru/en/magazine/archive/n7y2024/9347

6. Li Q., Wang Ya., Mao H., Yao J., Han Q. Mathematical Model and Topology Evaluation of Quantum Key Distribution Network. Optics Express. 2020;28(7):9419–9434. https://doi.org/10.1364/OE.387697

7. Cirigliano L., Brosco V., Castellano C., Conti C., Pilozzi L. Optimal Quantum Key Distribution Networks: Capacitance Versus Security. npj Quantum Information. 2024;10. https://doi.org/10.1038/s41534-024-00828-7

8. García-Cobo I., Menéndez H.D. Designing Large Quantum Key Distribution Networks Via Medoid-Based Algorithms. Future Generation Computer Systems. 2021;115:814–824. https://doi.org/10.1016/j.future.2020.09.037

9. MacQueen J. Some Methods for Classification and Analysis of Multivariate Observations. In: Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability: Volume 1: Statistics, 21 June – 18 July 1965, 27 December 1965, 07 January 1966, Berkeley, CA, USA. Berkeley-Los Angeles: University of California Press; 1967. P. 281–297.

10. Kaufman L., Rousseeuw P.J. Finding Groups in Data: An Introduction to Cluster Analysis. John Wiley & Sons; 2009. 368 p.