PaperlayerView exact revision on arXiv

Source-linked AI summary

Measurement-Device Placement in MDI-QKD Networks with Minimal Trusted Relays

Tianqu Luo, Ibrahim Arslantas, Sezin Ozturk, Qiaolun Zhang, Alberto Sebastián-Lombraña, Mehdi Bolourian, Jiaheng Xiong, Francesco Musumeci, Vicente Martín, Raouf Boutaba, Massimo Tornatore

arXiv:2609.06603v2cs.NI

TL;DR

Channel loss limits MDI-QKD reach, leaving network planners to place shared BSM hubs while minimizing reliance on trusted relays. The paper formalizes this joint planning task as an NP-hard problem and develops a MILP for its deployment decisions. Across metropolitan topologies, trusted-relay demand depends on topology, loss balancing, and network diameter.

  • Problem

    The planning question is how to place BSM hubs on fiber infrastructure to minimize trusted-relay use while providing long-range MDI-QKD service.

    Source: §I · p. 2

  • Method

    The MHD model jointly optimizes BSM-hub placement, two-link user-to-hub routing, and trusted-relay assignment with a MILP under budget and capacity constraints.

    Source: §I · p. 2, C. Problem Statement · p. 4

  • Results

    Compact meshes need no trusted relays through hub placement alone, sparse topologies benefit from relaxing loss balancing, and the threshold for trusted relays shifts monotonically with network diameter.

    Source: §I · p. 2, §VIII · p. 9

  • Takeaways & Limitations

    The results delineate a feasibility boundary for pure MDI-QKD deployment and show that topology-specific planning can reduce trusted-relay demand.

    Source: §VII · p. 8, §VIII · p. 9

Abstract

from arXiv · show

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 MDI-QKD 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 trusted-relay 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 MDI-QKD deployment.

I. INTRODUCTION

QKD range is limited by channel loss, while trusted relays extend service at the cost of additional security assumptions. This work formalizes joint MDI-QKD hub placement and routing, then evaluates how topology and loss balancing shape trusted-relay demand.

I. INTRODUCTION

  • MDI-QKD delegates measurements to an untrusted BSM relay, removing detector side channels, while trusted relays extend range by forwarding keys under additional security assumptions.Detector imperfections and attacks such as blinding can open side channels that compromise security.Source: §I · pp. 1–2
  • A shared BSM hub serves multiple user pairs through separate user-to-hub channels, whose loss asymmetry can degrade interference and reduce achievable key rate.The paper models balancing by adding attenuation to the lower-loss path.Source: §I · p. 2
  • Prior MDI-QKD deployment studies do not jointly address hub placement, two-link user-to-hub routing, and trusted-relay assignment under realistic deployment constraints.The cited approaches either select relay types along predetermined paths or use heuristics without the two-link structure or realistic budget and capacity constraints.Source: §I · p. 2
  • The MHD problem jointly chooses BSM hub locations, user-pair assignments, and trusted-relay paths to meet service demand, and is NP-hard.The formulation accounts for operational conditions.Source: §I · p. 2
  • The proposed MILP captures shared-hub, two-link MDI-QKD routing and loss balancing, and can be solved optimally for metropolitan-scale deployments.Loss asymmetry is handled through a loss-balancing constraint based on passive attenuation.Source: §I · p. 2
  • Compact metropolitan meshes eliminate all trusted relays through hub placement alone, while sparse topologies benefit from relaxing loss balancing and trusted-relay thresholds shift with network diameter.The evaluation covers three metropolitan topologies with 12 to 50 nodes at realistic geographic distances.Source: §I · p. 2

II. RELATED WORK

Prior quantum-network optimization models target relay-chain architectures, while MDI-QKD-specific deployment studies address restricted subproblems. The network model represents fiber links, candidate BSM hubs, service requests, and distinct trusted and untrusted relay roles.

II. RELATED WORK

  • Prior optimization formulations target trusted-node forwarding or repeater entanglement distribution, and do not capture MDI-QKD’s two independent user-to-shared-hub links.Existing MDI-QKD deployment studies also do not jointly model hub placement, routing, and trusted-relay assignment under realistic constraints.Source: §II · p. 3

A. Network Model

  • The network is a directed fiber graph with candidate hub locations; each physical link is represented by opposite directed arcs.Candidate locations follow deployment policies, including fiber midpoints, network nodes, and geographic midpoints.Source: A. Network Model · p. 3
  • S1 uses fiber midpoints, S2 adds network nodes, and S3 adds geographic midpoints, with S3 treated as a theoretical reference rather than an equal-cost deployment option.Reaching S3 sites requires new fiber whose cost is not captured by the budget.Source: A. Network Model · p. 3
  • Requests may use an untrusted BSM hub or trusted-relay forwarding; the model minimizes trusted-relay use subject to installation budget and hub capacity.A compromised trusted relay reveals keys it forwards, whereas the BSM hub performs measurement and announces the outcome without learning the secret key.Source: A. Network Model · p. 3

B. Key-Rate Model and Deployment Assumptions

