# A Null-space based Approach for a Safe and Effective Human-Robot
Collaboration

Federico Benzi and Cristian Secchi F. Benzi and C. Secchi are with the
Department of Sciences and Methods of Engineering, University of Modena and
Reggio Emilia, Italy<EMAIL_ADDRESS>
(February 2021)

###### Abstract

During physical human robot collaboration, it is important to be able to
implement a time-varying interactive behaviour while ensuring robust
stability. Admittance control and passivity theory can be exploited for
achieving these objectives. Nevertheless, when the admittance dynamics is
time-varying, it can happen that, for ensuring a passive and stable behaviour,
some spurious dissipative effects have to be introduced in the admittance
dynamics. These effects are perceived by the user and degrade the
collaborative performance. In this paper we exploit the task redundancy of the
manipulator in order to harvest energy in the null space and to avoid spurious
dynamics on the admittance. The proposed architecture is validated by
simulations and by experiments onto a collaborative robot.

##  I Introduction

Kinematically redundant robots are endowed with more degrees of freedom (DOFs)
than those required for the execution of a specific task. This extra dexterity
of theirs can be exploited for implementing additional sub-tasks alongside the
main one. This capability is pivotal in a Human Robot Collaboration (HRC)
scenario, in which the applications often require high flexibility and
dexterity.

In order to exploit the kinematic redundancy [1], it is possible to encode the
tasks of the robot as functions which depend on the robot configuration,
namely the task function [2]. We can then map the resulting control input from
the task space into the joint space using the (pseudo-) inverse of the
Jacobian, as shown in [3] and [4]. This method has been extensively used for
the likes of redundant manipulators [5], humanoids [6] and high-dimensional
robots [7].

Furthermore, it is possible to consider redundancy with respect to a specific
task. Exploiting the concept of task redundancy, it is possible to
simultaneously implement secondary tasks which do not affect the execution of
the main one. This is often carried out by exploiting the null space
projection of the Jacobian, as in [8, 9, 10].

The concept of redundancy has been also exploited in the control of
interaction between the robot and the environment. In particular, control
strategies for implementing impedance control on redundant robots have been
proposed in [11], [12] and [13].

Admittance control [14] is used for controlling the interaction in velocity
controlled robots. The main idea is to control the robot to mimic a desired
physical dynamics, i.e. the admittance dynamics. Since physical dynamics are
passive, a robustly stable interaction with the environment is guaranteed,
namely the system is stable both in free motion and in interaction phase (see
e.g. [15]).

While operating using admittance control, the interactive behaviour is
entirely determined by the choice of the admittance parameters, such as
inertia and stiffness. A specific set of parameters might not be optimal for
the whole duration of the task [16].

However, varying online the dynamic parameters can lead to the loss of
passivity [17] and thus to the implementation of unstable behaviours for HRC
[18].

This limitation onto the flexibility of admittance control is due to the
embodiment of passivity into the admittance dynamics. Enforcing the passivity
of the specific motion poses much tighter restrictions compared to simply
requiring the passivity of the overall controlled system. Passivity itself, in
fact, does not depend on any given interaction dynamics, only onto the energy
flow in the system.

Following this line, the Time Domain Passivity Approach (TDPA) keeps track of
the energy flow through a power port of the system and exploits a variable
damper to compensate for possible energy production [19, 20]. However, the
passivating damper acts as a spurious dynamics that affects the desired
dynamic behavior. The problem of distributing the energy dissipated over the
different subspaces is tackled in [21]. Nevertheless, due to the lack of an
exciting input in the null space, the amount of energy that can be dissipated
is limited and it can be necessary to resort to a damping in the main task.

A different strategy was adopted in [17], [18] and [22], in which a variable
admittance controller was passively implemented by leveraging energy tanks.
Here, energy tanks [17] have been exploited in order to unbind passivity from
the specific admittance dynamics. This allows to maximise the flexibility of
the application while maintaining a passive energy balance. Nevertheless,
implementing a time-varying admittance dynamics can deplete the tank. Thus, it
can happen that no more energy is available for implementing the desired
behavior. Different solutions have been proposed in literature for facing this
issue. Authors of [17] and [23] design a specific additional damping term for
refilling the tank whenever passivity is threatened, [18] saturates the amount
of energy which can be extracted from the tank at a given time, while [22]
passively approximates the desired behaviour whenever the current energy level
is too low for implementing it. All of these solutions involve an
approximation of the desired dynamics, which can compromise the effectiveness
and efficiency of the application. In order to achieve a variable admittance
free of spurious limiting effects, it is important to separate the tank refill
procedure from the desired interaction dynamics.

In this paper, we propose a control architecture which exploits task
redundancy and energy tanks in order to faithfully reproduce a desired
behaviour while preserving a passive energy balance. By means of kinematic
decomposition and null space projection, we generate motions which are
kinematically decoupled from the main admittance task, and use them to store
energy in the tank for controlling the energy flow in a non-invasive way in
terms of task execution. This allows to implement a variable admittance
controller in a passive way without altering the implementation of the desired
behaviour.

Even if energy tanks have been previously exploited in a null-space scenario
in [24], they were utilised for passifying the dynamics implemented in a
hierarchy of null spaces; thus, the main goal was using the tank for
guaranteeing the passivity of the null space.

In this paper, we make use of the dynamics in the null space for harvesting
energy and refilling the tank. This novel approach exploits the null space of
the task for keeping the tank at an energy level sufficient for ensuring both
performances and the overall passivity of the system.

Thus, the contributions of this paper are:

  * •

A non-invasive control architecture capable of passively implementing a
variable admittance controller

  * •

A technique for exploiting the task redundancy of the robot in order to refill
the energy tank without compromising the execution of the main task

  * •

An experimental validation of the proposed architecture, both in simulation
and onto a real collaborative robot

The paper is organised as follows: in Sec. II the main problem addressed in
this paper is formulated. In Sec. III energy tanks are presented, alongside
their role in the implementation of a variable admittance controller. In Sec.
IV the exploitation of task redundancy for storing energy in the tank is
presented. Finally, in Sec. V the resulting architecture is experimentally
validated onto a UR10e manipulator, while in Sec. VI conclusions are drawn and
future works are discussed.

##  II Problem Statement

Consider a fully actuated and velocity controlled $n$-DOFs manipulator that
can be modelled by the following kinematic model:

$\dot{x}=J(q)u$ (1)

where $q\in\mathbb{R}^{n}$ is the vector of joint variables,
$u\in\mathbb{R}^{n}$ is the control input, $x\in\mathbb{R}^{m}$ the pose of
the end-effector and $\dot{x}\in\mathbb{R}^{m}$ its velocity, both expressed
in operational space, while $J(q)\in\mathbb{R}^{m\times n}$ is the Jacobian
matrix.

We consider a human and a robot physically collaborating for executing a task.
The physical interaction between the robot and the human is regulated by means
of a variable admittance controller in order to make the collaboration safe
and efficient [18]. The admittance dynamics governs only a given subset of the
workspace of dimension $m_{1}<m$, meaning that the interaction task takes
place only onto certain operational directions. For tasks of simple nature,
this is most often sufficient.

The interaction task is given by $x_{1}=f_{1}(q)$, where
${x_{1}\in\mathbb{R}^{m_{1}}}$ and $f_{1}$ is the forward kinematic mapping
that relates the task variable with the joint variables. By differentiating,
it follows that

$\dot{x}_{1}=J_{1}(q)\dot{q}\,,\,J_{1}(q)=\frac{\partial f_{1}}{\partial q}$
(2)

where $J_{1}\in\mathbb{R}^{m_{1}\times n}$ is the analytic task Jacobian,
$\dot{q}\in\mathbb{R}^{n}$ are the joint velocities and $\dot{x}_{1}$ are the
operational task velocities along the considered directions. We now assume to
have a certain degree of kinematic redundancy w.r.t. the task, i.e. task
redundancy, meaning that $m_{1}<n$. Then, the control input $u=\dot{q}$
implementing the task in (2) can be synthesized as

$\dot{q}=J_{1}^{+}(q)\dot{x}_{1}+(I-J_{1}^{+}(q)J_{1}(q))z$ (3)

where $J_{1}^{+}\in\mathbb{R}^{n\times m_{1}}$ is the Moore-Penrose pseudo-
inverse [25] of $J_{1}$, while $z\in\mathbb{R}^{n}$ are joint velocities which
get projected in the null space of the task.

Figure 1: The admittance control architecture. We define as $\dot{q}_{d}$ the
commanded input to the velocity controller, while $\dot{q}_{c}$ represent the
velocity set point imposed to each joint by the robot actuation. We assume
that the low-level controllers of the robot are such that
$\dot{q}_{d}=\dot{q}$.

The admittance controller architecture is portrayed in Fig. 1 and the
controlled dynamic behaviour is represented by:

$M(x_{1},t)\ddot{x}_{1}+D(x_{1})\dot{x}_{1}=GF_{e}$ (4)

where $M(x_{1},t),D(x_{1},t)\in\mathbb{R}^{m_{1}\times m_{1}}$ are the
symmetric positive definite inertia matrix and damping matrix.
$F_{e}\in\mathbb{R}^{m}$ is the force the human is applying on the end-
effector. $G\in\mathbb{R}^{m_{1}\times m}$ is a selection matrix that extracts
the components of $F_{e}$ corresponding to the admittance control directions.
The admittance dynamics (4) is the most commonly used in human robot
collaboration. All the results in the paper can be easily extended to more
complex dynamics.

In order to cope with the loss of passivity due to the variability of the
admittance parameters, a tank based admittance control will be implemented.
Our goal is to exploit the redundancy of the robot with respect to the task
for refilling the energy tank. Specifically, we aim at exploiting the null-
space motions for dissipating the required energy, without altering the
desired execution of the main task. This allows us to obtain a flexible and
robust interactive behaviour without compromising the nominal execution of the
task, thus enhancing the performance of the application.

##  III Tank-based admittance control

In this section we present how to exploit energy tanks [17] for reproducing a
variable admittance dynamics on the robot primary task following the approach
presented in [18].

Energy tanks are virtual energy reservoirs, which store the energy dissipated
by the system for future usage. They can generally be represented by

$\begin{cases}\dot{x}_{t}(t)=u_{t}(t)\\\ y_{t}(t)=\frac{\partial T}{\partial
x_{t}}=x_{t}(t)\end{cases}$ (5)

in which $x_{t}(t)\in\mathbb{R}$ is the state of the tank,
$(u_{t}(t),y_{t}(t))\in\mathbb{R}\times\mathbb{R}$ is the power port handling
the energy flowing through the tank, while

$T(x_{t}(t))=\frac{1}{2}x_{t}(t)^{2}$ (6)

is the energy stored in the tank.

In particular, this energy can be reused for passively implementing any
desired control action.

The non-passive admittance dynamics (4) can be passively implemented by
augmenting it with an energy tank as follows:

$\begin{cases}M(x_{1},t)\ddot{x}_{1}+D(x_{1},t)\dot{x}_{1}=F_{1}\\\
\dot{x}_{t}(t)=\frac{\phi(t)}{x_{t}(t)}P_{D}(t)-\frac{\gamma(t)}{x_{t}(t)}P_{M}(t)\end{cases}$
(7)

in which $F_{1}=GF_{e}$, $F_{1}\in\mathbb{R}^{m_{1}}$, while

$P_{D}(t)=\dot{x}_{1}(t)^{T}D(t)\dot{x}_{1}(t)\quad
P_{M}(t)=\tfrac{1}{2}\dot{x}_{1}(t)^{T}\dot{M}(t)\dot{x}_{1}(t)$ (8)

$P_{D}(t)\geq 0$ is the power dissipated by the admittance dynamics, that
fills the tank. $P_{M}(t)$ is sign indefinite and it is the power required for
the varying the inertia; it can either refill the tank (passive variation) or
extract energy from the tank (non passive variation).

We define two additional terms $\phi(t)$ and $\gamma(t)$ to enable/disable the
energy storing process. This serves to limit the energy intake by inserting an
upper bound, namely $T(x_{t}(t))\leq\overline{T}$. In fact, an excessive
amount of stored energy in the tank may lead to the implementation of
practically unstable behaviours [26]. This upper bound is application
dependant and is ensured by the presence of $\phi(t)\in\\{0,1\\}$ and
$\gamma(t)\in\\{0,1\\}$, whose values are defined as

$\phi=\begin{cases}1\quad\text{if $T(x_{t}(t))\leq\overline{T}$}\\\
0\quad\text{otherwise}\end{cases}$ (9)

which regulates the storage of dissipated energy, and

$\gamma=\begin{cases}0\quad\text{if $\dot{M}(t)\leq 0$}\\\
1\quad\text{otherwise}\end{cases}$ (10)

which always allows energy to be extracted from the tank when $\dot{M}(t)>0$,
while blocking the injection if $\dot{M}(t)\leq 0$.

In order to avoid singularities in (7), it is necessary that $x_{t}\neq 0$,
i.e. that some energy is always present in the tank. Formally, it is necessary
that $T(x_{t}(t))\geq\underline{\varepsilon}>0$ for all $t\geq 0$. Using (6)
with (5) and (7), it is easy to show that

$\dot{T}(x_{t}(t))=x_{t}(t)\dot{x}_{t}(t)=\phi(t)P_{D}(t)-\gamma(t)P_{M}(t)$
(11)

