# Latent Code-Based Fusion: A Volterra Neural Network Approach

Sally Ghanem, Siddharth Roheda, and Hamid Krim
ECE Department, NCSU, Raleigh, NC, 27695

###### Abstract

We propose a deep structure encoder using the recently introduced Volterra
Neural Networks (VNNs) to seek a latent representation of multi-modal data
whose features are jointly captured by a union of subspaces. The so-called
self-representation embedding of the latent codes leads to a simplified fusion
which is driven by a similarly constructed decoding. The Volterra Filter
architecture achieved reduction in parameter complexity is primarily due to
controlled non-linearities being introduced by the higher-order convolutions
in contrast to generalized activation functions. Experimental results on two
different datasets have shown a significant improvement in the clustering
performance for VNNs auto-encoder over conventional Convolutional Neural
Networks (CNNs) auto-encoder. In addition, we also show that the proposed
approach demonstrates a much-improved sample complexity over CNN-based auto-
encoder with a superb robust classification performance.

###### Index Terms:

Sparse learning, Computer vision, Information fusion, Subspace clustering.

##  I Introduction

On account of recent advances in sensor technology, multimodal data has become
widely available and useful. Additional modalities can often provide
supplementary information about the targets/classes of interest. A principled
integration of multi-modal sensor data is expected to improve the quality of
extracted features. Multi-modal fusion has been extensively used in different
applications including but not limited to image fusion [1], target recognition
[2][3] [4], speaker recognition [5] and handwriting analysis [6]. In addition,
CNNs have been extensively utilized for multimodal data analysis as in [7],
[8],[9], and [10]. However, the complexity of implementing a multi-modal
fusion network still persists.
Convolutional Neural Networks (CNNs) have widely been adopted in deep learning
for analyzing visual images in many applications. These application include
but are not limited to image processing, segmentation, and segmentation.
However, the complexity and cost of implementing CNNs can be limiting in many
applications. The efficient and recently proposed Volterra Neural Networks
(VNNs) [11] was aimed to primarily address these limitations and also overcome
the CNN over parametrization problem. To control the non-linearities
intentionally induced in the network, a judicious setting of the degree of
interactions between the delayed input samples of the data is induced. The
cascaded implementation proposed in [11] has shown to significantly reduce the
number of parameters needed for training the network in comparison to
conventional neural networks. In addition to reducing the network complexity,
Volterra Neural Networks (VNNs) have a more tractable and comprehensible
structure. This represents a significant departure from the work in [12] and
[13], as the strategy of convolution together with an understanding of the
inherent complexity of a naive approach resulted in the success of this new
outlook. These prior approaches had limited the degree of the non-linearities
up to certain value to avoid the explosive complexity, but thereby defeating
the initial goal of overcoming the limitations of existing CNNs. The cascaded
implementation in [11] has been shown to alleviate this limitation through
applying the second order filter repeatedly applied until the desired order is
attained.
Inspired by the success of VNNs in deep learning [11], we propose an efficient
implementation of the Deep Multi-modal Subspace clustering[14], using Volterra
filters. More specifically, the CNNs are replaced with VNNs which controls the
introduced non-linearities via high order convolutions instead of using highly
non-linear activation functions as in [14] architecture. Moreover, we propose
additional techniques to significantly reduce the complexity of a VNN inspired
Multi-Modal Subspace Clustering Auto-Encoder as compared with [14] to a
fraction of the number of parameters used by CNNs while retaining a comparable
clustering performance.
The rest of the paper is organized as follows, in Section 2, we provide an
overview for DMSC [14], which is based on CNNs. In section 3, we provide the
problem formulation along with the our proposed approach, namely, Volterra
Multi-Modal Subspace Clustering Auto Encoder (VMSC-AE). In Section 4, we
present a substantiative validation along with experimental results of our
approach, while Section 5 provides concluding remarks.

##  II Affinity Fusion Deep Multimodal Subspace Clustering

In this Section, we provide a brief overview of the Affinity Fusion Deep
Multimodal Subspace Clustering (AFDMSC) which was proposed in [14]. AFDMSC
network is composed of three main parts: a multimodal encoder, a self-
expressive layer, and a multimodal decoder. The output of the encoder
contributes to a common latent space for all modalities. AFDMSC utilizes the
self-expressive property, which was presented in [15] and [16]. This property
ensures acquiring the latent space structure that reveals the relationships
between data points in each cluster. The self-representation property entails
the representation of each sample as a linear combination of all other samples
from the same subspace/cluster. The self-expressive property is enforced
through a fully connected layer between the encoder and the decoder results in
one common set of weights for all the data sensing modalities. The
reconstruction of the input data by the decoder, yields the following loss
function to secure the proper training of the self-expressive network,

$\begin{split}\min_{\mathbf{W}/w_{kk}=0}&\parallel\mathbf{W}\parallel_{2}+\frac{\gamma}{2}\sum_{t=1}^{T}\parallel\mathbf{X}(t)-\mathbf{X_{r}}(t)\parallel_{F}^{2}+\\\
&\frac{\mu}{2}\sum_{t=1}^{T}\parallel\mathbf{L}(t)-\mathbf{L}(t)\mathbf{W}\parallel_{F}^{2},\end{split}$
(1)

where $\mathbf{W}$ represents the parameters of the self expressive layer,
$\mathbf{X}(t)$ is the input to the encoder, $\mathbf{X_{r}}(t)$, denotes the
output of the decoder and $\mathbf{L}(t)$ denotes the output of the encoder.
$\mu$ and $\gamma$ are regularization parameters. An overview for the DMSC
approach is illustrated in Figure 1.

Figure 1: Deep Multimodal Subspace Clustering

.

##  III Volterra Filter Subspace Clustering

###  III-A Problem Formulation

We consider a set of data observations indexed by k = 1, 2, ….., n and assume
T data modalities, indexed by t = 1, 2, 3,….., T. Each data modality
$\mathbf{X}(t)=[\mathbf{x}_{1}(t)\ \mathbf{x}_{2}(t)\ .......\
\mathbf{x}_{n}(t)]\in\mathbb{R}^{m\times n}$. The goal is to partition
$\mathbf{X}(t)$ into clusters that can be well-represented by low-dimensional
subspaces. Mathematically, this is equivalent to partitioning $\mathbf{X}(t)$
as {$\mathbf{X}^{1}(t),\mathbf{X}^{2}(t),........,\mathbf{X}^{P}(t)$} of
[$n$], where $P$ is the number of clusters indexed by $p$, such that there
exist linear subspaces $\mathbf{S}^{p}(t)\subset\mathbb{R}^{m}$ with
dim($\mathbf{S}^{p}(t)$) $\ll m$.

###  III-B Volterra Filter Auto-encoder

In this section, we provide the fundamental concepts of our proposed approach
which we refer to as Volterra Multimodal Subspace clustering auto-encoder (or
VMSC). Our framework learns an efficient latent representation of multi-modal
data whose features are jointly captured by a union of subspaces. Our approach
was inspired by the Volterra series[17], which is a model for non-linear
behavior similar to the Taylor series. Volterra series represents a functional
expansion of non-linear and time-invariant systems. It differs from the Taylor
series in its ability to capture memory. In other words, Taylor series can be
used for approximating the response of a non-linear system if the output
depends strictly on the input at that particular time. In contrast to Volterra
series, whose output depends on the input to the system at all other times.
Volterra filters (VF) are based on the Volterra series, VF describe a non-
linear system via higher order convolutions. The relation between the output
and input of the Volterra filter can be expressed as follows,

$\begin{split}&\sum_{\tau_{1}=0}^{L-1}H^{1}_{\tau_{1}}x_{t-\tau_{1}}+\sum_{\tau_{1},\tau_{2}=0}^{L-1}H^{2}_{\tau_{1},\tau_{2}}x_{t-\tau_{1}}x_{t-\tau_{2}}+...\\\
&+\sum_{\tau_{1},\tau_{2},...,\tau_{k}=0}^{L-1}H^{k}_{\tau_{1},\tau_{2},...,,\tau_{k}}x_{t-\tau_{1}}x_{t-\tau_{2}}...x_{t-\tau_{k}}\end{split}$
(2)

where $L$ is the number of terms in the filter memory (also referred to as the
filter length), $H^{k}$ are the weights for the $k^{th}$ order term. The
linear term in the previous equation is actually similar to a convolutional
layer in CNNs. Generally speaking, non-linearities in CNNs are often
introduced by activation functions, and not in the convolutional layer, while
VNNs introduce non-linearities in the convolutional layers. Volterra Neural
Network (VNNs) has been recently proposed to control the non-linearities
introduced in the network and to overcome the CNN over parametrization
problem. The VF architecture introduces controlled non-linearities in the
Neural Networks in contrast to non-linear activation functions, which provide
infinite non-linearity into the neural network which can not be easily
truncated. Non-linear activation functions, such as Relu and Sigmoid, are
often utilized in CNNs to act as a gate in between the input of a neuron and
its output. However, in some cases, the unnecessary nonlinearities introduced
by those activation functions in CNNs induce useless or irrelevant information
to the network, which might confuse the classifier. In this work, we propose a
multi-modal autoencoder using the recently introduced Volterra Neural Networks
(VNNs) [11] to seek a latent representation of multi-modal data whose features
are jointly captured by a union of subspaces. More specifically, we replace
the CNNs in our network with VNNs to control the introduced non-linearities
and to non-linearly map the data points to a latent space that is well-adapted
to subspace clustering in an unsupervised manner. The VMSC exploits the self-
expressive property presented in [15] and [16] to acquire the latent space
structure that reveals the relationships between data points in each cluster.
In the following, we elaborate on the structure of the Volterra structure-
based multi-modal auto-encoder. As noted earlier for (AFDMSC)[14], the network
has 3 main components, namely a multi-modal encoder, a self-expressive layer,
and a multi-modal decoder.

The encoder in this work replaces the standard CNNs with the Volterra Neural
Networks (VNNs) developed in [11]. The multi-modal encoder consists of $T$
parallel Volterra NNs. Each branch of the encoder processes one of the
modalities and extracts relevant features. The $T$ feature maps are
subsequently concatenated, promoting the goal of obtaining a common latent
space. The second component of the auto encoder is the self-expressive layer,
the goal of which is to enforce the self-expressive property [15] among the
concatenated features. This is enforced by a fully connected layer which
operates on the concatenated output of the encoder. The last stage is the
decoder which reconstructs the input data from the self-expressive layers’
output. The objective functional sought through this approximation network is
reflected in Equation (3). A diagram showing our algorithm is depicted in
Figure 2.

$\begin{split}\min_{\mathbf{W}/w_{kk}=0}&\parallel\mathbf{W}\parallel_{1}+\frac{\gamma}{2}\sum_{t=1}^{T}\parallel\mathbf{X}(t)-\mathbf{X_{r}}(t)\parallel_{F}^{2}+\\\
&\frac{\mu}{2}\parallel\mathbf{L_{concat}}-\mathbf{L_{concat}}\mathbf{W}\parallel_{F}^{2},\end{split}$
(3)

