# Multi-Radical Lipkin-Meshkov-Glick Model for Avian Navigation

Jia-Yi Wu  Xin-Yuan Hu  Hai-Yuan Zhu  Ru-Qiong Deng  Qing Ai
<EMAIL_ADDRESS>http://quanphys.bnu.edu.cn Department of Physics, Applied
Optics Beijing Area Major Laboratory, Beijing Normal University, Beijing
100875, China

###### Abstract

The mechanism of avian navigation is an important question for global
scientists. One of the most famous candidates is the radical pair mechanism
(RPM), which shows that avian navigation is achieved by detecting the amount
of products from chemical reactions, which exhibit different properties for
singlet and triplet spin states. Based on the theory, we explore the amount of
the the singlet recombination product by changing the coupling strength and
direction of the magnetic field. The radical pair in our model is coupled with
a Lipkin-Meshkov-Glick (LMG) bath, which proposes attractive results at
quantum phase transition (QPT) point, especially when the magnetic field is
parallel with the original direction of the pair. We find weakest navigation
ability in QPT point according to one of our proposing methods. And we find
invariant subspace in our Hamiltonian when the magnetic field is vertical to
the plane of the radical pair and the bath, which will greatly speed up our
calculation. Our results could help the exploration of the design principle of
artificial avian navigation.

††preprint: AIP/123-QED

##  I Introduction

In the seminal book, What’s Life?, Schrödigner presented the idea that
physical laws in macroscale is decided by statistical behaviors in microscale
Schrödigner (1944). Ever since then, physical mechanisms have been applied to
explain various physiological processes in living beings, e.g. coherent energy
transfer in natural photosynthesis Lambert  _et al._ (2013); Cao  _et al._
(2020); Tao  _et al._ (2020); del Rey  _et al._ (2013); Ai  _et al._ (2013a);
Collini  _et al._ (2010), a quantum model for protein folding Mao, Lu, and Li
(2021), and the radical-pair mechanism for migrating birds Ritz, Adem, and
Schulten (2000); Solov’yov, Chandler, and Schulten (2008).

Among the 50 species, which include insects, crustaceans, fish, amphibians,
reptiles, mammals and birds, and utilize geomagnetic field for navigation,
migratory birds have been intensively studied Mouritsen (2018). In the
radical-pair hypothesis, the radical pair in the cryptochrome is activated by
photons. The anisotropic magnetic field due to the nearby nuclear spins can
result in the reaction yield which is sensitive to orientation of the
geomagnetic field. The cryptochrome is located at the avian retina and the
visual modulation patterns can be influenced by the geomagnetic field through
the above spin-selective chemical reaction Ritz, Adem, and Schulten (2000);
Solov’yov, Chandler, and Schulten (2008). In a model system,
carotenoid–porphyrin–fullerene, the radical pair is photochemically activated.
When the probe light is not perpendicular to the simulated geomagnetic field,
the lifetime of the radical pair in chemical reaction in vitro shows clear
dependence on the orientation of the magnetic field Maeda  _et al._ (2008). Xu
_et al._ (2021) Such kind of spin-dependent chemical reactions can be well
described by the Holstein model which is generalized to naturally include spin
degree of freedom of the radicals Yang, Ai, and Sun (2012). Inspired by these
interesting discoveries, bionic quantum coherent devices for navigation have
been proposed, e.g. criticality-enhanced quantum compass Cai  _et al._ (2012).

We notice that nuclear spins play a crucial role in the proposed radical-pair
mechanism, because the homogeneous geomagnetic field can not induce the
transition between the initial singlet state and the triplet states Ritz,
Adem, and Schulten (2000); Yang, Ai, and Sun (2012). Recent studies have
suggested that the hyperfine interaction is not necessary for the
magnetoreception, and dipolar interactions between radicals beyond the
radical-pair model can also assist navigation by the magnetic-field-sensitive
chemical reactions Keens, Bedkihal, and Kattnig (2018). Researchers also find
that non-uniform magnetic field can also be used to radical pair mechanism so
as to navigate Cai (2011). It is also shown that the QPT in the nuclear spins
described by the Ising model in the transverse field can improve the
sensitivity for navigation Cai  _et al._ (2012). Considering the above
discoveries, it is quite natural to ask: Can we use the QPT in the multi-
radical model to optimize navigation? Can the QPT beyond the Ising model in
the transverse field be used, e.g. the Lipkin-Meshkov-Glick (LMG) model?

The LMG model was proposed to offer exact suctions or solutions with ordinary
perturbation to quantum many-body problems Lipkin, Meshkov, and Glick (1965);
Meshkov, Glick, and Lipkin (1965); Glick, Lipkin, and Meshkov (1965). It
describes a system with $N$ fermions distributed on two $N$-fold degenerated
energy levels. Different from the Ising model in the transverse field or $XY$
model which only consider the nearest-neighbor interactions Garnerone  _et
al._ (2009); Invernizzi  _et al._ (2008); Ai  _et al._ (2008), the LMG model
take all interactions of the spins into consideration based on the mean-field
theory Salvatori, Mandarino, and Paris (2014); Quan, Wang, and Sun (2007).
Analytical methods have been use to obtain eigen values and corresponding
eigenfunctions for LMG model Pan and Draayer (1999), or the low-energy
spectrum and associated generator matrix elements in the eigen energy basis of
LMG Rosensteel, Rowe, and Ho (2007). An interesting result that the QPT also
exists in the LMG model Quan, Wang, and Sun (2007); Castaños  _et al._ (2006),
inspires us to improve the sensitivity of magnetic detection by the QPT in the
multi-radical which is described by the LMG model.

This paper is organized as follows: In Section II, we propose two new model to
explain avian navigation based on the LMG model with many radicals. In Section
A, we are going to explore the vertical situation. At last, the main
conclusions are summarized in Section IV and we also discuss the possibilities
of applications of our discoveries.

##  II Multi-Radical Models for Avian Navigation

Figure 1: Schematic of the radical-pair system interacting a multi-radical
bath. The red spheres represent the radical pair, while the blue spheres are
the radicals in the bath described by the LMG model. The angle between the
geomagnetic field and the normal of the plane is $\theta$.

As shown in Fig. 1, we consider a radical pair system coupling to $N$ radicals
which are described by the LMG model. The geomagnetic field is applied along
the direction $\cos\theta\vec{e}_{z}+\sin\theta\vec{e}_{x}$. The Hamiltonian
of the total system reads

$\displaystyle H=$
$\displaystyle-\frac{\lambda}{N}\sum_{i<j}^{N}\left(\sigma_{i}^{x}\sigma_{j}^{x}+\sigma_{i}^{y}\sigma_{j}^{y}\right)-\lambda^{\prime}\left(\sigma_{a}^{x}\sigma_{b}^{x}+\sigma_{a}^{y}\sigma_{b}^{y}\right)$
(1)
$\displaystyle-{\lambda}_{1}\sum_{i=1}^{N}\left[\sigma_{i}^{x}\left(\sigma_{a}^{x}+\sigma_{b}^{x}\right)+\sigma_{i}^{y}\left(\sigma_{a}^{y}+\sigma_{b}^{y}\right)\right]$
$\displaystyle-\sum_{i=1}^{N}\left(\cos{\theta}\sigma_{i}^{z}+\sin{\theta}\sigma_{i}^{x}\right)$
$\displaystyle-\cos{\theta}\left(\sigma_{a}^{z}+\sigma_{b}^{z}\right)-\sin{\theta}\left(\sigma_{a}^{x}+\sigma_{b}^{x}\right),$

where $\sigma_{i}^{\alpha}$ ($i=1,2,...,N,~{}\alpha=x,y,z$) represent the
Pauli matrices of the radical bath, $\sigma_{a}^{\alpha}$ and
$\sigma_{b}^{\alpha}$ are the Pauli matrices of the radical pair. $\lambda/N$
is the interaction between the radicals in the bath, which is inversely
proportional to the total number of the spins according to the mean field
theory. Here, we assume that the coupling strength between the radical pair
system and the bath, $\lambda_{1}$, can be approximated to the interaction of
bath, $\lambda/N$. $\lambda^{\prime}$ is the interaction between the two
radicals, which is $\lambda/2$ according to the LMG model. Notice that when
the direction of the geomagnetic field is reversed, i.e.,
$\theta\rightarrow\pi-\theta$, avian navigation will not be influenced
Wiltschko and Wiltschko (1972); Ritz, Adem, and Schulten (2000).

We define the collective spin operators for the bath and radical as,
$J_{N}^{\alpha}=\frac{1}{2}\sum_{i=1}^{N}\sigma_{i}^{\alpha}$ and
$S^{\alpha}=\frac{1}{2}\left(\sigma_{a}^{\alpha}+\sigma_{b}^{\alpha}\right)$
($x,y,z$). Correspondingly, the raising and lowering operators are given as
$J_{N}^{\pm}=J_{N}^{x}{\pm}\mathrm{i}J_{N}^{y}$ and
$S^{\pm}=S^{x}{\pm}\mathrm{i}S^{y}$. Therefore, the Hamiltonian can be
transformed into the Dicke representation as

$\displaystyle H=$
$\displaystyle-\frac{2\lambda}{N}\left[J_{N}^{2}-(J_{N}^{z})^{2}-\frac{N}{2}\right]-\left[S^{2}-(S^{z})^{2}-1\right]$
(2)
$\displaystyle-\frac{2\lambda}{N}\left(J_{N}^{-}S^{+}+J_{N}^{+}S^{-}\right)-2\cos{\theta}\left(J_{N}^{z}+S^{z}\right)$
$\displaystyle-2\sin{\theta}\left(J_{N}^{x}+S^{x}\right),$

where
$J_{N}^{2}=\left(J_{N}^{x}\right)^{2}+\left(J_{N}^{y}\right)^{2}+\left(J_{N}^{z}\right)^{2}$
and $S^{2}=S_{x}^{2}+S_{y}^{2}+S_{z}^{2}$ characterize the total angular
momentum operator of the bath and the radical pair, respectively.

In avian navigation, the spin-dependent chemical reaction only occurs in
radical-pair system and depletes the radical pair to generate different
chemical products according to their spin states, i.e., singlet or triplet
state Ritz, Adem, and Schulten (2000); Yang, Ai, and Sun (2012). For the sake
of simplicity, we assume that the singlet and triplet states have the same
recombination constant $k$, and neglect the quantum jumps in the system. The
time evolution of the density matrix of the total system is determined by
Ritz, Adem, and Schulten (2000)

$\displaystyle\frac{\mathrm{d}\hat{\rho}\left(t\right)}{\mathrm{d}t}=-\mathrm{i}\left[H,\hat{\rho}\left(t\right)\right]-k\hat{\rho}\left(t\right),$
(3)

where $k$ is the recombination rate. The quantum yield of the singlet state in
the chemical reaction can be calculated by using the projection operator
$\hat{P}_{\mathrm{S}}^{\left(ab\right)}=|0,0\rangle_{a}~{}_{b}\langle 0,0|$ to
the singlet state as

$\displaystyle{\phi}_{\mathrm{S}}=k\int_{0}^{\infty}\mathrm{d}\tau\textrm{Tr}[\hat{P}_{\mathrm{S}}^{\left(ab\right)}\hat{\rho}\left(\tau\right)].$
(4)

Generally, the open quantum dynamics of the spin-dependent chemical reaction
should be described by the quantum master equation Kominis (2009). In Eq. (3),
the quantum jump terms have been omitted and may lead to possible deviation
from the experimental observation at low and high magnetic field due to
quantum Zeno effect Kominis (2009); Ai  _et al._ (2013b). Moveover, the exact
quantum dynamics of the open quantum system can be given by the hierarchical
equation of motion Ishizaki and Fleming (2009). Recently, it has been
theoretically proposed and experimentally demonstrated that the exact solution
can be exponentially accelerated by a quantum simulation approach Wang  _et
al._ (2018); Zhang  _et al._ (2021).