Using the augmented dynamics in (7) together with (11) it is possible to prove

######  Proposition 1.

If $T(x_{t})\geq\underline{\varepsilon}$ for all $t\geq 0$, then the system
(7) remains passive with respect to the pair $(F_{1}(t),\dot{x}_{1}(t))$.

The proof can be found in [18].

Thus, as long as a sufficient amount of energy is stored in the tank, it is
possible to reproduce any desired behaviour, even non-physical ones, in a
passive way. This allows us to vary online the dynamic parameters of the
admittance controller while preserving a robustly stable interaction with the
environment.

Nevertheless, the implementation of non passive behaviors (e.g. inertia
variation) depletes the tank. Thus, it can happen that there is not enough
energy in the tank for passively implementing the desired behavior. In this
case, see e.g.[17], the damping of the admittance dynamics is augmented for
refilling the tank. Such an action is effective but the price to pay is an
unwanted dynamic behavior (additional damping) that is perceived by the user,
undermining the quality of the interaction. This problem will be solved by
moving the damping injection in the null space, as shown in Sec. IV.

##  IV Null Space Refill

In this section we will present the proposed technique for exploiting task
redundancy in order to refill the energy tank without altering the nominal
behaviour of the robot.

First, we need to ensure that secondary motion does not affect the execution
of the main task, i.e. the two motions must be kinematically decoupled. To
ensure this, we perform the following coordinate transformation[27, 28] onto
(3):

$\displaystyle\dot{q}$
$\displaystyle=\begin{bmatrix}J_{1}(q)^{+}\,Z(q)^{T}\end{bmatrix}\begin{bmatrix}\dot{x}_{1}\\\
v_{2}\end{bmatrix}$ (12)

in which $Z(q)\in\mathbb{R}^{m_{2}\times n}$ is a full row rank null space
base matrix of $J_{1}(q)$ and can be easily obtained via singular value
decomposition (SVD) of $J_{1}(q)$. Finally, the self motion velocity
$v_{2}\in\mathbb{R}^{m_{2}}$ is computed as

$v_{2}=N(q)\dot{q}$ (13)

in which $N(q)=(Z(q)Z(q)^{T})^{-1}Z(q)$. We can now go ahead and define the
extended Jacobian of the system as

$\displaystyle J_{e}(q)$ $\displaystyle=\begin{bmatrix}J_{1}(q)\\\
N(q)\end{bmatrix}\,,\,J_{e}(q)^{-1}=\begin{bmatrix}J_{1}(q)^{+}\,\,Z(q)^{T}\end{bmatrix}$
(14)

and the extended task-space velocities as

$\displaystyle\dot{x}_{e}$ $\displaystyle=\begin{bmatrix}\dot{x}_{1}\\\
v_{2}\end{bmatrix}=J_{e}(q)\dot{q}$ (15)

and finally compute the velocity commands in the joint space implementing the
combined motions as

$\dot{q}=J_{e}(q)^{-1}\dot{x}_{e}$ (16)

In this way, we achieved the kinematic decoupling between the two velocities
$\dot{x}_{1}$ and $v_{2}$, namely $J_{1}(q)Z(q)^{T}v_{2}=0$ and
$N(q)J_{1}(q)^{+}\dot{x}_{1}=0$. A more in-depth explanation of this procedure
can be found in [28].

Following this procedure, we can then implement a secondary task whose
execution does not interfere with the primary one, exploiting the task
redundancy of the robot.

Since our goal is the implementation of a time-varying dynamics as the main
admittance task, we can design the secondary task as a supplement to the main
one, aimed at injecting energy in the tank whenever a refill is required.

We achieve this by introducing an extra dynamics onto the secondary motion
$v_{2}$. In particular, we can endow this dynamics with a damper and utilise
the energy dissipated by the secondary motion for refilling the tank. In this
way, there is no need to introduce spurious terms onto the main dynamics,
which can be faithfully reproduced.

We can perform this by further augmenting the dynamics in (7) as:

$\begin{cases}M(x_{1},t)\ddot{x}_{1}+(D(x_{1},t)+\Psi(t))\dot{x}_{1}=F_{1}\\\
\dot{x}_{t}(t)=\frac{\phi(t)}{x_{t}(t)}(P_{D}(t)+P_{N}(t))-\frac{\gamma(t)}{x_{t}(t)}P_{M}(t)\\\
\dot{v}_{2}=-D_{N}(t)v_{2}+F_{null}\end{cases}$ (17)

in which $D_{N}(t)\in\mathbb{R}^{m_{2}\times m_{2}}$, $D_{N}(t)\geq 0$ is the
damping term for the null space motion, $F_{null}\in\mathbb{R}^{m_{2}}$ is a
control force acting onto the null space coordinates, while

$P_{N}(t)=v_{2}(t)^{T}D_{N}(t)v_{2}(t)$ (18)

is the energy dissipated by the damped null motion. Through this augmentation,
we obtain that

$\dot{T}(x_{t}(t))=\phi(t)(P_{D}(t)+P_{N}(t))-\gamma(t)P_{M}(t)$ (19)

which shows that the energy dissipated by the secondary dynamics can be
utilised for refilling the tank and for implementing a non passive inertia
variation. In this way, we can passively implement a variable admittance
controller without introducing spurious elements in the desired admittance
dynamics.

The force $F_{null}(t)\in\mathbb{R}^{m_{2}}$ is activated when the energy of
the tank drops below a threshold $T^{*}<\bar{T}$ and is defined as

$F_{null_{i}}(t)=\begin{cases}h_{i}(t)&\quad\text{if $T((t))<T^{*}$}\\\
0&\quad\text{otherwise}\end{cases}\quad i=\\{1,\dots,m_{2}\\}$ (20)

in which $h_{i}(t)$ is appropriately designed for exciting the null dynamics
in order to produce motion and dissipate energy.

The time-varying positive definite damping matrix implemented in the null
dynamics is defined as $D_{N}(t)=d_{N}(t)I_{m_{2}}$, where

$d_{N}(t)=\begin{cases}max\left(\frac{\gamma
P_{M}-P_{D}}{v_{2}^{T}v_{2}},\delta\right)\quad&\text{if}\,\,T(t)=\underline{\varepsilon}\,\,\text{and}\,\,v_{2}\neq
0\\\ \,\,\delta&\text{otherwise}\end{cases}$ (21)

where $\delta>0$ is the minimum damping that is always implemented in the null
dynamics. The presence of a non zero damping makes the null space dynamics
output strictly passive and, therefore, stable [29].

Using the null space damping dynamics in (17) and in (21) it is possible to
ensure that the tank is never depleted if $v_{2}\neq 0$. In fact, as long as
$T(t)>T^{*}$, $F_{null}=0$ and the null space energy harvesting is not enabled
since the energy dissipated by the main task is enough for refilling the tank.
When $T(t)\leq T^{*}$, the null space dynamics is activated and an extra
dissipated power $P_{N}(t)=v_{2}^{T}d_{N}(t)v_{2}=v_{2}^{T}\delta v_{2}$ is
fed into the tank for further refilling it, without disturbing the main task.
When the tank reaches its minimum value $\underline{\varepsilon}>0$, using
(21), the damping of the null dynamics is tuned in such a way to have
$P_{N}(t)=v_{2}^{T}d_{N}(t)v_{2}\geq\gamma P_{M}-P_{D}$. Then, from (19) we
have that $\dot{T}\geq 0$ and, therefore, an increase of the energy in the
tank. Thus, the tank can never go below the minimum energy threshold, i.e. the
tank can never deplete.

By properly choosing the damping parameter $\delta>0$, it is possible to keep
the energy of the tank above $\underline{\varepsilon}$ and, therefore, to
avoid the velocity dependent damping reported in (21). Nevertheless, it can
happen that the minimum is reached and, if $v_{2}=0$ the necessary control
action cannot be implemented. Energy then needs to be recovered by adding an
extra damping to the main task. This is done through the term $\Psi=\psi
I_{m_{1}}$ where

$\psi(t)=\begin{cases}max(\frac{P_{M}-P_{D}}{\dot{x}_{1}^{T}\dot{x}_{1}},0)&\text{if}\,\,T(t)=\underline{\varepsilon}\,\,\text{and}\,v_{2}=0,\,\dot{x}_{1}\neq
0\\\ \,\,0&\text{otherwise}\end{cases}$ (22)

Notice that, if $\dot{x}_{1}=0$, $P_{M}=0$, thus no energy is extracted from
the tank. It is easy to see that this damping term plays the same role as the
null space damping term when $T(t)=\underline{\varepsilon}$ with the main
difference that it produces an unwanted effect on the main task. Nevertheless,
if the null space dynamics is properly designed, $\Psi$ is almost never
active.

Combining (17) with (19) we can finally prove the following.

######  Proposition 2.

If $T(x_{t})\geq\underline{\varepsilon}$ for all $t\geq 0$, then the system
(17) remains passive with respect to the pairs $(F_{1}(t),\dot{x}_{1}(t))$ and
$(F_{null}(t),v_{2}(t))$.

###### Proof.

Let us consider the following positive storage function

$S(\dot{x}_{1}(t),x_{t}(t),v_{2}(t))=H_{1}(\dot{x}_{1}(t))+T(x_{t}(t))+H_{2}(v_{2}(t))$
(23)

in which $H_{1}(\dot{x}_{1}(t))$ is defined as

$H_{1}(\dot{x}_{1}(t))=\frac{1}{2}\dot{x}_{1}^{T}(t)M(t)\dot{x}_{1}(t)$ (24)

while $H_{2}(v_{2}(t))$ as

$H_{2}(v_{2}(t))=\frac{1}{2}v_{2}^{T}(t)v_{2}(t)$ (25)

and $T(x_{t}(t))$ as in (6). From now onward, we indicate as $S(t)$,
$H_{1}(t)$, $H_{2}(t)$ and $T(t)$ the values of $S(\dot{x}(t),x_{t}(t))$,
$H_{1}(\dot{x}_{1}(t))$, $H_{2}(v_{2}(t))$ and $T(x_{t}(t))$ at time $t$ for
the sake of readability. By differentiating, we obtain:

$\dot{S}(t)=\dot{H}_{1}(t)+\dot{T}(t)+\dot{H}_{2}(t)=\dot{x}_{1}^{T}F_{1}-(1-\phi(t))P_{D}(t)+\\\
-(1-\phi(t))P_{N}(t)+(1-\gamma(t))P_{M}(t)+v_{2}^{T}F_{null}$ (26)

from which, since $\phi(t)\in\\{0,1\\}$, $P_{D}(t)\geq 0$, $P_{N}(t)\geq 0$,
we have that

$\dot{x}_{1}^{T}F_{1}+v_{2}^{T}F_{null}\geq\dot{H}_{1}(t)+\dot{T}(t)+\dot{H}_{2}(t)-(1-\gamma(t))P_{M}(t)$
(27)

From (8) and (10), we get that if $\dot{M}(t)\leq 0$ then $P_{M}=0$.
Otherwise, if $\dot{M}(t)>0$ then $(1-\gamma(t))P_{M}=0$. Thus, we obtain that

$\dot{x}_{1}^{T}F_{1}+v_{2}^{T}F_{null}\geq\dot{H}_{1}(t)+\dot{T}(t)+\dot{H}_{2}(t)$
(28)

which implies

$\int_{0}^{t}(\dot{x}_{1}^{T}(\tau)F_{1}(\tau)+v_{2}(\tau)^{T}F_{null}(\tau))d\tau\geq\\\
H_{1}(t)-H_{1}(0)+T(t)-T(0)+H_{2}(t)-H_{2}(0)\\\ \geq-H_{1}(0)-T(0)-H_{2}(0)$
(29)

thus proving passivity. ∎

######  Remark.

Notice that, even if the two motions $\dot{x}_{1}$ and $v_{2}$ are
kinematically decoupled, the overall passivity is not guaranteed a priori,
since the two dynamics are energetically coupled via the energy tank.

Passivity makes the overall system robust to external disturbances [15], that
can happen both in the main and in the null space dynamics. Passivity can only
be proven with respect to the two pairs. Nevertheless, from the kinematic
decoupling in (12) we have that

$\dot{q}=J_{1}(q)^{+}\dot{x}_{1}+Z(q)^{T}v_{2}$ (30)

Taking (2) into account, we obtain that

$\dot{x}_{1}=J_{1}(q)\dot{q}+J_{1}(q)Z(q)^{T}v_{2}$ (31)

in which, from the previous kinematic decoupling, $J_{1}(q)Z(q)^{T}v_{2}=0$.
In this way, the contribution of the pair $(F_{null}(t),v_{2}(t))$ does not
affect the implementation of $\dot{x}_{1}(t)$. Therefore, since the two
dynamics are passive w.r.t. their power ports and are passively interconnected
via the energy tank, the overall passivity is preserved.

Thus, we are able to preserve a passive energy flow without having to
introduce additional damping terms onto the main motion, guaranteeing at the
same time both passivity and efficiency. It should be noticed that the energy
harvesting dynamics is a simple mass-damper dynamics and, as well known (see
e.g. [15]), it is passive with respect to the pair $(F_{null},v_{2})$. Thus
the secondary task dynamics is bounded input/bounded output stable and, when
$F_{null}=0$ it, it is asymptotically stable [15].

