# Polarization rotation and near-Earth quantum communications

Pravin Kumar Dahal  Department of Physics & Astronomy, Macquarie University,
Sydney NSW 2109, Australia  Daniel R. Terno  Department of Physics &
Astronomy, Macquarie University, Sydney NSW 2109, Australia

###### Abstract

We revisit polarization rotation due to gravity, known as the gravitational
Faraday effect, with a view on its role in quantum communications with Earth-
orbiting satellites. In a static spherically symmetric gravitational field
Faraday rotation is purely a reference frame (gauge) effect. This is so also
in the leading post-Newtonian expansion of the Earth’s gravitational field.
However, establishing the local reference frame with respect to distant stars
leads to the nonzero Faraday phase. In communications between a ground station
and an Earth-orbiting spacecraft this phase is of the order of $10^{-10}$.
Under the same conditions the Wigner phase of special relativity is typically
of the order $10^{-4}$–$10^{-5}$. These phases lead to the physical lower
bound on communication errors. However, both types of errors can be
simultaneously mitigated. Moreover, they are countered by a fully reference
frame independent scheme that also handles arbitrary misalignments between the
reference frames of sender and receiver.

##  I Introduction

Space deployment of quantum technology [1, 3, 4] brings it into a weakly
relativistic regime. As a side effect, low-Earth orbit (LEO) quantum
communication satellites provide new opportunities to test fundamental
physics. Once these tiny physical effects fall within the sensitivity range of
these devices, they may impose constraints on practical quantum
communications, time-keeping, or remote sensing tasks. This dual relationship
between quantum technology and relativistic physics makes it important to
study the relativistic aspects of quantum information processing [5, 6, 7].

Qubits are routinely realized as polarization states of photons [8]. The
effects of special relativity (SR) on quantum-informational tasks with massive
and massless particles are well-understood [5, 7]. On the other hand, effects
of general relativity (GR) in quantum-optical LEO experiments were discussed
primarily in the context of interferometry [6, 9, 10, 11].

The dominant source of relativistic errors in this setting is the Wigner
rotation (or phase), a SR effect [5, 7]. Gravitational polarization rotation,
also known as the gravitational Faraday effect [12, 13] occurs in a variety of
astrophysical systems, such as accretion disks around astrophysical black hole
candidates [14] or gravitational lensing [15]. This effect was the subject of
a large number of theoretical investigations, first in the framework of
geometric optics [12, 13, 15, 16, 17], and recently in the post-eikonal
approximation [18, 19]. Interpretation of these results is sometimes
contradictory, as the crucial role of local reference frames and the ensuing
introduction of the standard polarization directions were not always treated
in a fully satisfactory manner.

The Faraday effect in quantum experiments was discussed in [20]. Geometric
optics approximation is sufficient to describe it in near-Earth environments.
In this framework a careful analysis of the local standard polarization
directions allows one to obtain transparent expressions for polarization
rotation [17]. In particular, it clarifies the statement about the absence of
polarization rotation in Schwarzschild space-time. For an open trajectory this
is true only for a particular choice of local polarization directions (that we
call the Newton gauge and review below). For a closed (in phase space)
trajectory the net rotation disappears in any gauge. Given that the leading
order corrections due to gravity result from the leading terms in the post-
Newtonian expansion of the Schwarzschild metric [21, 22], this result seems to
indicate that the Faraday rotation can be ignored. However, it was pointed out
in Ref. [23] that in realistic situations the closed spatial trajectories are
not closed in the phase space, as well as that enforcing the Newton gauge is
in general impractical. Hence, even if the gravitationally induced
polarization rotation in the near-Earth environment is essentially a pure
gauge effect, it cannot be simply dismissed.

We provide a simple estimation of this emitter- and observer-dependent phase
and give its explicit form in several settings. The phase errors due to SR can
be mitigated, and in the limit of sharply defined frequencies, completely
removed by a simple encoding procedure [24]. The same techniques are
applicable to counter the Faraday rotation.

The rest of this paper is organized as follows. In Sec. II we review the SR
effects. Polarization rotation in general stationary space-times is described
in Sec. III. In Sec. IV we evaluate the effects in communication with Earth-
orbiting satellites. In Sec. V we present a simple error-correcting scheme,
discuss the role of the relativistic errors (as well as errors due to the
reference frame misalignment), in quantum key distribution (QKD), and discuss
the feasibility of the error-correcting schemes. This is a fully reference
frame independent (RFI) scheme that may be useful not only for countering tiny
relativistic effects in communications with the LEO satellites, but also as
the major source of the phase errors — frame misalignment.

We work with $c=\hbar=G=1$. The constants $G$ and $c$ are restored in a small
number of expressions where their presence is helpful. The space-time metric
$\textsl{g}_{\mu\nu}$ has a signature $-+++$. The four-vectors are
distinguished by the sans font, ${\mathsf{k}}$,
$k^{\mu}=({\mathsf{k}})^{\mu}$. The three-dimensional spatial metric is
denoted as $\gamma_{mn}$, and three-dimensional vectors are set in boldface,
${\bf{k}}$, or are referred to by their explicit coordinate form, $k^{m}$. The
inner product in the metric $\gamma$ is denoted as
${\bf{k}}\\!\cdot\\!\mathbf{f}$, and the unit vectors in this metric are
distinguished by the caret, ${\hat{{\bf{k}}}}$,
${\hat{{\bf{k}}}}\cdot{\hat{{\bf{k}}}}\equiv 1$. Post-Newtonian calculations
employ a fiducial Euclidean space. Euclidean vectors are distinguished by
arrows, ${\vec{k}}$. Components of the two types of vectors may coincide,
$(\mathbf{v})^{m}=({\vec{b}})^{m}$, but
${\vec{b}}\\!\cdot\\!{\vec{k}}=\sum_{k=1}^{3}v^{m}k^{m}$. Accordingly, the
coordinate distance is the Euclidean length of the radius vector,
$r\equiv\sqrt{{\vec{x}}\\!\cdot\\!{\vec{x}}}$.

##  II Wigner rotation

Quantum states of a photon with a definite four-momentum
${\mathsf{k}}=(|{\bf{k}}|,{\bf{k}})$ can be represented either as Hilbert
space vectors or as complex polarization vectors in the usual three-
dimensional space,

$|\Psi_{\mathsf{k}}\rangle=f_{+}|{\mathsf{k}},+\rangle+f_{-}|{\mathsf{k}},-\rangle\quad\Leftrightarrow\quad{\hat{\mathbf{f}}}_{\bf{k}}=f_{+}{{\hat{\mathbf{b}}}}_{\hat{{\bf{k}}}}^{+}+f_{-}{{\hat{\mathbf{b}}}}_{\hat{{\bf{k}}}}^{-},$
(1)

with the transversal vectors ${\hat{\mathbf{b}}}^{\pm}_{\hat{{\bf{k}}}}$,
${\bf{k}}\cdot{\hat{\mathbf{b}}}^{\pm}_{\hat{{\bf{k}}}}=0$. The correspondence
is rooted in the relationship between finite-dimensional and unitary
representations of the Poincaré group [25, 26].

Unitary transformations $U$ of states of elementary particles are obtained via
the induced representation of the Poincaré group. Basis states that correspond
to arbitrary momenta ${\bf{k}}$ are defined with the help of the standard
Lorentz transformation $L({\mathsf{k}})$ that takes the four-momentum from the
standard value ${\mathsf{k}}_{S}$ to ${\mathsf{k}}$. The direction
${\hat{{\bf{k}}}}$ is determined by the spherical angles $(\theta,\phi)$. For
massless particles $k_{S}^{\mu}=(1,0,0,1)$ and

$L({\mathsf{k}})=R({\hat{{\bf{k}}}})B_{z}(\xi_{|{\bf{k}}|}),$ (2)

where $R({\hat{{\bf{k}}}})=R_{z}(\phi)R_{y}(\theta)$ rotates the $z$ axis into
the direction ${\hat{{\bf{k}}}}$ by performing rotations around the $y$ and
$x$ axes by the angles $\theta$ and $\phi$, respectively. These rotations
follow the boost $B_{z}(\xi_{|{\bf{k}}|})$ along the $z$ axis that brings the
magnitude of the momentum to $|{\bf{k}}|$ (the rapidity
$\xi_{|{\bf{k}}|}\geqslant 0$ is determined by
$\sinh\xi+\cosh\xi=|{\bf{k}}|$).

The states of an arbitrary momentum are defined via

$|{\mathsf{k}},\pm\rangle\vcentcolon=U\big{(}L({\mathsf{k}})\big{)}|{\mathsf{k}}_{S},\pm\rangle,$
(3)

while the standard right and left-circular polarization vectors are defined
via

${\hat{\mathbf{b}}}_{\hat{{\bf{k}}}}^{\pm}\vcentcolon=R({\hat{{\bf{k}}}})(\hat{\mathbf{x}}\pm
i\hat{\mathbf{y}})/\sqrt{2},$ (4)

while the linear polarization vectors are
${\hat{\mathbf{b}}}_{1}\vcentcolon=R({\hat{{\bf{k}}}})\hat{\mathbf{x}}$ and
${\hat{\mathbf{b}}}_{2}\vcentcolon=R({\hat{{\bf{k}}}})\hat{\mathbf{y}}$,
respectively. Alternatively, these vectors can be obtained as

${\hat{\mathbf{b}}}_{2}=\frac{\hat{\mathbf{z}}\times\hat{\mathbf{k}}}{|\hat{\mathbf{z}}\times{\hat{{\bf{k}}}}|},\qquad{\hat{\mathbf{b}}}_{1}={\hat{\mathbf{b}}}_{2}\times{\hat{{\bf{k}}}}.$
(5)

The explicit form of the polarization four-vector $\mathsf{f}_{\mathsf{k}}$,
$\mathsf{f}_{\mathsf{k}}\cdot{\mathsf{k}}=0$ depends on the gauge [5, 20, 27].

The Wigner stability subgroup consists of all proper Lorentz transformations
that leave the standard four-momentum ${\mathsf{k}}_{S}$ invariant:

$W(\Lambda,{\mathsf{k}})=L^{-1}(\Lambda{\mathsf{k}})\Lambda L({\mathsf{k}}).$
(6)

For massless particles it is decomposed as

$W=SR_{z}(\varpi),$ (7)

where $S$ is a translation in the $xy$ plane and $R_{z}(\varpi)$ is the
rotation around the $z$ axis. As the translations $S$ do not correspond to
physical degrees of freedom, the state transforms according to

$U(\Lambda)|{\mathsf{k}},\pm\rangle=e^{\pm
i\varpi}|\Lambda{\mathsf{k}},\pm\rangle.$ (8)

There are no generic explicit expressions for $\varpi$. Their evaluation is
not considerably simpler if $\Lambda={\mathscr{R}}$, where ${\mathscr{R}}$ is
a rotation (as there is no risk of confusion we use the same designation for
the four-dimensional matrices of spatial dimensions and for their $3\times 3$
blocks). However, as the transformation law of ${\hat{\mathbf{f}}}$ can be
obtained from the three-dimensional form of the Lorentz transformations of the
transversal electromagnetic wave, in this case [5, 28]

$U({\mathscr{R}})|\Psi_{\mathsf{k}}\rangle\Leftrightarrow{\mathscr{R}}{\hat{\mathbf{f}}}_{\bf{k}}.$
(9)

Moreover, an arbitrary rotation around the direction ${\hat{\mathbf{b}}}_{2}$,
$R_{{\hat{\mathbf{b}}}_{2}}(\alpha)$, does not introduce a phase $\varpi$
[17]. This provides the motivation for introduction of the so-called Newton
gauge that we review below.

##  III Faraday rotation

The equations of geometric optics are obtained by performing the short-wave
asymptotic expansion of the wave equation in the Lorentz gauge. The four-
vector potential is represented as $A^{\mu}(x)=a^{\mu}e^{i\psi}$. The wave
vector, $k_{\mu}:=\partial_{\mu}\psi$, is by definition normal to
hypersurfaces of constant phase $\psi$; in addition it is null,
$k^{\mu}k_{\mu}=0$. Hence hypersurfaces of constant $\psi$ are null and their
normals are also tangent vectors to the null geodesics $x^{\mu}(\sigma)$ that
lie in them [29]:

$\frac{dx^{\mu}}{d\sigma}=k^{\mu},\qquad k^{\mu}\nabla_{\mu}k^{\nu}=0.$ (10)

Here $\nabla_{\mu}$ is a covariant derivative compatible with the background
metric g and $\sigma$ is the affine parameter along a geodesic.

The eikonal equation, which is a restatement of the null condition, is given
by

$\textsl{g}^{\mu\nu}\frac{\partial\psi}{\partial
x^{\mu}}\frac{\partial\psi}{\partial x^{\nu}}=0,$ (11)

which is the Hamilton-Jacobi equation for a free massless particle on a given
background space-time.

The polarization four-vector is defined as
$f^{\mu}:=a^{\mu}/\sqrt{a^{\mu}a_{\mu}^{*}}$. It is transversal to the null
geodesic generated by $k^{\mu}$ and is parallel propagated along it:

$f^{\mu}k_{\mu}=0,\qquad k^{\mu}\nabla_{\mu}f^{\nu}=0.$ (12)