Assuming that initially the radical-pair system is in the singlet state, and
the bath is in the thermal state $\sum_{M}|N/2,M\rangle\langle N/2,M|/(N+1)$,
the initial density matrix is

$\displaystyle\hat{\rho}\left(t=0\right)=\frac{1}{N+1}\sum_{M=-N/2}^{N/2}|N/2,M\rangle\langle
N/2,M|\otimes\hat{P}_{\mathrm{S}}^{\left(ab\right)}.$ (5)

Here, we use Dicke states $\left|N/2,M\right\rangle$ ($M=-N/2,\cdots,N/2)$ for
the bath, and $|0,0\rangle,~{}|1,0\rangle,~{}|1,1\rangle,~{}|1,-1\rangle$ for
the radical pair.

It was suggested that birds’ sensory transduction pathway can be effected by
the quantum yield of the chemical reaction involved in radical-pair mechanism,
and different amount of singlet-state quantum yield produces different visual
modulation patterns, enabling birds to distinguish the direction of the
geomagnetic field Ritz, Adem, and Schulten (2000). Therefore, a reasonable
model for avian navigation should have remarkable change in the quantum yield
with respect to the variation of strength and direction of the magnetic field,
so as to have a distinct sense of direction.

However, the quantum yield of this coupled system will remain a constant as
the magnitude and direction of the magnetic field changes. This result can be
expected by analysing the Hamiltonian (2). The operators of the radical pairs,
$S$, $S^{z}$ and $S^{\pm}$ can not change the total spin number of the radical
pair, making transition between the singlet and triplet states unavailable.
Under this circumstance, no matter which initial state we choose for the
radical bath, these two kinds of spin states will respectively convert to the
corresponding chemical products without effecting each other. Therefore, this
multi-radical LMG model can not be used in the avian navigation. To solve this
problem, we propose two models based on the LMG model for the avian
navigation. The design principle of these two models is to break the symmetry
between radical $a$ and $b$ in the Hamiltonian, in order to induce the
transition between the singlet and triplet states of the radical-pair system.

###  II.1 Absence of Zeeman Effect on Radical $b$

The symmetry of the Hamiltonian can be broken by neglecting Zeeman Effect of
the radical $b$, making the Hamiltonian of the system become

$\displaystyle H_{1}=$
$\displaystyle-\frac{\lambda}{N}\sum_{i<j}^{N}\left(\sigma_{i}^{x}\sigma_{j}^{x}+\sigma_{i}^{y}\sigma_{j}^{y}\right)-\frac{\lambda}{2}\left(\sigma_{a}^{x}\sigma_{b}^{x}+\sigma_{a}^{y}\sigma_{b}^{y}\right)$
$\displaystyle-\frac{\lambda}{N}\sum_{i=1}^{N}\left[\sigma_{i}^{x}\left(\sigma_{a}^{x}+\sigma_{b}^{x}\right)+\sigma_{i}^{y}\left(\sigma_{a}^{y}+\sigma_{b}^{y}\right)\right]$
$\displaystyle-\sum_{i=1}^{N}\left(\cos{\theta}\sigma_{i}^{z}+\sin{\theta}\sigma_{i}^{x}\right)-\left(\cos{\theta}\sigma_{a}^{z}+\sin{\theta}\sigma_{a}^{x}\right).$
(6)

To figure out the impact of this Hamiltonian on the quantum states, we
transform the operators of single spin to those of multiple spins. Therefore,
the Hamiltonian can be finally transformed into

$\displaystyle H_{1}=$
$\displaystyle-\frac{2\lambda}{N}\left[J_{N}^{2}-\left(J_{N}^{z}\right)^{2}-\frac{N}{2}\right]-\lambda\left[S^{2}-\left(S^{z}\right)^{2}-1\right]$
(7)
$\displaystyle-\frac{2\lambda}{N}\left(J_{N}^{-}S^{+}+J_{N}^{+}S^{-}\right)-2\cos{\theta}\left(J_{N}^{z}+S_{a}^{z}\right)$
$\displaystyle-2\sin{\theta}\left(J_{N}^{x}+S_{a}^{x}\right).$

Since there’s no invariant subspace in the Hamiltonian with dimension
$4(N+1)$. After careful calculation, the Hamiltonian is given as

$\displaystyle H_{1}=$ (8)
$\displaystyle\begin{bmatrix}\Lambda_{1}(-\frac{N}{2},\theta)&R_{1}^{\dagger}(-\frac{N}{2},\theta)&\\\
R_{1}(-\frac{N}{2},\theta)&\Lambda_{1}(-\frac{N}{2}+1,\theta)&\\\
&R_{1}(-\frac{N}{2}+1,\theta)&\ddots\\\
&&\ddots&R_{1}^{\dagger}(\frac{N}{2}-2,\theta)\\\
&&&\Lambda_{1}(\frac{N}{2}-1,\theta)&R_{1}^{\dagger}(\frac{N}{2}-1,\theta)\\\
&&&R_{1}(\frac{N}{2}-1,\theta)&\Lambda_{1}(\frac{N}{2},\theta)\end{bmatrix}$

where $\Lambda_{1}(M)$ are the diagonal blocks and $R_{1}(M)$ are the
nondiagonal blocks. The details are shown in Appendix B. For a specific case
with $\theta=0$, the Hamiltonian $H$ is simplified as a block-diagonal matrix,
cf. Appendix A.

###  II.2 Absence of Spin $b$’s Interaction with Bath

We can also break the conservation of total spin number of the radical pair by
neglecting the interaction between the bath and the radical $b$. Thus, the
Hamiltonian becomes

$\displaystyle H_{2}=$
$\displaystyle-\frac{\lambda}{N}\sum_{i<j}^{N}\left(\sigma_{i}^{x}\sigma_{j}^{x}+\sigma_{i}^{y}\sigma_{j}^{y}\right)-\frac{\lambda}{2}\left(\sigma_{a}^{x}\sigma_{b}^{x}+\sigma_{a}^{y}\sigma_{b}^{y}\right)$
(9)
$\displaystyle-\frac{\lambda}{N}\sum_{i=1}^{N}\left(\sigma_{i}^{x}\sigma_{a}^{x}+\sigma_{i}^{y}\sigma_{a}^{y}\right)-\sum_{i=1}^{N}\left(\cos{\theta}\sigma_{i}^{z}+\sin{\theta}\sigma_{i}^{x}\right)$
$\displaystyle-\cos{\theta}\left(\sigma_{a}^{z}+\sigma_{b}^{z}\right)-\sin{\theta}\left(\sigma_{a}^{x}+\sigma_{b}^{x}\right).$

After transformed into the Dicke representation, it reads

$\displaystyle H_{2}=$
$\displaystyle-\frac{2\lambda}{N}\left[J_{N}^{2}-(J_{N}^{z})^{2}-\frac{N}{2}\right]-\lambda\left[S^{2}-(S^{z})^{2}-1\right]$
(10)
$\displaystyle-\frac{2\lambda}{N}\left(J_{N}^{-}S_{a}^{+}+J_{N}^{+}S_{a}^{-}\right)-2\cos{\theta}\left(J_{N}^{z}+S^{z}\right)$
$\displaystyle-2\sin{\theta}\left(J_{N}^{x}+S^{x}\right),$

where $S_{a}=\frac{1}{2}\sigma_{a}$. This system can be realized if the
radical $b$ is further away from the bath than radical $a$, since the dipole-
dipole interaction between the radicals decays with $1/r^{3}$, making the
interaction sensitive to the distance. Considering the invariant subspaces in
Eq. (7), we can also write this Hamiltonian as

$\displaystyle H_{2}=$ (11)
$\displaystyle\begin{bmatrix}\Lambda_{2}(-\frac{N}{2},\theta)&R_{2}^{\dagger}(-\frac{N}{2},\theta)&\\\
R_{2}(-\frac{N}{2},\theta)&\Lambda_{2}(-\frac{N}{2}+1,\theta)&\\\
&R_{2}(-\frac{N}{2}+1,\theta)&\ddots\\\
&&\ddots&R_{2}^{\dagger}(\frac{N}{2}-2,\theta)\\\
&&&\Lambda_{2}(\frac{N}{2}-1,\theta)&R_{2}^{\dagger}(\frac{N}{2}-1,\theta)\\\
&&&R_{2}(\frac{N}{2}-1,\theta)&\Lambda_{2}(\frac{N}{2},\theta)\end{bmatrix}$

where the explicit expressions of $\Lambda_{2}$ and $R_{2}$ are given in
Appendix B.

##  III Numerical Simulation and Discussion

In Fig. 2, our calculation shows that in the model for Eq. (9), the quantum
yield ${\phi}_{\mathrm{S}}$ of the singlet state will change remarkably with
respect to both the direction and magnitude of the magnetic field, which
covers a range from $0.8$ to $0.93$, making it feasible for avian navigation.
We notice that the QPT takes place at $\lambda=1$, at which the quantum yield
spans a wider range as $\theta$ changes. This implies that the sensitivity of
avian navigation can be enhanced by the QPT. Furthermore, the QPT occurs only
in the thermodynamic limit, i.e., $N\rightarrow\infty$. We also investigate
the dependence of ${\phi}_{\mathrm{S}}$ on $N$ in Fig. 3. As shown, the line
will converge as $N$ increases. And the difference between the lines for
$N=50$ and $N=100$ is small. Therefore, in Fig. 2, we demonstrate the result
for $N=50$.

Figure 2: Quantum yield ${\phi}_{\mathrm{S}}$ varies with respect to the
magnetic field’s direction $\theta$ and strength $\lambda$ for $N=50$,
$k=0.7~{}\mu$s-1 based on Eq. (9). The color in the figure represents the
magnitude of production rate ${\phi}_{\mathrm{S}}$. Figure 3: Quantum yield
${\phi}_{\mathrm{S}}$ varies with respect to the magnetic field’s direction
$\theta$ with $\lambda=1$ and $k=0.7~{}\mu$s-1 for $N=5,10,25,50,100$, based
on Eq. (9). The quantum yield converges as $N$ increases. Figure 4: (a)
Quantum yield ${\phi}_{\mathrm{S}}$ varies with respect to the magnetic
field’s strength $\lambda$ and recombination rate $k$ for $N=50$, based on Eq.
(6). (b) The sensitivity of avian navigation at different sets of $\lambda$
and $k$.

Hereafter, we will investigate the avian navigation for Eq. (6). Figure 4(a)
shows the dependence of $\phi_{\mathrm{S}}$ on $\lambda$ and $k$ for
$\theta=0$ when there exist invariant subspaces, cf. Appendix B. At the first
glance, there is a wide flat region in the outer parameter space, which is
close to unity. When $k$ approaches infinity as $\lambda$ stays constant,
there is no probability for the initial singlet state to convert to the
triplet states and thus $\phi_{\mathrm{S}}\simeq 1$ because the chemical
reaction is too fast. On the contrary, when $k$ is close to 0, the radical
pair will have sufficient time to evolve. Notice that for $\theta=0$ Eq. (8)
will become a block-diagonal matrix, cf. Appendix B. As an approximation, we
assume the diagonal terms to be identical and $\Lambda_{1}(M)$ in Eq. (8) can
be written as

$\Lambda_{1}(M)=\begin{bmatrix}\alpha&\lambda y(M)&0&0\\\ \lambda
y(M)&\alpha&\lambda x(M)&-1\\\ 0&\lambda x(M)&\alpha&0\\\
0&-1&0&\alpha\end{bmatrix},$ (12)

