* [CL89] Anne Condon and Richard J. Lipton.  On the complexity of space bounded interactive proofs.  In 30th Annual Symposium on Foundations of Computer Science (FOCS), pages 462–467. IEEE, 1989.
  * [COW16] Ventsislav Chonev, Joël Ouaknine, and James Worrell.  On the Skolem problem for continuous linear dynamical systems.  In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming (ICALP), volume 55 of LIPIcs, pages 100:1–100:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.
  * [CY95] Costas Courcoubetis and Mihalis Yannakakis.  The complexity of probabilistic verification.  Journal of the ACM, 42(4):857–907, 1995.
  * [dA99] Luca de Alfaro.  Computing minimum and maximum reachability times in probabilistic systems.  In Jos C. M. Baeten and Sjouke Mauw, editors, 10th International Conference on Concurrency Theory (CONCUR), volume 1664 of Lecture Notes in Computer Science, pages 66–81. Springer, 1999.
  * [EvdPSW03] Graham Everest, Alfred Jacobus van der Poorten, Igor Shparlinski, and Thomas Ward.  Recurrence sequences.  ACM, 2003.
  * [EY05] Kousha Etessami and Mihalis Yannakakis.  Recursive Markov decision processes and recursive stochastic games.  In Luís Caires, Giuseppe F. Italiano, Luís Monteiro, Catuscia Palamidessi, and Moti Yung, editors, 32nd International Colloquium on Automata, Languages and Programming (ICALP), volume 3580 of Lecture Notes in Computer Science, pages 891–903. Springer, 2005.
  * [EY09] Kousha Etessami and Mihalis Yannakakis.  Recursive markov chains, stochastic grammars, and monotone systems of nonlinear equations.  J. ACM, 56(1):1:1–1:66, 2009.
  * [EY15] Kousha Etessami and Mihalis Yannakakis.  Recursive Markov decision processes and recursive stochastic games.  Journal of the ACM, 62(2):1–69, 2015.
  * [FK15] Vojtech Forejt and Jan Krcál.  On frequency LTL in probabilistic systems.  In Luca Aceto and David de Frutos-Escrig, editors, 26th International Conference on Concurrency Theory (CONCUR), volume 42 of LIPIcs, pages 184–197. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015.
  * [FKK15] Vojtech Forejt, Jan Krcál, and Jan Kretínský.  Controller synthesis for MDPs and frequency $\text{LTL}_{{\setminus}{\text{GU}}}$.  In Martin Davis, Ansgar Fehnker, Annabelle McIver, and Andrei Voronkov, editors, 20th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR), volume 9450 of Lecture Notes in Computer Science, pages 162–177. Springer, 2015.
  * [GKM14] Friedrich Gretz, Joost-Pieter Katoen, and Annabelle McIver.  Operational versus weakest pre-expectation semantics for the probabilistic guarded command language.  Performance Evaluation, 73:110–132, 2014.
  * [Hen13] Thomas A. Henzinger.  Quantitative reactive modeling and verification.  Computer Science - Research and Development, 28(4):331–344, 2013\.
  * [HHHK05] Vesa Halava, Tero Harju, Mika Hirvensalo, and Juhani Karhumäki.  Skolem’s problem–on the border between decidability and undecidability.  Technical report, Technical Report 683, Turku Centre for Computer Science, 2005.
  * [HK79] Arie Hordijk and Lodewijk Kallenberg.  Linear programming and Markov decision chains.  Management Science, 25(4):352–362, 1979.
  * [HK15] Christoph Haase and Stefan Kiefer.  The odds of staying on budget.  In Magnus M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, 42nd International Colloquium on Automata, Languages, and Programming (ICALP), volume 9134 of Theoretical Computer Science and General Issues, pages 234–246. Springer, 2015.
  * [HKL17] Christoph Haase, Stefan Kiefer, and Markus Lohrey.  Computing quantiles in Markov chains with multi-dimensional costs.  In 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1–12. IEEE, 2017.
  * [KGJ+15] Joost-Pieter Katoen, Friedrich Gretz, Nils Jansen, Benjamin Lucien Kaminski, and Federico Olmedo.  Understanding probabilistic programs.  In Roland Meyer, André Platzer, and Heike Wehrheim, editors, Correct System Design - Symposium in Honor of Ernst-Rüdiger Olderog on the Occasion of His 60th Birthday, volume 9360 of Lecture Notes in Computer Science, pages 15–32. Springer, 2015.
  * [KK15] Benjamin Lucien Kaminski and Joost-Pieter Katoen.  On the hardness of almost–sure termination.  In Giuseppe F. Italiano, Giovanni Pighizzini, and Donald T. Sannella, editors, 40th International Symposium on Mathematical Foundations of Computer Science (MFCS), volume 9235 of Theoretical Computer Science and General Issues, pages 307–318. Springer, 2015.
  * [KM18] Jan Kretínský and Tobias Meggendorfer.  Conditional value-at-risk for reachability and mean payoff in Markov decision processes.  In 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 609–618. ACM, 2018.
  * [LPM+15] Yu Lu, Zhaoguang Peng, Alice A Miller, Tingdi Zhao, and Christopher W Johnson.  How reliable is satellite navigation for aviation? Checking availability properties with probabilistic verification.  Reliability Engineering & System Safety, 144:95–116, 2015.
  * [Meg22] Tobias Meggendorfer.  Risk-aware stochastic shortest path.  In Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022, Thirty-Fourth Conference on Innovative Applications of Artificial Intelligence, IAAI 2022, The Twelveth Symposium on Educational Advances in Artificial Intelligence, EAAI 2022 Virtual Event, February 22 - March 1, 2022, pages 9858–9867. AAAI Press, 2022.
  * [MHC99] Omid Madani, Steve Hanks, and Anne Condon.  On the undecidability of probabilistic planning and infinite-horizon partially observable Markov decision problems.  In 16th National Conference on Artificial Intelligence (AAAI), pages 541–548. MIT Press, 1999.
  * [MMM05] Annabelle McIver, Carroll Morgan, and Charles Carroll Morgan.  Abstraction, refinement and proof for probabilistic systems.  Springer, 2005.
  * [MSS20] Rupak Majumdar, Mahmoud Salamati, and Sadegh Soudjani.  On decidability of time-bounded reachability in CTMDPs.  In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming (ICALP), volume 168 of LIPIcs, pages 133:1–133:19. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2020.
  * [MSTW17] Richard Mayr, Sven Schewe, Patrick Totzke, and Dominik Wojtczak.  MDPs with energy-parity objectives.  In 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1–12. IEEE, 2017.
  * [Odi92] Piergiorgio Odifreddi.  Classical recursion theory: The theory of functions and sets of natural numbers.  Elsevier, 1992.
  * [OGJ+18] Federico Olmedo, Friedrich Gretz, Nils Jansen, Benjamin Lucien Kaminski, Joost-Pieter Katoen, and Annabelle Mciver.  Conditioning in probabilistic programming.  ACM Transactions on Programming Languages and Systems, 40(1):4:1–4:50, 2018.
  * [OW12] Joël Ouaknine and James Worrell.  Decision problems for linear recurrence sequences.  In Alain Finkel, Jerome Leroux, and Igor Potapov, editors, 6th International Workshop on Reachability Problems (RP), volume 7550 of Theoretical Computer Science and General Issues, pages 21–28. Springer, 2012\.
  * [OW14a] Joël Ouaknine and James Worrell.  On the positivity problem for simple linear recurrence sequences.  In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, 41st International Colloquium on Automata, Languages, and Programming (ICALP), volume 8573 of Theoretical Computer Science and General Issues, pages 318–329. Springer, 2014.
  * [OW14b] Joël Ouaknine and James Worrell.  Positivity problems for low-order linear recurrence sequences.  In 25th Annual ACM-SIAM Symposium on Discrete algorithms (SODA), pages 366–379. SIAM, 2014.
  * [OW14c] Joël Ouaknine and James Worrell.  Ultimate positivity is decidable for simple linear recurrence sequences.  In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, 41st International Colloquium on Automata, Languages, and Programming (ICALP), volume 8573 of Theoretical Computer Science and General Issues, pages 330–341. Springer, 2014.
  * [OW15] Joël Ouaknine and James Worrell.  On linear recurrence sequences and loop termination.  ACM SIGLOG News, 2(2):4–13, 2015.
  * [Paz71] Azaria Paz.  Introduction to Probabilistic Automata.  Academic Press, 1971.
  * [PB19] Jakob Piribauer and Christel Baier.  Partial and conditional expectations in Markov decision processes with integer weights.  In Mikolaj Bojanczyk and Alex Simpson, editors, 22nd International Conference on Foundations of Software Science and Computation Structures (FoSSaCS), volume 11425 of Lecture Notes in Computer Science, pages 436–452. Springer, 2019.
  * [PB20] Jakob Piribauer and Christel Baier.  On Skolem-hardness and saturation points in Markov decision processes.  In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming (ICALP), volume 168 of LIPIcs, pages 138:1–138:17. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2020.
  * [Pir21] Jakob Piribauer.  On non-classical stochastic shortest path problems.  PhD thesis, Technische Universität Dresden, Germany, 2021.
  * [Put94] Martin L. Puterman.  Markov Decision Processes: Discrete Stochastic Dynamic Programming.  John Wiley & Sons, Inc., 1994.
  * [RRS17] Mickael Randour, Jean-François Raskin, and Ocan Sankur.  Percentile queries in multi-dimensional Markov decision processes.  Formal Methods in System Design, 50(2-3):207–248, 2017.
  * [STM84] Tarlok N. Shorey, Robert Tijdeman, and Max Mignotte.  The distance between terms of an algebraic recurrence sequence.  Journal für die reine und angewandte Mathematik, 1984(349):63–76, 1984.
  * [Tiw04] Ashish Tiwari.  Termination of linear programs.  In Rajeev Alur and Doron Peled, editors, 16th International Conference on Computer Aided Verification (CAV), volume 3114 of Lecture Notes in Computer Science, pages 70–82. Springer, 2004.
  * [UB13] Michael Ummels and Christel Baier.  Computing quantiles in Markov reward models.  In Frank Pfenning, editor, 16th International Conference on Foundations of Software Science and Computation Structures (FoSSaCS), volume 7794 of Lecture Notes in Computer Science, pages 353–368. Springer, 2013\.
  * [Ury00] Stanislav Uryasev.  Conditional value-at-risk: optimization algorithms and applications.  In Computational Intelligence and Financial Engineering (CIFEr), pages 49–57. IEEE, 2000.
  * [Ver85] NK Vereshchagin.  The problem of appearance of a zero in a linear recurrence sequence.  Mat. Zametki, 38(2):609–615, 1985.


# Normalized K-Means for Noise-Insensitive
Multi-Dimensional Feature Learning

Nicholas Pellegrino Paul W. Fieguth Parsin Haji Reza  PhotoMedicine Labs,
Department of Systems Design Engineering, University of Waterloo
Waterloo, Ontario, Canada
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Many measurement modalities which perform imaging by probing an object pixel-
by-pixel, such as via Photoacoustic Microscopy, produce a multi-dimensional
feature (typically a time-domain signal) at each pixel. In principle, the many
degrees of freedom in the time-domain signal would admit the possibility of
significant multi-modal information being implicitly present, much more than a
single scalar “brightness”, regarding the underlying targets being observed.
However, the measured signal is neither a weighted-sum of basis functions
(such as principal components) nor one of a set of prototypes (K-means), which
has motivated the novel clustering method proposed here, capable of learning
centroids (signal shapes) that are related to the underlying, albeit unknown,
target characteristics in a scalable and noise-robust manner.