where $\mathbf{X_{r}}(t)$ represents the reconstructed data corresponding to
modality $t$, and $\mathbf{L_{concat}}$ is the concatenation of
$\mathbf{L}(1),\mathbf{L}(2),...,\mathbf{L}(T)$, and $\mathbf{L}(t)$ is the
output of the encoder corresponding to modality $t$ . $\mathbf{W}$ is the
sparse weight function that ties the concatenated features. The above cost
function is optimized in Tensorflow using the adaptive momentum based gradient
descent method (ADAM) [18]. Under a suitable arrangement/permutation of the
data realizations, the sparse coefficient matrix $\mathbf{W}$ is an $n\times
n$ block-diagonal matrix with zero diagonals provided that each sample is
represented by other samples only from the same subspace. More precisely,
$\mathbf{W_{ij}}=0$ whenever the indices $i,j$ correspond to samples from
different subspaces. As a result, the majority of the elements in $\mathbf{W}$
are equal to zero. $\|\|_{1}$ denotes the $l_{1}$ norm, i.e. the sum of
absolute values of the argument and is used in order to ensure that the
$\mathbf{W}$ matrix is sparse.

To proceed with distinguishing the various classes in an unsupervised manner,
we first evaluate the affinity matrix as follows,

$\mathbf{A}=\mathbf{W}+\mathbf{W}^{T},$ (4)

where $\mathbf{A}\in\mathbb{R}^{n\times n}$. We subsequently use spectral
clustering as detailed in [19] to find the clusters underlying the multi-modal
data.

Figure 2: Volterra Neural Network Auto-encoder

###  III-C Reducing the Model Complexity

In this subsection, we will introduce two different solutions to further
reduce the number of parameters required in training the auto-encoder network.
The total number of parameters required for training the auto-encoder network
is dominated by the self-expressive layer parameters, which is a function of
$O(N^{2})$, where $N$ is the number of samples in the dataset. As a result,
this may lead to a longer training time and require a lot of computational
resources. In section IV, we attempt to reduce the number of parameters needed
by randomly removing a ratio of the edges in the self-expressive layer and
train the network with the remaining edges. By eliminating the appropriate
number of edges and setting them equal to zero, the clustering performance
should not be highly affected. The reason is the fact that the self-expressive
coefficient matrix, $\mathbf{W}$ is sparse and has a block-diagonal structure.
Therefore, most of the edges will eventually be equal to zero.

The second approach we evaluate in section IV is referred to as cyclic
sparsely connected (CSC) layers [20]. This approach was employed as an overlay
for fully connected (FC) layers whose number of parameters, $O(N^{2})$, can
dominate the parameters of the entire deep neural network model. The CSC
layers are composed of a few sequential layers, referred to as support layers,
which result in full connectivity between the inputs and outputs of each CSC
layer. The sparsely connected layers are composed of a sequence of $L$ layers:
an Input layer, $L-1$ layers in between referred to as support layers, and an
output layer. Assume having $N$ nodes and the fan-out of every node, as well
as the fan-in of every layer, is equal to $F$. Therefore, the total number of
edges, $E$, in the CSC layers structure is as follows,

$E=NFL,$ (5)

Every layer in the CSC structure is defined by an adjacency matrix, $A_{i}$
s.t. $i=1,...,L$, whose length and width is equal to $N$, where $A(i,j)$
indicate the number of edges that connect the input node $i$ to the output
node $j$. As a result, $NF$ out of $N^{2}$ elements of each adjacency matrix
corresponding to one support layer are equal to 1 and the rest of the elements
are zeros. The connectivity, $C$, is defined as the number of paths between
any pair from the diagram input and output layers. Therefore,

$F^{L}=NC$ (6)

From Eqns. (5) and (6), it can be deduced that the complexity decreased from
$O(N^{2})$ to $O(NlogN)$. The relationship between the number of edges and the
number of nodes is as follows,

$E=NFlog_{F}(NC)$ (7)

An adjacency matrix $A_{i}$ is defined for every support layer $i$ in the CSC
layers we use to replace the fully connected layer. Every support layer has a
generator polynomial $p_{i}(x)$, which is composed of $F$ terms to generate a
cyclic adjacency matrix of block length $N$ as explained in [20]. The
generator polynomial corresponding to each support cyclic matrix constructs
the first row and every next row of the matrix is a cyclic right shift of its
previous row. In [20], two different factorization approaches were proposed
for constructing the support layers. For our problem, we assume that the
connectivity, $C$, is equal to 1. We follow the first approach proposed in
[20] to construct the generator polynomial $p_{i}(x)=\sum_{i=0}^{N-1}$ as
follows,

$\sum_{i=0}^{N-1}x^{i}=\prod_{i=0}^{L-1}p_{i}(x)~{}s.t.~{}p_{i}(x)=\sum_{j=0}^{F-1}x^{S_{i}.j},S_{i}=F^{i},$
(8)

The CSC layers are described by the polynomial function by assigning each
$p_{i}(x)$ to each support layer $i$. $S_{i}$ is the stride value which
specifies the distance between elements of value 1s in the first row of the
support matrix of layer $i$.

##  IV EXPERIMENTAL RESULTS

###  IV-A Dataset description

To substantiate the discussed approach along with the various steps, we select
two different datasets. The first one is the Extended Yale Dataset [21]. This
dataset has been used extensively in subspace clustering as in [15, 22]. The
dataset is composed of 64 frontal images of 38 individuals under different
illumination conditions. In this work, we utilize the augmented data used in
[14], where facial components such as left eye, right eye, nose and mouth have
been cropped to represent four additional modalities. Images corresponding to
each modality have been cropped to a size of 32$\times$32 A sample image for
each modality is shown in Figure (3).

(a) Face.

(b) Left eye.

(c) Right eye.

(d) Mouth.

(e) Nose.

Figure 3: Sample images from the Augmented Extended Yale-B Dataset.

The second validation dataset we use is the ARL polarimetric face dataset
[23], which is composed of facial images for 60 individuals in the visible
domain and in four different polarimetric states. The dataset was collected
using a polarimetric long-wave infrared imager, to facilitate cross-spectrum
face recognition research. Different polarization states of thermal emissions
provide additional geometric and textural facial details, which can be used to
improve face identification. The Stokes parameters S0, S1, S2, and S3 are
often used to represent polarization-state information. They are collected by
measuring the radiant intensity transmitted through a polarizer that rotates
at different angles. S0 represents the conventional total intensity thermal
image, S1 captures the horizontal and vertical polarimetric information, and
S2 captures the diagonal polarimetric information. S1 and S2 capture
orthogonal, yet complementary, polarimetric information. The degree-of-linear-
polarization (DoLP) describes the portion of an electromagnetic wave that is
linearly polarized. All the images are spatially aligned for each subject. We
have also resized the images to 32$\times$32 pixels. Sample images from this
dataset are shown in Figure (4).

(a) Visible.

(b) DoLP.

(c) S0.

(d) S1.

(e) S2.

Figure 4: Sample images from the ARL Polarimetric Dataset.

###  IV-B Network Architecture

For both datasets, the data corresponding to each modality goes into the
corresponding encoder. The encoder projects the input modality into the
feature space. Features are extracted from each modality independently, and
are subsequently concatenated before going through the self-expressive layer.
The input to the self-expressive represents the data modalities’ projection
into the latent space. The second component of the Volterra filter auto-
encoder is the self-expressive layer. The goal of this layer is to enforce the
self-representation property among the features extracted from each data
modality, utilizing a fully connected layer which operates on the merged
features. The last stage is the decoder which reconstructs input data from the
self-expressive layers’ output and has the same structure as the encoder.

We implement the VNN-AE with Tensorflow and use the adaptive momentum based
gradient descent method (ADAM) [18] to minimize the loss function in Equation
(2) with a learning rate of $10^{-3}$ for ARL dataset and $10^{-4}$ for EYB
dataset. For DMSC, we use the same network structure described in [14]. In the
following, we will elaborate on the network constructed for the VNN-AE for the
two datasets:

####  IV-B1 ARL Dataset

The ARL dataset consists of five data modalities, therefore, the auto-encoder
has five encoder branches, one self expressive layers, and five decoder
branches. Each encoder branch is composed of a single layered VNN (equivalent
to a $2^{nd}$ order filter). The VNN consists of a multi-channel
implementation inspired by the googlenet architecture on inception dataset
[24]. In our implementation, we use 3 channels with 1x1 filters and 2 channels
with 3x3 filters. The decoder has the same structure as the encoder.

####  IV-B2 EYB Dataset

For EYB dataset, we use five data modalities, therefore, we have an encoder
for each modality, one self expressive layers and five decoder branches. Each
encoder is composed of a single layered VNN (equivalent to a $2^{nd}$ order
filter). Each encoder consists of 7 channels with 1x1 filters, 7 channels with
3x3 filters, and 6 channels of 5x5 filters.

###  IV-C Fusion Results

We evaluate the performance of our proposed Volterra filter auto-encoder
against the CNN based DMSC network. The sparse solution $\mathbf{W}$ provides
important information about the relations among data points, which may be used
to split data into individual clusters residing in a common subspace.
Observations from each object can be seen as data points spanning one
subspace. Interpreting the subspace-based affinities based on $\mathbf{W}$, we
proceed to carry out what amounts to modality fusion. For clustering by
$\mathbf{W}$, we applied the same spectral clustering approach that we
previously demonstrated in Section III.B. We used 75% of the data to learn the
cluster structure underlying the multi-modal data. We exploited three
clustering metrics to evaluate the performance; the clustering accuracy rate
(ACC), normalized mutual information (NMI) [25], and Adjusted Rand Index (ARI)
[26] metrics. The results are depicted in Tables I and II for EYB and ARL
dataset respectively. From the results, it can be seen that VMSC-AE
outperforms the DMSC network, all while reducing the number of parameters
needed to carry out the clustering task. The reason behind this improvement is
the fact that the VMSC-AE maintains a tractable structure that controls the
non-linearities introduced in the system in contrast to the CNN network that
can introduce undesirably infinite non-linearities.

TABLE I: Fusion Results for EYB Dataset | ACC | ARI | NMI | No. of Parameters
---|---|---|---|---
DMSC | 98.82% | 98.08% | 98.81% | 2,367,400
VFSC | 99.34% | 98.63% | 99.15% | 2,332,800
TABLE II: Fusion Results for ARL Dataset | ACC | ARI | NMI | Number of Parameters
---|---|---|---|---
DMSC | 97.59% | 97.53% | 99.42% | 4,667,720
VFSC | 99.95% | 99.90% | 99.94% | 4,666,650

###  IV-D Training with Less Data