##  V Simulations and Experiments

The experimental validation of the architecture has been conducted onto a
Universal Robot 10e manipulator, equipped with an on-board 6-axis force/torque
(F/T) sensor. Both the robot and the sensor run at a frequency of $500$Hz.

A first validation experiment was performed in a simulated environment, while
an equivalent version of it was implemented on the real manipulator.

###  V-A Simulations

(a)

(b)

Figure 2: Velocity of the end effector along the $z$ axis using damping
injection (a) and null-space refill (b) in red and the desired motion in blue.
The dotted line at $t=34s$ in (a) represent the starting time of the damping
injection.

(a)

(b)

Figure 3: Evolution of the energy in the tank using damping injection (a) and
null-space refill (b).

In the simulation, the robot is employed to reproduce the behaviour in (4)
while aiming at preserving a desired amount of energy $T^{*}=25J$ in the tank.
This is first accomplished using the standard tank-based admittance control in
(7), then with the proposed null-space refill technique in (17).

We assume the admittance task takes place only along the translational
directions of motion. Thus, the primary task $x_{1}$ has dimension $m_{1}=3$
and its Jacobian $J_{1}$ is equivalent to the first $m_{1}$ rows of the
geometric Jacobian $J$. Since $m=n=6$, we can exploit the remaining $m_{2}=3$
DOFs for implementing the secondary task $x_{2}$.
Under these conditions, the selection matrix $G$ becomes

$G=\begin{bmatrix}\mathbb{I}_{3}\quad\mathbb{O}_{3}\\\ \end{bmatrix}$ (32)

where $\mathbb{I}_{3}$ is the 3D identity matrix and $\mathbb{O}_{3}$ is the
3D zero matrix. The inertia and damping matrices $M(x_{1},t)$ and $D(x_{1},t)$
are initialised as diagonal matrices, whose elements have respectively the
value of $6kg$ and $0.75\frac{Ns}{m}$.

The external force $F_{e}$ presents only one non-null component $F_{z}$ with
magnitude $2N$, applied along the vertical direction. The force cyclically
inverts its sign. Whenever this happens, the value of
$M(x_{1},t)=diag(m_{i}(t))$ is changed, increasing or decreasing its elements
by $3kg$ at each cycle.

As we can see from (8) and (10), increasing the inertia leads to an extraction
of energy from the tank, while no energy is injected if the inertia decreases.
Thus, since we aim at an energy level of $T^{*}$, a technique for refilling
the tank is required.

First, the tank is refilled via the standard damping injection. Whenever the
energy level $T(x_{t}(t))$ drops below $T^{*}$, the value of the elements of
$D(x_{1},t)$ is increased to $4\frac{Ns}{m}$.

Figure 4: Velocities of the secondary motion using null space refill.

As can be noticed in Fig. 2a, this solution severely affects the execution of
the main task, resulting in a rough approximation of the desired motion after
the damping injection. Additionally, the energy level never rises back to
$T^{*}$, due to the slower evolving nature of the dynamics, meaning that the
additional damping would persist indefinitely (see Fig. 3a).

The same simulation is then conducted using the proposed null-space refill
technique. The null damping matrix $D_{N}(t)\in\mathbb{R}^{3\times 3}$ is
initialised as a diagonal matrix, with elements equal to $1\frac{Ns}{m}$. The
null force $F_{null}\in\mathbb{R}^{3}$ has components designed as periodic
functions $h_{i}$, namely

$h_{i}=\gamma_{i}|T(x_{t}(t))-T^{*}|(sin(\omega t))$ (33)

in which $\gamma_{i}\in\mathbb{R}$ is a proportional gain and
$\omega=1\frac{rad}{s}$. The gains are chosen as $\gamma_{1}=0$,
$\gamma_{2}=0.5$ and $\gamma_{3}=-0.5$. Notice from (20) that $F_{null_{i}}=0$
if no refill is needed.

To highlight the capabilities of the technique, we set as the only refilling
term in the tank the null power $P_{N}$, namely we impose $P_{D}=0$ in (17).

The results are showcased in Fig. 2b and Fig. 3b. Whenever the energy level in
the tank drops below $T^{*}$, the force $F_{null}$ is applied, allowing to
damp onto the secondary motion $v_{2}$. Even without $P_{D}$, the tank is
refilled up until the desired value $T^{*}$ after each extraction. After that,
$h_{i}=0\,N$, thus the null motion slowly stops, leading to $P_{N}=0$. The
generated null-space motions are shown in Fig. 4.

From the kinematic decoupling of $x_{1}$ and $v_{2}$, we achieve that the main
motion is unaffected by the secondary damped one, avoiding the introduction of
spurious terms in the main dynamics. At the same time, it is always possible
to inject energy in the tank, thus passivity is preserved at all times.

###  V-B Experiments

The experiment conducted onto the real robot is analogous to the second
simulation. Here, the human operator controls the manipulator by means of the
main admittance task, in order to paint lines on a paper sheet, using a brush
attached to the end effector, while motions in the null space of the task
serve the refill purpose. The operator is skilled and is aware of how the
robot will behave during the null motions.

The inertia, damping and null damping matrices are initialised with elements
equal to $15kg$, $40\frac{Ns}{m}$ and $7\frac{Ns}{m}$ respectively. The gains
$\gamma_{(.)}$ in (33) are chosen as $\gamma_{1}=\gamma_{2}=0$,
$\gamma_{3}=-0.5$, meaning the motion $v_{2}$ is restricted to the rotation of
the end effector along its $z$ axis. Due to the choice of (33), the null
motion only causes small deviations from the initial angular position of the
end effector. Thus, the operator is minimally affected during the task
execution. As in the simulations, the inertia matrix is changed according to
the sign of the force $F_{z}$, with variations of $\pm 5kg$.

Figure 5: Evolution of the energy in the tank during the experiment

As previously, energy is extracted from the tank for compensating the inertia
increase due to the change in orientation of the applied force. The activation
of the null space dynamics allows to keep on implementing the desired
dynamics. Thanks to the non-invasive nature of the motion, the operator is
unaffected by the energy injection process, while the null-space refill refill
ensures the preservation of passivity. The evolution of the energy in the tank
during the experiment is portrayed in Fig. 5.

##  VI Conclusions

In this paper we have proposed a control architecture which exploits both task
redundancy and energy tanks for passively implement a variable admittance
controller. Through kinematic decoupling, we can generate damped motions in
the null space of the main admittance task for refilling the energy tank
whenever needed, thus avoiding the introduction of spurious effects onto the
desired behaviour.

Given the projection-based nature of this approach, inequality and equality
constraints, such as joint position limits or maximum permitted values of
velocity and acceleration, cannot be incorporated. Future work aims at
extending the framework proposed in the paper for including robot and task
based constraints.

## References

  * [1] B. Siciliano, L. Sciavicco, L. Villani, and G. Oriolo, _Robotics: modelling, planning and control_. Springer Science & Business Media, 2010.
  * [2] C. Samson, B. Espiau, and M. L. Borgne, _Robot control: the task function approach_. Oxford University Press, Inc., 1991.
  * [3] O. Khatib, “A unified approach for motion and force control of robot manipulators: The operational space formulation,” _IEEE Journal on Robotics and Automation_ , vol. 3, no. 1, pp. 43–53, 1987.
  * [4] S. B. Slotine and B. Siciliano, “A general framework for managing multiple tasks in highly redundant robotic systems,” in _proceeding of 5th International Conference on Advanced Robotics_ , vol. 2, 1991, pp. 1211–1216.
  * [5] S. Chiaverini, “Singularity-robust task-priority redundancy resolution for real-time kinematic control of robot manipulators,” _IEEE Transactions on Robotics and Automation_ , vol. 13, no. 3, pp. 398–410, 1997.
  * [6] N. Mansard, A. Remazeilles, and F. Chaumette, “Continuity of varying-feature-set control laws,” _IEEE Transactions on Automatic Control_ , vol. 54, no. 11, pp. 2493–2505, 2009.
  * [7] F. Flacco and A. De Luca, “Fast redundancy resolution for high-dimensional robots executing prioritized tasks under hard bounds in the joint space,” in _2013 IEEE/RSJ International Conference on Intelligent Robots and Systems_ , 2013, pp. 2500–2506.
  * [8] B. Siciliano and J. . E. Slotine, “A general framework for managing multiple tasks in highly redundant robotic systems,” in _Fifth International Conference on Advanced Robotics ’Robots in Unstructured Environments_ , 1991, pp. 1211–1216 vol.2.
  * [9] C. Ott, A. Dietrich, and A. Albu-Schäffer, “Prioritized multi-task compliance control of redundant manipulators,” _Automatica_ , vol. 53, pp. 416–423, 2015.
  * [10] A. Escande, N. Mansard, and P.-B. Wieber, “Hierarchical quadratic programming: Fast online humanoid-robot motion generation,” _The International Journal of Robotics Research_ , vol. 33, no. 7, pp. 1006–1028, 2014.
  * [11] C. Ott, _Cartesian impedance control of redundant and flexible-joint robots_. Springer, 2008.
  * [12] A. Albu-Schaffer, C. Ott, U. Frese, and G. Hirzinger, “Cartesian impedance control of redundant robots: Recent results with the dlr-light-weight-arms,” in _2003 IEEE International conference on robotics and automation (Cat. No. 03CH37422)_ , vol. 3. IEEE, 2003, pp. 3704–3709.
  * [13] V. Lippiello and F. Ruggiero, “Exploiting redundancy in cartesian impedance control of uavs equipped with a robotic arm,” in _2012 IEEE/RSJ International Conference on Intelligent Robots and Systems_. IEEE, 2012, pp. 3768–3773.
  * [14] L. Villani and J. De Schutter, “Force control,” in _Springer Handbook of Robotics_ , B. Siciliano and O. Khatib, Eds. Cham: Springer International Publishing, 2016.
  * [15] C. Secchi, S. Stramigioli, and C. Fantuzzi, _Control of interactive robotic interfaces: A port-Hamiltonian approach_. Springer Science & Business Media, 2007, vol. 29.
  * [16] F. Dimeas and N. Aspragathos, “Online stability in human-robot cooperation with admittance control,” _IEEE Transactions on Haptics_ , vol. 9, no. 2, pp. 267–278, 2016.
  * [17] F. Ferraguti, N. Preda, A. Manurung, M. Bonfè, O. Lambercy, R. Gassert, R. Muradore, P. Fiorini, and C. Secchi, “An energy tank-based interactive control architecture for autonomous and teleoperated robotic surgery,” _IEEE Transactions on Robotics_ , vol. 31, no. 5, pp. 1073–1088, 2015.
  * [18] F. Ferraguti, C. T. Landi, L. Sabattini, M. Bonfè, C. Fantuzzi, and C. Secchi, “A variable admittance control strategy for stable physical human–robot interaction,” _The International Journal of Robotics Research_ , vol. 38, no. 6, pp. 747–765, 2019. [Online]. Available: https://doi.org/10.1177/0278364919840415
  * [19] J.-H. Ryu, D.-S. Kwon, and B. Hannaford, “Stability guaranteed control: Time domain passivity approach,” _IEEE Transactions on Control Systems Technology_ , vol. 12, no. 6, pp. 860–868, 2004.
  * [20] Y.-D. Kim, B.-J. Lee, J.-H. Ryu, and J.-H. Kim, “Landing force control for humanoid robot by time-domain passivity approach,” _IEEE Transactions on Robotics_ , vol. 23, no. 6, pp. 1294–1301, 2007.
  * [21] C. Ott, J. Artigas, and C. Preusche, “Subspace-oriented energy distribution for the time domain passivity approach,” in _2011 IEEE/RSJ International Conference on Intelligent Robots and Systems_. IEEE, 2011, pp. 665–671.
  * [22] F. Benzi, F. Ferraguti, G. Riggio, and C. Secchi, “An energy-based control architecture for shared autonomy,” _IEEE Transactions on Robotics_ , pp. 1–19, 2022.
  * [23] G. Riggio, C. Fantuzzi, and C. Secchi, “On the use of energy tanks for multi-robot interconnection,” in _2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2018, pp. 3738–3743.
  * [24] A. Dietrich, C. Ott, and S. Stramigioli, “Passivation of projection-based null space compliance control via energy tanks,” _IEEE Robotics and automation letters_ , vol. 1, no. 1, pp. 184–191, 2015.
  * [25] K. L. Doty, C. Melchiorri, and C. Bonivento, “A theory of generalized inverses applied to robotics,” _The International Journal of Robotics Research_ , vol. 12, no. 1, pp. 1–19, 1993.
  * [26] D. Lee and K. Huang, “Passive-set-position-modulation framework for interactive robotic systems,” _IEEE Transactions on Robotics_ , vol. 26, no. 2, pp. 354–369, 2010.
  * [27] J. Park, W. Chung, and Y. Youm, “On dynamical decoupling of kinematically redundant manipulators,” in _Proceedings 1999 IEEE/RSJ International Conference on Intelligent Robots and Systems. Human and Environment Friendly Robots with High Intelligence and Emotional Quotients (Cat. No. 99CH36289)_ , vol. 3. IEEE, 1999, pp. 1495–1500.
  * [28] Y. Michel, C. Ott, and D. Lee, “Passivity-based variable impedance control for redundant manipulators,” in _in Proc. IFAC World Congress (IFAC)_ , 2020\.
  * [29] A. Van der Schaft, _L2-gain and passivity techniques in nonlinear control_. Springer, 2000.