##  I Introduction

Medical imaging broadly serves as a powerful diagnostic tool, often non-
invasively giving medical care providers valuable information that cannot be
obtained otherwise [1, 2]. Many biomedical sensing techniques operate by
capturing time-domain (TD) signals from which diagnostically relevant
information can be inferred. A list of some of these modalities includes
sonography / ultrasound imaging [3, 4], echocardiography [5],
electrocardiography [6, 7, 8], electromyography [9, 10], phonocardiography
[11, 12], phonomyography [13], etc. In many cases objects are scanned, pixel-
by-pixel, to produce a TD signal at each pixel. Two such modalities are Time-
Domain Optical Coherence Tomography (TD-OCT) [14, 15] and Photoacoustic
Microscopy (PAM) [16, 17, 18].

In principal, the many degrees of freedom available within TD signals admit
the possibility of significant multi-modal information related to the imaged
target being implicitly present, far beyond a single scalar value used to
represent pixel “brightness”. However, extracting the information from these
signals is not necessarily straightforward. Indeed, the work presented in this
paper is motivated by the TD signals of Photoacoustic Remote Sensing (PARS)
Microscopy [19, 20, 21, 22, 23], a novel all-optical variation of
photoacoustic microscopy. The underlying physics lead to TD signals having
shapes specific to tissue type, but where the signals from a given target may
vary in amplitude, be inverted (negative amplitudes), and suffer from noise.
What is required is a set of time-domain _features_ , that adequately capture
information from the underlying target that is present in the TD signals.

##  II Background

This work is motivated by imaging modalities that scan, pixel-by-pixel,
measuring a signal, $s_{j}(t)$, over time, $t$, at each pixel, $j$:

$s_{j}(t)=\alpha_{j}f_{i}(t),$ (1)

for some weight, $\alpha_{j}$, applied to feature $f_{i}$ for target type $i$.
In principle $t$ is continuous, however in practice the TD signals are
recorded by a data acquisition system. For the purpose of this work, the same
notation is used for both the discrete- and continuous-time representations,
however all numerical computations involving the TD signals clearly refer to
the measured discrete-time representation.

Conventionally, in PAM and PARS [2, 19, 20, 21, 24, 25, 26], only a scalar
amplitude is extracted from each TD signal, accomplished by either using a
Hilbert transform [27] to find an envelope of the signal, from which the
difference between maximum and minimum values is computed, or by directly
computing the difference between maximum and minimum of the raw TD signal
itself. Recently, other methods have been developed to extract additional
information related to the frequency content of the signals, as a means of
inferring information related to the imaged target [28, 29, 30]. This work
takes a different approach by proposing an unsupervised (clustering) approach
to learn time-domain features that relate to the underlying target.

In principle, such a feature inference would seem to have been solved.
Principal Components Analysis (PCA) and its variations [31, 32, 33, 34, 35]
are capable of extracting features (the principal components) from TD data;
the principal components yield a representation,

$s_{j}(t)=\sum_{i}\alpha_{j,i}b_{i}(t),$ (2)

based on a weighted sum of basis elements $b_{i}$. However the optimal basis
elements are those minimizing the variance of the residual error, and not
necessarily those which _individually_ effectively represent most of the
signals, as in Equation 1. That is, the principal components are unknown
weighted combinations of the desired features, and therefore do not
individually lead to meaningful features.

Clustering methods, such as K-Means [36, 37, 38, 39], assume _all_ measured
data-points (TD signals) are _one_ of a set of prototypes, and have variation
only as a consequence of measurement error and noise. This assumption does not
hold in Equation 1, as measured TD signals may be scaled or inverted versions
of what would be a prototype relating to a specific target.

A further clustering issue arises when computing centroids. In K-Means,
cluster centroids are calculated as the mean of the points associated to each
cluster. High amounts of background noise, if included in any cluster, would
strongly influence the mean, steering it away from a truer representation of
the non-noise portion of the cluster.

Addressing these constraints has prompted the development of the method
proposed here, capable of learning features that relate characteristic signal
shapes to individual components of the target, in a scalable and noise-robust
manner.

##  III Methods

We wish to cluster TD signals based on their signal _shape_ , but not
amplitude. A given pixel (and its corresponding TD signal) may be expressed in
terms of characteristic signal shapes of one or more targets $\\{f_{i}\\}$ and
a residual term, $r_{j}(t)$,

$s_{j}(t)=\sum_{\forall i}\alpha_{i,j}f_{i}(t)+r_{j}(t),$ (3)

but where most pixels come from only a single target, as in Equation 1, thus
that $\\{\alpha_{i,j}\\}$ is sparse. The proposed method is based on K-Means,
but varies in its definition of distance and its method for computing cluster
centroids (the learned features). The characteristic signals shapes, a set of
$K$ centroids, $\mathscr{F}=\\{f_{i}(t)\\}$, $i=1,...,K$, may be discoverable
by clustering the TD signals from a given image.

Note that TD signals are just vectors in space, $\mathbb{R}^{n}$, where the
dimension, $n$, of the space is simply the number of discrete TD samples.
Thus, the equivalences $s(t)\equiv\vec{s},f(t)\equiv\vec{f}$, etc. are made.
Because TD signals are treated as Cartesian vectors, the signal shape is then
analogous to the vector _angle_.

TD signals associated with a given target may be arbitrarily scaled and be
subject to noise, thus any proposed clustering algorithm must be tolerant to
these effects. The assumptions for the proposed method are as follows:

  1. 1.

Each underlying class (i.e., isolated component) is characterized by a single
prototype signal.

  2. 2.

_Most_ pixels are a member of only one class. Relatively few pixels may be
members of several classes (i.e., exhibit a response associated with a mixture
of underlying components).

  3. 3.

The noise level, both in background and in higher-amplitude signals, is
significant.

  4. 4.

A large fraction of the pixels may be a member of no class, and thus contains
only noise.

###  III-A Distance Metric

The clustering algorithm requires a distance metric that is

  1. 1.

Scale (amplitude) invariant, and

  2. 2.

polarity-agnostic (i.e., insensitive to signal inversions).

Consider an arbitrary TD signal, $\vec{s}~{}=~{}m\vec{u}$, for unit-vector
$\vec{u}$ that defines the characteristic signal. The _negative_ of this
signal, $-\vec{s}=(-m)\vec{u}$, shares the same direction, $\vec{u}$, however
the sign is opposite. The angle between $\vec{s}$ and $-\vec{s}$ is $\pi$
radians, however they share the exact same signal shape, and are thus
associated with the same underlying imaged target. Therefore, a polarity-
agnostic distance metric must assign a distance of zero between $\vec{s}$ and
$-\vec{s}$.

For simplicity, and to achieve symmetry in the distance metric, all angles
will be considered to be positive. The angle, $\vartheta$, between two
vectors, $\vec{v}_{1}$ and $\vec{v}_{2}$, is defined as

$\vartheta\mathrel{\mathop{\mathchar
58\relax}}=\angle\left(\vec{v}_{1},\vec{v}_{2}\right)=\arccos\left(\frac{\langle\vec{v}_{1},\vec{v}_{2}\rangle}{\lVert\vec{v}_{1}\rVert\lVert\vec{v}_{2}\rVert}\right),$
(4)

for $\arccos(\cdot)$ defined abstractly as $x\mapsto\arccos(x)$,
$[-1,1]~{}\to~{}[0,\pi]$. The proposed distance metric, satisfying polarity
agnosticism, is

$d\left(\vec{v}_{1},\vec{v}_{2}\right)=\sin(\vartheta),$ (5)

for $\sin(\cdot)$ defined on the interval $[0,\pi]$, constraining the range of
$d(\cdot)$ to $[0,1]$. Note that the function composition

$\sin\left(\arccos(x)\right)=\sqrt{1-x^{2}},$ (6)

therefore the distance metric simplifies as

$d(\vec{v}_{1},\vec{v}_{2})=\sqrt{1-\left(\frac{\langle\vec{v}_{1},\vec{v}_{2}\rangle}{\lVert\vec{v}_{1}\rVert\lVert\vec{v}_{2}\rVert}\right)^{2}}.$
(7)

###  III-B Calculation of Cluster Centroids

As mentioned at the start of Section III, an alternative method for computing
cluster centroids is required. Although angle-based variations of K-Means do
exist — such as Spherical K-Means [40, 41, 42] whereby data-points are
projected onto the unit-hypersphere via normalization and distance is defined
by cosine _dissimilarity_ — centroids are still computed by taking the mean of
all points within a given cluster, an approach which does not apply to
Equation 3:

  * •

We have a requirement for polarity-agnosticism, whereby antipodal TD signals
are clustered together, and these signals will largely cancel (negate each
other) when averaged.

  * •

A large fraction of pixels are background (composed of zero-mean noise),
having a random angle, and therefore are associated to clusters at random,
leading to significant biases if included in the sample mean, and it is highly
undesirable for background noise to dominate the learned centroids.

Instead, we desire a unit-vector pointing in the direction of the non-noise
portion of the given cluster to define the centroid. The method needs to be
polarity-agnostic, however we do not actually know, a priori, whether both
positive and negative examples are present. Given the set of points,
$\mathscr{S}_{i}$, associated with cluster, $i$, we construct the union set,

$\mathscr{S}_{i}^{\pm}=\mathscr{S}_{i}\bigcup\,\left(-\mathscr{S}_{i}\right),$
(8)

made up of the cluster, $\mathscr{S}_{i}$, and its negated points,
$-\mathscr{S}_{i}$. From $\mathscr{S}_{i}^{\pm}$, the centroid can be found as
the direction of greatest variance (the first principal component from the
sample covariance of $\mathscr{S}_{i}^{\pm}$), allowing higher amplitude
signals (having a greater signal to noise ratio) to have greater influence,
effectively eliminating the influence of background noise (those random-angle
data-points near the origin).

###  III-C Algorithm

With the distance metric and the method for calculating centroids now defined,
the clustering algorithm, detailed in Algorithm 1, follows fairly naturally
from conventional K-Means. The calculation of cluster centroids is detailed in
Centroid Update (24), and on 30 an SVD (Singular Value Decomposition) is used
to extract the first principal component.

Similar to conventional K-Means, we need to define convergence criteria:

  1. 1.

Sufficiently few data-points change clusters between iterations (algorithm
parameter MovesCriterion), or

  2. 2.

The difference in the mean residual is sufficiently small between iterations
(algorithm parameter DifferenceCriterion).

Algorithm 1 Proposed Clustering Algorithm

Input:
Set of TD signals, $\mathscr{S}=\\{s_{j}(t)\\}$, to be clustered.
Number of desired clusters, $K$.
Minimum allowable moves criterion, MovesCriterion.
Difference in mean residual criterion, DifferenceCriterion. Output:
Set of cluster labels, $\mathscr{L}=\\{\ell\\}$, associated with each TD
signal.
Set of cluster centroids, $\mathscr{F}=\\{\vec{f}_{i}\\}$, for $i=1,...,K$.

1: Initialization:

2: Randomly select $K$ data-points as initial centroids.

3:for $i=1,...,K$ do

4: $\vec{f}_{i}\overset{Random}{\leftarrow}s(t)\in\mathscr{S}$

5:end for