We proceed to evaluate the performance of the proposed Volterra filter auto-
encoder with limited training data. A major challenge for any deep neural-
network may be the availability of inadequately sufficient data to train the
network. In the following, we will assess our proposed data fusion network
versus the convolutional deep neural network, DMSC, in case of limited data
availability during training. We train the auto-encoder structure using
portions of the available data, i.e., 25%, 40%, 50%, 60%, and 75%. The Results
are depicted in Table III and IV for ARL and EYB dataset respectively. From
the results, it is clear that fusing the data using VMSC-AE significantly
boosts the clustering accuracy while using less parameters than DMSC. The
VMSC-AE in case of ARL data uses just 520K parameters and 25% of the data and
still outperforms the DMSC model using 4.5M parameters and 75% of the data for
training. On the other hand, for EYB dataset, the performance of VMSC-AE with
just 854K parameters and 40% of data is comparable to that of the DMSC
implementation with 2.4M parameters and 75% data. Note that the number of
parameters decreases with decrease in the amount of training data because the
size of the self-expressive layer, $\mathbf{W}$ is directly dependent on the
number of samples used for training the model. These results thus show that
VMSC-AE is more robust and less sensitive to limited data availability during
training.

TABLE III: ARL Dataset: Training with Less Data Dataset/Ratio | VFSC | No. parameters | DMSC | No. of parameters
---|---|---|---|---
| ACC | ARI | NMI |  | ACC | ARI | NMI |
ARL 25% | 99.32% | 98.19% | 99.72% | 519,450 | 93.33% | 88.25% | 97.86% | 520,520
ARL 40% | 99.42% | 99.49% | 99.78% | 1,328,154 | 94% | 91.98% | 98.5% | 1,329,224
ARL 50% | 99.56% | 99.63% | 99.86% | 2,074,650 | 94.17% | 92.7% | 98.6% | 2,075,720
ARL 60% | 99.9% | 99.88% | 99.94% | 2,987,034 | 95.69% | 93.87% | 98.64% | 2,988,104
ARL 75% | 99.95% | 99.9% | 99.95% | 4,666,650 | 97.59% | 97.53% | 99.42% | 4,667,720

The comparison between VFSC and DMSC performance for both ARL and EYB dataset
are depicted in Figures 5 and 6 respectively.

Figure 5: Comparison between VFSC and DMSC for ARL dataset.

.

Figure 6: Comparison between VFSC and DMSC for EYB dataset.

.

TABLE IV: EYB Dataset: Training with Less Data Dataset/Ratio | VFSC | No. parameters | DMSC | No. of parameters
---|---|---|---|---
| ACC | ARI | NMI |  | ACC | ARI | NMI |
EYB 25% | 95.58% | 94.42% | 96.8% | 333,784 | 93.33% | 86.83% | 92.34% | 368,384
EYB 40% | 97.25% | 96.81% | 97.9% | 854,144 | 94% | 93.21% | 96.34% | 888,744
EYB 50% | 98.4% | 96.9% | 98.26% | 1,322,000 | 94.17% | 95.05% | 97.41% | 1,356,600
EYB 60% | 98.96% | 97.99% | 98.97% | 1,893,824 | 95.69% | 97.18% | 98.47% | 1,928,424
EYB 75% | 99.34% | 98.63% | 99.15% | 2,332,800 | 97.59% | 98.08% | 98.81% | 2,367,400

###  IV-E Network Pruning by Random Removal of Edges

It is clear from Table 1 and 2 that the total number of parameters needed is
dominated by the self-expressive layer parameters, which is a function of
$O(N^{2})$, where $N$ is the number of samples in the dataset. In this
subsection, we reduce the number of parameters by randomly removing a ratio of
the edges in the self-expressive layer. In addition to training the network
with less data, we reduce the number of edges needed to be trained by setting
a fixed ratio of those edges to be equal zero and ignore them while training
as if they do not exist. In Figures 7 and 8, we illustrate the error bar after
removing 10%, 30%, 50% and 70% of the edges from the self-expressive layer for
the ARL and EYB datasets respectively. The results have been averaged over 10
trials. From the results, we conclude that the VMSC-AE is more robust to the
changes in the self-expressive layer connections as compared to DMSC. As we
remove edges from the self-expressive layer, the performance degradation in
case of VMSC-AE is more graceful. In addition, the Volterra Filter auto-
encoder is less sensitive to training with less data as compared to DMSC
network, as a result of lower number of parameters in the encoder and decoder
which prevents over-fitting when lower number of samples are available.

Figure 7: Pruning the auto-encoder network while using different portions of
the ARL data.

Figure 8: Pruning the auto-encoder network while using different portions of
the EYB data.

###  IV-F Network Pruning Using Cyclic Sparse Connected Layers

In the following, we evaluate the CSC layers to further prune the auto-encoder
network. As explained in section III, the CSC layers are described by the
polynomial function by assigning each $p_{i}(x)$ to each support layer $i$. In
our experiment, we assume that $C$=1 and given $N$, we compute the number of
edges in each support layer accordingly using Eqn. (5). For the ARL dataset,
we assume that $C=1$ and $L=2$ while for the EYB dataset, we take $L=1$. We
found out that this structure achieves the best performance while retaining a
high compression rate. The experimental results are depicted in Table (4) and
(5) for ARL and EYB datasets respectively. We utilized different data ratios
for training the auto-encoder network and subsequently compare the results
from the VMSC-AE network to the DMSC network. In addition, we list the number
of parameters required for training the auto-encoder with the fully-connected
self-expressive layer versus the number of parameters needed for training the
auto-encoder utilizing the CSC layers. The results are also illustrated in
Figures 9 and 10 for ARL Dataset and EYB Dataset respectively.

Figure 9: Performance VS. Number of parameters of VFSC CSC, and DMSC CSC for
ARL dataset.

.

Figure 10: Performance VS. NUmber of parameters of VFSC CSC, and DMSC CSC for
EYB dataset.

.

TABLE V: ARL: Impact of CSC layers when training with less data. Dataset$|$Ration | Fully Connected | No. parameters | CSC Layers | No. of parameters
---|---|---|---|---
| ACC | ARI | NMI |  | ACC | ARI | NMI |
ARL DMSC 25% | 93.33% | 88.25% | 97.86% | 520,520 | 92.34% | 85.1% | 97.54% | 56,840
ARL VFSC 25% | 99.32% | 98.19% | 99.72% | 519,450 | 99.03% | 97.19% | 99.16% | 55,770
ARL DMSC 40% | 94% | 91.98% | 98.5% | 1,329,224 | 93.2% | 90.24% | 98.13% | 117,320
ARL VFSC 40% | 99.42% | 99.49% | 99.78% | 1,328,154 | 98.75% | 97.67% | 99.27% | 116,250
ARL DMSC 50% | 94.17% | 92.7% | 98.6% | 2,075,720 | 93.67% | 92.05% | 98.22% | 174,920
ARL VFSC 50% | 99.56% | 99.63% | 99.86% | 2,074,650 | 99.48% | 99.01% | 99.55% | 153,690
ARL DMSC 60% | 95.69% | 93.87% | 98.64% | 2,988,104 | 95.66% | 92.89% | 98.4% | 203,960
ARL VFSC 60% | 99.9% | 99.88% | 99.94% | 2,987,034 | 99.77% | 99.53% | 99.71% | 202,890
ARL DMSC 75% | 97.59% | 97.53% | 99.42% | 4,667,720 | 97.55% | 97.81% | 99.47% | 282,920
ARL VFSC 75% | 99.95% | 99.9% | 99.95% | 4,666,650 | 99.91% | 99.8% | 99.93% | 281,850
TABLE VI: EYB Dataset: Impact of CSC layers when training with less data. Dataset$|$Ration | Fully Connected | No. parameters | CSC Layers | No. of parameters
---|---|---|---|---
| ACC | ARI | NMI |  | ACC | ARI | NMI |
EYB DMSC 25% | 93.03% | 86.83% | 92.34% | 368,384 | 92.75% | 82.25% | 91.74% | 84,900
EYB VFSC 25% | 95.58% | 94.42% | 96.8% | 333,784 | 95.14% | 91.85% | 95.92% | 50,300
EYB DMSC 40% | 93.42% | 93.21% | 96.34% | 888,744 | 93.01% | 86.43% | 93.41% | 98,040
EYB VFSC 40% | 97.25% | 96.81% | 97.9% | 854,144 | 96.33% | 96.12% | 97.43% | 63,440
EYB DMSC 50% | 97.34% | 95.05% | 97.41% | 1,356,600 | 94.89% | 88.43% | 94.78% | 114,000
EYB VFSC 50% | 98.4% | 96.9% | 98.26% | 1,322,000 | 98.33% | 96.71% | 98.22% | 79,400
EYB DMSC 60% | 98.72% | 97.18% | 98.47% | 1,928,424 | 95.51% | 91.59% | 95.72% | 199,272
EYB VFSC 60% | 98.96% | 97.99% | 98.97% | 1,893,824 | 98.68% | 97.42% | 98.5% | 131,840
EYB DMSC 75% | 98.82% | 98.08% | 98.81% | 2,367,400 | 96.29% | 96.93% | 98.32% | 224,200
EYB VFSC 75% | 99.34% | 98.63% | 99.15% | 2,332,800 | 99.07% | 98.09% | 98.81% | 174,400

From the results, we can conclude that VMSC-AE significantly outperform the
CNN-based autoencoder, DMSC, after pruning the self-expressive layer using CSC
layer structure. VMSC-AE could achieve a very competitive performance with
almost 1%-2% accuracy loss as compared to fully connected network. Moreover,
the model complexity has decreased by slightly over $>90$%.

##  V Conclusion

In this paper, we presented an efficient Volterra Neural Network auto-encoder
for multi-modal data fusion. The introduced framework extracted the underlying
embedding of each data modality under the assumption of data self-
representation. Experimental results show a significant improvement for
Volterra Neural Network over the Convolutional Neural Network auto-encoder. In
addition, we evaluated multiple approaches to further prune the network
structure and reduce the model complexity of the multi-modal subspace
clustering auto encoder method. The experimental results showed that our
proposed approach provides better sample complexity over CNN-based auto-
encoder and demonstrates a robust classification performance.