# Quantum state transfer in graphs with tails

Pierre-Antoine Bernard  Centre de Recherches Mathématiques, Université de
Montréal  Christino Tamon  Department of Computer Science, Clarkson University
Luc Vinet  Centre de Recherches Mathématiques, Université de Montréal  Weichen
Xie  Department of Mathematics, Clarkson University

###### Abstract

We consider quantum state transfer on finite graphs which are attached to
infinite paths. The finite graph represents an operational quantum system for
performing useful quantum information tasks. In contrast, the infinite paths
represent external infinite-dimensional systems which have limited (but
nontrivial) interaction with the finite quantum system. We show that perfect
state transfer can surprisingly still occur on the finite graph even in the
presence of the infinite tails. Our techniques are based on a decoupling
theorem for eventually-free Jacobi matrices, equitable partitions, and
standard Lie theoretic arguments. Through these methods, we rehabilitate the
notion of a dark subspace which had been so far viewed in an unflattering
light.

##  1 Introduction

Continuous-time quantum walk on graphs has been fundamental to quantum
information and computation. Bose [2] studied quantum communication protocols
on quantum spin chains using continuous-time quantum walk (see the
comprehensive survey by Kay [21]). On the algorithmic side, Farhi et al. [9]
designed a quantum algorithm (with provable speedup) for a famous Boolean
formula evaluation problem. A notable feature of their algorithm is that it
employs continuous-time quantum walk on finite graphs which are attached to
infinite paths (or tails). This idea was used subsequently by Childs [4] to
show that continuous-time quantum walk is a universal model for quantum
computation.

In this work, we explore quantum state transfer (which was the original
problem studied by Bose [2]) on finite graphs which are attached to infinite
paths (as considered by Farhi et al. [9]). We view the finite graph, on one
hand, to represent our internal quantum system for performing basic quantum
information tasks. On the other hand, we view the attached infinite paths as a
model of an external infinite-dimensional quantum system which has limited
(but potentially destructive) interaction with our system. The main question
which we investigate here is if our quantum protocols can still work in the
presence of this infinite-dimensional system. We provide an affirmative answer
to this question.

Our main result shows that, under modest conditions, if perfect state transfer
occurs in a finite graph, then perfect state transfer can still occur in the
finite graph even when infinite paths are attached. The main technique we
employ is based on a decoupling theorem for eventually-free Jacobi matrices as
stated by Golinskii [17]. This technique shows that the notion of a dark
subspace is useful as a tool to construct protected computational subspace.
This is in contrast to previous works which tried to mitigate the existence of
these dark subspaces [23].

A second technique we use involves basic representation theory of the Lie
algebra $\mathfrak{sl}_{2}{\mathbb{C}}$. This allows us to construct perfect
state transfer in the Cartesian square of Krawtchouk chains (or quotients of
the $n$-cube) and the $n$-cube itself when both are attached to an infinite
tail. These constructions exhibit perfect state transfer between multiple
pairs of quantum states on the same graph. Through these, we establish
connections between the dark subspaces and the walk modules of the Terwilliger
algebra of the $n$-cube (see [28]).

Finally, we utilize the dual-rail encoding useful for heralded perfect state
transfer in quantum spin chains (see [3, 21]). This method exploits the
presence of an anti-symmetric subspace in our graphs with tails. We view this
method in the context of a Cartesian product a perfect state transfer graph
$G$ with $K_{2}$. This allows us to protect any graph with perfect state
transfer from an infinite tail probe by simply “doubling” the finite graph.

##  2 Preliminaries

We review some basic notation and terminology which will be used throughout.
The set of integers is denoted $\mathbb{Z}$ while $\mathbb{Z}^{+}$ denotes the
set of positive integers.

The all-one $n\times m$ matrix is denoted $J_{n,m}$, for $n,m\geq 1$; we
simply use $J_{n}$ if $n=m$. The identity matrix of order $n$ is denoted
$I_{n}$. Whenever the dimensions are clear from context, we omit them for
brevity. We use $\mathbbm{1}_{S}$ to denote the characteristic vector of a
subset $S$. The unit vectors are denoted $e_{j}$ or $e(j)$ (with an implied
dimension). The unit matrix $E_{j,k}$ (which is $e_{j}e_{k}^{T}$) is zero
everywhere except at entry $(j,k)$ where it is $1$ (again with implied
dimensions).

We adopt standard asymptotic notation where $o_{n}(f_{n})$ denote functions
$g_{n}$ for which $g_{n}/f_{n}\rightarrow 0$, $O_{n}(f_{n})$ denote functions
$g_{n}$ for which $g_{n}/f_{n}$ is bounded from above by a constant, as
$n\rightarrow\infty$; see Janson et al. [20].

###  2.1 Graphs

The graphs we study are mainly simple and undirected (unless stated
otherwise). For a graph $G$, we denote its vertex and edge sets as $V(G)$ and
$E(G)$, respectively. The adjacency matrix of $G$ is a matrix $A(G)$ whose
$(j,k)$ entry is $1$ if $(j,k)\in E(G)$ and $0$ otherwise. The neighborhood of
a vertex $u$ in $G$ is denoted $N_{G}(u)=\\{v\in V(G):(u,v)\in E(G)\\}$. The
degree $\deg(u)$ of vertex $u$ is the cardinality of $N_{G}(u)$. We use
standard notation to denote common families of graphs: $K_{n}$ for complete
graphs (cliques), $\overline{K}_{n}$ for the empty graphs (cocliques), $P_{n}$
for paths, $Q_{n}$ for the binary $n$-cubes. See Godsil and Royle [16] for
further background on graph theory.

Given two graphs $G$ and $H$, the join $G+H$ is the graph obtained by taking a
disjoint union of $G$ and $H$ and then adding all edges $(g,h)$ for every
$g\in G$ and $h\in H$. The adjacency matrix of $G+H$ is given by

$A(G+H)=\begin{pmatrix}A(G)&J_{n,m}\\\ J_{m,n}&A(H)\end{pmatrix}$

where $G$ has $n$ vertices and $H$ has $m$ vertices. The cone of a graph $G$
is given by $\widehat{G}:=K_{1}+G$. By extension, the $m$-cone of $G$ is given
by $\overline{K}_{m}+G$.

The one-sum of two graphs $G$ and $H$ at a vertex $u$ is obtained by
identifying a vertex of $G$ with a vertex of $H$; thus, $V(G)\cap
V(H)=\\{u\\}$. The adjacency matrix of this one-sum is given by

$\begin{pmatrix}A(G\setminus u)&\mathbbm{1}_{N_{G}(u)}&0\\\
\mathbbm{1}_{N_{G}(u)}^{T}&0&\mathbbm{1}_{N_{H}(u)}^{T}\\\
0&\mathbbm{1}_{N_{H}(u)}&A(H\setminus u)\end{pmatrix}.$

Let $G$ be a graph on $n$ vertices and let
$\mathcal{Y}=\\{H_{i}(r_{i}):i=1,\ldots,n\\}$ be a collection of rooted graphs
(where $r_{i}$ is a distinguished root vertex in $H_{i}$). The rooted product
of $G$ with $\mathcal{Y}$, denoted $G^{\mathcal{Y}}$, is a graph obtained from
the one-sum of $G$ with $H_{i}$ by identifying vertex $i$ of $G$ with vertex
$r_{i}$ in $H_{i}$, for each $i=1,\ldots,n$; see Godsil and McKay [14].

Given a graph $G=(V,E)$, a vertex partition $\pi=(V_{j})$ of $G$ is called
equitable if $V=\bigcup_{j}V_{j}$ is a disjoint union, each induced subgraph
$G[V_{j}]$ is $d_{j}$-regular for some $d_{j}$, and each induced bipartite
subgraph $G[V_{j},V_{k}]$ is $(d_{jk},d_{kj})$-biregular for some $d_{jk}$ and
$d_{kj}$. We call each $V_{j}$ a cell of the equitable partition $\pi$. The
partition matrix of $\pi$ is given by $Q=(q_{uj})$ where
$q_{uj}=\mathbbm{1}_{\\{u\in V_{j}\\}}\cdot|V_{j}|^{-1/2}$. Then, the quotient
graph $G/\pi$ is a weighted graph whose adjacency matrix is
$A(G/\pi)=Q^{\dagger}A(G)Q$. For a fixed vertex $u$ of $G$, the equitable
partition relative to $u$ is an equitable partition $\pi$ of $G$ where
$\\{u\\}$ is a cell of $\pi$. In the case where $A(G/\pi)$ is a symmetric
tridiagonal matrix (or Jacobi matrix) we say $\pi$ forms a distance partition
relative to $u$.

###  2.2 Linear operators

We will allow our graphs to be infinite with a countable vertex set (see [24,
25, 15]). A main example is the infinite path $P_{\infty}$ with
$\mathbb{Z}^{+}$ as vertices and with edges connecting consecutive positive
integers. The adjacency matrix of $P_{\infty}$ is the free Jacobi matrix
$J_{0}$ given by

$J_{0}=\begin{pmatrix}0&1&&&\\\ 1&0&1&&\\\ &1&0&1&\\\
&&&\vdots&\end{pmatrix}.$

A Jacobi matrix $J$ is called eventually-free if $J_{0}$ can be obtained from
$J$ by the removal of the first $k$ rows and $k$ columns, for some finite $k$.
In this case, we also say $J$ is an extension of $J_{0}$ (see Golinskii [17]).

Let $\\{G_{n}\\}$ be a family of infinite graphs where each $G_{n}$ is
parameterized by a finite subgraph of size $n$. As an example, consider the
infinite lollipop graph $L_{n}$ which is the one-sum of the complete graph
$K_{n}$ with the infinite path $P_{\infty}$ (see Figure 1). We say $G$ is
locally finite if $\deg(u)$ is finite for each $u\in V$. Let
$\deg(G)=\sup\\{\deg(u):u\in V\\}$.

We consider the complex separable Hilbert space $\ell^{2}(V)$ which is
equipped with the inner product $\langle x,y\rangle=\sum_{u\in
V}\overline{x}_{u}y_{u}$ for $x,y\in\mathbb{C}^{V}$ and an induced norm
$\lVert x\rVert_{2}=\sqrt{\langle x,x\rangle}$. Recall $\ell^{2}(V)$ consists
of vectors $x$ with $\lVert x\rVert_{2}<\infty$. A complete orthonormal system
for $\ell^{2}(V)$ is given by the standard basis $\\{e_{v}:v\in V\\}$.

The adjacency matrix $A$ of $G$ is defined on the basis vectors as
$Ae_{v}=\sum_{u\in V}a_{u,v}e_{u}$ (the sum converges if $G$ is locally
finite); or, $\langle e_{u},Ae_{v}\rangle=a_{u,v}$. If $\deg(G)<\infty$, then
the adjacency matrix $A$ is a bounded self-adjoint operator (see Mohar and
Woess [25]). We also say that the adjacency operator of $G$ admits a matrix
representation relative to the standard basis (see [1], section 26).

The spectrum $\sigma(A)$ of $A$ is the set of all $\lambda\in\mathbb{C}$ for
which $\lambda I-A$ is not invertible. The point spectrum $\sigma_{p}(A)$ is
the set of all $\lambda\in\mathbb{C}$ for which $\lambda I-A$ is not one-to-
one. Any element of $\sigma_{p}(A)$ is called an eigenvalue of $A$. The
continuous spectrum $\sigma_{c}(A)$ is the set of all $\lambda\in\mathbb{C}$
for which $\lambda I-A$ is a one-to-one mapping of $H$ onto a dense proper
subspace of $H$. If $A$ is bounded and self-adjoint, then
$\sigma(A)\subset\mathbb{R}$ and $\sigma(A)=\sigma_{p}(A)\cup\sigma_{c}(A)$;
that is, $A$ has no residual spectrum. Our primary sources for functional
analysis are [1, 27].

######  Theorem 1.

(Spectral theorem) If $A$ is a bounded self-adjoint operator on a complex
Hilbert space $H$, then there exists a unique resolution of the identity $E$
on the Borel subsets of $\sigma(A)$ which satisfies

$A=\int_{\sigma(A)}\lambda\ dE(\lambda).$

Moreover, if $f$ is a bounded Borel function on $\sigma(A)$, then there is a
linear operator $f(A)$ where

$\langle f(A)x,y\rangle=\int_{\sigma(A)}f(\lambda)dE_{x,y}(\lambda)$ (1)

for every $x,y\in H$, where $E_{x,y}(\omega)=\langle E(\omega)x,y\rangle$ is a
complex measure over the Borel subsets of $\sigma(A)$.

Based on (1), it is customary to adopt the notation

$f(A)=\int_{\sigma(A)}f\ dE.$

It is often convenient to assume the resolution $E$ of the identity is defined
over all Borel subsets of $\mathbb{C}$ by letting $E(\omega)=0$ if
$\omega\cap\sigma(A)=\emptyset$.

The following result is the basis of our main technique.

######  Theorem 2.

