Measurement-Device Placement in MDI-QKD Networks with Minimal Trusted Relays Tianqu Luo
Ibrahim Arslantas
Sezin Ozturk
Qiaolun Zhang
arXiv:2609.06603v1 [cs.NI] 6 Sep 2026
Politecnico di Milano, Italy Politecnico di Milano, Italy Politecnico di Milano, Italy Politecnico di Milano, Italy [email protected] [email protected] [email protected] [email protected] Corresponding author
Alberto Sebastián-Lombraña
Mehdi Bolourian
Jiaheng Xiong
Universidad Politécnica de Madrid, Spain Center for Computational Simulation, Madrid, Spain [email protected]
University of Waterloo, Canada [email protected]
Politecnico di Milano, Italy [email protected]
Francesco Musumeci
Vicente Martı́n
Raouf Boutaba
Politecnico di Milano, Italy [email protected]
Universidad Politécnica de Madrid, Spain Center for Computational Simulation, Madrid, Spain [email protected]
University of Waterloo, Canada [email protected]
Massimo Tornatore Politecnico di Milano, Italy [email protected]
Abstract—Measurement-Device-Independent Quantum Key Distribution (MDI-QKD) removes detector side-channel vulnerabilities by delegating measurements to an untrusted relay that, when shared by several user pairs, acts as a Bell-state measurement (BSM) hub. Channel loss still limits the reach of MDI-QKD links, so long-range services rely on trusted relays for key forwarding. As MDI-QKD moves toward metropolitan deployment, a key network-planning question arises: how should BSM hubs be placed on existing fiber infrastructure to minimize the use of trusted relays? In this work, we formalize this challenge as the MDI-QKD Hub Deployment (MHD) problem. We first prove that the MHD problem is NP-hard, and then formulate it as a Mixed-Integer Linear Programming (MILP). To the best of our knowledge, this is the first formulation for MDIQKD network planning that captures the structural features specific to MDI-QKD, namely a shared BSM hub, two-link user-to-hub routing, and loss-balancing constraints, while jointly determining hub placement, user-to-hub assignment, and trustedrelay demand allocation. Our solution accounts for realistic budget and capacity constraints, including practical insights from real-world deployments of commercial MDI-QKD solutions. Numerical evaluations on three metropolitan topologies (12 to 50 nodes) at realistic geographic distances show that topology structure governs trusted-relay demand: hub placement alone eliminates all trusted relays in compact urban meshes, while in sparse topologies, relaxing the loss-balancing constraint removes the dominant source of trusted-relay usage at no additional infrastructure cost. The key-rate threshold at which trusted relays first appear shifts monotonically with the network diameter, i.e., the largest shortest-path distance between any node pair in fiber kilometers, delineating the feasibility boundary of pure MDIQKD deployment. Index Terms—Measurement-device-independent QKD, trusted relay, mixed-integer linear programming, network planning
I. I NTRODUCTION Quantum key distribution (QKD) can provide informationtheoretically secure key exchange [1]–[3], but its transmission range is limited by channel losses [3]. To extend QKD services over metropolitan and backbone networks, current deployments rely on trusted relay nodes that forward keys hop by hop [4], at the cost of introducing additional security assumptions at each relay. The need to extend QKD services beyond point-to-point links has motivated substantial effort toward integrating QKD into optical fiber infrastructures, including studies on resource allocation, routing, and key-rate optimization in networked settings [5]–[7]. Over the past two decades, QKD technology has progressed from laboratory experiments to deployed metropolitan and backbone networks, confirming its practical viability for securing critical communications. Currently, several efforts for the deployment of quantum network infrastructures to support QKD-enabled secure communications are ongoing, such as those related to the EuroQCI initiative [8]– [10]. Nevertheless, the information-theoretic security of QKD assumes that detectors behave as ideal single-photon counters. Real-world detectors deviate from this model through imperfections such as efficiency mismatch, dead time, and afterpulsing [11], and they remain vulnerable to active attacks such as detector blinding [12], all of which open side channels that can completely compromise security. MeasurementDevice-Independent QKD (MDI-QKD) [11], [13] overcomes
this vulnerability by delegating all measurements to an untrusted relay performing Bell-state measurements (BSMs), thereby removing detector side channels. Since its introduction, MDI-QKD has been experimentally demonstrated over long fiber distances [14] and in metropolitan-scale optical networks [15], including coexistence with classical data traffic [16]. Some commercial MDI-QKD systems, notably those by Q*Bird [16], [17], employ a shared measurement relay that can serve multiple user pairs, effectively functioning as a central hub. These advances naturally raise a network design question: how should BSM hubs be placed on existing fiber infrastructure to minimize the use of trusted relays while delivering longrange QKD services? This can be viewed as a hub location problem [18], [19], where each hub denotes a shared BSM relay serving multiple user pairs, but with several constraints specific to MDI-QKD. First, communication between two users is realized via a two-link connection to a shared relay, i.e., each user independently establishes a quantum channel to the same BSM hub. Second, the achievable secret key rate decays rapidly with channel loss, which effectively limits the maximum transmission distance. Third, practical MDIQKD performance is sensitive to imbalance between the two paths from the user pair to the BSM hub. For a given user pair (conventionally referred to as Alice and Bob), significant mismatch between the two optical paths to the same BSM hub degrades two-photon interference (i.e., the Hong-Ou-Mandel interference [20] that enables BSM) and reduces the achievable key rate. A common approach is therefore to compensate this asymmetry by adding attenuation to the lower-loss path, effectively enforcing balanced end-to-end losses. In this work, we adopt this symmetric approach [15], [16] and treat loss equalization as a deployment constraint: a user pair can be assigned to a BSM hub only if the two paths from the users to that hub can be loss-balanced, by attenuating the lower-loss path, without pushing the effective distance beyond the key-rate threshold. Because balancing always raises both channels to the higher-loss level, hub placements with highly asymmetric user-to-hub paths may become infeasible even when each individual channel is within range. This assumption captures standard experimental practice and enables a tractable optimization formulation, though it does not cover asymmetric MDI-QKD protocols [21], [22]. As interest in MDI-QKD network deployment grows, a network planning model that captures realistic deployment constraints becomes essential to optimize both infrastructure placement and ongoing service provision. Prior studies on MDI-QKD deployment rely on simplified system models: Cao et al. [23] select relay types along predetermined paths without jointly modeling hub placement and routing, while Jia et al. [24] and He et al. [25] employ heuristic frameworks that do not model the two-link user-to-hub routing structure or realistic budget and capacity constraints. On the other hand, ILP and MILP formulations for adjacent quantum-network problems, such as repeater placement [26] and resource placement [27], do not capture the constraints specific to MDI-
QKD, namely a two-link connection to a shared BSM hub, distance-dependent key-rate decay, and loss-balancing constraints on the two user-to-hub paths. As a result, no existing framework jointly addresses hub placement, two-link userto-hub routing, and trusted-relay assignment under realistic deployment constraints. The contributions of this study can be summarized as follows. • Problem formulation and complexity. We introduce the MDI-QKD Hub Deployment (MHD) problem, which jointly determines the placement of BSM hubs in the fiber-based QKD network, the assignment of user pairs to those hubs, and the use of trusted-relay paths when direct MDI-QKD is infeasible, so as to satisfy the expected service demand under operational conditions. We show that the MHD problem is NP-hard. • MILP-based optimal design. We formulate the MHD problem as a Mixed-Integer Linear Programming (MILP) model that explicitly captures the two-link connection to a shared relay of MDI-QKD connections under lossbalancing constraints. Channel asymmetry is handled via a loss-balancing constraint based on passive attenuation, yielding a tractable yet physically grounded approximation. The resulting formulation can be solved to optimality for metropolitan-scale deployments. • Network-level insights. Through simulations on three metropolitan topologies (12 to 50 nodes) at realistic geographic distances under three candidate placement strategies of increasing density, we show that topology structure governs trusted-relay demand: compact meshes eliminate all trusted relays through hub placement alone, sparse topologies benefit substantially from relaxing the loss-balancing constraint, and the key-rate threshold at which trusted relays first appear shifts monotonically with network diameter, delineating explicit feasibility boundaries for deployment planning. II. R ELATED W ORK Metropolitan and backbone QKD networks have been deployed in multiple continents, from the DARPA testbed in Boston [28], the SECOQC network in Vienna [29] and the Tokyo QKD network [30] to the 2,000 km Beijing–Shanghai backbone [31]. Although these deployments validated QKD in real-world settings, they relied on trusted intermediate nodes, each of which must be assumed secure since a compromise exposes the keys it relays. MDI-QKD eliminates detector sidechannel vulnerabilities by delegating measurements to an untrusted relay; recent deployments include a metropolitan MDIQKD network [15] and the Madrid quantum network [32], in both cases using a hub-based approach. A growing body of research is now focusing on how to efficiently allocate resources in QKD networks through mathematical optimization. ILP and MILP formulations have been proposed for quantum-repeater placement [26], resource placement [27], and joint routing and key-rate assignment [6], while other studies have investigated key management, resource
allocation, and finite-key security analyses [33]–[37]. These formulations target relay-chain architectures, whether trustednode key forwarding or quantum-repeater entanglement distribution, and thus do not apply to MDI-QKD, where each user pair connects to a shared BSM hub via two independent links. The few prior studies that target MDI-QKD-specific deployment [23]–[25] address only restricted subproblems and do not jointly model hub placement, two-link user-to-hub routing, and trusted-relay assignment under realistic constraints. III. S YSTEM M ODEL AND P ROBLEM S TATEMENT A. Network Model We model a metropolitan fiber-based QKD network as a directed graph G = (V, A), where V is the set of nodes and A is the set of directed arcs representing fiber links, each with physical length ℓa in kilometers. Each physical fiber link is represented by a pair of opposite directed arcs, hence the arc-set notation A rather than an undirected edge set. A set C denotes candidate hub locations where Bell-state measurement (BSM) equipment may be installed. The set C is determined by a candidate selection policy reflecting deployment constraints: • S1 (Fiber Midpoints): Candidates are placed at midpoints of existing fiber links (Fig. 1(a)), reusing splice points or amplifier sites without new facility construction. Under homogeneous fiber, such locations tend to reduce channel-loss asymmetry. • S2 (Fiber Midpoints + Network Nodes): Candidates include all S1 locations plus all network nodes V (Fig. 1(b)), additionally leveraging existing switching facilities for co-locating BSM equipment. • S3 (S2 + Geographic Midpoints): Candidates include all S2 locations plus the geographic midpoint of every non-adjacent node pair (up to |V2 | additional locations), subject to a minimum separation of 2 km (Fig. 1(c)); reaching these sites requires new fiber whose cost is not captured by B. Since the candidate hub locations C under S3 include all the candidate hub locations under S1 and S2, S3 provides a lower bound on achievable trusted-relay usage and helps distinguish topology-limited requests from distance-limited ones; it should therefore be read as a theoretical reference rather than a deployment option on an equal cost footing with S1 and S2. |R|
A set of key distribution requests R = {(sr , dr )}r=1 specifies source–destination pairs requiring quantum-distributed keys. Each request must be served either via an MDI-QKD connection through a BSM hub or, when such service is not feasible, via trusted-relay forwarding through existing network nodes under different security assumptions. These two options differ fundamentally in their trust model. A BSM hub is untrusted: it only performs the Bell-state measurement and publicly announces the outcome, learning nothing about the secret key, so compromising a hub does not expose key material. A trusted relay, in contrast, receives, stores, and re-forwards key bits and must therefore be trusted, since
TABLE I: MDI-QKD key rate as a function of total channel loss, expressed as effective distance deff [16], [17]. deff (km)
50
100
150
200
225
250
κ (bps)
1300
110
8.5
0.71
0.20
0.02
its compromise reveals every key it relays. We treat BSM hubs as intermediate measurement stations distinct from the communicating endpoints: a network node may host a BSM hub, but a user pair is never served by a hub co-located with either of its own endpoints. Since trusted-relay operation introduces additional trust assumptions at the relay nodes, the primary optimization objective is to minimize the number of requests served with trusted relays (TR). Deploying BSM equipment at a candidate location h incurs a fixed installation cost ch , and routing a user pair through an active hub incurs an additional per-connection cost cu . The aggregate deployment expenditure is bounded by a budget B. Each BSM unit can serve at most Kmax concurrent requests; deploying multiple units at the same site increases its capacity proportionally. B. Key-Rate Model and Deployment Assumptions In an MDI-QKD link, each of the two users (defined as Alice and Bob) acts as a transmitter, independently sending prepared quantum states through a dedicated fiber channel to a shared BSM hub whose detection apparatus serves as the receiver. The secret key rate is governed by the optical losses in these two transmitter-to-receiver channels. Under the decoystate MDI-QKD protocol [11], the asymptotic key rate per pulse is X Z Z R ≥ QZ (1) 11 1 − H(e11 ) − Qµµ fe H(Eµµ ), X where QZ 11 and e11 denote the single-photon gain and phaseZ error rate estimated via decoy-state analysis, QZ µµ and Eµµ are the overall gain and QBER, H(·) is the binary entropy function, and fe ≈ 1.16 is the error-correction inefficiency. In standard fibers with attenuation αdB ≈ 0.2 dB/km, channel transmittance decays exponentially with distance. In MDIQKD, the secret-key rate is highly sensitive to imbalance between the two user-to-BSM channels, because large asymmetry degrades the effective two-photon interference conditions at the relay and thereby limits performance. Consequently, BSM-hub placement is a critical design variable, as it directly determines the degree of channel-loss asymmetry. For tractability, rather than evaluating (1) for each candidate configuration, we follow [16] and model the key rate κ as a function of an effective distance deff :
κ = f (deff ),
viable iff κ ≥ κmin ,
(2)
where f (·) is implemented via interpolation over experimentally reported data points (50–250 km, 5 km spacing), links beyond the maximum tabulated reach dmax are treated as unreachable, and κmin is a minimum QoS threshold. Representative values are shown in Table I. The exponential decay reflects fiber attenuation at 1550 nm.
Fig. 1: Candidate hub locations under three placement strategies on a five-node example topology.
Throughout this work, path asymmetry is modeled only through the dominant loss mechanisms in fiber-based MDIQKD networks: fiber attenuation and node-bypass loss. Connector losses, splice losses, and other intermediate-node component losses are neglected; αdB could be easily increased to include the cumulative effect of these losses. For user i ∈ {A, B}, let di denote the fiber length from the user to the BSM hub, and let Ni denote the number of intermediate nodes traversed along that path. The corresponding channel loss is modeled as Li = di αdB + Ni bl (in dB), where αdB is the fiber attenuation coefficient and bl is the bypass loss incurred at each intermediate node. Based on these channel losses, we define the effective distance as deff =
2 max(LA , LB ), αdB
uncompensated model, with the effect concentrated in sparse topologies. Loss-uncompensated deployment. In this model, no lossbalancing is enforced: any BSM hub reachable within the key-rate threshold is admissible, regardless of the imbalance between the two user-to-hub paths. We retain the same key-rate model and evaluate the rate conservatively at the worse of the two channels through the effective distance deff = (2/αdB ) max(LA , LB ) of (3), which over-estimates the effective loss whenever the two paths differ. The resulting key rate is therefore a lower bound and the trusted-relay counts are conservative. The two deployment options thus differ only in candidate admissibility; neither models an asymmetric MDIQKD protocol.
(3)
which maps the larger of the two user-to-BSM channel losses to an equivalent end-to-end fiber distance, with the division by αdB (in dB/km) converting the loss in dB back into kilometers. Under loss-balanced operation, this expression reduces to the total equivalent distance across the two user-to-BSM paths. Deployment options. We consider two deployment options that differ in how channel-loss asymmetry is handled. Loss-compensated deployment. This deployment option assumes that channel-loss asymmetry can be actively mitigated (e.g., via optical attenuation or protocol-level compensation), so that the two-link connections from the user pair to the BSM hub operate under effectively balanced loss. We enforce |LA − LB | ≤ 2τ · αdB , which, under the homogeneous fiber assumption, is equivalent to |dA −dB | ≤ 2τ . We set τ = 3 km, corresponding to at most 1.2 dB of residual loss imbalance. This is consistent with typical optical penalty budgets and is conservative relative to prior theoretical analyses [38] and experimental demonstrations [15] showing robust MDI-QKD operation under significantly larger asymmetries. A sensitivity sweep over τ values between 1 and 10 km across the evaluated instances shows the expected monotone behavior, i.e., tightening the window increases trusted-relay usage while widening it gradually relaxes the deployment toward the loss-
C. Problem Statement Definition 1 (MDI-QKD Hub Deployment (MHD) Problem). The MHD problem can be formally stated as follows: given a fiber-based QKD network G = (V, A), candidate hub locations C, key distribution requests R, deployment budget B, per-hub capacity Kmax , and a key-rate function f (·) with minimum threshold κmin , determine a hub deployment H ⊆ C S(with multiplicities) and a routing assignment ϕ : R → r Pr , where Pr is the set of candidate serving paths for request r (defined formally in Section IV-A), that minimizes the number of requests served via trusted relays, i.e., |{r ∈ R : ϕ(r) is a trusted-relay path}|, subject to budget, hub capacity, arc capacity, and key-rate constraints. The MHD problem simultaneously decides where to deploy BSM equipment, how to route the quantum path across each user pair, and which pairs must use trusted relays. This joint optimization distinguishes it from sequential approaches that first fix hub locations and then optimize routing [24], [25]. We address the static planning phase, in which hub placement and the user-to-hub routing it must support are decided jointly and offline, prior to deployment; dynamic, per-session key routing over an already-provisioned infrastructure operates at a different time scale and is outside the scope of this work.
IV. MILP F ORMULATION
C. Constraints
A. Decision Variables and Parameters Following the model in Section III, the candidate path set for each request r is TR Pr = {pr,h | h ∈ C, κ(dr,h eff ) ≥ κmin } ∪ {pr },
(4)
where pr,h denotes the two-link MDI-QKD path through hub h and pTR r the path that uses trusted relay. We define the following decision variables: • Yh ∈ Z≥0 : number of BSM units deployed at candidate location h ∈ C. Multiple units at a single site increase its concurrent request-serving capacity, modeling scenarios where a facility hosts several BSM receivers. • Xr,p ∈ {0, 1}: equals 1 if request r ∈ R is assigned to path p ∈ Pr , and 0 otherwise. The model uses the following input parameters: Hub • δp,h ∈ {0, 1}: equals 1 if path p uses hub h for BSM. TR • δp ∈ {0, 1}: equals 1 if path p is a trusted-relay path. • ch : fixed cost for deploying BSM equipment at hub h. • cu : per-connection cost for each user pair routed through a hub. ch • np : number of quantum channels consumed by path p. • Kmax : maximum number of requests a single BSM unit can serve. • B: upper bound on aggregate hub deployment and connection cost. B. Objective Function MDI-QKD network planning involves three competing objectives: minimizing the number of requests that are served with trusted relays (security), minimizing deployment cost (economics), and minimizing quantum channel usage (resource efficiency). We combine these into a single weighted objective with lexicographic-style priorities: X X min α δpTR Xr,p r∈R p∈Pr
! +β
X
ch Yh + cu
h∈C
+γ
X X
X
nhub p Xr,p
r,p
nch p Xr,p ,
(5)
r∈R p∈Pr
P Hub where nhub = h∈C δp,h is the number of BSM hubs used p by path p. The weight hierarchy α = 1000 ≫ β = 1 ≫ γ = 0.001 enforces strict priority: security (TR minimization) is nonnegotiable, cost is secondary, and channel count is a tiebreaker. This choice makes the weighted objective equivalent to a strict lexicographic order (TR ≻ cost ≻ channels) refining the trusted-relay minimization objective of Definition 1: the cost term is Pbounded by βB = B < α and the channel term satisfies γ r,p nch p Xr,p < 1 across all evaluated instances, so the second and third terms together can never offset a singleunit change in the trusted-relay count.
Connectivity. Every request is served by exactly one path: X Xr,p = 1, ∀ r ∈ R. (6) p∈Pr
Hub activation. A path using hub h requires deployed BSM equipment: Xr,p ≤ Yh ,
Hub ∀ r, p, h : δp,h = 1.
(7)
This per-path formulation is tighter than big-M alternatives [18], producing a stronger LP relaxation. Hub capacity. Each BSM unit serves at most Kmax requests: X X Xr,p ≤ Kmax · Yh , ∀ h ∈ C. (8) r∈R p∈Pr Hub δp,h =1
Budget limit. X
ch Yh + cu
h∈C
X
nhub p Xr,p ≤ B.
(9)
r,p
Arc capacity. Each directed fiber arc carries at most W quantum channels: X X Xr,p ≤ W, ∀ a ∈ A, (10) r∈R p∈Pr Arc δp,a =1 Arc = 1 if path p uses arc a. This prevents overwhere δp,a subscription of quantum channels on shared fiber links. Key-rate prefiltering. Paths with κ(dpeff ) < κmin are excluded during path generation, keeping the MILP constraint matrix sparse.
D. NP-hardness of the MHD Problem We establish the computational hardness of the MHD problem by reduction from the Set Cover problem, a classical NPhard problem [39]. Theorem 1 (Computational Hardness). The decision version of the MHD problem is NP-complete: given a deployment budget B, it is NP-complete to determine whether there exists a feasible hub deployment under which all requests are served via MDI-QKD paths, i.e., no request needs a trusted relay. Proof. The MHD problem is in NP. Given a candidate hub deployment and routing assignment, feasibility can be verified in polynomial time by checking path assignment, hub activation, capacity, budget constraints, and counting the number of trusted-relay requests. NP-hardness. We reduce from the Set Cover problem [39], defined as follows: given a universe U = {u1 , . . . , um }, a collection of subsets S = {S1 , . . . , Sn } ⊆ 2U , and an integer k, determine whetherSthere exists a sub-collection I ⊆ S with |I| ≤ k such that S∈I S = U . Given a Set Cover instance (U, S, k), we construct an MHD problem instance as follows. Each element ui ∈ U is mapped to a request ri ∈ R. Each subset Sj ∈ S is mapped to a candidate hub hj ∈ C. Using a standard distance-threshold
TABLE II: Topology parameters for the three evaluation networks. Topology
|V |
|A|
Avg. ℓ (km)
Diam. (km)
Default B
Tokyo [30] Madrid [40] G50 [41]
12 13 50
38 26 176
8.2 8.7 9.2
30 61 84
50 50 50
construction, the network topology and key-rate parameters can be constructed in polynomial time so that request ri is reachable via hub hj if and only if ui ∈ Sj (e.g., place hj at distance L1 from both endpoints of ri if ui ∈ Sj and at distance L2 > L1 otherwise, with κmin set between κ(2L2 ) and κ(2L1 )). Hub costs are set to unity (ch = 1) with zero per-connection cost (cu = 0), the deployment budget is B = k, and the hub capacity Kmax = m and arc capacity W = m are chosen large enough to be non-binding. Suppose the Set Cover instance has a feasible solution I = {Sj1 , . . . , Sjk′ } with k ′ ≤ k covering all elements of U . Deploying hubs at {hj1 , . . . , hjk′ } routes every request ri through some hub hj with ui ∈ Sj , yielding zero trusted relays within budget B = k. Conversely, suppose the MHD problem instance admits a zero-TR deployment within budget B = k. Each request ri is served by some hub hj , which implies ui ∈ Sj . The set of activated hubs thus corresponds to a subcollection of S of size at most k that covers all of U . V. S IMULATION S ETUP We implement the MILP model in AMPL and solve it using IBM ILOG CPLEX 22.1. We evaluate the model across three metropolitan-scale fiber topologies, three candidate placement strategies, and both deployment models (loss-compensated and loss-uncompensated, as defined in Section III-B), varying the request load and the minimum key-rate requirement, both individually and jointly. A. Topologies We evaluate our MILP on three metropolitan-scale network topologies, summarized in Table II and visualized in Fig. 2, that span the range from dense urban core to large regional infrastructure. Table II summarizes the main parameters of the three evaluation topologies. Tokyo [30] and Madrid [32], [40] adopt the geographic distances of their real metropolitan fiber infrastructures. G50 [41] is a 50-node backbone topology whose link lengths are scaled to metropolitan working distances comparable to the other two topologies [42]. Throughout this work, the network diameter denotes the largest shortest-path distance between any node pair, measured in fiber kilometers rather than in hops, and therefore corresponds to the longest end-to-end span that a hub placement may have to cover. Tokyo is a dense urban mesh (average degree 3.2, diameter 30 km) in which all node pairs lie within MDI-QKD reach, serving as a baseline where hub placement alone can eliminate
TABLE III: Default MILP parameters used across all simulation scenarios. Parameter
Value
Description
ch cu Kmax κmin B dmax W bl α, β, γ
2.0 0.5 3 10 bps 50 250 km 20 0.5 dB 1000, 1, 0.001
BSM hub setup cost Per-use measurement cost Hub capacity (requests/unit) Min. key-rate threshold Default budget MDI-QKD reach limit Quantum channel capacity per arc Bypass loss per node Objective weights
all trusted relays. Madrid is a sparse, near-tree metropolitan network (average degree 2.0, diameter 61 km) derived from the MadQCI infrastructure, where limited path redundancy makes MDI-QKD coverage particularly sensitive to the deployment model. G50 provides metropolitan-scale link lengths comparable to those of Tokyo and Madrid but at a larger network diameter (84 km) and 50 nodes, enabling evaluation of scalability; some node pairs are structurally unreachable by MDI-QKD regardless of hub placement, revealing topologylimited performance floors. B. Simulation Scenarios Unless otherwise stated, all MILP instances use the baseline parameter values listed in Table III; each scenario below varies one of these parameters while the others remain at their default. The parameter values reflect commercial MDIQKD practice: Kmax = 3 matches the multiplexing capacity of deployed shared-relay systems [16]; the hub setup cost ch and per-use cost cu are normalized so that installing a BSM unit dominates per-connection usage; and the default budget B = 50 is chosen so that the budget constraint becomes binding at intermediate request loads rather than being trivially slack or globally infeasible. We design four simulation scenarios by varying key parameters while keeping all other parameters at their baseline values: • ExpA (Key-Rate Sweep): We vary κmin ∈ {10, 100, 200, 400, 700, 1000, 1300} bps with |R| = 20 to study how stricter key-rate thresholds affect relay deployment feasibility across topologies of different diameter. • ExpB (Joint Load and Key-Rate Sweep): We jointly vary |R| ∈ {5, . . . , 35} and κmin ∈ {10, 100, 200, 400, 700, 1000, 1300} bps to map the operating region of pure MDI-QKD deployment. • ExpC (Budget Sweep): We vary the budget B ∈ {15, 20, . . . , 50, 60, 75, 100} at |R| = 35 and κmin = 400 bps to identify the minimum investment required for a feasible pure MDI-QKD deployment. • ExpD (Network-Scale Sweep): We uniformly scale the G50 link lengths so that the network diameter spans 84 to 252 km, with |R| = 20 and κmin ∈ {10, 200, 400, 700, 1000} bps, to isolate the effect of geographic scale from that of topology structure.
(a) Tokyo (12 nodes, 19 links)
(b) Madrid (13 nodes, 13 links)
(c) G50 (50 nodes, 88 links; geographic layout, link lengths scaled by 0.09)
CEM
Adachi
Hamburg Bremen
Itabashi Nerima
Hannover
CETSE
Shinjuku
Edogawa
Bunkyo Chiyoda
Koto
Minato Setagaya Shinagawa
ETSIINF
ETSIT
CTB
RECT
CESTIC
Berlin
TORR.
ESPOL
Leipzig Düsseldorf
CSIC
Dresden Cologne
CCS CAIT
Frankfurt
Nuremberg
MARAN. Stuttgart
Ota 10 km
Munich 20 km
100 km
Fig. 2: The three evaluation topologies: (a) Tokyo, (b) Madrid, (c) G50. Topology parameters are listed in Table II.
Each scenario is executed for all three topologies, three candidate strategies (S1, S2, S3), and both deployment models (loss-compensated, loss-uncompensated), yielding 3 × 3 × 2 = 18 configurations per parameter point. All instances are solved with a per-instance time limit of 60 s. Across the evaluated instances, the median solve time is below one second and most complete within a few seconds; the exceptions are large loss-uncompensated instances, whose broad candidate-path sets enlarge the model. The MILP is solved to proven optimality for the majority of feasible instances, confirming that the per-path hub-activation formulation is tractable at metropolitan scale despite the NP-hardness of the underlying problem. VI. R ESULTS AND A NALYSIS A. Impact of Key-Rate Threshold and Candidate Strategy Fig. 3 shows how trusted-relay usage grows with the minimum key-rate threshold κmin under three candidate strategies (S1–S3) for each topology (|R| = 20, B = 50, lossuncompensated). In Tokyo (panel a), the compact topology (diameter 30 km) keeps all node pairs within MDI-QKD reach: all strategies achieve TR = 0 across the entire threshold range up to κmin = 1300 bps, confirming that hub placement alone eliminates all trusted relays in dense metropolitan meshes. In Madrid (panel b), the sparser structure and larger diameter (61 km) cause trusted relays to appear at approximately 400 bps, rising to TR = 4 (S1, S2) and TR = 1 (S3) at κmin = 1300. In G50 (panel c), the largest diameter (84 km) makes the model most sensitive to κmin : TR begins increasing at κmin ≈ 200 bps and reaches TR = 7 under all three strategies at κmin = 1300. The onset of nonzero TR thus shifts monotonically with network diameter, from 1300+ bps (Tokyo) through ∼400 bps (Madrid) to ∼200 bps (G50). Across all topologies, the ordering S1 ≥ S2 ≥ S3 is consistent, confirming that richer candidate placement reduces trusted-relay demand at every operating point.
B. Impact of Network Scale The comparison across the three topologies suggests that network diameter is the primary driver of trusted-relay demand, yet the topologies also differ in connectivity structure. To isolate the effect of scale, ExpD uniformly scales all G50 link lengths while keeping the node set, connectivity, and request set fixed, so that only the geographic extent of the network changes. Fig. 4 shows the resulting trusted-relay count as the diameter grows from 84 to 252 km. Trustedrelay usage increases monotonically along both axes, and the infeasibility frontier advances diagonally: at diameters up to roughly 110 km, all evaluated key-rate targets remain feasible, whereas at larger scales the most demanding targets become progressively infeasible under the given budget. This controlled sweep reproduces, within a single topology, the diameter-governed onset observed across topologies in Fig. 3, confirming that geographic scale is the dominant driver of the feasibility boundary of pure MDI-QKD deployment. Under loss-compensated deployment the same sweep reaches infeasibility at smaller scales, since the loss-balancing window tightens relative to the growing link lengths, consistent with the behavior observed in Madrid. C. Impact of Deployment Budget Varying the budget (ExpC, |R| = 35, κmin = 400 bps) reveals a sharp transition governed by a critical value B ∗ : below B ∗ , no budget-feasible pure MDI-QKD deployment exists, because the budget cannot fund the BSM units needed to serve all requests via two-link connections; at or above B ∗ , trusted-relay usage immediately saturates at a topologyand model-dependent floor. Tokyo and G50 become feasible at B ∗ = 45 under all strategies, after which Tokyo saturates at TR = 0 (its density admits a qualifying hub for every pair) while G50 saturates at TR = 3 (a few node pairs exceed MDIQKD range regardless of budget). Madrid exposes the cost of loss balancing most clearly: under loss-compensated (Comp.) deployment it requires B ∗ = 60 (S1, S2) and saturates at
2
Trusted Relay Count
S1 S2 S3
8
5
7 4
1
6 5
3
4
S1–S3 coincide
2
3 2
1
0
1 0 0
250
500
750
1000
1250
0 0
250
500
750
1000
1250
0
250
500
750
1000
Minimum Key Rate κmin (bps)
Minimum Key Rate κmin (bps)
Minimum Key Rate κmin (bps)
(a) Tokyo
(b) Madrid
(c) G50
1250
252
6
205
4
11
168
1
7
11
140
0
5
8
11
112
0
4
5
7
84
9
6
10
0
1
2
5
5
10
200
400
700
1000
3
Trusted Relay Count
Network diameter (km)
Fig. 3: Trusted-relay count vs. minimum key-rate threshold under three candidate strategies (loss-uncompensated, |R| = 20, B = 50). The onset of nonzero TR shifts with network diameter.
0
κmin (bps)
Fig. 4: Trusted-relay count for G50 under uniform scaling of all link lengths (loss-uncompensated, S2, |R| = 20, B = 50). Gray crosses (×) mark infeasible configurations.
TR = 9 and 8, whereas the loss-uncompensated (Uncomp.) deployment lowers the threshold to B ∗ = 45 and the floor to TR = 2, and the richest candidate set (S3) drives Madrid to TR = 3 under Comp. and TR = 0 under Uncomp. This infeasible-to-saturation transition shows that pure MDI-QKD deployment requires a minimum infrastructure investment before any service is possible, and that the required investment grows with the loss-balancing constraint in sparse topologies. The choice of a default B = 50 therefore sits just above B ∗ for most configurations, keeping the budget constraint operative rather than vacuous. D. Impact of Deployment Model Fig. 5 maps trusted-relay usage across the (|R|, κmin ) operating space under S2 candidate placement, with the key-rate axis extended to 1300 bps. In Tokyo, both deployment models yield TR = 0 across the entire operating region, confirming that in compact metropolitan meshes, hub placement alone
is sufficient. In Madrid, the Comp. and Uncomp. deployments diverge: under Comp., TR rises with load and becomes infeasible for |R| = 35 at all κmin , whereas Uncomp. remains feasible with substantially lower TR throughout, confirming that the loss-balancing constraint is the dominant cost driver in sparse topologies. In G50, both deployment models exhibit similar TR (the dense connectivity makes loss balancing nearly free), and the feasibility boundary is instead driven by high κmin combined with high load, reflecting the larger network diameter. Across all topologies, relaxing the loss-balancing constraint either reduces trusted-relay usage (Madrid) or has no effect (Tokyo, G50), making it a cost-free or cost-effective planning lever. The mechanism is structural. In Madrid, hub candidates satisfying the loss-balancing constraint are scarce: under Comp. S2, TR reaches 4 at |R| = 20 and κmin = 10, whereas Uncomp. achieves TR = 0 under the same conditions, eliminating all trusted relays at no additional infrastructure cost. In Tokyo and G50, denser connectivity ensures that near-midpoint hub candidates are almost always available, so loss balancing is effectively free. VII. D ISCUSSION The results suggest several practical implications for MDIQKD network planning. First, in compact metropolitan networks such as Tokyo (diameter 30 km), hub placement alone eliminates all trusted relays regardless of the key-rate threshold or deployment model, confirming that pure MDI-QKD deployment is straightforward at this scale. Second, in sparse topologies such as Madrid, relaxing the loss-balancing constraint eliminates trusted relays that would otherwise be required under loss-compensated deployment, making it the most costeffective planning lever because it requires no additional infrastructure. In denser topologies, loss balancing is effectively free. Third, increasing candidate density (S1→S3) consistently
0
0
0
0
0
0
0
2
4
6
7
9
2
4
6
7
7
1000
0
0
0
0
0
0
0
0
1
3
5
6
8
1
2
4
5
5
7
700
0
0
0
0
0
0
0
0
1
2
4
5
6
1
2
4
5
5
6
400
0
0
0
0
0
0
0
0
1
2
4
5
6
0
0
2
2
2
2
3
200
0
0
0
0
0
0
0
0
1
2
4
5
6
0
0
1
1
1
1
1
100
0
0
0
0
0
0
0
0
1
2
4
5
6
0
0
0
0
0
0
0
10
0
0
0
0
0
0
0
0
1
2
4
5
6
0
0
0
0
0
0
0
(b) Madrid, Comp.
8
6
(c) G50, Comp.
1300
0
0
0
0
0
0
0
0
2
3
4
4
5
6
2
4
6
7
7
10
1000
0
0
0
0
0
0
0
0
0
1
2
2
3
4
1
2
4
5
5
7
700
0
0
0
0
0
0
0
0
0
0
1
1
1
2
1
2
4
5
5
6
400
0
0
0
0
0
0
0
0
0
0
1
1
1
2
0
0
2
2
2
2
3
200
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
100
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
5
10
15
20
25
30
35
5
10
15
20
25
30
35
5
10
15
20
25
30
35
||
||
||
(d) Tokyo, Uncomp.
(e) Madrid, Uncomp.
(f) G50, Uncomp.
4
Trusted Relay Count
κmin (bps)
0
(a) Tokyo, Comp.
κmin (bps)
10
1300
2
0
Fig. 5: Trusted-relay count under S2 candidate placement (B = 50). Gray crosses (×) mark infeasible configurations. Top row: loss-compensated; bottom row: loss-uncompensated. The key-rate axis extends to 1300 bps to capture the full operating region.
reduces TR across all topologies, though S3 remains a theoretical reference given its uncaptured new-fiber cost. Finally, the key-rate threshold at which trusted relays first appear shifts monotonically with network diameter, from beyond 1300 bps in Tokyo to approximately 200 bps in G50, and the controlled scale sweep of Fig. 4 confirms this dependence within a single topology, indicating that QoS targets must be matched to network scale. Several modeling simplifications should be noted. The key-rate model uses an experimental lookup table [16] with asymptotic rates, and tighter security analyses incorporating finite-key effects [43] would reduce the achievable rates. Since the key rate enters the model solely through the viability condition κ(deff ) ≥ κmin , a uniform rate reduction by a factor η is exactly equivalent to raising the threshold to κmin /η; the sensitivity of our results to finite-key corrections can therefore be read directly from the key-rate sweeps in Figs. 3 and 5. At the default 10 bps threshold, the optimal trusted-relay count is unchanged under a tenfold rate reduction across all evaluated topologies and both deployment models. The effective-distance metric deff = (2/αdB ) max(LA , LB ) is likewise conservative under loss-uncompensated deployment, since evaluating the key rate at the worse of the two channels over-estimates the loss whenever the two user-to-hub paths differ. In fact, the two deployment models bracket any perlink optimized operating point: the loss-uncompensated rate is achievable today with passive attenuation, while evaluating the key rate at the total loss of the two channels, i.e., deff = (LA + LB )/αdB , upper-bounds what asymmetric MDIQKD protocols [21], [22] could achieve. Re-solving the ExpA and ExpB instances under this upper bound leaves the optimal trusted-relay count unchanged across the evaluated instances with κmin ≤ 100 bps, so the reported results are unaffected by
protocol-level optimization in this regime. At more demanding thresholds in the sparse and large-diameter topologies, the bound lowers TR by at most three and marginally extends the feasible region, quantifying the maximum residual benefit of per-link protocol optimization, which we leave for future work. VIII. C ONCLUSION In this work, we formalized the MDI-QKD Hub Deployment (MHD) problem, proved its NP-hardness, and proposed a MILP formulation that jointly optimizes BSM-hub placement, two-link user-to-hub routing, and trusted-relay assignment under budget and capacity constraints. Evaluation across three metropolitan topologies (12 to 50 nodes) at realistic geographic distances reveals that topology structure governs trusted-relay demand: compact meshes eliminate all trusted relays through hub placement alone, sparse topologies benefit from relaxing the loss-balancing constraint, and the key-rate threshold at which trusted relays first appear shifts monotonically with network diameter. The formulation delineates the feasibility boundary of pure MDI-QKD deployment, providing actionable guidance for network planners. Future work will extend the model to dynamic demand scenarios and larger networks via scalable heuristics. ACKNOWLEDGMENT This work was supported in part by funding from the Innovation for Defence Excellence and Security (IDEaS) program from the Department of National Defence (DND); the EU Horizon Europe project “Quantum Secure Networks Partnership” (QSNP), grant 101114043; and the “Hub Nacional de Excelencia en Comunicaciones Cuánticas” project, funded by
Ministerio para la Transformación Digital y de la Función Pública and by the Recovery, Transformation and Resilience Plan – Funded by the European Union – NextGenerationEU (PRTR-C16.R1). R EFERENCES [1] C. H. Bennett and G. Brassard, “Quantum cryptography: Public key distribution and coin tossing,” in Proc. IEEE Int. Conf. Comput. Syst. Signal Process., Bangalore, India, 1984, pp. 175–179. [2] H.-K. Lo, M. Curty, and K. Tamaki, “Secure quantum key distribution,” Nature Photon., vol. 8, no. 8, pp. 595–604, 2014. [3] S. Pirandola, R. Laurenza, C. Ottaviani, and L. Banchi, “Fundamental limits of repeaterless quantum communications,” Nature Commun., vol. 8, no. 15043, 2017. [4] M. Mehic, M. Niemiec, S. Rass, J. Ma, M. Peev, A. Aguado, V. Martin, S. Schauer, A. Poppe, C. Pacher, and M. Voznak, “Quantum key distribution: A networking perspective,” ACM Comput. Surv., vol. 53, no. 5, pp. 96:1–96:41, 2020. [5] Y. Zhao, Y. Cao, W. Wang, H. Wang, X. Yu, J. Zhang, M. Tornatore, Y. Wu, and B. Mukherjee, “Resource allocation in optical networks secured by quantum key distribution,” IEEE Commun. Mag., vol. 56, no. 8, pp. 130–137, 2018. [6] Q. Zhang, O. Ayoub, A. Gatto, J. Wu, F. Musumeci, and M. Tornatore, “Routing, channel, key-rate, and time-slot assignment for QKD in optical networks,” IEEE Trans. Netw. Serv. Manag., vol. 21, no. 1, pp. 148–160, 2024. [7] J. Xiong, Q. Zhang, Y. Piétri, R. Yehia, R. Boutaba, F. Musumeci, and M. Tornatore, “Power consumption analysis of QKD networks under different protocols and detector configurations,” in Proc. Eur. Conf. Opt. Commun. (ECOC), 2025. [8] “The European Quantum Communication Infrastructure (EuroQCI) Initiative,” https://digital-strategy.ec.europa.eu/en/policies/ european-quantum-communication-infrastructure-euroqci, 2024. [9] QUID Consortium, “Quid website,” https://quid-euroqci-italy.eu/, 2025, accessed: 2025-11-30. [10] EuroQCI-Spain Consortium, “Euroqci-spain website,” https: //euroqci-spain.eu/, 2025, accessed: 2025-11-30. [11] H.-K. Lo, M. Curty, and B. Qi, “Measurement-device-independent quantum key distribution,” Phys. Rev. Lett., vol. 108, no. 130503, 2012. [12] L. Lydersen, C. Wiechers, C. Wittmann, D. Elser, J. Skaar, and V. Makarov, “Hacking commercial quantum cryptography systems by tailored bright illumination,” Nature Photon., vol. 4, no. 10, pp. 686– 689, 2010. [13] S. L. Braunstein and S. Pirandola, “Side-channel-free quantum key distribution,” Phys. Rev. Lett., vol. 108, no. 130502, 2012. [14] Y.-L. Tang et al., “Measurement-device-independent quantum key distribution over 200 km,” Phys. Rev. Lett., vol. 113, no. 190501, 2014. [15] Y.-L. Tang, H.-L. Yin, Q. Zhao, H. Liu, X.-X. Sun, M.-Q. Huang, W.-J. Zhang, S.-J. Chen, L. Zhang, L.-X. You, Z. Wang, Y. Liu, C.-Y. Lu, X. Jiang, X. Ma, Q. Zhang, T.-Y. Chen, and J.-W. Pan, “Measurementdevice-independent quantum key distribution over untrustful metropolitan network,” Phys. Rev. X, vol. 6, no. 011024, 2016. [16] R. C. Berrevoets et al., “Deployed measurement-device independent quantum key distribution and Bell-state measurements coexisting with standard internet data and networking equipment,” Commun. Phys., vol. 5, no. 186, 2022. [17] Q*Bird, “Falqon MDI-QKD Platform,” https://q-bird.com/ mdi-qkd-falqon-series/, 2025, accessed: 2026-04-24. [18] S. Alumur and B. Y. Kara, “Network hub location problems: The state of the art,” Eur. J. Oper. Res., vol. 190, no. 1, pp. 1–21, 2008. [19] M. E. O’Kelly, “A quadratic integer program for the location of interacting hub facilities,” Eur. J. Oper. Res., vol. 32, no. 3, pp. 393–404, 1987.
[20] C.-K. Hong, Z.-Y. Ou, and L. Mandel, “Measurement of subpicosecond time intervals between two photons by interference,” Physical review letters, vol. 59, no. 18, pp. 2044–2046, 1987. [21] W. Wang, F. Xu, and H.-K. Lo, “Asymmetric protocols for scalable high-rate measurement-device-independent quantum key distribution networks,” Phys. Rev. X, vol. 9, no. 041012, 2019. [22] H. Liu et al., “Experimental demonstration of high-rate measurementdevice-independent quantum key distribution over asymmetric channels,” Phys. Rev. Lett., vol. 122, no. 160501, 2019. [23] Y. Cao, Y. Zhao, J. Li, R. Lin, J. Zhang, and J. Chen, “Hybrid trusted/untrusted relay-based quantum key distribution over optical backbone networks,” IEEE J. Sel. Areas Commun., vol. 39, no. 9, pp. 2701– 2718, 2021. [24] J. Jia, B. Dong, L. Kang, H. Xie, and B. Guo, “Cost-optimization-based quantum key distribution over quantum key pool optical networks,” Entropy, vol. 25, no. 4, p. 661, 2023. [25] J. He, Y. Zhou, S. Xie, and C. Wang, “A cost-optimal quantum key distribution based on hybrid trusted relays,” in Proc. BDCTA, 2025, pp. 130–138. [26] J. Rabbie, K. Chakraborty, G. Avis, and S. Wehner, “Designing quantum networks using preexisting infrastructure,” npj Quantum Inf., vol. 8, no. 5, 2022. [27] S. Pouryousef, H. Shapourian, A. Shabani, R. Kompella, and D. Towsley, “Resource placement for rate and fidelity maximization in quantum networks,” IEEE Trans. Quantum Eng., vol. 5, pp. 1–16, 2024. [28] C. Elliott, A. Colvin, D. Pearson, O. Pikalo, J. Schlafer, and H. Yeh, “Current status of the DARPA quantum network,” in Quantum Information and Computation III (SPIE), vol. 5815, 2005, pp. 138–149. [29] M. Peev et al., “The SECOQC quantum key distribution network in Vienna,” New J. Phys., vol. 11, no. 075001, 2009. [30] M. Sasaki et al., “Field test of quantum key distribution in the Tokyo QKD network,” Opt. Express, vol. 19, no. 11, pp. 10 387–10 409, 2011. [31] Y.-A. Chen et al., “An integrated space-to-ground quantum communication network over 4,600 kilometres,” Nature, vol. 589, pp. 214–219, 2021. [32] A. Sebastián-Lombraña, L. Ortiz, J. P. Brito, J. Faba, R. B. Méndez, J. S. De Buruaga, R. J. Vicente, J. Setien, J. J. Romero, C. Escribano, P. Salas, J. L. Bejarano, and V. Martı́n, “Advancing the future of quantum communication networks: the new MadQCI,” in Proc. 25th Int. Conf. Transparent Opt. Netw. (ICTON), 2025, pp. 1–5. [33] Q. Zhang, O. Ayoub, J. Wu, X. Lin, and M. Tornatore, “IC-QKD: An information-centric quantum key distribution network,” IEEE Commun. Mag., vol. 61, no. 12, pp. 148–154, 2023. [34] L. Cirigliano, V. Brosco, C. Castellano, C. Conti, and L. Pilozzi, “Optimal quantum key distribution networks: Capacitance versus security,” npj Quantum Inf., vol. 10, no. 44, 2024. [35] O. Amer, W. O. Krawec, and B. Wang, “Efficient routing for quantum key distribution networks,” in Proc. IEEE Int. Conf. Quantum Comput. Eng. (QCE), 2020, pp. 137–147. [36] W. O. Krawec, B. Wang, and R. Brown, “Finite key security of simplified trusted node networks,” in Proc. IEEE Int. Conf. Quantum Comput. Eng. (QCE), 2024, pp. 1777–1787. [37] A. K. Marik, B. Palit, and S. Behera, “Trusted repeater placement in QKD-enabled optical networks,” arXiv preprint arXiv:2509.10338, 2025. [38] G. Avis, R. Knegjens, A. S. Sørensen, and S. Wehner, “Asymmetric node placement in fiber-based quantum networks,” Phys. Rev. A, vol. 109, no. 052627, 2024. [39] R. M. Karp, “Reducibility among combinatorial problems,” in Complexity of Computer Computations, R. E. Miller, J. W. Thatcher, and J. D. Bohlinger, Eds. Plenum Press, 1972, pp. 85–103. [40] V. Martin et al., “MadQCI: A heterogeneous and scalable SDN QKD network deployed in production facilities,” npj Quantum Inf., vol. 10, no. 80, 2024. [41] S. Orlowski, R. Wessäly, M. Pióro, and A. Tomaszewski, “SNDlib 1.0— survivable network design library,” Networks, vol. 55, no. 3, pp. 276– 286, 2010. [42] R. Alléaume, F. Roueff, E. Diamanti, and N. Lütkenhaus, “Topological optimization of quantum key distribution networks,” New J. Phys., vol. 11, no. 075002, 2009. [43] M. Curty, F. Xu, W. Cui, C. C. W. Lim, K. Tamaki, and H.-K. Lo, “Finite-key analysis for measurement-device-independent quantum key distribution,” Nat. Commun., vol. 5, no. 3732, 2014.