## References

  * [1] O. Hellwich and C. Wiedemann, “Object extraction from high-resolution multisensor image data,” in _Third International Conference Fusion of Earth Data, Sophia Antipolis_ , vol. 115, 2000.
  * [2] Z. Korona and M. M. Kokar, “Model theory based fusion framework with application to multisensor target recognition,” in _1996 IEEE/SICE/RSJ International Conference on Multisensor Fusion and Integration for Intelligent Systems (Cat. No. 96TH8242)_. IEEE, 1996, pp. 9–16.
  * [3] S. Ghanem, A. Panahi, H. Krim, R. A. Kerekes, and J. Mattingly, “Information subspace-based fusion for vehicle classification,” in _2018 26th European Signal Processing Conference (EUSIPCO)_. IEEE, 2018, pp. 1612–1616.
  * [4] S. Ghanem, A. Panahi, H. Krim, and R. A. Kerekes, “Robust group subspace recovery: A new approach for multi-modality data fusion,” _IEEE Sensors Journal_ , 2020.
  * [5] F. K. Soong and A. E. Rosenberg, “On the use of instantaneous and transitional spectral information in speaker recognition,” _IEEE Transactions on Acoustics, Speech, and Signal Processing_ , vol. 36, no. 6, pp. 871–879, 1988\.
  * [6] L. Xu, A. Krzyzak, and C. Y. Suen, “Methods of combining multiple classifiers and their applications to handwriting recognition,” _IEEE transactions on systems, man, and cybernetics_ , vol. 22, no. 3, pp. 418–435, 1992.
  * [7] J. Ngiam, A. Khosla, M. Kim, J. Nam, H. Lee, and A. Ng, “Multimodal deep learning (pp. 689–696),” in _International conference on machine learning (ICML), Bellevue, WA_ , 2011.
  * [8] S. Roheda, B. S. Riggan, H. Krim, and L. Dai, “Cross-modality distillation: A case for conditional generative adversarial networks,” in _2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2018, pp. 2926–2930.
  * [9] S. Roheda, H. Krim, and B. S. Riggan, “Robust multi-modal sensor fusion: An adversarial approach,” _IEEE Sensors Journal_ , vol. 21, no. 2, pp. 1885–1896, 2020.
  * [10] S. Roheda, H. Krim, Z.-Q. Luo, and T. Wu, “Decision level fusion: An event driven approach,” in _2018 26th European Signal Processing Conference (EUSIPCO)_. IEEE, 2018, pp. 2598–2602.
  * [11] S. Roheda and H. Krim, “Conquering the cnn over-parameterization dilemma: A volterra filtering approach for action recognition,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 34, no. 07, 2020, pp. 11 948–11 956.
  * [12] G. Zoumpourlis, A. Doumanoglou, N. Vretos, and P. Daras, “Non-linear convolution filters for cnn-based learning,” in _Proceedings of the IEEE International Conference on Computer Vision_ , 2017, pp. 4761–4769.
  * [13] R. Kumar, A. Banerjee, B. C. Vemuri, and H. Pfister, “Trainable convolution filters and their application to face recognition,” _IEEE transactions on pattern analysis and machine intelligence_ , vol. 34, no. 7, pp. 1423–1436, 2011.
  * [14] M. Abavisani and V. M. Patel, “Deep multimodal subspace clustering networks,” _IEEE Journal of Selected Topics in Signal Processing_ , vol. 12, no. 6, pp. 1601–1614, 2018.
  * [15] E. Elhamifar and R. Vidal, “Sparse subspace clustering: Algorithm, theory, and applications,” _IEEE transactions on pattern analysis and machine intelligence_ , vol. 35, no. 11, pp. 2765–2781, 2013.
  * [16] X. Bian and H. Krim, “Bi-sparsity pursuit for robust subspace recovery,” in _2015 IEEE International Conference on Image Processing (ICIP)_. IEEE, 2015, pp. 3535–3539.
  * [17] V. Volterra, “Theory of functionals and of integral and integro-differential equations,” 1959.
  * [18] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” _arXiv preprint arXiv:1412.6980_ , 2014.
  * [19] A. Y. Ng, M. I. Jordan, and Y. Weiss, “On spectral clustering: Analysis and an algorithm,” in _Advances in neural information processing systems_ , 2002, pp. 849–856.
  * [20] M. Hosseini, M. Horton, H. Paneliya, U. Kallakuri, H. Homayoun, and T. Mohsenin, “On the complexity reduction of dense layers from o (n 2) to o (nlogn) with cyclic sparsely connected layers,” in _2019 56th ACM/IEEE Design Automation Conference (DAC)_. IEEE, 2019, pp. 1–6.
  * [21] K.-C. Lee, J. Ho, and D. J. Kriegman, “Acquiring linear subspaces for face recognition under variable lighting,” _IEEE Transactions on pattern analysis and machine intelligence_ , vol. 27, no. 5, pp. 684–698, 2005.
  * [22] G. Liu, Z. Lin, S. Yan, J. Sun, Y. Yu, and Y. Ma, “Robust recovery of subspace structures by low-rank representation,” _IEEE transactions on pattern analysis and machine intelligence_ , vol. 35, no. 1, pp. 171–184, 2012.
  * [23] S. Hu, N. J. Short, B. S. Riggan, C. Gordon, K. P. Gurton, M. Thielke, P. Gurram, and A. L. Chan, “A polarimetric thermal database for face recognition research,” in _Proceedings of the IEEE conference on computer vision and pattern recognition workshops_ , 2016, pp. 187–194.
  * [24] C. Szegedy, W. Liu, Y. Jia, P. Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, and A. Rabinovich, “Going deeper with convolutions,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2015, pp. 1–9.
  * [25] N. X. Vinh, J. Epps, and J. Bailey, “Information theoretic measures for clusterings comparison: Variants, properties, normalization and correction for chance,” _The Journal of Machine Learning Research_ , vol. 11, pp. 2837–2854, 2010.
  * [26] W. M. Rand, “Objective criteria for the evaluation of clustering methods,” _Journal of the American Statistical association_ , vol. 66, no. 336, pp. 846–850, 1971.

Sally Ghanem received the B.Sc. degree in electrical engineering from
Alexandria University, in 2013, and the M.Sc. degree in electrical and
computer engineering from North Carolina State University, Raleigh, NC, USA in
2016, where she is currently pursuing the Ph.D. degree. During the PhD
program, she has spent time at Oak Ridge National Laboratory working on
multimodal data. Her research interests include the areas of computer vision,
digital signal processing, image processing and machine learning.
---
Siddharth Roheda received the B.Tech. degree in Electronics and Communication
from Nirma University, India, in 2015, and the M.Sc. and Ph.D. degrees from
the Department of Electrical and Computer Engineering, North Carolina State
University, Raleigh, NC, USA, in 2020. He is currently a Post-Doctoral
Researcher at North Carolina State University working with the Vision,
Information, and Statistical Signal Theories and Applications Group. His
current research interests include Robust Information Fusion, Machine
Learning, Deep Learning, Computer Vision, and Signal Processing. More
specifically, he is interested in Supervised Learning, developing novel deep
learning architectures and robust algorithms for exploiting multi-modal
information for target detection and recognition.
---
Hamid Krim received the B.Sc. and M.Sc. and Ph.D. in ECE. He was a Member of
Technical Staff at AT&T Bell Labs, where he has conducted research and
development in the areas of telephony and digital communication
systems/subsystems. Following an NSF Postdoctoral Fellowship at Foreign
Centers of Excellence, LSS/University of Orsay, Paris, France, he joined the
Laboratory for Information and Decision Systems, MIT, Cambridge, MA, USA, as a
Research Scientist and where he performed/supervised research. He is currently
a Professor of electrical engineering in the Department of Electrical and
Computer Engineering, North Carolina State University, NC, leading the Vision,
Information, and Statistical Signal Theories and Applications Group. His
research interests include statistical signal and image analysis and
mathematical modeling with a keen emphasis on applied problems in
classification and recognition using geometric and topological tools. He has
served on the SP society Editorial Board and on TCs, and is the SP
Distinguished Lecturer for 2015-2016.
---


11institutetext:  Gabriele Bressanini 11email<EMAIL_ADDRESS>22institutetext: QOLS, Blackett Laboratory, Imperial College London, London
SW7 2AZ, United Kingdom 33institutetext: Claudia Benedetti 33email:
<EMAIL_ADDRESS>
Matteo G. A. Paris 33email<EMAIL_ADDRESS>44institutetext:
Dipartimento di Fisica Aldo Pontremoli, Universitá degli Studi di Milano,
I-20133 Milano, Italy

# Decoherence and classicalization of continuous-time quantum walks on graphs

Gabriele Bressanini  Claudia Benedetti  Matteo G. A. Paris

###### Abstract

We address decoherence and classicalization of continuous-time quantum walks
(CTQWs) on graphs. In particular, we investigate three different models of
decoherence, and employ the quantum-classical (QC) dynamical distance as a
figure of merit to assess whether, and to which extent, decoherence
classicalizes the CTQW, i.e. turns it into the analogue classical process. We
show that the dynamics arising from intrinsic decoherence, i.e. dephasing in
the energy basis, do not fully classicalize the walker and partially preserves
quantum features. On the other hand, dephasing in the position basis, as
described by the Haken-Strobl master equation or by the quantum stochastic
walk (QSW) model, asymptotically destroys the quantumness of the walker,
making it equivalent to a classical random walk. We also investigate the speed
of the classicalization process, and observe a faster convergence of the QC-
distance to its asymptotic value for intrinsic decoherence and the QSW models,
whereas in the Haken-Strobl scenario, larger values of the decoherence rate
induce localization of the walker.

††journal: Quantum Information Processing

##  1 Introduction

Quantum walks (QWs) are the quantum-mechanical counterpart of classical random
walks (RWs) kempe003 ; venegas2012 ; xia20 ; kadian21 ; frigerio21 . If the
walker evolves in discrete temporal steps, we talk about discrete-time QWs,
while in continuous-time quantum walks (CTQWs) time is a real parameter
aharonov93 ; farhi98 . In this work, we focus on continuous-time quantum
walks. Quantum walks on graphs are used to describe the transport of energy or
information across a given structure in several physical, chemical and
biological systems mulken2011 ; mulken07 ; razzoli11 ; maciel20 . They also
proved to be powerful tools for building quantum algorithms ambainis2003 ;
portugal18  and provide a universal model of quantum computation childs09 ;
Wang20 ; Herrman2022 .

Experimental implementations of quantum walks unavoidably involve the
interaction with an external environment, and a question arises on whether,
and to which extent, the open quantum system dynamics of a quantum walker is
detrimental to its quantum features. In turn, the thorough characterisation of
decoherence effects in CTQWs is a key ingredient for their use in quantum
technology and, in particular, to envisage strategies that may mitigate or
cancel out noise. Several studies investigated how noise stemming from the
interaction between the system and the environment affects the dynamics of
quantum walks norio05 ; plenio08 ; caruso09 ; schreiber11 ; benedetti16 ;
tama17 ; benedetti19 ; Kurt20 . Different effects may emerge, such as
localization, transition toward a classically distributed walker schreiber11 ;
benedetti16 ; benedetti19 , but also an improvement in excitation transport
efficiency plenio08 ; caruso09 ; tama17 ; Kurt20 . However, if a QW loses all
of its quantum features and becomes a classical RW, then any potential quantum
advantage related to the quantum process is lost as well.

In this paper, we study if decoherence can turn a continuous-time quantum walk
over a graph into the corresponding classical random walk. We refer to this
phenomenon as _classicalization_. In order to make our analysis quantitative,
we use a fidelity-based measure of non-classicality, referred to as quantum-
classical distance, that quantifies the differences between the dynamics of a
quantum and a classical walker on a given graph gualtieri20 . Recently, this
quantity has been also used as a tool to design optimal quantum walks
frigerio22 . We use this distance to assess if and to which extent decoherence
makes the quantum evolution more similar to its classical counterpart, at
least asymptotically, with respect to the ideal noiseless case.