6: Set previous value of mean residual to 0.

7:$\mu_{r}^{prev}\leftarrow 0$

8:repeat

9: Set number of changed cluster labels to 0.

10: $moves\leftarrow 0$

11: Membership Update: Finding nearest centroid to each point.

12: for all $s_{j}(t)\in\mathscr{S}$ do

13:
$\ell_{j}\leftarrow\operatorname*{arg\,min}_{\,i\in\\{1,...,K\\}}\Big{\\{}d\Big{(}s_{j}(t),\vec{f}_{i}\Big{)}\Big{\\}}$

14: Increment $moves$ if cluster membership changes.

15: if $\ell_{j}$ changed this iteration then

16: $moves\leftarrow moves+1$

17: end if

18: end for

19: Evaluate mean residual (objective).

20:
$\mu_{r}\leftarrow\frac{1}{\lVert\mathscr{S}\rVert}\sum_{s_{j}(t)\in\mathscr{S}}{\,d\left(s_{j}(t),\vec{f}_{\ell_{j}}\right)}$

21: $\Delta\mu_{r}\leftarrow\mu_{r}-\mu_{r}^{prev}$

22: $\mu_{r}^{prev}\leftarrow\mu_{r}$

23: Centroid Update: Use data-points within clusters to update.

24: for $i=1,...,K$ do

25: Get set of data-points within cluster.

26: $\mathscr{S}_{i}\leftarrow\left\\{s_{j}(t)\,\middle|\,\ell_{j}=i\right\\}$

27: Take union of set with its negative.

28:
$\mathscr{S}_{i}^{\pm}\leftarrow\mathscr{S}_{i}\bigcup\,\left(-\mathscr{S}_{i}\right)$

29: Compute first principal component via SVD. Assign to centroid.

30: $\vec{f}_{i}\leftarrow\text{PC}_{1}\left(\mathscr{S}_{i}^{\pm}\right)$

31: Normalize centroid to fall on unit-hypersphere

32: $\vec{f}_{i}\leftarrow\vec{f}_{i}/\lVert\vec{f}_{i}\rVert$

33: end for

34:until $\Delta\mu_{r}\leq\textit{DifferenceCriterion}$ OR
$moves\leq\textit{MovesCriterion}$

###  III-D Evaluation of Proposed Method

To illustrate the necessity for the proposed method, synthetic data are
generated and analyzed via standard Principal Components Analysis (PCA),
Angular-distance K-Means, and the proposed clustering method. The results are
shown in Section IV-A.

On the basis that none of the methods being compared are sensitive to
correlations between specific indices / samples of the TD signals, randomly
generated synthetic data are used. Additionally, it is the _angle_ between
vectors / signals that matters. It can be verified that the _ordering_ of
indices has no impact on angle by considering permutation matrices [43], which
can be used to permute the signal / vector indices, but do not cause the
_angle_ between vectors to change because permutation matrices are orthogonal.
Ground truth prototype signals are first generated, then scaled (including
negatives) versions with added noise are used to generate synthetic data.
Additionally, background noise (zero-signal with added noise) is included. To
improve visual interpretability, to appear similar to TD signals, temporal
correlations are introduced to the prototypes using a first-order auto-
regressive model [44].

When analyzing the results of each method, the learned features (either
centroids or principal components) are compared to the ground truth
prototypes. Additionally, in the case of clustering, membership is compared to
the ground truth class membership of the data-points.

Finally, the proposed method is applied to real-world data, collected from a
PARS microscope. Centroids (representative features) are learned and then are
used to extract feature amplitudes from the TD signals of the PARS image.
These results are shown in Section IV-B.

Briefly, feature amplitude extraction is achieved by performing a change of
basis on the TD signals. Given a set of feature vectors,
$\mathscr{F}=\\{\vec{f}_{i}\\}$, as in Equation 3, the TD signals can be
expressed as a weighted sum of the feature vectors plus a residual term:

$s_{j}(t)=\sum_{\forall i}{\alpha_{i,j}\vec{f}_{i}}+\vec{r}_{j}.$ (9)

Arranging the feature vectors as matrix columns, forming a matrix of features,
$F=\big{[}\vec{f}_{1}\mid\vec{f}_{2}\mid...\big{]}$, the preceding expression
then becomes $s_{j}(t)=F\vec{\alpha}_{j}+\vec{r}_{j}$. To solve for the vector
of feature weights, $\vec{\alpha}$, the pseudo-inverse [45] of $F$ is used,
thus, $\vec{\alpha}_{j}=F^{+}s_{j}(t)$.

##  IV Results

Figure 1: The cluster centroids learned from the human breast tissue slide in
Figure 3. A wide variety of signal shapes are learned and presented here.

###  IV-A Comparison of Methods on Synthetic Data

The creation of synthetic data for use in comparing the proposed method to PCA
and Angular-Distance K-Means was presented in Section III-D, with the results
shown in Figure 2. The first row contains the ground truth prototypes (left)
and class membership of the data-points (right). For visualization purposes in
the right column, the data-points, which are 30-dimensional, are projected
onto a 2D plane defined by the ground truth prototypes (except for the case
where PCA is used, where the data-points are projected into the principal
component space).

It can clearly be seen that neither PCA nor the Angular-Distance K-Means
produce learned features that even resemble the ground truth prototypes, since
neither approach is able to produce the desired sparse-weighted features,
whereas the proposed method is in fact highly effective at doing so. Further
discussion is given in Section V.

|  | Prototypes / Learned Features
---
| Data-Points & Membership
---
| Ground
---
Truth
|
---
|
---
| PCA
---
|
---
|
---
| Angular-Distance
---
K-Means
|
---
|
---
| Proposed
---
Method
|
---
|
---
Figure 2: Various methods are applied to learn features from synthetic data.
The first row shows the ground truth classes present in the data and the
associated true cluster prototypes. Note that the data-points, shown in the
right column, are actually 30-dimensional but are projected onto a plane
defined by true prototypes, with planar coordinates denoted p1 and p2, for
ease of viewing (except for the PCA case, where a projection into the
principal component space is used instead). In addition to the two well-
defined classes, there is low-level background noise present in the data set.
The following rows demonstrate the ability of Angular-Distance K-Means, PCA,
and the proposed method to recover the true clusters and centroids. In the
case of PCA, no such clusters are identified; however, the principal
components (learned features) can be compared to the true prototypes.

###  IV-B Application Study — PARS Data

The use of the clustering algorithm for performing feature extraction is
demonstrated here on an unstained, formalin-fixed paraffin-embedded (FFPE)
human breast tissue slide. The standard projection PARS image of the slide is
shown in Figure 3. This image was captured and provided by Benjamin R.
Ecclestone with gratitude from the authors. A boxed-in region indicates the
selection of TD signals that were used for feature learning. An input of $K=6$
desired clusters was used somewhat arbitrarily here. The task of selecting the
number of clusters, $K$, is not addressed in this paper, and in principle the
same criteria issues apply as in selecting $K$ in K-Means or dimensionality in
PCA, and is assumed to be known based on external information.

Figure 3: A standard scalar signal projection of PARS imagery of unstained
human breast tissue on a slide. The time-domain signals from the yellow boxed
region are used for feature learning. Image captured by Benjamin R.
Ecclestone.

The learned centroids are shown in Figure 1. A wide variety of signal shapes
is present, each centroid representing a unique tissue type. The extracted
feature amplitudes (in absolute value, thus ignoring the effects of polarity)
are combined as an RGB image in Figure 4, with the amplitude of three features
mapped into RGB space, thus Feature 1 maps to red, feature 4 maps to green,
and feature 5 maps to blue, further discussed in Section V.

Figure 4: Absolute values of three feature amplitudes, extracted from the time
domain signals underlying the imagery in Figure 3. The three features are
combined to produce a colour image: Feature 1 maps to red, Feature 4 maps to
green, Feature 5 maps to blue. Quite remarkable structures and tissue
differentiation are clearly visible in this image, relative to that of Figure
3.

##  V Discussion

The comparison between methods, shown in Figure 2, illustrates qualitatively
that the learned features of PCA (the principal components) and Angular-
Distance K-Means do not adequately match the ground truth. This can be
explained by considering the underlying objective of each method:

  * •

PCA seeks to learn a minimal basis (set of principal components) that
preserves maximal variation in the data, but makes no assumption about the
underlying basis nor the associated sparsity of its weights. While the
principal components could, in principal, be a linear combination of the true
prototypes, information of the true prototypes cannot directly be inferred.

  * •

Regular K-Means, based on a Euclidean distance in the native dimensional
space, fails to assert the appropriate distance metric, and so is unable to
accommodate variable signal amplitudes and would, in any event, most likely
create a separate class for low-amplitude noise signals.

  * •

Angular-Distance K-Means creates clusters such that minimal intra-cluster
variance and maximal inter-cluster distance are achieved, as is intended;
however, due to the bi-polar nature of the TD signals explored in this report,
Angular-Distance K-Means cannot group antipodal components of the same class
together. Furthermore, K-Means remains highly susceptible to the influence of
background noise since its centroids are not weighted by signal amplitude.

The proposed method offers an attractive, intuitive, amplitude-flexible and
infrequent-class-mixing alternative to PCA or K-Means, due to its definition
of distance, mixing weight sparsity, and strategy for computing centroids.

Although ground truth is not available for the PARS imagery, the applied use
of the proposed method yielded biologically meaningful, spatially grouped,
highly compelling results. The learned features shown in Figure 1 represent a
wide variety of signal shapes which correspond to specific tissue structures
present in the image. A further detailed study involving commentary from
histology experts would be necessary to validate the inferred features, and is
the subject of ongoing research.

##  VI Conclusion

The proposed method developed in this report is capable of learning features
from high-dimensional signals that relate to individual components of the
underlying data, in spite of signal amplitude variations, inversions, and
noise. When tested on a synthetic data set, the proposed method learned
features that closely match the ground truth prototypes, whereas the other
compared methods could not. Finally, the proposed method was applied to real
data from a PARS microscope, yielding learned features that showed
correspondence with tissue structures. The method shows significant promise
and would be far more broadly applicable to multi-dimensional / multi-modal
signals than those explored here.

## Acknowledgment

The authors would like to thank Benjamin R. Ecclestone, a PhD student at
PhotoMedicine Labs at the University of Waterloo, for collecting the PARS
image analyzed here.