(see [1], Theorem 3, section 40) Let $\mathcal{H}$ be a complex separable
Hilbert space and let $A$ be a bounded self-adjoint operator on $\mathcal{H}$.
Let $W_{k}$ ($k=1,2,\ldots,m$) be pairwise orthogonal invariant subspaces of
$A$; that is, $\mathcal{H}=\bigoplus_{k=1}^{m}W_{k}$ and $AW_{k}\subset
W_{k}$, for every $k$. Let $P_{k}$ be the projection operator on $W_{k}$ and
$A_{k}$ be the restriction of $A$ to $W_{k}$. Then, for every
$\psi\in\mathcal{H}$, we have

$A\psi=\sum_{k=1}^{m}A_{k}P_{k}\psi.$

###  2.3 Quantum walk

Let $G=(V,E)$ be an infinite graph whose adjacency operator $A$ is a bounded
self-adjoint linear operator on $\ell^{2}(V)$. A continuous-time quantum walk
on $G$ is given by the unitary operator

$e^{-itA}=\int_{\sigma(A)}e^{-it\lambda}\ dE_{\lambda}.$

We say that a graph $G$ has perfect state transfer (adopting Bose [2]) between
vertices $u$ and $v$ if there is a time $\tau$ so that

$|\langle e_{v},e^{-i\tau A}e_{u}\rangle|=1.$

A family $\\{G_{n}\\}$ of graphs has asymptotically efficient perfect state
transfer (see Chen et al. [8]) between vertices $u$ and $v$ if there is a time
$\tau=n^{O(1)}$ so that

$|\langle e_{v},e^{-i\tau A(G_{n})}e_{u}\rangle|=1-o_{n}(1).$

##  3 Conical illusion

We begin by examining a small yet illustrative example of an infinite graph. A
vertex $u$ in a graph $G_{n}$ is called sedentary (see Godsil [13]) if for all
time $t$, we have

$|\langle e_{u},e^{-itA(G_{n})}e_{u}\rangle|=1-o_{n}(1).$

It is known that the (finite) clique $K_{n}$ is sedentary at any vertex. To
see this, note that the spectral decomposition of $A(K_{n})$ is given by
$A(K_{n})=(n-1)J/n-(I-J/n)$, which shows that

$e^{-itA(K_{n})}=e^{-it(n-1)}J/n+e^{it}(I-J/n).$

This immediately yields

$|\langle
e_{u},e^{-itA(K_{n})}e_{u}\rangle|=|e^{-it(n-1)}/n+e^{it}(1-1/n)|=1-o_{n}(1).$

We show that the clique is still sedentary even in the presence of an infinite
tail (see Figure 1).

$\ldots$ Figure 1: The infinite lollipop graph $L_{n}$. All shaded vertices
are sedentary.

######  Proposition 3.

For $n\geq 2$, let $L_{n}$ be the infinite graph that is the one-sum of the
clique $K_{n}$ and the infinite path $P_{\infty}$ at vertex $u$. Then, any
vertex $v\neq u$ of $K_{n}$ in $L_{n}$ is sedentary.

###### Proof.

Following Golinskii [17], we label the vertices of $K_{n}$ with
$1,2,\ldots,n$, where $n$ is the attachment vertex, and the vertices of
$P_{\infty}$ with the integers $n+1,n+2,\ldots$. The adjacency matrix of
$L_{n}$ is a bounded self-adjoint operator in $\ell_{2}(\mathbb{Z}^{+})$.
Relative to the standard basis $\\{e_{k}:k\in\mathbb{Z}^{+}\\}$, we have

$A(L_{n})=\begin{pmatrix}A(K_{n})&E_{n,1}\\\ E_{1,n}&J_{0}\end{pmatrix}$

where $J_{0}$ is the free Jacobi matrix. Now, define a new basis
$\\{\tilde{e}_{k}:k\in\mathbb{Z}^{+}\\}$ where $\tilde{e}_{k}=e_{k}$, for
$k=n,n+1,\ldots$, and

$\tilde{e}_{n-1}=\frac{1}{\sqrt{n-1}}\sum_{k=1}^{n-1}e_{k}$

and

$\tilde{e}_{k}=\frac{1}{\sqrt{n-1}}\sum_{j=1}^{n-1}\zeta_{n-1}^{(j-1)k}e_{j}\
\hskip 14.45377pt\ (k=1,\ldots,n-2)$

where $\zeta_{p}=e^{2\pi i/p}$ denotes the principal $p$-th root of unity. The
action of $A(L_{n})$ on the new basis is given by

$U^{-1}A(L_{n})U=\begin{pmatrix}-\mathbb{I}_{n-2}&O\\\
O&\tilde{J}_{0}\end{pmatrix}$

where $\tilde{J}_{0}$ is an eventually-free Jacobi matrix (of rank two) given
by

$\tilde{J}_{0}=\begin{pmatrix}n-2&\sqrt{n-1}&O\\\ \sqrt{n-1}&0&e_{1}^{T}\\\
O&e_{1}&J_{0}\end{pmatrix}.$ (2)

Here, $U$ is the unitary operator which maps $e_{k}$ to $\tilde{e}_{k}$ for
every $k=1,2,\ldots$. Thus,
$W_{0}=\operatorname{span}\\{\tilde{e}_{1},\ldots,\tilde{e}_{n-2}\\}$ and
$W_{\infty}=\operatorname{span}\\{\tilde{e}_{n-1},\tilde{e}_{n},\ldots\\}$ are
orthogonal invariant subspaces which span the entire space.

Finally, to see why any vertex $j\in\\{1,\ldots,n-1\\}$ in $K_{n}$ is
sedentary, observe that

$\langle
e_{j},e^{-itA(L_{n})}e_{j}\rangle=\frac{e^{it}}{n-1}\sum_{k=1}^{n-2}|\langle
e_{j},\tilde{e}_{k}\rangle|^{2}+O\left(\frac{1}{n-1}\right),$

which shows $|\langle e_{j},e^{-itA(L_{n})}e_{j}\rangle|=1-o_{n}(1)$ for all
$t$. ∎

The next result shows that even with an arbitrary but finite number of
infinite tails the clique is still sedentary. But, we make a slight shift in
our approach (which sheds light on the title of this section); see Figure 2.

######  Theorem 4.

Let $n$ and $m$ be positive integers where $n\geq 2$ and $m\geq 1$. Let $H$ be
the infinite graph obtained from the join $\overline{K}_{m}+K_{n}$ by
attaching separate infinite paths to each vertex of the coclique
$\overline{K}_{m}$. Then, any vertex of the clique $K_{n}$ is sedentary.

###### Proof.

The quotient of $H$ is the clique $K_{n}$ attached to a single infinite path
where each vertex of $K_{n}$ is connected to the first vertex of $P_{\infty}$
by an edge of weight $\sqrt{m}$. The proof now proceeds as in Proposition 3
without major changes. ∎

Observe that Proposition 3 is a corollary of Theorem 4 when $m=1$.

It seems curious to investigate sedentariness as it is the opposite of quantum
state transfer. Yet, as we will see, the above results reveal a dark subspace
which holds interesting properties.

$\ldots$$\ldots$$\ldots$$\ldots$ Figure 2: The join $\overline{K}_{m}+K_{n}$
attached to multiple tails. All shaded vertices are still sedentary.

##  4 Dark subspace transport over cones

We explore properties of a finite invariant subspace of graphs with tails.
First, observe that the clique $K_{n}$ is a cone over a smaller clique, that
is, $K_{n}=K_{1}+K_{n-1}$. Now, we consider the cone
$\widehat{G}_{n}:=K_{1}+G_{n}$ of an arbitrary $(n,d)$-regular graph $G_{n}$.
The following result shows that the one-sum of $\widehat{G}_{n}$ with
$P_{\infty}$ at the conical vertex inherits the state transfer properties of
$G_{n}$.

######  Theorem 5.

Let $G_{n}$ be a connected $d$-regular graph which admits efficient perfect
state transfer between vertices $u$ and $v$ at time $\tau$. Let $H$ be the
infinite graph that is the one-sum of the cone $\widehat{G}_{n}$ and the
infinite path $P_{\infty}$ at the conical vertex. Then, $H$ has asymptotically
efficient perfect state transfer between $u$ and $v$ at time $\tau$.

###### Proof.

Suppose the adjacency matrix of $G_{n}$ is diagonalized by the unitary matrix
$Z$, that is, $Z^{\dagger}A(G_{n})Z=\Lambda$, where
$\Lambda=\operatorname{diag}(\lambda_{1},\ldots,\lambda_{n})$ is the diagonal
matrix of the eigenvalues and the columns of $Z$ are eigenvectors of
$A(G_{n})$. Let $A(G_{n})=\sum_{k=1}^{n}\lambda_{k}z_{k}z_{k}^{\dagger}$ with
$\lambda_{n}=d$ and $z_{n}=\frac{1}{\sqrt{n}}\mathbbm{1}_{n}$. Similar to
Proposition 3, the adjacency matrix of $H$ can be decomposed into

$U^{-1}A(H)U=\begin{pmatrix}\Lambda_{0}&O\\\ O&\tilde{J}_{0}\end{pmatrix},\
\hskip 14.45377pt\ \mbox{ where }\ \ U=\begin{pmatrix}Z&O\\\
O&I\end{pmatrix}.$ (3)

Here, $U$ is the unitary change of basis transformation where
$\tilde{e}_{j}=Ue_{j}$, $j=1,2,\ldots$, shows the new basis vectors in terms
of the standard basis vectors. By the definition of $U$, notice that
$\tilde{e}_{j}=e_{j}$ whenever $j\geq n+1$. Also,
$\Lambda_{0}=\operatorname{diag}(\lambda_{1},\ldots,\lambda_{n-1})$ is a
diagonal matrix containing all non-principal eigenvalues (with multiplicities)
of $G_{n}$. The eventually-free Jacobi matrix $\tilde{J}_{0}$ is given by

$\tilde{J}_{0}=\begin{pmatrix}d&\sqrt{n}&O\\\ \sqrt{n}&0&e_{1}^{T}\\\
O&e_{1}&J_{0}\end{pmatrix}.$

Let $P$ denote the projection operator onto the subspace
$\operatorname{span}\\{\tilde{e}_{j}:j\geq n\\}$. From (3), we have

$\displaystyle\langle e_{v},e^{-i\tau A(H)}e_{u}\rangle$ $\displaystyle=$
$\displaystyle\langle e_{v},U\exp\left(-i\tau\begin{pmatrix}\Lambda_{0}&0\\\
0&\tilde{J}_{0}\end{pmatrix}\right)U^{-1}e_{u}\rangle$ $\displaystyle=$
$\displaystyle\langle e_{v},U\begin{pmatrix}e^{-i\tau\Lambda_{0}}&0\\\
0&e^{-i\tau\tilde{J}_{0}}\end{pmatrix}U^{-1}e_{u}\rangle.$

The last expression equals to

$\langle
e_{v},\sum_{j=1}^{n-1}e^{-i\tau\lambda_{j}}z_{j}z_{j}^{T}e_{u}\rangle+\langle
e_{v},UPe^{-i\tau\tilde{J}_{0}}PU^{-1}e_{u}\rangle.$

Therefore,

$\displaystyle\langle e_{v},e^{-i\tau A(H)}e_{u}\rangle$ $\displaystyle=$
$\displaystyle\langle
e_{v},\sum_{j=1}^{n-1}e^{-i\tau\lambda_{j}}z_{j}z_{j}^{\dagger}e_{u}\rangle+\langle
e_{v},z_{n}\rangle\langle z_{n},e^{-i\tau\tilde{J}_{0}}z_{n}\rangle\langle
z_{n},e_{u}\rangle$ $\displaystyle=$ $\displaystyle\langle e_{v},e^{-i\tau
A(G_{n})}e_{u}\rangle-\frac{e^{-i\tau d}}{n}+\frac{1}{n}\langle
z_{n}|e^{-i\tau\tilde{J}_{0}}|z_{n}\rangle$ $\displaystyle=$
$\displaystyle\langle e_{v},e^{-i\tau A(G_{n})}e_{u}\rangle+O(n^{-1}).$

This shows $|\langle e_{v},e^{-i\tau A(H)}e_{u}\rangle|=1-o_{n}(1)$. ∎

$\ldots$ Figure 3: A cone over the cube $Q_{n}$ attached to an infinite tail.
Asymptotically efficient perfect state transfer occurs between the shaded
antipodal vertices with fidelity $1-O(1/2^{n})$ at time $(\pi/2)n$.

######  Example 6.

The one-sum of the cone of the $n$-cube with $P_{\infty}$ at the conical
vertex has asymptotically efficient perfect state transfer between any pair of
antipodal vertices of $Q_{n}$ (see Figure 3). The fidelity of state transfer
is $1-O(1/2^{n})$ at the usual time of $(\pi/2)n$.

We remark that Theorem 5 allows for any other quantum state transfer tasks
(such as, fractional revival) provided the initial and target states have
negligible overlap with the principal eigenvector of the graph.

##  5 Decoupling

Proposition 3 offers another useful insight. The eventually-free Jacobi matrix
in the infinite lollipop graph has the quotient of the clique as its leading
principal submatrix. We generalize this to graphs with well-behaved quotients
(for example, distance-regular graphs). Our primary goal is still to
understand the structure of the underlying protected (dark) subspaces.

Let $G$ be a graph with adjacency matrix $A$ and let $v$ be one of its
vertices. The walk matrix of $G$ with respect to $v$ is defined as