The key-rate model maps effective distance, derived from user-to-hub channel losses, to achievable rate and enforces a minimum rate threshold. Deployment options either require loss balancing or allow imbalance while conservatively evaluating the worse channel.

B. Key-Rate Model and Deployment Assumptions

  • The effective distance maps the larger user-to-hub channel loss to an equivalent fiber distance, and the key-rate function is interpolated from experimental data.Links beyond the maximum tabulated reach are treated as unreachable, and κmin is the minimum QoS threshold.Source: B. Key-Rate Model and Deployment… · pp. 3–4
  • Channel loss includes fiber attenuation and intermediate-node bypass loss, while connector, splice, and other intermediate-node component losses are neglected.The attenuation coefficient could be increased to include the cumulative effect of those neglected losses.Source: B. Key-Rate Model and Deployment… · p. 4
  • Loss-compensated deployment admits a connection only when path losses can be balanced within the specified tolerance; the evaluation sets τ = 3 km.This corresponds to at most 1.2 dB of residual loss imbalance.Source: B. Key-Rate Model and Deployment… · p. 4
  • Relaxing loss balancing lowers trusted-relay demand in sparse topologies, while its effect is concentrated there.The compared deployment options differ only in candidate admissibility.Source: B. Key-Rate Model and Deployment… · p. 4
  • Loss-uncompensated deployment permits any hub within the key-rate threshold and evaluates rate using the worse channel, yielding a lower bound and conservative trusted-relay counts.This option does not model an asymmetric MDI-QKD protocol.Source: B. Key-Rate Model and Deployment… · p. 4

C. Problem Statement

The MHD problem jointly chooses BSM hub deployment and request routing to minimize trusted-relay use under network constraints. It addresses static planning before deployment, rather than dynamic key routing over installed infrastructure.

C. Problem Statement

  • MHD takes a fiber network, candidate hub locations, key requests, deployment budget, per-hub capacity, and minimum key-rate threshold as inputs.Source: C. Problem Statement · p. 4
  • The MHD objective minimizes requests served via trusted relays, subject to budget, hub-capacity, arc-capacity, and key-rate constraints.Source: C. Problem Statement · p. 4
  • The model jointly decides BSM equipment locations, quantum-path routing for each user pair, and which requests use trusted relays.Source: C. Problem Statement · p. 4
  • The work addresses static offline planning before deployment, not dynamic per-session routing over an already-provisioned infrastructure.Source: C. Problem Statement · p. 4

IV. MILP FORMULATION

The formulation represents each request using candidate serving paths and decision variables for hub deployment, path assignment, and path type. Its parameters capture deployment costs, capacity, budget, and quantum-channel use.

A. Decision Variables and Parameters

B. Objective Function

The objective balances trusted-relay use, deployment cost, and quantum-channel use through a weighted sum. Its weights impose a strict priority order: trusted-relay minimization, then cost, then channel count.

B. Objective Function

  • The objective combines minimizing trusted-relay-served requests, deployment cost, and quantum-channel usage.Source: B. Objective Function · p. 5
  • The weights α = 1000, β = 1, and γ = 0.001 prioritize trusted-relay minimization over cost and cost over channel count.Source: B. Objective Function · p. 5
  • The cost term is bounded below the trusted-relay weight, and the channel term is too small to offset a one-unit change in trusted-relay count across evaluated instances.Source: B. Objective Function · p. 5

C. Constraints

The constraints enforce request connectivity, require deployed BSM equipment for hub paths, and limit hub and fiber-channel capacity. The path formulation is tighter than big-M alternatives.

C. Constraints

  • Each request must be served by exactly one path, and any path using hub h requires deployed BSM equipment there.Source: C. Constraints · p. 5
  • The per-path formulation is tighter than big-M alternatives and produces a stronger LP relaxation.Source: C. Constraints · p. 5
  • Each BSM unit serves at most K_max requests, and each directed fiber arc carries at most W quantum channels.Source: C. Constraints · p. 5
  • The arc-capacity constraint prevents oversubscription of quantum channels on shared fiber links.Source: C. Constraints · p. 5
  • Paths below κmin are excluded during path generation, keeping the MILP constraint matrix sparse.Source: C. Constraints · p. 5

D. NP-hardness of the MHD Problem

The MHD decision problem asks whether a budgeted hub deployment can serve every request through MDI-QKD without trusted relays; this decision problem is NP-complete by reduction from Set Cover.

D. NP-hardness of the MHD Problem

  • The proof reduces Set Cover to MHD by mapping each universe element to a request and each subset to a candidate hub.Distances and key-rate parameters make a request reachable through a hub exactly when its corresponding element belongs to that subset.Source: D. NP-hardness of the MHD Problem · pp. 5–6
  • The decision version of MHD is NP-complete: it determines whether a budgeted deployment can serve every request without trusted relays.A candidate deployment's feasibility can be checked in polynomial time by verifying routing, activation, capacity, budget, and trusted-relay counts.Source: D. NP-hardness of the MHD Problem · p. 5
  • A Set Cover solution of size at most k yields a zero-trusted-relay deployment within budget B = k, and any such deployment yields a cover of size at most k.The construction sets hub costs to one and makes hub and arc capacities non-binding.Source: D. NP-hardness of the MHD Problem · p. 6