In the following, we study three different models of decoherence. First, we
investigate intrinsic decoherence Milburn91 , i.e. decoherence in the
Hamiltonian basis, then we shift our focus to two different mechanisms of
decoherence in the position basis. In particular, we consider dephasing
induced by the Haken-Strobl master equation haken73  and then we analyse the
interplay of unitary and irreversible dynamics using the quantum stochastic
walk framework QuantumStochasticWalk . We show that intrinsic decoherence is
not able to completely classicalize the walker: residual quantumness is
preserved, and the quantum walker dynamics departs from the corresponding
classical one. We give the analytic expressions for the asymptotic value of
the quantum-classical distance over the complete, cycle and star graphs. On
the other hand, the two models of decoherence in the position basis completely
suppress the quantum features of the coherent process, nullifying the quantum-
classical distance.

As we will see in detail, some general properties of the quantum-classical
distance do not depend on the decoherence model: it reaches an asymptotic
value which does not depend on the decoherence rate and its qualitative
behavior is not dependent on the size of the graph, nor the considered
topology. On the other hand, we show that speed of the convergence of the
quantum-classical distance to its asymptotic value is influenced by the noise
parameter with a non-universal behavior. For intrinsic decoherence and for the
quantum stochastic walk model, we observe that a larger value of the
decoherence parameter leads to a faster convergence, whereas for the Haken-
Strobl master equation we see an inversion, such that after a threshold value
of the noise rate the quantum-classical distance decays slower.

The paper is organized as follows. In Section 2, we establish notation and
briefly review classical and quantum walks, the master equation approach for
noisy quantum walks, and the quantum-classical distance. In Section 3. we
investigate the effects of intrinsic decoherence on CTWQs, while Section 4 is
devoted to the study of decoherence in the position basis. In Section 5 we
draw conclusions, and provide some concluding remarks.

##  2 Preliminary concepts

Let us consider a finite, simple, undirected, connected graph $G(V,E)$, where
$V$ is the set of vertices, also called nodes, and $E$ the set of edges. The
cardinality of $V$ sets the dimension of the graph, i.e. the number of nodes
$N=|V|$. A graph is uniquely identified by its Laplacian matrix $L=D-A$, where
$A$ is the adjacency matrix and $D$ is a diagonal degree matrix nica2018 . In
particular, $A_{jk}=1$ if vertices $j$ and $k$ are connected (with $j\neq k$),
and zero otherwise, and $D_{jj}=d_{j}$ is the vertex degree of the node, i.e.
the number of edges connecting the $j$-th node to the others. $L$ is a
positive semi-definite matrix and completely determines the classical
evolution of a walker on a graph. The dynamics of a classical walker initially
localized on node $j$ may be described by the diagonal density matrix

$\mathcal{E}_{C}[\rho_{j}](t)=\sum_{k=1}^{N}p_{kj}(t)|k\rangle\\!\langle k|.$
(1)

where $p_{kj}(t)=\langle k|e^{-\nu Lt}|j\rangle$ is the classical transition
probability from node $j$ to node $k$, $\nu$ is the transition rate,
$\\{|k\rangle\\}_{k=1}^{N}$ is the complete orthonormal basis which describes
localized states of the walker on the $N$ nodes of the graph and
$\rho_{j}=|j\rangle\\!\langle j|$ is the initial state. The map
$\mathcal{E}_{C}$ describes a continuous-time random walk (CTRW) on the graph
$G$. On the other hand, the purely coherent quantum evolution of a CTQW is
obtained by promoting the Laplacian to the system’s Hamiltonian $H=\nu L$
farhi98  (though this is not the only possible choice for a CTQW generator
frigerio21 ; wong2016 ). Without loss of generality we can set the transition
rate to $\nu=1$ and $\hbar=1$. The unitary evolution of the quantum walk is
thus given by $\ket{\psi(t)}=e^{-iHt}\ket{j}$, where $\ket{j}$ denotes the
initial localized state.

###  2.1 Noisy quantum walks

If the walker interacts with an external environment, its evolution is no
longer unitary and can be described, within the Markovian approximation, by a
master equation in the Lindblad form, i.e.

$\displaystyle\frac{d\rho(t)}{dt}$
$\displaystyle=-i\left[L,\rho(t)\right]+\sum_{k}\gamma_{k}\mathcal{D}\left[O_{k}\right]\rho(t)\,.$
(2)

Here $\mathcal{D}$ is the Limbladian superoperator, defined as
$\mathcal{D}\left[A\right]\rho=A\rho
A^{\dagger}-\frac{1}{2}\\{A^{\dagger}A,\rho\\}$ with the brackets
$\\{A,B\\}=AB+BA$ denoting the usual anticommutator, $O_{k}$ are the Lindblad
operators and $\gamma_{k}\geq 0$. The main goal of this work is to investigate
if, and to which extent, the presence of environmental noise makes the quantum
evolution of a walker on a graph more similar to its classical counterpart
(that is described by Eq. (1)), compared to the ideal noiseless scenario. In
particular, we consider three models of noisy quantum walks whose dynamics is
induced by three master equations that describe dephasing in some basis of
choice.

At first, we focus on decoherence in the energy basis, corresponding to the
following master equation

$\displaystyle\frac{d\rho(t)}{dt}$
$\displaystyle=-i\left[L,\rho(t)\right]-\frac{\gamma}{2}[L,[L,\rho(t)]]\,,$
(3)

which describes intrinsic decoherence of a quantum system. It has been derived
Milburn91  by assuming that at short timescales a quantum system evolves as a
stochastic sequence of random unitary operators. The parameter $\gamma\geq 0$
is referred to as the decoherence rate, and $L$ is the graph Laplacian. From
an operational point of view, intrinsic decoherence corresponds to a
randomized quadratic perturbation l2pert .

We then consider two different models of decoherence in the site (position)
basis. The first one corresponds to the Haken-Strobl master equation haken73 ,
which reads

$\displaystyle\frac{d\rho(t)}{dt}=$
$\displaystyle-i\left[L,\rho(t)\right]+\gamma\,\sum_{k}\mathcal{D}[P_{k}]\rho(t)\,,$
(4)

where $\gamma\geq 0$ is the decoherence rate and $P_{k}=\outerproduct{k}{k}$
are the site-projector operators. It can be shown haken73  that the Haken-
Strobl master equation corresponds to a system with a tight-binding
Hamiltonian affected by stochastic noise describing thermal Gaussian
fluctuations of the on-site energies. The decoherence parameter $\gamma$ is
related to the variance of the thermal fluctuations. The Haken-Strobl master
equation finds applications in the description of a single excitation
transport, e.g. in an $N$-site chain subject to dephasing induced by the
interaction with a fluctuating environment Rebentrost09 .

A second model of decoherence in the site basis is provided by the quantum
stochastic walk (QSW) approach QuantumStochasticWalk . The QSW formalism
axiomatically generalizes a classical random process to a quantum stochastic
process, where the topology of the underlying graph imposes constraints on the
dynamical evolution of the walker. It is described by the following master
equation Caruso

$\frac{d\rho(t)}{dt}=-(1-p)\,i\,[L,\rho(t)]+p\sum_{kj}\mathcal{D}[P_{kj}]\rho(t)\,.$
(5)

Here $p\in[0,1]$ quantifies the interplay between unitary ($p=0$) and
irreversible ($p=1$) dynamics and the $P_{kj}=L_{kj}\outerproduct{k}{j}$ are
the jump operators, with $L_{kj}=\bra{k}L\ket{j}$. This model generalizes both
the QW and the RW on the graph by continuously interpolating between the two
dynamics with a single real mixing parameter $p$. This model has been employed
to investigate the role of environmental noise in assisting the transport of
energy or information across a network, such as a light-harvesting complex in
a photosynthetic process Caruso ; caruso09 ; tama17 ; Kurt20 .

###  2.2 The quantum-classical distance

In order to compare the dynamics of different quantum walks models, and to
quantify the differences between quantum and classical evolutions, we use a
recently introduced dynamical distance based on fidelity gualtieri20 . Given
two dynamical maps, describing a classical $\mathcal{E}_{C}[\rho_{cl}]$ and a
quantum $\mathcal{E}_{Q}[\rho_{cl}]$ evolution, the QC-distance
$D_{\text{\tiny QC}}(t)$ between them is defined as gualtieri20 :

$D_{\text{\tiny QC}}(t)\doteq
1-\underset{\rho_{cl}}{\text{min}}\,\mathcal{F}\left(\mathcal{E}_{C}[\rho_{cl}](t),\mathcal{E}_{Q}[\rho_{cl}](t)\right)\,,$
(6)

where $\rho_{cl}$ is an initial classical state of the walker, i.e. a
statistical operator diagonal in the node basis, and
$\mathcal{F}(\mathcal{E}_{C}[\rho_{cl}],\mathcal{E}_{Q}[\rho_{cl}])$ is the
quantum fidelity between the classically and quantum evolved states, i.e.
$\mathcal{F}(\rho,\sigma)=\left[\Tr\sqrt{\sqrt{\rho}\sigma\sqrt{\rho}}\right]^{2}$.
The minimization in Eq. (6) is achieved, for every graph, by a localized state
$\rho_{j}$ gualtieri20 , hence we shall focus on such initial states only. An
interesting feature of this measure of non-classicality is that, for noiseless
unitary quantum dynamics, it has an horizontal asymptote which depends only on
the total number of nodes $N$, i.e. $\lim_{t\rightarrow\infty}D_{\text{\tiny
QC}}(t)=1-\frac{1}{N}$. In the next Section, we use the QC-distance as a
figure of merit to assess the robustness of CTQW against decoherence. In
particular, we compute the QC-distance between the classically evolved state
$\mathcal{E}_{C}[\rho_{j}](t)$ defined in Eq. (1), and the quantum state
described by a CPTP-map modeling decoherence in some basis of choice.

##  3 Decoherence in the energy basis

Let us consider a quantum walker subject to the intrinsic decoherence process
described by the master equation (3). The solution for an initial localized
state $\rho_{j}=\outerproduct{j}{j}$, is given by

$\displaystyle\mathcal{E}_{L}$
$\displaystyle[\rho_{j}](t)=\sum_{n,p}\langle\lambda_{n}|\rho_{j}|\lambda_{p}\rangle
e^{-i(\lambda_{n}-\lambda_{p})t-\frac{1}{2}\gamma(\lambda_{n}-\lambda_{p})^{2}t}|\lambda_{n}\rangle\\!\langle\lambda_{p}|\,,$
(7)

where $\\{\lambda_{n}\\}_{n=1}^{N}$ and $\\{|\lambda_{n}\rangle\\}_{n=1}^{N}$
are respectively the eigenvalues and eigenvectors of $L$, i.e.
$L|\lambda_{n}\rangle=\lambda_{n}|\lambda_{n}\rangle$. Eq. (7) represents
decoherence in the energy basis, and may also be expressed in the following
form:

$\displaystyle\mathcal{E}_{L}[\rho_{j}](t)=\int
dy\,g(y|\,0,\sigma)\,\,e^{-iL(t+y)}\rho_{j}e^{iL(t+y)}\,,$ (8)

where $g(y|\,0,\sigma)$ is a Gaussian probability distribution function with
standard deviation $\sigma$ and zero mean value. The connection between the
two representations is achieved by the correspondence $\sigma^{2}=\gamma t$.
This map can thus be reinterpreted as a coarse graining in time of the ideal
quantum evolution.

We now use Eq. (7) to compute the QC-distance $D_{\text{\tiny QC}}(t)$ and
analyze its behaviour for relevant graph topologies. In the long-time limit,
the classical transition probability distribution $p_{kj}(t)$ tends to the
flat distribution, i.e. for $t\gg 1$ we obtain

$\mathcal{E}_{C}[\rho_{j}](t)\simeq\frac{\mathbb{I}}{N}\quad\forall\rho_{j}\,.$

Furthermore, in the same limit, we see from Eq. (7) that, because of the
exponential damping, the only terms of the sum that survive asymptotically are
those that satisfy the condition $\lambda_{n}=\lambda_{p}$. We can write the
expression for the asymptotic quantum map
$\mathcal{E}_{L}[\rho_{j}](t_{\infty})\equiv\mathcal{E}_{\infty}[\rho_{j}]$ as
follows

$\mathcal{E}_{\infty}[\rho_{j}]=\sum_{n,p}\delta_{\lambda_{n}\lambda_{p}}\,\bra{\lambda_{n}}\rho_{j}\ket{\lambda_{p}}\outerproduct{\lambda_{n}}{\lambda_{p}}\,.$
(9)

The asymptotic quantum-classical distance reads

$\displaystyle D_{\text{\tiny
QC}}(t_{\infty})=1-\min_{\rho_{j}}\,\left[\left(\Tr\sqrt{\frac{\mathcal{E}_{\infty}[\rho_{j}]}{N}}\right)^{2}\right].$
(10)

$D_{\text{\tiny QC}}(t_{\infty})$ thus depends on the graph topology but not
on the decoherence parameter $\gamma$, which only affects the speed of
convergence to its asymptotic value.

From the asymptotic expression in Eq. (9), we see that decoherence in the
energy basis cannot turn the quantum evolution of CTQW into a classical random
walk for any graph with a degenerate Laplcian spectrum. Indeed, the QC
distance is zero if and only if the stationary quantum state is the maximally
mixed state. From the expression of $\mathcal{E}_{\infty}[\rho_{j}]$ it
follows that, if the spectrum of $L$ has eigenvectors corresponding to
degenerate eigenvalues $\lambda_{n}=\lambda_{p}$ with
$\bra{\lambda_{n}}\rho_{j}\ket{\lambda_{p}}\neq 0$ , then the density matrix
has non-zero off-diagonal elements and the QC-distance does not vanish.
Indeed, the absence of off-diagonal terms in the quantum density matrix is a
necessary, but not sufficient, condition to classicalize the walker. The
existence of degenerate Laplacian eigenvalues is thus a key element in the
classicalization of the QW and it is related to the symmetries of the
underlying graph, as we show in Appendix A.

Let us conclude this section with few comments about the speed of convergence
of the QC-distance to its asymptotic value. From the expression of the
classical transition probability from node $j$ to node $k$

$p_{kj}(t)=\langle k|e^{-Lt}|j\rangle=\sum_{n}e^{-\lambda_{n}t}\langle
k|\lambda_{n}\rangle\\!\langle\lambda_{n}|j\rangle$ (11)

it follows that the convergence of the classically evolved state
$\mathcal{E}_{C}[\rho_{j}](t)$ to the maximally mixed state is governed by the
smallest non-zero eigenvalue which is known as the Fiedler value
$\lambda_{F}$. The leading term in Eq. (11) is $e^{-\lambda_{F}t}$ and
consequently, the bigger the Fiedler value the faster the convergence of the
classical distribution to the uniform one. In the quantum case instead, the
speed of convergence to the stationary state is determined by the smallest
non-zero value of the energy gap $(\lambda_{n}-\lambda_{p})^{2}$, as can be
seen from Eq. (7). The parameter $\gamma$ determines the speed of convergence,
once $(\lambda_{n}-\lambda_{p})^{2}$ is fixed. For the three classes of graphs
we are going to consider in this paper, i.e. complete, cycle and star graphs,
the minimum of this gap is achieved by the difference of the two smallest
eigenvalues squared, namely when one is zero and the other is the Fiedler
value. However, this is not true for a general topology.

###  3.1 Complete Graph

The complete graph is the graph corresponding to maximal connectivity. The
Laplacian matrix of a an $N$-node complete graph has the expression
$L=N\mathbb{I}-\mathbb{J}$, where $\mathbb{J}$ is the unit matrix, i.e. its
elements are all ones, and $\mathbb{I}$ is the identity matrix. In Figure
1(a), we show the QC-distance of noisy (dephased) CTQWs on a complete graph
with $N=5$ nodes, for different values of the decoherence rate $\gamma$. All
the nodes of a complete graph are equivalent, hence without loss of generality
and for future convenience we set the initial state to
$\rho_{N}=|N\rangle\\!\langle N|$.

Figure 1: Quantum-classical distance computed for different values of the
dephasing parameter, for different graphs with $N=5$ nodes: (a) complete
graph, (b) cycle graph and (c) star graph. Dashed pink line indicate the
asymptotic value $D_{\text{\tiny QC}}(t_{\infty})$ in the three considered
cases. The inset of figure (c) shows the $D_{\text{\tiny QC}}(t;j)$ starting
from the two different kind of nodes for the star graph: central (solid lines)
and outer (dashed lines). $t$ is a dimensionless time.

At the initial time $D_{\text{\tiny QC}}(0)=0$, then the distance grows with
time, and eventually reaches an horizontal asymptote, not necessarily
monotonically depending on the value of $\gamma$. This asymptote does not
depend on the decoherence parameter which, in turn, only affects the rate of
convergence of $D_{\text{\tiny QC}}$ to its asymptotic value. In particular,
as $\gamma$ gets bigger the distance converges more rapidly. For vanishing
$\gamma$, the QC-distance for the noiseless case is recovered. We observe that
intrinsic decoherence indeed brings the quantum walk closer to the classical
random walk as the decoherence rate increases. However, due to the degeneracy
of the spectrum, the QW does not become fully classical and the QC-distance
remains positive at all times $t>0$. Notice that the qualitative behaviour of
the QC-distance does not depend on the number of nodes $N$, i.e. a behaviour
similar to that of Fig. 1 is observed for every $N$.

Let us now prove that the asymptotic value of the QC-distance does not depend
on the rate $\gamma$ but rather it is a function of $N$ only. The Laplacian
spectrum of an $N$-node complete graph reads
$\lambda_{1}=\cdots=\lambda_{N-1}=N$ and $\lambda_{N}=0$. The corresponding
eigenvectors are

$|\lambda_{k}\rangle=\frac{1}{\sqrt{N}}\sum_{j=1}^{N}e^{i\frac{2\pi
k}{N}j}|j\rangle.$ (12)

In order to obtain the stationary quantum-evolved state in Eq.(9), we first
need to find the values of $n$ and $p$ for which $\lambda_{n}=\lambda_{p}$
holds. For the complete graph this condition is satisfied when $n\neq N\wedge
p\neq N$ or $n=p=N$. Hence, it follows that the stationary quantum state reads

$\rho_{\infty}{=}\frac{1}{N}|\lambda_{N}\rangle\\!\langle\lambda_{N}|+\frac{1}{N}\sum_{n,p=1}^{N-1}|\lambda_{n}\rangle\\!\langle\lambda_{p}|\,,$
(13)

where we used $\langle N|\lambda_{k}\rangle=\frac{1}{\sqrt{N}}\,\,\forall k$.
We can now compute the asymptotic value of the QC-distance:

$\displaystyle D_{\text{\tiny QC}}(t_{\infty})=$ $\displaystyle
1-\frac{1}{N^{2}}\left(1+\sqrt{N-1}\right)^{2}.$ (14)

Indeed the asymptotic value does not depend on the decoherence rate $\gamma$,
but only on the number of nodes $N$. Notice that for $N\rightarrow\infty$ we
retrieve the asymptote of the noiseless case, i.e. $1-\frac{1}{N}$. This
suggests that, as the size of the complete graph grows, the effect of
intrinsic decoherence becomes negligible.

###  3.2 Cycle Graph

The cycle graph is a one-dimensional lattice with periodic boundary
conditions, i.e. it is a regular graph with vertex degrees
$d_{j}=2\quad\forall j$. The Laplacian for a $N$-node cycle graph is a
tridiagonal matrix with off-diagonal elements $L_{j,j+1}=L_{j+1,j}=-1$
$\forall j=1,\dots,N-1$ and diagonal elements $L_{jj}=2$ $\forall j$. As for
the previous case, and without loss of generality, we choose
$\rho_{j}=\outerproduct{N}{N}$ as initial localized state of the walker.

The behaviour of $D_{\text{\tiny QC}}(t)$ is qualitatively similar to the
complete graph, see Fig. 1(b), i.e. intrinsic decoherence brings the quantum
evolution closer to the classical one compared to the noiseless case. However,
although some quantumness is lost, the degeneracy of the Laplacian’s spectrum
prevents a full classicalization of the QW. Depending on the value of
$\gamma$, the QC-distance may reach its asymptotic value non-monotonically,
i.e. displaying a maximum at shorter times, or monotonically. We observed
that, for a fixed number of nodes, the asymptotic value of $D_{\text{\tiny
QC}}(t)$ is smaller with respect to the case of the complete graph.

To calculate the asymptotic value $D_{\text{\tiny QC}}(t_{\infty})$, we need
$\mathcal{E}_{\infty}[\rho_{j}]$ and, in turn, the values of $n$ and $p$ that
fulfill the condition $\lambda_{n}=\lambda_{p}$. The eigenvalues of the
$N$-cycle graph Laplacian are $\lambda_{n}=2\left[1-\cos\left(\frac{2\pi
n}{N}\right)\right]$, with $n=1,\cdots,N$, and the corresponding eigenstates
coincide with those in Eq. (12). In particular, $\lambda_{n}=\lambda_{p}$ is
satisfied when $n=p$ or when $n=N-p$ with $p\neq N$. In order to explicitly
evaluate $D_{\text{\tiny QC}}(t_{\infty})$, we study the odd and the even $N$
cases separately, since when $N$ is even there are $\frac{N}{2}-1$ couples of
equal eigevalues, while when $N$ is odd there are $\frac{N-1}{2}$ of them.
With this in mind, we obtain the stationary quantum state

$\mathcal{E}_{\infty}[\rho_{j}]=\frac{1}{N}\mathbb{I}+\frac{1}{N}\sum_{p=1}^{N-1}|\lambda_{N-p}\rangle\\!\langle\lambda_{p}|$
(15)