Thus we treat photons as massless point particles that move on the rays
prescribed by the geometric optics.

Stationary space-times allow a convenient three-dimensional representation of
the evolution of the polarization vector [16, 17]. Static observers follow the
congruence of timelike Killing vectors that define a projection from the
space-time manifold $\cal{M}$ onto a three-dimensional space $\Sigma_{3}$,
$\pi:\mathcal{M}\rightarrow\Sigma_{3}$. In practice, this projection is
performed by dropping the timelike coordinate of an event, and vectors are
projected via a push-forward map: $\pi_{*}{\mathsf{k}}={\bf{k}}$.

The metric $\textsl{g}_{\mu\nu}$ on $\mathcal{M}$ can be written in terms of a
three-dimensional scalar $h$, a vector $\mathbf{g}$ with components
$\textsl{g}_{m}$, and a three-dimensional metric $\gamma_{mn}$ on $\Sigma_{3}$
as

$ds^{2}=-h\left(dx^{0}-\textsl{g}_{m}dx^{m}\right)^{2}+dl^{2},$ (13)

where $h:=-\textsl{g}_{00}$,
$\textsl{g}_{m}:=-\textsl{g}_{0m}/\textsl{g}_{00}$, and the three-dimensional
distance is $dl^{2}:=\gamma_{mn}dx^{m}dx^{n}$, with the three-dimensional
metric

$\gamma_{mn}=\textsl{g}_{mn}-\frac{\textsl{g}_{0m}\textsl{g}_{0n}}{\textsl{g}_{00}},$
(14)

whose inverse is $\textsl{g}^{mn}$. The three-dimensional
$\gamma_{mn}$-compatible covariant derivative is denoted as $D_{m}$.

Using the relationships between the three- and four-dimensional covariant
derivatives, the propagation equations (10) and (12) in a stationary spacetime
result in the following three-dimensional expressions [16, 17]:

$\displaystyle\frac{D{\hat{{\bf{k}}}}}{d\sigma}$
$\displaystyle=\mbox{\boldmath$\Omega$}\times{\hat{{\bf{k}}}},$ (15)
$\displaystyle\frac{D{\hat{\mathbf{f}}}}{d\sigma}$
$\displaystyle=\mbox{\boldmath$\Omega$}\times{\hat{\mathbf{f}}},$ (16)

where $\sigma$ is an affine parameter along the curve with tangent vector
$\mathbf{k}=d\mathbf{x}/d\sigma$. From Eqs. (15) and (16) we see that both the
propagation direction and polarization are rigidly rotated, with an angular
velocity given by [17]

$\mbox{\boldmath$\Omega$}=2\mbox{\boldmath$\omega$}-(\mbox{\boldmath$\omega$}\\!\cdot\\!{\hat{{\bf{k}}}}){\hat{{\bf{k}}}}-\mathbf{E}_{g}\times{\bf{k}},$
(17)

with the vector $\left(h,\mathbf{g}\right)^{T}$ playing the role of a vector
potential for gravitoelectric and gravitomagnetic field [29, 30]:

$\mathbf{E}_{g}=-\frac{\nabla
h}{2h},\qquad\mbox{\boldmath$\omega$}=-\tfrac{1}{2}k_{0}\nabla\times\mathbf{g}.$
(18)

In flat spacetime this basis is uniquely fixed by Wigner’s little group
construction. However, on a general curved background the Wigner construction
must be performed at every point, i.e., absence of a global reference
direction ensures that the standard polarization triad
$({\hat{\mathbf{b}}}_{1},{\hat{\mathbf{b}}}_{2},{\hat{{\bf{k}}}})$ is
different at every location. Given such choice the net polarization rotation
can be found by starting with the initial polarization
$\mathsf{f}_{\mathrm{in}}(x_{\mathrm{in}})=\mathsf{b}_{1}(x_{\mathrm{in}})$,
parallel propagating it according to Eq. (12), and reading off the angle from
the decomposition of $f_{\mathrm{fin}}(x_{\mathrm{fin}})$,

$\mathsf{f}=\cos\chi\mathsf{b}_{1}+\sin\chi\mathsf{b}_{2}.$ (19)

Evaluation of the polarization rotation is much simpler in stationary
spacetimes. By setting ${\hat{\mathbf{f}}}={\hat{\mathbf{b}}}_{1}$ at the
starting point of the trajectory, we have
$\sin\chi={\hat{\mathbf{f}}}\cdot{\hat{\mathbf{b}}}_{2}$, so

$\displaystyle\frac{d\chi}{d\sigma}$
$\displaystyle=\frac{1}{{\hat{\mathbf{f}}}\\!\cdot\\!{\hat{\mathbf{b}}}_{1}}\frac{D({\hat{\mathbf{f}}}\\!\cdot\\!{\hat{\mathbf{b}}}_{2})}{d\sigma}$
$\displaystyle=\mbox{\boldmath$\omega$}\\!\cdot\\!{\hat{\mathbf{f}}}+\frac{1}{{\hat{\mathbf{f}}}\\!\cdot\\!{\hat{\mathbf{b}}}_{1}}{\hat{\mathbf{f}}}\\!\cdot\\!\frac{D{\hat{\mathbf{b}}}_{2}}{d\sigma}.$
(20)

In the Schwarzschild spacetime $\mbox{\boldmath$\omega$}\equiv 0$ and
polarization rotation is a pure gauge effect. The phase remains zero if the
standard directions are set with the help of the local free fall acceleration
$\mathbf{w}$ of a stationary observer. At each point in the spacetime we
choose the direction of the standard reference momentum, or equivalently the
$z$-axis of our standard polarization triad, to be
$\mbox{\boldmath$\hat{\zeta}$}\vcentcolon=\mathbf{w}$. For a photon with
momentum $\mathbf{k}$ we choose the linear polarization vector
$\hat{\mathbf{b}}_{2}$ to point in the direction
$\mbox{\boldmath$\hat{\zeta}$}\times\hat{\mathbf{k}}$, and finally we choose
$\hat{\mathbf{b}}_{1}\vcentcolon={\hat{\mathbf{b}}}_{2}\times{\hat{{\bf{k}}}}$
such that it completes the orthonormal triad
$(\hat{\mathbf{b}}_{1},\hat{\mathbf{b}}_{2},\hat{\mathbf{k}})$. This
construction is known as the Newton gauge [17]. With this convention
$\mbox{\boldmath$\Omega$}=-\mathbf{E}_{g}\times{\bf{k}}\equiv\Omega{\hat{\mathbf{b}}}_{2}$
and thus $\chi\equiv 0$ along the trajectory.

However, such choice of standard polarization direction is practically
unfeasible. We will see the consequences of setting the $z$-axis with the help
of a guide star in the next section.

Figure 1:  Scheme of the communication round between the ground station (GS)
and the spacecraft (SC). The light ray is highlighted in blue. All the vectors
are indicated in the Earth-centered inertial frame. In the flat space-time
approximation the unit tangent vectors to the ray
${\hat{{\bf{k}}}}_{\mathrm{gs}}$ and ${\hat{{\bf{k}}}}_{\mathrm{sc}}$ at the
GS and the SC, as well as the direction to an infinitely distant guide star,
$\mbox{\boldmath$\hat{\zeta}$}_{\mathrm{gs}}$ and
$\mbox{\boldmath$\hat{\zeta}$}_{\mathrm{sc}}$, respectively, coincide.
Velocity of the GS at the emission of the signal is $\mathbf{v}$ and velocity
of the SC at the moment of detection is $\mathbf{u}$.

##  IV Relativistic phases in the near-Earth quantum communications

###  IV.1 Setting

As a typical scenario we consider one round of communications between the
ground station (GS) and a LEO spacecraft (SC). The problem is most
conveniently analyzed in the geocentric (Earth-centered inertial) system, the
origin of which coincides with the center of the Earth at the moment of
emission. We direct the $z$ axis of this system along the Earth’s angular
momentum. Then the three-dimensional velocity $\mathbf{v}$ of the GS in this
frame lies in the $xy$ plane, while the initial propagation direction vector
${\hat{{\bf{k}}}}$ and the velocity of the SC at the time of detection
$\mathbf{u}$, both expressed in the global frame, are arbitrary. Fig. 1
represents this scenario.

The parametrized post-Newtonian approximation [21] is a systematic method for
obtaining corrections to the Newtonian motions of a system of slowly moving
bodies bound together by weak gravitational forces. For a metric theory in
question the corrections are organized by the powers of in $GM/rc^{2}$ and
$v/c$. Typical velocities and gravitational potentials are related by
$GM/r\sim v^{2}$. By estimating
$\epsilon^{2}\vcentcolon=GM/R_{\oplus}c^{2}\approx 10^{-5}$, where
$R_{\oplus}$ is the Earth’s radius we find that typical velocities are of the
order $\epsilon$, and the upper bound on the gravitational potential is of the
order $\epsilon^{2}$. The order of expansion is conveniently labeled by the
parameter $\epsilon$, the formal powers of which accompany the corresponding
expressions and that is taken to unity at the end of the calculation.

Figure 2:  Wigner phase in one round of the GS to SC communication as a
function of the passage time. The GS is located on the equator
($r_{\mathrm{gs}}=R_{\oplus}=6.38\times 10^{6}$m) and the SC has a circular
orbit ($r_{\mathrm{sc}}=7.00\times 10^{6}$m). The time origin corresponds to
the SC in the zenith. (left) The SC moves on a constant celestial meridian and
crosses the equator at $t=0$. The inset shows the Wigner phase when the SC is
close to the zenith. (right) The SC rotates in the equatorial plane in the
same sense as the Earth. For the coplanar motion the first-order effect
vanishes, and the Wigner phase is of the same order of magnitude as the
Faraday phase of Sec. IV.3.

Hence the leading corrections that take into account the effects of both SR
and GR include the terms of up to the order of $\epsilon^{2}$. In this
approximation the gravitational field of the Earth is spherically symmetric,
and thus it follows from Eq. (20) that the perceived polarization rotation
results only due to the reference frame choices by the communicating parties.
Moreover, at this level of precision the effects of SR and GR can be treated
separately, as the leading mixed term is of the order $\epsilon^{3}$.

###  IV.2 SR effects

It is easy to see that the SR effects dominate, resulting in
$\varpi\sim\epsilon$. It also should be noted that the freedom in choosing the
relative orientation of the reference frames allows one to eliminate the
Wigner phase for a fixed relative velocity $\mathbf{v}_{12}$ between the two
frames 1 and 2, and any four-momentum vector ${\mathsf{k}}_{1}$ (expressed,
say, in frame 1). This is similar to the two-frame invariant definition of
spin of massive particles [31]. Indeed, any proper Lorentz transformation that
relates these two frames has a form [26]

$\Lambda=R(\hat{\mathbf{v}}_{12})B_{z}(\xi_{v_{12}})R(\alpha,\beta,\gamma)^{-1},$
(21)

where $v_{12}=\tanh\xi_{v_{12}}$ and $R(\alpha,\beta,\gamma)$ is an arbitrary
(four-dimensional matrix of) rotation with the Euler angles $\alpha$, $\beta$,
$\gamma$. By choosing $R(\alpha,\beta,\gamma)=R({\hat{{\bf{k}}}})$ we have in
Eq. (6) $\Lambda L({\mathsf{k}})=L(\Lambda{\mathsf{k}})$, ensuring absence of
the Wigner phase.

We use the setting of Fig. 1 and the conventions of Sec. II (so the standard
propagation direction is along the $z$ axis of the Earth-centered inertial
frame). As we want to focus on the effects of relative motion we assume that
the global frame and the GS and SC frames are related by pure boosts,
$B(\mathbf{v})$ and $B(\mathbf{u})$, respectively. Then the momenta in GS and
SC frames are related by

$k_{\mathrm{{sc}}}=B(-\mathbf{u})B(-\mathbf{v})k_{\mathrm{gs}},$ (22)

and thus the Wigner rotation is obtained by extracting the angle $\varpi$ from
the decomposition of the Lorentz transformation
$\Lambda=B(-\mathbf{u})B(-\mathbf{v})$ via Eq. (7). We take the velocities of
the GS and SC in the global frame as

$\displaystyle\mathbf{v}=(v\cos\alpha,v\sin\alpha,0),$ (23)
$\displaystyle\mathbf{u}=u(\sin\vartheta\cos\varphi,\sin\vartheta\sin\varphi,\cos\vartheta),$
(24)

respectively, and the propagation direction

${\hat{{\bf{k}}}}=(\sin\theta\cos\phi,\sin\theta\sin\phi,\cos\theta).$ (25)

The first-order contribution to the Wigner phase is

$\varpi=u\cot\theta\sin\vartheta\sin(\phi-\varphi)+v\cot\theta\sin(\phi-\alpha)+{\cal{O}}(\epsilon^{2}).$
(26)

For the SC moving at the latitude of the GS coplanar the first-order effect is
absent.

Fig. 2 illustrates the Wigner phase accrued between the GS and the SC as a
function of the SC passage time. As our goal is to illustrate the relativistic
effects in their simplest settings we locate the ground station on the equator
and assume an exactly circular trajectory for the spacecraft. Except for the
coplanar motion where the first-order Doppler effect cancels, the induced
phase is of the order of $v/c$, where $v$ is the relative velocity between the
GS and SC.