whose eigenvectors are respectively $(1/\lambda y,0,0,1)^{T}$,
$(-x/y,0,1,0)^{T}$, $(-y\lambda,w,-x\lambda,1)^{T}$, and
$(-y\lambda,-w,-x\lambda,1)^{T}$, with $w=\sqrt{1+\lambda^{2}(x^{2}+y^{2})}$.
As $\lambda$ goes to infinity, the first eigenvector approaches
$(0,0,0,1)^{T}$, which is exactly the singlet state. This implies that the
singlet state forms a invariant subspace and there is no conversion between
the singlet and triplet states. Hence the quantum yield is almost 1 at
$k\rightarrow 0$ and $\lambda\rightarrow\infty$, which leads nearly-unity
plateau in the top left part of Fig. 4(a). However, as $\lambda$ vanishes, the
last two eigenvectors become $(0,1,0,1)^{T}$ and $(0,-1,0,1)^{T}$,
respectively. In this case, each of them make up 50% of the initial state. As
$k>\lambda\rightarrow 0$, the radical pair has sufficient time to oscillate
between these two states, and thus there is $\phi_{\mathrm{S}}\simeq 0.5$ at
the lower triangle of the bottom left of Fig. 5(a). In order to check the
validity of the above analysis, we numerically calculate the quantum yield as
a function of chemical-reaction rate for $\lambda=0$ in Fig. 5(a). As $k$
decreases, $\phi_{\mathrm{S}}$ dramatically drops from unity to half around
$k=1~{}\mu$s-1.

Figure 5: (a) The behavior of quantum yield $\phi_{\mathrm{S}}$ when $k$ goes
to 0. This figure is obtained when $\lambda=0$ and $N=50$. As $k$ approaches
0, $\phi_{\mathrm{S}}$ approaches 0.5. (b) Quantum yield varies with the angle
of the magnetic field $\theta$ at different $N$’s. Here we set
$k=0.07\,\mathrm{\mu s}^{-1}$ and $\lambda=1$, which corresponds to the solid
blue line in Fig. 4(b).

In Fig. 4(b), we analyse the sensitivity for Eq. (6) for four different sets
of $\lambda$ and $k$. When the bath is far away from the QPT, e.g.
$\lambda=0.1$, the quantum yield nearly stays constant for different
$\theta$’s. When the bath is at the critical point, we significantly decrease
$k$ from $7~{}\mu$s-1 to $0.07~{}\mu$s-1. When the chemical reaction happens
too fast, the quantum yield still remains unchanged as the direction of
magnetic field varies. When $k$ decreases, the quantum yield becomes lower
than unity and shows its dependence on the direction. Thus, it improves
sensitivity of the avian navigation.

According to Fig. 4(b), it seems that the QPT assists the avian navigation. In
general, the true QPT occurs in the thermodynamic limit. As a result, we
further investigate the sensitivity as $N$ is enlarged. When we constantly
increase $N$, the results seem to asymptotically approach a limit, which
implies our calculation is reliable. And the oscillation around
$\theta\in[0.3\pi,0.5\pi]$ becomes more and more profound. Thus, we may safely
arrive at the conclusion that the QPT can sensitively support the avian
navigation.

##  IV Conclusion

In this paper, inspired by the multi-radical model Keens, Bedkihal, and
Kattnig (2018), we propose three multi-radical models with the radical bath
described by the LMG model for artificial avian navigation. When the total
system including the central radical pair and bath radicals are fully
described by the LMG model, it can not be effectively used for navigation as
it will not induce the coherent transition between the singlet and triplet
states. However, if one of the central radical pair does not interact with the
magnetic field or the radical bath, the capacity of navigation emerges. We
further show that the sensitivity of navigation can be enhanced around the
critical point and can be further improved as the number of radicals
increases.

###### Acknowledgements.

This work is supported by Beijing Natural Science Foundation under Grant No.
1202017 and the National Natural Science Foundation of China under Grant Nos.
11674033, 11505007.

##  Appendix A Magnetic Field Parallel to $z$-axis

In Section II, we have discussed how the quantum yield of singlet state is
influenced by the direction of the magnetic field. We use a
$4(N+1)$-dimensional Hilbert space to calculate the quantum yield. However,
when the magnetic field is parallel to $z$-axis and thus $\theta=0$, $H_{1}$
and $H_{2}$ become respectively

$\displaystyle H_{1}=$
$\displaystyle-\frac{2\lambda}{N}\left[J_{N}^{2}-\left(J_{N}^{z}\right)^{2}-N\right]-2\lambda\left[S^{2}-(S^{z})^{2}-1\right]$
(13)
$\displaystyle-\frac{2\lambda}{N}\left(J_{N}^{-}S^{+}+J_{N}^{+}S^{-}\right)-2\left(J_{N}^{z}+S_{a}^{z}\right),$

$\displaystyle H_{2}=$
$\displaystyle-\frac{2\lambda}{N}\left[J_{N}^{2}-(J_{N}^{z})^{2}-\frac{N}{2}\right]-2\lambda\left[S^{2}-(S^{z})^{2}-1\right]$
(14)
$\displaystyle-\frac{2\lambda}{N}\left(J_{N}^{-}S_{a}^{+}+J_{N}^{+}S_{a}^{-}\right)-2\left(J_{N}^{z}+S^{z}\right).$

As shown in Appendix B, we find that there exist invariant subspaces for both
of these two models, which are spanned by

$\displaystyle\mathcal{H}=\\{$
$\displaystyle\left|N/2,M+1\right\rangle\left|1,-1\right\rangle,\left|N/2,M\right\rangle\left|1,0\right\rangle,$
(15)
$\displaystyle\left|N/2,M-1\right\rangle\left|1,1\right\rangle,\left|N/2,M\right\rangle\left|0,0\right\rangle\\}.$

Due to the existence of invariant subspaces, our calculations of the quantum
yield will be significantly simplified. Furthermore, by numerical simulations
in Fig. 6, we show that the chemical yield of singlet state coincide with each
other, and thus these two methods are the equivalent.

Figure 6: Comparison of the quantum yield ${\phi}_{\mathrm{S}}$ for using
invariant subspaces and the whole space based on Eq. (14) when $N=100$,
$k=0.7\,\mathrm{{\mu}s}^{-1}$, $\theta=0$ . The black solid line represents
the production rate based on invariant subspaces, and the blue dashed line
represents the production rate based on the whole space.

##  Appendix B Invariant Subspace

In this appendix, we will show that there exist invariant subspaces in the
Hilbert space of Hamiltonians (13) and (14) for the vertical situation, namely
$\theta=0$. We can prove that the total angular momentum along $z$-axis, i.e.,
$J_{N}^{z}+S^{z}$, is conserved for both cases when $\theta=0$, by calculating
the commutator with the corresponding Hamiltonian as

$\displaystyle\left[H_{1},J_{N}^{z}+S^{z}\right]=$
$\displaystyle-\left[2\sin\theta\left(J_{N}^{x}+S_{a}^{x}\right),\left(J_{N}^{z}+S^{z}\right)\right]$
(16) $\displaystyle=$
$\displaystyle\mathrm{i}2\sin\theta\left(J_{N}^{y}+S_{a}^{y}\right),$

$\displaystyle\left[H_{2},J_{N}^{z}+S^{z}\right]=$
$\displaystyle-\left[2\sin\theta\left(J_{N}^{x}+S^{x}\right),\left(J_{N}^{z}+S^{z}\right)\right]$
(17) $\displaystyle=$
$\displaystyle\mathrm{i}2\sin\theta\left(J_{N}^{y}+S^{y}\right).$

If $\theta\neq 0$, the total angular momentum is not conserved along $z$-axis.
The Hamiltonian $H_{1}$ can be rewritten as Eq. (8), where

$\begin{aligned} &R_{1}(M)=\\\
&\begin{bmatrix}-\sin\theta\zeta_{M+2}&-\frac{1}{\sqrt{2}}\sin{\theta}&0&-\frac{1}{\sqrt{2}}\sin{\theta}\\\
0&-\sin{\theta}\zeta_{M+1}&-\frac{1}{\sqrt{2}}\sin{\theta}&0\\\
0&0&-\sin{\theta}\zeta_{M}&0\\\
0&0&\frac{1}{\sqrt{2}}\sin{\theta}&-\sin{\theta}\zeta_{M+1}\end{bmatrix}\end{aligned},$
(18) $\begin{aligned} &\Lambda_{1}(M)=\\\
&\begin{bmatrix}d^{(1)}_{M}\left(\theta\right)&-\frac{2\sqrt{2}\lambda}{N}\zeta_{M+1}&0&0\\\
-\frac{2\sqrt{2}\lambda}{N}\zeta_{M+1}&b^{(1)}_{M}\left(\theta\right)&-\frac{2\sqrt{2}\lambda}{N}\zeta_{M}&-\frac{2\lambda}{N}\cos\theta\\\
0&-\frac{2\sqrt{2}\lambda}{N}\zeta_{M}&a^{(1)}_{M}\left(\theta\right)&0\\\
0&-\frac{2\lambda}{N}\cos\theta&0&c^{(1)}_{M}\left(\theta\right)\end{bmatrix}\end{aligned}.$
(19)

Here,

$\displaystyle\zeta_{M}$
$\displaystyle=\sqrt{\left(\frac{N}{2}-M+1\right)\left(\frac{N}{2}+M\right)},$
(20a) $\displaystyle a_{M}^{(1)}\left(\theta\right)$
$\displaystyle=-\frac{2\lambda}{N}\left[\frac{N^{2}}{4}-\left(M-1\right)^{2}\right]-\left(2M-1\right)\cos{\theta},$
(20b) $\displaystyle b_{M}^{(1)}\left(\theta\right)$
$\displaystyle=-\frac{2\lambda}{N}\left(\frac{N^{2}}{4}-M^{2}\right)-\lambda-2M\cos{\theta},$
(20c) $\displaystyle c_{M}^{(1)}\left(\theta\right)$
$\displaystyle=-\frac{2\lambda}{N}\left(\frac{N^{2}}{4}-M^{2}\right)+\lambda-2M\cos{\theta},$
(20d) $\displaystyle d_{M}^{(1)}\left(\theta\right)$
$\displaystyle=-\frac{2\lambda}{N}\left[\frac{N^{2}}{4}-\left(M+1\right)^{2}\right]-\left(2M+1\right)\cos{\theta}.$
(20e)

When the magnetic field is vertical to the plane, i.e., $\theta=0$, the
commutator is $0$ and thus total angular momentum is conserved along $z$-axis.
Therefore, the invariant subspaces in Eq.(15) will appear in those two
Hamiltonians. We can rewrite $H_{1}$ as

$\begin{aligned} H_{1}=\begin{bmatrix}\Lambda_{1}(-\frac{N}{2},0)&&\\\
&\ddots&\\\ &&\Lambda_{1}(\frac{N}{2},0)\end{bmatrix}\end{aligned}.$ (21)

$H_{2}$ is generally given as Eq. (11), where

$\begin{aligned}
R_{2}(M,\theta)=-\begin{bmatrix}\zeta_{M+2}\sin{\theta}&0&0&0\\\
\sqrt{2}\sin{\theta}&\zeta_{M+1}\sin{\theta}&0&0\\\
0&\sqrt{2}\sin{\theta}&\zeta_{M}\sin{\theta}&0\\\
0&0&0&\zeta_{M+1}\sin{\theta}\end{bmatrix}\end{aligned},$ (22)
$\begin{aligned}
\Lambda_{2}(M,\theta)=\begin{bmatrix}d_{M}^{(2)}(\theta)&-\frac{\lambda}{2\sqrt{2}}\zeta_{M+1}&0&-\frac{\lambda}{2\sqrt{2}}\zeta_{M+1}\\\
-\frac{\lambda}{2\sqrt{2}}\zeta_{M+1}&b_{M}^{(2)}(\theta)&0&-\frac{\lambda}{2\sqrt{2}}\zeta_{M}\\\
0&-\frac{\lambda}{2\sqrt{2}}\zeta_{M}&a_{M}^{(2)}(\theta)&\frac{\lambda}{2\sqrt{2}}\zeta_{M}\\\
-\frac{\lambda}{2\sqrt{2}}\zeta_{M+1}&0&\frac{\lambda}{2\sqrt{2}}\zeta_{M}&c_{M}^{(2)}(\theta)\end{bmatrix}\end{aligned}.$
(23)

Here,