## References

  * [1] B. Burbridge and E. Mah, _Undergraduate diagnostic imaging fundamentals_. University of Saskatchewan, 2017.
  * [2] L. V. Wang and H.-i. Wu, _Biomedical optics: principles and imaging_. John Wiley & Sons, 2012.
  * [3] P. L. Allan, G. M. Baxter, and M. J. Weston, _Clinical Ultrasound, 2-Volume Set E-Book: Expert Consult: Online and Print_. Elsevier Health Sciences, 2011.
  * [4] J. C. Hobbins, _Obstetric ultrasound: artistry in practice_. John Wiley & Sons, 2008.
  * [5] J. Laurenceau and M. Malergue, _the essentials in echocardiography_. Springer Science & Business Media, 2012, vol. 4.
  * [6] D. B. Foster, _Twelve-lead electrocardiography: Theory and interpretation_. Springer Science & Business Media, 2007.
  * [7] K. Wang, _Atlas of electrocardiography_. JP Medical Ltd, 2012.
  * [8] S. Chugh, _Textbook of clinical electrocardiography_. JAYPEE BROTHERS PUBLISHERS, 2014.
  * [9] A. A. Leis and M. P. Schenk, _Atlas of nerve conduction studies and electromyography_. Oxford University Press, 2013.
  * [10] G. Kamen and D. A. Gabriel, _Essentials of electromyography_. Human Kinetics Publishers, 2009.
  * [11] M. E. Tavel, “Clinical phonocardiography and external pulse recording,” in _Clinical phonocardiography and external pulse recording_ , 1972, pp. 322–322.
  * [12] A. Leatham, _Auscultation of the Heart and Phonocardiography_. Churchill London, 1970.
  * [13] T. Fuchs-Buder, _Neuromuscular monitoring_. Springer Science & Business Media, 2011.
  * [14] U. Haberland, P. Jansen, V. Blazek, and H. J. Schmitt, “Optical coherence tomography of scattering media using frequency-modulated continuous-wave techniques with tunable near-infrared laser,” in _Coherence Domain Optical Methods in Biomedical Science and Clinical Applications_ , vol. 2981\. International Society for Optics and Photonics, 1997, pp. 20–28.
  * [15] Y. Watanabe, F. Sajima, T. Itagaki, K. Watanabe, and Y. Shuto, “High-speed linear detection time domain optical coherence tomography with reflective grating-generated spatial reference delay,” _Applied optics_ , vol. 48, no. 18, pp. 3401–3406, 2009.
  * [16] P. Beard, “Biomedical photoacoustic imaging,” _Interface focus_ , vol. 1, no. 4, pp. 602–631, 2011.
  * [17] G. Li, K. I. Maslov, and L. V. Wang, “Reflection-mode multifocal optical-resolution photoacoustic microscopy,” _Journal of biomedical optics_ , vol. 18, no. 3, p. 030501, 2013.
  * [18] J. Yao and L. V. Wang, “Photoacoustic microscopy,” _Laser & photonics reviews_, vol. 7, no. 5, pp. 758–778, 2013.
  * [19] P. Hajireza, W. Shi, K. Bell, R. J. Paproski, and R. J. Zemp, “Non-interferometric photoacoustic remote sensing microscopy,” _Light: Science & Applications_, vol. 6, no. 6, pp. e16 278–e16 278, 2017.
  * [20] S. Abbasi, M. Le, B. Sonier, D. Dinakaran, G. Bigras, K. Bell, J. R. Mackey, and P. H. Reza, “All-optical reflection-mode microscopic histology of unstained human tissues,” _Scientific reports_ , vol. 9, no. 1, pp. 1–11, 2019.
  * [21] S. Abbasi, K. Bell, and P. Haji Reza, “Rapid high-resolution mosaic acquisition for photoacoustic remote sensing,” _Sensors_ , vol. 20, no. 4, p. 1027, 2020.
  * [22] B. R. Ecclestone, K. Bell, S. Abbasi, D. Dinakaran, F. K. van Landeghem, J. R. Mackey, P. Fieguth, and P. H. Reza, “Improving maximal safe brain tumor resection with photoacoustic remote sensing microscopy,” _Scientific Reports_ , vol. 10, no. 1, pp. 1–7, 2020.
  * [23] B. R. Ecclestone, K. Bell, S. Abbasi, D. Dinakaran, M. Taher, J. R. Mackey, and P. H. Reza, “Histopathology for mohs micrographic surgery with photoacoustic remote sensing microscopy,” _Biomedical Optics Express_ , vol. 12, no. 1, pp. 654–665, 2021.
  * [24] W. Bost, F. Stracke, M. Fournelle, and R. Lemor, “Developing a high-resolution photoacoustic microscopy platform,” in _4th European Conference of the International Federation for Medical and Biological Engineering_. Springer, 2009, pp. 448–451.
  * [25] G. Ku, K. I. Maslov, L. Li, and L. V. Wang, “Photoacoustic microscopy with 2-$\mu$m transverse resolution,” _Journal of biomedical optics_ , vol. 15, no. 2, p. 021302, 2010.
  * [26] B. Rao, L. Li, K. Maslov, and L. Wang, “Hybrid-scanning optical-resolution photoacoustic microscopy for in vivo vasculature imaging,” _Optics letters_ , vol. 35, no. 10, pp. 1521–1523, 2010.
  * [27] V. Cizek, “Discrete hilbert transform,” _IEEE Transactions on Audio and Electroacoustics_ , vol. 18, no. 4, pp. 340–343, 1970.
  * [28] M. J. Moore, E. Hysi, M. N. Fadhel, S. El-Rass, Y. Xiao, X.-Y. Wen, and M. C. Kolios, “Photoacoustic f-mode imaging for scale specific contrast in biological systems,” _Communications Physics_ , vol. 2, no. 1, pp. 1–10, 2019.
  * [29] P. Kedarisetti, N. J. Haven, B. S. Restall, M. T. Martell, and R. J. Zemp, “Label-free virtual h&e histopathology using f-mode ultraviolet photoacoustic remote sensing,” in _Photons Plus Ultrasound: Imaging and Sensing 2021_ , vol. 11642. International Society for Optics and Photonics, 2021, p. 116422S.
  * [30] P. Kedarisetti, B. S. Restall, N. J. Haven, M. T. Martell, B. D. Cikaluk, J. Deschenes, and R. J. Zemp, “F-mode ultraviolet photoacoustic remote sensing for label-free virtual h&e histopathology using a single excitation wavelength,” _Optics Letters_ , vol. 46, no. 15, pp. 3500–3503, 2021.
  * [31] K. Pearson, “Liii. on lines and planes of closest fit to systems of points in space,” _The London, Edinburgh, and Dublin philosophical magazine and journal of science_ , vol. 2, no. 11, pp. 559–572, 1901.
  * [32] H. Hotelling, “Analysis of a complex of statistical variables into principal components.” _Journal of educational psychology_ , vol. 24, no. 6, p. 417, 1933.
  * [33] R. Bro and A. K. Smilde, “Principal component analysis,” _Analytical methods_ , vol. 6, no. 9, pp. 2812–2831, 2014.
  * [34] J. Shlens, “A tutorial on principal component analysis,” _arXiv preprint arXiv:1404.1100_ , 2014.
  * [35] B. M. S. Hasan and A. M. Abdulazeez, “A review of principal component analysis algorithm for dimensionality reduction,” _Journal of Soft Computing and Data Mining_ , vol. 2, no. 1, pp. 20–30, 2021.
  * [36] J. MacQueen _et al._ , “Some methods for classification and analysis of multivariate observations,” in _Proceedings of the fifth Berkeley symposium on mathematical statistics and probability_ , vol. 1, no. 14. Oakland, CA, USA, 1967, pp. 281–297.
  * [37] H. Steinhaus _et al._ , “Sur la division des corps matériels en parties,” _Bull. Acad. Polon. Sci_ , vol. 1, no. 804, p. 801, 1956.
  * [38] J. A. Hartigan and M. A. Wong, “Algorithm as 136: A k-means clustering algorithm,” _Journal of the royal statistical society. series c (applied statistics)_ , vol. 28, no. 1, pp. 100–108, 1979.
  * [39] S. Lloyd, “Least squares quantization in pcm,” _IEEE transactions on information theory_ , vol. 28, no. 2, pp. 129–137, 1982.
  * [40] I. S. Dhillon and D. S. Modha, “Concept decompositions for large sparse text data using clustering,” _Machine learning_ , vol. 42, no. 1, pp. 143–175, 2001.
  * [41] V. Nguyen, “Gene clustering on the unit hypersphere with the spherical k-means algorithm: coping with extremely large number of local optima,” in _World Congress in Computer Science, Computer Engineering, and Applied Computing_. CSREA Press, 2008, pp. 226–233.
  * [42] K. Hornik, I. Feinerer, M. Kober, and C. Buchta, “Spherical k-means clustering,” _Journal of statistical software_ , vol. 50, pp. 1–22, 2012\.
  * [43] F. Zhang, _Matrix theory: basic results and techniques_. Springer Science & Business Media, 2011.
  * [44] G. Kirchgässner, J. Wolters, and U. Hassler, _Introduction to modern time series analysis_. Springer Science & Business Media, 2012.
  * [45] P. Fieguth, _Statistical image processing and multidimensional modeling_. Springer Science & Business Media, 2010.


# Fundamental decoherence from quantum spacetime

Michele Arzano<EMAIL_ADDRESS>Vittorio D’Esposito
<EMAIL_ADDRESS>Giulia Gubitosi<EMAIL_ADDRESS>
###### Abstract

We show that quantum properties of spacetime, encoded by noncommutativity at
the Planck scale, lead to a generalized time evolution of quantum systems in
which pure states can evolve into mixed states. Specifically, a decoherence
mechanism is obtained in the form of a Lindblad-like time evolution for the
density operator when the action of time translations generator is deformed by
the effects of spacetime noncommutativity. The decoherence time for the
evolution of a free particle is used to show that the Planck mass is the
maximum allowed mass for elementary quantum systems.

##  1 Introduction

The emergence of the classical macroscopic world from the microscopic quantum
realm is a long-standing open problem, still heavily debated in the physics
community and subject to theoretical and experimental research [1, 2]. Several
different mechanisms causing decoherence of quantum systems have been
considered. They are not mutually exclusive, and their relative relevance
might vary depending on the specific physical setup. The most studied and best
understood possibility relies on the interaction of quantum systems with an
environment [1, 2]. The resulting entanglement between the respective degrees
of freedom leads to the emergence of classical properties for the quantum
system. Growing theoretical evidence [3] indicates that gravity might
contribute to environmental decoherence, if one accounts for the entanglement
between the gravitational degrees of freedom (either classical or quantum) and
those of the quantum system [4, 5, 6, 7, 8, 9]. Gravity might also induce
decoherence via different mechanisms. In fact, an enticing possibility is that
classical or quantum gravity effects might cause departures from standard
quantum theory, as proposed in the pioneering works [10, 11]. This type of
decoherence is called fundamental, since it would affect the quantum system
independently of its environment. As opposed to environmental decoherence,
where information on quantum coherence is delocalized in the environment, in
the case of fundamental decoherence such information is lost, since there is
no environment to which it could have been transferred.

Fundamental decoherence opens up the possibility that quantum gravity might be
tested far away from the Planck scale, for example in nonrelativistic quantum
systems and in table-top experiments [12, 13, 14]. After almost a century of
intense theoretical research which did not lead to a solid understanding of
the interplay between the quantum realm and gravity, this might provide a
turning point.

The possibility that the interplay between quantum and gravitational effects
can generate decoherence of quantum systems emerged already in the earliest
investigations on quantum gravity. The original motivation was provided by
Hawking’s proposal [15] that the evaporation of a black hole evolves pure
states into mixed states. This is at the basis of the so-called black hole
information paradox, which is still nowadays at the center of a heated debate
aimed at establishing whether the evolution of the quantum states of a black
hole and the emitted radiation is unitary [16, 17, 18, 19, 20, 21, 22].
Further motivation comes from the need to explain the evolution of quantum
vacuum fluctuations generated in the primordial universe so that they turn
into the classical large-scale structures observed today. How this quantum-to-
classical transition can occur is one of the most pressing open problems in
cosmology and has been the subject of many studies [23, 24, 25, 26, 27, 28].
It is then clear that establishing the role of gravity in the generation of
decoherence would have far-fetching implications for a number of issues that
lie at the foundations of several areas of physics research.