###  IV.3 GR effects

Electromagnetic radiation and massless particles are not affected by Newtonian
gravity. The leading post-Newtonian contributions (corrections to
trajectories, time differences, and phases) are of order $\epsilon^{2}$ in the
parametrized post-Newtonian (PPN) expansion [21, 22, 29, 30]; to take into
account gravitomagnetic effects we need contribution up to $\epsilon^{3}$.

The post-Newtonian expansion of the metric near a single slowly rotating
quasirigid gravitating body, assuming that the underlying theory of gravity is
GR [21, 22, 29], up to terms of order $\epsilon^{3}$ is given by

$ds^{2}=-V^{2}(r)c^{2}dt^{2}+\vec{R}\\!\cdot\\!d{\vec{x}}\,cdt+W^{2}(r)d{\vec{x}}\\!\cdot\\!d{\vec{x}},$
(27)

where

$V(r)=1-\epsilon^{2}\frac{U}{c^{2}},\qquad
W(r)=1+\epsilon^{2}\gamma\frac{U}{c^{2}}.$ (28)

The Newtonian gravitational potential $-U=-GMQ(r,\theta)/r\simeq-GM/r$ depends
on the mass $M$ and higher multipoles [22, 30], and

$\vec{R}=-\epsilon^{3}4\frac{G}{c^{3}}\frac{{\vec{J}}\times{\vec{x}}}{r^{3}},$
(29)

where $\vec{J}$ is the angular momentum of the rotating body. Hence we see
that the gauge-invariant polarization rotation is absent in the leading order
of the post-Newtonian expansion and the Faraday phase at the order
$\epsilon^{2}$ is a reference-frame effect. As we are interested only in the
leading contribution to the phase we set $Q=1$, and as it limits the precision
at the level of $10^{-3}$ [30], $\gamma=1$. In the remainder of the section we
revert to the units $G=c=1$.

To obtain the leading contributions to the phase and polarization rotation,
the photon trajectories only need to be expanded up to $\epsilon^{2}$,

${\vec{x}}(t)=:{\vec{x}}_{(0)}(t)+\epsilon^{2}{\vec{x}}_{(2)}(t),$ (30)

where the zeroth-order Newtonian trajectory is determined by the initial
position ${\vec{x}}(t_{0})\equiv{\vec{x}}_{0}$ and the initial direction
${\vec{n}}$, ${\vec{n}}\cdot{\vec{n}}=1$. The leading-order corrections are
decomposed into the tangential and transversal components,

${\vec{x}}_{(2)}(t)={\vec{n}}x_{\parallel}(t)+{\vec{x}}_{\perp}(t),$ (31)

with ${\vec{x}}_{\perp}(t)\cdot{\vec{n}}=0$ and the initial conditions
${\vec{x}}_{(2)}(t_{0})=0$. The initial tangent vector satisfies [22]

${\vec{k}}(t_{0})\vcentcolon=\left.\frac{d\vec{x}}{dt}\right|_{t_{0}}=(1-2\epsilon^{2}U(\vec{x}_{0})){\vec{n}},\qquad\\!{\vec{n}}\\!\cdot{\vec{n}}=1.$
(32)

Since $\gamma_{mn}k^{m}k^{n}=W^{2}V^{4}$, then with a slight abuse of notation
in leading post-Newtonian order we have

${\hat{{\bf{k}}}}_{0}=W_{0}{\vec{k}}_{0}.$ (33)

The post-Newtonian corrections are obtained either from the evolution of the
unit Euclidean vector ${\vec{v}}$ or from the equations

$\displaystyle\frac{d^{2}{\vec{x}}_{\perp}}{dt^{2}}=2\big{(}\vec{\nabla}U-{\vec{n}}({\vec{n}}\\!\cdot\\!\vec{\nabla}U)\big{)},$
(34) $\displaystyle\frac{dx_{\parallel}}{dt}=-2{U}.$ (35)

Figure 3:  The Faraday phase depends on the choice of the reference direction
$\vec{\zeta}(\alpha,\beta)$ and the initial propagation direction
${\vec{n}}(\phi)$. The angles are defined in Eqs. (48) and (49). (left)
$\beta=0$. (center) $\beta=7\pi/16$. (right) $\beta=\pi$.

With the origin at the center of the Earth the integration results in the
tangent vector

${\vec{k}}={\vec{n}}-\epsilon^{2}\frac{2M{\vec{n}}}{r(t)}-\epsilon^{2}\frac{2M{\vec{d}}}{d^{2}}\left(\frac{{\vec{x}}(t)\cdot{\vec{n}}}{r(t)}-\frac{{\vec{x}}_{0}\cdot{\vec{n}}}{r_{0}}\right),$
(36)

where it is enough to take the Newtonian equation of the trajectory to obtain
the leading post-Newtonian correction,

${\vec{x}}(t)\cdot{\vec{n}}={\vec{x}}_{0}\cdot{\vec{n}}+t-t_{0}+{\cal{O}}(\epsilon^{2}),$
(37)

and

${\vec{d}}\vcentcolon={\vec{x}}_{0}-({\vec{x}}_{0}\cdot{\vec{n}}){\vec{n}},$
(38)

is the vector joining the center of the Earth and the point of the closest
approach of the unperturbed ray.

The leading-order post-Newtonian metric is spherically symmetric. The rest of
the calculations are considerably simplified if we note that the initial
polarization that is perpendicular to the propagation plane remains
perpendicular to it, which is an immediate consequence of Eqs. (16)–(18).
Therefore we select the reference frame differently from that of Fig. 1. As
the effects of SR contribute at least one additional factor of $\epsilon$,
here we focus only on the gravitational effects and treat them separately from
the effects of rotation and relative motion. Hence take as $z=0$ the plane
where the ray from the GS to the SC lies, set their velocities to zero, and
consider the (constant Euclidean) polarization vector

${\vec{f}}=(0,0,1)=\mathrm{const}.$ (39)

The gauge-dependent Faraday phase results from the changes in the definitions
of the standard polarization directions along the trajectory. In turn, these
follow from the changes in the standard polarizations. At each point they are
defined via Eqs. (5) where the unit vector $\hat{\zeta}$ pointing to a distant
reference star takes the role of $\hat{\mathbf{z}}$ and the local unit tangent
${\hat{{\bf{k}}}}$.

The local propagation direction at the GS and the SC is conveniently
represented:

$\displaystyle{\vec{k}}_{i}$
$\displaystyle={\vec{n}}\left(1-\epsilon^{2}\frac{2M}{r_{i}}\right)-\epsilon^{2}\frac{2M{\vec{d}}}{d^{2}}\left(\frac{{\vec{x}}_{i}\cdot{\vec{n}}}{r_{i}}-\frac{{\vec{x}}_{\mathrm{gs}}\cdot{\vec{n}}}{r_{\mathrm{gs}}}\right)$
$\displaystyle=\vcentcolon{\vec{n}}+\epsilon^{2}{\vec{\kappa}}_{i},\qquad
i=\mathrm{gs,sc}.$ (40)

The reference directions $\mbox{\boldmath$\hat{\zeta}$}_{i}$,
$i=\mathrm{gs,sc}$ are obtained from the tangents to the rays from the fixed
guide star that arrive to the GS and SC, respectively, and
$r_{\mathrm{gs}}=R_{\oplus}$. We assume that the star is infinitely far, so in
the Newtonian limit $\mbox{\boldmath$\hat{\zeta}$}_{i}^{m}\to l^{m}$, where
$-{\vec{l}}$ is the flat space direction from the infinitely distant star to
the observers, ${\vec{l}}\cdot{\vec{l}}=1$. Approximating differences in the
local directions as arising solely from the gravitational field of the Earth,
we have

$\vec{\zeta}_{i}={\vec{l}}\left(1-\epsilon^{2}\frac{2M}{r_{i}}\right)-\epsilon^{2}\frac{2M{\vec{d}}_{i}}{d^{2}_{i}}\left(\frac{{\vec{x}}_{i}\\!\cdot\\!{\vec{l}}}{r_{i}}-1\right)=\vcentcolon{\vec{l}}+\epsilon^{2}\vec{\varsigma}_{i}.$
(41)

Then the standard polarization vectors at the GS and the SC are

${\hat{\mathbf{b}}}_{2i}=\frac{\vec{\zeta}_{i}\times{\vec{k}}}{\big{|}\vec{\zeta}_{i}\times{\vec{k}}\big{|}}=\vcentcolon{\vec{e}}_{2}+\epsilon^{2}\vec{\beta}_{2i},\qquad{\hat{\mathbf{b}}}_{1i}={\hat{\mathbf{b}}}_{2i}\times{\hat{{\bf{k}}}}=\vcentcolon{\vec{e}}_{1}+\epsilon^{2}\vec{\beta}_{1i}.$
(42)

In the Newtonian limit,

${\hat{\mathbf{b}}}_{2i}\rightarrow\vec{e}_{2}\vcentcolon=\frac{{\vec{l}}\times{\vec{n}}}{\big{|}{\vec{l}}\times{\vec{n}}\big{|}},$
(43)

and to ensure $|{\hat{\mathbf{b}}}_{2}|=1$ the post-Newtonian terms satisfy
${\vec{e}}_{2}\cdot\vec{\beta}_{2i}+M/r_{i}=0$, with analogous expressions for
${\hat{\mathbf{b}}}_{1i}$. Explicitly,

$\displaystyle{\vec{e}}_{2}=\frac{{\vec{l}}\times{\vec{n}}}{\sqrt{1-({\vec{l}}\\!\cdot\\!{\vec{n}})^{2}}},$
(44)
$\displaystyle\vec{\beta}_{2i}=\frac{{\vec{l}}\times{\vec{n}}\,({\vec{l}}\\!\cdot\\!{\vec{n}})({\vec{n}}\\!\cdot\\!\vec{\varsigma_{i}}+{\vec{l}}\\!\cdot\\!{\vec{\kappa}}_{i})+{\vec{l}}\times{\vec{\kappa}}_{i}-{\vec{n}}\times\vec{\varsigma_{i}}}{\sqrt{1-({\vec{l}}\\!\cdot\\!{\vec{n}})^{2}}}.$
(45)

As a result, the leading order Faraday phase that is accrued between the GS
and the SC is obtained from

$\displaystyle\sin(\chi+\Delta\chi)-\sin\chi={\hat{\mathbf{f}}}_{\mathrm{sc}}\\!\cdot\\!{\hat{\mathbf{b}}}_{2{\mathrm{sc}}}-{\hat{\mathbf{f}}}_{\mathrm{gs}}\\!\cdot\\!{\hat{\mathbf{b}}}_{2{\mathrm{gs}}}$
$\displaystyle=\Delta\chi\cos\chi=\Delta\chi{\vec{f}}\\!\cdot{\vec{e}}_{1}+{\cal{O}}(\epsilon^{3}).$
(46)

Substituting the explicit expressions into the above equation results in

$\Delta\chi=\frac{e_{2}^{z}M}{e_{1}^{z}}\left(\frac{1}{r_{\mathrm{gs}}}-\frac{1}{r_{\mathrm{sc}}}\right)+\frac{\beta_{2{\mathrm{sc}}}^{z}-\beta_{2{\mathrm{gs}}}^{z}}{e_{1}^{z}}.$
(47)

where we assume that $e_{1}^{z}\gg\epsilon^{2}$, which is the validity
condition for this expression for the Faraday rotation.

If we choose the $x$ axis to pass through the GS, then

${\vec{n}}=(\cos\phi,\sin\phi,0),\qquad-\tfrac{1}{2}\pi<\phi<\tfrac{1}{2}\pi,$
(48)

and

${\vec{l}}=(\cos\alpha,\sin\alpha\sin\beta,\sin\alpha\cos\beta),$ (49)

where the altitude of the guide star is $\tfrac{1}{2}\pi-\alpha$,
$0\leqslant\alpha\leqslant\tfrac{1}{2}\pi$. Some useful auxiliary expressions
are given in the Appendix.

When the reference direction $\hat{\zeta}$ and the propagation direction
${\hat{{\bf{k}}}}$ are collinear, the standard polarization directions are
undefined. If $\hat{\zeta}$ lies in the plane determined by GS, SC, and centre
of the Earth, then the Faraday phase is zero. Moreover, the post-Newtonian
expansion of Eq. (47) fails in the $\epsilon^{2}$ vicinity of $\alpha=0$ or
$\beta=\tfrac{1}{2}\pi,\tfrac{3}{2}\pi$.

While for a general configuration an expression for the Faraday phase is
rather cumbersome, some special cases are quite simple. For
$|\tan\beta|\ll\epsilon^{-2}$ and the SC at the zenith ($\phi=0$) the Faraday
phase is

$\varpi_{\mathrm{F}}=\frac{GM}{c^{2}}\frac{r_{\mathrm{sc}}-r_{\mathrm{gs}}}{r_{\mathrm{sc}}r_{\mathrm{gs}}}\tan\beta,$
(50)

while for the guide star close to the zenith the resulting phase is