$\displaystyle a_{M}^{(2)}(\theta)$
$\displaystyle=a_{M}^{(1)}(\theta)+\cos{\theta},$ (24a) $\displaystyle
b_{M}^{(2)}(\theta)$ $\displaystyle=b_{M}^{(1)}(\theta),$ (24b) $\displaystyle
c_{M}^{(2)}(\theta)$ $\displaystyle=c_{M}^{(1)}(\theta),$ (24c) $\displaystyle
d_{M}^{(2)}(\theta)$ $\displaystyle=d_{M}^{(1)}(\theta)-\cos{\theta}.$ (24d)

When $\theta=0$, Hamiltonian $H_{2}$ can be also written in the block-diagonal
form as

$\begin{aligned} H_{2}=\begin{bmatrix}\Lambda_{2}(-\frac{N}{2},0)&&\\\
&\ddots&\\\ &&\Lambda_{2}(\frac{N}{2},0)\end{bmatrix}\end{aligned}.$ (25)

In the above derivation, we have used the properties of raising and lowering
operators of the bath and radical pair, i.e.,

$\displaystyle
J_{N}^{+}\left|\frac{N}{2},M\right>=\sqrt{\left(\frac{N}{2}-M\right)\left(\frac{N}{2}+M+1\right)}\left|\frac{N}{2},M+1\right>,$
(26a) $\displaystyle
J_{N}^{-}\left|\frac{N}{2},M\right>=\sqrt{\left(\frac{N}{2}+M\right)\left(\frac{N}{2}-M+1\right)}\left|\frac{N}{2},M-1\right>,$
(26b) $\displaystyle
S^{+}\left|0,0\right>=S^{-}\left|0,0\right>=S^{+}\left|1,1\right>=S^{-}\left|1,-1\right>=0.$
(26c)

Notice that $s_{a}^{z}$ can induce the transition between $|0,0\rangle$ and
$|1,0\rangle$, while $|1,\pm 1\rangle$ are the eigen states of $s_{a}^{z}$,
i.e.,

$\displaystyle S_{a}^{z}\left|0,0\right>$
$\displaystyle=S_{a}^{z}\frac{1}{\sqrt{2}}\left(\left|\uparrow\downarrow\right>-\left|\downarrow\uparrow\right>\right)=\frac{1}{2}\left|1,0\right>,$
(27a) $\displaystyle S_{a}^{z}\left|1,0\right>$
$\displaystyle=S_{a}^{z}\frac{1}{\sqrt{2}}\left(\left|\uparrow\downarrow\right>+\left|\downarrow\uparrow\right>\right)=\frac{1}{2}\left|0,0\right>,$
(27b) $\displaystyle S_{a}^{z}\left|1,1\right>$
$\displaystyle=S_{a}^{z}\left|\uparrow\uparrow\right>=\frac{1}{2}\left|1,1\right>,$
(27c) $\displaystyle S_{a}^{z}\left|1,-1\right>$
$\displaystyle=S_{a}^{z}\left|\downarrow\downarrow\right>=-\frac{1}{2}\left|1,-1\right>.$
(27d)

## References

  * Schrödigner (1944) E. Schrödigner,  _What’s Life_ (Cambridge University Press, 1944).
  * Lambert  _et al._ (2013) N. Lambert, Y. N. Chen, Y. C. Cheng, C.-M. Li, G. Y. Chen, and F. Nori, “Quantum biology,” Nat. Phys. 9, 10–18 (2013).
  * Cao  _et al._ (2020) J. Cao, R. J. Cogdell, D. F. Coker, H. G. Duan, J. Hauer, U. Kleinekathöfer, T. L. C. Jansen, T. Mančal, R. J. D. Miller, J. P. Ogilvie, V. I. Prokhorenko, T. Renger, H. S. Tan, R. Tempelaar, M. Thorwart, E. Thyrhaug, S. Westenhoff, and D. Zigmantas, “Quantum biology revisited,” Sci. Adv. 6, eaaz4888 (2020).
  * Tao  _et al._ (2020) M. J. Tao, N. N. Zhang, P. Y. Wen, F. G. Deng, Q. Ai, and G. L. Long, “Coherent and incoherent theories for photosynthetic energy transfer,” Sci. Bull. 65, 318–328 (2020).
  * del Rey  _et al._ (2013) M. del Rey, A. W. Chin, S. F. Huelga, and M. B. Plenio, “Exploiting structured environments for efficient energy transfer: The phonon antenna mechanism,” J. Phys. Chem. Lett 4, 903–907 (2013).
  * Ai  _et al._ (2013a) Q. Ai, T. C. Yen, B. Y. Jin, and Y. C. Cheng, “Clustered geometries exploiting quantum coherence effects for efficient energy transfer in light harvesting,” J. Phys. Chem. Lett 4, 2577–2584 (2013a).
  * Collini  _et al._ (2010) E. Collini, C. Y. Wong, K. E. Wilk, P. M. G. Curmi, P. Brumer, and G. D. Scholes, “Coherently wired light-harvesting in photosynthetic marine algae at ambient temperature,” Nature 463, 644–647 (2010).
  * Mao, Lu, and Li (2021) W. W. Mao, L. H. Lu, and Y. Q. Li, “Quantum model for understanding protein misfolding behavior—phase diagram and manual intervention,” Sci. China: Phys. Mech. Astron. 64, 260011 (2021).
  * Ritz, Adem, and Schulten (2000) T. Ritz, S. Adem, and K. Schulten, “A model for photoreceptor-based magnetoreception in birds,” Biophys. J. 78, 707 (2000).
  * Solov’yov, Chandler, and Schulten (2008) I. A. Solov’yov, D. E. Chandler, and K. Schulten, “Exploring the possibilities for radical pair effects in cryptochrome,” Plant Signal. & Behav. 3, 676–677 (2008).
  * Mouritsen (2018) H. Mouritsen, “Long-distance navigation and magnetoreception in migratory animals,” Nature 558, 50–59 (2018).
  * Maeda  _et al._ (2008) K. Maeda, K. B. Henbest, F. Cintolesi, I. Kuprov, C. T. Rodgers, P. A. Liddell, D. Gust, C. R. Timmel, and P. J. Hore, “Chemical compass model of avian magnetoreception,” Nature 453, 387–390 (2008).
  * Xu  _et al._ (2021) J. Xu, L. E. Jarocha, T. Zollitsch, M. Konowalczyk, K. B. Henbest, S. Richert, M. J. Golesworthy, J. Schmidt, V. Déjean, D. J. C. Sowood, M. Bassetto, J. Luo, J. R. Walton, J. Fleming, Y. Wei, T. L. Pitcher, G. Moise, M. Herrmann, H. Yin, H. Wu, R. Bartölke, S. J. Käsehagen, S. Horst, G. Dautaj, P. D. F. Murton, A. S. Gehrckens, Y. Chelliah, J. S. Takahashi, K.-W. Koch, S. Weber, I. A. Solov’yov, C. Xie, S. R. Mackenzie, C. R. Timmel, H. Mouritsen, and P. J. Hore, “Magnetic sensitivity of cryptochrome 4 from a migratory songbird,” Nature 594, 535–540 (2021).
  * Yang, Ai, and Sun (2012) L. P. Yang, Q. Ai, and C. P. Sun, “Generalized Holstein model for spin-dependent electron-transfer reactions,” Phys. Rev. A 85, 032707 (2012).
  * Cai  _et al._ (2012) C. Y. Cai, Q. Ai, H. T. Quan, and C. P. Sun, “Sensitive chemical compass assisted by quantum criticality,” Phys. Rev. A 85, 22315 (2012).
  * Keens, Bedkihal, and Kattnig (2018) R. H. Keens, S. Bedkihal, and D. R. Kattnig, “Magnetosensitivity in dipolarly coupled three-spin systems,” Phys. Rev. Lett. 121, 096001 (2018).
  * Cai (2011) J. Cai, “Quantum probe and design for a chemical compass with magnetic nanostructures,” Phys. Rev. Lett. 106, 100501 (2011).
  * Lipkin, Meshkov, and Glick (1965) H. Lipkin, N. Meshkov, and A. Glick, “Validity of many-body approximation methods for a solvable model: (I). Exact solutions and perturbation theory,” Nucl. Phys. 62, 188–198 (1965).
  * Meshkov, Glick, and Lipkin (1965) N. Meshkov, A. Glick, and H. Lipkin, “Validity of many-body approximation methods for a solvable model: (II). Linearization procedures,” Nucl. Phys. 62, 199–210 (1965).
  * Glick, Lipkin, and Meshkov (1965) A. Glick, H. Lipkin, and N. Meshkov, “Validity of many-body approximation methods for a solvable model: (III). Diagram summations,” Nucl. Phys. 62, 211–224 (1965).
  * Garnerone  _et al._ (2009) S. Garnerone, N. T. Jacobson, S. Haas, and P. Zanardi, “Fidelity approach to the disordered quantum $XY$ model,” Phys. Rev. Lett. 102, 057205 (2009).
  * Invernizzi  _et al._ (2008) C. Invernizzi, M. Korbman, L. C. Venuti, and M. G. A. Paris, “Optimal quantum estimation in spin systems at criticality,” Phys. Rev. A 78, 042106 (2008).
  * Ai  _et al._ (2008) Q. Ai, T. Shi, G. Long, and C. P. Sun, “Induced entanglement enhanced by quantum criticality,” Phys. Rev. A 78, 022327 (2008).
  * Salvatori, Mandarino, and Paris (2014) G. Salvatori, A. Mandarino, and M. G. A. Paris, “Quantum metrology in Lipkin-Meshkov-Glick critical systems,” Phys. Rev. A 90, 022111 (2014).
  * Quan, Wang, and Sun (2007) H. T. Quan, Z. D. Wang, and C. P. Sun, “Quantum critical dynamics of a qubit coupled to an isotropic Lipkin-Meshkov-Glick bath,” Phys. Rev. A 76, 012104 (2007).
  * Pan and Draayer (1999) F. Pan and J. P. Draayer, “Analytical solutions for the LMG model,” Phys. Lett. B 451, 1–10 (1999).
  * Rosensteel, Rowe, and Ho (2007) G. Rosensteel, D. J. Rowe, and S. Y. Ho, “Equations of motion for a spectrum–generating algebra: Lipkin–Meshkov–Glick model,” J. Phys. A Math. Theor. 41, 25208 (2007).
  * Castaños  _et al._ (2006) O. Castaños, R. López-Peña, J. G. Hirsch, and E. López-Moreno, “Classical and quantum phase transitions in the Lipkin-Meshkov-Glick model,” Phys. Rev. B 74, 104118 (2006).
  * Wiltschko and Wiltschko (1972) W. Wiltschko and R. Wiltschko, “Magnetic compass of european robins,” Science 176, 62–64 (1972).
  * Kominis (2009) I. K. Kominis, “Quantum Zeno effect explains magnetic-sensitive radical-ion-pair reactions,” Phys. Rev. E 80, 56115 (2009).
  * Ai  _et al._ (2013b) Q. Ai, D. Xu, S. Yi, A. G. Kofman, C. P. Sun, and F. Nori, “Quantum anti-Zeno effect without wave function reduction,” Sci. Rep. 3, 1752 (2013b).
  * Ishizaki and Fleming (2009) A. Ishizaki and G. R. Fleming, “Unified treatment of quantum coherent and incoherent hopping dynamics in electronic energy transfer: Reduced hierarchy equation approach,” J. Chem. Phys 130, 234111 (2009).
  * Wang  _et al._ (2018) B. X. Wang, M. J. Tao, Q. Ai, T. Xin, N. Lambert, D. Ruan, Y. C. Cheng, F. Nori, F. G. Deng, and G. L. Long, “Efficient quantum simulation of photosynthetic light harvesting,” npj Quantum Inf. 4, 52 (2018).
  * Zhang  _et al._ (2021) N. N. Zhang, M. J. Tao, W. T. He, X. Y. Chen, X. Y. Kong, F. G. Deng, N. Lambert, and Q. Ai, “Efficient quantum simulation of open quantum dynamics at various hamiltonians and spectral densities,” Front. Phys. 16, 51501 (2021).


