Utility-Based Path Selection and Configuration in Quantum Networks via Layered Shortest Paths

In quantum networks, distributing entanglement between two nodes requires selecting a path and configuring link-level parameters (such as distillation rounds or emitter brightness). These choices create a fundamental trade-off between the rate and the quality (fidelity) of the delivered entanglement. The authors ask how to jointly optimize the path and link configurations to maximize an arbitrary, nondecreasing application-specific utility function, given that these metrics do not compose additively in the standard way.

The authors observe that after a suitable reparameterization—specifically, using inverse rate and negative log-fidelity—the composition rules for rate and fidelity become additive. They construct a layered graph where each physical node is replicated across multiple layers, each representing a discretized value of the end-to-end fidelity. By running Dijkstra's algorithm on this layered graph, the authors compute the highest achievable rate for every discretized fidelity level, effectively recovering the full rate-fidelity Pareto frontier. This frontier allows for the selection of the optimal path for any nondecreasing utility function.

The QLSP algorithm provides a fully polynomial-time approximation scheme (FPTAS) for a wide class of utility functions, including the secret key rate of the BB84 protocol. The authors prove that while cheaper scalarization-based routing (which collapses rate and fidelity into a single weighted-sum cost) is optimal for utilities with convex fidelity profiles, it can be arbitrarily suboptimal for non-convex utilities, such as those with step-like or sigmoidal requirements. QLSP avoids this duality gap by explicitly maintaining the Pareto frontier, consistently outperforming baseline methods in synthetic and real-world network topologies.

As quantum networks move toward practical deployment, routing must support diverse applications with varying requirements for rate and fidelity. This work provides a mathematically rigorous and computationally efficient framework for joint path selection and configuration. By demonstrating that simple scalarization methods are insufficient for many realistic quantum applications, the authors provide a necessary tool for achieving optimal performance in heterogeneous quantum network environments.