Scheduling Algorithms for Quantum Switches

R. SRIKANT
Electrical and Computer Engineering
University of Illinois Urbana-Champaign
 

Title: Scheduling Algorithms for Quantum Switches

 

Abstract: We consider scheduling in a quantum switch with stochastic entanglement generation, finite quantum memories, and decoherence. The objective is to design a scheduling algorithm with polynomial-time computational complexity that stabilizes a nontrivial fraction of the capacity region. Scheduling in such a switch corresponds to finding a matching in a graph subject to additional constraints. We propose an LP-based policy, which finds a point in the matching polytope, which is further implemented using a randomized decomposition into matchings. The main challenge is that service over an edge is feasible only when entanglement is simultaneously available at both endpoint memories, so the effective service rates depend on the steady-state availability induced by the scheduling rule. To address this, we introduce a single-node reference Markov chain and derive lower bounds on achievable service rates in terms of the steady-state nonemptiness probabilities. We then use a Lyapunov drift argument to show that, whenever the request arrival rates lie within the resulting throughput region, the proposed algorithm stabilizes the request queues. We further analyze how the achievable throughput depends on entanglement generation rates, decoherence probabilities, and buffer sizes, and show that the throughput lower bound converges exponentially fast to its infinite-buffer limit as the memory size increases. Numerical results illustrate that the guaranteed throughput fraction is substantial for parameter regimes relevant to near-term quantum networking systems.

 

Bio: R. Srikant is the director for the National Center for Supercomputing Applications (NCSA), a Grainger Distinguished Chair in Engineering, and Professor in the Department of Electrical and Computer Engineering and the Coordinated Science Lab, all at the University of Illinois Urbana-Champaign. His research interests include machine learning, applied probability, stochastic control, and communication networks. He is the recipient of the 2015 INFOCOM Achievement Award, the 2019 IEEE Koji Kobayashi Computers and Communications Award and the 2021 ACM SIGMETRICS Achievement Award. He has also received several Best Paper awards including the 2015 INFOCOM Best Paper Award, the 2017 Applied Probability Society Best Publication Award, and the 2017 WiOpt Best Paper award. He was the Editor-in-Chief of the IEEE/ACM Transactions on Networking from 2013-2017 and is currently an Area Editor for the Mathematics of Operations Research. 

THIS TALK IS CO-SPONSORED BY THE DATA SCIENCE DISTINGUISHED LECTURE SERIES AND THE ORIE COLLOQUIUM