#  USSR is in P/poly

Nikhil Balaji<EMAIL_ADDRESS>Department of Computer Science and
Engineering, IIT Delhi, New Delhi, India  Samir Datta<EMAIL_ADDRESS>Chennai
Mathematical Institute & UMI ReLaX, Chennai, India

###### Abstract

The Sum of Square Roots (SSR) problem is the following computational problem:
Given positive integers $a_{1},\dots,a_{k}$, and signs
$\delta_{1},\dots,\delta_{k}\in\\{-1,1\\}$, check if
$\sum_{i=1}^{k}\delta_{i}\sqrt{a_{i}}>0$. The problem is known to have a
polynomial time algorithm on the _real RAM_ model of computation, however no
sub-exponential time algorithm is known in the bit or Turing model of
computation. The precise computational complexity of SSR has been a notorious
open problem [GGJ76] over the last four decades. The problem is known to admit
an upper bound in the third level of the _Counting Hierarchy_ , i.e.,
P${}^{\bf PP^{\bf PP^{\bf PP}}}$ and no non-trivial lower bounds are known.
Even when the input numbers are _small_ , i.e., given in _unary_ , no better
complexity bound was known prior to our work. In this paper, we show that the
unary variant (USSR) of the sum of square roots problem is considerably easier
by giving a ${\bf P}/{\bf poly}$ upper bound.

##  1 Introduction

The Sum of Square Roots problem (SSR) is the following computational problem:
Given positive integers $a_{1},\dots,a_{k}$, and signs
$\delta_{1},\dots,\delta_{k}\in\\{-1,1\\}$, check if
$\sum_{i=1}^{k}\delta_{i}\sqrt{a_{i}}>0$. It was first explicitly posed in an
influential paper of Garey, Graham and Johnson [GGJ76] on NP-hardness of
geometric problems such as Euclidean TSP and Euclidean Steiner tree. They
remark that while such geometric problems are NP-hard “it is not at all
apparent that this $\dots$ is in NP”, since comparing two given tours is
reducible to SSR, which is not known to be in NP. In fact, even when the input
graph is presented via an embedding where vertices have integer co-ordinates,
the distance between vertices could still be irrational in the Euclidean
metric. Hence comparing lengths of two paths on such a graph, reduces to
comparing two linear combinations of square roots for which the best bounds we
currently have seem to require exponential precision [BFMS00]. However it has
been often observed that in practice that a near-linear bit-precision is
sufficient to decide the sign of an SSR instance [SY17, Chapter 45], and it is
conjectured to be in P. SSR is an important subroutine in Computational
Geometry where many problems are known to be solvable in polynomial time
relative to SSR [HS99]. We refer the interested reader to [DMO06, KS12] and
the references therein for a discussion on the status of SSR and the
stackexchange posts [Erib, Eria] for some interesting discussion on SSR-hard
problems and related geometric questions. Along with the more general problem,
PosSLP111Given an arithmetic circuit using gates $\\{+,\times\\}$ whose only
input is $-1$, check if it computes a positive integer., SSR has been
frequently used as to show _numerical hardness_ in diverse areas such as
algorithmic game theory [EY10, UW11, CIJ14], Semidefinite programming [Goe97],
probabilistic verification [EKL08, HK15, KW11, BLW13], formal language theory
and logic [HKL17, LOW15].

### Prior work

Garey et al. [GGJ76] attribute Andrew Odlyzko to the observation that
approximating every square root in the SSR instance by rational numbers with
$O(k2^{k})$ bits and summing them up suffices to infer the correct sign, which
yields an EXP upper bound for SSR. The main idea behind this observation is
that $\sum_{i=1}^{k}\delta_{i}\sqrt{a_{i}}$ is an _algebraic integer_ whose
_minimal polynomial_ has degree at most $2^{k}$. Therefore by using standard
_root separation bounds_ (see Proposition 2), one can infer the sign of any
such algebraic integer by a suitable numerical approximation.

Using the root separation bound, Tiwari [Tiw92] proved that SSR can be solved
in polynomial time on the unit cost arithmetic RAM model of computation via
Newton iteration. Implicit in Tiwari’s algorithm is an improved complexity
bound: Newton iteration can be used to obtain rational approximation to the
square roots up to $O(k2^{k})$ bits, which can be represented as pair of ${\bf
poly}(k)$-sized arithmetic circuits (for the numerator and the denominator).
Evaluating such circuits can be done in PSPACE. We now know from the work of
Allender et al. [ABKPM09] that Tiwari’s algorithm is essentially a polynomial
time reduction from SSR to PosSLP, which places SSR in P${}^{\bf PP^{\bf
PP^{\bf PP}}}$. This is currently the best known complexity upper bound for
SSR. A different algorithm achieving the same complexity bound, but via a
reduction to _matrix powering_ was presented in [ABD14]. All these results
seem to inherently depend on root separation bounds. Unfortunately, this line
of attack on SSR has its limitations: there exist an integer linear
combination of $k$ square roots, whose minimal polynomial has degree exactly
$2^{k}$; Indeed consider $\alpha=\sum_{i=1}^{k}\sqrt{p_{i}}$ for distinct
primes $p_{i}$. It is well-known from Galois theory [ST01] that the minimal
polynomial of $\alpha$ has degree exactly $2^{k}$. Therefore we require
fundamentally new techniques to substantially improve the complexity of SSR.

### Our work

Many authors have observed [GGJ76, Pap77] that Euclidean TSP is _strongly_ NP-
hard, i.e., the problem is already NP-hard for those graphs where the co-
ordinates of the graph are integers of polynomially (in the number of
vertices) bounded magnitude. This motivates the following variant, USSR :
Given $1\leq a_{1},\dots,a_{k}\leq k$, and
$\delta_{1},\dots,\delta_{k}\in\\{-1,1\\}$, test if
$\sum_{i=1}^{k}\delta_{i}\sqrt{a_{i}}>0$. We remark here that by the prime
number theorem, the magnitude of numbers appearing under the square roots in
the example we constructed above, i.e., $\alpha=\sum_{i=1}^{k}\sqrt{p_{i}}$
are at most ${\cal O}(k\log{k})$. Even for this simple “unary” variant, there
is no better complexity upper bound known than P${}^{\bf PP^{\bf PP^{\bf
PP}}}$. In this work, we improve the state of affairs considerably. We show
that

######  Theorem 1.

${{\bf USSR}}\in{\bf P/poly}$.

We provide two proofs of Theorem 1, both yielding a ${\bf P}/{\bf poly}$ (in
fact even a $\mbox{{\bf TC${}^{0}$}}/{\bf poly}$) upper bound, which is tight
modulo the non-uniformity since checking iterated addition of integers is
TC0-hard. This is a strong indication that USSR should be decidable in P. One
consquence222However this consequence can be inferred by other means too:
since SSR is closed under complement, if it was also NP-complete, this would
imply NP = coNP, collapsing the polynomial hierarchy.  of our result is that
USSR cannot be NP-complete unless the polynomial hierarchy collapses to the
second level. We would like to point out here that USSR is not a _sparse_
333If it were, then it would be trivially in P/poly language: For every $k$
where the instances of USSR have $k$ positive integers from the range
$\\{1,\dots k\\}$, there could be potentially $2^{k}$ distinct instances of
${\bf USSR}$. Amazingly, there is still a $k^{{\cal O}(1)}$ -length _advice
string_ that non-trivially helps solve all the _exponentially-many instances_.
To the best of our knowledge, this is the first instance of a natural (non-
sparse) language that can be solved in P/poly, but not known to be solvable in
the _polynomial hierarchy_ (PH).

### Related work

Cheng [Che06] studied the complexity of USSR and gave a subexponential time
algorithm when the integers in the instance are bounded by ${\cal
O}(k\log{k})$ in magnitude. Kayal and Saha [KS12] define an analogue of SSR
for univariate polynomials and obtain an efficient algorithm for deciding this
variant. As a byproduct, they are able to show that SSR can be solved in P for
the closely related class of _polynomial integers_. The variant they solve is
orthogonal to USSR since there can be numbers of small magnitude that are not
polynomial integers and vice versa. Both SSR and USSR have been conjectured
[Che06] to admit efficient algorithms, though there has not been any concrete
complexity-theoretic evidence before our work. A natural related question,
namely whether a sum of square roots can be checked for equality, i.e.,
$\sum_{i=1}^{k}\delta_{i}\sqrt{a_{i}}=0$ (as against SSR where one wants to
infer the sign of the expression) can be solved efficiently in P [Blo91].

##  2 Preliminaries

Here we recall a few relevant propositionositions about polynomials and
integers, which can be found in standard texts on Computer Algebra [VZGG13]
and Algebraic Number Theory [ST01]. For a polynomial
$P(x)=\sum_{k=0}^{n}a_{k}x^{k}$ with integer coefficients, let
$s=size(P):=\sum_{k=0}^{n}|a_{k}|$.

######  Proposition 2.

[Mah64] Let
$P(x)=\sum_{k=0}^{n}a_{k}x^{k}=a_{n}\cdot\prod_{k=1}^{n}(x-\alpha_{k})$ where
$a_{n}\neq 0$ be an integer polynomial of size $s$ and degree $n$. Then,

$sep(P):=min_{\alpha_{i}\neq\alpha_{j}}|\alpha_{i}-\alpha_{j}|>\frac{\sqrt{3}}{n^{n/2+1}s^{n-1}}$

Earlier we encountered the linear combination of square roots of primes as a
hard instance of USSR. Infact, this observation is true also for linear
combinations of square roots of square-free numbers. First we define square-
free numbers and note that they are abundant.

######  Proposition 3 (Distribution of Square-free numbers [Sha08]).

A square-free number is a positive integer that is not divisible any perfect
square integer other than $1$. Let $m(k)$ denote the number of square-free
numbers in the set $\\{1,\dots,k\\}$. Then $m(k)$ grows asymptotically as
${\Theta}(k)$.

Since $m=m(k)$ and $k$ have the same growth rate, in the rest of the paper, we
will mildly abuse notation and use them interchangeably. The following
important propositionerty of square roots of square free numbers will be an
important component of our ${\bf P}/{\bf poly}$ upper bound.

######  Proposition 4.

Let $\\{s_{1},\dots,s_{m}\\}\subseteq\mathbb{N}$ be square-free positive
integers. Then $\\{\sqrt{s_{1}},\dots,\sqrt{s_{m}}\\}$ are linearly
independent over the rationals. That is, if for some
$c_{1},\dots,c_{m}\in\mathbb{Q}$, $\sum_{i=1}^{m}c_{i}\sqrt{s_{i}}=0$ then we
have $c_{1}=\dots=c_{m}=0$.

Moreover, the set of square-free numbers generate a field of large extension
degree over the rationals.

######  Proposition 5 ([ST01, Bes40]).

Let $\\{s_{1},\dots,s_{m}\\}\subseteq\mathbb{N}$ be square-free positive
integers. Let $\alpha=\sum_{i=1}^{m}c_{i}\sqrt{s_{i}}$ where
$c_{i}\in\mathbb{Z}$ and $p(x)\in\mathbb{Z}[x]$ be a polynomial such that
$p(\alpha)=0$. Then, $p(x)$ must have degree at least $2^{m}$.

##  3 Non-uniform algorithms for USSR

We present two fundamentally different proofs of the ${\bf P/poly}$ upper
bound for USSR. Both the proofs require a crucial preprocessing step to obtain
a _normal form_ for USSR that we call _Universal_ USSR (UUSSR) consisting of
“small” linear combinations of square roots of square-free integers. Formally,
UUSSR is the following computational problem: Given $(\Delta,U)$ where
$\Delta\in[-k^{2},k^{2}]^{m+1}$ and
$U=\\{\sqrt{s_{0}}=1,\sqrt{s_{1}},\dots,\sqrt{s_{m}}\\}$, check if
$\sum_{i=0}^{m}\Delta_{i}\sqrt{s_{i}}>0$. We saw in Proposition 5 that square
roots of square-free integers are a hard instance of USSR. We now observe that
they are in fact the hardest subclass of USSR: That is, in order to solve
USSR, it suffices to estimate the sign of linear combinations of square roots
of square-free integers. We have the following

