⚛️ quantum physics

On Utility-optimal Entanglement Routing in Quantum Networks

This paper proposes a Mixed-Integer Convex Program formulation and efficient randomized heuristics to solve the utility-optimal entanglement routing problem in quantum networks, thereby extending classical flow-based routing concepts to determine optimal paths that maximize network utility without relying on predetermined routes.

Original authors: Sounak Kar, Arpan Mukhopadhyay

Published 2026-03-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Sounak Kar, Arpan Mukhopadhyay

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a future where the internet doesn't just send emails and cat videos, but teleports quantum information—the kind of data needed for unhackable communication and super-powerful computers. This is the "Quantum Internet."

But building this internet is tricky. In our current internet, data travels like water through pipes. If a pipe is clogged, you just send the water down a different pipe. In a quantum network, the "water" is entanglement (a spooky connection between particles), and the "pipes" are fiber optic cables.

Here is the problem: Entanglement is fragile. The longer the path, the weaker the connection gets. Also, the more people trying to use the same cable at once, the worse the connection becomes for everyone.

The paper you provided is about finding the best way to route these quantum connections so that everyone gets a fair, high-quality service.

The Core Problem: The "Pizza Delivery" Dilemma

Think of the quantum network as a pizza delivery service in a busy city.

The Customers: Users who want to send quantum data (Demands).
The Drivers: The quantum links (fiber cables).
The Pizza: The entangled particles.

In a normal network, you might just tell the driver, "Go the shortest way." But in a quantum network, the "shortest way" might be too crowded, making the pizza arrive cold (low quality/fidelity). Or, you might send a driver on a long, empty road, but they get stuck in traffic later.

The goal is to maximize "Network Utility." In plain English, this means: How happy are all the customers combined? We want to make sure everyone gets a decent slice of pizza, not just one person getting a whole pie while others get crumbs.

The Old Way vs. The New Way

The Old Way (The "Fixed Route" Assumption):
Previous research assumed that the routes were already decided. It was like saying, "Okay, Driver A must take Main Street, Driver B must take 5th Avenue. Now, let's figure out how fast they should drive."

The Flaw: What if Main Street is a parking lot? The old method couldn't fix that; it just accepted the bad route.

The New Way (This Paper):
The authors say, "Let's stop assuming the routes are fixed. Let's figure out the best possible routes and the best speed simultaneously to make everyone happiest."

The Challenge: There are so many possible routes in a city (network) that checking every single one is impossible. It's like trying to find the perfect path through a maze by checking every single dead end. The number of paths grows so fast it breaks computers.

The Solution: The "Smart Map" and the "Gambler"

To solve this, the authors created two main tools:

1. The "Perfect Map" (The MICP)

They turned the problem into a giant, complex math puzzle called a Mixed-Integer Convex Program (MICP).

The Analogy: Imagine a super-smart GPS that doesn't just look at traffic, but also calculates how the weather, road quality, and driver mood affect the pizza temperature. It tries to find the perfect combination of routes and speeds.
The Catch: This "Perfect Map" is very heavy. It works great for small cities (small networks) or when the roads are very empty. But for a huge city like New York, the GPS might take years to calculate the answer.

2. The "Smart Gamblers" (The Heuristics)

Since the "Perfect Map" is too slow for big networks, the authors invented two "Smart Gamblers" (heuristics) to get a really good answer quickly.

Gambler A (Randomized Rounding):
- How it works: The "Perfect Map" gives a blurry, fractional answer (e.g., "Take 30% of Route A and 70% of Route B"). The Gambler looks at these percentages and says, "Okay, I'll flip a coin. 30% chance I take Route A, 70% chance I take Route B."
- The Result: It picks a single, clear path for each driver. It's fast and usually gets a very good result.
Gambler B (The "Min-Congestion" Strategy):
- How it works: This gambler looks at the map and asks, "Which route will cause the least traffic jams?" It tries to spread the drivers out so no single road gets overloaded.
- The Result: Surprisingly, this simple "avoid traffic" strategy often works better than the complex coin-flipping method, especially in real-world networks. It's faster and gets closer to the "Perfect Map" answer.

Why This Matters

The paper proves that their "Smart Gamblers" are incredibly accurate.

When they tested it on real-world network maps (like the backbone of the internet in Europe), their fast methods were 99.99% as good as the slow, perfect method.
They also proved that their math is "exact" in certain conditions, meaning no information is lost.

The Big Picture Takeaway

This research is like upgrading the traffic control system for the future Quantum Internet.

Fairness: It ensures that if you are sending a quantum message, you don't get a terrible connection just because someone else is using the network.
Efficiency: It finds the best paths automatically, so we don't waste precious quantum resources.
Scalability: It gives us a way to handle huge networks without our computers melting.

In short, they figured out how to route the "spooky" connections of the quantum world so that the future internet is fast, fair, and reliable for everyone.

1. Problem Statement

The paper addresses the Quantum Network Utility Maximization (QNUM) problem, specifically focusing on entanglement routing.

Context: Quantum networks aim to distribute quantum information (entanglement) between users. Unlike classical networks where the primary resource is transmission rate, quantum user utility depends on both the entanglement generation rate and the fidelity of the entangled state.
The Gap: Existing QNUM frameworks assume that routes for user demands are predetermined. The authors argue that to achieve true optimality, the network must jointly optimize the selection of routes and the allocation of resources (rate and fidelity).
The Challenge: The number of feasible paths between source-destination pairs grows exponentially with network size. A brute-force approach (evaluating QNUM for every possible route combination) is computationally intractable.
Objective: Formulate and solve the single-path utility-based entanglement routing problem to maximize the product of individual user utilities (network utility) by selecting optimal paths and resource allocations.

