Quantum-enhanced Network Tomography Yufei Zheng∗1 , Zihao Gong†2 , Saikat Guha2 , and Don Towsley1 1
arXiv:2604.25194v1 [quant-ph] 28 Apr 2026
2
College of Information and Computer Sciences, University of Massachusetts Amherst Department of Electrical and Computer Engineering, University of Maryland, College Park
Abstract Network tomography refers to the use of inference techniques for inferring internal network states from end-to-end probes. Quantum probes, implemented by sending blocks of n coherent-state pulses augmented with continuous-variable (CV) squeezing (n = 1) or weak temporal-mode entanglement (n > 1) over a lossy channel to a receiver with homodyne detection capabilities, are known to carry information about the channel transmissivity. Assuming a subset of nodes in an optical network is capable of sending and receiving such probes through intermediate nodes with all-optical switching capabilities, we leverage these quantum probes to estimate link transmissivities. To determine how to route the probes in a network, we propose a probe construction algorithm that guarantees link identifiability, while maximizing the number of information orthogonal sets of transmissivities. A set of probes induces a Fisher information matrix (FIM). We then derive two metrics, the determinant of the FIM and the trace of its inverse, to evaluate the performance of the probes. In particular, our results can be used to characterize the quantum improvement in estimating link transmissivities in a general optical network.
1
Introduction
Network tomography [36, 23] refers to the use of inference techniques that reconstruct the internal states of a network using external measurements, taken between a selected subset of network nodes. In stark contrast to conventional approaches that require link- or device-level access to every internal state of interest (the Simple Network Management Protocol (SNMP) [6]), network tomography obviates this need by solely leveraging endto-end measurements, making it particularly suitable for monitoring networks with inaccessible internal nodes (optical networks [21], cloud networks [8]). When measurements are modeled as random variables, network tomography bears some resemblance to multiparameter estimation. While certain statistical techniques transfer, the key difference lies in that network tomography problems are fundamentally graph-constrained: the underlying network topology must be accounted for when designing measurements. A large body of existing work in classical network tomography has focused on upper-layer performance metrics such as packet loss rate [22, 18, 5, 34], delay [22, 14, 35, 9], and bandwidth [13, 3]. Quantum network tomography, a newly emerged field of study, applies the classical tomography framework to quantum networks. By treating a quantum network as a collection of noisy quantum channels, recent work has investigated how to determine the corresponding channel parameters [38, 12]. In this work, we consider the problem of estimating link transmissivity, a physical-layer metric in optical networks. This problem may arise in several contexts, as optical networks are not only highly prevalent in modern communication systems [24, 37, 31], but also strong candidates for the physical infrastructure of future quantum networks [28, 26]. Meanwhile, link transmissivity is central to optical power budgeting [25] and routing decisions [16], while also serving as a critical indicator for performance monitoring and fault ∗ {yufeizheng, † {zgong12,
towsley}@cs.umass.edu saikat}@umd.edu
1
detection in optical networks [41]. To estimate the transmissivities of all links, network tomography is a natural approach. Even with full control over all the links, exhaustively testing each one does not scale to large networks. Instead, we rely on end-to-end probes to infer the transmissivities. Quantum probes, implemented by sending blocks of n coherent-state pulses augmented with continuousvariable (CV) squeezing or weak temporal-mode entanglement over a pure-loss bosonic channel to a receiver with homodyne detection capabilities, are known to be more sensitive than their quasi-classical counterparts in detecting sudden changes in transmission loss [20, 41]. These probes, when traversing a set of links in the network, carry information about link transmissivities. Therefore, we also adopt such probes in solving our estimation problem. Although transceivers for quantum probes are experimentally accessible using current quantum optical technology, it is only reasonable to assume that a subset of network nodes will be equipped with such capabilities. Given a network topology and a subset of network nodes that can send and receive quantum probes, to infer transmissivities for all links, we must decide how to route the probes in the network, and what physical implementation to use for each probe. Solving the latter involves optimizing parameters for the physical implementation and experiment design. While it is an interesting problem in its own right, it lies beyond the scope of the present work. Instead, we focus on routing, and on characterizing how well a given set of probes with specified physical implementations performs the estimation task. In deciding how to route the probes in a network, we incorporate the notion of information orthogonality from estimation theory [11]. Informally, and particularly in the context of network tomography, two sets of unknown parameters that are information orthogonal can be estimated separately. Estimating unknown link transmissivities in practice for a general network typically involves the use of numerical solvers. Subsets of link transmissivities that are information orthogonal can be treated independently and in parallel using numerical tools, which makes solving large instances more tractable. Therefore, we introduce a probe construction algorithm that maximizes the number of information orthogonal subsets of link transmissivities. To quantify how much information a given set of probes P carries about the unknown link transmissivities, we consider the Fisher information matrix (FIM) induced by P. Since the observation from each probe can be modeled as a Gaussian random vector [20], the FIM admits a convenient structure that enables closed-form expressions for both its determinant and the trace of its inverse, two standard metrics from the theory of optimal experiment design [2] for evaluating the performance of P. Moreover, we show that, in a general network setting, both metrics are closely related to the Fisher information (FI) associated each individual probe, which allows us to extend results from the single-channel case to characterize the quantum improvement for the general network case. Our contributions in this paper are twofold: • We present a probe construction algorithm that guarantees the identifiability of all link transmissivities, while maximizing the number of information orthogonal subsets of these unknown parameters (§ 4). • We derive the determinant of the FIM induced by a given set of probes, and the trace of its inverse, and use both metrics to characterize the quantum improvement in a general network (§ 5). In § 2, we formally define what constitutes a probe, and provide the necessary background on the two metrics related to the FIM. § 3 reviews the quantum and classical probes used throughout this work, and discusses the potential benefits—or lack thereof—of sharing entanglement across multiple channels in the network. Finally, we discuss related work in § 6, and conclude the paper in § 7.
2
Preliminaries
A network is a graph G = (V (G), E(G)), with a set of monitors M ⊆ V (G) that can send and receive probes. Here each edge (link) ei in E(G) represents a channel with transmissivity ηi . Throughout this work, we assume the graph topology is known (i.e., G and M ), but the transmissivity of each link is unknown, and the problem is to estimate the vector of all link transmissivities η = (η1 , η2 , . . . , ηn ), through probing the network. Next we formally define what a probe is (§ 2.1), and introduce the two metrics for characterizing the performance of the probes (§ 2.2). 2
2.1
What is a probe?
Definition. Formally, a probe is a 4-tuple (P, impl(P ), t(P ), c(P )), where P describes how the probe is routed in the network, impl(P ) ∈ {‘coherent’, ‘squeezed’, ‘entangled’} specifies the physical implementation1 , t(P ) is the number of pulses in the entangled block, and c(P ) is the number of copies to send. For example, we may send 3 copies of a probe that follows the route P , and each copy consists of a block of 4 entangled pulses. In this example, impl(P ) = ‘entangled’, t(P ) = 4, and c(P ) = 3. If a probe that traverses some P ′ is implemented by coherent of squeezed states, t(P ′ ) is trivially set to 1. Here P , the graph-theoretic description of a probe in the 4-tuple representation, is formally a walk 2 in the graph with endpoints in the set of monitors M . However, it is more convenient to think of P as the multiset of edges that the probe traverses. Whenever we refer to a set of probes P, we mean that P = {(Pi , impl(Pi ), t(Pi ), c(Pi ))}ni=1 , where P1 , P2 , . . . , Pn are distinct. For ease of notation, the term “probe” refers to different components in the formal 4-tuple definition depending on the context. In § 3, where the underlying graph is trivially an edge or a star, we treat a probe as (impl(P ), t(P ), c(P )). In § 4, which is concerned solely with routing, a probe refers to the graph-theoretic object P . Only in § 5, when all elements from previous sections are combined, do we require the full 4-tuple definition of a probe. Observations from probes. The three types of probes we consider in this work are implemented by coherent states, squeezed states, and entanglement augmented states. At the homodyne detector placed at the receiving end of these probes, each probe (P, impl(P ), t(P ), c(P )) produces a random Q vector XP of length t(P )c(P ) sampled from some Gaussian distribution N (µ(ηP ), Σ(ηP )), where3 ηP = e∈P ηe . We refer to XP as the observation from the probe (P, impl(P ), t(P ), c(P )). The observation from a set of probes P = {(Pi , impl(Pi ), t(Pi ), c(Pi ))}ni=1 is a random vector X, given by the concatenation of XP1 , XP2 , . . . , XPn , and sampled from some d-variate P Gaussian distribution Nd (µ(η), Σ(η)), with mean vector µ(η), covariance n matrix Σ(η), and dimension d = i=1 t(Pi )c(Pi ). We detail the forms of µ(·) and Σ(·) for different physical implementations in § 3.
2.2
Two metrics related to the Fisher information matrix
Fisher information matrix. In estimation theory, Fisher information matrix (FIM) quantifies how much information the observations from the probes contain about the vector of unknown parameters η. Given probes P, the vector of observations generated by P is sampled from a multivariate Gaussian distribution. Therefore, we restrict our attention to the FIM of Gaussian distributions. For a d-dimensional Gaussian distribution Nd (µ(η), Σ(η)), the (i, j)-entry of the FIM I(η) is ∂Σ −1 ∂Σ 1 ∂µT −1 ∂µ Σ + Tr Σ−1 Σ , (1) Ii,j = ∂ηi ∂ηj 2 ∂ηi ∂ηj where ∂µ1
∂Σ1,1
∂η ∂µi2 ∂ηi
∂ηi ∂Σ2,1 ∂ηi
∂µ ∂Σ = .. , ∂ηi = ∂ηi . ∂µn ∂ηi
.. .
∂Σn,1 ∂ηi
∂Σ1,2 ∂ηi ∂Σ2,2 ∂ηi
.. .
∂Σn,2 ∂ηi
··· ··· .. . ···
∂Σ1,n ∂ηi ∂Σ2,n ∂ηi
.. .
∂Σn,n ∂ηi
.
1 This is an oversimplification for notational convenience. impl(P ) should also include the classical coherent energy N and the quantum energy Na used in the physical implementation. In what follows, assume these parameters are explicitly specified in impl(P ). 2 A walk with endpoints v and v is a sequence v , e , v , e , ..., e , v , where v ∈ V for all 0 ≤ i ≤ k, and e ∈ E for all 0 0 1 1 2 i j k k k 1 ≤ i ≤ k. 3 In this notation, the multiset P is represented as sets, with some elements repeated. And we iterate over all edges e in P , including repetitions.
3
Note that the size of the FIM I(η) depends on the number of unknown parameters n, not the dimensionality d of the Gaussian distribution. In particular, when the number of edges (i.e., the number of unknown link transmissivities) n = 1, we have a single channel with unknown transmissivity η, and (1) gives the Fisher information (FI) I(η). Metrics. For an unbiased estimator η̂ of η that achieves the Cramér-Rao bound, the volume of its error , and the sum of the variances of the individual components of η̂ is ellipsoid is proportional to √ 1 det(I(η))
equal to Tr(I(η)−1 ). Even if an efficient unbiased estimator does not exist, det(I(η)) still characterizes the minimal achievable volume of the uncertainty ellipsoid, and Tr(I(η)−1 ) represents a fundamental local information-theoretic benchmark for the minimum attainable total variance. Therefore, we adopt det(I(η)) and Tr(I(η)−1 ) as measures for the performance a given set of probes P. Ideally, a good set of probes should induce a large determinant and a small trace. In the special case of a single channel (§ 3.1), det(I(η)) = I(η), Tr(I(η)−1 ) = I(η)−1 , and it suffices to consider the FI I(η).
3
Physical implementations of probes
We begin this section by introducing the classical (coherent states) and quantum probes (squeezing and entanglement augmented states) considered throughout this work. In § 3.1, we show that quantum probes are strictly better than classical ones for estimating the transmissivity of a single channel, and entanglement always brings benefits over squeezing alone. With the goal of extending the channel case to a general network setting, we consider in § 3.2 the problem of estimating the transmissivities of multiple channels. We demonstrate that, in contrast, sharing entanglement leaves both the determinant of the FIM and the trace of its inverse worse off than using squeezing alone.
3.1
The single-channel case
Consider a single lossy channel between monitors M1 and M2 , with unknown transmissivity η. Fix the total number of probes |P| = n, where each probe is sent from M1 to M2 . At the receiving monitor, we observe an n-dimensional Gaussian random vector X ∼ Nn (µ(η), Σ(η)). In what follows, we introduce specific forms of µ(·) and Σ(·) for each physical implementation of P, and compare the corresponding Fisher information I(η) between different implementations. Coherent states. For the classical (or quasi-classical) benchmark, similar to [20, 41], each probe is implemented as a coherent-state pulse |α⟩, with mean photon number α2 = N + Na . One can think of N as the classical energy, while the quantum energy 0 < Na << N is introduced to fairly compare the classical case with its quantum-augmented counterpart. We assume all n probes are independent. Denote I as the n × n identity matrix, and u as the column vector of n ones. When we send n coherent state pulses, the observation follows a Gaussian distribution with mean vector µc (η) and covariance matrix Σc (η) specified below: p µc (η) = (N + Na )η · u, 1 Σc (η) = I. 4 Since Σc (η) is constant with respect to η, the second term in (1) is 0, the Fisher information (FI) for the classical case, Ic (η), has the form Ic (η) =
(N + Na )n . η
4
Squeezed states. For the first quantum case, each probe is physically a displaced squeezed state |α; r⟩, with α2 = N photon equivalent of classical coherent energy and sinh2 (r) = Na << N quantum photon energy. In both the classical and the squeezing cases, the n pulses are uncorrelated, so again the covariance matrix for the observation is diagonal: p (2) µs (η) = N η · u, 1 Σs (η) = (1 − (1 − e−2r )η) · I. (3) 4 By (1), the FI for the squeezing case Is (η) is N (1 − e−2r )2 . Is (η) = n · + η(1 − (1 − e−2r )η) 2(1 − (1 − e−2r )η)2
(4)
Entanglement augmentation. Next, we consider entanglement-augmented probes. Specifically, a block ⊗n of n ∈ Z+ coherent-state pulses |α⟩ are augmented by a continuous variable entangled state generated by splitting a squeezed-vacuum state |0; s⟩, s ∈ R+ , where N = α2 , and sinh2 (s) = nNa . In this case, the n probes are correlated, and for the observation we have p (5) µe (η) = N η · u, Σe (η) =
1 η(1 − e−2s ) I− · uuT . 4 4n
(6)
To compute the FI I(η), first note that Σ(η) is the sum of a diagonal matrix and a rank-1 matrix. This allows us obtain a closed-form for Σ(η) by applying the Sherman-Morrison formula [33]: −1
(Σe (η))
= 4I +
where cn = 1 − e
−2s
4cn η uuT , n(1 − cn η)
√ 2 nNa √ =√ . nNa + 1 + nNa
(7)
The notation cn will recur throughout this paper. While all results can be given in terms of the original parameters of the probes (i.e., N, Na , n), the cn notation shortens the expressions, which makes them more intuitive to reason about. We will frequently make use of the following properties of cn : (i) cn ∈ (0, 1), and (ii) for any fixed Na , cn increases in n and approaches 1 as n → ∞. Then (1) gives the FI Ie (η) for the entanglement case Ie (η) =
nN c2n + . η(1 − cn η) 2(1 − cn η)2
(8)
Quantum vs. classical. Throughout this paper, we refer to probes implemented by coherent-state pulses as classical probes, and squeezing- and entanglement-augmented probes as quantum probes. To see how quantum probes fare relative to the classical ones, we compare their FIs, Ic (η), Is (η) and Ie (η). We first bring Is (η) into the same parametrization as Ic (η) and Ie (η). Note that by (7), 1 − e−2r = c1 and (4) gives N c21 Is (η) = n + . (9) η(1 − c1 η) 2(1 − c1 η)2 Next we show that, as long as the classical energy N is large enough compared to the quantum energy Na , entanglement augmentation is superior to squeezing (Fact 1), and quantum probes outperform their classical counterparts (Fact 2). c2
1 Fact 1. If N > 2(cn −c , Ie (η) > Is (η). 1)
5
Proof. Consider Ie (η) − Is (η), nc21 nN 1 1 1 c2n − Ie (η) − Is (η) = − + η 1 − cn η 1 − c1 η 2 (1 − cn η)2 (1 − c1 η)2 nN (cn − c1 ) nc21 > − (1 − cn η)(1 − c1 η) 2(1 − c1 η)2 nN (cn − c1 ) nc21 > − 2 (1 − c1 η) 2(1 − c1 η)2 n 2N (cn − c1 ) − c21 . = 2 2(1 − c1 η)
(cn > c1 > 0)
To have Ie (η) > Is (η), it suffices to set 2N (cn − c1 ) > c21 . Fact 2. If N > cn1η − 1 Na , Ie (η) > Ic (η). In particular, Is (η) > Ic (η) if N > c11η − 1 Na . nN Proof. Note that for large enough N , the first term in Ie (η) (8) dominates, therefore Ie (η) > η(1−c . This n η) Ie (η) 1 gives a simple lower bound Ic (η) > (N +NaN )(1−cn η) . The first bound N > cn η − 1 Na follows from setting Is (η) N N (N +Na )(1−cn η) > 1. Similarly, Ic (η) > (N +Na )(1−c1 η) , and the second part of the claim follows.
Though we tend to opt for simplicity over tightness throughout this work, Facts 1 and 2 quantify what it means for the classical energy N to be large enough, a notion that recurs in this section. Moreover, Facts 1 and 2 provide practical bounds for realistic parameters. For example, with 10 log10 (e2r ) = 6dB of squeezing per-pulse, for n = 2 probes, Fact 1 implies that entanglement augmentation outperforms squeezing alone, given N > 3.03 photon equivalent of classical coherent energy, and regardless of how large the underlying channel transmissivity η is. On the other hand, forη = 0.8, Fact 2 states that squeezed states are still better than classical coherent states if we merely have N > 0.4.
3.2
Sharing entanglement across channels
When there are multiple channels with unknown transmissivities, we further have the option to split the entangled probes spatially across different channels. An interesting question that arises, is whether the correlation among probes, introduced by entanglement, still brings benefits as in the single-channel case (§ 3.1). Next, through analyzing two special configurations, we give strong evidence that the answer to this question is likely to be in the negative. To be concrete, for the first configuration, we think of the n channels as forming a tree, with one internal node u as the sender of all the probes, and each leaf vi as the receiver for the channel along edge (u, vi ), i ∈ [n]. Consider n probes (pulses), where the i-th probe is sent through the channel along (u, vi ), whose unknown transmissivity is denoted as ηi for all i ∈ [n]. Crucially, we assume the ηi s do not depend on each other. Fix the classical and quantum energy per-pulse, N and Na , we compare two cases: (i) each probe is a displaced squeezed state; and (ii) the n probes are entangled. We show that, with respect to both the determinant of the FIM and the trace of its inverse, entanglement is in fact worse than independent squeezing. When we go beyond the channel case and consider probes in a general network, the walk specified by each probe corresponds to a channel, and the channels may share edges. Consequently, their channel transmissivities may also share common factors. For example, when two probe both traverse a link e, their channel transmissivities share the common factor ηe . Accordingly, we must consider whether the statements above still apply in this case. Unfortunately, analyzing this case for n channels, even with a relatively clean setup of the the probes, turns out to be quite heavy. We therefore include numerical results supporting the statements above for a two-channel setup in Appendix A, and analyze the configuration of n independent channels in the remainder of this section.
6
√ √ √ Independent squeezing. Let v = ( η1 , η2 , . . . , ηn ). When we send a displaced squeezed state with parameters N and Na through each channel, by (2), (3) and (7) for n = 1, √ µs,d (η) = N · v, 1 c1 Σs,d (η) = I − · diag(η1 , η2 , . . . , ηn ). 4 4 Next we consider the FIM of this case, Is,d . Since each channel transmissivity ηi has no dependence on ηj for j ̸= i, and the covariance matrix Σs,d (η) is diagonal, it is easy to check that Is,d is also diagonal, where c2
N + 2(1−c11 ηi )2 , following (9) for n = 1. Then, (Is,d )i,i = ηi (1−c 1 ηi ) n Y
c21 N + ηi (1 − c1 ηi ) 2(1 − c1 ηi )2 i=1 n Y Nn c21 ηi 1 , · = Qn + 2N (1 − c1 ηi )2 i=1 ηi i=1 1 − c1 ηi
det(Is,d ) =
−1 Tr(Is,d )=
(10)
n X
2ηi (1 − c1 ηi )2 . 2N (1 − c1 ηi ) + c21 ηi i=1
Correlated probes through entanglement. Here we split the block of n entangled pulses across n channels, where the i-th pulse is sent through the channel with transmissivity ηi , then we have √ µe,d (η) = N · v, (11) cn 1 · vv T . (12) Σe,d (η) = I − 4 4n √ In the special case of η1 = η2 = · · · = ηn = η, v = η · u and vv T = η · uuT , (11) and (12) indeed reduce to (5) and (6) respectively. Next we shall see that the FIM for this case, denoted as Ie,d , is in fact the sum of a diagonal matrix and a scaling of the all-ones matrix. Claim 1. Ie,d = β · diag( η11 , η12 , . . . , η1n ) + γuuT , where u is the n-dimensional column vector of ones, Pn c2n (n+cn Sη ) c2n Sη cn N + 4n(n−c β = N + 4n(n−c and γ = n−c 2 , with Sη = i=1 ηi . n Sη ) n Sη n Sη ) The proof of Claim 1, given in Appendix B, involves careful yet straightforward derivations of each term in (1). Claim 1 shows that Ie,d is yet again well structured, which allows us to derive det(Ie,d ) through a direct application of the matrix determinant lemma, βn 1 T det(Ie,d ) = Qn · 1 + u · diag(η1 , η2 , . . . , ηn ) · γu β i=1 ηi βn γSη = Qn · 1+ β i=1 ηi n 2n Nn c2n Sη 2N n(n − cn Sη ) + c2n Sη = · Qn · 1+ · . (13) (n − cn Sη ) 4N n(n − cn Sη ) 4N n(n − cn Sη ) + c2n Sη i=1 ηi | {z } (♠)
−1 By the Sherman-Morrison formula, we can also obtain Ie,d , −1 Ie,d =
1 1 1 1 γ · diag( , , . . . , ) − · ηη T . β η1 η2 ηn β(β + γSη )
7
Denote Qη =
Pn
2 i=1 ηi , we have the trace of the inverse FIM as follows:
−1 Tr(Ie,d )=
γQη Sη − β β(β + γSη )
= 2(n − cn Sη ) · 3.2.1
4N n(n − cn Sη )(nSη − cn Qη ) + c2n (nQη + cn Sη Qη ) − 2nSη2 . (4N n(n − cn Sη ) + c2n Sη )(2N n(n − cn Sη ) + c2n Sη )
Spatial entanglement induces a smaller determinant of the FIM
Next, we show that independent squeezing is indeed better than entanglement, with respect to the determinant of the corresponding FIMs. A formal proof would be inevitably cumbersome, so here we opt for an intuitive argument on why det(Is,d ) > det(Ie,d ), as long as the classical coherent energy N and the sum of the transmissivities Sη are not too small. As is customary in proofs of such statements, we show that some lower bound on det(Is,d ) (10) is still larger than some upper bound on det(Ie,d ) (13). In comparing these expressions, we ignore the n common factor QnN ηi . To obtain a suitable lower bound on det(Is,d ), we apply Jensen’s inequality to i=1 Qn 1 c21 x c21 ηi log 1−c1 1 x + 2N (1−c , and get that attains its minimum at η1 = η2 = + 2 i=1 1−c1 ηi 2N (1−c1 ηi )2 1 x) S
· · · ηn = nη . Then define f (Sη ) =
n Y
S
c21 · nη
1
!
+ S S 1 − c1 · nη 2N (1 − c1 · nη )2 n n n c21 Sη . = 1+ n − c1 Sη 2N (n − c1 · Sη ) i=1
(14)
To upper bound det(Ie,d ), notice that for N that is not too small, the (♠) term in (13) is very close to 0.5, and can be upper bounded by an absolute constant of 0.55. Therefore, define n 1.1n c2n Sη g(Sη ) = · 1+ . (15) n − cn Sη 4N n(n − cn Sη ) f (Sη ) > g(Sη ) would be a sufficient condition for det(Is,d ) > det(Ie,d ). Note that for N that is not too c2 S
c2 S
1 η n η small, 2N (1−c > 4N n(n−c , so the second factor in (14) is larger than that of (15). Moreover, the 1 ·Sη ) nn Sη ) 1.1n first factor in (14), n−cn1 Sη , grows more rapidly than (n−c in (15), albeit with a smaller initial value. n Sη )
We hence conclude that given N and Sη that are not too small, we have f (Sη ) > g(Sη ), and consequently det(Is,d ) > det(Ie,d ). As an example, given Na = 0.558, which corresponds to having 6dB of squeezing per-pulse (see the end of § 3.1), if we send n = 2 probes, we merely need the classical coherent energy N ≥ 6 to guarantee that the (♠) term in (13) is bounded from above by 0.55. If we further impose that the combined transmissivities from the n = 2 channels Sη ≥ 0.26, f (Sη ) > g(Sη ) holds, and we have det(Is,d ) > det(Ie,d ). 3.2.2
Spatial entanglement induces a larger trace of the inverse FIM
−1 −1 −1 Finally, we sketch the argument for Tr(Is,d ) < Tr(Ie,d ). To upper bound Tr(Is,d ), note that the function 2η(1−c1 η)2 −1 is now concave in η, so Jensen’s inequality conveniently gives that Tr(Is,d ) attains its maximum 2N (1−c1 η)+c21 η Sη at η1 = η2 = · · · = ηn = n : 2Sη (n − c1 Sη )2 −1 Tr(Is,d )≤ . 2N n(n − c1 Sη ) + nc21 Sη
8
Tr(FIMe 1) Tr(FIMs 1)
max: 0.00654
2
6e-3 5e-3 4e-3 3e-3 2e-3 1e-3 0 1.0 0.8 0.6 0.0 0.2 0.4 0.4 0.2 0.6 0.8 1 1.0 0.0
0.005 0.004 0.003 0.002 0.001 min: 1.65e-05
−1 −1 Figure 1: Tr(Ie,d ) − Tr(Is,d ) with respect to η1 and η2 .
When N is large enough, 2N n(n − c1 Sη ) dominates nc21 Sη , we drop the nc21 Sη term in the denominator to get a cleaner upper bound, Sη (n − c1 Sη ) −1 . (16) Tr(Is,d )≤ Nn −1 Similarly for Tr(Ie,d ), the intuition is best understood by focusing on the dominating terms, even though this does not yield a lower bound: −1 Tr(Ie,d ) ∼ 2(n − cn Sη ) ·
=
4N n(n − cn Sη )(nSη − cn Qη ) 4N n(n − cn Sη ) · 2N n(n − cn Sη )
nSη − cn Qη . Nn
(17)
−1 −1 For Tr(Is,d ) < Tr(Ie,d ) to hold, by comparing (16) and (17), we approximately need
c1 Sη2 > cn Qη .
(18)
Notice that (18) naturally holds if Sη is not too small. This is because, Qη < Sη by definition, so when Sη ≥ ccn1 , we have c1 Sη2 ≥ cn Sη > cn Qη . When Sη is small, for (18) to hold, we need η1 , η2 . . . , ηn not S
too dispersed and concentrate around their mean nη . The extent to which they need to be concentrated is governed by the quantum energy Na through the ratio ccn1 . For a fixed n, as we increase Na , ccn1 increases towards 1, and η1 , η2 . . . , ηn can be slightly more dispersed while satisfying (18). Although this argument provides intuition for the general case, it is not a tight analysis. In the case of sending n = 2 probes, with classical coherent energey per-pulse N = 100, quantum energy per-pulse −1 −1 Na = 0.558 (6dB of squeezing as before), numerical results indicate that Tr(Is,d ) < Tr(Ie,d ) for all choices of η1 and η2 (Figure 1).
4
Routing probes in a network
A network is an undirected graph G = (V, E) with a given set of monitors M ⊆ V , where each edge e ∈ E is associated with an unknown channel transmissivity ηe ∈ (0, 1]. We think of each probe P as a multiset of edges. While distinct probes may intersect on a subset of common edges, what we showed in § 3.2 alludes 9
to the fact that sharing entanglement among such probes is unlikely to be beneficial. This motivates us to again consider how each individual probe is routed in the network, without worrying about the correlation among distinct probes, a setting similar to [41]. Here our goal is to construct a set of probes P that can identify all link transmissivities, while ensuring the observations from P are as informationally orthogonal as possible. We introduce the notions of identifiability and information orthogonality in § 4.1, and connect information orthogonality with graph properties in § 4.2. Then in § 4.3, we propose an algorithm that constructs a set of probes P with these desirable properties. We illustrate the ideas from this section using a small network in Figure 2.
4.1
The probe construction problem
Identifiability. In stochastic network tomography, a set of probes P, together with its underlying network (graph) G = (V, E), defines a |P|×|E| measurement matrix A. Each row of A corresponds to a probe P ∈ P, each column in A corresponds to an edge e ∈ E, and the (i, j)-entry Ai,j describes the number of times the ith probe Pi passes through the j-th edge ej . Using the measurement matrix A, the problem of estimating link transmissivities in a network can be Q cast as a linear Q system Az = w, Q where z = (log η1 , log η2 , . . . , log η|E| ) is a bijection of η, and w = (log( e∈P1 ηe ), log( e∈P2 ηe ), . . . , log( e∈P|P| ηe )) is a column vector related to the transmissivities of each probe in P. Since the observations from P depend on η only through w, and w can be estimated consistently from P, it is known that η is identifiable if and only if A has full column rank [22]. This indicates, that if we think of each column in A as the signature of that edge, for probes P to be able to identify all link transmissivities, the signatures of the edges must be linearly independent. Information orthogonality. In classical network tomography, once given a measurement matrix, and some experiment design, the problem of solving the unknown parameters is often treated as a maximum likelihood estimation problem [7, 22, 39]. In our context, if we use quantum implementations of the probes (§ 3.1), solving the maximum likelihood estimator (MLE) of η requires solving a system of nonlinear equations, which generally admits no analytical solution. Then, to obtain an approximation of the MLE, one has to rely on various gradient-based optimization methods, such as the BFGS algorithm [4, 15, 19, 32]. Recall that |E| is the number of links in a network. If we send w probes in total, and on average each 2 probe passes through t edges, each iteration of the BFGS algorithm has time complexity O(|E| + wt), and existing heuristics suggest that BFGS often requires roughly O(|E|) iterations before converging rapidly [30]. 3 For a large network, a time complexity of Ω(|E| ) can be prohibitively expensive. In this case, if the probes are designed in a way that enables solving for smaller subnetworks in parallel, the time needed to solve for a large network can be greatly reduced. This brings about the notion of information orthogonality. Definition 1 (Information orthogonality [11]). k sets of parameters H1 , H2 , . . . , Hk are information orthogonal, if for any ηi ∈ Hx and any ηj ∈ Hy with distinct x, y ∈ [k], the corresponding entry Ii,j in the FIM I satisfies Ii,j = 0. Specific to our case of network tomography, information orthogonality implies optimization decoupling.4 This is to say, that the more information orthogonal sets of parameters we have, the more instances can be run in parallel. Therefore, in constructing the probes, we solve the following problem: Problem 1. Given a graph G and a set of monitors M , construct a set of probes P that (i) can identify all link transmissivities; and (ii) maximizes the number of information orthogonal subsets of link transmissivities. 4 This is not the case in general. However, in our context, the intuition is that, probes in one subnetwork does not contribute to objective functions (e.g., the maximum likelihood function) of other networks, therefore the objective functions of separate subnetworks can be decoupled, and information orthogonality implies optimization decoupling.
10
3 η2 2 η1
3 P3
η3 η5
4
2 η4
P1
η6 1
5
(a) A network G with a set of monitors M = { 1 , 5 }. Other vertices in G correspond to optical switches that can pass through the probes.
1
P5 P2
P6
3
3 G2
3
G1
P3
4 2
4
4
2
5
P4
1 1
5
5
(c) P in (b) can be grouped into a maximum subgraph cover: G1 is obtained by grouping P1 , P2 and P3 , G2 is obtained by grouping P 4 and P5 , G3 comes from P6 .
(b) Running Algorithm 1 on G and M returns a set of graph theoretic-probes P = {P1 , P2 , P3 , P4 , P5 , P6 }.
P1
G3 1
P5 P2′
P6
4 P4 5
(d) In contrast, this set of probes only induces 2 information orthogonal subsets of link transmissivities: {η1 , η2 , η3 , η4 , η5 } and {η6 }.
Figure 2: A network and two sets of probes that guarantees identifiability.
4.2
Connecting information orthogonality with graph properties
Compared to the general multi-parameter estimation problems, the uniqueness of network tomography stems from the fact that the estimated parameters are graph-constrained. Next, we establish connections between information orthogonality and graph properties, which would allow us to upper bound the maximum number of information orthogonal sets for a given network topology, and set the stage for proving the optimality of our probe construction algorithm in § 4.3. First we show that if two probes are edge-disjoint, their corresponding sets of link transmissivities are information orthogonal. Recall that in this section, we think of a probe P as a multiset of edges. Let supp(P ) denote the underlying set of P , i.e., the set of distinct edges probe P passes through. Claim 2. For probes P1 and P2 , let Hi be the set of link transmissivities associated with edges in Pi , Hi = {ηi | ∀ei ∈ supp(Pi )}, i = 1, 2. H1 and H2 are information orthogonal if and only if supp(P1 )∩supp(P2 ) = ∅. Proof sketch. We show that if supp(P1 ) ∩ supp(P2 ) = ∅, H1 and H2 are information orthogonal. W.l.o.g., we assume the parameters are indexed such that the covariance matrix Σ is block diagonal, with parameters from H1 in one block, and parameters from H2 in another block.5 This is possible due to the fact that distinct probes are not entangled by assumption, so there is no correlation between P1 and P2 . Then Σ−1 is also block diagonal, with parameters from H1 in one block, and parameters from H2 in another block. For any ηi ∈ H1 and any ηj ∈ H2 , one can check that similar to (28), the first term in Ii,j (1) is a rescaling of −1 Σ−1 i,j . Since ηi and ηj are located in separate blocks, Σi,j = 0. For the second term in Ii,j , it is not hard to check that the matrix multiplication of the chain of block diagonal matrices yields a zero matrix. For the other direction, a similar reasoning gives that if supp(P1 ) ∩ supp(P2 ) ̸= ∅, H1 and H2 are no longer information orthogonal. Given a set of probes P on a graph G, we can group subsets of P into subgraphs of G by taking all vertices and edges of the probes. Denote V (P ) as the set of vertices a probe P passes through, including its two endpoints. Grouping probes P1 , P2 , . . . , Pk yields a subgraph G1 = (V (G1 ), E(G1 )), where V (G1 ) = Sk Sk i=1 supp(Pi ). A direct consequence of Claim 2 is that, if two subgraphs are i=1 V (Pi ), and E(G1 ) = edge-disjoint, their corresponding sets of link transmissivities are information orthogonal. 5 Strictly speaking, we need to specify the physical implementations of the probes to write the covariance matrix Σ. Though here it is enough to think of Σ abstractly, as a block diagonal matrix.
11
Corollary 1. For subgraphs G1 = (V (G1 ), E(G1 )) and G2 = (V (G2 ), E(G2 )), let Hi be the set of link transmissivities associated with edges in Gi , Hi = {ηi | ∀ei ∈ E(Gi )}, i = 1, 2. H1 and H2 are information orthogonal if and only if E(G1 ) ∩ E(G2 ) = ∅. Then, to maximize the number of information orthogonal sets of parameters, we just need to maximize the number of edge-disjoint subgraphs in G. Note that these are not meant to be arbitrary subgraphs of G. Each subgraph should be obtained by grouping some subset of the probes. This gives rise to the definition of the subgraph cover. Definition 2 (Subgraph cover). Given a graph G = (V (G), E(G)) with monitors M ⊆ V , a set of connected subgraphs {Gi = (V (Gi ), E(Gi ))}m i=1 is a subgraph cover of G if 1) E(Gi ) ̸= ∅ and V (Gi ) ∩ M ̸= ∅, for all i ∈ [m] (every subgraph has at least an edge and a monitor); 2) E(Gi ) ∩ E(Gj ) = ∅ for all i ̸= j ∈ [m] (subgraphs are edge-disjoint); and Sm 3) i=1 E(Gi ) = E(G) (all edges in G are covered). {Gi = (V (Gi ), E(Gi ))}m i=1 is a maximum subgraph cover of G if m is maximized. To upper bound m, let deg(S) be the number of edges with exactly one endpoint in S, deg(S) = |{(u, v) ∈ E | u ∈ S, v ∈ / S}|. Denote E(S) as the set of edges with both endpoints in S, E(S) = {(u, v) ∈ E | u, v ∈ S}. Fact 3. For any subgraph cover {Gi = (V (Gi ), E(Gi ))}m i=1 of a graph G with monitors M , m ≤ deg(M ) + |E(M )|. Proof. Consider all edges in E(G) that are incident to at least one vertex in M , there are deg(M ) + |E(M )| number of such edges. Due to Condition 1), each such edge contributes at most one subgraph, while edges not incident to M cannot create any new subgraph. It follows that m ≤ deg(M ) + |E(M )|. If a set of probes can be grouped into a maximum subgraph cover, it effectively maximizes the number of information orthogonal subsets of link transmissivities, thus addressing Problem 1(ii). The subtlety lies in whether the upper bound on m (Fact 3) is tight and, if so, whether there exists a set of probes that attains it. The algorithm we introduce next in § 4.3 answers both questions in the affirmative.
4.3
The probe construction algorithm
Algorithm. Given a graph G and a set of monitors M , we iteratively construct one probe for each edge in E(G). While we are not explicitly trying to minimize the length of the probes in this work, restricting our attention to the shortest loop-back probes in most iterations is helpful in two respects. As noted in [41], quantum probes are inherently sensitive to the distance they travel, it is therefore always desirable to use shorter probes whenever possible. Moreover, a shortest loop-back probe passes through the least number of distinct edges possible (when G is unweighted). A set of shorter probes are less likely to intersect on many edges, which results in better chances of maximizing information orthogonality. Algorithm 1 describes FindProbe(G, M ), our probe construction algorithm. For each edge incident to at least one monitor, we simply construct a probe that only passes through that edge (Steps 4-7). For each edge that is further away from the monitors, similar in spirit to [41, Algorithm 3], we use all-pair shortest paths to generate the shortest loop-back probe that passes through the edge (Steps 9-11). To obtain the all-pair shortest paths (Step 1), we opt for a version of the Floyd-Warshall algorithm (e.g., § 25.2 in [10]), which not only returns the all-pair shortest distances, but also allows the construction of the shortest paths using a predecessor array. The notation u1 ⇝ u2 ⇝ · · · ui ⇝ ui+1 ⇝ · · · ⇝ uk refers to the concatenation of the shortest paths from ui to ui+1 , i ∈ [k − 1].
12
Algorithm 1 FindProbe(G, M ) Input: A graph G = (V (G), E(G)), and a set of monitors M ; Output: A set of distinct probes P. 1: Run Floyd-Warshall with path construction on G = (V, E), obtain distance matrix D and predecessor array T ▷ D(u, v) is the shortest distance from u to v, and T (u, v) gives the penultimate vertex on the shortest path from u to v, both in G. 2: P ← ∅ 3: for (u, v) ∈ E do 4: if both u, v ∈ M then 5: Construct P to be u ⇝ v 6: else if Exactly one of u, v ∈ M (w.l.o.g. say u ∈ M ) then 7: Construct P to be u ⇝ v ⇝ u 8: else 9: mu ← argminm∈M D(m, u) 10: mv ← argminm∈M D(v, m) 11: Let P be the shorter of mu ⇝ u ⇝ v ⇝ u ⇝ mu and mv ⇝ v ⇝ u ⇝ v ⇝ mv (If D(mu , u) = D(mv , v), let P be mu ⇝ u ⇝ v ⇝ u ⇝ mu if and only if mu is lexicographically smaller than mv ) 12: Add P to P 13: return P
Correctness. Next we show that Algorithm 1 correctly outputs a solution to Problem 1. We start by showing that the probes generated by Algorithm 1 guarantee identifiability. Lemma 1. Given a graph G with monitors M and unknown link transmissivities η = (η1 , η2 , . . . , ηn ), η is identifiable from P = FindProbe(G, M ). Proof sketch. We sketch a proof using induction on the length of the probes generated by FindProbe(G, M ). For the base case, we have probes of length 1 or 2 (from Steps 4-7). These probes pass through exactly 1 edge incident to M . The transmissivity of each such edge (u1 , v1 ) is identifiable from the probe that only passes through (u1 , v1 ). Assuming all edges on probes of length at most 2k are identifiable for some positive integer k, we have that on a probe P with length 2(k + 1), the transmissivities of all but one edge (u2 , v2 ) are identifiable by the induction hypothesis, with (u2 , v2 ) being the edge furthest away from M . Then the observation from P , together with the other transmissivities that are identifiable on P , suffice to identify the transmissivity of (u2 , v2 ). In fact, the induction argument mirrors the steps of Gaussian elimination applied to the measurement matrix A associated with P. At the end of the induction, up to relabeling of the probes, A is in row echelon form, with exactly n nonzero pivots. We can then conclude that A has full column rank, thus making η identifiable from P. To demonstrate P = FindProbe(G, M ) also maximizes the number of information orthogonal subsets of ∗ m∗ link transmissivities, we construct a sequence of subgraphs {Gi }m i=1 from P, check that {Gi }i=1 is a subgraph ∗ cover of G, and prove that {Gi }m i=1 is maximum by attaining the upper bound in Fact 3. Since P can be grouped into a maximum subgraph cover, it follows that P satisfies satisfies Problem 1(ii). Lemma 2. Given a graph G with monitors M and unknown link transmissivities {η1 , η2 , . . . , ηn }, P = FindProbe(G, M ) maximizes the number of information orthogonal subsets of {η1 , η2 , . . . , ηn }. ∗
Proof. We start by constructing a sequence of subgraphs {Gi }m i=1 from P. Let P1 , P2 and P3 be the sets of probes generated in Steps 5, 7 and 11 of Algorithm 1, respectively. Clearly, P1 ∪ P2 ∪ P3 = P. (a) For each Pi ∈ P1 ∪ P2 , supp(Pi ) is an edge incident to some vertex in M . Define subgraph Gi for each Pi , where V (Gi ) = V (Pi ), and E(Gi ) = supp(Pi ).
13
(b) For each Pj ∈ P3 , by Step 11, there exists a unique Pi∗ ∈ P2 , such that supp(Pi∗ ) ⊆ supp(Pj ). Then add Pj to Gi∗ , that is, update V (Gi∗ ) ← V (Gi∗ ) ∪ V (Pj ), and E(Gi∗ ) ← E(Gi∗ ) ∪ supp(Pj ). ∗
Next we verify that {Gi }m i=1 is indeed a subgraph cover. Condition 1) in Definition 2 is guaranteed to hold by (a). Condition 3) is satisfied by the fact that Algorithm 1 iteratively generates one probe P for each edge (u, v) ∈ E(G), and (u, v) ∈ supp(P ). To prove that Condition 2) is also satisfied, suppose for ∗ contradiction that there exists subgraphs G1 and G2 in {Gi }m i=1 , such that E(G1 ) ∩ E(G2 ) ̸= ∅. There must exist P1 from the construction of G1 , and P2 from the construction of G2 , such that some edge (u, v) ∈ supp(P1 )∩supp(P2 ). Let mu and mv be the monitors on P1 and P2 , respectively. By the construction of subgraphs, we have that mu ̸= mv . W.l.o.g., assume mu is the monitor closer to u, and mv the monitor closer to v. Then P1 corresponds to mu ⇝ u ⇝ v ⇝ · · · ⇝ v ⇝ u ⇝ mu , and P2 corresponds to mv ⇝ v ⇝ u ⇝ · · · ⇝ u ⇝ v ⇝ mv . In constructing P1 , Steps 9-11 ensures that D(mu , u) ≤ D(mv , v). Similarly from P2 , we have D(mu , u) ≥ D(mv , v). If D(mu , u) ̸= D(mv , v), we have a contradiction. When D(mu , u) = D(mv , v), Step 11 indicates that we always breaks ties consistently. That is, either P1 and P2 both pass through mu ⇝ u, or they both pass through mv ⇝ v. This contradicts the fact that mu ̸= mv . Finally, observe that only (a) created |P1 ∪ P2 | subgraphs, while (b) updated the existing subgraphs. ∗ ∗ Therefore, we have that {Gi }m i=1 is a maximum subgraph cover with m = deg(M ) + |E(M )|. Time complexity. Suppose the given graph G has |V | vertices, |E| edges, and |M | monitors. Running 3 Floyd-Warshall on G (Step 1) takes time O(|V | ). For each edge incident to M , it only takes constant time to construct a probe (Steps 4-7). These edges together contribute O(deg(M ) + |E(M )|) time. For each of the rest of the |E| − (deg(M ) + |E(M )|) edges that is further away from M , locating monitors closest to each endpoint (Steps 9-10) takes time O(|M |). Constructing a probe (Step 11) requires at most O(|V |) time. The time it takes to report n probes is clearly subsumed by previous steps of the algorithm. The overall time 3 complexity of FindProbe(G, M ) adds up to O(|V | + |V | · |E| − |V | · (deg(M ) + |E(M )|)). Even though the Floyd-Warshall algorithm dominates the runtime, it is clear that the more monitors we have, the more shorter probes we can construct, and the faster is Algorithm 1.
5
Quantum improvement in a network
Given two sets of probes P and P ′ , each capable of identifying all links in a network, which set better estimates the link transmissivities? To address this question, we consider the FIM induced by a set of probes in the general network case, and characterize the determinant of the FIM, and the trace of its inverse. Recall that each probe (P, impl(P ), t(P ), c(P )) ∈ P corresponds to a channel with FI IP . In § 5.1, we shall see that both the determinant of the FIM and the trace of its inverse relate neatly to the channel FI of the individual probes. Finally, we show why the two metrics admit particularly clean closed-forms in § 5.2.
5.1
The two metrics for a general network
Our main result below provides explicit expressions for the the determinant of the FIM, and the trace of its inverse: Lemma 3. Given a set of probes P = {(Pi , impl(Pi ), t(Pi ), c(Pi ))}ni=1 that identifies all link transmissivities {η1 , η2 , . . . , ηn } of a graph G, P induces a measurement matrix A and a FIM I. Then ! ! n n Y Y −2 2 2 det(I) = ηi · det(A) · c(Pi ) · ηPi IPi , (19) i=1 n X
i=1 n X
(A−1 )2i,j Tr(I −1 ) = ηi2 , c(Pj ) · ηP2 j IPj i=1 j=1
(20)
where ηPi and IPi are the channel transmissivity and the FI corresponding to the probe (Pi , impl(Pi ), t(Pi ), c(Pi )). 14
First we clarify that, since n link transmissivities are identifiable by n 4-tuple probes, P1 , P2 , . . . , Pn must be distinct. Let P = {P1 , P2 , . . . , Pn } be the set of graph-theoretic probes. We have that the measurement matrix A, defined solely based on P, must be a non-singular matrix, det(A) is therefore well-defined. A notable feature of Lemma 3 is that it relates the two metrics of interest in the general setting to the FI of the channel case, while decoupling the physical implementation of the probes from their graph-theoretic properties. This feature makes it especially convenient when comparing different physical implementations given the same set of graph-theoretic probes. For example, given two sets of probes P and P ′ , both with the same set of graph-theoretic probes P = {P1 , P2 , . . . , Pn }, P and P ′ only differ in the impl(Pi ), t(Pi ) and c(Pi ) on some subset of the Pi . Since the dependence on t(Pi ) is implicit in the channel FI IPi , when switching from P to P ′ , only c(Pi ) and IPi may change in (19) and (20). Using the prime (′ ) to label the quantities det(I ′ ) induced by P ′ , we have that the ratio det(I ′ ) completely depends on the physical implementations of the probes, while Tr(I ′
−1
) − Tr(I −1 ) is a weighted sum of c(Pi1)′ I ′ − c(Pi1)IP , with weights solely determined by Pi
the graph-theoretic properties of P:
i
n det(I ′ ) Y c(Pi )′ · IP′ i = , det(I ′ ) i=1 c(Pi ) · IPi
Tr(I
′ −1
) − Tr(I
−1
)=
n n X X ηi2 (A−1 )2i,j i=1 j=1
ηP2 j
(21) 1 1 − ′ ′ c(Pi ) IPi c(Pi )IPi
.
(22)
In particular, if P is implemented by classical probes, and P ′ is quantum, (21) and (22) together with Fact 2 characterize the quantum improvement in a general network. In fact, Lemma 3 could also apply in other contexts. While we have not focused on finding the optimal probes under resource constraints, (19) and (20) could serve as objective functions should such optimization problem arises. When only local changes are made to a small subset of the probes, many factors in these expressions remain unchanged, making them efficient to evaluate. A subtle issue, however, is that evaluating (19) and (20) requires prior knowledge of η1 , η2 , . . . , ηn , the very parameters we seek to estimate in teh tomography problem. A potential solution is to first obtain rough estimates of these link transmissivities, and use the estimates in the objective function. We leave this optimization problem for future work.
5.2
Proof of Lemma 3
To prove Lemma 3, it is important to understand the structure of the covariance matrix Σ induced by P. Notice that for any pair of distinct P1 and P2 from P, regardless of whether P1 and P2 share edges, observations from (P1 , impl(P1 ), t(P1 ), m(P1 )) and (P2 , impl(P2 ), t(P2 ), m(P2 )) are always uncorrrelated. This implies that Σ is block diagonal, where a probe (P, impl(P ), t(P ), m(P )) occupies m(P ) number of blocks of size t(P ) × t(P ) each (a fact glossed over in the proof sketch of Claim 2). In particular, a probe (P, impl(P ), t(P ), m(P )) implemented by coherent or squeezed states, i.e., impl(P ) = ‘coherent’ or ‘squeezed’, contributes m(P ) elements on the the diagonal of Σ. It is also implicit from § 3.1 that (P ) Σ−1 preserves the same block diagonal structure. Denote Ii,j as the contribution to Ii,j from probe −1 (P, impl(P ), t(P ), m(P )). Since Σ and Σ are both block diagonal, (1) implies X (P ) Ii,j = m(P ) · Ii,j . (23) P ∈P
A direct application of (1) to the channel corresponding to (P, impl(P ), t(P ), m(P )) also gives the channel FI 1 ∂ΣP −1 ∂ΣP ∂µTP −1 ∂µP IP = ΣP + Tr Σ−1 Σ . (24) P ∂ηP ∂ηP 2 ∂ηP P ∂ηP
15
Following (24) and the chain rule, (P )
∂µTP −1 ∂µP 1 ∂ΣP −1 ∂ΣP ΣP + Tr Σ−1 Σ P ∂ηi ∂ηj 2 ∂ηi P ∂ηj ∂µTP ∂ηP −1 ∂µP ∂ηP 1 ∂ΣP ∂ηP −1 ∂ΣP ∂ηP = · ΣP · + Tr Σ−1 · Σ · P ∂ηP ∂ηi ∂ηP ∂ηj 2 ∂ηP ∂ηi P ∂ηP ∂ηj ∂ηP ∂ηP = · · IP . ∂ηi ∂ηj
Ii,j =
(25)
(P )
Here in Ii,j , we can already observe a separation between the graph-theoretic properties of (P, impl(P ), t(P ), m(P )) ∂ηP P and its physical implementation — the factor ∂η ∂ηi · ∂ηj only depends on how the probe is routed in the network. P Next we express ∂η ∂ηi in terms of the measurement matrix A. Recall that each row in the A corresponds to a probe P , and each column in A corresponds to an edge e. With a slight abuse of notation, we write AP,e as the entry in A corresponding to probe (P, impl(P ), t(P ), m(P )) and edge e, and AP,e specifies the Q P A multiplicity of e in the multiset P . Then we have ηP = e∈supp(P ) ηe P,e , and ln ηP = e∈supp(P ) AP,e ln ηe . Taking the partial derivative with respect to ηi (the transmissivity of edge ei ) on both sides, we have AP,ei AP,ei ∂ ln ηP ∂ηP ∂ηP ∂ ln ηi ∂ ln ηP 1 ∂ηi AP,ei · ∂ηi = ηi . Applying the chain rule to the LHS leads to ∂ηP · ∂ηi = ηP · ∂ηi = ηi , (P )
η2
ηP P P which gives ∂η ∂ηi = AP,ei · ηi . Therefore, we can rewrite (25) as Ii,j = AP,ei AP,ej · ηi ηj IP . Then by (23),
Ii,j =
X
m(P ) · AP,ei AP,ej ·
P ∈P
ηP2 IP . ηi ηj
(26)
Let Dη = diag(η1 , η2 , . . . , ηn ) and DP = diag(c(P1 ) · ηP2 1 IP1 , c(P2 ) · ηP2 2 IP2 , . . . , c(Pn ) · ηP2 n IPn ). One can check that (26) is in fact consistent with I being the following matrix product: I = Dη−1 AT DP ADη−1 .
(27)
Therefore, (19) follows from the fact that A, Dη and DP are all non-singular matrices. For (20), by (27) and (AT )−1 = (A−1 )T , −1 I −1 = Dη A−1 DP (A−1 )T Dη .
Using the cyclic property of the trace, −1 Tr(I −1 ) = Tr(Dη2 A−1 DP (A−1 )T ) n X −1 = ηi2 (A−1 DP (A−1 )T )i,i i=1
=
=
n X
n X (A−1 )i,j ·
i=1
j=1
n X
n X
i=1
6
ηi2 ηi2
1 · (A−1 )Ti,j c(Pj ) · ηP2 j IPj
(A−1 )2i,j . c(Pj ) · ηP2 j IPj j=1
Related Work
The probes. The quantum and classical probes in this work have previously been used in the context of detecting drops in link transmissivity within a channel [20], and localizing transmission loss change in a general network [41]. In both cases, the quantum speedup essentially comes from the fact that quantum probes induce a larger Kullback–Leibler divergence from the pre-change to the post-change distributions. Here we use these probes to estimate link transmissivities, and the quantum improvement is quantified by the determinannt of the FIM, and the trace of its inverse. 16
Sharing entanglement. When we go beyond a single channel and look at a general network, an interesting question that arises is whether sharing entanglement across probes traversing different paths is beneficial. While we do not yet have a rigorous argument, the evidence in § 3.2 and Appendix A points to a negative answer. This is in fact unsurprising. In multiparameter quantum metrology, it has been shown that entanglement does not provide a systematic advantage over displaced squeezed states [17, 29]. It remains open whether we can leverage techniques from quantum metrology to formally prove such no-go results in network tomography. Probe construction algorithms. A large body of work has studied how to route the probes in a network [41, 27, 1, 40], however, to the best of our knowledge, none has focused on maximizing the number of information orthogonal sets of unknown parameters. Algorithm 1 bears the closest resemblance to the probe construction algorithm in [41]. While we have not explicitly tried to minimize the length of the longest probe (a central goal in [41]), it is not hard to see that Algorithm 1 achieves this goal approximately: the longest probe it generates exceeds the minimum possible by at most 1 if the underlying graph is unweighted. The metrics. While we think of each link in the network as a pure-loss bosonic channel, prior works in quantum network tomography have modeled the links as bit-flip [12], depolarizing [12] and Pauli channels [38]. In both [38] and [12], the trace of the inverse quantum FIM has been used to evaluate the performance of the estimation. The two metrics in this work, the determinant of the FIM, and the trace of its inverse, have been studied in finding the optimal probe allocation in classical network tomography [22]. Although the packet loss tomography in [22] estimates upper-layer link success rates, whereas we focus on physical-layer link transmissivity, and the observations from the probes follow entirely different distributions, we nevertheless observe a striking similarity between our FIM (27) and (17) in [22].
7
Conclusion
In this paper, we consider the problem of estimating link transmissivities in optical networks using quantum probes. To decide how to route the probes in a network, we propose a probe construction algorithm that not only guarantees identifiability, but also maximizes the number of information orthogonal sets of link transmissivities. To measure the performance of a given set of probes, we derive closed-form expressions for the determinant of the FIM, and the trace of its inverse. In particular, both metrics can be used to quantify the quantum improvement in this estimation problem. As noted at the end of § 5.1, both metrics could potentially serve as objective functions in the associated optimization problem, namely, finding the optimal set of probes under resource constraints. We leave this for future work.
Acknowledgment The initial stage of this research was supported by the DARPA Quantum Augmented Networking (QuANET) Program under contract number HR001124C0405.
17
References [1] Satyajeet S Ahuja, Srinivasan Ramasubramanian, and Marwan Krunz. Srlg failure localization in optical networks. IEEE/ACM Transactions on Networking, 19(4):989–999, 2011. [2] Anthony Atkinson, Alexander Donev, and Randall Tobias. Optimum experimental designs, with SAS, volume 34. OUP Oxford, 2007. [3] Laurent Bobelin and Traian Muntean. Algorithms for network topology discovery using end-to-end measurements. In 2008 International Symposium on Parallel and Distributed Computing, pages 267– 274. IEEE, 2008. [4] Charles George Broyden. The convergence of a class of double-rank minimization algorithms 1. general considerations. IMA Journal of Applied Mathematics, 6(1):76–90, 1970. [5] Tian Bu, Nick Duffield, Francesco Lo Presti, and Don Towsley. Network tomography on general topologies. ACM SIGMETRICS Performance Evaluation Review, 30(1):21–30, 2002. [6] Jeffrey D Case, Mark Fedor, Martin L Schoffstall, and James Davin. Simple network management protocol (SNMP). Technical report, 1989. [7] Rui Castro, Mark Coates, Gang Liang, Robert Nowak, and Bin Yu. Network Tomography: Recent Developments. Statistical Science, 19(3):499 – 517, 2004. [8] Ryan Chard, Kris Bubendorfer, and Bryan Ng. Network health and e-science in commercial clouds. Future Generation Computer Systems, 56:595–604, 2016. [9] Mark J Coates and Robert D Nowak. Network tomography for internal delay estimation. In 2001 IEEE International Conference on Acoustics, Speech, and Signal Processing. Proceedings (Cat. No. 01CH37221), volume 6, pages 3409–3412. IEEE, 2001. [10] Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2022. [11] David Roxbee Cox and Nancy Reid. Parameter orthogonality and approximate conditional inference. Journal of the Royal Statistical Society: Series B (Methodological), 49(1):1–18, 1987. [12] Matheus Guedes De Andrade, Jake Navas, Saikat Guha, Inès Montaño, Michael Raymer, Brian Smith, and Don Towsley. Quantum network tomography. IEEE Network, 38(5):114–122, 2024. [13] Kiril Dichev, Fergal Reid, and Alexey Lastovetsky. Efficient and reliable network tomography in heterogeneous networks using bittorrent broadcasts and clustering algorithms. In SC’12: Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, pages 1–11. IEEE, 2012. [14] Nick G Duffield and F Lo Presti. Network tomography from measured end-to-end delay covariance. IEEE/ACM Transactions On Networking, 12(6):978–992, 2004. [15] Roger Fletcher. A new approach to variable metric algorithms. The computer journal, 13(3):317–322, 1970. [16] Zhan Gao, Mark Eisen, and Alejandro Ribeiro. Resource allocation via graph neural networks in free space optical fronthaul networks. In GLOBECOM 2020-2020 IEEE Global Communications Conference, pages 1–6. IEEE, 2020. [17] Manuel Gessner, Augusto Smerzi, and Luca Pezzè. Multiparameter squeezing for optimal quantum enhancements in sensor networks. Nature communications, 11(1):3817, 2020.
18
[18] Denisa Ghita, Hung Nguyen, Maciej Kurant, Katerina Argyraki, and Patrick Thiran. Netscope: Practical network loss tomography. In 2010 Proceedings IEEE INFOCOM, pages 1–9. IEEE, 2010. [19] Donald Goldfarb. A family of variable-metric methods derived by variational means. Mathematics of computation, 24(109):23–26, 1970. [20] Saikat Guha, Tiju Cherian John, Zihao Gong, and Prithwish Basu. Quantum-enhanced quickest change detection of transmission loss. Physical Review Letters, 135(21):210801, 2025. [21] Nicholas JA Harvey, Mihai Patrascu, Yonggang Wen, Sergey Yekhanin, and Vincent WS Chan. Nonadaptive fault diagnosis for all-optical networks via combinatorial group testing on graphs. In IEEE INFOCOM 2007-26th IEEE International Conference on Computer Communications, pages 697–705. IEEE, 2007. [22] Ting He, Chang Liu, Ananthram Swami, Don Towsley, Theodoros Salonidis, Andrei Iu Bejan, and Paul Yu. Fisher information-based experiment design for network tomography. ACM SIGMETRICS Performance Evaluation Review, 43(1):389–402, 2015. [23] Ting He, Liang Ma, Ananthram Swami, and Don Towsley. Network tomography: identifiability, measurement design, and network state inference. Cambridge University Press, 2021. [24] Fredrik Korsbäck, Lincoln Dale, and Dave McGaugh. Growing AWS internet peering with 400 GbE, 2023. https://aws.amazon.com/blogs/networking-and-content-delivery/ growing-aws-internet-peering-with-400-gbe/. [25] Jintao Liang, Aizaz U Chaudhry, Eylem Erdogan, and Halim Yanikomeroglu. Link budget analysis for free-space optical satellite networks. In 2022 IEEE 23rd International Symposium on a World of Wireless, Mobile and Multimedia Networks (WoWMoM), pages 471–476. IEEE, 2022. [26] Joseph M Lukens, Nicholas A Peters, and Bing Qi. Hybrid classical-quantum communication networks. Progress in Quantum Electronics, page 100586, 2025. [27] Liang Ma, Ting He, Kin K Leung, Don Towsley, and Ananthram Swami. Efficient identification of additive link metrics via network tomography. In 2013 IEEE 33rd International Conference on Distributed Computing Systems, pages 581–590. IEEE, 2013. [28] Stephen Nellis. Cisco and qunnect build quantum network using new york fiber optic cables. https://www.reuters.com/business/media-telecom/ cisco-qunnect-build-quantum-network-using-new-york-fiber-optic-cables-2026-02-18/, February 2026. Accessed: 2026-04-17. [29] Rosanna Nichols, Pietro Liuzzo-Scorpo, Paul A Knott, and Gerardo Adesso. Multiparameter gaussian quantum metrology. Physical Review A, 98(1):012114, 2018. [30] Jorge Nocedal and Stephen J Wright. Numerical optimization. Springer, 2006. [31] Leon Poutievski, Omid Mashayekhi, Joon Ong, Arjun Singh, Mukarram Tariq, Rui Wang, Jianan Zhang, Virginia Beauregard, Patrick Conner, Steve Gribble, et al. Jupiter evolving: transforming google’s datacenter network via optical circuit switches and software-defined networking. In Proceedings of the ACM SIGCOMM 2022 Conference, pages 66–85, 2022. [32] David F Shanno. Conditioning of quasi-newton methods for function minimization. Mathematics of computation, 24(111):647–656, 1970. [33] Jack Sherman and Winifred J Morrison. Adjustment of an inverse matrix corresponding to a change in one element of a given matrix. The Annals of Mathematical Statistics, 21(1):124–127, 1950.
19
[34] Yolanda Tsang, Mark Coates, and Robert Nowak. Passive network tomography using em algorithms. In 2001 IEEE International Conference on Acoustics, Speech, and Signal Processing. Proceedings (Cat. No. 01CH37221), volume 3, pages 1469–1472. IEEE, 2001. [35] Yolanda Tsang, Mark Coates, and Robert D Nowak. Network delay tomography. IEEE Transactions on Signal Processing, 51(8):2125–2136, 2003. [36] Yehuda Vardi. Network tomography: Estimating source-destination traffic intensities from link data. Journal of the American statistical association, 91(433):365–377, 1996. [37] Lukas Velush. Boosting our connectivity with our own next-generation optical network, 2023. https://www.microsoft.com/insidetrack/blog/ boosting-our-connectivity-with-our-own-next-generation-optical-network/. [38] Xuchuang Wang, Matheus Guedes De Andrade, Guus Avis, Yu-Zhen Janice Chen, Mohammad Hajiesmaili, and Don Towsley. Quantum network tomography for general topology with spam errors. arXiv preprint arXiv:2511.01074, 2025. [39] Bowei Xi, George Michailidis, and Vijayan N Nair. Estimating network loss rates using active tomography. Journal of the American Statistical Association, 101(476):1430–1448, 2006. [40] Yao Zhao, Yan Chen, and David Bindel. Towards unbiased end-to-end network diagnosis. IEEE/ACM Transactions on Networking, 17(6):1724–1737, 2009. [41] Yufei Zheng, Yu-Zhen Janice Chen, Prithwish Basu, and Don Towsley. A quantum speedup in localizing transmission loss change in optical networks. In 2025 IEEE International Conference on Quantum Computing and Engineering (QCE), volume 1, pages 958–968. IEEE, 2025.
20
0.2
0.4 1
0.6
0.8
1.0 0.0
0.2
0.4
0.6
0.8
Tr(FIMe 1) Tr(FIMs 1)
4e5 3e5 2e5 1e5 0 1.0
2
1.8e-2 1.5e-2 1.2e-2 9e-3 6e-3 3e-3 0 1.0 0.8 0.6 0.4 0.2 0.0 0.2 0.4 0.6 0.8 1.00.0
400000 300000 200000 100000
2
0.0
det(FIMs) det(FIMe)
max: 477384
min: 355
max: 0.0182 0.015 0.0125 0.01 0.0075 0.005 0.0025 min: 4.56e-05
1
−1 −1 (b) Tr(Ie,s ) − Tr(Is,s ) wrt η1 and η2 .
(a) det(Is,s ) − det(Ie,s ) wrt η1 and η2 .
Figure 3: Differences in the two metrics for the two-channel setup.
A
Sharing entanglement across two probes that share links
Consider two probes that are set through two channels with transmissivities η1 η2 and η2 , respectively. Fix the classical and quantum energy per-pulse, N and Na , we compare two cases: (i) each probe is a displaced squeezed state; and (ii) the two probes are entangled. We present numerical results demonstrating that, similar to the independent channel configuration in § 3.2, with respect to both the determinant of the FIM and the trace of its inverse, entangled probes perform worse than the ones implemented by independent squeezing. We use the subscript ‘·, s’ to distinguish this setup, where the channel transmissivities have shared factors. Recall that cn (7) hides the quantum energy Na . When the two probes are implemented by squeezed states, we have √ √ η1 η2 , µs,s = N · √ η2 1 c 1 η1 η2 − 4 0 4 , Σs,s = c1 η2 1 0 4 − 4 1 2N (1 − c1 η1 η2 ) + c21 η1 η2 2N (1 − c1 η2 ) + c21 η2 · , · 4η1 (1 − c1 η1 η2 )2 (1 − c1 η2 )2 2 η1 (1 − c1 η1 η2 )2 (η12 + η22 )(1 − c1 η2 )2 −1 Tr(Is,s ) = · + . η2 2N (1 − c1 η1 η2 ) + c21 η1 η2 2N (1 − c1 η2 ) + c21 η2
det(Is,s ) =
If the two probes are entangled, √
√ η η √1 2 , η2
µe,s =
N·
Σs,s =
c 2 η1 η2 1 4 −√ 8 c η η − 2 81 2
c
√
η η
− 2 81 2 c2 η2 1 4 − 8
! ,
32N 2 (2 − c2 η2 (1 + η1 ))2 + 12N c22 η2 (1 + η1 )(2 − c2 η2 (1 + η1 )) + c42 η22 (1 + η1 )2 , 16η1 (2 − c2 η2 (1 + η1 ))3 2(2 − c2 η2 (1 + η1 )) 4η1 ((1 + η1 )2 + η22 ) η22 (2 − c2 η2 (1 + η1 )) −1 · + . Tr(Is,s ) = (1 + η1 )η2 16N − c2 η2 (8N − c2 )(1 + η1 ) 8N − c2 η2 (4N − c2 )(1 + η1 )
det(Ie,s ) =
21
−1 −1 We compute det(Is,s ) − det(Ie,s ) (Figure 3a) and Tr(Ie,s ) − Tr(Is,s ) (Figure 3b) as η1 , η2 range from 0 −1 −1 to 1. Numerical evidence suggests that, we indeed have det(Is,s ) > det(Ie,s ) and Tr(Is,s ) < Tr(Ie,s ) for all η1 , η2 ∈ (0, 1].
B
The structure of Ie,d (proof of Claim 1)
To derive a closed-form for Ie,d , we mechanically derive each element that appears in (1) for (Ie,d )i,j . √ ∂µ √N ei by (11). Because Σe,d (12) is a rank-1 ap= First denote ei as the i-th unit vector, then ∂ηe,d 2 ηi i 4cn T proximation of 14 I, the Sherman-Morrison formula applies, and Σ−1 e,d = 4I + n−cn Sη vv . (Recall that √ √ √ v = ( η1 , η2 , . . . , ηn ).) The first term in (1) hence becomes
∂µTe,d N 1[i = j] ∂µe,d cn N · Σ−1 = √ · Σ−1 +N · √ ·. = e,d · e,d ∂ηi ∂ηj 4 ηi ηj n − cn Sη ηi ηj i,j
(28)
Therefore, the contribution to Ie,d from the first term in (1) is N · diag(
1 cn N 1 1 , ,..., ) + · uuT . η1 η2 ηn n − cn Sη
For the second term in (1), we have cn ∂vv T cn ∂Σe,d =− · =− ∂ηi 4n ∂ηi 4n
4cn For convenience, let b = n−c . Since v T ei = n Sη
Σ−1 e,d ·
∂v ∂v T · vT + v · ∂ηi ∂ηi √
=−
cn √ (ei v T + veTi ). 8n ηi
ηi , and v T v = Sη ,
∂Σe,d cn = − √ (4I + bvv T )(ei v T + veTi ) ∂ηi 8n ηi cn cn (4 + bSη ) T bcn T vv , = − √ ei v T − vei − √ 2n ηi 8n ηi 8n
Σ−1 e,d ·
cn ∂Σe,d ∂Σe,d bSη ) T bcn T √ ei v T + cn (4 + · Σ−1 · = ve vv + √ i e,d 2n ηi ∂ηi ∂ηj 8n ηi 8n{z } | | {z } | {z } (■)
(♦)
(▲)
cn cn (4 + bSη ) T bcn T T . · e v + ve + vv √ j 2n√ηj j 8n ηj 8n{z } | | {z } | {z } (□)
22
(△)
(♢)
Let 1[i = j] denote the indicator function, such that 1[i = j] = 1 if and only if the condition i = j holds, and 1[i = j] = 0 otherwise. By the cyclic property of the trace, we obtain the following product terms, Tr((■)(□)) =
c2n c2n c2n T T T T , · Tr(e v e v ) = · Tr(v e v e ) = √ √ i j j i 4n2 ηi ηj 4n2 ηi ηj 4n2
Tr((■)(△)) =
c2n (4 + bSη ) c2 Sη (4 + bSη ) c2 Sη (4 + bSη ) · Tr(ei v T veTj ) = n 2 √ · Tr(ei eTj ) = n 2 √ · 1[i = j], √ 2 16n ηi ηj 16n ηi ηj 16n ηi ηj
Tr((■)(♢)) =
bc2n Sη bc2n Sη bc2n Sη bc2n T T T T , · Tr(e v vv ) = · Tr(e v ) = · v e = √ √ √ i i i 16n2 ηi 16n2 ηi 16n2 ηi 16n2
Tr((▲)(□)) =
c2n (4 + bSη ) c2n (4 + bSη ) c2n Sη (4 + bSη ) T T T · Tr(ve e v ) = · 1 [i = j] · v v = · 1[i = j], √ √ √ j i 16n2 ηi ηj 16n2 ηi ηj 16n2 ηi ηj
Tr((▲)(△)) =
c2 (4 + bSη )2 c2 (4 + bSη )2 c2n (4 + bSη )2 , · Tr(veTi veTj ) = n · Tr(eTj v) = n √ √ 2 2 64n ηi ηj 64n ηj 64n2
Tr((▲)(♢)) =
bc2n (4 + bSη ) bc2n (4 + bSη ) bc2n Sη (4 + bSη ) T T T · Tr(vv , · Tr(ve vv ) = ) = √ i 64n2 ηi 64n2 64n2
Tr((♦)(□)) =
bc2n bc2n Sη bc2n T T T · Tr(vv ) = , · Tr(vv e v ) = √ j 16n2 ηj 16n2 16n2
Tr((♦)(△)) =
bc2n (4 + bSη ) bc2 Sη (4 + bSη ) , · Tr(vv T veTj ) = n √ 2 64n ηj 64n2
Tr((♦)(♢)) =
b2 c2n Sη2 b2 c2n T T · Tr(vv vv ) = . 64n2 64n2
Using the linearity of the trace, we get the second term in (1) by summing up all of the above, 1 ∂Σe,d 1[i = j] c2 (n + cn Sη ) c2n Sη −1 ∂Σe,d Tr Σ−1 · · √ · Σ · = n + . e,d e,d 2 2 ∂ηi ∂ηj 4n(n − cn Sη ) 4n(n − cn Sη ) ηi ηj The claim follows by combining (28) and (29), which gives c2n Sη 1[i = j] cn N c2n (n + cn Sη ) + N+ · √ (Ie,d )i,j = + . n − cn Sη 4n(n − cn Sη )2 4n(n − cn Sη ) ηi ηj
23
(29)