######  Proposition 6.

For every $k\in\mathbb{N}$, given a USSR instance $(\delta,A)$, with
$\delta\in\\{\pm 1\\}^{k},A=\\{a_{1},\dots,a_{k}\\}$ and $1\leq a_{i}\leq k$,
there exists a UUSSR instance computable in ${\bf poly}(k)$-time, $(\Delta,U)$
where $\Delta\in[-k^{2},k^{2}]^{m+1}$ and
$U=\\{\sqrt{s_{0}}=1,\sqrt{s_{1}},\dots,\sqrt{s_{m}}\\}$, and
$s_{1},\dots,s_{m}$ are the distinct square-free integers smaller than $k$
such that,

$\sum_{i=1}^{k}\delta_{i}\sqrt{a_{i}}>0\mbox{ \ if and only if \
}\sum_{j=0}^{m}\Delta_{j}\sqrt{s_{j}}>0$

.

###### Proof.

We design as an intermediate step the USSR instance $(\Gamma,[k])$ which
consists of all the integers between $1$ and $k$, i.e.,
$\sum_{\ell=1}^{k}\Gamma_{\ell}\sqrt{\ell}$. Now we can partition $[k]$ as

$[k]=S\sqcup P\sqcup R$

where

  * •

$S=\\{s_{1},\dots,s_{m}\\}$ are the square-free numbers.

  * •

$P$ consists of perfect squares.

  * •

$R$ consists of the rest, i.e., $R=[k]\setminus(S\cup P)$.

The sum $\sum_{\ell=1}^{k}\Gamma_{\ell}\sqrt{\ell}$ can be rewritten as

$\displaystyle\sum_{\ell=1}^{k}\Gamma_{\ell}\sqrt{\ell}$ $\displaystyle=$
$\displaystyle\sum_{s\in S}\Gamma_{s}\sqrt{s}+\sum_{p\in
P}\Gamma_{p}\sqrt{p}+\sum_{r\in R}\Gamma_{r}\sqrt{r}$

where we set $\Gamma_{s},\Gamma_{p},\Gamma_{r}$ to be $\\{0,\pm 1\\}$
according to the given USSR instance $(\delta,A)$ as follows. If the number
$\ell\in A$, then there must be a corresponding sign for this number in the
$\delta$ vector, and we set $\Gamma_{\ell}$ to be this sign. Otherwise
$\ell\notin A$ and we set $\Gamma_{\ell}=0$. To prove the claimed bounds on
$\Delta$ we proceed as follows.

  * •

Since there will be roughly $\lfloor\sqrt{k}\rfloor$ perfect squares between
$1$ and $k$, the contribution of $\sum_{p\in P}\Gamma_{p}\sqrt{p}$ will be an
integer $\Delta_{0}$, where $|\Delta_{0}|\leq k^{3/2}\leq k^{2}$.

  * •

Any number that is neither square free nor a perfect square can be decomposed
in to a square free part and a squared part. For example, if
$a_{i}=c_{i}^{2}s_{i}$ then we can write $\sqrt{a_{i}}=c_{i}\sqrt{s_{i}}$
where $c_{i}\leq\sqrt{k}$. Therefore $\sum_{r\in R}\Gamma_{r}\sqrt{r}$ can be
rewritten as $\sum_{s\in S}\Gamma_{s}^{\prime}\sqrt{s}$ where
$\Gamma_{s}^{\prime}\leq\sqrt{k}$.

Therefore we can rewrite the USSR instance
$\sum_{\ell=1}^{k}\Gamma_{\ell}\sqrt{\ell}$ as a UUSSR instance
$\sum_{j=0}^{m}\Delta_{j}\sqrt{s_{j}}$ where $\forall
j\in\\{0,1,\dots,m\\},|\Delta_{j}|\leq k^{2}$ as claimed. The reduction is
clearly in polynomial (in $k$) time. ∎

Henceforth, we will concern ourselves with only instances of UUSSR: Given $k$,
and $\Delta\in[-k^{2},k^{2}]^{m}$, check if
$\sum_{j=0}^{m}\Delta_{j}\sqrt{s_{j}}>0$. Note that by Proposition 3, $m={\cal
O}(k)$. With the help of Proposition 6, we have encoded the input set of
numbers $A$ in to the small linear combinations $\Delta$. We are now ready to
give a proof of Theorem 1

###  3.1 Proof of Theorem 1 via Linear Threshold Functions

A Boolean function $f:\mathbb{B}^{m}\to\\{\pm 1\\}$ over a bounded discrete
domain $\mathbb{B}$ is said to be a Linear Threshold Function (LTF) if and
only if _there exist_ real numbers $w_{0},w_{1},\dots,w_{m}\in\mathbb{R}$ such
that for every $x\in\mathbb{B}^{m}$, $f(x)=1$ iff
$\sum_{i=1}^{m}w_{i}x_{i}\geq w_{0}$. LTFs are central objects of study in
many areas of theoretical computer science such as circuit complexity,
learning theory, analysis of Boolean functions and communication complexity
[AB09].

The real numbers $w_{0},w_{1},\dots,w_{m}$ are said to be a _realization_ of
the LTF $f$. Note that any LTF has infinitely many realizations. The following
classical theorem due to Muroga [Mur65] says that any LTF over a _bounded
discrete domain_ $\mathbb{B}$, can also be realized with integer weights of
_small_ 444It is easy to see that there always exists _some_ integer
realization for any LTF. Indeed, consider
$\varepsilon=min_{x\in\mathbb{B}^{m}}\left(\sum_{i=1}^{m}w_{i}x_{i}-w_{0}\right)$,
and for every $i\in[m]$, pick a rational number $w_{i}^{\prime}$ in the
interval $(w_{i}-\frac{\varepsilon}{10m},w_{i}+\frac{\varepsilon}{10m})$.
Clearly, for every $x\in\mathbb{B}^{n}$, $\sum_{i=1}^{m}w_{i}x_{i}-w_{0}>0$ if
and only if $\sum_{i=1}^{m}w_{i}^{\prime}x_{i}-w_{0}^{\prime}>0$. By clearing
the denominators of the rationals, we obtain the integer realization. Notice
however that the magnitude of $w_{i}^{\prime}$ depend on $\varepsilon$
magnitude (i.e., representable using at most ${\cal O}(m\log{m})$-bits). In
fact the theorem shows that such a representation is only dependent on $m$ and
the the maximum absolute value of any element in the discrete bounded domain
$\mathbb{B}$. In particular it is independent of the real numbers
$w_{0},w_{1},\dots,w_{m}$.

######  Theorem 7 (Muroga [Mur65]).

Let $b$ be the maximum magnitude of elements in $\mathbb{B}$. For any LTF
$f:\mathbb{B}^{m}\to\\{\pm 1\\}$ realized using weights
$w_{0},w_{1},\dots,w_{m}\in\mathbb{R}$, there exists an equivalent integer
realization with weights $u_{0},u_{1}\dots,u_{m}\in\mathbb{Z}$, where
$1\leq|u_{0}|,\dots,|u_{m}|\leq{\cal O}((m+1)!b^{m})$.

The proof of Theorem 7 follows from a simple application of Linear Programming
and is a fundamental result in Circuit Complexity and Learning Theory. We give
an exposition of the proof in the Appendix A for the sake of completeness. The
proof of Theorem 1 is now immediate; we simply consider the LTF which is
realized using the weights
$\Delta_{0},\Delta_{1}\sqrt{s_{1}},\dots,\Delta_{m}\sqrt{s_{m}}$ and observe
that there is also an integer realization of this LTF that uses small
_integer_ weights of magnitude at most $m^{{\cal O}(m)}$.

###### Proof.

(of Theorem 1)

We invoke Theorem 7 with $\mathbb{B}=\\{-1,0,1\\}$ and
$w_{0}=\Delta_{0},w_{1}=\Delta_{1}\sqrt{s_{1}},\dots,w_{m}=\Delta_{m}\sqrt{s_{m}}$.
The LTF $f:{\mathbb{B}}^{m}\to\\{\pm 1\\}$ is given by $f(x)=1$ if and only if
$\sum_{j=1}^{m}x_{j}|\Delta_{j}|\sqrt{s_{j}}>\Delta_{0}$. By Theorem 7, there
exist integers $u_{0},\dots,u_{m}$ of magnitude at most ${\cal
O}((m+1)!)=m^{{\cal O}(m)}$ such that for every $x\in\mathbb{B}^{m}$

$\sum_{j=1}^{m}x_{j}\Delta_{j}\sqrt{s_{j}}>\Delta_{0}\mbox{\ if and only if\
}\sum_{j=1}^{m}x_{j}u_{j}>u_{0}$

The non-uniform advice for our algorithm will be exacly these $m+1$ numbers
$u_{0},\dots,u_{m}$ each of which is ${\cal O}(m\log{m})$ bits long. Since
$m={\cal O}(k)$ by Proposition 3, for every $k$, the total length of the
advice string is ${\cal O}(k^{2}\log{k})$ bits. Given this advice, to decide
the sign of any given UUSSR instance $\sum_{j=0}^{m}\Delta_{j}\sqrt{s_{j}}$,
we can instead now check if $\sum_{j=1}^{m}u_{j}>u_{0}$. Since
$u_{0},\dots,u_{m}$ are integers of magnitude at most ${\cal
O}((m+1)!)=2^{{\cal O}(m\log m)}$, such a computation is just an iterated
addition of ${\cal O}(m\log m)$-bit integers which can be performed in
polynomial time. ∎

######  Remark 8.

A closer observation of the proofs of Proposition 6 and Theorem 7 shows that
in fact USSR $\in\mbox{{\bf TC${}^{0}$}}/{\bf poly}$. The reduction from USSR
to UUSSR in Proposition 6 can be implemented in TC0: Since the numbers are in
unary, checking membership in the sets $S,P$ and $R$ reduces to bruteforce
division. Similarly checking if $\sum_{j=1}^{m}u_{j}>u_{0}$ is essentially an
iterated addition of ${\cal O}(k\log{k})$-bit integers. Since division and
iterated addition can be performed in TC0 [HAB02], this shows that both ${{\bf
UUSSR}}$ and ${{\bf USSR}}$ are in $\mbox{{\bf TC${}^{0}$}}/{\bf poly}$.

###  3.2 Proof of Theorem 1 via Numerical Approximations

We now present a fundamentally different ${\bf P}/{\bf poly}$ upper bound
proof which allows us to solve UUSSR provided we know the _approximate
magnitudes_ of ($m+1$) _smallest_ UUSSR instances. The high-level idea behind
the proof is follows: Given an instance of UUSSR as in Proposition 6 we can
interpret the USSR problem as estimating the sign of the inner product of a
vector in $\mathbb{B}^{m+1}$ with a _fixed vector_ in $\mathbb{R}^{m+1}$,
namely the vector of square roots of square-free numbers. Next, observe that
there exists a set of $m+1$ vectors in $\mathbb{B}^{m+1}$ which spans
$\mathbb{R}^{m+1}$ Could it be possible that the sign of this inner product
can be estimated from the sign/value of the inner products of the basis
elements? While this is not possible for an arbitrary basis, we show that
there exists a _nice_ basis which allows us to do precisely this. Therefore,
if this basis along with the _approximate values_ of the inner product of the
basis vectors is given as advice, we show that we can estimate the sign of
UUSSR instance.

First we set up some notation. As alluded to earlier, any UUSSR instance can
be interpreted as an inner product as follows:

$\displaystyle
A=\sum_{j=0}^{m}\Delta_{j}\sqrt{s_{j}}=\langle\vec{\Delta},\vec{S}\rangle$