$W_{G}(v)=\begin{pmatrix}e_{v}&Ae_{v}&A^{2}e_{v}&\ldots&A^{n-1}e_{v}\end{pmatrix}.$

Thus, the columns of the walk matrix generate the Krylov subspace of $A$
relative to the unit vector $e_{v}$. The vertex $v$ is called controllable if
$W_{G}(v)$ has full rank (see Godsil [12]).

The following result appeared in Golinskii [17]. We will provide an
alternative proof which illuminates the structure of the dark (protected)
subspace.

######  Theorem 7.

Let $G_{n}$ be a connected graph and let $v$ be one of its vertices. Let $H$
be the infinite graph that is the one-sum of a finite graph $G_{n}$ with the
infinite path $P_{\infty}$ at vertex $v$. Then, there is an invertible matrix
$U$ so that

$U^{-1}A(H)U=\begin{pmatrix}\Im_{v}&0\\\ 0&\tilde{J}_{0}\end{pmatrix}$

where $\dim(\Im_{v})=n-\operatorname{rank}(W_{G_{n}}(v))$ and $\tilde{J}_{0}$
is an eventually-free Jacobi matrix.

Moreover, if $G_{n}$ admits an equitable distance partition $\pi$ relative to
$v$ so that $A(G_{n}/\pi)$ is a Jacobi matrix, then the leading principal
submatrix of $\tilde{J}_{0}$ is $A(G_{n}/\pi)$.

###### Proof.

For brevity, let $A=A(G_{n})$. First, we show that we can construct an
extension $\tilde{J}_{0}$ of the free Jacobi matrix $J_{0}$. We apply the
Lanczos algorithm for tridiagonalizing a symmetric matrix starting with
$e_{v}$ (see Horn and Johnson [19], 3.5P5, page 221). This algorithm will find
an orthonormal basis for the Krylov subspace
$K=\\{e_{v},Ae_{v},\ldots,A^{n-1}e_{v}\\}$. Assume that $m=\dim K$ and let
$\\{\tilde{e}_{0},\ldots,\tilde{e}_{m-1}\\}$ be an orthonormal basis of $K$,
where $\tilde{e}_{0}=e_{v}$. Denote $\tilde{e}_{-1}$ as the unit vector
corresponding to the unique neighbor of $v$ on the infinite path. Then,

$A\tilde{e}_{j}=\operatorname{span}\\{\tilde{e}_{j-1},\tilde{e}_{j},\tilde{e}_{j+1}\\}\
\hskip 14.45377pt\ (j=0,\ldots,m-2)$

and

$A\tilde{e}_{m-1}=\operatorname{span}\\{\tilde{e}_{m-2},\tilde{e}_{m-1}\\}.$

This shows that the subspace spanned by $\tilde{e}_{0},\ldots,\tilde{e}_{m-1}$
and the standard basis $\\{e_{w}:w\in V(P_{\infty})\\}$ for $P_{\infty}$ is an
invariant subspace of $H$; moreover, the restriction of $H$ on this subspace
forms an extension $\tilde{J}_{0}$ of $J_{0}$ (because of the tridiagonal
structure imposed by the Krylov subspace).

It remains to show that the leading $m\times m$ principal submatrix of
$\tilde{J}_{0}$ is $A(G_{n}/\pi)$. By our assumption on $\pi$, we may write
$A(G_{n})$ in a tridiagonal block form:

$A(G_{n})=\begin{pmatrix}A_{1}&B_{1}^{T}&&&&\\\ B_{1}&A_{2}&B_{2}^{T}&&&\\\
&B_{2}&A_{3}&B_{3}^{T}&&\\\ &&&\vdots&&\\\
&&&&A_{m-1}&\mathbbm{1}_{N_{G_{n}}(v)}\\\
&&&&\mathbbm{1}_{N_{G_{n}}(v)}^{T}&0\end{pmatrix}.$

Here, the last row and column correspond to vertex $v$. Notice that each
$A_{i}$ is the adjacency matrix of a regular subgraph of $G_{n}$ and each
$B_{i}$ represents the incidence matrix between subgraphs $A_{i}$ and
$A_{i+1}$, where $B_{i}$ has constant row-sum and constant column-sum. Because
of these properties, it is easy to see that the Lanczos algorithm, starting
with $e_{v}$ (last row and column), will construct a basis
$\\{\tilde{e}_{0}=e_{v},\tilde{e}_{1},\ldots,\tilde{e}_{m-1}\\}$ so that the
action of $H$ on this basis is given by

$\begin{pmatrix}d_{1}&d_{1,2}&&&\\\ d_{2,1}&d_{2}&d_{2,3}&&\\\
&d_{3,2}&d_{3}&d_{3,4}&\\\ &&\vdots&&\\\ &&&d_{m-1}&1\\\
&&&|N(v)|&0\end{pmatrix}$

where $d_{i}$ is the degree of regular subgraph $G[V_{i}]$ and $d_{i,j}$
denotes the number of neighbors in $V_{j}$ of each vertex in $V_{i}$. After a
standard transformation, the previous matrix is equal to the adjacency matrix
of the symmetrized quotient of $G_{n}/\pi$. ∎

We refer to the finite invariant subspace of $H$ in Theorem 7 as the protected
(or dark) subspace of $H$. Using the above theorem, we observe that a random
graph offers no protection.

######  Corollary 8.

Let $G_{n}=G(n,1/2)$ be a random graph. Then, the one-sum of
$\widehat{G}_{n}=K_{1}+G_{n}$ with $P_{\infty}$ has no protected subspace
almost surely.

###### Proof.

This follows since a random graph $G(n,1/2)$ is controllable relative to
$\mathbbm{1}_{n}$ almost surely (see O’Rourke and Touri [26]). ∎

##  6 Dark subspace transport via equitable partitions

Using Theorem 7, we explore the dark subspaces induced by regular subgraphs
within the (equitable) distance partitions of graphs. Our goal is to show that
state transfer occurs within each local subgraph under suitable conditions.

Given a regular graph $G$, consider the graph $P_{m}(G)$ obtained by
connecting $m$ disjoint copies of $G$ in a series using the graph join
operator. So, the adjacency matrix of this graph is $I_{m}\otimes
A(G)+A(P_{m})\otimes J$. We now generalize this series graph by allowing $m$
(possibly distinct) regular graphs, $G_{0},G_{1},\ldots,G_{m-1}$ and denote
the resulting graph as $P_{m}(G_{0},\ldots,G_{m-1})$.

######  Theorem 9.

Let $\mathcal{G}_{n}=P_{m}(\\{u\\},G_{1},\ldots,G_{m-1})$ be a series graph.
Let $H$ be the infinite graph that is the one-sum of $\mathcal{G}_{n}$ and the
infinite path $P_{\infty}$ at $u$. If there is $G_{j}$, $j=1,\ldots,m-1$, with
perfect state transfer between its vertices $a$ and $b$ at time $\tau$, then
$H$ has asymptotic perfect state transfer between $a$ and $b$ at time $\tau$.

###### Proof.

We prove the claim by induction on $m$. The base case of $m=2$ is simply
Theorem 5. Next, we prove the case for $m=3$ (and leave the full inductive
argument as a straightforward exercise). Let
$\mathcal{G}_{n}=P_{3}(\\{u\\},G_{1},G_{2})$ where $G_{i}$ is a
$(n_{i},d_{i})$-regular graph. The adjacency matrix $A$ of $\mathcal{G}_{n}$
is given by

$A=\begin{pmatrix}A_{2}&J&0\\\ J&A_{1}&\mathbbm{1}_{V_{1}}\\\
0&\mathbbm{1}_{V_{1}}^{T}&0\end{pmatrix}.$

By Theorem 7, we know that

$A=\begin{pmatrix}\Im_{u}&O\\\ O&\tilde{J}_{0}\end{pmatrix},\ \hskip
14.45377pt\mbox{ where }\
\tilde{J}_{0}=\begin{pmatrix}d_{2}&\sqrt{n_{1}n_{2}}&0\\\
\sqrt{n_{1}n_{2}}&d_{1}&\sqrt{n_{1}}\\\ 0&\sqrt{n_{1}}&0\end{pmatrix}$

Suppose $z_{1}$ is an eigenvector of $A_{1}$ corresponding to a non-principal
eigenvalue $\lambda_{1}$ (that is, $\lambda_{1}<d_{1}$) and $z_{2}$ is an
eigenvector of $A_{2}$ corresponding to a non-principal eigenvalue
$\lambda_{2}$ (that is, $\lambda_{2}<d_{2}$). Then,

$(\lambda_{1}-A)\begin{pmatrix}0\\\ z_{1}\\\ 0\end{pmatrix}=0,\ \hskip
14.45377pt\ (\lambda_{2}-A)\begin{pmatrix}z_{2}\\\ 0\\\ 0\end{pmatrix}=0.$

This implies that $\Im_{u}$ is block diagonal. Therefore, for some invertible
matrix $U$, we have

$U^{-1}AU=\begin{pmatrix}\Im_{1}&O&O\\\ O&\Im_{2}&O\\\
O&O&\tilde{J}_{0}\end{pmatrix}$

So, asymptotic perfect state transfer occurs within each block (by a similar
argument to Theorem 5). ∎

$\ldots$ Figure 4: A complex Hermitian clique $K_{6}$ attached to the infinite
path $P_{\infty}$. The shaded vertices have asymptotically efficient universal
perfect state tranfer (PST between every pair).

######  Example 10.

Let $\vec{K}_{3}$ be the complex oriented clique of order $3$ whose adjacency
matrix is

$\begin{pmatrix}0&-i&i\\\ i&0&-i\\\ -i&i&0\end{pmatrix}.$ (4)

We consider the graph $H=P_{3}(K_{1},\vec{K}_{3},\vec{K}_{3})$ (see Figure 4).
By Theorem 9 and an observation in Cameron et al. [6], we may conclude that
each local $\vec{K}_{3}$ has asymptotically efficient universal perfect state
transfer.

##  7 Perfect state transfer in a dark subspace

In this section, we show that perfect state transfer (with unit fidelity) can
be engineered to occur in graphs with tails. Our techniques are primarily
based on the representation theory of the Lie algebra
$\mathfrak{sl}_{2}{\mathbb{C}}$ and the dual-rail encoding scheme in spin
chains.

We recall that the Cartesian product of two graphs $G_{1}$ and $G_{2}$,
denoted $G_{1}\Box G_{2}$, is a graph with vertex set $V(G_{1})\times
V(G_{2})$ where the pairs $(a_{1},a_{2})$ and $(b_{1},b_{2})$ are adjacent if
either $a_{1}=b_{1}$ and $(a_{2},b_{2})\in E(G_{2})$ or $(a_{1},b_{1})\in
E(G_{1})$ and $a_{2}=b_{2}$. The adjacency matrix of $G_{1}\Box G_{2}$ is
given by $A(G_{1})\otimes I+I\otimes A(G_{2})$. If the two graphs are equal,
we use $G^{\Box 2}$ to denote the Cartesian square.

###  7.1 Walk modules

The following example shows perfect pair state transfer (see Chen and Godsil
[7]) on $P_{3}^{\Box 2}$ in the presence of an infinite tail.

$3,3$$2,3$$3,2$$1,3$$2,2$$3,1$$1,2$$2,1$$1,1$$\ldots$ Figure 5: The fly-
swatter graph: $P_{3}^{\Box 2}$ attached to an infinite tail. Perfect state
tranfer occurs between $\frac{1}{\sqrt{2}}(e_{1,2}-e_{2,1})$ and
$\frac{1}{\sqrt{2}}(e_{2,3}-e_{3,2})$ at time $\pi/\sqrt{2}$.

######  Example 11.

Suppose the vertex set of $P_{3}$ is $\\{1,2,3\\}$ where $1$ and $3$ are the
leaves. Let $H$ be the one-sum of $P_{3}^{\Box 2}$ and $P_{\infty}$ at vertex
$(1,1)$ (see Figure 5). Let $e_{j,k}$ denote $e_{j}\otimes e_{k}$. We show
there is perfect state transfer between the states
$\tfrac{1}{\sqrt{2}}(e_{1,2}-e_{2,1})$ and
$\tfrac{1}{\sqrt{2}}(e_{2,3}-e_{3,2})$ at time $\pi/\sqrt{2}$. Consider a new
basis for $A(H)$. Let $\tilde{e}_{k}=e_{k}$, $k\geq 10$, correspond to
vertices of $P_{\infty}$, and let

$\displaystyle\tilde{e}_{9}$ $\displaystyle=e_{1,1}$
$\displaystyle\tilde{e}_{1}$
$\displaystyle=\tfrac{1}{\sqrt{3}}(e_{1,3}-e_{2,2}+e_{3,1})$
$\displaystyle\tilde{e}_{8}$
$\displaystyle=\tfrac{1}{\sqrt{2}}(e_{1,2}+e_{2,1})$
$\displaystyle\tilde{e}_{2}$
$\displaystyle=\tfrac{1}{\sqrt{2}}(e_{1,2}-e_{2,1})$
$\displaystyle\tilde{e}_{7}$
$\displaystyle=\tfrac{1}{\sqrt{6}}(e_{1,3}+2e_{2,2}+e_{3,1})$
$\displaystyle\tilde{e}_{3}$
$\displaystyle=\tfrac{1}{\sqrt{2}}(e_{1,3}-e_{3,1})$
$\displaystyle\tilde{e}_{6}$
$\displaystyle=\tfrac{1}{\sqrt{2}}(e_{2,3}+e_{3,2})$
$\displaystyle\tilde{e}_{4}$
$\displaystyle=\tfrac{1}{\sqrt{2}}(e_{2,3}-e_{3,2})$
$\displaystyle\tilde{e}_{5}$ $\displaystyle=e_{3,3}$