$\varpi_{\mathrm{F}}=-\frac{GM}{c^{2}}\frac{r_{\mathrm{sc}}-r_{\mathrm{gs}}}{r_{\mathrm{sc}}r_{\mathrm{gs}}}\frac{1}{\cos\beta}\left(\frac{\sin\phi}{\alpha}-\cos\phi\sin\beta+{\cal{O}}(\alpha)\right).$
(51)

for $\epsilon^{2}\ll\alpha\ll 1$.

Fig. 3 shows the leading-order (gauge-dependent) Faraday phase for different
reference and propagation directions. As discussed above, to isolate the
gravitational contribution to the phase it is enough to consider a fictitious
scenario of the GS and SC being in fixed positions in the global reference
frame. Unless the first-order Doppler effect cancels, the Faraday phase is
$\epsilon$ times smaller than the Wigner phase.

##  V Errors and their mitigation

Regardless of the basis that is used to encode polarization qubits the
relativistic phases lead to errors in distinguishing the signals. For small
phases the fidelity loss, $1-F$,
$F\vcentcolon=|\langle\Psi_{\mathrm{sc}}|\Psi_{\mathrm{gs}}\rangle|$, scales
as $\varpi^{2}$. The SR and GR effects appear jointly and can be countered
using the same techniques. As the phases are opposite for the opposite
helicities, for the states with sharply defined momenta the phase errors can
be easily countered [24].

Consider two entangled well-separated and therefore distinguishable wave
packets, with the same momentum profile centered on ${\mathsf{k}}$. For
example, the two-photon states

$|\Psi^{\pm}_{\mathsf{k}}\rangle=\frac{1}{\sqrt{2}}\big{(}|{\mathsf{k}},+\rangle_{1}|{\mathsf{k}},-\rangle_{2}\pm|{\mathsf{k}},-\rangle_{1}|{\mathsf{k}},+\rangle_{2}\big{)},$
(52)

have a zero helicity and are thus insensitive to the Wigner and Faraday phase
rotations.

The two states $|\Psi^{\pm}_{\mathsf{k}}\rangle$ are orthogonal to each other
and thus perfectly distinguishable. Hence using them one logical qubit can be
encoded with two physical qubits (photons). If multiphoton states can be
resolved then the asymptotically efficient encoding scheme of using $N$
photons to transmit $N-2^{-1}\log_{2}N$ qubits can be employed.

The relative importance of the relativistic noise and, therefore, necessity of
using this invariant encoding, depend on the specific task and its performance
requirements. Consider for definiteness a QKD protocol with discrete variables
[32, 33], where qubits are realized as polarization states of photons with
well-defined momenta. Let the protocol be a version of Eckert’s protocol E91,
where the entangled state is prepared onboard of the SC and is sent to the
communicating parties on the ground.

The measured qubit error rates were reported to be 1-3% [1] for the SC–GS
link, raising to 4.5–8.1% for the entanglement-based QKD that enabled secure
communications between two GSs [2]. Weather is the main source of the bit rate
variability [1]. In situations like this, where the protocol operates close to
the maximal allowed error rate of approximately 11% [32], the relativistic
phase is negligible and should be ignored. Moreover, a nonrelativistic effect
— misalignment of the reference frames — is a much more serious problem that
potentially may prevent the establishment of a secure key.

As all such misalignments (both relativistic and nonrelativistic) introduce
the phase error $|{\mathsf{k}}\pm\rangle\to e^{\pm
i\phi}|{\mathsf{k}}^{\prime}\pm\rangle$, we consider their correction by the
RFI protocol of Ref. [34]. The protocol is based on the assumption of a shared
(logical) $z$-axis by the communicating parties. We denote the logical Pauli
operators $\sigma_{x}\equiv X$, $\sigma_{y}\equiv Y$ and $\sigma_{Z}\equiv Z$
of the two parties (Alice and Bob) as $X_{A,B}$, $Y_{A,B}$ and $Z_{A}=Z_{B}$,
and the logical qubits are realized as
$|0\rangle\vcentcolon=|{\mathsf{k}}+\rangle$ and
$|1\rangle\vcentcolon=|{\mathsf{k}}-\rangle$, respectively.

Taking the ideal entangled state that is to be shared between the parties as
$|\Psi^{-}\rangle$, in the absence of other sources of noise the actual state
is

$|\Psi^{-}\rangle_{AB}=\frac{1}{\sqrt{2}}\big{(}e^{\phi}|{\mathsf{k}}_{1}+\rangle_{A}|{\mathsf{k}}_{2}-\rangle_{B}-e^{-i\phi}|{\mathsf{k}}_{1}-\rangle_{A}|{\mathsf{k}}_{2}+\rangle_{B}\big{)},$
(53)

where the relative phase $2\phi$ depends on the momenta of the two photons and
the Lorentz transformation between the frames (we discuss weaker gravity
effects shortly).

Alice and Bob perform at each step one of the three randomly selected
measurements $X$,$Y$, $Z$. For simplicity we take them as equiprobable. At
each instance when both of them have selected a shared $Z$ Alice and Bob
generate a shared bit of the raw key. For the state of Eq (53) this shared bit
is generated error free (assuming the absence of eavesdropping and other
sources of noise), which results in the raw key bit generation rate per
communicated pair that is (bounded by) $P_{\mathrm{rfi}}=1/9$. Four of the
eight other possible measurement combinations that involve $X$ and $Y$ tests
are used to generate the correlator

$C=\langle X_{A}X_{B}\rangle^{2}+\langle X_{A}Y_{B}\rangle^{2}+\langle
Y_{A}X_{B}\rangle^{2}+\langle Y_{A}Y_{B}\rangle^{2}.$ (54)

For an arbitrary but constant $\phi$ it is independent of the phase and is
used to monitor the eavesdropper’s knowledge.

As a matter of principle, the scheme relies on the sufficiently good knowledge
of one direction and fails when this is corrupted. This direction is shared by
having some physical token. Without active feedback and correction the ideally
maintained local directions will lead to the errors of the order of the linear
Doppler effect, i.e. $\epsilon\sim 10^{-5}$ with the LEO satellites. However,
preservation of this token on its own is unrealistic even in purpose-built
systems such as the Gravity Probe B [35]. On board of the spacecraft torques
proportional to the angle between the gyro spin vector and the spacecraft roll
axis needed to be constantly monitored. A more practical bound is given by the
specifications of the CubeSat project, where the systems aligning the
transmitting telescope with the optical ground station during quantum
transmission are expected to operate at the level of percents [4].

As long as two-photon measurements are resource intensive, there is no
justification in using the two-to-one scheme of Eq. (52). On the other hand,
once such operations become inexpensive, and increase of the bit rate becomes
a priority, the scheme (52) will clearly have an advantage, as by being
incorporated in the standard E91 protocol it allows one raw bit per four
physical photons, even without using the many-particle encoding.

##  VI Summary

Describing propagation of electromagnetic waves in vacuum in terms of rays
that follow null geodesics is a very good approximation in the high-frequency
regime. Observable deviations from the geometric optics approximation are
expected only in ultrastrong gravitational fields. Within this approximation
the polarization rotation in the Schwarzschild metric, and as a result in the
leading post-Newtonian approximation, is a purely gauge effect.

This phase will be present as a consequence of practical methods of setting up
reference frames in the Earth-to-spacecraft communications. However, these
effects are typically about $10^{-5}$ weaker than the SR effects. If these
small errors need to be countered this can be done using the same encoding
scheme. Finally, we note that this scheme can serve as a basis of a true RFI
protocol that does not assume any shared reference frame information.

###### Acknowledgements.

DRT thanks Paul Alsing, Fan Jingyun, and Tim Ralph for useful discussions. PKD
thanks Daniel George for advice on graphical output in Mathematica. This work
was supported by the Grants No. FA2386-17-1-4015 and No. FA2386-20-1- 4016 of
the Asian Office of Aerospace Research and Development of the U.S. Air Force
Research Laboratory.

##  Appendix A Explicit expressions

The zeroth-order standard directions are

$\displaystyle{\vec{e}}_{1}=\bigg{(}\frac{\sin\phi\left(\tan\left(\frac{\alpha}{2}\right)\sin\beta\cos\phi+\cos\alpha\left(\tan\left(\frac{\alpha}{2}\right)\sin\beta\cos\phi-\sin\phi\right)\right)}{\sqrt{(\sin\alpha\sin\beta\cos\phi-\cos\alpha\sin\phi)^{2}+\sin^{2}\alpha\cos^{2}\beta}},$
$\displaystyle-\frac{\cos\phi\left(\tan\left(\frac{\alpha}{2}\right)\sin\beta\cos\phi+\cos\alpha\left(\tan\left(\frac{\alpha}{2}\right)\sin\beta\cos\phi-\sin\phi\right)\right)}{\sqrt{(\sin\alpha\sin\beta\cos\phi-\cos\alpha\sin\phi)^{2}+\sin^{2}\alpha\cos^{2}\beta}},-\frac{(\cos\alpha+1)\tan\left(\frac{\alpha}{2}\right)\cos\beta}{\sqrt{(\sin\alpha\sin\beta\cos\phi-\cos\alpha\sin\phi)^{2}+\sin^{2}\alpha\cos^{2}\beta}}\bigg{)},$
(55)

and

$\displaystyle{\vec{e}}_{2}=\bigg{(}-\frac{(\cos\alpha+1)\tan\left(\frac{\alpha}{2}\right)\cos\beta\sin\phi}{\sqrt{(\sin\alpha\sin\beta\cos\phi-\cos\alpha\sin\phi)^{2}+\sin^{2}\alpha\cos^{2}\beta}},\frac{(\cos\alpha+1)\tan\left(\frac{\alpha}{2}\right)\cos\beta\cos\phi}{\sqrt{(\sin\alpha\sin\beta\cos\phi-\cos\alpha\sin\phi)^{2}+\sin^{2}\alpha\cos^{2}\beta}},$
$\displaystyle\frac{\cos\alpha\sin\phi-(\cos\alpha+1)\tan\left(\frac{\alpha}{2}\right)\sin\beta\cos\phi}{\sqrt{(\sin\alpha\sin\beta\cos\phi-\cos\alpha\sin\phi)^{2}+\sin^{2}\alpha\cos^{2}\beta}}\bigg{)}.$
(56)

The first post-Newtonian term of ${\vec{k}}_{\mathrm{gs}}$ readily follows
from Eq. (32), while the leading correction to the propagation direction at
the SC is

$\kappa_{{\mathrm{sc}}}=\frac{2M}{r_{\mathrm{gs}}r_{\mathrm{sc}}}\Big{(}-L+\cos\phi(r_{\mathrm{sc}}-2r_{\mathrm{gs}}),\cot\phi\big{(}\cos\phi(r_{\mathrm{gs}}-r_{\mathrm{sc}})+L\big{)}-r_{\mathrm{gs}}\sin\phi,0\Big{)}.$
(57)

Finally, we quote the deviation of the line of sight to the guide star:

$\vec{\varsigma}_{{\mathrm{gs}}}=\frac{2M}{r_{\mathrm{gs}}}\big{(}2\cos\alpha-1,(2\cos\alpha+1)\tan\tfrac{1}{2}\alpha\sin\beta,(2\cos\alpha+1)\tan\tfrac{1}{2}\alpha\cos\beta\big{)},$
(58)

