Greedy Algorithms for Finding Entanglement Swap Paths in Quantum Networks

Pandey, Anoop Kumar and Srivastava, Anubhav and Handoo, Shuhul and Tamma, Bheemarjuna Reddy and Rao, M.V. Panduranga (2023) Greedy Algorithms for Finding Entanglement Swap Paths in Quantum Networks. In: 24th International Conference on Distributed Computing and Networking, ICDCN 2023, 4-7 January 2023, Kharagpur.

Text
3571306.3571408.pdf - Published Version
Download (2MB)

Abstract

The entanglement swap primitive facilitates the establishment of shared entanglement between non-adjacent nodes in a quantum network. This shared entanglement can subsequently be used for executing quantum communication protocols. The fundamental problem in quantum networks is to determine a path for entanglement swapping in response to demands for entanglement sharing between pairs of nodes. We investigate variants of this problem in this work. We propose a framework of Greedy algorithms that can be tweaked towards optimizing on various objective functions. In conjunction with a novel Spatial and Temporal (split across multiple paths) splitting approach to entanglement routing, we use this framework, which we call GST, to investigate the scenario when the demands are specified in terms of a starting time and a deadline. Considering the fragile nature of quantum memory, "bursty"demands are natural, and therefore the setting is important. We study the algorithm for maximizing the number of satisfied demands and the number of entangled pairs shared. We report empirical results on the performance against these objective functions, and compare with a naive algorithm that involves neither temporal and spatial splitting of the demands, nor the greedy approach to scheduling the demands.

[error in script]

IITH Creators:

IITH Creators	ORCiD
Tamma, Bheemarjuna Reddy	http://www.orcid.org/0000-0002-4056-7963
Rao, M V Panduranga	http://www.orcid.org/0000-0003-3761-8501

Item Type:

Conference or Workshop Item (Paper)

Uncontrolled Keywords:

Quantum communication;Adjacent nodes; Entanglement swapping; Greedy algorithms; Multiple-path; Objective functions; Quantum communication protocols; Quantum network; Routings; Shared entanglement; Splittings;Quantum entanglement

Subjects:

Computer science
Computer science > Algorithm Analysis
Computer science > Wireless Networks

Divisions:

Department of Computer Science & Engineering

Depositing User:

Mr Nigam Prasad Bisoyi

Date Deposited:

16 Aug 2023 11:15

Last Modified:

16 Aug 2023 11:15

URI:

http://raiithold.iith.ac.in/id/eprint/11547