2. Methodology and Formulation

A. Network Model and Assumptions

Topology: Represented as a graph $G=(V, E)$ with $k$ source-destination (SD) demands.
Entanglement Generation: Uses the "single-click" protocol. Elementary links generate states that are converted to Werner states.
Rate-Fidelity Trade-off: There is an inverse relationship between the generation rate ( $\mu$ $μ$ ) and the Werner parameter ( $w$ $w$ , representing fidelity). Higher rates imply lower fidelity.
- $\mu_j = d_j(1 - w_j)$ , where $d_j$ is a link-specific constant.
End-to-End (E2E) Entanglement: Established via entanglement swapping. The E2E Werner parameter for a path is the product of the Werner parameters of the constituent links.
Utility Function: The utility of a demand $i$ is $x_i f_i(u_i)$ , where $x_i$ is the rate, $u_i$ is the E2E fidelity, and $f_i$ is an entanglement measure (Secret Key Fraction - SKF, Distillable Entanglement - DE, or Negativity).
Network Utility: Defined as the product of individual utilities: $U = \prod x_i f_i(u_i)$ .

B. Mathematical Formulation (MICP)

The authors formulate the problem as a Mixed-Integer Convex Program (MICP).

Direct Link-Based Formulation:
- Converts the undirected graph to a directed one.
- Introduces continuous variables for rate allocation ( $x_{ij'}$ ) and binary variables ( $y_{ij'}$ ) to indicate if a link is used by a demand.
- Enforces single-path constraints (flow conservation, no loops, exactly one path per demand) using binary variables.
Handling Non-Linearity:
- The objective involves products of rates and non-linear functions of fidelity.
- Log-Transformation: The objective is transformed by taking the logarithm (maximizing $\ln U$ is equivalent to maximizing $U$ ).
- Surrogate Variables: New variables are introduced to linearize the relationship between link usage and the E2E Werner parameter.
- Convexification:
  - The term $-\ln(\max x)$ is handled via perspective transformation.
  - The fidelity function $f_i$ is approximated. For Negativity, the function is naturally concave, making the formulation exact. For SKF and DE, a concave envelope ( $\hat{F}_i$ ) is used to approximate the function, introducing a negligible error.
Resulting MICP: The final formulation involves $2kl$ binary variables and $6kl + k + l$ continuous variables (where $k$ is demands, $l$ is links).

C. Scalability Solutions (Heuristics and Bounds)

Since MICP solvers struggle with large networks, the authors propose two approaches:

Approach 1: Convex Relaxation & Randomized Rounding

Upper Bound: Relax the binary constraints ( $y_{ij'} \in \{0,1\}$ ) to continuous ( $0 \le y_{ij'} \le 1$ ). Solving this convex relaxation provides an upper bound on the optimal utility.
Heuristic: Use Randomized Rounding. The fractional solution from the relaxation is interpreted as probabilities. A "path-stripping" algorithm samples valid routes based on these probabilities. Once routes are fixed, a standard convex QNUM problem is solved to find the optimal rates.

Approach 2: Min-Congestion Based (Proposed Alternative)

Motivation: The E2E fidelity depends heavily on link congestion (how many paths share a link).
Step 1 (LP): Solve a Linear Program (LP) to minimize the maximum congestion (the highest number of paths on any single link). This yields a lower bound on congestion $\lceil c \rceil$ .
Heuristic: Sample routes based on the min-congestion LP solution, then solve the convex QNUM for rates.
Upper Bound: Construct an "optimistic" scenario where all but one link have minimal congestion, and the single congested link carries $\lceil c \rceil$ paths. This reduces the problem to a smaller MICP with only $k$ binary variables (one per demand to decide if it uses the congested link), making it computationally much faster.

3. Key Contributions

Joint Optimization: First formulation to jointly optimize routes and resource allocations (rate/fidelity) for utility maximization in quantum networks, relaxing the fixed-route assumption of prior QNUM work.
Exact MICP Formulation: Developed an exact MICP for the Negativity entanglement measure and a highly accurate approximation ( $>99.99\%$ ) for SKF and DE.
Scalable Algorithms:
- Proposed a Randomized Rounding heuristic and upper bound based on convex relaxation.
- Introduced a novel Min-Congestion heuristic and upper bound.
Performance Validation: Demonstrated that the Min-Congestion approach is computationally faster and often yields better average performance and tighter upper bounds than the standard relaxation method on real-world topologies.

4. Numerical Results

The authors evaluated their methods on three real-world optical fiber network topologies from TopologyBench:

BREN (10 nodes, 11 links)
UNIC (15 nodes, 17 links)
ARNES (17 nodes, 20 links)

Key Findings:

Accuracy: The approximation error for SKF and DE was empirically found to be less than 0.00051%, validating the concave envelope approximation.
Heuristic Performance: The Min-Congestion (MC) heuristic consistently outperformed the standard randomized rounding heuristic in terms of achieved network utility.
Upper Bound Tightness: The MC-based upper bound was often closer to the true optimum (MICP solution) than the standard relaxation bound.
Efficiency: The MC-based approach required solving a significantly smaller MICP (only $k$ binary variables vs. $2kl$) in the second step, making it more scalable.

5. Significance

Bridging Classical and Quantum: The work successfully extends classical flow-based routing and Quality of Service (QoS) concepts (like min-congestion routing) to the unique constraints of quantum networks (fidelity-rate trade-offs).
Practical Framework: It provides a rigorous mathematical framework for designing future quantum internet protocols that ensure fairness and efficiency in resource distribution.
Scalability: By offering computationally efficient heuristics that closely approximate the optimal solution, the paper makes the utility-based routing problem solvable for networks of practical size, moving beyond theoretical toy models.