## References

  * [1] S.-K. Liao et al., Nature 549, 43 (2017).
  * [2] J. Yin et al., Nature, 582 501 (2020).
  * [3] P. Kómár, E. M. Kessler, M. Bishof, L. Jiang, A. S. Sørensen, J. Ye, and M. D. Lukin, Nature Phys. 10, 582 (2014); H. Dai et al., Nature. Phys. 16, 848 (2020).
  * [4] D. K. L. Oi, et al., EPJ Quantum Tech. 4, 6 (2017); L. Mazzarella, C. Lowe, D. Lowndes, S. K. Joshi, S. Greenland, D. McNeil, C. Mercury, M. Macdonald, J. Rarity, and D. K. L. Oi, Cryptography 4, 7 (2020).
  * [5] A. Peres and D. R. Terno, Rev. Mod. Phys. 76, 93 (2004).
  * [6] R. B. Mann and T. C. Ralph, Relativisitc Quantum Information, Class. Quant. Grav. 29 (22) (2012).
  * [7] D. Rideout et al., Class. Quant. Grav. 29, 224011 (2012).
  * [8] F. Flamini, N. Spagnolo, and F. Sciarrino, Rep. Prog. Phys. 82, 016001 (2019).
  * [9] D. E. Bruschi, T. C. Ralph, I. Fuentes, T. Jennewein, and M. Razavi, Phys. Rev. D 90, 045041 (2014).
  * [10] A. Brodutch, A. Gilchrist, T. Guff, A. R. H. Smith, and D. R. Terno, Phys. Rev. D 91, 064041 (2015).
  * [11] D. R. Terno, G. Vallone, F. Vedovato, and P. Villoresi, Phys. Rev D 101, 104052 (2020); D. R. Terno, F. Vedovato, M. Schiavon, A. R. H. Smith, P. Magnani, G. Vallone, and P. Villoresi, arXiv:1811.04835 (2018).
  * [12] G.V. Skrotskii, Sov. Phys. Dokl. 2, 226 (1957); J. Plebanski, Phys. Rev. 118, 1396 (1960); B. B. Godfrey, Phys. Rev. D 1, 2721 (1970).
  * [13] M. Nouri-Zonoz, Phys. Rev. D 60, 024013 (1999); M. Sereno, Phys. Rev. D 69, 087501 (2004); S. M. Kopeikin and B. Mashhoon, Phys. Rev. D 65, 064025 (2002).
  * [14] R. F. Stark and P. A. Connors, Nature 266, 429 (1977) ; P.A. Connors, T. Piran, and R. F. Stark, Astrophys. J. 235, 224 (1980).
  * [15] P. P. Kronberg, C. C. Dyer, E.M. Burbidge, and V. T. Junkkarinen, Astrophys. J. 367, L1 (1991); C. R. Burns, C. C. Dyer, P. P. Kronberg, and H.-J. Roöser, Astrophys. J. 613, 672 (2004).
  * [16] F. Fayos and J. Llosa, Gen. Rel. Grav. 14, 865 (1982).
  * [17] A. Brodutch, T. F. Demarie, and D. R. Terno, Phys. Rev. D 84, 104043 (2011); A. Brodutch and D. R. Terno, Phy. Rev. D 84, 121501(R) (2011).
  * [18] M. A. Oancea, C. F. Paganini, J. Joudioux, C. F. Paganini, and L. Andersson, Phys. Rev. D 102, 024075 (2020); V. Frolov, Phys. Rev. D 102, 084013 (2020).
  * [19] A. A. Deriglazov,arXiv:2103.07794 (2021).
  * [20] P. M. Alsing and G. J. Stephenson, Jr, arXiv:0902.1399; M. Rivera-Tapia, A. Delgao, G. Rubilar, Class. Quant. Grav. 37, 195001 (2020).
  * [21] E. Poisson and C. W. Will, Gravity: Newtonian, Post-Newtonian, Relativistic (Cambridge University Press, 2014).
  * [22] C. M. Will, Theory and Experiment in Gravitational Physics, 2nd edition (Cambridge University Press, 2018).
  * [23] J. Kohlrus, J. Louko, I. Fuentes, and D. E. Bruschi, arXiv:1810.10502 (2018).
  * [24] S. D. Bartlett and D. R. Terno, Phys. Rev. A 71, 012302 (2005).
  * [25] E. Wigner, Ann. Math. 40, 149 (1939); S. Weinberg, The Quantum Theory of Fields (Cambridge University Press, Cambridge, England, 1996), vol. I.
  * [26] W.-K. Tung, Group Theory in Physics (World Scientific, Singapore, 1985).
  * [27] D. Han, Y. S. Kim, and D. Son, Phys. Rev. D 31, 328 (1985).
  * [28] N. H. Lindner, A. Peres, and D. R. Terno, J. Phys. A 36, L449 (2003).
  * [29] C.W. Misner, K. S. Thorn, and J. A. Wheeler, Gravitation (Freeman, San Francisco, 1973).
  * [30] I. Ciufolini and J. A. Wheeler, Gravitation and Inertia (Princeton University, Princeton, New Jersey, 1995).
  * [31] M. Czachor and M. Wilczewski, Phys. Rev. A 68, 010302(R) (2003).
  * [32] N. Lütkenhaus, Theory of Quantum Key Distribution, in D. Bruß and G. Leuchs, Lectures on Quantum Information (Wiley-VCH, 2007), p. 271.
  * [33] V. Scarani, H. Bechmann-Pasquinucci, N. J. Cerf, M. Dušek, N. Lütkenhaus, and M. Peev, Rev. Mod. Phys. 81, 1301 (2009). (2009).
  * [34] A. Laing, V. Scarani, J. G. Rarity, and J. L. O’Brien, Phys. Rev. A 82, 012304 (2010).
  * [35] C. W. F. Everitt et al., Class. Quant. Grav. 25, 114002 (2008).


# Differentially Private All-Pairs Shortest Distances for Low Tree-Width
Graphs

1st Javad B. Ebrahimi  Sharif University of Technology
Institute for Research in Fundamental Sciences (IPM)
Tehran, Iran
<EMAIL_ADDRESS>2nd Alireza Tofighi Mohammadi  Sharif University of
Technology
Tehran, Iran
<EMAIL_ADDRESS>3rd Fatemeh Kermani  Sharif University of Technology
Tehran, Iran
<EMAIL_ADDRESS>
###### Abstract

In this paper, we present a polynomial time algorithm for the problem of
differentially private all pair shortest distances over the class of low tree-
width graphs. Our result generalizes the result of Sealfon [9] for the case of
trees to a much larger family of graphs. Furthermore, if we restrict to the
class of low tree-width graphs, the additive error of our algorithm is
significantly smaller than that of the best known algorithm for this problem,
proposed by Chen et. al. in [2].

###### Index Terms:

differential privacy, algorithms, shortest path, graph theory, tree-width.

##  I Introduction

###  I-A Differential Privacy

Privacy-preserving data analysis is a way of learning about population while
keeping confidential information about individuals private. Differential
privacy introduced in the work of Dwork et. al. [4] is a definition and
clarification of this concept.

There are two main ingredients to make an algorithm privacy preserving. The
first one is to answer queries in a randomized way. That is, to output a
random element from the set of all possible outcomes. Equivalently, the output
can be modeled as a probability distribution over the set of possible
outcomes. The second point is to make sure that adding or removing any
individual from the dataset does not significantly change the output
distribution. Datasets which are only different in one individual, are called
neighboring datasets. To generalize neighboring definition in a more abstract
context, we can consider the case where the domain of the algorithm is a
metric space $(\mathcal{X},d)$. In this case, we say $x,y\in\mathcal{X}$ are
neighbors if $d(x,y)\leq 1$. As an example, when $\mathcal{X}$ is the set of
integral vectors and $d$ is the $\ell_{1}$-metric, neighboring elements are of
the form $x,y\in\mathcal{X}$ such that $x,y$ differ in exactly one co-ordinate
and in that co-ordinate, they are equal to two consecutive numbers.

One may observe that if a mechanism outputs the same distribution regardless
of the input, it will be completely private. However, the main challenge in
differential privacy is to design differential private mechanism with high
level of privacy, while, approximating a target function reasonably accurate.
More precisely, for a target function $f$ on a metric space $(\mathcal{X},d)$,
$\mathcal{M}$ is a DP mechanism if for any close point
$x_{1},x_{2}\in\mathcal{X}$, $\mathcal{M}(x_{1}),\mathcal{M}(x_{2})$ are close
distributions and $\mathcal{M}(x)$ is a good approximation of $f(x)$. In
section IV we make this definition mathematically precise.

###  I-B Sensitivity

The $\ell_{1}$ sensitivity of a function $f$ is the maximum value that the
change of a single individual’s data in input can change the function $f$’s
output. Therefore, intuitively, sensitivity measures the minimum amount of
uncertainty we must have in the response in order to guarantee keeping an
individual’s data private.

The output of functions with higher sensitivity must be perturbed more to
preserve a certain extent of privacy, and for functions with lower
sensitivity, we can add lower noise to guarantee differential privacy with the
same amount of privacy leak.

By choosing the noise from a family of the distributions, called Laplace
distributions, we can guarantee that the mechanism is private and the error is
small. For more details about Laplace noise and the proof of this statement,
see [5] and for the formal definitions of the $\varepsilon$-differential
privacy, error and Laplace mechanism see section IV.

###  I-C Differential privacy on graphs

One of the canonical problems in graph theory and computer science is to
compute the shortest path between a pair of vertices of a given graph. This
problem is well-explored and efficient algorithms have been proposed in the
literature. However, we are interested in the differential private version of
this problem. This problem was first proposed by Sealfon in [9]. Now, we
explain the model of the problem.

Let $G=(V,E)$ be a graph on the vertex set $V$ and the edge set $E$ and let
$w$ be the edge weight function that assigns non-negative weights to the edges
of the underlying graph $G=(V,E)$. Suppose that $G$ is publicly known but $w$
is private. Each dataset is a weight function $w$ and two datasets
$w_{1},w_{2}$ are neighbors when $\|w_{1}-w_{2}\|_{1}:=\sum_{e\in
E}|w_{1}(e)-w_{2}(e)|\leq 1$.

In the all pairs shortest distances problem, the target function is
$f:\mathcal{X}\to\mathbb{R}^{\binom{n}{2}}$. Where $\mathcal{X}$ is the set of
all possible weights on edges of $G$ and for a $w\in\mathcal{X}$, $f(w)$ is a
vector of shortest distances of all pairs of vertices.

The goal is to efficiently construct a differential private mechanism to
approximate $f$ with minimum $\ell_{\infty}$ error. We call this error the
additive error of the algorithm.

The rest of this paper is organized as follows. In the next section, we review
the history of differentally private APSD problem and the previous results on
this problem. In Section III, we try to explain the main challenges to
generalizing the Sealfon’s approach from trees to low tree-width graphs. Then
we describe our solution to overcome these challenges in several stages. Also,
we explain our algorithm for differentially private APSD problem informally. A
high level justification of the correctness of the algorithm is also provided
in that section. Next, we overview some preliminaries and introduce basic
definitions and notations. Section V consists of the formal description of the
algorithm, the proof of its correctness and analysing the time complexity of
the algorithm. Finally, in the last section we conclude our paper.

##  II Related Works

Differential privacy has been applied to graph problems, including the all-
pairs shortest distances (APSD for short) problem. Sealfon [9] was the first
to formally study APSD with privacy. The paper introduces a model for
differentially private analysis of the shortest distances in a weighted graphs
in which the graph topology is assumed to be publicly known and the private
information consists only of the edge weights. In the DP framework, he
required that the algorithm be $(\varepsilon,\delta)$-DP, where neighboring
data sets (i.e. inputs) correspond to those whose weight vectors
$w,w^{\prime}$ which differs by at most 1 in the $\ell_{1}$-distance. Sealfon
gave an $O(n\log n/\varepsilon)$-error ”input-perturbation” algorithm for
APSD, which adds Laplace noise to all edge weights and computes the shortest
path in this resulting graph with noisy weights.

When the underlying graph is a tree, Sealfon developed a DP mechanism with
significantly smaller error. His main idea is to employ a standard technique
in graph algorithm known as “Centroid decomposition” of trees. He first finds
the unique path from the root to all the vertices and then, for every pair of
vertices, with 3 queries, he can compute the distances between the two.

The idea is to split the tree into subtrees of at most half the size of the
original tree. As long as we can release the distance from the root to each
subtree with small error, we can then, recurse on the subtrees. Sealfon showed
that there is an algorithm that is $\varepsilon$-differentially private on $T$
such that on the input $w:E\to\mathbb{R}^{+}$, outputs approximate distances
between all pairs of vertices. Also, with probability at least $1-\gamma$, the
additive error on each output distance is
$O(\log^{2.5}V\cdot\log(1/\gamma)/\varepsilon)$ for any $\gamma\in(0,1)$.

Fan and Li [6] revisited the problem of privately releasing approximate
distances between all pairs of vertices in a graph. They proposed improved
algorithms with smaller error term to that problem for grid graphs and trees.

Fan et al. [7] also generalized Sealfon’s approach for trees to graphs that
with removing few nodes become acyclic. The subset of vertices that removing
make graph without any cycles called feedback vertex set.

Chen et al. in [2] also studied this problem. They gave an $\varepsilon$-DP
algorithm with additive error $\tilde{O}(n^{2/3}/\varepsilon)$ and an
$(\varepsilon,\delta)$-DP algorithm with additive error
$\tilde{O}(\sqrt{n}/\varepsilon)$ where $n$ denotes the number of vertices.
This is the best known additive error for arbitrary graphs.

##  III Technical Overview

Two of the commonly used ideas of differential privacy, are to add random
noise to the input (input perturbation), or to add random noise to the output
of the algorithm (output perturbation). In both cases, the output of the
algorithm is a random function which estimates the desired function and has
some error.

For instance, if we add i.i.d. Laplace noises to the input, (i.e. edge
weights), and then, compute the shortest path according to noisy weights, the
magnitude of error to achieve $\varepsilon$-DP is $1/\varepsilon$. 111In order
to achieve $\varepsilon$-DP, we can add a Laplace noise with parameter
$1/\varepsilon$. In Section IV we define the Laplace distribution and see that
the magnitude of such noise will be proportional to $1/\varepsilon$ with high
probability. Since every path in a graph has at most $n-1$ edges, we may need
to use $\Theta(n)$ noisy values to compute each shortest distance. Thus, the
error is proportional to $\Theta(n\cdot 1/\varepsilon)$ (see Algorithm 3 of
[9]). Alternatively, if we add Laplace noise to the output, i.e. the weights
are exact and after computing the shortest distances we add the noise to the
result. Since there are $\Theta(n^{2})$ pairs of shortest distances, in order
to achieve $\varepsilon$-DP, the magnitude of the noise must be
$\Theta(n^{2}/\varepsilon)$. Thus, the error is proportional to
$\Theta(n^{2}/\varepsilon)$ (see Section 4 of [9]).

Note that in the both cases, the error is proportional to the product of the
magnitude of noise and the number of needed noisy values to release each
shortest distance. Therefore, roughly speaking, in order to reduce the
magnitude of error, we must reduce either the magnitude of the noises or the
number of added noises or both.

