Efficient routing and spectrum allocation in arbitrary flex-grid entanglement networks

Technical Summary: Efficient Routing and Spectrum Allocation in Arbitrary Flex-Grid Entanglement Networks

Problem Statement
As quantum networks scale toward large-scale deployment, there is an increasing need for efficient user-to-user frequency allocation. While classical flexible-grid (flex-grid) networks have established robust Routing and Spectrum Allocation (RSA) frameworks to manage dynamic bandwidth, quantum RSA presents unique challenges. Unlike classical systems, quantum networks must account for entanglement fidelity, source coordination, and the specific physics of photon pair generation.

Existing quantum RSA studies have largely focused on repeater-based architectures for long-distance distribution or idealized topologies. However, current testbeds often lack deployed quantum repeaters yet have reached sizes where resource management is critical. In this "repeater-less" regime, the goal is to distribute entangled frequency slots to multiple users across arbitrary topologies. This is formalized as the Entangled Flux Allocation (EFA) problem. Previous approaches for star topologies relied on genetic algorithms (GAs), which, while powerful, suffer from slow execution speeds and limited scalability. Furthermore, no prior work has combined efficient RSA with multiple entanglement sources and fidelity constraints on arbitrary network topologies.

Methodology
The authors propose a heuristic, three-stage pipeline that integrates classical networking tools with numerical optimization to solve the quantum RSA problem for arbitrary, repeater-less flex-grid networks. The pipeline operates as follows:

1. Phase 1: Low-Loss Route Discovery (Double Yen's Algorithm)
   To address the circular dependency between routing and spectrum allocation, the pipeline first determines routing candidates independent of spectrum constraints. It employs Yen's algorithm to identify the $N$ lowest-loss paths from every source to every user. For a specific source-link combination, this generates $N^2$ path pairs (one for each user in an entangled pair). The algorithm ranks these combinations based on a global efficiency metric (the product of path efficiencies) to select the most promising lightpaths. This step reduces the search space for the subsequent NP-hard phases.

2. Phase 2: Spectrum Allocation (Advanced Process Optimizer - APOPT)
   With fixed routes and source assignments, the problem reduces to the EFA problem: determining the optimal channel flux ($\mu$) and the number of frequency bin pairs ($K_\ell$) for each link to maximize distribution rates while satisfying fidelity constraints. The authors model this as a Mixed-Integer Nonlinear Programming (MINLP) problem. They utilize the Advanced Process Optimizer (APOPT), a solver designed for large-scale nonlinear problems, to maximize a logarithmic network utility function. This utility prioritizes high overall rates while preventing smaller links from being starved of resources. The optimization is subject to constraints on minimum fidelity ($F_\ell \geq f_\ell$) and per-source capacity limits.

3. Phase 3: Frequency Scheduling (CP-SAT Solver)
   In multi-source networks, assigning specific frequency bins is critical to prevent contention (i.e., different sources attempting to use the same frequency on the same network edge). The pipeline uses a Constraint Programming solver with Satisfiability methods (CP-SAT) to assign specific frequency bins to the allocated slots. This solver handles the discrete nature of the problem and backtracks if contention is detected. If a contention-free solution cannot be found for the current routing configuration, the pipeline iterates by selecting the next-best route combination from Phase 1 and re-running the optimization.

Key Contributions

• Generalized Pipeline: The work introduces the first heuristic workflow capable of solving quantum RSA for arbitrary topologies with multiple entanglement sources and fidelity constraints, moving beyond the limitations of single-source star topologies.
• Algorithmic Integration: The paper demonstrates the effective integration of Yen's algorithm (for routing), APOPT (for continuous/nonlinear resource allocation), and CP-SAT (for discrete scheduling) to tackle a problem that is strongly NP-hard.
• Performance Improvements: The approach replaces slow genetic algorithm methods with a pipeline that offers significant gains in speed, accuracy, and scalability.

Results
The authors numerically demonstrated the pipeline on two distinct network topologies:

1. Ring Topology: A 7-source, 24-user ring network. The pipeline found a contention-free solution in 0.498 seconds, achieving a network utility of 73.2 (compared to an infinite-resource upper bound of 73.9). Individual link rates averaged 89.2% of their theoretical maxima.
2. Manhattan ILEC Topology: A 3-source, 14-user network modeled after an incumbent local exchange carrier. The pipeline solved this in 0.283 seconds, reaching a utility of 51.1 (bound: 51.3) with an average link rate of 93.7% of the maximum.

In a pathological case designed to induce severe bandwidth contention, the pipeline successfully identified a valid solution after evaluating the 20th route configuration in 0.241 seconds.

Comparisons with the Genetic Algorithm (GA) approach from prior work (specifically on a star network scenario) showed that the APOPT-based pipeline achieved comparable or superior utility values in significantly less time (e.g., 0.36s vs. 24s for a specific scenario).

Significance and Claims
The paper claims that this pipeline provides an efficient, scalable heuristic for optimizing broadband entanglement distribution in arbitrarily connected quantum networks integrated within existing lightwave infrastructure. By solving the routing and spectrum allocation problem in under 0.5 seconds on a standard laptop, the method enables the practical management of complex, multi-source quantum networks without the computational overhead of exhaustive search or slow evolutionary algorithms. The authors note that while global optimality cannot be guaranteed without exhaustive search, the results are empirically close to asymptotic maxima, suggesting the approach is viable for real-world deployment. The work is presented as a foundational step for managing resources in the emerging era of quantum internet testbeds.