where $p\neq\frac{N}{2}$ if $N$ is even. After diagonalizing
$\mathcal{E}_{\infty}[\rho_{j}]$, the asymptote of the QC-distance can be
easily computed. When $N$ is even we obtain

$D_{\text{\tiny
QC}}(t_{\infty})=1-\frac{1}{N^{2}}\left(2+\frac{N-2}{\sqrt{2}}\right)^{2}\,,$
(16)

while for odd $N$ we get

$D_{\text{\tiny
QC}}(t_{\infty})=1-\frac{1}{N^{2}}\left(1+\frac{N-1}{\sqrt{2}}\right)^{2}.$
(17)

In both cases, we see that as $N\rightarrow\infty$ the asymptotic value of the
QC-distance approaches $\frac{1}{2}$, as opposed to the complete graph case,
where the asymptote reaches unity in the same limit, see Fig. 2 for a
comparison.

Figure 2: Asymptotic value of $D_{\text{\tiny QC}}$ in the case of intrinsic
decoherence, as a function of the graph size $N$, for the complete (black
dots), cycle (blue squares) and star (red rhombus) graph. The values for the
complete and star graph are identical.

###  3.3 Star Graph

As opposed to the complete graph and the cycle graph, the nodes of a star
graph are not all equivalent, but are rather grouped into two categories: the
central node, which we will refer to as $|1\rangle$, and the remaining $N-1$
external nodes. Consequently, the computation of the $D_{\text{\tiny QC}}(t)$
involves an optimization over these two distinct classes of initial states,
consistently with the definition in Eq. (6). Fig. 1(c) shows the QC-distance
of a quantum walker moving on a star graph. Note that the points of the plot
where the function is not differentiable correspond to intersections between
the QC-distance of a walker initially localized in the center node and that of
a walker whose initial state is an external node. We first study the system
with initial state $\rho_{1}=\outerproduct{1}{1}$ and denote this distance
with $D_{\text{\tiny QC}}(t,c)$, where $c$ stands for the central node.
Numerical computation of the distance between the classical and the quantum
noisy evolution shows that $D_{\text{\tiny QC}}(t,c)$ is the same as the one
obtained for the complete graph. The same happens in the noiseless case, where
analytic calculations of the quantum and classical transition probabilities
for the two graphs have the same expressions Xu2009 , as long as the walker is
initialized in the central vertex of the star graph. Moreover, it is possible
to show numerically that the QC-distance for the complete graph is equivalent
to that of a larger class of $N$-nodes graphs, namely those obtained from an
$N$-dimensional complete graph by removing edges that are not connected to the
central node $|1\rangle$. This holds true for the noiseless scenario razzoli22
as well as for the dynamics induced by intrinsic decoherence.
If, instead, the initial state is localized on any of the external nodes we
obtain a different distance, that we call $D_{\text{\tiny QC}}(t,e)$ (see the
inset of Fig 1(c)). In particular, while at short times the maximum of the
$D_{\text{\tiny QC}}(t)$ is obtained by starting from the central node, at
intermediate times it can be obtained by starting from one of the external
nodes, depending on the value of the parameter $\gamma$. At longer times, the
central node always proves to be the optimal initialization for the walker. We
can indeed compute the asymptotic value of $D_{\text{\tiny QC}}(t,e)$ through
Eq. (10). Given the Laplacian eigenvalues
$\lambda_{1}=\cdots=\lambda_{N-2}=1$, $\lambda_{N-1}=0$ $\lambda_{N}=N$, and
its respective eigenvectors Xu2009 :

$|\lambda_{k}\rangle=\sqrt{\frac{k}{k+1}}|k+2\rangle-\sqrt{\frac{1}{k(k+1)}}\sum_{j=2}^{k+1}|j\rangle,$
(18)

for $k=1,\cdots,N-2$ and

$\displaystyle|\lambda_{N-1}\rangle=\frac{1}{\sqrt{N}}\sum_{j=1}^{N}|j\rangle$
(19)
$\displaystyle|\lambda_{N}\rangle=\frac{1}{\sqrt{N(N-1)}}\sum_{j=1}^{N}|j\rangle-\sqrt{\frac{N}{N-1}}|1\rangle,$
(20)

one obtains the following stationary state

$\displaystyle\mathcal{E}_{\infty}[\rho_{j}]=$
$\displaystyle\frac{1}{N}|\lambda_{N-1}\rangle\\!\langle\lambda_{N-1}|+\frac{1}{N(N-1)}|\lambda_{N}\rangle\\!\langle\lambda_{N}|+$
$\displaystyle+$
$\displaystyle\sum_{j,k=1}^{N-2}\frac{1}{\sqrt{j(j+1)}}\frac{1}{\sqrt{k(k+1)}}|\lambda_{j}\rangle\\!\langle\lambda_{k}|.$
(21)

The asymptote of the QC-distance, having fixed the initial state to an
external node, then reads

$D_{\text{\tiny
QC}}(t_{\infty},e)=1-\frac{\left(\sqrt{N(N-2)}+\sqrt{N-1}+1\right)^{2}}{N^{2}(N-1)}$
(22)

which is always lower than the one obtained via the central node as initial
state. Hence, the asymptotic distance

$\displaystyle D_{\text{\tiny QC}}(t_{\infty})$
$\displaystyle=\max\left[D_{\text{\tiny QC}}(t_{\infty},c),D_{\text{\tiny
QC}}(t_{\infty},e)\right]=D_{\text{\tiny QC}}(t_{\infty},c)$ (23)

of the star-graph has the same expression of the asymptotic distance obtained
for the complete graph, Eq. (14), as shown in Fig. 2. We can thus conclude
that the quantumness of the QW is better preserved asymptotically if the
walker is initially localized in the central node of the graph.

##  4 Decoherence in the position basis

Besides energy, the other natural basis to consider for decoherence phenomena
is that of the states localized on the graph’s nodes
$\\{\ket{k}\\}_{k=1}^{N}$. In the following, we analyze two different
phenomenological models of decoherence in this basis.
We first consider the Haken-Strobl master equation introduced in Eq. (4)
which, expressed in the node basis, can be recast into the following form:

$\frac{d\rho(t)}{dt}=-i\left[L,\rho(t)\right]-\gamma(\mathbb{J}-\mathbb{I})\circ\rho(t).$
(24)

Here $\mathbb{J}$ is the unit matrix, i.e. a matrix whose entries are all 1,
$\mathbb{I}$ is the identity matrix, $\rho$ is the density matrix expressed in
the node basis and $\circ$ denotes the Hadamard product of matrices (entry-
wise product). Notice how the off-diagonal damping terms on the rhs of the
equation do not depend on the distance between the sites. These dissipative
terms cause off-diagonal elements of the density matrix to vanish
asymptotically and, at the same time, they also induce a non-trivial dynamics
of the diagonal elements since the commutator in the master equation, i.e. the
unitary evolution, couples coherences with populations.

We have computed the QC-distance for the complete, cycle and star graphs, and
for different values of the decoherence parameter $\gamma$, as in Fig. 3. Some
general features of $D_{\text{\tiny QC}}(t)$ do not depend on the kind of
graph at study.

Figure 3: Quantum-classical distance for a walker subject to the Haken-Strobl
decoherent dynamics described by Eq. (24) for a (a) complete (b) cycle and (c)
star graph with $N=7$ nodes, computed for different values of the dephasing
parameter $\gamma$.

In particular, we find that the quantum-classical distance, after overcoming
one or two local maxima, goes to zero asymptotically. This in turn means that
the quantum walk reaches the uniform distribution as a stationary state.
Hence, contrary to the model of intrinsic decoherence in the energy basis,
this map is able to suppress all quantum features of the QW and turn it into
the classical random walk asymptotically. The cuspids in Fig. 3(c)
corresponding to the star graph case, arise because of the maximization over
classical initial states involved in the definition of $D_{\text{\tiny
QC}}(t)$. In particular, for large values of $\gamma$ and at short times, the
central node is the one achieving maximal QC-distance, while after the point
where the function is not differentiable, the maximum is obtained by preparing
the walker in any of the external nodes. On the other hand, for smaller values
of $\gamma$ the maximization is achieved at all times by initializing the QW
in the central node of the star graph.

Also in this case, the decoherence parameter $\gamma$ affects the speed of
convergence of the QC-distance to its horizontal asymptote. However, as
opposed to the intrinsic decoherence model, it is not true anymore that
whenever $\gamma$ grows so does the speed of convergence of $D_{\text{\tiny
QC}}$ to its asymptotic value. In fact, there is a value of $\gamma$,
dependent on the dimension and on the topology of the graph, after which there
is an ’inversion’ and the convergence speed starts decreasing. This fact can
be intuitively understood in the asymptotic scenario $\gamma\gg 1$, where the
off-diagonal elements of the density matrix experience approximately pure
exponential decay, since we can neglect the unitary evolution. It is then
trivial to show that, within this approximation, the system stays in the
initial localized state. We thus conclude that, as $\gamma$ grows beyond a
certain threshold, decoherence effects dominate over the unitary evolution and
the system is frozen in the initial state. As a result it takes increasingly
more time for the quantum walk to reach the uniform distribution for larger
values of $\gamma$.

The second model of decoherence in the nodes basis we consider is the quantum
stochastic walk, where the classical and the quantum dynamics are mixed at the
master equation level via interpolation through a single real parameter $p$,
see Eq. (5). We can solve this master equation numerically and compute the QC-
distance for different values of the mixing parameter $p$ and for the classes
of graphs we have considered in this work. Our numerical results show that
this kind of noise is able to classicalize the quantum walk asymptotically,
regardless of the topology of the underlying graph and for every value of
$p>0$. The parameter $p$ only affects the speed of convergence of
$D_{\text{\tiny QC}}(t)$ to zero, as can be seen in Fig. 4.

Figure 4: Quantum-classical distance for a walker subject to decoherent
dynamics induced by QSW for a (a) complete (b) cycle and (c) star graph with
$N=7$ nodes, computed for different values of the mixing parameter $p$.

The larger the value of $p$ the faster the QW transitions into a classical
random walk, since the classical component in the dynamics has a larger weight
in this case, according to Eq. (5). We point out that, contrary to the two
previous models of decoherence, in this case we find that the QC-distance of a
quantum walker initially localized in the central node of a star graph does
not coincide with that of a quantum walk on a complete graph. The
discontinuity in the QC-distance derivative in Fig. 4(c) signals a change of
the initial state that satisfies the maximization condition in the definition
(6). In particular, while at short times this condition is achieved by having
the initial state localized in the central node, at larger times this is
attained by initializing the walker to any of the external nodes. As a final
remark, we want to highlight the shorter time-scale in Fig. 4 with respect to
Fig. 3, indicating a faster classicalization dynamics. The QSW model appears
to be the less robust to decoherence for the topologies and choice of
parameters considered.

##  5 Conclusions