Several quantum gravity-induced decoherence mechanisms proposed in the
literature relied on heuristic analyses. In particular, putative properties of
spacetime induced by quantum gravity effects were introduced in a rather ad-
hoc manner in the derivation of decoherence, based on general ideas about
gravity at the Planck scale, such as discretization [29], foaminess [8, 9],
stochasticity [11, 30, 31], fundamental uncertainties in length measurements
[32, 33].

In this work, we provide the first rigorous derivation of decoherence within a
full-fledged model of quantum spacetime, namely spacetime noncommutativity
[34, 35]111 ”Quantum spacetime” refers to a spacetime whose properties are
modified because of quantum-gravitational effects, see e.g. the review [36].
While in some models this might be seen as an abuse of notation, the case of
noncommutative spacetime is perhaps the one where the terminology is the most
accurate, since noncommuting spacetime coordinates can be described using the
theory of operators on a Hilbert space, see e.g. [37, 38].. Spacetime
noncommutativity was proposed already in the early days of quantum mechanics,
most notably by Heisenberg [39] and Snyder [40], as a means to introduce an
effective ultraviolet cutoff and control the divergences in quantum field
theory without breaking Lorentz symmetries. The idea was later revived in the
90’s, when it was realized that it provides a framework to describe the
fundamental limitations emerging when trying to localize an event with a
spatial accuracy comparable with the Planck length, due to the interplay of
quantum and gravitational effects [37, 41]. Over the past twenty years, the
relevance of spacetime noncommutativity for quantum gravity research has been
established on solid grounds: on the one hand it emerges as an effective
description of spacetime in some regimes of string theory [42, 43, 44] and
loop quantum gravity [45, 46, 47], and on the other hand it provides a source
of rich phenomenology [36, 48].

One of the most studied classes of noncommutative spacetime models is the so-
called $\kappa$-Minkowski spacetime [49], characterized by noncommutativity
between the time and spatial coordinates:

$\commutator{x^{0}}{x^{i}}=\frac{i}{\kappa}x^{i}\,,\quad\commutator{x^{i}}{x^{j}}=0\,.$
(1)

Here, $\kappa^{-1}$ is a length scale, usually identified with the Planck
length $\ell_{P}$ (unless otherwise stated, we use units such that
$c=\hbar=1$). In the following we will take $\kappa>0$. Notice that taking the
opposite sign for $\kappa$ amounts to considering a different physical model,
which would lead to different implications concerning decoherence.

For our purposes, the most relevant feature of (1) is the fact that its
relativistic symmetries are described by a quantum deformation of the Poincaré
symmetries, encoded by the $\kappa$-Poincaré Hopf algebra [50, 51]. In
particular, the time evolution operator turns out to have a deformed action on
the density operator and the ensuing nonstandard time evolution generates
decoherence. Ultimately, decoherence emerges because the time evolution of
quantum systems must not spoil the relativistic invariance of the
noncommutative spacetime. Therefore, the decoherence we derive within this
model is fundamental, in the sense described above: there is no actual
environment or interaction inducing decoherence; rather, this is due to the
properties of spacetime itself and as such no quantum system can avoid it.

The paper is organized as follows. In section 2 we introduce the novel
structures that are needed to describe quantum deformations of spacetime
symmetries. We discuss how these deformations emerge because of spacetime
noncommutativity and we present the deformed time evolution operator. In
section 3 we use the time evolution operator to define a Linblad-like equation
[52] describing the time evolution of the density operator of a generic
quantum system. We show that this time evolution generally implies an increase
of the linear entropy, signalling decoherence. Specializing to the case of a
free particle, we obtain the decoherence time for a quantum system in the
momentum basis. The decoherence rate is suppressed by the quantum deformation
scale $\kappa$ and is amplified by increasing values of momenta: the
efficiency of the decoherence process grows with the characteristic energy of
the quantum system. The quadratic momentum dependence of the decoherence time
allows us to obtain intrinsic fundamental constraints on the mass of
elementary quantum systems, which cannot exceed the quantum deformation scale
$\kappa$. This shows that fundamental decoherence puts an ultimate bound on
the scales at which quantum features of nature can be observed. Had the
momentum dependence been different, we would not have been able to derive such
absolute bound. This bound is thus a genuine implication of quantum spacetime
properties. Further theoretical and observational implications are discussed
in the outlook section.

##  2 Deformations of spacetime symmetries

In standard quantum mechanics, for a quantum system with symmetry under
translations we can define a basis of momentum eigenstates on the Hilbert
space of the system $\mathcal{H}$,

$P_{i}\ket{k}=k_{i}\ket{k}\,.$ (2)

For a free particle, these eigenstates can be represented as plane waves,
$\innerproduct{x}{k}=e^{ik_{\mu}x^{\mu}}$. This representation can be extended
to the dual space $\mathcal{H}^{*}$ spanned by bras:

$P_{i}\bra{k}=-k_{i}\bra{k}\,.$ (3)

The representation (3) can be written in terms of the antipode map $S(P_{i})$
connecting the left and right action of $P_{i}$ on dual states:

$P_{i}\bra{k}=-k_{i}\bra{k}=\bra{k}(-k_{i})\equiv\bra{k}S(P_{i})\,,$ (4)

where

$S(P_{i})=-P_{i}\,.$ (5)

Multi-particle states are given by tensor products of the Hilbert space
$\mathcal{H}$. The representation of $P_{i}$ on a two-particle state is given
by the familiar Leibniz rule, which can be written in terms of a coproduct map

$\Delta P_{i}=P_{i}\otimes\mathbbm{1}+\mathbbm{1}\otimes P_{i}\,,$ (6)

such that

$\displaystyle\Delta P_{i}\quantity(\ket{g}\otimes\ket{h})$ $\displaystyle=$
$\displaystyle\quantity(P_{i}\ket{g})\otimes\ket{h}+\ket{g}\otimes\quantity(P_{i}\ket{h})$
(7) $\displaystyle=$
$\displaystyle\quantity(g_{i}+h_{i})(\ket{g}\otimes\ket{h})\,.$

For a non-commutative space-time defined by commutators like (1) which close a
Lie algebra, plane waves are generalized to noncommutative ordered
exponentials $\mathrel{\mathop{\ordinarycolon}}\leavevmode\nobreak\
e^{ik_{\mu}x^{\mu}}\mathrel{\mathop{\ordinarycolon}}$ [53]. The parameters
appearing in these exponentials are coordinates of a non-abelian Lie group
rather than an ordinary vector space [54, 55]. Quantum states in the momentum
representation are then labelled by coordinates on the group $\ket{k(g)}$,
such that the action of translation generators is given by

$P_{i}\ket{k(g)}=k_{i}(g)\ket{k(g)}\,.$ (8)

The homomorphism property of coordinate functions tells us that momentum
eigenvalues $k_{i}(g)$ obey a deformed, non-abelian, composition law,

$k_{i}(g)\oplus k_{i}(h)\equiv k_{i}(gh)\neq k_{i}(h)\oplus k_{i}(g)\equiv
k_{i}(hg)\,,$ (9)

and this can be used to define the inverse group element $k_{i}(g^{-1})$, such
that

$k_{i}(g)\oplus k_{i}(g^{-1})=0\,.$ (10)

As a consequence, the antipode and coproduct maps defined above are deformed,
thus encoding a deformation of translational symmetries. For the analogue of
the dual representation (3)-(4) the antipode gives the coordinates of the
inverse momentum group element,

$P_{i}\bra{k(g)}=k_{i}(g^{-1})\bra{k(g)}=\bra{k(g)}\,S(P_{i})\,,$ (11)

while the coproduct allows us to establish the total momentum carried by a
two-particle state,

$\Delta P_{i}(\ket{g}\otimes\ket{h})=k_{i}(gh)(\ket{g}\otimes\ket{h})\,.$ (12)

For the specific model we are considering, in which spacetime noncommutativity
is determined by the commutators (1), the coproduct and antipodes for
translation generators read

$\displaystyle\Delta P_{0}$ $\displaystyle=$ $\displaystyle
P_{0}\otimes\Pi_{0}+\Pi_{0}^{-1}\otimes
P_{0}+\frac{1}{\kappa}P_{i}\Pi_{0}^{-1}\otimes P^{i}\,,$ $\displaystyle\Delta
P_{i}$ $\displaystyle=$ $\displaystyle
P_{i}\otimes\mathbbm{1}+\mathbbm{1}\otimes P_{i}\,,\;\;$ (13) $\displaystyle
S(P_{0})$ $\displaystyle=$ $\displaystyle-
P_{0}+\frac{1}{\kappa}\boldsymbol{P}^{2}\,\Pi_{0}^{-1}\,,\;\;S(P_{i})=-P_{i}\,\Pi_{0}^{-1},$

where

$\displaystyle\Pi_{0}$ $\displaystyle=$
$\displaystyle\frac{1}{\kappa}P_{0}+\sqrt{1-\frac{1}{\kappa^{2}}P^{\mu}P_{\mu}}\,,$
$\displaystyle\Pi_{0}^{-1}$ $\displaystyle=$
$\displaystyle\frac{\sqrt{1-\frac{1}{\kappa^{2}}P^{\mu}P_{\mu}}-\frac{1}{\kappa}P_{0}}{1-\frac{1}{\kappa^{2}}\boldsymbol{P}^{2}}\,,$
$\displaystyle P^{\mu}P_{\mu}$ $\displaystyle=$ $\displaystyle-
P_{0}^{2}+\boldsymbol{P}^{2}=-P_{0}^{2}+P_{i}P^{i}\,.$

This particular realization of the deformed generators of relativistic
translations is the translation sector of the so-called classical basis [56]
of the $\kappa$-Poincaré algebra. In such model only coproducts and antipodes
are deformed, while the commutators between the generators of space and time
translation, boosts and rotations, i.e. the Poincaré Lie algebra, remain
undeformed.

Since the symmetry group relevant for nonrelativistic quantum mechanics is the
Galilei group rather than the Poincaré group, we consider a nonrelativistic
limit of the $\kappa$-Poincaré algebra, namely, the $\kappa$-Galilei algebra.
This limit is obtained by means of a standard Hopf-algebra contraction
procedure [57, 58]. The speed of light $c$ is used to rescale both the
relevant generators, namely, space translations $P_{i}$ and boosts $N_{i}$,
and the quantum deformation parameter,

${P_{i}}\mapsto c^{-1}{P_{i}}\,,\;\;{N_{i}}\mapsto
c^{-1}{N_{i}}\,,\;\;\kappa\mapsto c^{-2}\kappa\,.$ (15)

After taking the limit $c\rightarrow\infty$, the commutation relations of the
Poincaré Lie algebra give the standard Galilei algebra, while the following
nontrivial structures in the coalgebra sector are obtained:

$\begin{array}[]{ll}\Delta P_{0}&=P_{0}\otimes\mathbbm{1}+\mathbbm{1}\otimes
P_{0}+\frac{1}{\kappa}P_{i}\otimes P^{i}\,,\\\
S(P_{0})&=-P_{0}+\frac{1}{\kappa}\boldsymbol{P}^{2}\,.\end{array}$ (16)

In order to study the evolution of quantum systems, we use the familiar
$G\mapsto-i\,G$ procedure to map the abstract elements $G$ of the
$\kappa$-Galilei algebra into Hermitian operators that can be represented on
the algebra of operators of a quantum system. We thus obtain the following
coalgebra relations:

$\Delta P_{0}=P_{0}\otimes\mathbbm{1}+\mathbbm{1}\otimes
P_{0}-\frac{i}{\kappa}P_{i}\otimes P^{i}\,,\quad
S(P_{0})=-P_{0}-\frac{i}{\kappa}\boldsymbol{P}^{2}\,.$ (17)

Notice how under the same $G\mapsto-i\,G$ transformation the nontrivial
coproducts and antipodes for the translation generators of the
$\kappa$-Poincaré algebra become

$\begin{array}[]{ll}\Delta P_{0}&=P_{0}\otimes\mathbbm{1}+\mathbbm{1}\otimes
P_{0}-\frac{i}{\kappa}P_{i}\otimes P^{i}\,,\\\
S(P_{0})&=-P_{0}-\frac{i}{\kappa}\boldsymbol{P}^{2}\,,\\\ \Delta
P_{i}&=P_{i}\otimes\mathbbm{1}+\mathbbm{1}\otimes
P_{i}-\frac{i}{\kappa}P_{i}\otimes P_{0}\,,\\\
S(P_{i})&=-P_{i}-\frac{i}{\kappa}P_{i}P_{0}\,,\end{array}$ (18)

at first order in $\kappa^{-1}$. In particular, we notice that the coalgebra
properties of the time translation generator $P_{0}$ are the same as those
found for the time generator of the $\kappa$-Galilei algebra (17). As we will
see in the following section, this correspondence guarantees that the same
decoherence produced by the $\kappa$-deformation of the Galilei algebra is
also produced by the $\kappa$-deformation of the Poincaré algebra to the first
order in $\kappa^{-1}$.

##  3 Generalized quantum evolution from deformed symmetries

The deformation of relativistic symmetries described in the previous section
affects the evolution of quantum systems and induces decoherence. This can be
shown by considering the action of the generators of translations on the
algebra of operators of a quantum system $\mathcal{A}_{\mathcal{H}}$, with
$\mathcal{H}$ being the Hilbert space of the quantum system itself.

Usually such action is given in terms of the standard commutator
$\commutator{\boldsymbol{\cdot}}{\boldsymbol{\cdot}}$, namely, via the adjoint
action of the algebra of symmetry generators on $\mathcal{A}_{\mathcal{H}}$.
When the Lie algebra of symmetry generators is generalized to a nontrivial
Hopf algebra, the deformed coproducts and antipodes lead to a generalization
of this action given by the quantum adjoint action [59]. This is defined by
[60]

$\text{ad}_{\,\boldsymbol{\cdot}}\,\boldsymbol{\cdot}\vcentcolon\mathcal{R}_{G}\times\mathcal{A}_{\mathcal{H}}\rightarrow\mathcal{A}_{\mathcal{H}}\,,\quad\text{ad}_{G}\,O\vcentcolon=\left(id\otimes
S\right)\Delta G\diamond O\,,$ (19)

where $\mathcal{R}_{G}$ is the vector space spanned by the representatives of
the generators of the symmetry algebra, $G\in\mathcal{R}_{G}$ and the
$\diamond$ operator is defined by

$(a\otimes b)\diamond O\vcentcolon=a\,O\,b\,.$ (20)

This generalization of the adjoint action reduces to the standard one when the
coproduct and antipode are the standard ones like e.g. in (5) and (6). In
fact, given $A\in\mathcal{A}_{\mathcal{H}}$ and $G$ with trivial coproduct
$\Delta G=G\otimes\mathbbm{1}+\mathbbm{1}\otimes G$ and antipode $S(G)=-G$,
one finds

$\text{ad}_{G}\,A=(G\otimes\mathbbm{1}-\mathbbm{1}\otimes G)\diamond
A=\,\commutator{G}{A}\,.$ (21)

In ordinary quantum mechanics, the evolution of the density operator $\rho$ is
given by the (standard) adjoint action (21) of the Hamiltonian, generator of
time translations, on the density operator itself:

$i\,\partial_{t}\rho=\text{ad}_{H}\,\rho=\,\commutator{H}{\rho}\,.$ (22)

This is the standard Liouville–von Neumann equation.

The generalised adjoint action (19) can be used to define the evolution
equation for the density operator of a quantum system when the symmetry
generators are those of the $\kappa$-Galilei Hopf algebra described in the
previous section. Assuming that the time evolution is given by the time
translation generator $P_{0}$, we define

$i\,\partial_{t}\rho\vcentcolon=\frac{1}{2}\quantity{\text{ad}_{P_{0}}(\rho)-\quantity[\text{ad}_{P_{0}}(\rho)]^{\dagger}}\,.$
(23)

This reproduces the standard evolution equation (22) for ordinary time
translations with standard antipode and coproduct. Notice that we considered
the combination of $\text{ad}_{P_{0}}(\rho)$ and
$\quantity[\text{ad}_{P_{0}}(\rho)]^{\dagger}$ in (23) so that the evolution
preserves the Hermiticity of $\rho$.

The evolution equation (23) encodes an equation of Lindblad type [52, 61]:

$\partial_{t}\rho=-i\,\commutator{H}{\rho}-\frac{1}{2}g^{mn}\left(Q_{m}Q_{n}\,\rho+\rho\,Q_{m}Q_{n}-2\,Q_{m}\,\rho\,Q_{n}\right)\,,$
(24)

where $Q_{n}$ form a basis of Hermitian operators. Indeed, after some algebra
one can show that

$\partial_{t}\rho=-i\,\commutator{P_{0}}{\rho}-\frac{1}{2\kappa}\left(\boldsymbol{P}^{2}\rho+\rho\,\boldsymbol{P}^{2}-2\,P_{i}\,\rho
P^{i}\,\right)\,,$ (25)

which reproduces (24) for $g^{mn}=\kappa^{-1}\delta^{mn}$, $H=P_{0}$ and
$Q_{m}=P_{m}$. The fact that the evolution equation (25) takes the form (24),
with a real and positive-definite matrix $g^{mn}$, guarantees that the
operator $\rho$ is a good density operator at any time, namely, (25) preserves
the positivity and the Hermiticity222The link between noncommutative
deformations of relativistic symmetries and generalized time evolution for
quantum systems was noticed by one of the authors a few years ago [60].
However, in [60] the time evolution is not of the Lindblad type and
conservation of the positivity of $\rho$ is not guaranteed. of $\rho$.

Equation (25) describes the evolution of the density operator of a quantum
system living on a noncommutative spacetime and whose symmetries are those of
a quantum deformation of the Galilei algebra: the $\kappa$-Galilei algebra.
Notice that with the same definition of the time evolution given in (23),
using the deformed coalgebra structures in (18), the same equation is obtained
to the first order in $\kappa^{-1}$ when symmetries are given by the
$\kappa$-deformation of the Poincaré algebra rather than the Galilei algebra.
Notice also that the key ingredient to obtain the decoherence described by eq.
(25) is a deformation of time translation symmetries. However, similar
decoherence mechanisms might arise in other models of spacetime
noncommutativity if time evolution is governed by a Hamiltonian with a
deformed coproduct and antipode.

By studying the evolution of the linear entropy

$S(t)=1-\Tr{\rho^{2}}\,,$ (26)

we can show that the density operator converges asymptotically to the
maximally mixed state proportional to the identity, with all the off-diagonal
terms being washed out by the evolution.

The time derivative of (26) gives

$\displaystyle\derivative{t}S$ $\displaystyle=$
$\displaystyle-2\Tr{\rho\,\partial_{t}\rho}=$ (27) $\displaystyle=$
$\displaystyle\frac{1}{2\kappa}\Tr{\rho\left(\boldsymbol{P}^{2}\rho+\rho\boldsymbol{P}^{2}-2\,P_{i}\rho\,P^{i}\right)\Big{]}}\,,$

where we used $\Tr{\rho\commutator{P_{0}}{\rho}}=0$. This result can be
rewritten as

$\derivative{t}S=\frac{1}{\kappa}\sum_{i}\Tr{O_{i}O_{i}^{\dagger}}\geq 0\,,$
(28)

where $O_{i}\vcentcolon=\commutator{\rho}{P_{i}}$. Therefore, we see that (25)
indeed leads to an increase of the entropy (or a decrease of the purity) of
the system.

In order to give a more detailed characterization of the nonunitary evolution,
we focus on a free nonrelativistic particle, and use $P_{0}$ as time evolution
operator:

$\displaystyle\derivative{t}\rho_{pq}=\Big{[}-i\big{(}E(p)-E(q)\big{)}-\frac{1}{2\kappa}(\boldsymbol{p}-\boldsymbol{q})^{2}\Big{]}\rho_{pq}(t)\,,$

where
$\rho_{pq}\vcentcolon=\matrixelement{E(p),\boldsymbol{p}}{\rho}{E(q),\boldsymbol{q}}$.
The solution of this equation gives the time evolution of the density operator

$\rho_{pq}(t)=\rho_{pq}(0)\exp\left[-it\big{(}E(p)-E(q)\big{)}-\frac{t}{2\kappa}(\boldsymbol{p}-\boldsymbol{q})^{2}\right]\,.$
(30)

The diagonal elements are conserved, while the off-diagonal elements are
characterized by an exponential damping factor, which realises a localization
in energy of the system. This indicates a decoherence process in the
superselected [62] basis of momenta.

For this density operator the linear entropy reads

$S(t)=1-\int\differential[3]{p}\differential[3]{q}\absolutevalue{\rho_{pq}(0)}^{2}\,e^{-\frac{t}{\kappa}(\boldsymbol{p}-\boldsymbol{q})^{2}}\,.$
(31)

Expanding asymptotically around $t\rightarrow\infty$ we find

$S(t)\sim
1-\quantity(\frac{\pi\,\kappa}{t})^{\frac{3}{2}}\int\differential[3]{p}{\rho_{pp}(0)}^{2}\,,$
(32)

This quantity converges to $1$ as $t\rightarrow\infty$, making the density
operator a maximally mixed state.

The decoherence time of this process is given by (30):

$\tau_{D}=\frac{2\,\kappa}{(\boldsymbol{p}-\boldsymbol{q})^{2}}\,.$ (33)

We can rewrite the time evolution of the density operator (30) in terms of the
decoherence rate $\Gamma=\tau_{D}^{-1}$ as

$\rho_{pq}(t)=\rho_{pq}(0)e^{-i\,t\,\Delta E-\Gamma\,t}\,.$ (34)

The decoherence rate is suppressed by the quantum deformation scale $\kappa$
(which, as we mentioned, is taken to be of the order of the Planck energy
scale, $\kappa\sim E_{P}$) and is amplified by increasing values of
$\boldsymbol{p}-\boldsymbol{q}$, in such a way that the decoherence process
becomes increasingly more efficient as the energies involved approach the
Planck scale.

We provide a comparison with other mechanisms of gravitational decoherence
proposed in the literature in table 1. To allow for such a comparison we
reinstate units of $\hbar$, set $\kappa=E_{P}$ and consider parallel momenta.
Notice that this provides an upper bound on the actual decoherence time, since
$\tau_{D}\leq\tau_{D}\quantity(\boldsymbol{p}\parallel\boldsymbol{q})$. Then
we can write the decoherence time as

$\tau_{D}\quantity(\boldsymbol{p}\parallel\boldsymbol{q})=\frac{\hbar\,E_{P}}{E_{0}\quantity(\delta\sqrt{E})^{2}}$
(35)

where $E=\boldsymbol{p}^{2}/2m$ and $E_{0}=m$.