where $\vec{\Delta}=(\Delta_{0},\dots,\Delta_{m})\in[-k^{2},k^{2}]^{m+1}$ and
$\vec{S}=(1,\sqrt{s_{1}},\dots,\sqrt{s_{m}})\in\mathbb{R}^{m+1}$. By
Proposition 4, none of them evaluate to $0$ except the inner product with the
zero vector. In what follows, we consider only those vectors $\vec{\Delta}$
which have a _positive inner product_ on $\vec{S}$, i.e.,
$W=\\{\vec{\Delta}\in[-k^{2},k^{2}]^{m+1}\mid\langle\vec{\Delta},\vec{S}\rangle>0\\}\subseteq\mathbb{R}^{m+1}$.
Let $|W|=t$. Let $\\{v_{i}\\}_{i=1}^{t}$ be the magnitude of the inner product
of the elements of $W$. By our assumption we have $0<v_{0}v_{1},\dots,v_{t}$
and each of these numbers are distinct since if $v_{i}=v_{j}$ it gives rise to
a non-trivial linear dependence between the square roots, which is impossible
by Proposition 4.

We now construct the unique _lightest_ basis for $\mathbb{R}^{m+1}$ from the
vectors in $W$ by picking the least (ordered by magnitude of inner product)
$m+1$ linearly independent vectors in $[-k^{2},k^{2}]^{m+1}$. It is clear that
a basis for $\mathbb{R}^{m+1}$ using these vectors exists and is unique
(uniqueness follows from Proposition 4). We denote these vectors by ${\bf
b_{0}},{\bf b_{1}},\dots,{\bf b_{m}}$, where ${\bf
b_{i}}=(b_{i0},\dots,b_{im})\in[-k^{2},k^{2}]^{m+1}$. Let $v_{0}=\langle{\bf
b_{0}},\vec{S}\rangle,v_{1}=\langle{\bf
b_{1}},\vec{S}\rangle,\dots,v_{m}=\langle{\bf b_{m}},\vec{S}\rangle$. Given an
instance of UUSSR of the form $A=\langle\vec{\Delta},\vec{S}\rangle$, it is
clear that we can express $\vec{\Delta}$ in the lightest basis as
$\vec{\Delta}=\sum_{i=0}^{m}c_{i}{\bf b_{i}}$. The $c_{i}$ can be obtained by
solving a system of linear equations over the rationals. This immediately
gives an upper and lower bound on $c_{i}$: The maximum entry of the matrix of
such a linear system is at most $k^{2}$ (which is also the maximum possible
entry in any ${\bf b_{i}}$); Therefore by Cramer’s rule we get that for all
$i,|c_{i}|\leq{\cal O}((m+1)!k^{2m})=2^{{\cal O}(m\log{km})}$. Since all the
entries of the matrix are integers, if $c_{i}\neq 0$, we also have
$|c_{i}|\geq\frac{1}{2^{{\cal O}(m\log{km})}}$. Now, we have

$A=\langle\sum_{i=0}^{m}c_{i}{\bf
b_{i}},\vec{S}\rangle=\sum_{i=0}^{m}c_{i}\langle{\bf
b_{i}},\vec{S}\rangle=\sum_{i=0}^{m}c_{i}v_{i}$

.

######  Remark 9.

Note that just by observing that $\frac{1}{2^{{\cal O}(m\log{km})}}\leq
c_{i}\leq 2^{{\cal O}(m\log{km})}$ we can conclude that there exists
$i\in\\{0,1,\dots,m\\}$ such that $|v_{i}|>\frac{1}{2^{{\cal O}(m\log{km})}}$.
That is, all the basis vectors cannot have double exponentially small inner
product with $\vec{S}$. Because, otherwise, they cannot express _large_
instance of USSR which are guaranteed to exist, for e.g.
$A=\sum_{i=0}^{m}\sqrt{s_{i}}$ whose magnitude is larger than $m$.

Notice that expressing the UUSSR instance in the lightest basis immediately
yields the following simple lower bound.

######  Proposition 10.

$|A|=|\sum_{i=0}^{m}c_{i}\langle{\bf
b_{i}},\vec{S}\rangle|=|\sum_{i=0}^{m}c_{i}v_{i}|>v_{m_{1}}$

where $m_{1}\in[m]$ is the largest index such that $c_{m_{1}}\neq 0$.

###### Proof.

If $|A|<v_{m_{1}}$, then by definition (of the lightest basis) the basis
vector ${\bf b_{m_{1}}}$ can be replaced by $\vec{\Delta}$. ∎

From the preceeding discussion, it seems like in order to find the sign of the
quantity $A$, it suffices to know the magnitude and sign of all the $v_{i}$.
The best bounds for $v_{i}$ are obtained through root separation bounds
(Proposition 2), which turn out to be doubly exponentially small as a function
of $m$ in magnitude (Proposition 5). Therefore, they need exponential (in $m$)
number of bits to express them unambiguously and any arithmetic with such
numbers is bound to result in an exponential time algorithm!

However the lower bound from Proposition 10 gives us some leeway to use
approximations to $v_{i}$ instead of $v_{i}$ themselves. We will now show that
if we have a suitable _rational approximation_ $\widetilde{v}_{i}$ to the
$v_{i}$’s the resulting error is small. Towards this we now assume we work
with $\widetilde{v}_{i}=\beta_{i}2^{-e_{i}}$, where $\beta_{i}$ is a ${\cal
O}(m^{2})$-bit rational number in the interval $(1,2)$. Notice that by
standard root separation bounds (see Proposition 2 and 5), one can infer that
$|e_{i}|\leq 2^{{\cal O}(m)}$ and hence expressible using ${\cal O}(m)$ bits.
The $\\{\widetilde{v}_{i}=\beta_{i}2^{-e_{i}}\\}_{i=0}^{m}$ are approximations
to $\\{\langle{\bf
b_{i}},\vec{S}\rangle=\sum_{j=0}^{m}b_{ij}\sqrt{s_{j}}\\}_{i=0}^{m}$. We have
the following

######  Proposition 11.

$\widetilde{A}=\sum_{i=0}^{m}c_{i}\widetilde{v_{i}}=\sum_{i=0}^{m}c_{i}\beta_{i}2^{-e_{i}}>0$
if and only if $A=\sum_{i=0}^{m}c_{i}v_{i}>0$

###### Proof.

If we use $\widetilde{v_{i}}$ instead of $v_{i}$, we can upper bound the total
accumulated error incurred as follows:

$\displaystyle|\sum_{i=0}^{m}c_{i}(v_{i}-\widetilde{v_{i}})|\hskip 8.5359pt$
$\displaystyle\leq\sum_{i=0}^{m}c_{i}|v_{i}-\widetilde{v_{i}}|\hskip
8.5359pt=\hskip
8.5359pt\sum_{i=0}^{m}c_{i}\left|v_{i}-\beta_{i}2^{-e_{i}}\right|$
$\displaystyle\leq\sum_{i=0}^{m}(2^{m\log{m}})\cdot(2^{-m^{2}}\cdot
2^{-e_{i}})\hskip 8.5359pt\leq\hskip
8.5359ptm\cdot(2^{m\log{m}})\cdot(2^{-m^{2}}2^{-e_{m_{1}}})$

where the inequality $|v_{i}-\beta_{i}2^{-e_{i}}|\leq(2^{-m^{2}}\cdot
2^{-e_{i}})$ above is obtained by noticing that by definition the
approximation $\widetilde{v_{i}}$ agrees with $v_{i}$ on the mantissa. The
last inequality is obtained by noting that $v_{m_{1}}$ is the basis vector
with the largest magnitude that is used in expressing $A$ in terms of the
lightest basis. We can now lower bound the ratio of value of the given
instance of UUSSR to the error accrued is at least

$\frac{|\sum_{i=0}^{m}c_{i}v_{i}|}{|\sum_{i=0}^{m}c_{i}(v_{i}-\widetilde{v_{i}})|}\hskip
8.5359pt\geq\hskip
8.5359pt\frac{2^{-e_{m_{1}}}}{m2^{m\log{m}}2^{-m^{2}}2^{-e_{m_{1}}}}\hskip
8.5359pt=\hskip 8.5359pt2^{\Omega(m^{2})}$ (1)

This means that the total error accrued by using $\widetilde{v_{i}}$ instead
of $v_{i}$ is a very small fraction of the absolute value of $A$ and hence the
${\cal O}(m^{2})$-bit approximation to each $v_{i}$, namely
$\widetilde{v_{i}}=\beta_{i}2^{-e_{i}}$ suffices to compute the correct sign
of $A$. ∎

We are now ready to give our second proof of the ${\bf P/poly}$ upper bound.

###### Proof.

We have as our ${\bf poly}(k)$-length advice string:

  1. 1.

The lightest basis $\\{{\bf b_{i}}\in[-k^{2},k^{2}]^{m}\\}_{i=0}^{m}$.

  2. 2.

$\\{\widetilde{v}_{i}=\beta_{i}2^{-e_{i}}\\}_{i=0}^{m}$, which are
approximations to $\\{\langle{\bf
b_{i}},\vec{S}\rangle=\sum_{j=0}^{m}b_{ij}\sqrt{s_{j}}\\}_{i=0}^{m}$.

Given this advice, our ${\bf P}/{\bf poly}$ algorithm for the UUSSR instance
$A=\langle\vec{\Delta},\vec{S}\rangle$ is straight forward: Firstly notice
that $A\neq 0$ by Proposition 4 and this can be checked in polynomial time
[Blo91, HBM+10] as well. If $\vec{\Delta}$ is present in the lightest basis or
a multiple of one of the basis elements, then the sign is just obtained
directly from the advice string in conjuction with the polynomial time tests
mentioned above. Therefore, let us assume that $\Delta$ is a non-trivial
linear combination of the basis vectors. We proceed as follows:

  1. 1.

Find $c_{i}$ such that $\vec{\Delta}=\sum_{i=0}^{m}c_{i}{\bf b_{i}}$.

  2. 2.

Return the sign of the appropriate linear combination
$\widetilde{A}=\sum_{i=0}^{m}c_{i}\widetilde{v}_{i}$.

Finding $c_{i}$ can be done by solving a system of linear equations, and hence
is in P. However, it is not clear how to return the sign of the linear
combination $\widetilde{A}=\sum_{i=0}^{m}c_{i}\widetilde{v}_{i}$, because this
involves arithmetic with exponential-bit numbers! Recall that by the root
separation bound, we only ensured that $e_{i}\leq 2^{{\cal O}(m)}$, so
$\widetilde{v_{i}}$’s are still exponetial-bit approximations to $v_{i}$ which
admit a succinct representation. We are now left with the task of ensuring
that (approximately) computing the linear combination can be done efficiently.
For this, let $m_{1}\in[m]$ be the largest index such that $c_{m_{1}}\neq 0$.
Also let $m_{0}\leq m_{1}$ be the smallest index such that
$e_{m_{0}}-e_{m_{1}}\leq m^{2}$. Let

$\widetilde{V}=\sum_{i=m_{0}}^{m_{1}}{c_{i}\beta_{i}2^{-e_{i}}}=\left(\sum_{i=m_{0}}^{m_{1}}{c_{i}\beta_{i}2^{-(e_{i}-e_{m_{1}})}}\right)2^{-e_{m_{1}}}$
(2)

where the quantity inside the large parentheses is a sum of at most $m$
rationals each with at most a $2m^{2}$-bit representation, and hence can be
computed in TC0. Essentially we drop all those terms whose exponents are
larger than $m_{0}$. It follows that $\widetilde{V}$ is a good approximation
to $\widetilde{A}$ and hence also to $A$. To this end, notice that we
introduce two kinds of errors while making this approximation:

  1. 1.

The error due to truncation (as argued in Proposition 11). This error is upper
bounded in absolute value by $(m_{1}-m_{0}+1)2^{-{(e_{m_{1}}+m^{2})}}$.

  2. 2.