Noise is a challenge to practical realisation of quantum walks. Indeed, the
presence of noise induces decoherence, and loss of quantum features, which are
critical to achieve quantum advantages, i.e. to outperform protocols and
algorithms based on classical random walks.

In this work, upon employing a fidelity-based measure of dynamical distance,
we have addressed the effects of decoherence on CTQWs. In particular, we have
investigated quantitatively the differences between the dynamics of a quantum
walker in the presence of noise, and that of the corresponding classical
walker on a given graph. In this way, we have been able to assess if, and to
which extent, decoherence makes the quantum walker to turn into a classical
incoherent random walker.

We have considered three different models of decoherence for a CTQW. We have
first focused on intrinsic decoherence, i.e. decoherence in the energy
eigenbasis, and linked the degeneracy of the Laplacian spectrum to the
impossibility for this kind of noise to completely classicalize the quantum
walker. In this case, we have analytically characterised the asymptotic
behaviour of the quantum-classical distance, and discussed how the
connectivity of the graph influences the speed of convergence to its
asymptotic value. We have then shifted our attention towards two models of
decoherence in the node basis, namely the quantum dynamics arising from the
Haken-Strobl master equation, and the quantum stochastic walk model, which
interpolates between the classical and quantum RW by means of a single real
mixing parameter. In both cases we have shown that all quantum features of the
dynamics are suppressed asymptotically, i.e. the quantum walker behaves like a
classical random walker in the long-time limit.

Our analysis has shown that, at least for the considered classes of graphs,
the qualitative features of the quantum-classical distance are not influenced
by the topology of the graph, and by the number of its nodes. In addition, the
asymptotic value of the quantum-classical distance does not depend on the
relevant noise parameter. Finally, we have found that there is no universal
behavior of the classicalization speed as a function of the decoherence rates.
A larger decoherence corresponds to a faster convergence of the QC-distance to
its asymptotic value for intrinsic decoherence and the QSW models, whereas in
the Haken-Strobl scenario, larger values of the decoherence rate induce
localization of the walker.

Our results contribute to deepen the knowledge on the effects of noise and
decoherence on quantum walks, and pave the way to engineering of decoherence,
as well as to identifying regimes where its effects may be mitigated.

## Acknowledgments

Work done under the auspices of INdAM-GNFM. G.B. is part of the AppQInfo MSCA
ITN which received funding from the EU Horizon 2020 research and innovation
programme under the Marie Sklodowska-Curie grant agreement No 956071.

## Appendices

##  Appendix A Graph symmetries and degenerate eigenvalues

In the following we show that the survival of quantum coherences in the
asymptotic quantum state Eq. (9), due to the presence of degenerate Laplacian
eigenstates, can be traced back to the symmetries of the underlying graph. The
symmetries of a graph $G(V,E)$ are, in turn, related to the group $\Gamma(G)$
of its automorphisms, i.e. the group of permutations $\sigma:V\rightarrow V$
of the set of vertices $V$ such that $\left(\sigma(n),\sigma(p)\right)\in
E\Leftrightarrow(n,p)\in E$, $\forall n,p\in V$, i.e. adjacency is preserved.
It follows, for example, that for the complete graph every permutation of the
nodes identifies a symmetry while, for the star graph, only permutations of
the external nodes are automorphisms. The connection between the symmetries of
a graph and the degeneracy of its spectrum is provided by the following
theorem merris :

Theorem: Let $G(V,E)$ be a connected graph and $\Gamma(G)$ the group of its
automorphisms. If a permutation in $\Gamma(G)$ contains $s$ odd cycles and $t$
even cycles, then the Laplacian matrix will have at most $s+2t$ simple
eigenvalues.

It follows that if a permutation in $\Gamma(G)$ contains a cycle with at least
3 elements, the spectrum of $L$ is degenerate and the QC-distance will not
reach zero asymptotically. We stress that this is only a sufficient condition
for degeneracy. This explains why the QC-distance in Eq. (10) does not reach
zero for the classes of graphs studied in this paper, where it is particularly
easy to find symmetries involving three or more nodes. On the other hand, we
expect to witness a different behavior with other classes of graphs, such as
random graphs. In this case, especially for large values of $N$, it is likely
that the only symmetries of the graph will be permutations decomposable in
cycles of 1 and 2 nodes only. Consequently, in this situation the theorem only
tells us that $L$ will have at most $N$ simple eigenvalues, hence it is of no
help.

## References

  * (1) J. Kempe, Quantum random walks: An introductory overview, Contemp. Phys. 44(4), 307 (2003)
  * (2) S.E. Venegas-Andraca, Quantum walks: a comprehensive review, Quant. Inf. Process. 11(5), 1015 (2012)
  * (3) F. Xia, J. Liu, H. Nie, Y. Fu, L. Wan, X. Kong, Random walks: A review of algorithms and applications, IEEE Trans. Emerg. Top. Comput. Intell. 4(2), 95 (2020).  DOI 10.1109/TETCI.2019.2952908
  * (4) K. Kadian, S. Garhwal, A. Kumar, Quantum walk and its application domains: A systematic review, Comput. Sci. Rev. 41, 100419 (2021)
  * (5) M. Frigerio, C. Benedetti, S. Olivares, M.G.A. Paris, Generalized quantum-classical correspondence for random walks on graphs, Phys. Rev. A 104, L030201 (2021)
  * (6) Y. Aharonov, L. Davidovich, N. Zagury, Quantum random walks, Phys. Rev. A 48, 1687 (1993)
  * (7) E. Farhi, S. Gutmann, Quantum computation and decision trees, Phys. Rev. A 58, 915 (1998)
  * (8) O. Mülken, A. Blumen, Continuous-time quantum walks: Models for coherent transport on complex networks, Phys. Rep. 502(2-3), 37 (2011)
  * (9) O. Mülken, V. Pernice, A. Blumen, Quantum transport on small-world networks: A continuous-time quantum walk approach, Phys. Rev. E 76, 051125 (2007)
  * (10) L. Razzoli, M.G.A. Paris, P. Bordone, Transport efficiency of continuous-time quantum walks on graphs, Entropy 23(1), 85 (2021)
  * (11) M. Maciel Cássio, C.F.O. Mendes, W.T. Strunz, M. Galiceanu, Quantum transport on generalized scale-free networks, Phys. Rev. A 102, 032219 (2020)
  * (12) A. Ambainis, Quantum walks and their algorithmic applications, Int. J. Quantum Inf. 1(04), 507 (2003)
  * (13) R. Portugal, _Quantum Walks and Search Algorithms_ (Springer International Publishing, 2018)
  * (14) A.M. Childs, Universal computation by quantum walk, Phys. Rev. Lett. 102, 180501 (2009)
  * (15) K. Wang, Y. Shi, L. Xiao, J. Wang, Y.N. Joglekar, P. Xue, Experimental realization of continuous-time quantum walks on directed graphs and their application in pagerank, Optica 7(11), 1524 (2020)
  * (16) R. Herrman, T.G. Wong, Simplifying continuous-time quantum walks on dynamic graphs, Quantum Inf. Process. 21(2), 54 (2022)
  * (17) N. Inui, K. Kasahara, Y. Konishi, N. Konno, evolution of continuous-time quantum random walks on circles, Fluct. Noise Lett. 05(01), L73 (2005)
  * (18) M.B. Plenio, S.F. Huelga, Dephasing-assisted transport: quantum networks and biomolecules, New J. Phys. 10(11), 113019 (2008)
  * (19) F. Caruso, A.W. Chin, A. Datta, S.F. Huelga, M.B. Plenio, Highly efficient energy excitation transfer in light-harvesting complexes: The fundamental role of noise-assisted transport, J. Chem. Phys. 131(10), 105106 (2009)
  * (20) A. Schreiber, K.N. Cassemiro, V. Potoček, A. Gábris, I. Jex, C. Silberhorn, Decoherence and disorder in quantum walks: From ballistic spread to localization, Phys. Rev. Lett. 106, 180403 (2011)
  * (21) C. Benedetti, F. Buscemi, P. Bordone, M.G.A. Paris, Non-markovian continuous-time quantum walks on lattices with dynamical noise, Phys. Rev. A 93, 042313 (2016)
  * (22) D. Tamascelli, A. Segati, S. Olivares, Dephasing assisted transport on a biomimetic ring structure, Int. J. Quant. Inf. 15(08), 1740006 (2017)
  * (23) C. Benedetti, M.A.C. Rossi, M.G.A. Paris, Continuous-time quantum walks on dynamical percolation graphs, Europhys. Lett. 124(6), 60001 (2019)
  * (24) A. Kurt, M.A.C. Rossi, J. Piilo, Efficient quantum transport in a multi-site system combining classical noise and quantum baths, New J. Phys. 22(1), 013028 (2020)
  * (25) V. Gualtieri, C. Benedetti, M.G.A. Paris, Quantum-classical dynamical distance and quantumness of quantum walks, Phys. Rev. A 102, 012201 (2020)
  * (26) M. Frigerio, C. Benedetti, S. Olivares, M.G.A. Paris, Quantum-classical distance as a tool to design optimal chiral quantum walks, Phys. Rev. A 105, 032425 (2022)
  * (27) G.J. Milburn, Intrinsic decoherence in quantum mechanics, Phys. Rev. A 44, 5401 (1991)
  * (28) H. Haken, G. Strobl, An exact solvable model for coherent and incoherent excitation motion, Z. Phys. 262, 135 (1973)
  * (29) J.D. Whitfield, C.A. Rodríguez-Rosario, A. Aspuru-Guzik, Quantum stochastic walks: A generalization of classical random walks and quantum walks, Phys. Rev. A 81, 022323 (2010)
  * (30) B. Nica, _A brief introduction to spectral graph theory_ (EMS Textbooks in Mathematics, 2018)
  * (31) T.G. Wong, L. Tarrataca, N. Nahimov, Laplacian versus adjacency matrix in quantum walk search, Quantum Inf. Proc. 15(10), 4029 (2016)
  * (32) A. Candeloro, L. Razzoli, S. Cavazzoni, P. Bordone, M.G.A. Paris, Continuous-time quantum walks in the presence of a quadratic perturbation, Phys. Rev. A 102, 042214 (2020)
  * (33) P. Rebentrost, M. Mohseni, I. Kassal, S. Lloyd, A. Aspuru-Guzik, Environment-assisted quantum transport, New J. Phys. 11, 033003 (2009)
  * (34) F. Caruso, Universally optimal noisy quantum walks on complex networks, New J. Phys. 16 (2014)
  * (35) X.P. Xu, Exact analytical results for quantum walks on star graphs, J. Phys. A Math. Theor. 42(11), 115205 (2009)
  * (36) L. Razzoli, P. Bordone, M.G.A. Paris, Universality of the fully connected vertex in laplacian continuous-time quantum walk problems, arXiv:2202.13824 (2022)
  * (37) R. Merris, Laplacian matrices of graphs: a survey, Linear Algebra Appl. 197-198, 143 (1994)