Physical source of decoherence | Decoherence time |
---|---|---
Stochastic perturbations with noise temperature $\Theta$ [30] | $\frac{\hbar\,}{k_{B}\Theta}\frac{E_{P}^{2}}{E\,\delta E}$ |
Perturbation around flat spacetime [31] | $\frac{\hbar\,E_{P}}{(\delta E)^{2}}$ |
Thermal background of gravitons at temperature $T$ [7] | $\frac{\hbar}{k_{B}T}\frac{E_{P}^{2}}{(\delta E)^{2}}$ |
Fluctuating minimal length [32] | $\frac{\hbar\,E_{P}^{5}}{E_{0}^{2}\quantity(\delta E^{2})^{2}}$ |
Deformation of symmetries (current model) | $\frac{\hbar\,E_{P}}{E_{0}\quantity(\delta\sqrt{E})^{2}}$ |
Table 1: Comparison of the behaviour of the decoherence times characterizing
different gravitational decoherence scenarios, compared to the model studied
in this work (last line).

The decoherence time (33) can be used to derive fundamental constraints on the
characteristic scales of quantum systems. To do so, we observe that if a
system is in a state with a given energy spread $\delta E$, the state is
characterized by a lifetime [63]

$\tau_{c}\gtrsim\frac{1}{\delta E}\,.$ (36)

Decoherence cannot be observed if the decoherence time is longer than the
lifetime of the state of the system. Thus, for decoherence to be observable,
the decoherence time and the lifetime must satisfy the condition
$\tau_{D}\leq\tau_{c}$. Conversely, if we do not observe decoherence in a
given quantum system prepared in a state with energy spread $\delta E$ we have
the opposite bound, $\tau_{D}\geq\tau_{c}\gtrsim\quantity(\delta E)^{-1}$,
namely,

$\frac{\quantity(\delta\,\boldsymbol{p})^{2}}{\delta E}\lesssim 2\,\kappa\,.$
(37)

For quantum states whose wave function is localized in spatial momentum,
$\frac{\absolutevalue{\expectationvalue{\boldsymbol{p}}}}{\absolutevalue{\delta\,\boldsymbol{p}}}\gg
1$ (from which
$\frac{\delta\,\boldsymbol{p}^{2}}{\quantity(\delta\,\boldsymbol{p})^{2}}\sim
1$), we have from (37) that

$m\lesssim\kappa\,.$ (38)

This bound sets a limit on the mass of quantum systems. Specifically, it is
not possible to create states highly delocalized in the position for quantum
systems with mass greater than the Planck scale $\kappa$. This can be regarded
as a more rigorous derivation of an expected feature of quantum-gravitational
physics, namely, that the Planck mass constitutes a limit on the mass of
quantum mechanical systems, as it is shown from heuristic arguments for
instance in [33]. Notice that had the momentum dependence in (33) been
different, e.g. linear, we would not have been able to derive such absolute
bound. This bound is a genuine implication of quantum spacetime properties.

Before closing this section let us remark that the limit (38) should be taken
seriously only for elementary quantum systems. For composite systems it has
been suggested that the effects of symmetry deformation might be suppressed by
some power of the number of constituents [64, 65, 66].

##  4 Outlook

We showed that a Lindblad equation arises naturally as the evolution equation
of quantum systems living in a noncommutative spacetime, where the symmetry
generators are deformed and described by nontrivial Hopf algebras. This leads
to a fundamental decoherence mechanism by which the density operator of a
quantum system asymptotically approaches a maximally mixed state. While the
decoherence mechanism we derived is due to a modified quantum evolution and
not to the presence of an environment, still the evolution equation we found
is described by a Lindlad equation, which is usually associated to
environmental decoherence. It would be interesting to understand what type of
environment could lead to such a Lindblad equation. This might also provide
insights into the physical origin of the time reversal asymmetry emerging in
our model, see eq. (30), which is usually an imprint of environmental
decoherence.

Our analysis shows that there exists a consistent framework modelling putative
quantum spacetime effects in which pure quantum states can evolve into mixed
states. This fact is particularly suggestive when seen from the perspective of
the black hole information paradox that we mentioned in the introduction.
Indeed the possibility that the evolution of quantum fields on a black hole
background might be not given by ordinary quantum evolution has been dismissed
over the years as problematic and lacking links with fundamental theories of
quantum gravity [67]. A natural development on this side would be to check
whether the nonunitary evolution we derived can be recast in the form of a
qubit toy model of black hole evaporation [68] thus providing the first fully
worked out model of nonunitary black hole evolution derived from first
principles.

The fundamental decoherence effect we uncovered might also be instrumental in
explaining the quantum-to-classical transition of primordial cosmological
perturbations. In fact, the Fourier modes of such perturbations are expected
to have Planckian energy at sufficiently early times. At these scales, the
decoherence time (33) is of the order of the Planck time, thus making the
decoherence process very effective. In this scenario, one does not need to
invoke any of the additional decoherence mechanisms that have been considered
in the past, such as the interaction of the perturbations with external
fields.

Besides the possible implications for the foundational issues just discussed,
the emergence of fundamental decoherence might open up several windows to
experimentally access the quantum gravity regime. Notice that the decoherence
process discussed in this work is not expected to replace the experimentally
well-established environmental decoherence [62, 69], and in fact it provides a
negligible contribution in typical experimental setups devised to study this.
However, it can become relevant and observable in specific regimes, as
discussed below.

One example of such experimental opportunities concerns tabletop experiments
with optomechanical cavities [14, 32]. In these setups, two cavities are
realized by means of four mirrors, one of which is movable. Inside the
cavities, two atoms or molecules in a harmonic potential are prepared in an
entangled state and are hit by an external laser source (realizing a Raman
single photon source). The excitations of these sources lead to single photon
excitations and the radiation so obtained in the cavities allows to study the
vibrational modes of the oscillators. In the presence of an environment,
entanglement between the two oscillators is degraded with a rate
$\Lambda_{\text{heat}}=\frac{k_{B}T}{\hbar Q}$ from mechanical heating at
temperature $T$; the presence of additional gravitational decoherence
mechanisms would increase such a rate to
$\Lambda_{\text{heat}}+\Lambda_{\text{grav}}$, where in our case
$\Lambda_{\text{grav}}=\frac{\quantity(\delta\boldsymbol{p})^{2}}{2\hbar
M_{P}}$. Adapting the analysis presented in [32] to the peculiarities of the
fundamental decoherence mechanism we uncovered, we find that experimental
parameters that will be achievable in the nearby future, like temperatures
$T\sim 10\,\text{mK}$ and quality factors $Q\sim 10^{6}$ [70, 71], will allow
to reach Planck-scale sensitivity on the quantum deformation scale,
$\kappa\sim 10^{19}\,\text{GeV}$, for quantum systems with mass $M\sim
10^{-28}\,\text{Kg}$.

Another physical framework that can allow to test the relativistic version of
our model333As we showed, the relativistic version, based on a quantum
deformation of the Poincaré algebra rather than the Galilean algebra, produces
the same quantum evolution to the first order in $\kappa^{-1}$. involves
modifications of the oscillation rates for cosmological neutrinos. Generic
decoherence mechanisms induce modifications on such rates [72, 73, 74] that
are driven by the exponential damping factor $e^{-\Gamma\,t}$. Such factor
starts giving a significant contribution to the oscillation probability
roughly when $e^{-\Gamma\,t}\sim e^{-1}$ [72]. In our case
$\Gamma\sim\kappa^{-1}(\delta p)^{2}\sim\kappa^{-1}(\delta m)^{2}$, see eq.
(34) and the discussion around it. Taking $\kappa\sim 10^{19}\,\text{GeV}$ and
$(\delta m)^{2}\sim 10^{-3}\,\text{eV}^{2}$ [74], we find $\Gamma\sim
10^{-40}\,\text{GeV}$. Therefore the $e^{-\Gamma\,t}$ factor starts producing
relevant effects on neutrino oscillation when they propagate over cosmological
times $t\sim 10^{15}\,s\sim 10^{8}\,\text{yr}$.

Such opportunities to look for experimental signatures of the interplay
between quantum and gravitational effects are not to be missed given their
potential significant impact in the quest for a theory of quantum gravity.

## Acknowledgements

We acknowledge support from the INFN Iniziativa Specifica QUAGRAP. This work
contributes to the European Union COST Action CA18108 Quantum gravity
phenomenology in the multi-messenger approach. This research was carried out
in the frame of Programme STAR Plus, financially supported by UniNA and
Compagnia di San Paolo.