The error due to dropping of all terms preceding $m_{0}$ in Equation 2. This
error is upper bounded in absolute value by
$(m_{0}-1)2^{(-e_{m_{0}-1}+m^{2})}$.

But we know from the definition of $m_{0}$ that
$|e_{m_{0}-1}|>|e_{m_{1}}|+m^{2}$. Thus the total error is upper bounded in
magnitude by $m_{1}2^{-{(e_{m_{1}}+2m^{2})}}$. As a fraction of the magnitude
of the UUSSR instance, this error is small and as argued previously via
Equation 1, our approximation using $\widetilde{v_{i}}$ always returns the
right answer. ∎

######  Remark 12.

Note that our second proof seems weaker than the first proof since it seems to
require solving a system of linear equations which is not known to be
implementable in TC0. However, notice that if we provide the inverse of the
$(m+1)\times(m+1)$ matrix $[{\bf b_{0}},{\bf b_{1}},\dots,{\bf b_{m}}]$ as
advice, the algorithm above can be implemented in TC0. Note that this is only
an additional ${\bf poly}(m)={\bf poly}(k)$ bits long since each entry is a
${\bf poly}(k)$-bit rational number.

##  4 Summary and Conclusion

We have presented two non-uniform algorithms for USSR. Both can be viewed as
“compressing” exponentially many input instances into a polynomial-length
advice string such that each instance can be solved _easily_ given the advice.
Moreover, it is easy to see that the unary nature of USSR does not play an
important role here. In other words, given any set of $k$ _fixed_ positive
integers the corresponding $2^{k}$ instances of SSR can be similarly
compressed into a polynomial length advice string from which extracting the
solution to an instance is easy. In fact, the compression is possible for the
signed sum of any $k$ _fixed_ real numbers.

A notable point about the numerical approximation proof is that the number of
basis elements $b_{i}$ is only $m+1$ while by the root separation bound their
exponents $e_{i}$ are distributed over an exponential range in $m$. Thus if
the $e_{i}$’s are “well-distributed” i.e. consecutive $e_{i}$’s differ by
$\Omega(m^{2})$ then we just need to consult the value of _one_ basis element
to decide on an instance. Prior to our work, there was no difference in the
computational complexity between USSR and SSR. Our work raises a few natural
questions:

  1. 1.

Is there a polynomial time algorithm for USSR? Is there a way to use both the
proofs in tandem to _verify_ the advice? This would give an NP algorithm for
USSR. Even a PH algorithm will be a significant improvement to the current
state of affairs.

  2. 2.

Consider the proof via LTFs: Is it possible to estimate the number of vertices
in the polytope of the LTF obtained from the UUSSR instance? Can we
characterize when the vertices will be determined by _easy_ UUSSR instances?

  3. 3.

Is it possible to eliminate either the values $\\{v_{i}\\}_{i=0}^{m}$ or the
basis $\\{{\bf b_{i}}\\}_{i=0}^{m}$ from the advice string in the numerical
approximation proof?

  4. 4.

Is SSR $\in{\bf P}/{\bf poly}$?

  5. 5.

Can reasoning similar to Remark 9 be used to give better bounds on
distribution on roots of a univariate polynomial, or give improved root
separation bounds?

#### Acknowledgements

We would like to thank Nikhil Mande, Mahesh Sreekumar Rajasree, Vikram Sharma,
Mahsa Shirmohammadi and James Worrell for many insightful discussions around
the Sum of Square Roots problem. N.B is partially supported by the TBO faculty
fellowship (IIT Delhi) and the CNRS International Emerging Actions grant
(IEA’22).

## References

  * [AB09] Sanjeev Arora and Boaz Barak.  Computational Complexity: A Modern Approach.  Cambridge University Press, 2009.
  * [ABD14] Eric Allender, Nikhil Balaji, and Samir Datta.  Low-depth uniform threshold circuits and the bit-complexity of straight line programs.  In Mathematical Foundations of Computer Science 2014, pages 13–24. Springer, 2014.
  * [ABKPM09] Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, and Peter Bro Miltersen.  On the complexity of numerical analysis.  SIAM J. Comput., 38(5):1987–2006, 2009.
  * [Bes40] Abram S Besicovitch.  On the linear independence of fractional powers of integers.  Journal of the London Mathematical Society, 1(1):3–6, 1940.
  * [BFMS00] Christoph Burnikel, Rudolf Fleischer, Kurt Mehlhorn, and Stefan Schirra.  A strong and easily computable separation bound for arithmetic expressions involving radicals.  Algorithmica, 27(1):87–99, 2000.
  * [Blo91] J Blomer.  Computing sums of radicals in polynomial time.  In [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science, pages 670–677. IEEE, 1991.
  * [BLW13] Michael Benedikt, Rastislav Lenhardt, and James Worrell.  Ltl model checking of interval markov chains.  In International Conference on Tools and Algorithms for the Construction and Analysis of Systems, pages 32–46. Springer, 2013.
  * [Che06] Qi Cheng.  On comparing sums of square roots of small integers.  In International Symposium on Mathematical Foundations of Computer Science, pages 250–255. Springer, 2006.
  * [CIJ14] Krishnendu Chatterjee and Rasmus Ibsen-Jensen.  The complexity of ergodic mean-payoff games.  In International Colloquium on Automata, Languages, and Programming, pages 122–133. Springer, 2014.
  * [DMO06] Erik D Demaine, Joseph SB Mitchell, and Joseph O’Rourke.  The open problems project: Problem 33, 2006.
  * [EKL08] Javier Esparza, Stefan Kiefer, and Michael Luttenberger.  Solving monotone polynomial equations.  In Fifth Ifip International Conference On Theoretical Computer Science–Tcs 2008, pages 285–298. Springer, 2008.
  * [Eria] Jeff Erickson.  Complexity of computing shortest paths in the plane with polygonal obstacles.  cstheory.stackexchange.  URL:https://cstheory.stackexchange.com/q/4034/256 (visited on 2010-12-31).
  * [Erib] Jeff Erickson.  Sum-of-square-roots-hard problems?  cstheory.stackexchange.  URL:https://cstheory.stackexchange.com/q/4053/256 (visited on 2011-01-01).
  * [EY10] K. Etessami and M. Yannakakis.  On the complexity of Nash equilibria and other fixed points.  SIAM J. Comput., 39(6):2531–2597, 2010.
  * [GGJ76] Michael R Garey, Ronald L Graham, and David S Johnson.  Some np-complete geometric problems.  In Proceedings of the eighth annual ACM symposium on Theory of computing, pages 10–22. ACM, 1976.
  * [Goe97] Michel X Goemans.  Semidefinite programming in combinatorial optimization.  Mathematical Programming, 79(1-3):143–161, 1997.
  * [HAB02] W. Hesse, E. Allender, and D.A.M. Barrington.  Uniform constant-depth threshold circuits for division and iterated multiplication.  Journal of Computer and System Sciences, 65:695–716, 2002.
  * [HBM+10] Paul Hunter, Patricia Bouyer, Nicolas Markey, Joël Ouaknine, and James Worrell.  Computing rational radical sums in uniform tc^ 0.  In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2010.
  * [HK15] Christoph Haase and Stefan Kiefer.  The odds of staying on budget.  In International Colloquium on Automata, Languages, and Programming, pages 234–246. Springer, 2015.
  * [HKL17] Christoph Haase, S Kiefer, and Markus Lohrey.  Counting problems for Parikh images.  In Leibniz International Proceedings in Informatics, LIPIcs, volume 83, page 12. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017.
  * [HS99] John Hershberger and Subhash Suri.  An optimal algorithm for euclidean shortest paths in the plane.  SIAM Journal on Computing, 28(6):2215–2256, 1999.
  * [KS12] Neeraj Kayal and Chandan Saha.  On the sum of square roots of polynomials and related problems.  ACM Transactions on Computation Theory (TOCT), 4(4):9, 2012.
  * [KW11] Stefan Kiefer and Dominik Wojtczak.  On probabilistic parallel programs with process creation and synchronisation.  In International Conference on Tools and Algorithms for the Construction and Analysis of Systems, pages 296–310. Springer, 2011.
  * [LOW15] Antonia Lechner, Joël Ouaknine, and James Worrell.  On the complexity of linear arithmetic with divisibility.  In 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science, pages 667–676. IEEE, 2015.
  * [Mah64] Kurt Mahler.  An inequality for the discriminant of a polynomial.  The Michigan Mathematical Journal, 11(3):257–262, 1964.
  * [Mur65] Saburo Muroga.  Lower bounds of the number of threshold functions and a maximum weight.  IEEE Transactions on Electronic Computers, (2):136–148, 1965.
  * [Pap77] Christos H Papadimitriou.  The euclidean travelling salesman problem is np-complete.  Theoretical computer science, 4(3):237–244, 1977.
  * [Sha08] Harold N Shapiro.  Introduction to the Theory of Numbers.  Courier Corporation, 2008.
  * [ST01] Ian Stewart and David Tall.  Algebraic number theory and Fermat’s last theorem.  AK Peters/CRC Press, 2001.
  * [SY17] Vikram Sharma and Chee Yap.  Robust geometric computation.  In Handbook of Discrete and Computational Geometry, Third Edition, pages 1189–1223. CRC Press, 2017.
  * [Tiw92] P. Tiwari.  A problem that is easier to solve on the unit-cost algebraic ram.  J. Complexity, 8(4):393–397, 1992.
  * [UW11] Michael Ummels and Dominik Wojtczak.  The complexity of Nash equilibria in limit-average games.  In International Conference on Concurrency Theory, pages 482–496. Springer, 2011.
  * [VZGG13] Joachim Von Zur Gathen and Jürgen Gerhard.  Modern computer algebra.  Cambridge university press, 2013.

##  Appendix A Muroga’s Proof

Let $\mathbb{B}$ be any bounded discrete domain.

######  Theorem 13.

Let $b$ be the maximum magnitude of elements in $\mathbb{B}$. For any LTF
$f:\mathbb{B}^{m}\to\\{\pm 1\\}$ realized using weights
$w_{0},w_{1},\dots,w_{m}\in\mathbb{R}$, there exists an equivalent integer
realization with weights $u_{0},u_{1}\dots,u_{m}\in\mathbb{Z}$, where
$1\leq|u_{0}|,\dots,|u_{m}|\leq{\cal O}((m+1)!b^{m})$.

###### Proof.

Given $w_{1},\dots,w_{n},\theta$, let $X$ be that subset of $\mathbb{B}^{n}$
for which $\sum_{i=1}^{n}w_{i}x_{i}\geq 1$. Now consider the linear program
with variables $z_{1},\dots,z_{n}$ and the following $|\mathbb{B}|^{n}$
constraints

$\displaystyle\sum_{i=1}^{n}z_{i}x_{i}$ $\displaystyle\geq 1\hskip
28.45274pt\mbox{ for }(x_{1},\dots,x_{n})\in X$
$\displaystyle\sum_{i=1}^{n}z_{i}x_{i}$ $\displaystyle\leq-1\hskip
28.45274pt\mbox{ for }(x_{1},\dots,x_{n})\notin X$

Clearly, this is a feasible LP because $z_{i}=w_{i}/\theta$ is a feasible
solution. Therefore it should also have a solution that is a vertex, i.e., a
solution with $n$ tight LP constraints of the form
$\sum_{i=1}^{n}z_{i}x_{i}=\pm 1$. We can solve such a system of linear
equations $X{\bf z}={\bf b}$ where $X\in{\mathbb{B}}^{n\times n}$ and ${\bf
b}\in\\{\pm 1\\}^{n}$. By Cramer’s rule, this should give a solution which is
the ratio of two determinants. An upper bound on the determinant (and hence
any minor) of $X$ is ${\cal O}(n!b^{n})$. This gives a rational solution for
$z_{i}$. By clearing the denominators, we get the claimed integer solution. It
is clear that such a solution will satisfy all the constraints since it is a
vertex of the polytope. ∎