be the basis vectors for the finite graph. The subspaces
$W_{0}=\operatorname{span}\\{\tilde{e}_{1},\tilde{e}_{2},\tilde{e}_{3},\tilde{e}_{4}\\}$
and $W_{1}=\operatorname{span}\\{\tilde{e}_{k}:k\geq 5\\}$ are orthogonal and
invariant under $A(H)$. Under this new basis, we have

$A(H)=\begin{pmatrix}0&&&&\\\ &&1&&\\\ &1&&1&\\\ &&1&&\\\
&&&&\tilde{J}_{0}\end{pmatrix}$

where $\tilde{J}_{0}$ is an eventually-free Jacobi matrix. As the action of
$A(H)$ on the invariant subspace spanned by
$\\{\tilde{e}_{2},\tilde{e}_{3},\tilde{e}_{4}\\}$ is equivalent to the
adjacency matrix of $P_{3}$, it follows that perfect state transfer occurs
between $\tilde{e}_{2}$ and $\tilde{e}_{4}$ at time $\pi/\sqrt{2}$.

We now generalize the above example. For the $n$-cube $Q_{n}$, let $\pi$
denote the equitable partition whose cells correspond to the set of vertices
with the same Hamming weight. The quotient graph $Q_{n}/\pi$ is a weighted
path of length $n+1$ (also known as the Krawtchouk chain; see Christandl et
al. [5]).

As we will use some basic Lie theoretic arguments, we briefly recall some
relevant terminology; see [18, 10] for more background on Lie theory. The Lie
algebra $\mathfrak{sl}_{2}{\mathbb{C}}$ is the algebra of complex $2\times 2$
traceless matrices that is equipped with a bracket111The Lie bracket is
bilinear, anti-symmetric, and satisfies $[A,[B,C]]+[B,[C,A]]+[C,[A,B]]=0$.
operation $[A,B]=AB-BA$. A representation of $\mathfrak{sl}_{2}{\mathbb{C}}$
is a homomorphism
$\rho:\mathfrak{sl}_{2}{\mathbb{C}}\rightarrow\operatorname{End}(V)$ for some
vector space $V$ of finite dimension (here, $\operatorname{End}(V)$ is
equipped with the natural bracket).

######  Theorem 12.

For any integer $n\geq 2$, let $H_{n}$ be the infinite weighted graph that is
the one-sum of the Cartesian square $(Q_{n}/\pi)^{\Box 2}$ and the infinite
path $P_{\infty}$ at vertex $(0_{n},0_{n})$. Then, there exist multiple
perfect state transfer on $H_{n}$ at time $\pi/2$.

###### Proof.

The Clebsch-Gordan decomposition (see [18], appendix C) states that if
$\rho_{m}$ is an irreducible representation of $\mathfrak{sl}_{2}{\mathbb{C}}$
of dimension $m+1$, then a tensor product of two irreducible representations
can be decomposed into a direct sum of irreducible representations. In
particular, for any $n\geq 1$:

$\rho_{n}(M)\otimes I+I\otimes\rho_{n}(M)\ \cong\
\bigoplus_{k=0}^{n}\rho_{2n-2k}(M),\ \ \ \forall
M\in\mathfrak{sl}_{2}{\mathbb{C}}.$ (5)

To use (5), we observe there exists $M\in\mathfrak{sl}_{2}{\mathbb{C}}$ where
$\rho(M)\cong A(Q_{m}/\pi)$, for every $m\geq 2$. Recall that a basis for
$\mathfrak{sl}_{2}{\mathbb{C}}$ is given by

$\displaystyle X$ $\displaystyle=\begin{pmatrix}0&1\\\ 0&0\end{pmatrix},$
$\displaystyle Y$ $\displaystyle=\begin{pmatrix}0&0\\\ 1&0\end{pmatrix},$
$\displaystyle H$ $\displaystyle=\begin{pmatrix}1&0\\\ 0&-1\end{pmatrix}.$

If we let $M=X+Y$, then $\rho(M)=\rho(X)+\rho(Y)$. Under the basis of all
eigenvectors of $\rho(H)$, we have

$\displaystyle\rho(Y)=\begin{pmatrix}0&&&&\\\ 1&0&&&\\\ &1&0&&\\\
&&\vdots&&\\\ &&&1&0\end{pmatrix},\ \ \rho(X)=\begin{pmatrix}0&m&&&\\\
&0&2(m-1)&&\\\ &&0&3(m-2)&\\\ &&&\vdots&\\\ &&&&m\\\ &&&&0\end{pmatrix}.$

This shows that $\rho(M)\cong A(Q_{m}/\pi)$ by a standard basis change. Hence,
perfect state transfer occurs in each of the Krawtchouk chains in (5). ∎

Next, we show that the $n$-cube itself can be “immunized” against the infinite
tail. Recall that $\zeta_{n}=\exp(2\pi i/n)$ is the primitive $n$th root of
unity. It will be convenient to identify the vertices of the $n$-cube $Q_{n}$
with subsets of $\\{1,2,\ldots,n\\}$.

$111$$110$$101$$011$$100$$010$$001$$000$$\ldots$ Figure 6: The $3$-cube
attached to an infinite tail. Perfect state tranfer occurs between
$\frac{1}{\sqrt{3}}(e_{100}+\zeta e_{010}+\zeta^{2}e_{001})$ and
$\frac{1}{\sqrt{3}}(e_{011}+\zeta e_{101}+\zeta^{2}e_{110})$ at time $\pi/2$,
where $\zeta=\exp(2\pi i/3)$ is the primitive cube root of unity.

######  Theorem 13.

For integer $n\geq 2$, let $H_{n}$ be the infinite graph that is the one-sum
of the $n$-cube $Q_{n}$ and the infinite path $P_{\infty}$ at vertex $0_{n}$.
Then, perfect state transfer occurs in $H_{n}$ between the states

$\frac{1}{\sqrt{n}}\sum_{j=1}^{n}\zeta_{n}^{j-1}e(\\{j\\})\ \ \mbox{ and }\ \
\frac{1}{\sqrt{n}}\sum_{j=1}^{n}\zeta_{n}^{j-1}e([n]\setminus\\{j\\})$

at time $\pi/2$

###### Proof.

By Theorem 7, the infinite invariant subspace of $A=A(H)$ is the walk module
$U_{0}$ generated by $e_{\emptyset}$ (which corresponds to the vertex
$0_{n}$). Let $W_{d}$ be the set of vertices of $Q_{n}$ of Hamming weight $d$.
Thus,

$\displaystyle U_{0}$
$\displaystyle=\operatorname{span}\\{e(\emptyset),Ae(\emptyset),A^{2}e(\emptyset),\ldots\\}$
$\displaystyle=\operatorname{span}(\\{e_{\emptyset},\mathbbm{1}_{W_{1}},\mathbbm{1}_{W_{2}},\ldots,\mathbbm{1}_{W_{n}}\\}\cup\\{e_{u}:u\in
V(P_{\infty})\\}).$

The action of $A$ on $U_{0}$ is given by the eventually-free Jacobi matrix

${\left.\kern-1.2ptA\mathchoice{\vphantom{\big{|}}}{}{}{}\right|_{U_{0}}}=\begin{pmatrix}0&n&&&&&&\\\
1&0&n-1&&&&&\\\ &2&0&&&&&\\\ &\vdots&\vdots&\vdots&&&&\\\ &&&0&1&&&\\\
&&&n&0&1&&\\\ &&&&1&0&1&\ldots\\\ &&&&&\vdots&\vdots&\end{pmatrix}.$

Next, consider a state supported on the singleton subsets of $Q_{n}$ which is
defined as

$\psi_{1}:=\sum_{j=1}^{n}\zeta_{n}^{j-1}e(\\{j\\}).$

and its walk module

$U_{1}=\operatorname{span}\\{\psi_{1},A\psi_{1},A^{2}\psi_{1},\ldots\\}.$

It is clear that $U_{1}$ is an invariant subspace of $A$ and that
$U_{1}\subset U_{0}^{\perp}$. The latter follows as $A$ is self-adjoint and
$\psi_{1}$ is orthogonal to $\mathbbm{1}_{W_{1}}$. We now show that
$\dim(U_{1})=n-1$ and

${\left.\kern-1.2ptA\mathchoice{\vphantom{\big{|}}}{}{}{}\right|_{U_{1}}}\
\cong\ \begin{pmatrix}&n-2&&&\\\ 1&&n-3&&\\\ &2&&\ldots&\\\ &&\vdots&&\\\
&&&&1\\\ &&&n-2&\end{pmatrix}.$ (6)

To see this, consider the set $\\{\psi_{1},\psi_{2},\ldots,\psi_{n-1}\\}$ of
orthogonal basis vectors for $U_{1}$, where

$\psi_{k}=\sum_{\begin{subarray}{c}S\subset[n]\\\
|S|=k\end{subarray}}\alpha(S)e(S),\ \ \mbox{ where }\ \ \alpha(S)=\sum_{j\in
S}\zeta_{n}^{j}.$

Then, for $k=1,\ldots,n-2$, we have

$\displaystyle\langle\psi_{k+1},A\psi_{k}\rangle$ $\displaystyle=k$
$\displaystyle\langle\psi_{k},A\psi_{k+1}\rangle$ $\displaystyle=n-k,$

which shows (6). Thus, it follows
${\left.\kern-1.2ptA\mathchoice{\vphantom{\big{|}}}{}{}{}\right|_{U_{1}}}\cong
A(Q_{n-2}/\pi)$, where $\pi$ is the equitable partition whose cells are the
vertices with the same Hamming weight. Hence, perfect state transfer occurs in
$U_{1}$ from $n^{-1/2}\psi_{1}$ to $n^{-1/2}\psi_{n-1}$ at time $\pi/2$ as
antipodal perfect state transfer occurs in $A(Q_{n-2}/\pi)$ at that time. ∎

In the proof of Theorem 13, the infinite invariant subspace $U_{0}$ is related
to the primary module of the Terwilliger algebra of the $n$-cube (see
Terwilliger [28], Definition 7.2). Our dark subspaces correspond to the
irreducible modules orthogonal to this primary module.

We offer an alternative proof of Theorem 13 which emphasizes the underlying
connection with the Lie algebra $\mathfrak{sl}_{2}{\mathbb{C}}$.

######  Theorem 14.

For integer $n\geq 2$, let $H_{n}$ be the infinite graph that is the one-sum
of the $n$-cube $Q_{n}$ and the infinite path $P_{\infty}$ at vertex $0_{n}$.
Then, multiple perfect state transfer occur in $H_{n}$.

###### Proof.

Given the $n$-cube $Q_{n}$, recall the standard lowering $L_{n}$ and raising
$R_{n}$ operators on the lattice of subsets of $\\{1,2,\ldots,n\\}$. For
subsets $A,B\subset\\{1,2,\ldots,n\\}$, define
$(L_{n})_{A,B}=\mathbbm{1}_{\\{|A|=|B|+1\wedge B\subset A\\}}$ and
$R_{n}=(L_{n})^{T}$. Now, let $H_{n}=R_{n}L_{n}-L_{n}R_{n}$. Notice that
$A(Q_{n})=L_{n}+R_{n}$. Inductively, it can be shown that

$[R_{n},L_{n}]=H_{n},\ \hskip 7.22743pt\ [H_{n},R_{n}]=2R_{n},\ \hskip
7.22743pt\ [H_{n},L_{n}]=-2L_{n}.$

Thus, the homomorphism
$\rho:\mathfrak{sl}_{2}{\mathbb{C}}\rightarrow\operatorname{End}(V_{n})$, with
$|V_{n}|=2^{n}$, where $\rho(H)=H_{n}$, $\rho(X)=R_{n}$, and $\rho(Y)=L_{n}$,
is a representation of the Lie algebra $\mathfrak{sl}_{2}{\mathbb{C}}$ (where
$H,X,Y\in\operatorname{Mat}_{2}(\mathbb{C})$ are the standard basis of
$\mathfrak{sl}_{2}{\mathbb{C}}$). This allows us to employ the following
standard Lie theoretic argument (see [18, 10]).

The eigenvalues of $H_{n}$ are $\lambda=-n,-n+2,\ldots,n-2,n$. Let
$W_{\lambda}$ be the eigenspace of $H_{n}$ corresponding to eigenvalue
$\lambda$. By the properties of $\rho$ as a representation of
$\mathfrak{sl}_{2}{\mathbb{C}}$, if $z\in W_{\lambda}$, then $R_{n}z\in
W_{\lambda+2}$ (or $0$ if $\lambda=n$) and $L_{n}z\in W_{\lambda-2}$ (or $0$
if $\lambda=-n$). Now, let $z$ be an eigenvector in the maximum eigenspace
$W_{n}$. Consider the invariant subspace $K_{0}$ spanned by the following set
of orthogonal eigenvectors of $H_{n}$. Let $z_{k}=L_{n}^{k}z$,
$k=0,1,\ldots,n$, and set