For trees, Sealfon in Section 4.1 of [9] invented an elegant idea to decrease
the magnitude of noise and the number of noisy values needed to compute each
of the shortest distances.

The algorithm constructs an intermediate graph, which has two important
properties: First, if we change the weights of the input graph by at most 1,
only $O(\log n)$ of the weights in the intermediate graph will change and they
change no more than 1. Secondly, for all $v,u\in V$, the weight of an $O(\log
n)$-hop shortest path between $v$ and $u$ in the intermediate graph, is equal
to the shortest distance between $v$ and $u$ in the input graph. Thus, we can
use $O(\log n/\varepsilon)$-magnitude Laplace noises and we only need $O(\log
n)$ noisy values to compute each shortest distance. Hence, the magnitude of
the error is roughly $O(\log^{2}n/\varepsilon)$. 222The exact value is
$O(\log^{2.5}n/\varepsilon)$. The extra log factor is because this property
with high probability.

$w_{1}$$w_{2}$$w_{3}$$w_{4}$$w_{5}$$w_{6}$$w_{7}$$w_{1}$$w_{2}$$w_{4}$$w_{5}$$w_{7}$$w_{1}+w_{2}+w_{3}$$w_{5}+w_{6}$
Figure 1: Making an intermediate graph for a path. black edges are the base
graph and the blue edges are the intermediate graph.

######  Example 1 (Sealfon’s construction of the intermediate graph for a path
)

Figure 1 gives an example of the graph made by Sealfon’s algorithm. The
$\ell_{1}$ sensitivity of the graph is at most 2, i.e. changing the weight of
a black edge affects at most 2 of the blue edges

In this paper, we aim to extend the Sealfon’s idea beyond trees. We address
several challenges due to inherent differences between trees and low tree-
width graphs. These challenges include:

  1. 1.

The edges of the shortest path between two specific vertices in a tree, only
depend on the publicly known topology of the graph and they are unique. So the
desired algorithm, only needs to privately release the summation of private
weights of the edges of the unique paths. Clearly, this property is not true
for non-tree graphs.

  2. 2.

In trees, due to uniqueness of shortest paths, it is possible to calculate the
all pairs shortest distances using only the shortest distances between the
root and other vertices. This can be achieved by computing the lowest common
ancestor for each pairs of vertices and calculating the distances from the
root to every vertex. This property of trees allows for efficient calculation
of all pairs shortest distances using only the root to all distances.

  3. 3.

Trees have a vertex called the centroid. The centroid is a vertex that,
removing it, separates the tree into connected components which have sizes no
greater than half the size of the original tree.

This paper introduces Algorithm 3 that calculates all pairs shortest distances
with differential privacy on low tree-width graphs and overcome the challenges
above. The algorithm takes $G=(V,E)$ and $T$ as input. Where $T$ is tree
decomposition of $G$ and $T$ has width $p$. Also assume that $|V|=n$. The
algorithm consists of three stages. In the first stage, we construct an
intermediate graph with the properties that mentioned above, in the second
stage, we ensure the differential privacy by adding noises to the intermediate
graph and in the last one, the algorithm estimates all pairs shortest
distances.
Stage 1: Algorithm 2, uses a divide and conquer approach that constructs an
intermediate graph $G^{\prime}$ by adding edges to the original graph. By
proposition 2, the algorithm exploits $T$ and finds a subset of vertices,
called separator, which removing it partitions graph into components with half
size. Thus, the depth of recursion call of the algorithm will be $O(\log n)$.
We use separator instead of centroid to address challenge 3.

The edges of intermediate graph are computed by the ComputeEdges recursive
function in Algorithm 1. This function takes as input, a weighted graph
$G=(V,E)$, a tree decomposition $T$ of $G$, and a subset of vertices $V_{0}$
of $G$. The union of $V_{0}$ and separator act like root in tree. we call the
union, $V^{\prime}_{0}$. We deal challenge 2 using $V^{\prime}_{0}$. In each
recursion call of ComputeEdges, lemma 4 shows that the shortest distances
between all $v\in V^{\prime}_{0}$ and $V$ is equals to $O(\log n)$-hop
shortest distance between $v$ and $u$ in the returned graph.
We need to extend the result to all pairs shortest distances. To do so, we
need a wise selection of smaller problems and $V_{0}$. We construct smaller
versions of the problem by combining the connected components after removing
the separator and the separator itself. We also propagate $V^{\prime}_{0}$ for
$V_{0}$ of smaller versions of the problem in the divide and conquer approach.
In Lemma 5, we show that with this selection, we can extend the result from
$V_{0}^{\prime}$ to $V$ for all pairs shortest distances.
Stage 2: Lemma 3 shows that the sensitivity of the intermediate graph is low.
Thus, the algorithm then adds Laplace noise to the edge weights of
$G^{\prime}$ to provide differential privacy. The scale of the Laplace noise
is $O(p^{2}\log^{2}n/\varepsilon)$, where $p$ is the tree-width of the graph.
Stage 3: In the description of stage 1, we mentioned that for each $v,u\in V$,
the shortest distance between $v$ and $u$ is equal to an $O(\log n)$-hop
shortest distance in the intermediate graph. The algorithm uses post-
processing Proposition 4 to return all-pairs shortest path distances for paths
with at most $O(\log n)$ hops in the graph $G^{\prime}$ with noisy edge
weights. The minimization of the weight of all $O(\log n)$-hop paths addresses
challenge 1.

We uses Laplace noises, thus, with high probability, the magnitude of each
noise is proportional to $O(\log n\cdot p^{2}\log^{2}n/\varepsilon)$. We
minimize over $O(\log n)$-hop paths, thus we use only $O(\log n)$ noises to
estimate each shortest distance. Thus, with high probability, the magnitude of
the additive error of each shortest distance is at most
$O(p^{2}\log^{4}n/\varepsilon)$. This result outperforms previous results in
$\varepsilon$-DP when $p=o(n^{1/3})$.

In section VII, we provide a detailed description of the technical aspects of
the algorithm and its proof.

##  IV Preliminaries

In this section we describe the main concepts of graph theory and differential
privacy, that are used in this paper.

###  IV-A Graph Theory

Let $G=(V,E)$ denote an undirected graph with vertex set $V$ and edge set $E$.
we also show $V$ and $E$ by $V(G)$ and $E(G)$ respectively and let
$w:E\rightarrow\mathbb{R}^{+}$ be a weight function. Let $|V|$ and $|E|$ be
the number of vertices and edges, respectively. For $X,Y\subseteq V$, let
donate $E[X,Y]$ be all edges between $X$ and $Y$.

Let $\mathcal{P}^{G}_{xy}$ denote the set of paths between a pair of vertices
$x,y\in V(G)$. For any path $P\in\mathcal{P}^{G}_{xy}$, the weight $w(P)$ is
the sum $\sum_{e\in P}w(e)$ of the weights of the edges of $P$. The distance
$d_{G,w}(x,y)$ from $x$ to $y$ denotes the weighted shortest distance
$\min_{P\in\mathcal{P}^{G}_{xy}}w(P)$. We will denote the hop length $\ell(P)$
of path $P=\left(v_{0},\ldots,v_{\ell}\right)$ is the number $\ell$ of edges
on the path. Also the $k$-hop distance $d_{G,w}^{k}(x,y)$ between $x$ and $y$
denotes as the minimum weight between at most $k$-hop paths
$d_{G,w}^{k}=\min_{P\in\mathcal{P}^{G}_{xy},\ell(P)\leq k}w(P)$.

######  Definition 1 (Tree decomposition)

[3, 1] A tree decomposition of a graph $G(V,E)$ is a labeled tree $T$, where
each node $i$ of $T$ is labeled by a subset (bag) $B_{i}\subset V$ of vertices
of $G$, each edge of $G$ is in a subgraph induced by at least one of the
$B_{i}$, and the nodes of $T$ labeled by any vertex $v\in V$ are connected in
$T$. The width of $T$ is maximum of cardinality of bags of $T$ minus 1.

######  Definition 2 (Tree-width)

[3, 1] The tree-width of $G$ is the minimum integer $p$ such that there exists
a tree decomposition $G$ with width $p$.

It is known that a tree has tree-width 1, a series-parallel graph has tree-
width 2, a $k$-clique has tree-width $k-1$, and an $n$ by $n$ grid has tree-
width $\Theta(n)$.

######  Proposition 1 (Reduced tree decomposition)

Let $G=(V,E)$ be a graph of tree-width $k$, and let
$H=(V^{\prime},E^{\prime})$ be a subgraph of $G$. If $T$ a width-$k$ tree
decomposition of $G$, then, by removing nodes that are not in $V^{\prime}$
from the bags of $T$ and removing any bags that become subsets of other bags,
we obtain a reduced tree decomposition $T^{\prime}$ of $H$ with width $k$, and
no bag of $T^{\prime}$ being a subset of another.

######  Proposition 2 (Tree-width implies separator)

[8] Let $G(V,E)$ be a graph of tree-width $p$. Then, there is a set $S$ of at
most $p+1$ such that every connected component of $G\setminus S$ has no more
than half of vertices. We call this set the separator of graph and we can find
it with $O(|V|^{2})$ time complexity by tree decomposition of graph.

###  IV-B Differential Privacy

We now formally define differential privacy in the private edge weight model.

######  Definition 3 (Neighboring weights)

For any edge set $E$, two weight functions
$w,w^{\prime}:E\rightarrow\mathbb{R}^{+}$ are neighboring, denoted $w\sim
w^{\prime}$, if

$\left\|w-w^{\prime}\right\|_{1}=\sum_{e\in
E}\left|w(e)-w^{\prime}(e)\right|\leq 1$

######  Definition 4 (Mechanism)

A randomized algorithm $\mathcal{M}$ with domain $A$ and discrete range $B$ is
associated with a mapping $\mathcal{M}:A\to\Delta(B)$. On input $a\in A$, the
algorithm $\mathcal{M}$ outputs $\mathcal{M}(a)=b$ with probability
$(\mathcal{M}(a))_{b}$ for each $b\in B$. The probability space is over the
coin flips of the algorithm $\mathcal{M}$.

######  Definition 5 (Differential privacy, [4])

A randomized algorithm $\mathcal{M}:A\to R$ is
$(\varepsilon,\delta)$-differentially private if for all $\mathcal{S}\subseteq
R$ and for all $x,y\in R$ such that $x\sim y$ :

$\operatorname{Pr}[\mathcal{M}(x)\in\mathcal{S}]\leq\exp(\varepsilon)\operatorname{Pr}[\mathcal{M}(y)\in\mathcal{S}]+\delta$

where the probability space is over the coin flips of the mechanism
$\mathcal{M}$.

If $\delta=0$, we use $\epsilon$-differential privacy or $\epsilon$-DP as
$\epsilon$-differential privacy.

######  Definition 6 (Sensitivity of a function)

The $\ell_{1}$-sensitivity of a function $f:A\to\mathbb{R}^{k}$ is:

$\Delta_{1}f=\max_{x,y\in A,x\sim y}\|f(x)-f(y)\|_{1}$

The Laplace distribution with scale parameter $b>0$ is defined by the
probability density function

$f(x)=\frac{1}{2b}\exp\left(-\frac{|x|}{b}\right).$

For a random variable $X\sim\text{Lap}(b)$, the probability that $|X|\geq
t\cdot b$ for some $t>0$ is given by $\Pr(|X|\geq t\cdot b)=2\exp(-t).$

######  Definition 7 (Laplace mechanism)

Given any function $f:A\rightarrow\mathbb{R}^{k}$, the Laplace mechanism is
defined as:

$\mathcal{M}_{L}(x,f(\cdot),\varepsilon)=f(x)+\left(Y_{1},\ldots,Y_{k}\right)$

where $Y_{i}$ are i.i.d. random variables drawn from
$\text{Lap}(\Delta_{1}f/\varepsilon)$.

In order to be able to use the Laplace mechanism, we should know that it
preserve the privacy of the algorithm. Theorem 3.6 of [5] states as bellow.

######  Proposition 3 (Laplace mechanism is $\varepsilon$-DP [5])

The Laplace mechanism $\mathcal{M}_{L}(x,f(\cdot),\varepsilon)$ is
$\varepsilon$-DP.

######  Proposition 4 (Post-Processing)

Let $\mathcal{M}:\mathbb{R}^{|\mathcal{X}|}\rightarrow R$ be a randomized
algorithm that is $(\varepsilon,\delta)$-differentially private. Let
$f:R\rightarrow\mathbb{R}^{\prime}$ be an arbitrary randomized mapping. Then,
$f\circ\mathcal{M}:\mathbb{R}^{|\mathcal{X}|}\rightarrow\mathbb{R}^{\prime}$
is $(\varepsilon,\delta)-$ differentially private.

##  V Main result

In Section III, we described the intuition behind the algorithm and its
properties. In this section, we will present the details of the algorithm
implementation in pseudo-code form. Next, we will present the technical
aspects of its properties and correctness.

Algorithm 1 Determining Shortcut Edges for Addition to The Intermediate Graph

1:function ComputeEdges($G=(V,E),w:E\to\mathbb{R}^{+},T,V_{0}\subseteq V$)

