Column Generation for the Optimization of Switching in Repeaterless Quantum Networks
arXiv:2604.20338v1 [quant-ph] 22 Apr 2026
Álvaro Troyano Olivas∗‡ , Andrés Agustı́ Casado† , Hans H. Brunner‡ , Chi-Hang Fred Fung‡ , Momtchil Peev‡ , Laura Ortiz∗ , and Vicente Martin∗ ∗ Center for Computational Simulation, Universidad Politécnica de Madrid, Madrid, Spain † Departamento de Fı́sica Teórica, Universidad Autónoma de Madrid, Madrid, Spain ‡ Munich Research Center, Huawei Technologies Duesseldorf GmbH, Munich, Germany [email protected]
Abstract—Efficient resource allocation and optical switching promise high key rates, network adaptability, and cost reduction in repeaterless quantum communication networks. However, identifying optimal switching configurations remains a significant challenge due to the combinatorial complexity. We introduce a novel graph formulation to model the physical and logical structure of repeaterless quantum networks, enabling the systematic optimization of switching strategies. The problem is posed as a linear program and solved using a column generation approach. This method enables scalable computation despite the exponential number of possible network configurations. Our results not only provide a formal foundation but also a practical algorithm for the optimization of switching. Empirical tests confirm the solver’s scalability with network size, demonstrating the framework’s effectiveness and laying the groundwork for future optimization of quantum network control. Index Terms—Repeaterless quantum communication; QKD; QKD networks; switched QKD; optimization; column generation
I. I NTRODUCTION Quantum communication networks are rapidly evolving from laboratory experiments into operational infrastructures that enable unprecedented capabilities, e.g., secure information transfer through quantum key distribution [1]. Recent testbeds such as MadQCI [2] have demonstrated the feasibility of deploying these networks with flexible management of quantum and classical resources. A key element for the performance of such quantum networks is the ability to dynamically switch among key generation paths or configurations to optimize key generation rates, enhance network resilience, and ensure service continuity [3]–[5]. Architectures like such with quantum reconfigurable optical add-drop multiplexers (q-ROADMs) [6] are paving the way for scalable, flexible, and cost-efficient repeaterless quantum networks. However, determining optimal switching strategies in these dynamic systems remains a significant and unresolved challenge. In this contribution, we address this gap by developing a mathematical framework based on graph theory. This framework models the physical structure of a repeaterless quantum network and determines how and when to perform switching of quantum links. It also allows for the enumeration of all network configurations (i.e. each particular way to allocate
the network resources), an unsolved problem, to the best of our knowledge. Within this framework, we pose the switching optimization as a linear program [7]. To ensure scalability, we devise a solution method based on column generation, which efficiently handles the problem’s inherent complexity. This approach contrasts with prior works [8], [9] that pose the problem as a computationally hard mixed integer linear program [7] and lack a formal modeling foundation. Our analysis shows that the number of solver iterations required by the proposed algorithm scales roughly quadratically with the size of the network (this is, number of transmitters, receivers, switches and edges). This quadratic growth is unaffected when the number of switches in the network is fixed. Linear scaling is achieved when either the number of transmitters or receivers is fixed. However, each iteration solves an integer subproblem, which is worst case exponential time. The paper is structured as follows: Section II states the problem and defines the mathematical framework. Section III details the linear optimization model. Section IV presents our scaling analysis, and Section V concludes with directions for future research. II. P ROBLEM S ETUP The problem we address in this work is defined as follows: Given a reconfigurable (switched), repeaterless quantum communication network consisting of transmitters and receivers with the capability to form various feasible pairs and known average key generation rates, the objective is to determine the optimal distribution of network configurations over a specified time period. In this section we establish the mathematical foundation required to formalize this optimization. Definition 1 (Raw Network Graph). A raw network graph G = (V, E) is a directed graph with E = {(u, v) : u, v ∈ V } the set of arcs (directed edges) and V = T ∪ R ∪ S consisting of 3 types of nodes (which we will refer to as vertices onward): transmitters (T ), receivers (R), and switches (S). We assume no ingoing edges exist for a transmitter and no outgoing edges for a receiver.
of all realizable transmitter-receiver pairs in the raw network graph. In the context of the present problem, we need to define network configurations, since the optimization concerns them directly.
Fig. 1. An example of a raw network graph, with transmitters shown as empty round vertices, receivers as filled round vertices and switches as square vertices.
Definition 4 (Network Configuration). Let G = (T ∪S∪R, E) be a raw network graph. A network configuration is a set M̃ of pairwise edge disjoint simple TR-paths in G such that 1) For every transmitter t ∈ T , at most a single path p ∈ M̃ contains an edge with t. 2) For every receiver r ∈ R, at most a single path p ∈ M̃ contains an edge with r. Note that a configuration is exactly a flow in the raw network graph G setting each edge in G to have unit capacity, and considering nodes in T to be sources and nodes in R to be sinks. Proposition 1 (Network Configuration). A network configuration in the raw network graph G = (T ∪ R ∪ S, E) is a mapping M : E → {0, 1} such that, 1) For every t ∈ T : X X −1 ≤ M (u, t) − M (t, v) ≤ 0 (u,t)∈E
Fig. 2. A simple path in an example raw network graph, shown as orange edges.
This framework can be extended to directed multigraphs, but without loss of generality and to simplify the notation we will assume the underlying graph is a digraph. For an example of a raw network graph, the reader is referred to Fig. 1. Definition 2 (TR-Path). A TR-path p in a raw network graph G = (V, E), from transmitter t ∈ T to receiver r ∈ R, is a set of connected edges p = {(t, s1 ), (s1 , s2 ) . . . (sn , r)},
(1)
where e1 = (t, s1 ) ∈ E, ei = (si−1 , si ) ∈ E and en+1 = (sn , r) ∈ E. A TR-path p is a simple path if all vertices in p are distinct. Following path p, each vertex will only be visited at most one time, i.e., it is a loop-free path. In this work we will assume that the desirable (in the sense of useful for the optimization) paths are simple TR-paths, and hence, the word path will be used to refer to a simple TRpath. For an example of a simple path, the reader is referred to Fig. 2. Definition 3 (Link and Set of all Links). A transmitter-receiver pair is realizable if a TR-path exists that connects them. Such a realizable pair might also be called link. The set L is the set
(4)
(r,v)∈E
3) For every s ∈ S: X X M (u, s) − M (s, v) = 0 (u,s)∈E
(3)
(t,v)∈E
2) For every r ∈ R: X X 0≤ M (u, r) − M (r, v) ≤ 1 (u,r)∈E
(2)
(5)
(s,v)∈E
This corresponds to a unit capacity flow in graph G. A proof for proposition 1 can be found in appendix A. A. Weighted Key Capacity as Path Weights Given a raw network graph G = (V, E), we will allow every edge e ∈ E to have a channel attenuation αe in decibel. The secret key capacity of a path can then be calculated with the rate-loss scaling of repeaterless quantum communication defined in [10]. We will use a weighted secret key capacity as weight ωP (M,l) of the path for link l in configuration M : X αP (M,l) = αe , (6) e∈P (M,l)
( ωP (M,l) =
αP (M,l) , if P (M, l) ̸= ∅ −cl log2 1 − 10− 10 0, if P (M, l) = ∅. (7)
where P (M, l) is a function that gives the path in configuration M that connects the transmitter-receiver pair of link l. cl ≥ 0
is used as an additional weight to reflect the priority of a link [8]. In this contribution, the attenuation of the edges, the secret key capacity, and the link weights are assumed to be known constants.
We can linearize this objective by introducing an auxiliary variable k, which serves as a lower bound for the weighted per-link generation rate. The resulting linear program is: max
B. Link Buffers and Time Evolution Each link in the network (l ∈ L) has a finite buffer to store generated keys. This buffering allows keys to be consumed on demand, even when a link is not part of the active configuration. To prevent any buffer from depletion, the system must switch between different network configurations. This design effectively decouples the immediate demand for keys from the slower, time-consuming process of network reconfiguration. Key forwarding can establish end-to-end keys between any pair of nodes in trusted-node networks. Finding keyforwarding routes is a separate problem outside the scope of this work. We treat any forwarded key as a consumption demand on the individual links along its route. For our analysis, we normalize all parameters relative to the total duration of a configuration sequence. We assume the buffers are sufficiently large and initially filled such that a calculated non-negative average key gain guarantees a nonnegative gain over the evolution and prevents buffers from depletion. This allows us to analyze system behavior without tracking precise buffer levels over time. Although key generation pauses during switching, we consider the time required to switch to be negligible. This assumption is justified because sufficiently large buffers allow very low switching frequencies (e.g, no more than once per hour). III. L INEAR M ODEL We formulate the optimization problem using a linear program based on the raw network graph model. Over a given finite time period, we seek to determine the fractions of time λM that the network should operate in each configuration M ∈ M to maximize a chosen objective, where M denotes the set of all possible network configurations. These P P fractions need to sum to one: M ∈M λM = 1, where M ∈M (•) denotes summing over all possible values of M (so all possible configurations). We define the total amount of weighted key generation rate in link l ∈ L as X bl = λM ωP (M,l) , (8) M ∈{M ∈M:l∈M }
where l ∈ M denotes link l being realized by configuration M. Among various possible objective functions, we adopt the max-min optimization strategy to maximize the minimum weighted key generation rate across all links: X max min λM ωP (M,l) . (9) P λM ≥0,
M ∈M λM =1
l∈L
M ∈{M ∈M:l∈M }
λM ≥0
k
(10) X
s.t.
ωP (M,l) λM ≥ k
∀ l ∈ L,
M ∈{M ∈M:l∈M }
X
λM = 1.
M
In regard to the physical meaning, k can be viewed as a measure of the maximum weighted per-link consumption rate supported by the network for a given strategy [8]. A. Complexity of Column Enumeration The reader should note that this problem scales poorly, due to the exponential number of configurations (λM variables). Intuitively, this is because a configuration is essentially a set of edge disjoint paths. The number of configurations is lower bounded by the number of paths themselves, because each path alone forms a network configurations, respectively. The number of simple paths in a graph is, in the worst case, exponential in the number of edges (O(exp(|E|))). In the worst case, the number of configurations is the number of subsets of the set of all simple paths, the size of its power set (2β exp(|E|) with β exp(|E|) simple paths). This number is an upper bound in networks with active edge-disjointness requirements, but the exponential relationship still establishes that the search space is too large for a brute-force solution approach. Acknowledging that some configurations supersede other configurations might be a good way to reduce the search space. However, this does not necessarily reduce the computational complexity of identifying the relevant configurations, since still, an exponential amount could exist. B. Solving the Problem The exponential number of variables in problem (10) makes a full enumeration of all constraint matrix columns computationally infeasible. We therefore employ column generation [7], an algorithm designed to tractably solve such large-scale linear programs. The method operates by iteratively solving a restricted master problem (RMP), which is the original problem posed on only a subset of variables or columns. We define this restricted set of columns (configurations) as M ⊂ M. In each iteration, a pricing problem is solved to identify a new column outside of M to be added to the RMP. The selection of the new column is based on the reduced cost, the benefit of adding this variable to the current pseudo optimal basis. Column generation is an exact algorithm, guaranteeing convergence to the optimal solution. However, it provides no a priori bound on the number of iterations it requires to converge to this optimum.
The RMP is given by λM ≥0
k
(11) X
s.t.
ωP (M,l) λM ≥ k
∀ l ∈ L,
Average number of iterations
max
80
(12)
M ∈{M ∈M:l∈M }
X
λM = 1.
(13)
M ∈M
To leverage the column generation framework, we need the dual of the original RMP. By associating dual variables µl , l ∈ L, to constraints (12) and γ to the convexity constraint (13), the dual program can be found as min
µl ≥0
s.t.
γ X
60 50 40 30 20 10 0
2
ωP (M,l) µl ≤ γ
∀ M ∈ M,
(15)
µl ≥ 1.
(16)
3
4
5
6
7
8
9
Number of transmitters |T |
(14)
l∈M
X
|T | = |R| = |S|
70
Fig. 3. Mean number of iterations required to solve the optimization for random raw network graphs as a function of network size. The number of transmitters equals the number of receivers and switches. Each data point represents the average over 15 graph instances.
l∈L
To solve problem (11) with column generation, we need a pricing problem that at each iteration gives the column (or new configuration, not in the RMP) with the most positive reduced cost. For this, we want to find the configuration that maximally violates constraint (15). In essence, we would like to solve X max ωP (M,l) µl (17) M
s.t.
l∈M
X
ωP (M,l) µl > γ.
(18)
l∈M
Constraint (18) is in place because adding a column to the RMP with negative or zero reduced cost would not change the optimal solution, and hence, stall our iterative column generation. If the pricing problem is unfeasible, we will stop as we have found the optimum. 1) Pricing Problem Derivation: A possible formulation for the pricing problem is the following one. Since we can think of a configuration as an edge disjoint path set, we can encode a configuration using some binary variables yp ∈ {0, 1} where p is a path connecting the transmitter-receiver pair (t, r) of link l. Its value is 1 if the path is part of the configuration, 0 otherwise. However, we need to enforce several constraints to encode a compliant network configuration; let P be the set of all paths, P (t,r) the set of all paths connecting t to r, and µp = µl , ∀p ∈ P (t,r) : • Maximum transmitter usage: A single transmitter t ∈ T should only be used once. This can be enforced as X X yp ≤ 1, ∀ t ∈ T. (19) r∈R p∈P (t,r) •
Maximum receiver usage: A completely analogous argument follows for receivers, X X yp ≤ 1, ∀ r ∈ R. (20) t∈T p∈P (t,r)
•
Maximum fiber (edge) usage: Equivalently, we can only use each fiber channel (directed edge) in the raw network graph at most once, X yp ≤ 1, ∀ e ∈ E. (21) p∈{p∈P :e∈p}
Hence, the full problem can be formulated as X max ωp µp yp yp ∈{0,1}
s.t.
(22)
p∈P
X
X
yp ≤ 1,
∀ t ∈ T,
yp ≤ 1,
∀ r ∈ R,
yp ≤ 1,
∀ e ∈ E.
r∈R p∈P (t,r)
X X t∈T p∈P (t,r)
X p∈{p∈P :e∈p}
IV. E MPIRICAL C OMPLEXITY A NALYSIS In this section, we present an empirical analysis of the optimization problem posed in Equation (11). Our methodology involves randomly generating raw network graphs, solving the optimization for each, and recording the number of iterations required by the column generation algorithm. We analyze the results under three distinct scenarios: full network growth, growth with a fixed number of receivers, and growth with a fixed number of switches. Fig. 3 displays the average iteration count as the entire network scales (i.e., the number of transmitters, receivers and switches all increase). The relationship exhibits non-linear growth. To understand this behavior, we consider the other two scenarios. When the number of receivers is held constant (Fig. 4), the number of iterations scales linearly with the number of transmitters and switches. This linear trend suggests that the non-linearity in the full-growth case is not inherent to the algorithm’s core mechanics. We hypothesize that it stems from the
V. C ONCLUSIONS
30 Average number of iterations
|T | = |S|, |R| = 5 25 20 15 10 5
2
3
4
5
6
7
8
Number of transmitters |T | Fig. 4. Mean number of iterations required to solve the optimization for random raw network graphs as a function of network size, while the number of receivers is held fixed at 5. Each data point represents the average over 15 graph instances.
Average number of iterations
35 |T | = |R|, |S| = 5
30
VI. ACKNOWLEDGEMENTS
25 20 15 10 5 0
In this work, we developed a mathematical optimization framework to characterize the switching configurations of a repeaterless quantum network. Our results demonstrate that the column generation approach is a powerful method for optimizing these networks, effectively solving a linear program with an exponential number of variables. While the pricing problem inside of the column generation is computationally expensive, solving this problem is substantially more tractable than a full enumeration of all possible network configurations. Future work should address the exploration of heuristic approaches for solving the pricing problem. A fast approximation could dramatically accelerate convergence, making the approach viable for industrial protocols. Additionally, time-dependent, statistical, and stochastic consumption and generation models should be investigated as well as the actual filling of the link buffers. A more realistic model of switching time between configurations should be integrated. Moreover, extending the mathematical framework to accommodate advanced protocols, such as multi-party key distribution [11], [12], represents a significant opportunity for future research.
2
3
4
5
6
Number of transmitters |T |
The authors would like to thank projects EU Horizon Europe project “Quantum Secure Networks Partnership” (QSNP), grant 101114043; the project “MADQuantum-CM”, funded by Comunidad de Madrid (Programa de Acciones Complementarias) and by the Recovery, Transformation and Resilience Plan—Funded by the European Union—NextGenerationEU (PRTRC17.I1) and the project “CAM Programa TEC2024/COM-84 QUITEMAD-CM”. A PPENDIX A P ROOF FOR P ROPOSITION 1
Fig. 5. Mean number of iterations required to solve the optimization for random raw network graphs as a function of network size, while the number of switches is held fixed at 5. Each data point represents the average over 15 graph instances.
We prove that a mapping M : E → {0, 1} that verifies equations (3), (4) and (5) is a network configuration if and only if the set M̃ = {{(t, s1 ), (s1 , s2 ), . . . (sk , r) : M (t, s1 ) = M (si−1 , si ) = M (sk , r) = 1}, ∀ t ∈ T, r ∈ R} is congruent with definition 4.
combinatorial increase in the number of possible transmitterreceiver pairs, which scales quadratically as |T | · |R|.
Proof. Let G = (T ∪ R ∪ S, E) be a raw network graph.
This hypothesis is further supported by the results in Fig. 5, which shows non-linear growth when the number of switches is constant but the number of transmitters and receivers increases. As we previously mentioned, given the linear growth when the number of receivers is constant, this non-linear growth could be explained by the quadratic increase in the possible number of transmitter-receiver pairs.
( =⇒ ) Let M : E → {0, 1} be a mapping in G such that it verifies equations (3), (4) and (5). PLet t ∈ T . Since no ingoing edges exist for a transmitter, (u,t)∈E M (u, t) = 0, Equation (3) simplifies to X −1 ≤ − M (t, v) ≤ 0. (23)
Although the number of column-generation iterations is well-behaved, each iteration requires solving the pricing problem given in Equation (22). This is a constrained binary optimization problem that is, in the worst case, exponential to solve in both time and computational steps. Efficient exact methods and fast heuristics for this subproblem exist, but their consideration falls beyond the scope of this contribution.
So at most a single (t, v) edge can exist in M̃ (for a particular t ∈ T , and some other node v ∈ S ∪ R). Furthermore, let r P ∈ R. Again, since no outgoing edges exist for a receiver, (r,v)∈E M (r, v) = 0, Equation (4) simplifies to X 0≤ M (u, r) ≤ 1. (24)
(t,v)∈E
(u,r)∈E
Hence at most a single (u, r) can exist in M̃ (for a particular r ∈ R and some node u ∈ T ∪ S). Finally, Equation (5) ensures that if a path reaches a switch on a dedicated edge, it must leave that same switch on a dedicated edge. Only transmitters can be sources and only receivers can be sinks of a flow in G. Every flow starts with a dedicated edge and, therefore, can only follow dedicated edges. This forms a set of edge disjoint simple paths, such that a transmitter can only pertain in a single one of them (equivalently for receivers). ( ⇐= ) Let M̃ be a network configuration. Construct the mapping M : E → {0, 1} where M (e) = 1 ⇐⇒ e ∈ p for some p ∈ M̃ . Then, for every t ∈ T , at most one path has t as its source and no path has t as its sink, so Equation (3) holds. Similarly, for every r ∈ R, at most one path contains r as its target and no path contains r as source, so Equation (4) holds. Finally, for every s that some path contains, Equation (5) holds because a path is a set of dedicated and connected edges (and so, if a node in S is reached, it must be left). R EFERENCES [1] V. Martin, J. Martinez-Mateo, and M. Peev, “Introduction to quantum key distribution,” in Wiley Encyclopedia of Electrical and Electronics Engineering. John Wiley & Sons, Ltd, 2017. [2] V. Martin et al., “MadQCI: a heterogeneous and scalable SDN-QKD network deployed in production facilities,” npj Quantum Information, vol. 10, no. 1, p. 80, Sep 2024. [3] D. R. Lopez et al., “Demonstration of software defined network services utilizing quantum key distribution fully integrated with standard telecommunication network,” Quantum Reports, vol. 2, no. 3, pp. 453– 458, Sep. 2020. [4] J. Martinez-Mateo, A. Ciurana, and V. Martin, “Quantum key distribution based on selective post-processing in passive optical networks,” IEEE Photonics Technology Letters, vol. 26, no. 9, pp. 881–884, 2014. [5] H. H. Brunner et al., “Demonstration of a switched CV-QKD network,” EPJ Quantum Technology, vol. 10, no. 38, Sep. 2023. [6] R. Wang et al., “End-to-end quantum secured inter-domain 5G service orchestration over dynamically switched flex-grid optical networks enabled by a q-ROADM,” Journal of Lightwave Technology, vol. 38, no. 1, pp. 139–149, 2020. [7] M. Conforti, G. Cornuéjols, and G. Zambelli, Integer Programming, ser. Graduate Texts in Mathematics. Cham, Switzerland: Springer, 2014, vol. 271. [8] K. Christodoulopoulos, N. Makris, G. T. Kanellos, and D. Syvridis, “Optimizing key consumption in switched QKD networks,” in 2024 Optical Fiber Communications Conference and Exhibition (OFC), Mar. 2024. [9] A. Selentis-Boulntadakis, K. Christodoulopoulos, and G. T. Kanellos, “Relayed vs. switched QKD: a comparison in non-uniform ring networks,” in 2025 International Conference on Optical Network Design and Modeling (ONDM), 2025. [10] S. Pirandola, R. Laurenza, C. Ottaviani, and L. Banchi, “Fundamental limits of repeaterless quantum communications,” Nature Communications, vol. 8, p. 15043, Apr. 2017. [11] A. A. E. Hajomer, I. Derkach, R. Filip, U. L. Andersen, V. C. Usenko, and T. Gehring, “Continuous-variable quantum passive optical network,” Light: Science & Applications, vol. 13, no. 1, Oct. 2024. [Online]. Available: http://dx.doi.org/10.1038/s41377-024-01633-9 [12] Y. Bian, Y.-C. Zhang, C. Zhou, S. Yu, Z. Li, and H. Guo, “High-rate point-to-multipoint quantum key distribution using coherent states,” 2023. [Online]. Available: https://arxiv.org/abs/2302.02391