$K_{0}=\operatorname{span}\\{z,L_{n}z,L_{n}^{2}z,\ldots,L_{n}^{n}z\\}.$

By definition, the action of $L_{n}$ on $K_{0}$ is given by $\langle
z_{j},L_{n}z_{k}\rangle=\mathbbm{1}_{\\{j=k+1\\}}$, while the action of
$R_{n}$ on $K_{0}$ is given by $\langle
z_{j},R_{n}z_{k}\rangle=k(n-k)\mathbbm{1}_{\\{j=k-1\\}}$. Therefore, the
action of $L_{n}+R_{n}$ on $K_{0}$ is similar to $A(Q_{n}/\pi)$ (a Krawtchouk
chain of length $n+1$). Next, we repeat the argument on $K_{0}^{\perp}$ to
extract additional Krawtchouk chains. This shows that the entire space $V_{n}$
can be decomposed into the invariant subspaces (or walk modules) as follows:

$V_{n}=\bigoplus_{\ell\geq 0}K_{\ell}.$

As the action of $L_{n}+R_{n}$ (or the adjacency operator of $Q_{n}$) on each
invariant subspace $K_{\ell}$ is similar to $A(Q_{d}/\pi)$, for some $d\leq
n$, perfect state transfer occur in all of these Krawtchouk chains. ∎

###  7.2 Dual-Rail Encoding

We describe a simple idea for constructing perfect state transfer in graphs
with tails based on the dual-rail encoding in spin chains (see Burgarth and
Bose [3], and Kay [21] for a relevant survey). Recall that the notation $e(x)$
denotes the unit vector corresponding to vertex $x$.

######  Theorem 15.

Let $G$ be a graph with perfect state transfer between vertices $u$ and $v$ at
time $\tau$. Let $H$ be the rooted product $P_{3}^{\mathcal{Y}}$ where
$\mathcal{Y}=\\{G_{0},P_{\infty},G_{1}\\}$ with $G_{0}$ and $G_{1}$ represent
two identical copies of $G$. Then, $H$ has perfect state transfer between the
states $\frac{1}{\sqrt{2}}(e(u_{0})-e(u_{1}))$ and
$\frac{1}{\sqrt{2}}(e(v_{0})-e(v_{1}))$ at time $\tau$, where $u_{0},v_{0}$
and $u_{1},v_{1}$ are vertices which correspond to the copies of $u,v$ in
$G_{0},G_{1}$, respectively.

$a_{4}$$b_{4}$$a_{3}$$b_{3}$$a_{2}$$b_{2}$$a_{1}$$b_{1}$$\ldots$$\sqrt{3}$$2$$\sqrt{3}$$\sqrt{3}$$2$$\sqrt{3}$
Figure 7: A rooted product $P_{3}^{\mathcal{Y}}$ where
$\mathcal{Y}=\\{\widetilde{Q}_{n},P_{\infty},\widetilde{Q}_{n}\\}$ and
$\widetilde{Q}_{n}$ is a Krawtchouk chain (quotient of the $n$-cube). Perfect
pair state tranfer occurs between $\frac{1}{\sqrt{2}}(e(a_{1})-e(b_{1}))$ and
$\frac{1}{\sqrt{2}}(e(a_{n})-e(b_{n}))$ at time $\pi/2$.

###### Proof.

Let $(b,w)$ denote the vertices in the two copies of $G$, where
$b\in\\{0,1\\}$ and $w\in V(G)$. Let $e_{0}=\begin{pmatrix}1\\\
0\end{pmatrix}$ and $e_{1}=\begin{pmatrix}0\\\ 1\end{pmatrix}$ be the standard
two-dimensional unit vectors. We show there is perfect state transfer in $H$
between the states $\frac{1}{\sqrt{2}}(e_{0}-e_{1})\otimes e(u)$ and
$\frac{1}{\sqrt{2}}(e_{0}-e_{1})\otimes e(v)$ at time $\tau$.

Let $q_{0}$ be the middle vertex of $P_{3}$ in the rooted product
$H=P_{3}^{\\{G_{0},P_{\infty},G_{1}\\}}$. Also, let $r\in V(G)$ be the
designated root vertex of $G$. Note that $A(H)$ is given by

$A(H)=\begin{pmatrix}A(G)&O&e(r)&\\\ O&A(G)&e(r)&\\\
e(r)^{T}&e(r)^{T}&0&e_{1}^{T}\\\ &&e_{1}&J_{0}\end{pmatrix}$

where the third row and column correspond to vertex $q_{0}$. Consider the
subspaces $W^{-}$ and $K$ defined as

$W^{-}=\operatorname{span}\left\\{\frac{1}{\sqrt{2}}(e_{0}-e_{1})\otimes
e(w):w\in V(G)\right\\}$

and

$K=\operatorname{span}\left\\{A(H)^{m}e(q_{0}):m=0,1,\ldots\right\\}.$

######  Claim 16.

$W^{-}$ is orthogonal to $K$.

###### Proof.

Let $W^{+}$ be a subspace defined as

$W^{+}=\operatorname{span}\left\\{\frac{1}{\sqrt{2}}(e_{0}+e_{1})\otimes
e(w):w\in V(G)\right\\}.$

Suppose the vertex set of $P_{\infty}$ is denoted as $\\{q_{n}:n\geq 0\\}$.
Let $W^{\infty}$ be defined as
$W^{\infty}=\operatorname{span}\\{e(q_{n}):n\geq 0\\}$. Notice that

$A(H)e(q_{0})=e(q_{1})+\frac{1}{\sqrt{2}}(e_{0}+e_{1})\otimes e(r).$

Therefore, we see that

$K=W^{+}+W^{\infty}.$

Each vector in $W^{-}$ is orthogonal to any vector in $W^{+}$ since
$\frac{1}{\sqrt{2}}(e_{0}\pm e_{1})$ form an orthogonal pair. Moreover, each
vector in $W^{-}$ is orthogonal to any $e(q_{n})$ since the vertices of
$G_{0},G_{1}$ and $P_{\infty}$ are disjoint from each other. ∎

######  Claim 17.

$W^{-}$ is an invariant subspace of $A(H)$ and the action of $A(H)$ restricted
to $W^{-}$ is equivalent to $A(G)$.

###### Proof.

The action of $A(H)$ on $\frac{1}{\sqrt{2}}(e_{0}-e_{1})\otimes e(w)$ is given
by $I_{2}\otimes A(G)$ (by the structure of the rooted product $H$). This
shows $W^{-}$ is an invariant subspace of $A(H)$ and that the action of $A(H)$
is equivalent to $A(G)$. ∎

The above two claims show that for some unitary matrix $U$ we have

$U^{-1}A(H)U=\begin{pmatrix}A(G_{n})&O\\\
O&{\left.\kern-1.2ptA(H)\mathchoice{\vphantom{\big{|}}}{}{}{}\right|_{K}}\end{pmatrix}.$

This shows that there is perfect state transfer between
$\frac{1}{\sqrt{2}}(e_{0}-e_{1})\otimes|u\rangle$ and
$\frac{1}{\sqrt{2}}(e_{0}-e_{1})\otimes|v\rangle$ at time $\tau$. ∎

We remark that the construction used in Theorem 15 applies also to the graph
$G\Box K_{2}$ whose adjacency matrix is $I_{2}\otimes A(G)+A(K_{2})\otimes I$
(that is, trading the zero matrix for the identity matrix).

##  8 Conclusions

This work was motivated by the following question: can state transfer occur in
a finite graph which is connected to an infinite graph? We show that the
answer is affirmative in graphs with tails. As such, our work was influenced
by Golinskii [17] who studied the spectra of graphs with tails. More
surprisingly, we found that perfect state transfer is possible in graphs with
tails. Our main observation is that state transfer can occur in the finite
invariant subspace obtained from the decoupling theorem for eventually-free
Jacobi matrices. It would be interesting to investigate state transfer (or
lack thereof) in the infinite invariant subspace. In fact, it is possible to
replace the infinite tail with an arbitrary (but suitably defined) finite
graph. We leave this for future work.

We conclude with the following open questions.

  1. 1.

The original motivation for this work is to investigate if spatial search
works on infinite graphs. Although this question remains open, the
corresponding problem for discrete-time quantum walk was studied by Konno et
al. [22].

  2. 2.

Are there deeper connections lurking between the dark subspaces studied here
and the non-primary modules of the Terwilliger algebra?

  3. 3.

Corollary 8 shows $\widehat{G}(n,1/2)$ has no dark subspace. But, what about
$G(n,1/2)$?

  4. 4.

What information about the dark (protected) subspace is revealed by scattering
(as employed by Farhi et al. [9])?

## Acknowledgments

Work partly done while the authors were participants of the workshop “Graph
Theory, Algebraic Combinatorics, and Mathematical Physics” at Centre de
Recherches Mathématiques (CRM), Université de Montréal. C.T. would like to
thank CRM for its hospitality and support during his sabbatical visit. W.X.
was supported by NSF travel grant DMS-2212755. We thank Chris Godsil for
helpful discussions.

## References

  * [1] N.I. Akhiezer, I.M. Glazman.  Theory of Linear Operators in Hilbert Space.  Dover, 1993.
  * [2] S. Bose.  Quantum communication through an unmodulated spin chain.  Physical Review Letters 91(20):207901, 2003.
  * [3] D. Burgarth, S. Bose.  Conclusive and arbitrarily perfect quantum state transfer using parallel spin chain channels.  Physical Review A 71:052315, 2005.
  * [4] A. Childs.  Universal Computation by Quantum Walk.  Physical Review Letters 102:180501, 2009.
  * [5] M. Christandl, N. Datta, T. Dorlas, A. Ekert, A. Kay, A. Landahl.  Perfect state transfer of arbitrary states in quantum spin networks.  Physical Review A 71:032312, 2005.
  * [6] S. Cameron, S. Fehrenbach, L. Granger, O. Hennigh, S. Shreshtha, C. Tamon.  Universal State Transfer on Graphs.  Linear Algebra and Its Applications 455:115-142, 2014.
  * [7] Q. Chen, C. Godsil.  Pair state transfer.  Quantum Information Processing 19, 321, 2020.
  * [8] X. Chen, R. Mereau, D. Feder.  Asymptotically perfect efficient quantum state transfer across uniform chains with two impurities.  Physical Review A 93:012343, 2016.
  * [9] E. Farhi, J. Goldstone, S. Gutmann.  A Quantum Algorithm for the Hamiltonian NAND Tree.  Theory of Computing 4, Article 8, p169-190, 2008.
  * [10] W. Fulton, J. Harris.  Representation Theory: A First Course.  Springer, 1991.
  * [11] C. Godsil.  Association Schemes.  unpublished notes, 2010.
  * [12] C. Godsil.  Controllable Subsets in Graphs.  Annals of Combinatorics 16:733-744, 2012.
  * [13] C. Godsil.  Sedentary quantum walks.  arxiv:1710.11192 [math.CO].
  * [14] C. Godsil, B. McKay.  A new graph product and its spectrum.  Bulletin of the Australian Mathematical Society 18:21-28, 1978.
  * [15] C. Godsil, B. Mohar.  Walk Generating Functions and Spectral Measures of Infinite Graphs.  Linear Algebra and Its Applications 107:191-206, 1988.
  * [16] C. Godsil, G. Royle.  Algebraic Graph Theory.  Springer, 2001.
  * [17] L. Golinskii.  Spectra of infinite graphs with tails.  Linear and Multilinear Algebra 64(11):2270-2296, 2016.
  * [18] B. Hall.  Lie Groups, Lie Algebras, and Representations, 2nd edition.  Springer, 2015.
  * [19] R. Horn, C. Johnson.  Matrix Analysis, 2nd edition.  Cambridge, 2013.
  * [20] S. Janson, T. Łuczak, and A. Ruciński.  Random Graphs.  Wiley, 2000.
  * [21] A. Kay.  Perfect, Efficient, State Transfer and Its Applications as a Constructive Tool.  International Journal of Quantum Information 8(4):641-676, 2010.
  * [22] N. Konno, E. Segawa, M. Štefaňák.  Relation between quantum walks with tails and quantum walks with sinks on finite graphs.  arXiv:2105.03111 [math-ph].
  * [23] T. Le, L. Donati, S. Severini, F. Caruso.  How to suppress dark states in quantum networks and bio-engineered structures.  Journal of Physics A: Mathematical and Theoretical 51(36):365306, 2018.
  * [24] B. Mohar.  The Spectrum of an Infinite Graph.  Linear Algebra and Its Applications 48:245-256, 1982.
  * [25] B. Mohar, W. Woess.  A Survey on Spectra of Infinite Graphs.  Bulletin of London Mathematical Society 21:209-234, 1989.
  * [26] S. O’Rourke, B. Touri.  On a Conjecture of Godsil Concerning Controllable Random Graphs.  SIAM Journal on Control and Optimization 54(6):3347-3378, 2016.
  * [27] W. Rudin.  Functional Analysis, 2nd edition.  McGraw-Hill, 1991.
  * [28] P. Terwilliger.  Distance-regular graphs, the subconstituent algebra, and the Q-polynomial property.  arXiv:2207.07747 [math.CO].