2:$G$ is the graph with weight function $w$. $T$ is the tree decomposition of
$G$ with maximum bag size $p+1$, and $V_{0}$ is a helper argument called the
starting set.

3:A list of triples $(v,u,x)$ where $v,u\in V$ and $x\in\mathbb{R}^{+}$ that
should be added to the intermediate graph for computing distances with few
hops

4: $R\leftarrow\emptyset$ $\triangleright$ Array $R$ is a list of weighted
edges

5: if $|V|\leq 6(p+1)$ then

6: for all $v\in V$ do

7: for all $u\in V$ do

8: Insert $(v,u,d_{G,w}(v,u))$ into $R$

9: else$\triangleright$ Partition the graph into smaller components using a
bag from the tree decomposition

10: Let $S$ be the bag of $T$ that partitions $G$ into components of size at
most $|V|/2$ by proposition 2

11: $V_{0}^{\prime}\leftarrow V_{0}\cup S$

12: Let the connected components of $G\setminus S$ be $C_{1},\ldots,C_{l}$
$\triangleright$ Add edges between vertices in the starting set and separator

13: for all $v\in V_{0}^{\prime}$ do

14: for all $u\in S$ do

15: Insert $(v,u,d_{G,w}(v,u))$ into $R$ $\triangleright$ Recursively compute
edges for each component

16: for all $i\in[l]$ do

17: $H_{i}\leftarrow(V(C_{i})\cup S,E(C_{i})\cup E[C_{i},S])$

18: $V_{i}\leftarrow(V(C_{i})\cap V_{0}^{\prime})$

19: Let $T_{i}$ be the reduced tree decomposition $T$ for $H_{i}$ using
Proposition 1

20: Let $w_{i}$ be the restriction of function $w$ to edges in $H_{i}$

21: $R_{i}\leftarrow$ComputeEdges($H_{i},w_{i},T_{i},V_{i}$)

22: for all $(v,u,x)\in R_{i}$ do

23: Insert $(v,u,x)$ into $R$

24: return $R$

25:end function

Algorithm 2 Constructing a Low $\ell_{1}$-Sensitivity Intermediate Graph for
Efficient APSD Computation

1:function ConstructGraph($G=(V,E),w:E\to\mathbb{R}^{+},T,V_{0}\subseteq V$)

2:Graph $G$ with weight function $w$, tree decomposition $T$ of $G$ with
maximum bag size $p+1$, and starting set $V_{0}$

3:A graph in which all-pair shortest path distances of $G$ can be computed
using only $O(\log|V|)$-hop paths

4: $R\leftarrow$ ComputeEdges($G,V_{0}$)

5: Create a copy of $G$ and call it $G^{\prime}$

6: Create a copy of $w$ and call it $w^{\prime}$ $\triangleright$ Add the
computed shortcut edges to the new graph

7: for all $(v,u,x)\in R$ do

8: if there is no edge between $v$ and $u$ then

9: Add edge between $v$ and $u$ in $G^{\prime}$

10: Set $w^{\prime}(v,u)\leftarrow x$

11: else if $x<w^{\prime}(v,u)$ then

12: Set $w^{\prime}(v,u)\leftarrow x$

13: return ($G^{\prime}$, $w^{\prime}$)

14:end function

The following theorem, states that Algorithm 3 has the desired properties.

######  Theorem 1 (Main theorem)

Let $G=(V,E)$ be a graph of tree-width $p$. Then, there exists an
$\varepsilon$-differentially private algorithm that takes as input a weight
function $w:E\to\mathbb{R}^{+}$ and releases the all-pairs shortest path
distances of $G$ with weight $w$. For any $\gamma\in(0,1)$, the error is
bounded by $O(\log(1/\gamma)\cdot p^{2}\cdot\log^{4}(|V|)/\varepsilon)$ with
probability at most $1-\gamma$.

To prove that Algorithm 3 satisfies the conditions of our main theorem
(Theorem 1), we need to establish several properties of Algorithms 1, 2, and
3.

We present these properties in the form of following lemmas. The proofs can be
found in Section VII.

The first property we will show is that the recursion depth of Algorithm 1 is
not too large.

######  Lemma 1 (Recursion depth of algorithm is logarithmic)

Let $G=(V,E)$ be a graph of tree-width $p$ and let $T$ be its corresponding
tree-decomposition. Then, the recursion depth of Algorithm 1 on input $G$ and
$T$ is at most $O(\log|V|)$.

In the previous lemma, we demonstrated that the depth of the Algorithm 1 is
$O(\log|V|)$. Since the size of the starting set $V_{0}$ increases by at most
$O(p)$ at each depth, there is an upper bound for the size of the starting set
in all recursive steps. The following lemma presents this condition in a
formal format.

######  Lemma 2 (Upper bound on starting set size)

When running the $\textsc{ComputeEdges}(G,w,T,V_{0})$ function on a graph
$G=(V,E)$ with tree-width $p$ and a set of starting vertices $V_{0}\subseteq
V$, the size of the starting vertex set in all recursive steps of the function
is bounded by $O(|V_{0}|+p\cdot\log|V|)$.

Now, it’s time to find an upper bound for the sensitivity of the function.

######  Lemma 3 (Sensitivity of algorithm)

Let $G=(V,E)$ be a graph of tree-width $p$ and let $T$ be its corresponding
tree-decomposition. Let $V_{0}\subseteq V$ be an arbitrary set of starting
vertices. If $f(w)=\textsc{ConstructGraph}(G,w,T,V_{0})$, then, the $\ell_{1}$
sensitivity of $f$ is $O\left((|V_{0}|+p)\cdot
p\cdot\log^{2}|V|+p^{2}\right)$.

By Lemma 3, we know that to guarantee $\varepsilon$-DP, the magnitude of each
noise can be bounded by $O(p^{2}\log^{2}|V|/\varepsilon)$. The next two lemmas
state that we can also involve only a small number of shortcuts to compute the
shortest distances. The following lemma states that we can compute the
shortest distance between each pair $v\in V_{0}\cup S$ and $u\in V$ using only
$O(\log|V|)$-hop paths in the intermediate graph.

######  Lemma 4 (Distance preservation of intermediate graph: Some pair case)

Let $G=(V,E)$ be a weighted graph of tree-width $p$, $T$ be its corresponding
tree-decomposition and $w:E\to\mathbb{R}^{+}$ be the weight function. Let
$V_{0}\subseteq V$ be an arbitrary subset of vertices. Let
$(G^{\prime},w^{\prime})$ be the output of
$\textsc{ConstructGraph}(G,w,T,V_{0})$ and $S$ be the bag selected on first
call of ComputeEdges on line 10 in Algorithm 1. Then, for all $v\in V_{0}\cup
S$ and $u\in V$, we have $d_{G,w}(v,u)=d_{G^{\prime},w^{\prime}}^{l}(v,u)$
where $l=\max(2,\log_{1.5}|V|)$.

Now, it’s time to improve upon the result of the last lemma. In the next
lemma, we will prove that the result is also correct for all pairs shortest
distances.

######  Lemma 5 (Distance preservation of intermediate graph: All pair case)

Let $G=(V,E)$ be a weighted graph of tree-width $p$ and the weight function
$w:E\to\mathbb{R}^{+}$. Let $T$ be a tree-decomposition of $G$, and let
$(G^{\prime},w^{\prime})=\textsc{ConstructGraph}(G,w,T,\emptyset)$. Let $S$ be
the bag selected on the first call of ComputeEdges on line 10 in Algorithm 1.
Then, for all $v$ and $u\in V$, we have
$d_{G,w}(v,u)=d_{G^{\prime},w^{\prime}}^{l}(v,u)$ where
$l=2\cdot\max(2,\log_{1.5}|V|)$.

Algorithm 3 Differentially Private All-Pairs Shortest Path Distances for Low
Tree-Width Graphs

1:Graph $G$ with weight function $w$, tree decomposition $T$ of $G$ with
maximum bag size $p+1$ and a constant number $c$ and privacy parameter
$\varepsilon$

2:An estimate of all-pairs shortest distances with low error

3:$\triangleright$ First stage: construct the shortcut graph

4:$(G^{\prime},w^{\prime})\leftarrow\textsc{ConstructGraph}(G,w,T,\emptyset)$

5:$\triangleright$ Second stage: add Laplace noise to the edge weights to
provide differential privacy

6:for all $e\in E(G^{\prime})$ do

7: $X_{e}\sim\mathrm{Lap}(c\cdot(p+1)^{2}\log(|V|)/\varepsilon)$

8: $w^{\prime}(e)\leftarrow w^{\prime}(e)+X_{e}$

9:$\triangleright$ Third stage: use post-processing to return all-pairs
shortest path distances

10:return All-pairs shortest at most $c\cdot\log|V|$-hop distances for
$G^{\prime}$ with weight function $w^{\prime}$

#### Proof of Theorem 1

Let $\mathcal{M}(G,T,p,w,c,\varepsilon)$ be the following mechanism. Run
Algorithm 3. Lemma 3 asserts that the $\ell_{1}$ sensitivity of the algorithm
after the first stage is $O\left((0+p)\cdot p\cdot\log^{2}|V|+p^{2}\right)$.
Then, there exists some $c_{1}$ such that the $\ell_{1}$ sensitivity after the
first stage is at most $c_{1}\cdot\left(p^{2}\cdot\log^{2}(|V|)\right)$. This
allows us to use the Laplace mechanism. By the Laplace mechanism 3, after the
second stage, the algorithm is $\varepsilon$-DP for all $c\geq c_{1}$. So, by
post-processing 4, $\mathcal{M}(G,T,p,w,c,\varepsilon)$ is $\varepsilon$-DP
for all $c\geq c_{1}$.

For all $\gamma\in(0,1)$, from the Laplace distribution, we know that for all
$e\in E(G^{\prime})$, $\Pr(|X_{e}|\geq\log(|E(G^{\prime})|/\gamma)\cdot c\cdot
p^{2}\cdot\log^{2}(|V|)/\varepsilon)=\gamma/|E(G^{\prime})|$, and we also know
that $|E(G^{\prime})|\leq|V|^{2}$. So by the union bound, with probability
$1-\gamma$, no $X_{e}$ has magnitude greater than
$2c\cdot\log(|V|/\gamma)\cdot p^{2}\cdot\log^{2}(|V|)/\varepsilon$. In the
last stage, we return at most $c\log|V|$-hop shortest distances. These paths
contain at most $c\log|V|$ edges and so with probability $1-\gamma$, the
magnitude of error in each released distance is at most $2c^{2}\cdot
log(|V|/\gamma)p^{2}log^{3}(|V|)/\varepsilon$ between the returned value and
the result if all $X_{e}$s are equal to zero. From lemma 5, for
$c>2/\log(1.5)$, the result when $X_{e}$s are equal to zero is APSD for $G$
with weight $w$. Thus, for $c>max(c_{1},2/\log(1.5))$,
$\mathcal{M}(G,T,p,w,c,\varepsilon)$ is an $\varepsilon$-DP mechanism and with
probability $1-\gamma$, has an error less than
$2c^{2}log(|V|/\gamma)p^{2}log^{3}(|V|)/\varepsilon$, which is
$O(log(1/\gamma)p^{2}log^{4}(|V|)/\varepsilon)$.

Note that in the proof of Theorem 1, we took the mechanism
$\mathcal{M}(G,T,p,w,c,\varepsilon)$ as Algorithm 3 on the input graph $G$,
weight function $w$, tree decomposition $T$, constant $c$, and privacy
parameter $\varepsilon$, and returns its result.

###  V-A Time Complexity

In this sub-section, we analyze the time complexity of Algorithm 3 and show
that it has a polynomial-time implementation. Lemma 6 shows that the first
stage of the algorithm is polynomial-time and Theorem 2 shows that our main
algorithm is a polynomial-time algorithm.

###### Lemma 6

The time complexity of Algorithm 2 on an input graph $G=(V,E)$ is
$O(|V|^{3}\log|V|)$.

The proof of Lemma 6 is deferred to the appendix.

###### Theorem 2

The time complexity of Algorithm 3 on input graph $G=(V,E)$ is
$O(|V|^{3}\log|V|)$.

###### Proof:

Lemma 6 shows that the first stage of the algorithm has $O(|V|^{3}\log|V|)$
time complexity. In the second stage, we run a for loop on every edge of the
intermediate graph, so its time complexity is $O(|V|^{2})$. The third stage of
the algorithm can be implemented using dynamic programming. Let $d(v,u,k)$ be
the $k$-hop shortest distance on $G^{\prime}$ between $v$ and $u$. We can fill
it if $k=0$ or $k=1$ in $O(|V|^{2})$ time. Then, for every $v,u\in V,1\leq
k\leq c\cdot\log|V|$, $d(v,u,k)$ is equal to the minimum of
$d(v,z,k-1)+w^{\prime}(z,u)$ for every $z\in V$. So we can compute it in
$O(|V|^{3}\log|V|\cdot c)$ time. We assume $c$ is constant, so the running
time of the algorithm is $O(|V|^{3}\log|V|)$. ∎

##  VI Conclusion

