  Distributed quantum computing (DQC) holds immense promise in harnessing the
potential of quantum computing by interconnecting multiple small quantum
computers (QCs) through a quantum data network (QDN). Establishing
long-distance quantum entanglement between two QCs for quantum teleportation
within the QDN is a critical aspect, and it involves entanglement routing -
finding a route between QCs and efficiently allocating qubits along that route.
Existing approaches have mainly focused on optimizing entanglement performance
for current entanglement connection (EC) requests. However, they often overlook
the user's perspective, wherein the user making EC requests operates under a
budget constraint over an extended period. Furthermore, both QDN resources
(quantum channels and qubits) and the EC requests, reflecting the DQC workload,
vary over time. In this paper, we present a novel user-centric entanglement
routing problem that spans an extended period to maximize the entanglement
success rate while adhering to the user's budget constraint. To address this
challenge, we leverage the Lyapunov drift-plus-penalty framework to decompose
the long-term optimization problem into per-slot problems, allowing us to find
solutions using only the current system information. Subsequently, we develop
efficient algorithms based on continuous-relaxation and Gibbs-sampling
techniques to solve the per-slot entanglement routing problem. Theoretical
performance guarantees are provided for both the per-slot and long-term
problems. Extensive simulations demonstrate that our algorithm significantly
outperforms baseline approaches in terms of entanglement success rate and
budget adherence.