V. SIMULATION SETUP

The evaluation uses three metropolitan-scale fiber topologies, varies key-rate, request-load, budget, and geographic-scale conditions, and solves the resulting MILP instances with a commercial solver.

A. Topologies

  • Tokyo, Madrid, and G50 span a dense urban mesh, a sparse near-tree network, and a larger backbone, with diameters of 30, 61, and 84 km.Tokyo's node pairs lie within MDI-QKD reach; Madrid has limited path redundancy, while some G50 pairs are unreachable regardless of hub placement. Fig. 2 depicts the three topologies.Source: A. Topologies · p. 6, Figure 2 · p. 7

B. Simulation Scenarios

  • Baseline parameters reflect commercial practice: Kmax = 3, and budget B = 50 is set to bind at intermediate request loads.Hub setup cost is normalized to dominate per-connection usage.Source: B. Simulation Scenarios · p. 6, Table III · p. 6
  • ExpA sweeps κmin; ExpB jointly sweeps request load and κmin; ExpC varies budget; ExpD scales G50 link lengths to isolate geographic extent.ExpA uses |R| = 20; ExpC uses |R| = 35 and κmin = 400 bps; ExpD scales diameter from 84 to 252 km.Source: B. Simulation Scenarios · p. 6
  • Each parameter point is evaluated across three topologies, three placement strategies, and two deployment models, with a 60-second per-instance limit.Median solve time is below one second, and most feasible instances are solved to proven optimality; large loss-uncompensated instances are exceptions.Source: §V · p. 6, B. Simulation Scenarios · p. 7

VI. RESULTS AND ANALYSIS

The results show that trusted-relay demand depends on network diameter, deployment strategy, and loss balancing, while budget constraints create a feasibility threshold before relay counts reach topology-dependent floors.

C. Impact of Deployment Budget

  • At |R| = 35 and κmin = 400 bps, Tokyo and G50 become feasible at B∗ = 45, then saturate at TR = 0 and TR = 3, respectively.Madrid requires B∗ = 60 under loss compensation, with TR = 9 and 8 for S1 and S2; without compensation, B∗ = 45 and TR = 2, while S3 reaches TR = 0.Source: C. Impact of Deployment Budget · pp. 7–8

A. Impact of Key-Rate Threshold and Candidate Strategy

  • TR stays at 0 in Tokyo through 1300 bps, begins near 400 bps in Madrid, and near 200 bps in G50; onset shifts with network diameter.At 1300 bps, Madrid reaches TR = 4 (S1, S2) and TR = 1 (S3), while G50 reaches TR = 7 under all strategies; across operating points S1 ≥ S2 ≥ S3.Source: A. Impact of Key-Rate Threshold and… · p. 7, Figure 3 · p. 8

B. Impact of Network Scale

  • In the G50 scale sweep, trusted-relay use rises as diameter grows from 84 to 252 km, while demanding key-rate targets become infeasible at larger scales.All evaluated targets remain feasible up to roughly 110 km; loss-compensated deployment becomes infeasible at smaller scales.Source: B. Impact of Network Scale · p. 7, Figure 4 · p. 8

D. Impact of Deployment Model

Deployment-model effects depend on topology: relaxing loss balancing substantially reduces trusted-relay use in sparse Madrid, while it has no effect in Tokyo or G50. The discussion and conclusion connect relay demand and pure MDI-QKD feasibility to network scale and topology.

D. Impact of Deployment Model

  • Tokyo has TR = 0 throughout the operating region; Madrid’s loss-compensated deployment becomes infeasible at |R| = 35, while loss-uncompensated deployment remains feasible with substantially lower TR.In G50, both models show similar TR; high key-rate thresholds combined with high load instead drive the feasibility boundary.Source: D. Impact of Deployment Model · p. 8
  • In Madrid, loss-compensated S2 reaches TR = 4 at |R| = 20 and κmin = 10, while loss-uncompensated S2 achieves TR = 0 at no additional infrastructure cost.Scarce hub candidates satisfying loss balancing explain the difference; denser connectivity makes balancing nearly free in Tokyo and G50.Source: D. Impact of Deployment Model · p. 8

VII. DISCUSSION

  • Compact networks such as Tokyo eliminate trusted relays through hub placement alone, while relaxing loss balancing is a cost-effective lever in sparse networks such as Madrid.Increasing candidate density reduces TR across topologies, although S3 does not account for new-fiber cost.Source: §VII · pp. 8–9

VIII. CONCLUSION

  • The key-rate threshold at which trusted relays first appear shifts monotonically with network diameter, delineating the feasibility boundary of pure MDI-QKD deployment.The evaluation covers three metropolitan topologies with 12 to 50 nodes at realistic geographic distances.Source: §VIII · p. 9
Loading 2609.06603v2…