## References

  * [1] M. Schlosshauer, “Decoherence, the Measurement Problem, and Interpretations of Quantum Mechanics,” Rev. Mod. Phys., vol. 76, pp. 1267–1305, 2004\.
  * [2] D. Giulini, C. Kiefer, E. Joos, J. Kupsch, I. O. Stamatescu, and H. D. Zeh, Decoherence and the appearance of a classical world in quantum theory.  Berlin: Springer, 2003.
  * [3] A. Bassi, A. Großardt, and H. Ulbricht, “Gravitational Decoherence,” Class. Quant. Grav., vol. 34, no. 19, p. 193002, 2017.
  * [4] C. Kiefer, “Continuous Measurement of Minisuperspace Variables by Higher Multipoles,” Class. Quant. Grav., vol. 4, p. 1369, 1987.
  * [5] J. R. Ellis, S. Mohanty, and D. V. Nanopoulos, “Quantum Gravity and the Collapse of the Wave Function,” Phys. Lett. B, vol. 221, pp. 113–119, 1989.
  * [6] E. Joos and H. D. Zeh, “The emergence of classical properties through interaction with the environment,” Zeitschrift für Physik B Condensed Matter, vol. 59, no. 2, pp. 223–243, 1985.
  * [7] M. P. Blencowe, “Effective Field Theory Approach to Gravitationally Induced Decoherence,” Phys. Rev. Lett., vol. 111, no. 2, p. 021302, 2013.
  * [8] L. J. Garay, “Quantum evolution in space-time foam,” Int. J. Mod. Phys. A, vol. 14, pp. 4079–4120, 1999.
  * [9] N. E. Mavromatos, “CPT violation and decoherence in quantum gravity,” Lect. Notes Phys., vol. 669, pp. 245–320, 2005.
  * [10] L. Diósi, “Gravitation and quantum-mechanical localization of macro-objects,” Physics Letters A, vol. 105, no. 4, pp. 199–202, 1984\.
  * [11] I. C. Percival, “Quantum space-time fluctuations and primary state diffusion,” Proc. Roy. Soc. Lond. A, vol. 451, p. 503, 1995.
  * [12] G. Amelino-Camelia, C. Lammerzahl, A. Macias, and H. Muller, “The Search for quantum gravity signals,” AIP Conf. Proc., vol. 758, no. 1, pp. 30–80, 2005.
  * [13] D. Carney, P. C. E. Stamp, and J. M. Taylor, “Tabletop experiments for quantum gravity: a user’s manual,” Class. Quant. Grav., vol. 36, no. 3, p. 034001, 2019.
  * [14] C. Pfister, J. Kaniewski, M. Tomamichel, A. Mantri, R. Schmucker, N. McMahon, G. Milburn, and S. Wehner, “A universal test for gravitational decoherence,” Nature Communications, vol. 7, no. 1, p. 13022, 2016.
  * [15] S. W. Hawking, “Breakdown of Predictability in Gravitational Collapse,” Phys. Rev. D, vol. 14, pp. 2460–2473, 1976.
  * [16] T. Banks, L. Susskind, and M. E. Peskin, “Difficulties for the Evolution of Pure States Into Mixed States,” Nucl. Phys. B, vol. 244, pp. 125–134, 1984.
  * [17] L. Susskind, L. Thorlacius, and J. Uglum, “The Stretched horizon and black hole complementarity,” Phys. Rev. D, vol. 48, pp. 3743–3761, 1993.
  * [18] Y. Kiem, H. L. Verlinde, and E. P. Verlinde, “Black hole horizons and complementarity,” Phys. Rev. D, vol. 52, pp. 7053–7065, 1995.
  * [19] C. Kiefer, “Hawking radiation from decoherence,” Class. Quant. Grav., vol. 18, p. L151, 2001.
  * [20] S. W. Hawking, “Information loss in black holes,” Phys. Rev. D, vol. 72, p. 084013, 2005.
  * [21] S. L. Braunstein, S. Pirandola, and K. Życzkowski, “Better Late than Never: Information Retrieval from Black Holes,” Phys. Rev. Lett., vol. 110, no. 10, p. 101301, 2013.
  * [22] W. G. Unruh and R. M. Wald, “Information Loss,” Rept. Prog. Phys., vol. 80, no. 9, p. 092002, 2017.
  * [23] R. H. Brandenberger, V. F. Mukhanov, and T. Prokopec, “Entropy of a classical stochastic field and cosmological perturbations,” Phys. Rev. Lett., vol. 69, pp. 3606–3609, 1992.
  * [24] A. Perez, H. Sahlmann, and D. Sudarsky, “On the quantum origin of the seeds of cosmic structure,” Class. Quant. Grav., vol. 23, pp. 2317–2354, 2006\.
  * [25] C. Kiefer and D. Polarski, “Why do cosmological perturbations look classical to us?,” Adv. Sci. Lett., vol. 2, pp. 164–173, 2009.
  * [26] D. Sudarsky, “Shortcomings in the Understanding of Why Cosmological Perturbations Look Classical,” Int. J. Mod. Phys. D, vol. 20, pp. 509–552, 2011.
  * [27] G. Gubitosi and J. Magueijo, “The phenomenology of squeezing and its status in non-inflationary theories,” JCAP, vol. 11, p. 014, 2017.
  * [28] J. Martin and V. Vennin, “Observational constraints on quantum decoherence during inflation,” JCAP, vol. 05, p. 063, 2018.
  * [29] R. Gambini, R. A. Porto, and J. Pullin, “Realistic clocks, universal decoherence and the black hole information paradox,” Phys. Rev. Lett., vol. 93, p. 240401, 2004.
  * [30] C. Anastopoulos and B. L. Hu, “A Master Equation for Gravitational Decoherence: Probing the Textures of Spacetime,” Class. Quant. Grav., vol. 30, p. 165007, 2013.
  * [31] H. P. Breuer, E. Goklu, and C. Lammerzahl, “Metric fluctuations and decoherence,” Class. Quant. Grav., vol. 26, p. 105012, 2009.
  * [32] L. Petruzziello and F. Illuminati, “Quantum gravitational decoherence from fluctuating minimal length and deformation parameter at the Planck scale,” Nature Commun., vol. 12, no. 1, p. 4449, 2021.
  * [33] Y. J. Ng and H. Van Dam, “Limit to space-time measurement,” Mod. Phys. Lett. A, vol. 9, pp. 335–340, 1994.
  * [34] A. Connes, Noncommutative Geometry.  San Diego: Academic Press, 1994.
  * [35] R. J. Szabo, “Quantum field theory on noncommutative spaces,” Phys. Rept., vol. 378, pp. 207–299, 2003.
  * [36] G. Amelino-Camelia, “Quantum-Spacetime Phenomenology,” Living Rev. Rel., vol. 16, p. 5, 2013.
  * [37] S. Doplicher, K. Fredenhagen, and J. E. Roberts, “Space-time quantization induced by classical gravity,” Phys. Lett. B, vol. 331, pp. 39–44, 1994\.
  * [38] F. Lizzi, M. Manfredonia, F. Mercati, and T. Poulain, “Localization and Reference Frames in $\kappa$-Minkowski Spacetime,” Phys. Rev. D, vol. 99, no. 8, p. 085003, 2019.
  * [39] W. Pauli, Letter from Heisenberg to Peierls in: Scientific Correspondence with Bohr, Einstein, Heisenberg a.o. Volume II: 1930–1939.  Springer Berlin, Heidelberg, 1985.
  * [40] H. S. Snyder, “Quantized space-time,” Phys. Rev., vol. 71, pp. 38–41, 1947.
  * [41] D. V. Ahluwalia, “Quantum measurements, gravitation, and locality,” Phys. Lett. B, vol. 339, pp. 301–303, 1994.
  * [42] G. Veneziano, “A Stringy Nature Needs Just Two Constants,” EPL, vol. 2, p. 199, 1986.
  * [43] D. J. Gross and P. F. Mende, “String Theory Beyond the Planck Scale,” Nucl. Phys. B, vol. 303, pp. 407–454, 1988.
  * [44] D. Amati, M. Ciafaloni, and G. Veneziano, “Can Space-Time Be Probed Below the String Size?,” Phys. Lett. B, vol. 216, pp. 41–47, 1989.
  * [45] G. Amelino-Camelia, L. Smolin, and A. Starodubtsev, “Quantum symmetry, the cosmological constant and Planck scale phenomenology,” Class. Quant. Grav., vol. 21, pp. 3095–3110, 2004.
  * [46] L. Freidel and E. R. Livine, “3D Quantum Gravity and Effective Noncommutative Quantum Field Theory,” Phys. Rev. Lett., vol. 96, p. 221301, 2006.
  * [47] G. Amelino-Camelia, M. M. da Silva, M. Ronco, L. Cesarini, and O. M. Lecian, “Spacetime-noncommutativity regime of Loop Quantum Gravity,” Phys. Rev. D, vol. 95, no. 2, p. 024028, 2017.
  * [48] A. Addazi et al., “Quantum gravity phenomenology at the dawn of the multi-messenger era—A review,” Prog. Part. Nucl. Phys., vol. 125, p. 103948, 2022.
  * [49] S. Majid and H. Ruegg, “Bicrossproduct structure of kappa Poincare group and noncommutative geometry,” Phys. Lett. B, vol. 334, pp. 348–354, 1994\.
  * [50] J. Lukierski, H. Ruegg, A. Nowicki, and V. N. Tolstoi, “Q deformation of Poincare algebra,” Phys. Lett. B, vol. 264, pp. 331–338, 1991.
  * [51] J. Lukierski and H. Ruegg, “Quantum kappa Poincare in any dimension,” Phys. Lett. B, vol. 329, pp. 189–194, 1994.
  * [52] G. Lindblad, “On the Generators of Quantum Dynamical Semigroups,” Commun. Math. Phys., vol. 48, p. 119, 1976.
  * [53] G. Amelino-Camelia and S. Majid, “Waves on noncommutative space-time and gamma-ray bursts,” Int. J. Mod. Phys. A, vol. 15, pp. 4301–4324, 2000\.
  * [54] J. Kowalski-Glikman, “Living in Curved Momentum Space,” Int. J. Mod. Phys. A, vol. 28, p. 1330014, 2013.
  * [55] M. Arzano and J. Kowalski-Glikman, “A group theoretic description of the $\kappa$-Poincaré Hopf algebra,” Phys. Lett. B, vol. 835, p. 137535, 2022.
  * [56] A. Borowiec and A. Pachol, “Classical basis for kappa-Poincare algebra and doubly special relativity theories,” J. Phys. A, vol. 43, p. 045203, 2010\.
  * [57] A. Ballesteros, G. Gubitosi, I. Gutierrez-Sagredo, and F. J. Herranz, “The $\kappa$-Newtonian and $\kappa$-Carrollian algebras and their noncommutative spacetimes,” Phys. Lett. B, vol. 805, p. 135461, 2020.
  * [58] A. Ballesteros, G. Gubitosi, and F. Mercati, “Interplay between Spacetime Curvature, Speed of Light and Quantum Deformations of Relativistic Symmetries,” Symmetry, vol. 13, no. 11, p. 2099, 2021.
  * [59] H. Ruegg and V. N. Tolstoi, “Representation theory of quantized Poincare algebra: Tensor operators and their applications to one particle systems,” Lett. Math. Phys., vol. 32, pp. 85–102, 1994.
  * [60] M. Arzano, “Purity is not eternal in theories with Planck-scale deformed symmetries,” Phys. Rev. D, vol. 90, no. 2, p. 024016, 2014.
  * [61] V. Gorini, A. Kossakowski, and E. C. G. Sudarshan, “Completely Positive Dynamical Semigroups of N Level Systems,” J. Math. Phys., vol. 17, p. 821, 1976.
  * [62] M. Schlosshauer, “Quantum Decoherence,” Phys. Rept., vol. 831, pp. 1–57, 2019.
  * [63] J. Hilgevoord, “The uncertainty principle for energy and time,” American Journal of Physics, vol. 64, no. 12, pp. 1451–1456, 1996.
  * [64] S. Hossenfelder, “The Soccer-Ball Problem,” SIGMA, vol. 10, p. 074, 2014\.
  * [65] G. Amelino-Camelia, L. Freidel, J. Kowalski-Glikman, and L. Smolin, “Relative locality and the soccer ball problem,” Phys. Rev. D, vol. 84, p. 087702, 2011.
  * [66] G. Amelino-Camelia, “Planck-scale soccer-ball problem: a case of mistaken identity,” Entropy, vol. 19, no. 8, p. 400, 2017.
  * [67] M. Srednicki, “Is purity eternal?,” Nucl. Phys. B, vol. 410, pp. 143–154, 1993.
  * [68] S. G. Avery, “Qubit Models of Black Hole Evaporation,” JHEP, vol. 01, p. 176, 2013.
  * [69] M. Schlosshauer, “Decoherence: From Interpretation to Experiment,” Fundam. Theor. Phys., vol. 204, pp. 45–64, 2022.
  * [70] I. Pikovski, M. R. Vanner, M. Aspelmeyer, M. S. Kim, and C. Brukner, “Probing Planck-scale physics with quantum optics,” Nature Phys., vol. 8, pp. 393–397, 2012.
  * [71] J. D. Teufel, T. Donner, D. Li, J. W. Harlow, M. S. Allman, K. Cicak, A. J. Sirois, J. D. Whittaker, K. W. Lehnert, and R. W. Simmonds, “Sideband cooling of micromechanical motion to the quantum ground state,” Nature, vol. 475, no. 7356, pp. 359–363, 2011.
  * [72] J. Christian, “Testing gravity-driven collapse of the wavefunction via cosmogenic neutrinos,” Phys. Rev. Lett., vol. 95, p. 160403, 2005.
  * [73] L. A. Anchordoqui, H. Goldberg, M. C. Gonzalez-Garcia, F. Halzen, D. Hooper, S. Sarkar, and T. J. Weiler, “Probing Planck scale physics with IceCube,” Phys. Rev. D, vol. 72, p. 065019, 2005.
  * [74] J. a. A. B. Coelho and W. A. Mann, “Decoherence, matter effect, and neutrino hierarchy signature in long baseline experiments,” Phys. Rev. D, vol. 96, no. 9, p. 093009, 2017.