We proposed a polynomial time differentially private algorithm for the problem
of all pair shortest distance problem for the class of low tree-width graphs.
This class of graphs contains trees as a subclass. Thus, our founding
generalizes the result of Sealfon in [9]. Despite the fact that general low
tree-width graphs are fundamentally more complex than trees, we manage to
achieve essentially the same additive error term as that of the work of
Sealfon for trees.

On the other hand, while the algorithm of the work of [2] provides a
differentially private algorithm for the all pair shortest distance problem
for general graphs, when restrict to the class of low tree-width graphs (i.e
tree-width of order $o(n^{1/3})$), our algorithm benefits from significantly
lower additive error. i.e. $O(p^{2}\operatorname{polylog}(n)/\varepsilon)$
versus $O(n^{2/3}\operatorname{polylog}(n)/\varepsilon)$.

## References

  * [1] H. L. Bodlaender, “A tourist guide through treewidth,” _Acta Cybernetica_ , vol. 11, pp. 1–21, 1998.
  * [2] J. Y. Chen, B. Ghazi, R. Kumar, P. Manurangsi, S. Narayanan, J. Nelson, and Y. Xu, “Differentially private all-pairs shortest path distances: Improved algorithms and lower bounds,” in _Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)_. SIAM, 2023, pp. 5040–5067.
  * [3] R. Diestel, _Graph Theory_ , 4th ed. Springer-Verlag, 2010.
  * [4] C. Dwork, F. McSherry, K. Nissim, and A. Smith, “Calibrating noise to sensitivity in private data analysis,” in _Theory of Cryptography_ , S. Halevi and T. Rabin, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006, pp. 265–284.
  * [5] C. Dwork and A. Roth, “The algorithmic foundations of differential privacy,” _Foundations and Trends in Theoretical Computer Science_ , vol. 9, 01 2013\.
  * [6] C. Fan and P. Li, “Distances release with differential privacy in tree and grid graph,” in _2022 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2022, pp. 2190–2195.
  * [7] C. Fan, P. Li, and X. Li, “Breaking the linear error barrier in differentially private graph distance release,” _arXiv preprint arXiv:2204.14247_ , 2022\.
  * [8] U. Feige, “Treewidth and graph minors,” https://www.wisdom.weizmann.ac.il/ robi/teaching/2012a-AdvancedAlgorithms/Lecture9+10-Treewidth.pdf, 2012\.
  * [9] A. Sealfon, “Shortest paths and distances with differential privacy,” in _Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems_ , ser. PODS ’16. New York, NY, USA: Association for Computing Machinery, 2016, p. 29–41. [Online]. Available: https://doi.org/10.1145/2902251.2902291

##  VII Appendix

###  VII-A Proof of Lemma 1

Let $d(n)$ denote the maximum recursion depth of the ComputeEdges function on
graph inputs with $n$ vertices with tree-width $p$, we have:

$d(n)\leq\left\\{\begin{array}[]{ll}1&n\leq 6\cdot(p+1)\\\
d(n/2+p+1)+1&Otherwise\\\ \end{array}\right.$

Thus, we claim that for $C\geq\frac{1}{\log 1.5}$, $d(n)\leq C\log n$ we show
the result by induction.

For $n\leq 6(p+1)$, we have $d(n)=1=O(\log n)$. Otherwise, we have:

$\displaystyle\operatorname{d}(n)$ $\displaystyle=1+d(n/2+p+1)$
$\displaystyle\leq 1+C(\log(n/2+p+1))$ $\displaystyle\leq 1+C(\log(n/c))$
$\displaystyle(3n/2>p+1+n/2)$ $\displaystyle\leq 1-C\log 1.5+C\log(n)$
$\displaystyle\leq C\log(n)$ $\displaystyle(C\geq 1/\log 1.5)$

Hence, $d(n)=O(\log n)$ and by induction, the statement is proved.

###  VII-B Proof of Lemma 2

During the execution of the algorithm, the size of the starting vertex set
increases by at most $p+1$ in each recursive step. According to Lemma 1, the
maximum recursion depth is $O(\log|V|)$. Therefore, the size of the starting
vertex set is bounded by $O(|V_{0}|+p\cdot\log|V|)$.

###  VII-C Proof of Lemma 3

During each recursive call of the ConstructGraph function (except for the base
case), with a starting set of size $k$, $(k+p)\cdot p$ edges are added to the
returned list. By Lemma 2, $k=O(|V_{0}|+p\cdot\log|V|)$. For each edge, we add
two public vertices that are calculated without using private data and a
shortest distance. Since the $\ell_{1}$ sensitivity of each shortest distance
is 1, returning all $(k+p)\cdot p$ edges has an $\ell_{1}$ sensitivity of
$O(p\cdot(|V_{0}|+p)+p^{2}\cdot\log|V|)$, which is $O((|V_{0}|+p)\cdot
p\cdot\log|V|)$.

In each recursive call, we call some graphs for the next level which are edge-
disjoint. So at each recursion depth level, the graphs in each call are edge-
disjoint from one another, so the $\ell_{1}$ sensitivity of the result at each
recursion depth remains $O((|V_{0}|+p)\cdot p\cdot\log|V|)$. At the last
recursion depth, the number of vertices in the graph is less than $6p^{2}$ and
we return all-pairs shortest distances, so the $\ell_{1}$ sensitivity at this
depth level is $O(p^{2})$. On the other hand, by Lemma 1, there are at most
$O(\log|V|)$ recursion depth levels. Therefore, the $\ell_{1}$ sensitivity of
$f$ is $O((|V_{0}|+p)\cdot p\cdot\log^{2}|V|+p^{2})$.

###  VII-D Proof of Lemma 4

In algorithm 2, the weights of all added edges are the weights of some path in
$G$, so $d_{G,w}(v,u)\leq d_{G^{\prime},w^{\prime}}^{l}(v,u)$ for all $v,u\in
V$ and $l\in[|V|]$.
We will use induction on $|V|$ to prove we have:

$d_{G^{\prime},w^{\prime}}^{t}(v,u)\leq d_{G,w}(v,u)$ (1)

for $t=\max(2,\log_{1.5}|V|)$ and for all $v\in V_{0}\cup S$ and $u\in V$. If
$|V|\leq 6(p+1)$, then, $w^{\prime}(v,u)=d_{w}(v,u)$ which concludes the
result for this case.

Now assume that the claim holds for graphs of tree-width at most $p$ and fewer
vertices than $n$. Consider a weighted graph $G=(V,E)$ with weight function
$w:E\to\mathbb{R}^{+}$ and $|V|=n$. For any $v\in V_{0}\cup S$ and $u\in V$,
let P be $v=v_{0},v_{1},\ldots,v_{t}=u$ shortest path in $G$. If $u\in S$, we
have $d_{G^{\prime},w^{\prime}}^{1}(v,u)=w(P)$ which makes the result trivial.
Otherwise, if $u\in G\setminus S$, let $C_{1},\ldots,C_{l}$ be the connected
components of $G\setminus S$ and let $U_{1},\ldots U_{t}$ be the subgraphs
that are constructed on line 17 using the sets $C_{i}$. Also define the sets
$V_{i}$, weight functions $w_{i}$, and tree decompositions $T_{i}$ following
the algorithm. Thus there exists an index $i\in[l]$ such that $u\in C_{i}$.
Let graph $G_{i}$ with weight function $w_{i}$ be the return of
$\textsc{ConstructGraph}(U_{i},w_{i},T_{i},V_{i})$.

If the path $P$ is completely contained in $U_{i}$, according to induction
hypothesis and since $|V(U_{i})|\leq n$, 1 holds for $G_{i}$ and weight
$w_{i}$. Since this graph a subgraph of $G^{\prime}$ and all edge weights of
$G^{\prime}$ is less than edge weights of $G_{i}$, we can conclude the result
in this case. Otherwise, if $P$ is not in fully on $U_{i}$, then, since
$C_{i}\subseteq U_{i}$, $P$ is not completely contained in $C_{i}$. Because
$\\{C_{1},\ldots,C_{t}\\}$ are the connected components of $G\setminus S$,
thus there exists an index $j\in[t]$ such that the vertex $v_{j}$ lies in $S$.
Without loss of generality we can assume that $j$ is the largest index such
that vertex $v_{j}$ lies in $S$. Then, the subpath $P^{\prime}$ consisting of
vertices $v_{j},v_{j+1},\ldots,v_{t}$ lies entirely within $U_{i}$. The
induction hypothesis implies that
$d_{G_{i},w_{i}}^{\max(2,\log_{1.5}|V_{i}|)}(v_{j},v_{t})\leq w(P^{\prime})$.

Because $n>6(p+1)$, we have $|{V_{i}}\leq n/1.5$. Therefore, we have
$\log_{1.5}|V_{i}|\leq\log_{1.5}|V|-1.$

For the last step note that because all edge weights in $G^{\prime}$ is less
than or equal to those in $G_{i}$ and $G_{i}$ is a subgraph of $G^{\prime}$,
we have $d_{G^{\prime},w^{\prime}}^{\log_{1.5}(|V|)-1}(v_{j},v_{t})\leq
w(P^{\prime})$. Since $v_{j}\in S$, there is an edge between $v_{0}$ and
$v_{j}$ in $G^{\prime}$ with weight $d_{G,w}(v_{0},v_{j})=w(v_{0},v_{1},\ldots
v_{j})$. Thus for $l=\log_{1.5}(|V|)$, we have
$d_{G^{\prime},w^{\prime}}^{l}(v_{0},v_{k})\leq w(v_{0},v_{1},\ldots
v_{j})+w(v_{j},v_{j+1},\ldots v_{t})=w(P)$. Because $n>6(p+1)$, thus
$\log_{1.5}(|V|)>2$, so the claim is true and thus, the lemma is true.

###  VII-E Proof of Lemma 5

We prove the lemma by induction. If $|V|\leq 6(p+1)$, the result follows
trivially. Now assume that the result holds true for all graphs of tree-width
at most $p$ and less than $n$ vertices. Let $G$ be a graph with $n$ vertices
with weight $w:E\to\mathbb{R}^{+}$ and tree-width at most $p$ and $T$ its
corresponding tree decomposition. Let $v,u\in V$ be two arbitrary vertices and
let path $P=v=v_{0},v_{1},\ldots v_{t}=u$ be the shortest path between $v$ and
$u$ in $G$ with weight function $w$. If there exists some
$i\in\\{0,1,\ldots,t\\}$ such that $v_{i}\in S$, then, Lemma 4 implies that
$d_{G,w}(v,v_{i})=d_{G^{\prime},w^{\prime}}^{\max(2,\log_{1.5}|V|)}(v,v_{i})$
and
$d_{G,w}(v_{i},u)=d_{G^{\prime},w^{\prime}}^{\max(2,\log_{1.5}|V|)}(v_{i},u)$.
Since $v_{i}$ is on the shortest path between $v$ and $u$, we have
$d_{G,w}(v,u)=d_{G,w}(v,v_{i})+d_{G,w}(v_{i},u)$. We also can deduce that
$d_{G^{\prime},w^{\prime}}^{2\cdot\max(2,\log_{1.5}|V|)}(v,u)\leq
d_{G^{\prime},w^{\prime}}^{\max(2,\log_{1.5}|V|)}(v,v_{i})+d_{G^{\prime},w^{\prime}}^{\max(2,\log_{1.5}|V|)}(v_{i},u)$
which implies that
$d_{G^{\prime},w^{\prime}}^{2\cdot\max(2,\log_{1.5}|V|)}(v,u)\leq
d_{G,w}(v,u)$. In proof of Lemma 4, we also showed that
$d_{G^{\prime},w^{\prime}}^{2\cdot\max(2,\log_{1.5}|V|)}(v,u)\geq
d_{G,w}(v,u)$ so the result implies in this case. Otherwise assume that there
is no $i$ such that $v_{i}\in S$. Then, path $P$ is completely contained on
one of connected components of $G\setminus S$ which implies the result by
induction hypothesis.

###  VII-F Proof of Lemma 6

The algorithm consists of two steps. At first, it runs the
$\textsc{ComputeEdges}(\cdot)$ function and then constructs the graph. The
second step runs a for loop on every item of the result of the first step, so
if the time complexity of the first stage be $T(|V|)$, the time complexity of
the second stage is $O(T(|V|)+|V|^{2})$, $O(|V|^{2})$ for initializing
$w^{\prime}$ and $O(T(|V|)$ for iterating $R$. Now, we prove that the
$T(|V|)=O(|V^{3}|\log|V|)$. The ComputeEdges function is a recursive function.
Lemma 1 shows that the depth of it is $O(\log|V|)$. The recursion call of each
instance of the function is based on connected components created when
removing a bag from input, thus, in each depth-level of recursion call, at
most $|V|$ instances of the function can be executed simultaneously. If
$|V|\leq 6(p+1)$, the running time of function is $O(|V|^{2})$. Otherwise,
computing $S$ and constructing $H_{i}$s, $V_{i}^{\prime}$s and $T_{i}$s also
has $O(|V|^{2})$ time complexity. Thus, the time complexity of each instance
of ComputeEdges without recursion calls is $O(|V|^{2})$.

Thus, the time complexity of ComputeEdges on input graph $G=(V,E)$ is
$O(|V|^{2}\cdot|V|\cdot\log|V|)=O(|V|^{3}\log|V|)$ and the lemma is proved.