* Wang et al. (2018) Wenshan Wang, Su Yang, Zhiyuan He, Minjie Wang, Jiulong Zhang, and Weishan Zhang. 2018\.  Urban Perception of Commercial Activeness from Satellite Images and Streetscapes. In _Companion Proceedings of the The Web Conference 2018_ (Lyon, France) _(WWW ’18)_. International World Wide Web Conferences Steering Committee, Republic and Canton of Geneva, CHE, 647–654.  https://doi.org/10.1145/3184558.3186581
  * Ward et al. (1998) Peter T Ward, John K McCreery, Larry P Ritzman, and Deven Sharma. 1998.  Competitive priorities in operations management.  _Decision Sciences_ 29, 4 (1998), 1035–1046.
  * Wei et al. (2019) Peter Wei, Haocong Shi, Jiaying Yang, Jingyi Qian, Yinan Ji, and Xiaofan Jiang. 2019\.  City-scale vehicle tracking and traffic flow estimation using low frame-rate traffic cameras. In _Adjunct Proceedings of the 2019 ACM International Joint Conference on Pervasive and Ubiquitous Computing and Proceedings of the 2019 ACM International Symposium on Wearable Computers_. 602–610.
  * Weld et al. (2019) Galen Weld, Esther Jang, Anthony Li, Aileen Zeng, Kurtis Heimerl, and Jon E Froehlich. 2019\.  Deep learning for automatically detecting sidewalk accessibility problems using streetscape imagery. In _The 21st International ACM SIGACCESS Conference on Computers and Accessibility_. 196–209.
  * Wexler et al. (2020) James Wexler, Mahima Pushkarna, Tolga Bolukbasi, Martin Wattenberg, Fernanda Viégas, and Jimbo Wilson. 2020.  The What-If Tool: Interactive Probing of Machine Learning Models.  _IEEE Transactions on Visualization and Computer Graphics_ 26, 1 (2020), 56–65.  https://doi.org/10.1109/TVCG.2019.2934619
  * White and Feiner (2009) Sean White and Steven Feiner. 2009.  SiteLens: Situated Visualization Techniques for Urban Site Visits. In _Proceedings of the SIGCHI Conference on Human Factors in Computing Systems_ (Boston, MA, USA) _(CHI ’09)_. Association for Computing Machinery, New York, NY, USA, 1117–1120.  https://doi.org/10.1145/1518701.1518871
  * Wu et al. (2021) Tong Wu, Nikolas Martelaro, Simon Stent, Jorge Ortiz, and Wendy Ju. 2021.  Learning When Agents Can Talk to Drivers Using the INAGT Dataset and Multisensor Fusion.  _Proceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies_ 5, 3 (2021), 1–28.
  * Xie et al. (2020) Qian Xie, Dawei Li, Zhenghao Yu, Jun Zhou, and Jun Wang. 2020.  Detecting Trees in Street Images via Deep Learning With Attention Module.  _IEEE Transactions on Instrumentation and Measurement_ 69, 8 (2020), 5395–5406.  https://doi.org/10.1109/TIM.2019.2958580
  * Yates et al. (2021) Roy D Yates, Yin Sun, D Richard Brown, Sanjit K Kaul, Eytan Modiano, and Sennur Ulukus. 2021\.  Age of information: An introduction and survey.  _IEEE Journal on Selected Areas in Communications_ 39, 5 (2021), 1183–1210.
  * Ye et al. (2019a) Nanqi Ye, Bowen Wang, Michihiro Kita, Ming Xie, and Wenyue Cai. 2019a.  Urban Commerce Distribution Analysis Based on Street View and Deep Learning.  _IEEE Access_ 7 (2019), 162841–162849.  https://doi.org/10.1109/ACCESS.2019.2951294
  * Ye et al. (2019b) Yu Ye, Wei Zeng, Qiaomu Shen, Xiaohu Zhang, and Yi Lu. 2019b.  The visual quality of streets: A human-centred continuous measurement based on machine learning algorithms and street view images.  _Environment and Planning B: Urban Analytics and City Science_ 46, 8 (2019), 1439–1457.  https://doi.org/10.1177/2399808319828734 arXiv:https://doi.org/10.1177/2399808319828734
  * Yoong (2018) Janine Yoong. 2018\.  Vermont opens up 5 years of road imagery for improving transportation services.  https://blog.mapillary.com/update/2018/03/28/vermont-opens-up-5-years-of-road-imagery.html
  * Zeng et al. (2018) Liyue Zeng, Jun Lu, Wuyan Li, and Yongcai Li. 2018\.  A fast approach for large-scale Sky View Factor estimation using street view images.  _Building and Environment_ 135 (2018), 74–84.
  * Zeng et al. (2014) Wei Zeng, Chi-Wing Fu, Stefan Müller Arisona, Alexander Erath, and Huamin Qu. 2014.  Visualizing Mobility of Public Transportation System.  _IEEE Transactions on Visualization and Computer Graphics_ 20, 12 (2014), 1833–1842.  https://doi.org/10.1109/TVCG.2014.2346893
  * Zhang et al. (2019) Fan Zhang, Lun Wu, Di Zhu, and Yu Liu. 2019\.  Social sensing from street-level imagery: A case study in learning spatio-temporal urban mobility patterns.  _ISPRS Journal of Photogrammetry and Remote Sensing_ 153 (2019), 48–58.
  * Zhang et al. (2020) Yihong Zhang, Panote Siriaraya, Yukiko Kawai, and Adam Jatowt. 2020.  Automatic latent street type discovery from web open data.  _Information Systems_ 92 (2020), 101536.
  * Zhang et al. (2018) Yihong Zhang, Panote Siriaraya, Yuanyuan Wang, Shoko Wakamiya, Yukiko Kawai, and Adam Jatowt. 2018.  Walking down a different path: route recommendation based on visual and facility based diversity. In _Companion Proceedings of the The Web Conference 2018_. 171–174.
  * Ziems et al. (2023) Caleb Ziems, William Held, Omar Shaikh, Jiaao Chen, Zhehao Zhang, and Diyi Yang. 2023\.  Can Large Language Models Transform Computational Social Science?  _arXiv preprint arXiv:2305.03514_ (2023).


# Trees of Dot Products in Thin Subsets of $\mathbb{R}^{d}$

Arian Nadjimzadah

###### Abstract.

A. Iosevich and K. Taylor showed that compact subsets of $\mathbb{R}^{d}$ with
Hausdorff dimension greater than $(d+1)/2$ contain trees with gaps in an open
interval. Under the same dimensional threshold, we prove the analogous result
where distance is replaced by the dot product. We additionally show that the
gaps of embedded trees of dot products are prevalent in a set of positive
Lebesgue measure, and for Ahlfors-David regular sets, the number of trees with
given gaps agrees with the regular value theorem.

##  1\. Introduction

The theme of this work can be summarized in the following question: how large
must a subset of $\mathbb{R}^{d}$ be for it to contain certain geometric
structures? Though in our work we focus on dot products, the the study of such
questions was first motivated by distances.

If $E$ is a set in $\mathbb{R}^{d}$, define its distance set by
$\Delta(E)=\\{|x-y|:x,y\in E\\}$. When $E\subset\mathbb{R}^{2}$ is finite, the
study of the relationship between $|\Delta(E)|$ and $|E|$ is the celebrated
Erdős distance problem. The conjecture is $|\Delta(E)|\geq|E|/\log|E|$, which
was met up to a square root with Guth and Katz’s bound of
$|\Delta(E)|\geq|E|/\sqrt{\log|E|}$ [9]. One could ask what happens when
$E\subset\mathbb{R}^{d}$ is infinite. A first notion of size that one learns
in real analysis is the Lebesgue measure, which we will denote from here
onward by $|\cdot|$. The following question could be posed.

######  Question 1.

If $|E|>0$, how large must $\Delta(E)$ be?

A theorem of Steinhaus says that when $|E|>0$, $E-E$ contains an open set
around 0, so in particular $\Delta(E)$ contains an open set. This is as large
of a set in $\mathbb{R}^{d}$ that we could ever hope for, so we need a more
refined notion of the size of infinite sets. Another notion of size that one
might encounter is the Minkowski dimension.

######  Definition 1 (Minkowski Dimension).

Let $N(E,\epsilon)$ be the number of balls of radius $\epsilon>0$ required to
cover the set $E$. Then the lower Minkowski dimension of $E$ is given by

$\underline{\dim_{\mathcal{M}}}(E)=\liminf_{\epsilon\to 0}\frac{\log
N(E,\epsilon)}{\log(1/\epsilon)},$

and the upper Minkowski dimension is

$\overline{\dim_{\mathcal{M}}}(E)=\limsup_{\epsilon\to 0}\frac{\log
N(E,\epsilon)}{\log(1/\epsilon)}.$

We can pose the following possibly more refined question.

######  Question 2.

How large does $\underline{\dim_{\mathcal{M}}}(E)$ have to be for
$|\Delta(E)|>0$?

Unfortunately this question is still uninteresting. There exist sets which
have “full” Minkowski dimension, in the sense that the lower Minkowski
dimension is as large as it can be, yet their distance sets have measure 0. In
fact, they can be merely countable! Consider

$E=\mathbb{Q}^{d}\cap[0,1]^{d}.$

By the density of the rationals, it takes (up to a constant) $1/\epsilon^{d}$
balls of radius $\epsilon$ to cover $E$, regardless of how small we take
$\epsilon$. Thus $\underline{\dim_{\mathcal{M}}(E)}=d$, the largest possible
dimension in $\mathbb{R}^{d}$. However $\Delta(E)$ is the image of a countable
set, so it is itself countable.

The deficiency in Minkowski dimension is that our covers can consist only of
balls of _the same size_. However this does make computations with Minkowski
dimension easier. The Hausdorff dimension does not have this issue, but it is
often more difficult to compute.

######  Definition 2 (Hausdorff Dimension).

Let

$\mathcal{H}_{\delta}^{s}(E)=\inf\sum_{j}r_{j}^{s},$

where the infimum is taken over all countable coverings of $E$ by balls
$\\{B(x_{i},r_{i})\\}$ such that $r_{i}<\delta$. Define the $s$-dimensional
Hausdorff measure $\mathcal{H}^{s}$ by

$\mathcal{H}^{s}(E)=\lim_{\delta\to 0}\mathcal{H}_{\delta}^{s}(E).$

The _Hausdorff Dimension_ of $E$, $\dim_{\mathcal{H}}(E)$, is the unique
number $s_{0}$ such that $H^{s}(E)=\infty$ if $s<s_{0}$ and $H^{s}(E)=0$ if
$s>s_{0}$.

We can now ask the following interesting question.

######  Question 3.

How large must $\dim_{\mathcal{H}}(E)$ be to ensure that $|\Delta(E)|>0$?

Kenneth Falconer constructed compact sets $E\subset\mathbb{R}^{d}$ with
$\dim_{\mathcal{H}}(E)<d/2$ and $|\Delta(E)|=0$. He also showed the first
nontrivial threshold $\dim_{\mathcal{H}}(E)>(d+1)/2]$, which ensures
$|\Delta(E)|>0$ [5]. The correct threshold thus lies in $[d/2,(d+1)/2)$ and
the conjecture is $d/2$. The cutting edge is still far from the conjectured
threshold. Below is a summary of progress to date.

$\begin{cases}\frac{5}{4},&d=2,\text{\cite[cite]{[\@@bibref{}{guth2020falconer}{}{}]}}\\\
\frac{9}{5},&d=3,\text{\cite[cite]{[\@@bibref{}{du2021weighted}{}{}]}}\\\
\frac{d}{2}+\frac{1}{4}&d\geq 4,d\text{
even},\text{\cite[cite]{[\@@bibref{}{du2021improved}{}{}]}}\\\
\frac{d}{2}+\frac{1}{4}+\frac{1}{4(d-1)}&d\geq 4,d\text{
odd},\text{\cite[cite]{[\@@bibref{}{du2019sharp}{}{}]}}\end{cases}.$

Steps have been taken in understanding more complex distance configurations in
$E$. Let $G$ be a graph and define the _$G$ -distance configuration_ of $E$ by

$\Delta_{G}(E)=\\{(|x_{i}-x_{j}|)_{(i,j)\in\mathcal{E}(G)}:(x_{1},\ldots,x_{|\mathcal{V}(G)|})\in
E^{|\mathcal{V}(G)|}\\}.$

Here $\mathcal{V}(G)$ and $\mathcal{E}(G)$ are the vertices and edges of $G$
respectively. A. Iosevich and K. Taylor [11] showed that for a tree $T$,
$\Delta_{T}(E)$ contains an entire interval when $E\subset\mathbb{R}^{d}$ has
$\dim_{\mathcal{H}}(E)>(d+1)/2$. At the other extreme, A. Greenleaf, A.
Iosevich, B. Liu and E. Palsson [6] showed using a group theoretic approach
that if $G$ is the complete graph on $k+1$ vertices (the $k$-simplex), then
$|\Delta_{G}(E)|>0$ as long as $\dim_{\mathcal{H}}(E)>(dk+1)/(k+1)$.

Distance is certainly not the only quantity that can be associated with two
points, and progress has been made in generalizing the Falconer problem in
this direction too. A. Greenleaf, A. Iosevich, and K. Taylor [7] considered
more general $\Phi$-configurations for a class of
$\Phi:\mathbb{R}^{d}\times\mathbb{R}^{d}\to\mathbb{R}^{k}$. They showed that
the associated configuration set $\Delta_{\Phi}(E)=\\{\Phi(x,y):x,y\in E\\}$
has nonempty interior under certain lower bound assumptions on
$\dim_{\mathcal{H}}(E)$ and regularity of the family of generalized Radon
transforms associated with $\Phi$. To avoid some of the Fourier integral
operator theory needed to handle a general class of $\Phi$ and because of the
nice geometric interpretation, we specialize to dot product in
$\mathbb{R}^{d}$, i.e.

$\Phi(x,y)=x\cdot y=x^{1}y^{1}+\cdots x^{d}y^{d}.$

Define $\Lambda(E)=\\{x\cdot y:x,y\in E\\}$. The lower bounds on Hausdorff
dimension for dot products and similar configurations as in [7] are far less
developed than for distances. The best bound so far to ensure that
$|\Lambda(E)|>0$ is $\dim_{\mathcal{H}}(E)>(d+1)/2$. Compare this with the
table above for distances.

In this work we make progress on understanding $T$-dot-product configurations,
for $T$ a tree with some $k$ edges. Define

$\Lambda_{T}(E)=\\{(x_{i}\cdot x_{j})_{(i,j)\in
E(T)}:(x_{1},\ldots,x_{k+1})\in E^{k+1}\\}.$

Before arriving at our results, we need the following machinery. It is well
known that if $E\subset\mathbb{R}^{d}$ has $\dim_{\mathcal{H}}(E)>\alpha$,
there is a number $s\in(\alpha,\dim_{\mathcal{H}}(E))$ and finite Borel
measure supported on $E$ such that

$\mu(B(x,r))\lesssim r^{s},$

for each $x\in\mathbb{R}^{d}$ and $r>0$. We call such a $\mu$ a _Frostman
measure with exponent_ $s$. In light of this, we have the following results.

######  Theorem 1.

Let $T$ be a tree with $k$ edges and $E\subset\mathbb{R}^{d}$ compact with
$\dim_{\mathcal{H}}(E)>(d+1)/2$. Then for every Frostman measure with exponent
$s>(d+1)/2$ supported on $E$, there is a constant $C>0$ independent of
$\epsilon$ such that

(1) $\mu^{k+1}(\\{(x_{1},\ldots,x_{k+1})\in E^{k+1}:t^{ij}-\epsilon<x_{i}\cdot
x_{j}<t^{ij}+\epsilon,(i,j)\in\mathcal{E}(T)\\})<C\epsilon^{k},$

for every collection $\\{t^{ij}\\}$ and $\epsilon>0$.

In the proof of Theorem 1, we follow a scheme developed by A. Iosevich et. al.
[10] to bootstrap a Sobolev operator bound to a $L^{2}(\mu)\to L^{2}(\mu)$
bound. This gives us a mechanism to ‘rip’ leaves from a tree until nothing is
left. We remark that in the case of chain configurations

$\\{(x_{1}\cdot x_{2},x_{2}\cdot x_{3},\ldots,x_{k}\cdot
x_{k+1}):(x_{1},\ldots,x_{k+1})\in E^{k}\\},$

Theorem 1 is a special case of work done by A. Iosevich, K. Taylor, and I.
Uriarte-Tuero [12].

We would also like to find a lower bound for a quantity like (1). The idea
will be to embed $T$ in a _symmetric tree cover_ $\sigma(T)$ which can be
‘folded’ down to a single edge, at which point we can apply a result in [7] to
the single edge. We define $\sigma(T)$ in Section 4.

######  Theorem 2.

Let $T$ be a tree with $k$ edges and $E\subset\mathbb{R}^{d}$ compact with
$\dim_{\mathcal{H}}(E)>(d+1)/2$. For every Frostman measure with exponent
$s>(d+1)/2$ supported on $E$, there is a constant $c>0$ independent of
$\epsilon$ and open interval $I$ such that for each $t\in I$ and $\epsilon>0$,

$\mu^{k+1}(\\{(x_{1},\ldots,x_{k+1})\in E^{k+1}:t-\epsilon<x_{i}\cdot
x_{j}<t+\epsilon,(i,j)\in\mathcal{E}(\sigma(T))\\})>c\epsilon^{k}.$

From Theorem 1 we can deduce that any tree $T$ is embedded in $E$ with _many_
different edge-wise dot products. We mean this in the following sense.

######  Corollary 1.

Let $E\subset\mathbb{R}^{d}$ be compact with $\dim_{\mathcal{H}}(E)>(d+1)/2$.
Then $|\Lambda_{T}(E)|>0$.

It is also interesting to pinpoint which embeddings of a graph are contained
in $E$ and how many such embeddings there are. For the distance variant of
this question see [11]. We define the set of embeddings of $T$ in $E$ with
dot-product vector $t=(t^{ij})$ as

$T_{t}(E)=\\{(x_{1},\ldots,x_{k+1})\in E^{k+1}:x_{i}\cdot
x_{j}=t^{ij},(i,j)\in\mathcal{E}(T)\\}.$

When $t$ is a scalar, we take all the $t^{ij}=t$ in (1). We can use Theorem 2
to show that there are embeddings with equal edge value.

######  Corollary 2.

Let $E\subset\mathbb{R}^{d}$ be compact with $\dim_{\mathcal{H}}(E)>(d+1)/2$.
Then there is an open interval $I$ such that for each $t\in I$, $T_{t}(E)$ is
nonempty.

Using Theorem 1, we can show that when $E$ is Ahlfors-David regular, there
cannot be too many embeddings of any given type $t=(t^{ij})$. Before getting
to the corollary, we define Ahlfors-David regular.

######  Definition 3.

A set $E\subset\mathbb{R}^{d}$ is Ahlfors-David $s$-regular if it is closed
and if there exists a Borel measure $\mu$ supported on $E$ and a constant $C$
such that

$C^{-1}r^{s}\leq\mu(B(x,r))\leq Cr^{s},$

for all $x\in E$, $0<r\leq\operatorname{diam}(E)$, $r<\infty$.

Note that when working on compact sets $E$, such measures $\mu$ are finite. We
prove the following.

######  Corollary 3.

Let $E\subset\mathbb{R}^{d}$ be compact Ahlfors-David $s$-regular, for some
$s>(d+1)/2$. Then for any $t=(t^{ij})$,

$\overline{\dim_{\mathcal{M}}}(T_{t}(E))\leq(k+1)s-k.$

As we explained above, Minkowski dimension is a weaker notion than Hausdorff
dimension when working with lower bounds. However for upper bounds, Minkowski
dimension is the stronger statement. In summary

$\dim_{\mathcal{H}}(A)\leq\underline{\dim_{\mathcal{M}}(A)}\leq\overline{\dim_{\mathcal{M}}(A)}.$

Corollary 3 should not be too surprising. Say we were working on
$\mathbb{R}^{d}$ instead of $E$. Then we have $k$ equations $x_{i}\cdot
x_{j}=t^{ij}$ and $k+1$ variables $x_{1},\ldots,x_{k+1}$. So the regular value
theorem tells us that $T_{t}(E)$ has dimension $1$. In our case $E$ has
dimension $s$, so one can think of $T_{t}(E)$ as $s(k+1)$ dimensions of
freedom cut by $k$ equations, giving $(k+1)s-k$ remaining dimensions.

##  2\. Initial Reductions

Let $E\subset\mathbb{R}^{d}$ have $\dim_{\mathcal{H}}(E)>(d+1)/2$. Then there
is a Frostman measure $\mu$ with exponent $s$ supported on $E$, for some
$s\in((d+1)/2,\dim_{\mathcal{H}}(E))$.

We can reduce the problem to when $E\subset[c,1]^{d}$ for a fixed constant
$c$. To see this, cut $\mathbb{R}^{d}$ into dyadic annuli $\\{2^{j}\leq|x|\leq
2^{j+1}\\}$. $\mu$ is positive on at least one of these, and by rescaling we
can assume it is $\\{1/2\leq|x|\leq 1\\}$. If we cover $\\{1/2\leq|x|\leq
1\\}$ with balls of radius $1/100$, $\mu$ is again positive on at least one of
these. Notice that for $\theta\in\operatorname{SO}(2)$,
$(x\theta)\cdot(y\theta)=x\cdot y$. Thus rotating the measure $\mu$ does not
affect the quantity in Theorem 1 or 2, so we can assume this ball is contained
in $[c,1]^{d}$ for a fixed constant $c$. Then we simply restrict $\mu$ to this
ball and renormalize.

##  3\. Proof of Theorem 1 and Corollaries 1 and 3

###  3.1. Proof of Theorem 1

We define a quantity $\mathcal{V}_{T,t}$ which is approximately the quantity
in Theorem 1. Let $\rho$ be a smooth bump function on $\mathbb{R}$ supported
around 0 and set
$\rho^{\epsilon}(\cdot)=\epsilon^{-1}\rho(\epsilon^{-1}\cdot)$. Then define

$\mathcal{V}^{\epsilon}_{T,t}(\mu)=\int\cdots\int\left(\prod_{(i,j)\in\mathcal{E}(T)}\rho^{\epsilon}(x_{i}\cdot
x_{j}-t^{ij})\right)d\mu(x_{1})\cdots d\mu(x_{k+1}).$

The idea is to rip a leaf edge from $T$ one at a time until the tree is empty.
One needs a corresponding mechanism that operators on
$\mathcal{V}_{T,t}^{\epsilon}(\mu)$ executing this plan, which is what we
develop below. This is in the same spirit as M. Bennet, A. Iosevich, and K.
Taylor’s work on chain configurations [1]. More concretely, we need to show
that $\mathcal{V}_{T,t}^{\epsilon}(\mu)\leq C$ independently of $\epsilon$ and
$t$. We recast this problem in terms of operators for which we have nice
results. Define $\mathcal{R}_{t}^{\epsilon}$ to be the operator with kernel
$\rho^{\epsilon}(x\cdot y-t)$, that is

$\mathcal{R}^{\epsilon}_{t}f(x)=\int f(y)\rho^{\epsilon}(x\cdot y-t)dy.$

We also define

$\mathcal{R}^{\epsilon}_{t}(f\mu)(x)=\int f(y)\rho^{\epsilon}(x\cdot
y-t)d\mu(y).$ 111This operator is known as the _Radon Transform_. See Section
5.1 for more details or [15] for an in-depth review.

Then we can cast $\mathcal{V}^{\epsilon}_{T,t}(\mu)$ in a way conducive to
‘ripping off’ edges.

######  Definition 4.

For $T$ a tree with a single vertex, define $f_{T}^{\epsilon}=1$. Let $T$ be a
tree with $k\geq 1$ edges and say $y$ is a leaf with edge $(x,y)$. Say $(x,y)$
has corresponding dot product $t^{\prime}$. Remove the leaf edge from $T$ to
obtain a subtree $T^{\prime}$. Define

$f_{T}^{\epsilon}=\mathcal{R}_{t}^{\epsilon}(f_{T^{\prime}}^{\epsilon}\mu).$

One can think of $f_{T}^{\epsilon}(x)$ as $T$ pinned at $x$. Then integrating
over the pinned point gives the entirety of
$\mathcal{V}^{\epsilon}_{T,t}(\mu)$. That is

$\mathcal{V}^{\epsilon}_{T,t}(\mu)=\int f_{T}^{\epsilon}(x)d\mu(x).$

By Cauchy-Schwarz and as $\mu$ is a probability measure,

$\mathcal{V}^{\epsilon}_{T,t}(\mu)=\norm{f_{T}^{\epsilon}}_{L^{1}(\mu)}\leq\norm{f_{T}^{\epsilon}}_{L^{2}(\mu)}.$

We use the following operator norm to run the induction.

######  Theorem 3.

If $\mu$ is a Frostman measure with exponent $s>(d+1)/2$ and with support as
was established in Section 2, $\mathcal{R}_{t}^{\epsilon}$ is a bounded linear
operator $L^{2}(\mu)\mapsto L^{2}(\mu)$ with

$\|\mathcal{R}_{t}^{\epsilon}(f\mu)\rVert_{L^{2}(\mu)}\lesssim\norm{f}_{L^{2}(\mu)}$

independently of $\epsilon>0$ and for $t\approx 1$.

The proof is left to Section 5.1. By our initial reduction $\mu$ has support
in $[c,1]^{d}$, so $x\cdot y\approx 1$ on $\operatorname{supp}\mu$. In light
of Definition 4,
$f_{T}^{\epsilon}=\mathcal{R}_{t^{\prime}}^{\epsilon}(f_{T^{\prime}}^{\epsilon})$.
By Theorem 3 and the inductive hypothesis,

$\displaystyle\|f_{T}^{\epsilon}\rVert_{L^{2}(\mu)}$
$\displaystyle=\|\mathcal{R}_{t^{\prime}}^{\epsilon}(f_{T^{\prime}}^{\epsilon})\rVert_{L^{2}(\mu)}$
$\displaystyle\lesssim\|f_{T^{\prime}}^{\epsilon}\rVert_{L^{2}(\mu)}$
$\displaystyle\lesssim 1$

independently of $\epsilon>0$ and $t=(t^{ij})$. ∎

###  3.2. Proof of Corollary 1

Consider any cover of $\Lambda_{T}(E)$ by products of intervals

$\Lambda_{T}(E)\subset\bigcup_{\ell}\prod_{(i,j)\in\mathcal{E}(T)}(t_{\ell}^{ij}-\epsilon_{\ell},t_{\ell}^{ij}+\epsilon_{\ell}).$

We have

$\displaystyle E^{k+1}$
$\displaystyle=\bigcup_{t\in\Lambda_{T}(E)}\\{(x_{1},\ldots,x_{k+1})\in
E^{k+1}:x_{i}\cdot x_{j}=t^{ij},(i,j)\in\mathcal{E}(T)\\}$
$\displaystyle\subset\bigcup_{\ell}\\{(x_{1},\ldots,x_{k+1})\in
E^{k+1}:t_{\ell}^{ij}-\epsilon_{\ell}<x_{i}\cdot
x_{j}<t_{\ell}^{ij}+\epsilon_{\ell},(i,j)\in\mathcal{E}(T)\\},$

so by Theorem 1,

$\displaystyle 1$ $\displaystyle=\mu^{k+1}(E^{k+1})$
$\displaystyle\leq\sum_{\ell}\mu^{k+1}(\\{(x_{1},\ldots,x_{k+1})\in
E^{k+1}:t_{\ell}^{ij}-\epsilon_{\ell}<x_{i}\cdot
x_{j}<t_{\ell}^{ij}+\epsilon_{\ell},(i,j\in\mathcal{E}(T))\\})$
$\displaystyle<\sum_{\ell}C\epsilon_{\ell}.$

Thus $\sum_{\ell}\epsilon_{\ell}>1/C$. This holds for any choice of covering
so $|\Lambda_{T}(E)|\geq 1/C>0$. ∎

###  3.3. Proof of Corollary 3

In Definition 1, we can replace $N(A,\epsilon)$ with $P(A,\epsilon)$. Here
$P(A,\epsilon)$ is the packing number, the greatest number of disjoint
$\epsilon$-balls with centers in $A$. This follows from the inequality

$N(A,2\epsilon)\leq P(A,\epsilon)\leq N(A,\epsilon/2),$

which one can find in a wonderful book by P. Mattila [13]. Consider such a
packing $\\{B(x_{i},\epsilon)\\}$ of $T_{t}(E)$ of size
$P(T_{t}(E),\epsilon)$. Since the centers of the balls $B(x_{i},\epsilon)$ are
in $T_{t}(E)$,

$\bigcup_{i}B(x_{i},\epsilon)\subset(T_{t}(E))^{\epsilon}.$ 222$A^{\epsilon}$
is the $\epsilon$-neighborhood of $A$ defined as
$A^{\epsilon}=\\{x\in\mathbb{R}^{d}:\exists y\in A,|x-y|<\epsilon\\}$.

For any $(x_{1},\ldots,x_{k+1})\in E^{k+1}\cap(T_{t}(E))^{\epsilon}$, there
are $x_{1}^{\prime},\ldots,x_{k+1}^{\prime}\in E$ such that
$x_{i}^{\prime}\cdot x_{j}^{\prime}=t$ for $(i,j)\in E(T)$ and
$|x_{i}-x_{i}^{\prime}|<\epsilon$. Thus

$\displaystyle|x_{i}\cdot x_{j}-t|$
$\displaystyle\leq|x_{i}||x_{j}-x_{j}^{\prime}|+|x_{j}^{\prime}||x_{i}-x_{i}^{\prime}|$
$\displaystyle\leq 2\epsilon,$

giving

$E^{k+1}\cap(T_{t}(E))^{\epsilon}\subset\\{(x_{1},\ldots,x_{k+1})\in
E^{k+1}:t^{ij}-2\epsilon<x_{i}\cdot
x_{j}<t^{ij}+2\epsilon,(i,j)\in\mathcal{E}(T)\\}.$

We can conclude with Theorem 1 that

$\displaystyle\sum_{i}\mu^{k+1}(B(x_{i},\epsilon))$
$\displaystyle=\mu^{k+1}\left(\bigcup_{i}B(x_{i},\epsilon)\right)$
$\displaystyle\leq\mu^{k+1}(E^{k+1}\cap(T_{t}(E))^{\epsilon})$
$\displaystyle\leq\mu^{k+1}(\\{(x_{1},\ldots,x_{k+1})\in
E^{k+1}:t^{ij}-2\epsilon<x_{i}\cdot
x_{j}<t^{ij}+2\epsilon,(i,j)\in\mathcal{E}(T)\\})$
$\displaystyle<C\epsilon^{k}.$

Since $\mu(B(x,r))\geq C^{\prime-1}r^{s}$, we get $\mu^{k+1}(B(x,r))\geq
C^{\prime-1}r^{(k+1)s}$. We conclude from the above calculation that

$C^{\prime-1}\epsilon^{(k+1)s}P(T_{t}(E),\epsilon)<C\epsilon^{k},$

so

$P(T_{t}(E),\epsilon)<C^{\prime\prime}\epsilon^{k-s}.$

We obtain

$\displaystyle\overline{\dim_{\mathcal{M}}}(T_{t}(E))$
$\displaystyle=\limsup_{\epsilon\to
0}\frac{\log(P(T_{t}(E),\epsilon))}{\log(1/\epsilon)}$
$\displaystyle\leq(k+1)s-k.$

∎

##  4\. Proof of Theorem 2 and Corollary 2

In this section we consider $\mathcal{V}_{T,t}$ with $t$ a scalar as

$\mathcal{V}^{\epsilon}_{T,t}(\mu)=\int\cdots\int\left(\prod_{(i,j)\in\mathcal{E}(T)}\rho^{\epsilon}(x_{i}\cdot
x_{j}-t)\right)d\mu(x_{1})\cdots d\mu(x_{k+1}).$

Our lower bound comes from repeated use of Holder’s inequality, which ‘folds’
the graph onto itself until reaching a single edge. $T$ itself is not
guaranteed to enjoy enough symmetry for such an argument to work out, so we
embed $T$ in a larger graph $\sigma(T)$ which is highly symmetric.

$\cdots$$T_{1}$$T_{n}$$T:$$\cdots$$T_{1}$$T_{n}$$T_{u}:$$\cdots$$\sigma(T_{u})$$\sigma(T_{u})$${\displaystyle\times
n}$$\sigma(T):$ Figure 1. Inductive construction of $\sigma(T)$.

######  Definition 5 (Symmetric Tree Covers).

Let $T$ be a tree with at least $k\geq 1$ edges. We define the symmetric tree
cover $\sigma(T)$ of $T$ as follows. If $k=1$ then $\sigma(T)=T$. Otherwise
let $u$ be a non-leaf vertex of $T$. Let $T_{u}$ be the tree obtained by
collapsing every neighbor of $u$ to a single vertex and reattaching $u$ to
this vertex. Finally join $\deg(u)$ copies of $\sigma(T_{u})$ at $u$ and call
the resulting tree $\sigma(T)$.

A diagram of the induction is provided in Figure 1. A concrete example is in
Figure 2.

$T_{{\color[rgb]{0.29,0.56,0.89}\definecolor[named]{pgfstrokecolor}{rgb}{0.29,0.56,0.89}\bullet}}$$\sigma$$T_{{\color[rgb]{0.29,0.56,0.89}\definecolor[named]{pgfstrokecolor}{rgb}{0.29,0.56,0.89}\bullet}}$$\sigma$$\sigma$$\bowtie{\color[rgb]{0.5,0.5,0.5}{}_{\bullet}}$$\bowtie{\color[rgb]{0.5,0.5,0.5}{}_{\bullet}}$
Figure 2. Unwrapping the induction for a concrete tree. Downward arrows are
the construction of the $T_{u}$’s as in Definition 5. Rightward arrows are the
$\sigma$ operation. Upward arrows are the joining operation as in the last
step of Definition 5. Edges in the upper left graph are tracked in red.

Note that the symmetric tree covering can depend on the choice of pivot at
each stage, but we have no need for uniqueness. It is not difficult to
establish the following properties of $\sigma(T)$.

######  Lemma 1.

$T\subset\sigma(T)$ and $\sigma(T)$ is finite.

###### Proof.

We proceed by induction. If $T$ is a single edge we are done. Suppose that $T$
has $k\geq 2$ edges and $T^{\prime}\subset\sigma(T^{\prime})$ for any tree
$T^{\prime}$ on fewer than $k$ edges. $T_{u}$ contains $k-\delta(u)+1$ edges,
and $\delta(u)>1$ as we can take $u$ to be a non-leaf vertex. Thus
$T_{u}\subset\sigma(T_{u})$. $\sigma(T_{u})$ contains a copy of $T_{u}$ for
each vertex, so it contains each connected component of $T\setminus u$
connected to $u$, giving $T\subset\sigma(T)$. Also $\sigma(T)$ is finite as
$\sigma(T_{u})$ is by induction finite. ∎

The base case when $T$ has a single edge is contained in a paper by A.
Greenleaf, A. Iosevich, and K. Taylor [7]. We give the theorem in our notation
below, letting $e$ denote an edge.

######  Theorem 4 (Greenleaf–Iosevich–Taylor [7]).

Let $\mu$ have exponent $s>(d+1)/2$. Then there is an open interval $I$ such
that

$\mathcal{V}^{\epsilon}_{e,t}=\langle\mathcal{R}_{t}^{\epsilon}\mu,\mu\rangle\gtrsim
1$

independently of $\epsilon>0$ and $t\in I$.

Consider when $T$ has $k\geq 2$ edges and let $T_{u}$ be as in Definition 5.
Note that the disjoint copies of $T_{u}$ are common only in $u$. We have

$\mathcal{V}_{\sigma(T),t}^{\epsilon}(\mu)=\int\left(\int\cdots\int\prod_{(i,j)\in\mathcal{E}(\sigma(T_{u}))}\rho^{\epsilon}(x_{i}\cdot
x_{j}-t)d\mu(x_{1})\cdots d\mu(x_{k^{\prime}})\right)^{\deg(u)}d\mu(u),$

where we are abusing notation and letting $u$ represent the vertex as embedded
in $E$ and as in the abstract graph $T$. Here $x_{1},\ldots,x_{k^{\prime}}$
are the vertices in $T_{u}$ excluding $u$. Since $\mu$ is a probability
measure, Holder gives

$\displaystyle\int$
$\displaystyle\left(\int\cdots\int\prod_{(i,j)\in\mathcal{E}(\sigma(T_{u}))}\rho^{\epsilon}(x_{i}\cdot
x_{j}-t)d\mu(x_{1})\cdots d\mu(x_{k^{\prime}})\right)^{\deg(u)}d\mu(u)$
$\displaystyle\geq\left(\int\int\cdots\int\prod_{(i,j)\in\mathcal{E}(\sigma(T_{u}))}\rho^{\epsilon}(x_{i}\cdot
x_{j}-t)d\mu(x_{1})\cdots d\mu(x_{k^{\prime}})d\mu(u)\right)^{\deg(u)}$
$\displaystyle=(\mathcal{V}_{\sigma(T_{u}),t}^{\epsilon}(\mu))^{\deg(u)}\gtrsim
1,$

where the last line is by induction. ∎

###  4.1. Proof of Corollary 2

Set

$K_{n}=\\{(x_{1},\ldots,x_{k+1})\in E^{k+1}:t-1/n\leq x_{i}\cdot x_{j}\leq
t+1/n,(i,j)\in\mathcal{E}(T)\\}.$

Then the $K_{n}$ are nested, non-increasing, and

$\bigcap_{n\geq 1}K_{n}=\sigma(T)_{t}(E).$

Consider $\Phi(x_{1},\ldots,x_{k+1})=(x_{i}\cdot x_{j})_{(i,j)\in E(T)}$,
which is continuous as a function $\mathbb{R}^{k+1}\to\mathbb{R}^{k}$. Then
$K_{n}=E^{k+1}\cap\Phi^{-1}([t-1/n,t+1/n])$ is compact, being the intersection
of a compact set and a closed set. By Theorem 2 $\mu(K_{n})\geq c/n^{k}>0$, so
$K_{n}$ is nonempty. By Cantor’s intersection theorem $\sigma(T)_{t}(E)$ is
thus nonempty. By the inclusion of $T$ in $\sigma(T)$, $T_{t}(E)$ is nonempty.
∎

##  5\. Appendix

###  5.1. The Radon Transform

As alluded to in Section 3, we have a family of Radon transforms
$\mathcal{R}_{t}^{\epsilon}$ given by

$\mathcal{R}_{t}^{\epsilon}f(x)=\int f(y)\rho^{\epsilon}(x\cdot y-t)dy.$

When $\mu$ is a Borel measure we write

$\mathcal{R}_{t}^{\epsilon}(f\mu)(x)=\int f(y)\rho^{\epsilon}(x\cdot
y-t)d\mu(y).$

The following is a well-known mapping property of
$\mathcal{R}^{\epsilon}_{t}$. See [14] for the original argument. For a source
with more background, see Stein and Shakarchi’s book on functional analysis
[15].

######  Theorem 5.

$\mathcal{R}_{t}^{\epsilon}$ is a bounded linear operator
$L^{2}(\mathbb{R}^{d})\to L^{2}_{(d-1)/2}(\mathbb{R}^{d})$ with

$\|\mathcal{R}_{t}^{\epsilon}f\rVert_{L_{(d-1)/2}^{2}(\mathbb{R}^{d})}\lesssim\|f\rVert_{L^{2}(\mathbb{R}^{d})}$

independently of $\epsilon>0$ and for $t\approx 1$.

Recall that the Sobolev space $L^{2}_{\alpha}(\mathbb{R}^{d})$ is the function
space equipped with the norm

$\|f\rVert_{L_{\alpha}^{2}(\mathbb{R}^{d})}:=\left(\int(1+|\xi|^{2})^{\alpha}|\widehat{f}(\xi)|^{2}d\xi\right)^{1/2}.$

We bootstrap off this result to show $L^{2}(\mu)\to L^{2}(\mu)$ boundedness of
$\mathcal{R}_{t}^{\epsilon}$. This was done for convolution operators in [10],
but the method also applies (as the authors of [10] remark) to Radon-type
operators. We give the proof below.

######  Theorem 3.

If $\mu$ is a Frostman measure with exponent $s>(d+1)/2$ and with support as
was established in Section 2, $\mathcal{R}_{t}^{\epsilon}$ is a bounded linear
operator $L^{2}(\mu)\mapsto L^{2}(\mu)$ with

$\|\mathcal{R}_{t}^{\epsilon}(f\mu)\rVert_{L^{2}(\mu)}\lesssim\|f\rVert_{L^{2}(\mu)}$

independently of $\epsilon>0$ and for $t\approx 1$.

###### Proof.

By polarization, it suffices to show that for any $\|g\rVert_{L^{2}(\nu)}\leq
1$,

$|\langle\mathcal{R}^{\epsilon}_{t}(f\mu),g\mu\rangle|\lesssim\|f\rVert_{L^{2}(\mu)}\|g\rVert_{L^{2}(\mu)}$

independently of $\epsilon>0$ and $t\approx 1$. To proceed, we localize to
dyadic frequencies. We will see that the large frequencies are the only ones
that give us any trouble, so we consider a partition of unity

$\sum_{j\geq 1}\chi(2^{-j}\xi)+\chi_{0}(\xi)=1,$

where $\chi$ is supported in the annulus $\\{\xi:1/4\leq|\xi|\leq 1\\}$. One
can construct such functions by considering a $C^{\infty}$ function $\phi$
equal to 1 when $|\xi|\geq 1$ and to $0$ when $|x|\leq 1/2$, and letting
$\chi(\xi)=\phi(2\xi)-\phi(\xi)$. The function $\chi_{0}$ is supported in the
ball $\\{\xi:|\xi|\leq 1\\}$ and is also smooth, since $\sum_{j\geq
1}\chi(2^{-j}\cdot)$ being the sum of only a finite number of smooth functions
in a neighborhood of any point is smooth. Now we can define the Littlewood-
Paley projection by the relation

$\widehat{P_{j}f}(\xi)=\widehat{f}(\xi)\chi(2^{-j}\xi)$

for $j\geq 1$, and

$\widehat{P_{0}f}(\xi)=\widehat{f}(\xi)\chi_{0}(\xi).$

Then $f=\sum_{j\geq 0}P_{j}f$. Applying the Littlewood-Paley decomposition to
$f\mu$ and $g\mu$, we obtain

(2) $\displaystyle|\langle\mathcal{R}^{\epsilon}_{t}(f\mu),g\mu\rangle|$
$\displaystyle\leq\sum_{j,k\geq
0}|\langle\mathcal{R}^{\epsilon}_{t}(P_{j}(f\mu)),P_{k}(g\mu)\rangle|$ (3)
$\displaystyle=\sum_{|j-k|\leq
M}|\langle\mathcal{R}^{\epsilon}_{t}(P_{j}(f\mu)),P_{k}(g\mu)\rangle|+\sum_{|j-k|>M}|\langle\mathcal{R}^{\epsilon}_{t}(P_{j}(f\mu)),P_{k}(g\mu)\rangle|,$

where $M$ is a constant to be chosen later. We handle the $|j-k|\leq M$
portion first. We need a mechanism to transfer an $L^{2}_{(d+1)/2}$ bound to a
$L^{2}(\mu)$ one. We need the following generic test for $L^{2}$ boundedness.
See [17] Lemma 7.5.

######  Theorem 6 (Schur’s test).

Let $(X,\mu)$ and $(Y,\nu)$ be measure spaces, and let $K(x,y)$ be a
measurable function on $X\times Y$ with

$\int_{X}|K(x,y)|d\mu(x)\leq A\text{ for each $y$},$
$\int_{Y}|K(x,y)|d\nu(x)\leq B\text{ for each $x$}.$

Define $T_{K}f(x)=\int K(x,y)f(y)d\nu(y)$. Then there is an estimate

$\|T_{K}f\rVert_{L^{2}(\mu)}\leq\sqrt{AB}\|f\rVert_{L^{2}(\mu)}.$

Now we can continue to prove the following.

######  Lemma 2.

If $\mu$ is a Frostman measure with exponent $s$ we have the estimate

$\|\widehat{f\mu}\rVert_{L^{2}(|\xi|\leq 2^{j})}\lesssim
2^{j(d-s)/2}\|f\rVert_{L^{2}(\mu)}.$

Lemma 2 is a special case of a result in [16]. A straightforward proof of
Lemma 2 is contained in [17], but we give it here with all the details.

###### Proof.

Let $\phi$ be an even Schwarz function which is $\geq 1$ on the unit ball and
whose Fourier transform has compact support. It is not difficult to see that
such a function exists. For example, let $f$ be a real-valued, nonnegative,
symmetric $C_{0}^{\infty}(\mathbb{R}^{d})$ function such as

$f(x)=\begin{cases}\exp(-\frac{1}{1-|x|^{2}})&|x|\leq 1\\\
0&\text{otherwise}\end{cases}.$

Define $g:=\mathcal{F}^{-1}(f)$. Then

$g(0)=\int f(x)dx>0,$

and by rescaling $f$ we can assume $g(0)\geq 2$. $g$ is certainly continuous,
so for some $\delta>0$, $g\geq 1$ on $\\{|x|\leq\delta\\}$. Finally define
$\phi(x)=\phi(\delta x)$ which is as desired.

Now we define $\phi_{j}(\cdot)=\phi(2^{-j}\cdot)$, which is at least 1 on
$\\{|\xi|\leq 2^{j}\\}$. Using this and Plancherel,

$\displaystyle\|\widehat{f\mu}\rVert_{L^{2}(|\xi|\leq 2^{j})}$
$\displaystyle\leq\|\phi_{j}\widehat{f\mu}\rVert_{L^{2}}$
$\displaystyle=\|\widehat{\phi_{j}}*(f\mu)\rVert_{L^{2}}.$

This last line is the $L^{2}$ norm of the function

$x\mapsto\int 2^{jd}\widehat{\phi}(2^{j}(x-y))f(y)d\mu(y).$

We have

$\int|2^{jd}\widehat{\phi}(2^{j}(x-y))|dx=\|\widehat{\phi}\rVert_{L^{1}}$

by a change of variables. $\widehat{\phi}$ has compact support in some fixed
ball $M$, so

$\displaystyle\int|2^{jd}\widehat{\phi}(2^{j}(x-y))|d\mu(y)$
$\displaystyle=2^{jd}\int_{|x-y|\leq
M2^{-j}}|\widehat{\phi}(2^{j}(x-y))|d\mu(y)$ $\displaystyle\lesssim
2^{j(d-s)}.$

The last line follows from the fact that $\mu(B(x,r))\lesssim r^{s}$. Now we
can apply Schur’s test with the kernel
$K(x,y)=2^{jd}\widehat{\phi}(2^{j}(x-y))$ and obtain

$\|\widehat{\phi_{j}}*(f\mu)\rVert_{L^{2}}\lesssim
2^{j(d-s)/2}\|f\rVert_{L^{2}(\mu)}.$

∎

Returning to the proof of Theorem 3, Plancherel and Cauchy-Schwarz give that
the $|j-k|\leq M$ portion of (3) is dominated by

$\displaystyle\sum_{|j-k|\leq
M}\|\widehat{\mathcal{R}^{\epsilon}_{t}(P_{j}(f\mu))}\rVert_{L^{2}(|\tau|\approx
2^{k})}\|\widehat{P_{k}(g\mu)}\rVert_{L^{2}}.$

We take advantage of Theorem 5, the $L^{2}(\mathbb{R}^{d})\to
L^{2}_{(d-1)/2}(\mathbb{R}^{d})$ boundedness of the Radon transform
$\mathcal{R}_{t}^{\epsilon}$. We have

$\displaystyle\|\widehat{\mathcal{R}^{\epsilon}_{t}(P_{j}(f\mu))}\rVert_{L^{2}(|\tau|\approx
2^{k})}$ $\displaystyle\lesssim
2^{-k(d-1)/2}\left(\int(1+|\tau|^{2})^{(d-1)/2}|\widehat{\mathcal{R}^{\epsilon}_{t}(P_{j}(f\mu))}(\tau)|^{2}d\tau\right)^{1/2}$
$\displaystyle=2^{-k(d-1)/2}\|\mathcal{R}^{\epsilon}_{t}(P_{j}(f\mu))\rVert_{L^{2}_{(d-1)/2}}$
$\displaystyle\leq 2^{-k(d-1)/2}\|P_{j}(f\mu)\rVert_{L^{2}}$
$\displaystyle\lesssim 2^{-k(d-1)/2}2^{j(d-s)/2}.$

Thus we are left with

$\displaystyle\sum_{|j-k|\leq
M}\|\widehat{\mathcal{R}^{\epsilon}_{t}(P_{j}(f\mu))}\rVert_{L^{2}(|\tau|\approx
2^{k})}\|\widehat{P_{k}(g\mu)}\rVert_{L^{2}}\lesssim\sum_{|j-k|\leq
M}2^{-k(d-1)/2}2^{j(d-s)/2}2^{k(d-s)/2},$

which is summable if $s>(d+1)/2$.

We still need to handle the $|j-k|>M$ portion of (3). This diagonalization can
be executed with the following Lemma.

######  Lemma 3.

For any positive integer $N$, there is a $K$ such that if $|j-k|>K$,

$\displaystyle|\langle\mathcal{R}^{\epsilon}_{t}(P_{j}(f\mu)),P_{k}(g\mu)\rangle|\lesssim_{N}2^{-N\max(j,k)}\|f\rVert_{L^{2}(\mu)}\|g\rVert_{L^{2}(\mu)},$

independently of $\epsilon>0$ and for $t\approx 1$.

We give the proof below. With Lemma 3 we see that

$\sum_{|j-k|>M}|\langle\mathcal{R}_{t}^{\epsilon}(P_{j}(f\mu)),P_{k}(g\mu)\rangle|\lesssim_{N}\|f\rVert_{L^{2}(\mu)}\|g\rVert_{L^{2}(\mu)}\sum_{|j-k|>M}2^{-N\max(j,k)}.$

This is summable even when $N=1$. ∎

###### Proof of Lemma 3.

We will argue by nonstationary phase. By the support properties of $\mu$, we
can insert a bump function $\eta$ with support in $[c,1]^{d}$. By Fourier
inversion on $P_{j}(f\mu)$ and $\rho^{\epsilon}$,

$\displaystyle\mathcal{R}_{t}^{\epsilon}(P_{j}(f\mu))(x)$ $\displaystyle=\int
P_{j}(f\mu)(y)\eta(x,y)\rho^{\epsilon}(x\cdot y-t)dy$ $\displaystyle=\iiint
e^{2\pi i(y\cdot\xi+s(x\cdot
y-t))}\widehat{P_{j}(f\mu)}(\xi)\eta(x,y)\widehat{\rho}(\epsilon s)d\xi dsdy$

Taking the Fourier transform of $\mathcal{R}_{t}(P_{j}(f\mu))$,

$\displaystyle\widehat{\mathcal{R}_{t}(P_{j}(f\mu))}(\tau)$
$\displaystyle=\iiiint e^{2\pi i(y\cdot\xi-x\cdot\tau+s(x\cdot
y-t))}\widehat{P_{j}(f\mu)}(\xi)\eta(x,y)\widehat{\rho}(\epsilon s)d\xi dsdy.$

Finally Plancherel gives

$\displaystyle\langle\mathcal{R}_{t}^{\epsilon}(P_{j}(f\mu)),P_{k}(g\mu)\rangle=\iiint\widehat{P_{j}(f\mu)}(\xi)\widehat{P_{k}(g\mu)}(\tau)\widehat{\rho}(\epsilon
s)d\xi d\tau ds,$

where

$I_{jk}(\xi,\tau,s)=\chi_{j}(\xi)\chi_{k}(\tau)\iint e^{2\pi
i(y\cdot\xi-x\cdot\tau+s(x\cdot y-t))}\eta(x,y)dxdy.$

Inserting the smooth cutoffs from the definition of the Littlewood-Paley
decomposition is justified as $\chi_{j}\approx\chi_{j}^{2}$. For convenience
we write

$\Psi_{\xi,\tau,s}(x,y)=y\cdot\xi-x\cdot\tau+s(x\cdot y-t).$

We would be done if we could show that

(4) $|I_{jk}(\xi,\tau,s)|\lesssim_{N}(1+|s|)^{-2}2^{-N\max(j,k)}.$

$\rho$ is Schwarz since it is even $C_{0}^{\infty}$, so $\widehat{\rho}$ is
Schwarz. This gives $|\widehat{\rho}(\epsilon s)|\lesssim 1$. It would follow
from $|\widehat{\rho}(\epsilon s|\lesssim 1$ and (4) that

$\displaystyle|\langle\mathcal{R}_{t}^{\epsilon}(P_{j}(f\mu)),P_{k}(g\mu)\rangle|$
$\displaystyle\leq\iiint|\widehat{P_{j}(f\mu)}(\xi)||\widehat{P_{k}(g\mu)}(\tau)||\widehat{\rho}(\epsilon
s)|dsd\xi d\tau$
$\displaystyle\lesssim_{N}2^{-N\max(j,k)}\iiint|\widehat{P_{j}(f\mu)}(\xi)||\widehat{P_{k}(g\mu)}(\tau)|(1+|s|)^{-2}dsd\xi
d\tau$
$\displaystyle=2^{-N\max(j,k)}\int|\widehat{P_{j}(f\mu)}(\xi)|d\xi\int|\widehat{P_{k}(g\mu)}(\tau)|d\tau\int(1+|s|)^{-2}ds.$

The integral in $s$ is finite. By Cauchy-Schwarz and Lemma 2, the integrals in
$\xi$ and $\tau$ are dominated by $2^{jd/2}2^{j(d-s)/2}$ and
$2^{kd/2}2^{k(d-s)/2}$ respectively. Thus

$|\langle\mathcal{R}_{t}^{\epsilon}(P_{j}(f\mu)),P_{k}(g\mu)\rangle|\lesssim_{N}2^{(-N+2d-s)\max(j,k)},$

so by choosing a large enough $N$ we are done.

Now we prove $\eqref{eq:diag:meat}$. We have

$\nabla_{x}\Psi_{\xi,\tau,s}=-\tau+sy$

and

$\nabla_{y}\Psi_{\xi,\tau,s}=\xi+sx.$

Assume without loss of generality that $j>k+K$, so $|\xi|\ll|\tau|$. When
$|s|\ll|\tau|$,

$|\nabla_{x}\Psi_{\xi,\tau,s}|\gtrsim|\tau|-|s|\gtrsim|\tau|,$

Where we used that $\eta$ has fixed compact support. If $|s|\gg|\tau|$,

$|\nabla_{x}\Psi_{\xi,\tau,s}|\gtrsim|s|-|\tau|\gtrsim|s|,$

where we use that $\eta$ is not supported near the origin. If
$|s|\approx|\tau|$,

$\displaystyle|\nabla_{y}\Psi_{\xi,\tau,s}|$ $\displaystyle\gtrsim|s|-|\xi|$
$\displaystyle\approx|\tau|-|\xi|$ $\displaystyle\gtrsim|\tau|.$

In any case $|\nabla\Psi_{\xi,\tau,s}|\gtrsim\max(|\tau|,|s|)$.

It is immediate that all the partials of $\Psi_{\xi,\tau,s}$ are bounded above
by a constant multiple of $\max(|\tau|,|s|)$. Consider the differential
operator

$L=\frac{1}{2\pi
i}\frac{\nabla\Psi_{\xi,\tau,s}}{|\nabla\Psi_{\xi,\tau,s}|^{2}}\cdot\nabla,$

for which $e^{2\pi i\Psi_{\xi,\tau,s}}$ is clearly an eigenvalue. Therefore
$L^{N}(e^{2\pi i\Psi_{\xi,\tau,s}})=e^{2\pi i\Psi_{\xi,\tau,s}}$ for any
positive integer $N$. Thus

$I_{jk}(\xi,\tau,s)=\iint L^{N}(e^{2\pi i\Psi_{\xi,\tau,s}})\eta
dy^{\prime}dx=\iint e^{2\pi
i\Psi_{\xi,\tau,s}}(L^{t})^{N}(\eta)dy^{\prime}dx.$

The transpose $L^{t}$ of $L$ is given by

$\displaystyle L^{t}(f)$ $\displaystyle=-\frac{1}{2\pi
i}\nabla\cdot\left(\frac{\nabla\Psi_{\xi,\tau,s}}{|\nabla\Psi_{\xi,\tau,s}|^{2}}f\right)$
$\displaystyle=-\frac{1}{2\pi i}\left(\nabla
f\cdot\frac{\nabla\Psi_{\xi,\tau,s}}{|\nabla\Psi_{\xi,\tau,s}|^{2}}-f\cdot\frac{\nabla^{2}\Psi_{\xi,\tau,s}}{|\nabla\Psi_{\xi,\tau,s}|^{2}}\right)$

and taking the modulus,

$|L^{t}(\eta)|\lesssim|\nabla\eta|\max(|\tau|,|s|)^{-1}+|\eta|\max(|\tau|,|s|)^{-1}.$

We can continue integrating by parts up to any positive $N^{\prime}$ and
obtain a bound

$|(L^{t})^{N^{\prime}}(\eta)|\lesssim_{N^{\prime}}\max(|\tau|,|s|)^{-N^{\prime}}\sum_{|\alpha|\leq
N^{\prime}}|\partial^{\alpha}\eta|.$

Taking the modulus of $I_{jk}(\xi,\tau,s)$, we obtain

$|I_{jk}(\xi,\tau,s)|\lesssim_{N^{\prime}}\max(|\tau|,|s|)^{-N^{\prime}}\iint\sum_{|\alpha|\leq
N^{\prime}}|\partial^{\alpha}\eta|dy^{\prime}dx\lesssim_{N}\max(|\tau|,|s|)^{-N^{\prime}},$

since $\eta$ is Schwarz. Since $|\tau|\geq 1$,

$\displaystyle|I_{jk}(\xi,\tau,s)|$
$\displaystyle\lesssim_{N}\max(|\tau|,|s|)^{-2}\max(|\tau|,|s|)^{-N^{\prime}+2}$
$\displaystyle\lesssim(1+|s|)^{-2}|\tau|^{-N^{\prime}+2}$
$\displaystyle\lesssim(1+|s|)^{-2}2^{-(N^{\prime}+2)\max(j,k)}.$

Taking $N^{\prime}$ large enough we are done. ∎

With Lemma 3 proved, we are done. ∎

##  6\. acknowledgements

I would like to thank my undergraduate mentor and friend Alex Iosevich, for
his support in this project and in many others. Thank you to Ben Baily, Brian
Hu, and Ethan Pesikoff for helping to develop the symmetric tree cover idea
over SMALL 2021.

## References

  * [1] Michael Bennett, Alexander Iosevich, and Krystal Taylor.  Finite chains inside thin subsets of $\mathbb{R}^{d}$.  Analysis & PDE, 9(3):597–614, 2016.
  * [2] Xiumin Du, Larry Guth, Yumeng Ou, Hong Wang, Bobby Wilson, and Ruixiang Zhang.  Weighted restriction estimates and application to falconer distance set problem.  American Journal of Mathematics, 143(1):175–211, 2021.
  * [3] Xiumin Du, Alex Iosevich, Yumeng Ou, Hong Wang, and Ruixiang Zhang.  An improved result for falconer’s distance set problem in even dimensions.  Mathematische Annalen, 380(3):1215–1231, 2021.
  * [4] Xiumin Du and Ruixiang Zhang.  Sharp $L^{2}$ estimates of the schrödinger maximal function in higher dimensions.  Annals of Mathematics, 189(3):837–861, 2019.
  * [5] Kenneth J Falconer.  On the hausdorff dimensions of distance sets.  Mathematika, 32(2):206–212, 1985.
  * [6] Allan Greenleaf, Alex Iosevich, Bochen Liu, and Eyvindur Palsson.  A group-theoretic viewpoint on erdős–falconer problems and the mattila integral.  Revista Matemática Iberoamericana, 31(3):799–810, 2015.
  * [7] Allan Greenleaf, Alex Iosevich, and Krystal Taylor.  Configuration sets with nonempty interior.  The Journal of Geometric Analysis, 31(7):6662–6680, 2021.
  * [8] Larry Guth, Alex Iosevich, Yumeng Ou, and Hong Wang.  On falconer’s distance set problem in the plane.  Inventiones mathematicae, 219(3):779–830, 2020.
  * [9] Larry Guth and Nets Hawk Katz.  On the erdős distinct distances problem in the plane.  Annals of mathematics, pages 155–190, 2015.
  * [10] A Iosevich, Ben Krause, E Sawyer, K Taylor, and I Uriarte-Tuero.  Maximal operators: scales, curvature and the fractal dimension.  Analysis Mathematica, 45(1):63–86, 2019.
  * [11] A Iosevich and K Taylor.  Finite trees inside thin subsets of rd, modern methods in operator theory and harmonic analysis, 51–56.  Springer Proc. Math. Stat, 291, 2019.
  * [12] Alex Iosevich, Krystal Taylor, and Ignacio Uriarte-Tuero.  Pinned geometric configurations in euclidean space and riemannian manifolds, 2016.
  * [13] Pertti Mattila.  Geometry of sets and measures in Euclidean spaces: fractals and rectifiability.  Number 44. Cambridge university press, 1999.
  * [14] Duong H Phong and Elias M Stein.  Radon transforms and torsion.  International Mathematics Research Notices, 1991(4):49–60, 1991\.
  * [15] Elias M Stein and Rami Shakarchi.  Functional analysis: introduction to further topics in analysis.  Princeton Lectures in Analysis, 4, 2011.
  * [16] Robert S. Strichartz.  Fourier asymptotics of fractal measures.  Journal of Functional Analysis, 89(1):154–187, 1990.
  * [17] Thomas H Wolff.  Lectures on harmonic analysis, volume 29.  American Mathematical Soc., 2003.


# Ancilla-Free Measurement of Out-of-Time-Ordered Correlation Functions:
General Measurement Protocol and Rydberg Atom Implementation

Michael Kastner  Institute of Theoretical Physics, University of Stellenbosch,
Stellenbosch 7600, South Africa  Hanse-Wissenschaftskolleg, Lehmkuhlenbusch 4,
27753 Delmenhorst, Germany  Philip Osterholz  Christian Gross  Physikalisches
Institut, Eberhard Karls Universität Tübingen, 72076 Tübingen, Germany

###### Abstract

We introduce a protocol that gives access to out-of-time-ordered correlation
functions in many-body quantum systems. Unlike other such protocols, our
proposal, which can be applied to arbitrary initial states, neither requires
ancilla degrees of freedom to the quantum system of interest, nor has the need
for randomized measurements. Nontrivial experimental capabilities required to
implement the protocol are single-site measurements, single-site rotations,
and backwards time evolution. To exemplify the implementation of the protocol,
we put forward a strategy for Hamiltonian sign inversion $H\to-H$ in arrays of
Rydberg-dressed atoms. In this way, a complete and practical toolbox is
obtained for the measurement of out-of-time-ordered correlations in
equilibrium and nonequilibrium situations.

“Scrambling” refers to the process where, under unitary time evolution of a
many-body quantum system, initially local information disperses into many-body
entanglement and spreads over increasingly larger regions of the system. In
this process, information, while in principle conserved, becomes inaccessible
to local measurements, resulting in an effective loss of memory. Quantum
information scrambling rose to prominence in the context of the black hole
information problem [1, *ShenkerStanford14], and accompanies the dynamics of
thermalization in isolated quantum systems [3, *Srednicki94,
*GogolinEisert16].

A strategy to quantify the size of the region across which quantum information
is spread under the system dynamics consists in considering two operators $V$
and $W$ that are initially supported on separated regions of space, implying
$[W,V]=0$. The commutator
$C(t)=\left\langle\lvert[W(t),V]\rvert^{2}\right\rangle$ then quantifies the
degree to which the time-evolved operator $W(t)=\exp(iHt)W\exp(-iHt)$ spreads
into the support of $V$, indicating whether or not the region over which
quantum information can be scrambled in time $t$ extends into the support of
$V$. Moreover, the semiclassical limit of $C$ quantifies the sensitivity of
the dynamics to small changes in the initial conditions, which suggests to
interpret $C$ as a measure of quantum chaoticity [6]. Closely related to $C$,
and often more accessible, is the out-of-time-ordered correlation (OTOC)
111For unitary operators $V$ and $W$ satisfying $[W,V]=0$, a short calculation
yields
$\operatorname{\mathrm{Re}}[F(t)]=1-\left\langle\lvert[W(t),V]\rvert^{2}\right\rangle/2$.

$F(t)=\Braket{W^{\dagger}(t)V^{\dagger}W(t)V}.$ (1)

Such correlation functions have been used in early studies of electron
scattering off impurities in models of superconductors [8], are related to the
Renyi entropy and the generation of entanglement [9, 10], and have been
employed to distinguish many-body localized phases from thermalizing ones [10,
11, *Chen_etal17].

Figure 1: Sequence of steps for accessing the real part (a) and imaginary part
(b) of an OTOC. From top to bottom: (i) initial state, (ii) projective
measurement or spin rotation at site $j$, (iii) forward time evolution under
the Hamiltonian $H$, (iv) projective measurement or spin rotation at site $i$,
(v) backward time evolution under $H$, (vi) projective measurement or spin
rotation at site $j$, (vii) forward time evolution under $H$, (viii)
projective measurement at site $i$.

A setting of particular physical interest is when $V$ and $W$ are local
Hermitian operators that correspond to experimentally measurable observables.
But even in such a, presumably “simpler,” situation, $F$ in Eq. (1) is the
expectation value of a, in general, non-Hermitian and nonlocal operator. A
direct measurement of such an expectation value is unrealistic in all but the
most trivial special cases, and one therefore has to resort to indirect
measurement protocols in order to gain access to OTOCs. Such measurement
protocols for OTOCs essentially interpret the product of operators on the
right-hand side of Eq. (1) as a sequence of operations. Because of the lack of
time-ordering that is characteristic for OTOCs, this sequence of operations
involves forward-in-time as well as backward-in-time evolving unitaries,
which, while challenging in general, are available in certain experimental
platforms such as atoms in optical lattices [13] and in all-to-all interacting
neutral atom or ion systems [14, 15, 16]. While most of the proposed
measurement protocols for OTOCs require backward-in-time evolution, other
strategies, each with their own merits and challenges, are known as well [17,
*Blocher_etal22]. Some aspects of OTOCs have already been measured in small
systems [19, 20, 21, 22, 23, 24].

Here we will focus on measurement protocols for OTOCs that make use of
backwards time evolution. Several such protocols have been proposed by now
[25, *GarciaAlvarez_etal17, 27], some of which have been implemented
experimentally [28, *Li_etal17, *Braumueller_etal22, 31]. While none of these
protocols is easy to implement, some are less challenging, but at the expense
of being applicable only to specific choices of $V$ and/or specific initial
states [28, *Li_etal17, *Braumueller_etal22, 27]. The protocol put forward in
Ref. [25, *GarciaAlvarez_etal17], on the other side, is applicable to
arbitrary $V$, $W$ and arbitrary initial states. It is, however, significantly
more difficult to implement, as it requires, in addition to backwards time
evolution, the capability to couple an ancilla qubit to the system of interest
and to create entanglement between the two. An experimental realization of
this ancilla-based protocol was reported in Ref. [31] for a two-dimensional
array of superconducting qubits, which is known for the exquisite level of
experimental controllability. In many other experimental platforms, however,
the simultaneous requirements of backwards time evolution and ancilla coupling
poses an obstacle. This motivates the search for alternative measurement
protocols, ideally of broad applicability and with more moderate experimental
requirements.

The first main result of this Letter is a measurement protocol for OTOCs that
requires neither ancilla quantum degrees of freedom to be coupled to the
system, nor interferometric techniques, nor averaging over randomized initial
states. In addition to backwards time evolution, the main experimental
requirement to execute the protocol are single-site measurements and single-
site rotations in a system of qubits or spin-$1/2$ degrees of freedom; see
Fig. 1 for an illustration. Single-site resolution and addressability are key
capabilities of quantum computing platforms and are readily available in a
variety of experimental settings.

As the second main result of this Letter we propose a technique, based on
microwave-assisted Rydberg dressing [32, 33, 34], that facilitates Hamiltonian
sign inversion, and hence backwards time evolution, in array of ultracold
Rydberg-dressed atoms. Combining this technique with local in-sequence readout
and local rotation techniques, our measurement protocol becomes a full-fledged
tool for the measurement of OTOCs in a relevant experimental platform, while
avoiding the challenge of having to couple ancillas to individual sites. Since
the protocol is not restricted to specific initial states, OTOCs can be
measured and analyzed in arbitrary equilibrium and nonequilibrium situations.
The sign-inversion technique is interesting also in the context of other
applications, for example, for quantum simulation at finite energies [35] or
quantum metrology [36, *frowis2016, *macri2016].

OTOC measurement protocol.—We consider an arbitrary network of $N$ qubits,
including regular lattices as special cases. Time evolution is assumed to be
unitary, generated by a time-independent Hamiltonian $H$, but is arbitrary
otherwise, allowing for multi-site interactions (beyond pair interactions) as
well as interactions of arbitrarily long range.

Our main technical requirement is that the operators $V$ and $W$ in Eq. (1)
have only two distinct (albeit possibly degenerate) eigenvalues. In the
context of qubit systems, this is a very natural and not particularly
restrictive setting. For notational simplicity we will in the following choose
single-site Pauli spin operators as observables, $W=\sigma_{i}^{a}$ and
$V=\sigma_{j}^{b}$, where $i$ and $j$ denote sites on the network and
$a,b\in\\{x,y,z\\}$ label spin components. The object of study is the OTOC

$C(t):=\operatorname{{Tr}}\left[\rho\sigma_{i}^{a}(t)\sigma_{j}^{b}\sigma_{i}^{a}(t)\sigma_{j}^{b}\right],$
(2)

where $\rho$ is the initial density operator. Note that, even though each
factor of the operator product on the right-hand side of Eq. (2) is Hermitian,
the product of operators in general is not, and hence $C$ can be complex.

Measurement protocol for the real part.—We show that the real part of $C$ can
be obtained by interpreting the operator product inside the trace of Eq. (2)
as measurements of the occurring spin operators, interspersed with time
evolutions 222This strategy has been employed in a different context in Ref.
[57].. This is by no means a trivial statement, as Eq. (2) describes unitary
evolution, and measurements are known to disturb unitary evolution due to wave
function collapse. However, when probing bivariate observables, these
disturbing effects, which do occur, cancel out exactly when using the
following measurement protocol, illustrated in Fig. 1:

  1. (i)

Prepare the initial state $\ket{\psi}$.

  2. (ii)

Projectively measure the observable $\sigma_{j}^{b}$ and record the outcome
($+$ or $-$).

  3. (iii)

Time-evolve unitarily until time $t$.

  4. (iv)

Projectively measure the observable $\sigma_{i}^{a}$ and record the outcome.

  5. (v)

Evolve backwards in time for a time $t$.

  6. (vi)

Projectively measure the observable $\sigma_{j}^{b}$ and record the outcome.

  7. (vii)

Time-evolve unitarily until time $t$.

  8. (viii)

Projectively measure the observable $\sigma_{i}^{a}$ and record the outcome.

  9. (ix)

Repeat (i)–(viii) many times and record the relative frequencies of the
combinations of measurement outcomes $(+++\,+)$, $(+++\,-)$, $(++-\,+)$, etc.,
occurring in each of the measurement sequences.

  10. (x)

Use these relative frequencies to estimate the corresponding probabilities
$P_{++++}$, $P_{+++-}$, $P_{++-+}$, etc., and calculate the correlation
function

$\mathscr{C}(t):=\sum_{o_{1},o_{2},o_{3},o_{4}\in\\{-1,+1\\}}o_{1}o_{2}o_{3}o_{4}P_{o_{1}o_{2}o_{3}o_{4}}.$
(3)

We show in Appendix A that

$2\mathscr{C}(t)-1=\operatorname{\mathrm{Re}}C(t),$ (4)

i.e., the real part of the desired OTOC (2) is obtained by applying the above
protocol that “naively” disregards the effect of measurement backaction. The
key experimental capabilities to execute the protocol are unitary backwards
time evolution and projective measurements of single qubits.

Unitarily evolved vs. projectively measured OTOCs.—Equation (4) is an exact
relation between the OTOC $C$ and the correlation function $\mathscr{C}$,
where the latter is determined by the probabilities $P_{\pm\pm\pm\pm}$. In an
experimental realization of the measurement protocol, these probabilities must
be estimated through finite sample averages. The sampling introduces
statistical errors, which, by error propagation, cause errors in $C$. We
illustrate the magnitude of these errors, and hence the performance of the
proposed measurement protocol when constrained by limited resources, for spin
chains with nearest-neighbor $XY$ couplings,

$H=-\sum_{k=1}^{N-1}\left(\sigma_{k}^{x}\sigma_{k+1}^{x}+\sigma_{k}^{y}\sigma_{k+1}^{y}\right).$
(5)

For this Hamiltonian and using the initial state
$\rho=(\ket{\uparrow\cdots\uparrow}\bra{\uparrow\cdots\uparrow})^{\otimes N}$,
we calculate the probabilities $P_{\pm\pm\pm\pm}$ as given in Appendix A. To
simulate a finite number of experimental runs of the measurement protocol, we
draw pseudorandom numbers according to these probabilities and calculate a
finite-sample estimator of $\mathscr{C}$. In Fig. 2, the real part
$\operatorname{\mathrm{Re}}C$ of the exact OTOC is compared to the finite-
sample estimator of $2\mathscr{C}-1$ for samples of size $N_{s}=10^{4}$. While
the agreement with the exact result is excellent, small statistical errors are
visible in the estimator. To assess the magnitude of the statistical errors,
we compare the estimators obtained with sample sizes $N_{s}=10^{2}$, and
$10^{3}$ in Fig. 3. Statistical errors are found to decrease quickly with
increasing sample size, and a moderate value of $N_{s}=10^{3}$ is sufficient
to obtain relative statistical errors of only a few percent.

Figure 2:  Real part of the OTOC $C$ as a function of time $t$ in an $XY$ spin
chain of length $N$. Different colors correspond to different pairs of lattice
sites in definition (2), as specified in the legend. Solid lines show exact
results for $C$, the dots mark estimated values obtained by calculating
$2\mathscr{C}-1$ from samples of size $10^{4}$. The further apart the sites
$i$ and $j$, the longer it takes until the OTOC starts to deviate from its
initial value of $1$, which is a manifestation of quasilocality in a system
with short-range interactions.

Measurement protocol for the imaginary part.—The imaginary part of an OTOC is
known to contain information that is complementary to that of the real part
[40], and obtaining both is therefore desirable. The corresponding measurement
protocol we present here requires, in addition to backward time evolution, the
experimental capability to perform single-qubit rotations at sites $i$ and
$j$. The imaginary part of the OTOC (2) can be obtained by the following
sequence of operations (see Fig. 1 for an illustration):

  1. (i’)

Prepare the initial state $\ket{\psi}$.

  2. (ii’)

Rotate spin $j$ by an angle $\theta_{1}$ around the $b$-direction.

  3. (iii’)

Time-evolve unitarily until time $t$.

  4. (iv’)

Rotate spin $i$ by an angle $\theta_{2}$ around the $a$-direction.

  5. (v’)

Evolve backwards in time for a time $t$.

  6. (vi’)

Rotate spin $j$ by an angle $\theta_{3}$ around the $b$-direction.

  7. (vii’)

Time-evolve unitarily until time $t$.

  8. (viii’)

Projectively measure the observable $\sigma_{i}^{a}$.

  9. (ix’)

Repeat (i’)–(viii’) many times and record the empirical mean of the
measurement outcome.

This empirical mean gives an estimator of the expectation value
$\braket{\sigma_{i}^{a}}_{t,\theta_{1},\theta_{2},\theta_{3}}$ with respect to
the state at the end of step (vii’) of the above protocol. We show in Appendix
B that

$\bigl{\langle}\sigma_{i}^{a}\bigr{\rangle}_{t,-\theta_{1},-\theta_{2},-\theta_{3}}-\bigl{\langle}\sigma_{i}^{a}\bigr{\rangle}_{t,\theta_{1},\theta_{2},\theta_{3}}\\\
-\bigl{\langle}\sigma_{i}^{a}\bigr{\rangle}_{t,-\theta_{1},\theta_{2},-\theta_{3}}+\bigl{\langle}\sigma_{i}^{a}\bigr{\rangle}_{t,\theta_{1},-\theta_{2},\theta_{3}}\\\
=4\sin(\theta_{2})\sin(\theta_{1}+\theta_{3}/2)\sin(\theta_{3}/2)\operatorname{\mathrm{Im}}C(t).$
(6)

Hence, the imaginary part of the OTOC (2) is obtained by performing the above
protocol (i’)–(viii’) for the four sets of rotation angles
$(-\theta_{1},-\theta_{2},-\theta_{3})$, $(\theta_{1},\theta_{2},\theta_{3})$,
$(-\theta_{1},\theta_{2},-\theta_{3})$, and
$(\theta_{1},-\theta_{2},\theta_{3})$. A simple and, in some sense, optimal
choice is $\theta_{1}=\theta_{2}=\theta_{3}=\pi/2$, in which case the right-
hand side of Eq. (6) simplifies to $2\operatorname{\mathrm{Im}}C(t)$.

Figure 3:  Magnitude of the statistical fluctuations in the estimator
$2\mathscr{C}-1$, obtained from Eq. (3) and using samples of sizes
$N_{s}=10^{2}$ (left) and $N_{s}=10^{3}$ (right). All data are for the OTOC
(2) with $i=2$ and $j=3$ on a chain of $N=4$ sites. Solid lines show the exact
result, the dots are estimated values, fluctuating around the exact value. The
shaded area around the exact result indicates an estimate of the statistical
error, obtained by drawing multiple samples, each of size $N_{s}$, from the
probability distribution of $P_{\pm\pm\pm\pm}$ and then calculate the standard
deviation of the estimated values.

Experimental implementation with Rydberg atom arrays.—The requirements to
implement the above described protocols are coherent forward and backward time
evolution under an effective spin-$1/2$ Hamiltonian, as well as the capability
to conduct single-site projective measurements and single-site spin rotations.
Among the experimental platforms that allow for coherent dynamics of many-body
qubit systems, arrays of ultracold Rydberg atoms in optical tweezers are
particularly suitable (see Ref. [41] for a review). Optical tweezers allow the
experimenter to arrange and hold the atoms in a lattice geometry of choice,
with lattice constants of the order of micrometers. To make the atoms interact
over such distances, they are excited to Rydberg states, i.e., atomic states
with a large principal quantum number. Various schemes to emulate spin-$1/2$
Hamiltonians in such arrays have been devised, giving rise to coherent spin
dynamics under Ising- or $XY$-type Hamiltonians. Moreover, single-site control
is well established for these platforms [42, 43]. In the following we present
a solution to the remaining challenge for a successful implementation of our
OTOC measurement protocol in Rydberg platforms, namely backwards time
evolution or, equivalently, sign inversion of the Hamiltonian.

Time inversion in Rydberg atom arrays.—The experimental scheme we propose is
based on microwave-assisted Rydberg dressing [32, *petrosyan2014,
*bijnen2015]. Rydberg dressing naturally leads to spin-1/2 degrees of freedom
being encoded in two low-lying and long-lived atomic states, with long-range
Ising interactions between the spins [44]. The strength of these interactions
can be dynamically tuned by choosing the detuning of the light field, which
off-resonantly couples one of the states to a Rydberg state. Several
experiments demonstrated this technique in optical lattices and tweezers [45,
*zeiher2016, *zeiher2017a, *guardado-sanchez2021, *hollerith2022,
*steinert2023, *eckner2023]. The sign of the induced Ising interaction is
determined by the sign of the interaction in the laser-addressed Rydberg
state. Implementing time reversal with this technique is not straightforward,
as it requires the existence of Rydberg states with opposite sign and near-
equal magnitude of the interaction potential. Even if a specific pair of
Rydberg states is identified that meets this special condition, interaction
reversal is still a technically demanding task requiring two distinct laser
frequencies.

Figure 4: Illustration of microwave-assisted potential inversion for the
example of 39K. (a) Interaction potential between pairs of atoms for various
eigenstates of the dipolar interaction. The blue line highlights the pair
potential between atoms in the $\ket{50S_{1/2},m_{F}=1/2}$ state. The energy
corresponding to the laser frequency is chosen as the energy-zero level and
the polarization is such that only the highlighted level is coupled from the
groundstate. (b) Switching on microwave radiation with a frequency of 27.592
GHz, the $\ket{50S_{1/2},m_{J}=1/2}$ state is coupled to the
$\ket{50P_{1/2},m_{J}=1/2}$ state. As a result, the pair potentials
highlighted in red emerge from the blue line in (a) as microwave-dressed pair-
states. The plotted data assumes linear polarization and a realistic choice of
the Rabi frequency of about $30\,$MHz. The shading of the colored lines in (a)
and (b) is chosen proportional to the laser coupling strength. (c) Resulting
dressed Ising interactions in the electronic ground state for a laser red-
detuned by 4 MHz with respect to the single-atom resonance and 4.4 MHz blue-
detuned to the lower of the microwave-shifted states. The laser Rabi frequency
has been set to 2 MHz.

Here we show, for the example of 39K atoms, that this difficulty can be
overcome, and sign inversion of the Ising interactions can be implemented, by
strong microwave coupling of the van der Waals pair-potential curve to a
dipolar potential curve. The blue line in Fig. 4(a) shows the interaction
potential between pairs of atoms in the $\ket{50S_{1/2},m_{F}=1/2}$ state,
where the zero-energy level is chosen to coincide with the laser with the
laser-targeted energy. When switching on microwave radiation with a frequency
of 27.592 GHz, the $\ket{50S_{1/2},m_{J}=1/2}$ state is coupled to the
$\ket{50P_{1/2},m_{J}=1/2}$ state, resulting in the pair potential shown in
red in Fig. 4(b). The splitting of the two emerging potential branches at
large distances is determined by the Autler-Townes splitting of the single-
atom state. At shorter distances of around 3-4 $\mu$m, the signature of an
avoided level crossing is visible. For microwave interaction of a suitably
chosen strength, the avoided level crossing is opened up to an extent such
that the lower branch in Fig. 4(b) becomes the reflection image of the blue
line in Fig. 4(a) around the laser-targeted energy. This property of one pair
potential being the reflection image of another then gets imprinted onto the
corresponding Ising interactions, as illustrated in Fig. 4(c). These results
were obtained with the “pairinteraction” software [52], which diagonalizes the
two-atom Hamiltonian, including magnetic fields and dipolar interactions. We
extended the software to also include the effect of microwave coupling in the
diagonalization. Figure 4(c) illustrates that, by merely switching on or off
the microwave-induced coupling, the sign of the Ising interaction is inverted,
and hence backward time evolution can be realized. The Rydberg dressing
approach discussed here has the advantageous feature that the atoms remain
trapped in the optical tweezers during the entire sequence, and that forces
between the atoms remain small. This avoids decoherence due to uncontrolled
coupling to motional degrees of freedom, which would corrupt time reversal.

Summary and outlook.—The results presented in this Letter lay out a path
towards measuring OTOCs for arbitrary many-body qubit systems and initial
states. Unlike other measurement protocols of that generality, our proposal
requires neither randomized measurements nor the use of ancilla degrees of
freedom. In our protocol, real and imaginary parts of the OTOC are measured
separately, both requiring local control (single-site measurements and single-
site rotations, respectively) in the experiment. In addition, coherent
forward- as well as backward-in-time evolution are needed.

We demonstrate the feasibility of the proposed measurement protocol for
Rydberg-dressed atoms in optical tweezers. While single-site measurements and
rotations are readily available in this platform, Hamiltonian sign inversion,
which facilitates backward-in-time evolution, has hitherto been missing. We
introduced a method that facilitates sign inversion through microwave-assisted
Rydberg dressing, thus completing the toolset for successfully implementing
our OTOC measurement protocol in arrays of Rydberg atoms. This paves the way
for experimental explorations of equilibrium and nonequilibrium situations
through OTOCs in these platforms, including the detection of quantum chaos
[53, *GonzalezAlonso_etal], the monitoring of thermalization and the
scrambling of quantum information [10, 11, *Chen_etal17, 40], or more exotic
tasks like the probing of excited-state quantum phase transitions [55]. We
expect our protocol to become applicable in other many-body qubit systems or
analog quantum simulators of spin-$1/2$ Hamiltonians in the near future.

Note added: Upon completion of this Letter we became aware of Ref. [56], in
which sign inversion in a bulk Rydberg gas implementing the dipolar XXZ model
was demonstrated.

###### Acknowledgements.

We acknowledge funding from the Deutsche Forschungsgemeinschaft via projects
GR 4741/4-1, SPP 1929 GiRyd (GR 4741/5-1) and FOR 5413 (GR 4741/6-1), a
Heisenberg professorship (GR 4741/3-1 and GR 4741/7-1) and from the Alfried
Krupp von Bohlen und Halbach foundation.

##  Appendix A Proof of Eq. (4)

Denote by $\Pi_{i}^{\pm_{a}}$ the projector onto the $\pm$-eigenstate of the
Pauli operator $\sigma_{i}^{a}$.

In the course of the protocol (i)–(viii) the system state goes through the
following stages:

  * (i)

Initial state $\rho$.

  * (ii)

After the first measurement, and depending on the outcome $\pm$ of the
measurement, the state is

$\rho_{1}^{\pm}=\Pi_{j}^{\pm_{b}}\rho\Pi_{j}^{\pm_{b}}/P_{\pm},$ (7)

where

$P_{\pm}=\operatorname{{Tr}}\left(\rho\Pi_{j}^{\pm_{b}}\right)$ (8)

is the probability of measuring $+$ or $-$.

  * (iv)

After the second measurement, and depending on the outcome $\pm$ of the first
measurement (ii) and the outcome $\pm$ of the second measurement (iv), the
state is

$\rho_{2}^{\pm\pm}=\Pi_{i}^{\pm_{a}}e^{-iHt}\rho_{1}^{\pm}e^{iHt}\Pi_{i}^{\pm_{a}}/P_{\pm|\pm},$
(9)

where

$P_{\pm|\pm}=\operatorname{{Tr}}\left(e^{-iHt}\rho_{1}^{\pm}e^{iHt}\Pi_{i}^{\pm_{a}}\right)$
(10)

is the conditional probability of measuring $\pm$ in the second measurement
after having measured $\pm$ in the first measurement.

  * (vi)

Similarly one obtains

$\rho_{3}^{\pm\pm\pm}=\Pi_{j}^{\pm_{b}}e^{iHt}\rho_{2}^{\pm\pm}e^{-iHt}\Pi_{j}^{\pm_{b}}/P_{\pm|\pm\pm}$
(11)

with

$P_{\pm|\pm\pm}=\operatorname{{Tr}}\left(e^{iHt}\rho_{2}^{\pm\pm}e^{-iHt}\Pi_{j}^{\pm_{b}}\right)$
(12)

after the third measurement.

  * (viii)

And

$\rho_{4}^{\pm\pm\pm\pm}=\Pi_{i}^{\pm_{a}}e^{-iHt}\rho_{3}^{\pm\pm\pm}e^{iHt}\Pi_{i}^{\pm_{a}}/P_{\pm|\pm\pm\pm}$
(13)

with

$P_{\pm|\pm\pm\pm}=\operatorname{{Tr}}\left(e^{-iHt}\rho_{3}^{\pm\pm\pm}e^{iHt}\Pi_{i}^{\pm_{a}}\right)$
(14)

after the fourth measurement.

The probability of finding a specific sequence of the four measurement
outcomes $\pm$ is then given by

$P_{\pm\pm\pm\pm}=P_{\pm}P_{\pm|\pm}P_{\pm|\pm\pm}P_{\pm|\pm\pm\pm}.$ (15)

Inserting Eqs. (7)–(15) into the correlation function (3), the latter can be
written as

$\mathscr{C}(t)=\sum_{o_{1},o_{2},o_{3},o_{4}\in\\{-,+\\}}o_{1}o_{2}o_{3}o_{4}\\\
\times\operatorname{{Tr}}\left[\Pi_{i}^{o_{4}}(t)\Pi_{j}^{o_{3}}\Pi_{i}^{o_{2}}(t)\Pi_{j}^{o_{1}}\rho\Pi_{j}^{o_{1}}\Pi_{i}^{o_{2}}(t)\Pi_{j}^{o_{3}}\right],$
(16)

where $\Pi_{i}^{o}(t):=e^{iHt}\Pi_{i}^{o}e^{-iHt}$. Making use of the spectral
representation

$\sigma_{i}^{a}=\Pi_{i}^{+_{a}}-\Pi_{i}^{-_{a}}=\sum_{o_{4}\in\\{-,+\\}}o_{4}\Pi_{i}^{o_{4}}$
(17)

as well as the linearity of the trace, one obtains

$\mathscr{C}(t)=\sum_{o_{1},o_{2},o_{3}\in\\{-,+\\}}o_{1}o_{2}o_{3}\\\
\times\operatorname{{Tr}}\left[\sigma_{i}^{a}(t)\Pi_{j}^{o_{3}}\Pi_{i}^{o_{2}}(t)\Pi_{j}^{o_{1}}\rho\Pi_{j}^{o_{1}}\Pi_{i}^{o_{2}}(t)\Pi_{j}^{o_{3}}\right].$
(18)

Using the completeness relation
$\Pi_{j}^{o_{3}}={\mathbbm{1}}_{j}-\Pi_{j}^{-o_{3}}$ on the second occurrence
of $\Pi_{j}^{o_{3}}$ in (18), $\mathscr{C}$ can be rewritten as

$\mathscr{C}(t)=\sum_{o_{1},o_{2}\in\\{-,+\\}}o_{1}o_{2}\\\
\times\operatorname{{Tr}}\left[\sigma_{i}^{a}(t)\left(\sum_{o_{3}\in\\{-,+\\}}o_{3}\Pi_{j}^{o_{3}}\right)\Pi_{i}^{o_{2}}(t)\Pi_{j}^{o_{1}}\rho\Pi_{j}^{o_{1}}\Pi_{i}^{o_{2}}(t)\right]\\\
-\sum_{o_{1},o_{2},o_{3}\in\\{-,+\\}}o_{1}o_{2}o_{3}\\\
\times\operatorname{{Tr}}\left[\sigma_{i}^{a}(t)\Pi_{j}^{o_{3}}\Pi_{i}^{o_{2}}(t)\Pi_{j}^{o_{1}}\rho\Pi_{j}^{o_{1}}\Pi_{i}^{o_{2}}(t)\Pi_{j}^{-o_{3}}\right].$
(19)

The second line of (19) can be simplified by recognizing that the term in
round brackets is the spectral representation of
$\sigma_{j}^{b}=\Pi_{j}^{+_{b}}-\Pi_{j}^{-_{b}}$. Writing out the remaining
$o_{3}$-sum in the bottom two lines of (19) and using the cyclic invariance of
the trace, one obtains

$\mathscr{C}(t)=\sum_{o_{1},o_{2}\in\\{-,+\\}}o_{1}o_{2}\\\
\times\biggl{(}\operatorname{{Tr}}\left[\sigma_{i}^{a}(t)\sigma_{j}^{b}\Pi_{i}^{o_{2}}(t)\Pi_{j}^{o_{1}}\rho\Pi_{j}^{o_{1}}\Pi_{i}^{o_{2}}(t)\right]\\\
-\operatorname{{Tr}}\left[\sigma_{i}^{a}(t)\Pi_{j}^{+_{b}}\Pi_{i}^{o_{2}}(t)\Pi_{j}^{o_{1}}\rho\Pi_{j}^{o_{1}}\Pi_{i}^{o_{2}}(t)\Pi_{j}^{-_{b}}\right]\\\
+\operatorname{{Tr}}\left[\Pi_{j}^{-_{b}}\Pi_{i}^{o_{2}}(t)\Pi_{j}^{o_{1}}\rho\Pi_{j}^{o_{1}}\Pi_{i}^{o_{2}}(t)\Pi_{j}^{+_{b}}\sigma_{i}^{a}(t)\right]\biggr{)}.$
(20)

The operator products in the second and third trace in Eq. (20) are Hermitian
conjugates of each other. Hence, the difference of the traces can be expressed
as an imaginary part, yielding

$\mathscr{C}(t)=2i\operatorname{\mathrm{Im}}c_{3}+\sum_{o_{1},o_{2}\in\\{-,+\\}}o_{1}o_{2}\\\
\times\operatorname{{Tr}}\left[\sigma_{i}^{a}(t)\sigma_{j}^{b}\Pi_{i}^{o_{2}}(t)\Pi_{j}^{o_{1}}\rho\Pi_{j}^{o_{1}}\Pi_{i}^{o_{2}}(t)\right]$
(21)

with

$c_{3}=\sum_{o_{1},o_{2}\in\\{-,+\\}}o_{1}o_{2}\\\
\times\operatorname{{Tr}}\left[\Pi_{j}^{-_{b}}\Pi_{i}^{o_{2}}(t)\Pi_{j}^{o_{1}}\rho\Pi_{j}^{o_{1}}\Pi_{i}^{o_{2}}(t)\Pi_{j}^{+_{b}}\sigma_{i}^{a}(t)\right].$
(22)

Next we apply the completeness relation
$\Pi_{i}^{o_{2}}={\mathbbm{1}}_{j}-\Pi_{i}^{-o_{2}}$ and the corresponding
spectral representation to the first occurrence of $\Pi_{i}^{o_{2}}$ in Eq.
(21), which yields

$\mathscr{C}(t)=2i\operatorname{\mathrm{Im}}c_{3}+\sum_{o_{1}\in\\{-,+\\}}o_{1}\operatorname{{Tr}}\left[\sigma_{j}^{b}\Pi_{j}^{o_{1}}\rho\Pi_{j}^{o_{1}}\right]\\\
-\sum_{o_{1},o_{2}\in\\{-,+\\}}o_{1}o_{2}\operatorname{{Tr}}\left[\sigma_{i}^{a}(t)\sigma_{j}^{b}\Pi_{i}^{-o_{2}}(t)\Pi_{j}^{o_{1}}\rho\Pi_{j}^{o_{1}}\Pi_{i}^{o_{2}}(t)\right].$
(23)

Applying the same completeness relation and spectral representation to the
second occurrence of $\Pi_{i}^{o_{2}}$ in Eq. (21), one obtains

$\mathscr{C}(t)=2i\operatorname{\mathrm{Im}}c_{3}+\sum_{o_{1}\in\\{-,+\\}}o_{1}\operatorname{{Tr}}\left[\sigma_{i}^{a}(t)\sigma_{j}^{b}\sigma_{i}^{a}(t)\Pi_{j}^{o_{1}}\rho\Pi_{j}^{o_{1}}\right]\\\
+\sum_{o_{1},o_{2}\in\\{-,+\\}}o_{1}o_{2}\operatorname{{Tr}}\left[\sigma_{i}^{a}(t)\sigma_{j}^{b}\Pi_{i}^{-o_{2}}(t)\Pi_{j}^{o_{1}}\rho\Pi_{j}^{o_{1}}\Pi_{i}^{o_{2}}(t)\right].$
(24)

Summing Eqs. (23) and (24) gives

$2\mathscr{C}(t)=4i\operatorname{\mathrm{Im}}c_{3}+\sum_{o_{1}\in\\{-,+\\}}o_{1}\operatorname{{Tr}}\left[\sigma_{j}^{b}\Pi_{j}^{o_{1}}\rho\Pi_{j}^{o_{1}}\right]\\\
+\sum_{o_{1}\in\\{-,+\\}}o_{1}\operatorname{{Tr}}\left[\sigma_{i}^{a}(t)\sigma_{j}^{b}\sigma_{i}^{a}(t)\Pi_{j}^{o_{1}}\rho\Pi_{j}^{o_{1}}\right].$
(25)

Similarly, by applying the completeness relation
$\Pi_{j}^{o_{1}}={\mathbbm{1}}_{j}-\Pi_{j}^{-o_{1}}$ and the corresponding
spectral representation to the second occurrences of $\Pi_{j}^{o_{1}}$ in the
first as well as the second trace of Eq. (25), one arrives at

$2\mathscr{C}(t)=2i\operatorname{\mathrm{Im}}\left(c_{2}+2c_{3}\right)+C(t)+1$
(26)

with

$c_{2}=\sum_{o_{1}\in\\{-,+\\}}o_{1}\operatorname{{Tr}}\left[\Pi_{j}^{-_{b}}\rho\Pi_{j}^{+_{b}}\sigma_{i}^{a}(t)\sigma_{j}^{b}\sigma_{i}^{a}(t)\right].$
(27)

The first term on the right-hand side of (26) is purely imaginary, whereas
$\mathscr{C}$ is real by definition (3). Hence, by taking the real part on
both sides of the Eq. (26) one arrives at Eq. (4).

##  Appendix B Proof of Eq. (6)

Spin rotations at the lattice site $i$ around the $a$-axis by an angle
$\theta$ are described by the unitary rotation operator

$R_{i}^{a}(\theta)=\exp\left(-i\sigma_{i}^{a}\theta/2\right)\equiv\cos(\theta/2)-i\sin(\theta/2)\sigma_{i}^{a}.$
(28)

After step (vii’) of the rotation protocol the system is in the state

$\mathscr{R}(t,\theta_{1},\theta_{2},\theta_{3})\,\rho\,\mathscr{R}(t,\theta_{1},\theta_{2},\theta_{3})^{\dagger}$
(29)

with

$\mathscr{R}(t,\theta_{1},\theta_{2},\theta_{3}):=e^{-iHt}R_{j}^{b}(\theta_{3})e^{iHt}R_{i}^{a}(\theta_{2})e^{-iHt}R_{j}^{b}(\theta_{1}).$
(30)

Using this expression to calculate the expectation values of $\sigma_{i}^{a}$
on the left-hand side of Eq. (6) results in a lengthy expression with numerous
combinations of sine and cosine terms. Simplifying these terms, either by hand
in a tedious calculation or quickly using Mathematica, establishes the
validity of Eq. (6). This calculation makes repeated use of the involution
$(\sigma_{i}^{a})^{2}={\mathbbm{1}}$, which is an indication that the
measurement protocol is unlike to hold beyond bivariate observables.

## References

  * Sekino and Susskind [2008] Y. Sekino and L. Susskind, Fast scramblers, J. High Energy Phys. 2008, 065.
  * Shenker and Stanford [2014] S. H. Shenker and D. Stanford, Black holes and the butterfly effect, J. High Energy Phys. 2014, 067.
  * Deutsch [1991] J. M. Deutsch, Quantum statistical mechanics in a closed system, Phys. Rev. A 43, 2046 (1991).
  * Srednicki [1994] M. Srednicki, Chaos and quantum thermalization, Phys. Rev. E 50, 888 (1994).
  * Gogolin and Eisert [2016] C. Gogolin and J. Eisert, Equilibration, thermalisation, and the emergence of statistical mechanics in closed quantum systems, Rep. Prog. Phys. 79, 056001 (2016).
  * Maldacena  _et al._ [2016] J. Maldacena, S. H. Shenker, and D. Stanford, A bound on chaos, J. High Energy Phys. 2016, 106.
  * Note [1] For unitary operators $V$ and $W$ satisfying $[W,V]=0$, a short calculation yields $\operatorname{\mathrm{Re}}[F(t)]=1-\left\langle\lvert[W(t),V]\rvert^{2}\right\rangle/2$.
  * Larkin and Ovchinnikov [1969] A. I. Larkin and Y. N. Ovchinnikov, Quasiclassical method in the theory of superconductivity, J. Exp. Theor. Phys. 28, 1200 (1969).
  * Hosur  _et al._ [2016] P. Hosur, X.-L. Qi, D. A. Roberts, and B. Yoshida, Chaos in quantum channels, J. High Energy Phys. 2016, 4.
  * Fan  _et al._ [2017] R. Fan, P. Zhang, H. Shen, and H. Zhai, Out-of-time-order correlation for many-body localization, Sci. Bull. 62, 707 (2017).
  * Huang  _et al._ [2017] Y. Huang, Y.-L. Zhang, and X. Chen, Out-of-time-ordered correlators in many-body localized systems, Ann. Phys. (Berl.) 529, 1600318 (2017).
  * Chen  _et al._ [2017] X. Chen, T. Zhou, D. A. Huse, and E. Fradkin, Out-of-time-order correlations in many-body localized and thermal phases, Ann. Phys. (Berl.) 529, 1600332 (2017).
  * Braun  _et al._ [2013] S. Braun, J. P. Ronzheimer, M. Schreiber, S. S. Hodgman, T. Rom, I. Bloch, and U. Schneider, Negative absolute temperature for motional degrees of freedom, Science 339, 52 (2013).
  * Linnemann  _et al._ [2016] D. Linnemann, H. Strobel, W. Muessel, J. Schulz, R. J. Lewis-Swan, K. V. Kheruntsyan, and M. K. Oberthaler, Quantum-enhanced sensing based on time reversal of nonlinear dynamics, Phys. Rev. Lett. 117, 013001 (2016).
  * Gilmore  _et al._ [2021] K. A. Gilmore, M. Affolter, R. J. Lewis-Swan, D. Barberena, E. Jordan, A. M. Rey, and J. J. Bollinger, Quantum-enhanced sensing of displacements and electric fields with two-dimensional trapped-ion crystals, Science 373, 673 (2021).
  * Colombo  _et al._ [2022] S. Colombo, E. Pedrozo-Peñafiel, A. F. Adiyatullin, Z. Li, E. Mendez, C. Shu, and V. Vuletić, Time-reversal-based quantum metrology with many-body entangled states, Nat. Phys. 18, 925 (2022).
  * Vermersch  _et al._ [2019] B. Vermersch, A. Elben, L. M. Sieberer, N. Y. Yao, and P. Zoller, Probing scrambling using statistical correlations between randomized measurements, Phys. Rev. X 9, 021061 (2019).
  * Blocher  _et al._ [2022] P. D. Blocher, S. Asaad, V. Mourik, M. A. I. Johnson, A. Morello, and K. Mølmer, Measuring out-of-time-ordered correlation functions without reversing time evolution, Phys. Rev. A 106, 042429 (2022).
  * Li  _et al._ [2017a] J. Li, R. Fan, H. Wang, B. Ye, B. Zeng, H. Zhai, X. Peng, and J. Du, Measuring Out-of-Time-Order Correlators on a Nuclear Magnetic Resonance Quantum Simulator, Phys. Rev. X 7, 031011 (2017a).
  * Wei  _et al._ [2018] K. X. Wei, C. Ramanathan, and P. Cappellaro, Exploring Localization in Nuclear Spin Chains, Phys. Rev. Lett. 120, 070501 (2018).
  * Landsman  _et al._ [2019] K. A. Landsman, C. Figgatt, T. Schuster, N. M. Linke, B. Yoshida, N. Y. Yao, and C. Monroe, Verified quantum information scrambling, Nature 567, 61 (2019).
  * Nie  _et al._ [2020] X. Nie, B.-B. Wei, X. Chen, Z. Zhang, X. Zhao, C. Qiu, Y. Tian, Y. Ji, T. Xin, D. Lu, and J. Li, Experimental Observation of Equilibrium and Dynamical Quantum Phase Transitions via Out-of-Time-Ordered Correlators, Phys. Rev. Lett. 124, 250601 (2020).
  * Chen  _et al._ [2020] B. Chen, X. Hou, F. Zhou, P. Qian, H. Shen, and N. Xu, Detecting the out-of-time-order correlations of dynamical quantum phase transitions in a solid-state quantum simulator, Appl. Phys. Lett. 116, 194002 (2020).
  * Joshi  _et al._ [2020] M. K. Joshi, A. Elben, B. Vermersch, T. Brydges, C. Maier, P. Zoller, R. Blatt, and C. F. Roos, Quantum Information Scrambling in a Trapped-Ion Quantum Simulator with Tunable Range Interactions, Phys. Rev. Lett. 124, 240505 (2020).
  * Swingle  _et al._ [2016] B. Swingle, G. Bentsen, M. Schleier-Smith, and P. Hayden, Measuring the scrambling of quantum information, Phys. Rev. A 94, 040302 (2016).
  * García-Álvarez  _et al._ [2017] L. García-Álvarez, I. L. Egusquiza, L. Lamata, A. del Campo, J. Sonner, and E. Solano, Digital quantum simulation of minimal $\mathrm{AdS}/\mathrm{CFT}$, Phys. Rev. Lett. 119, 040501 (2017).
  * Sundar  _et al._ [2022] B. Sundar, A. Elben, L. K. Joshi, and T. V. Zache, Proposal for measuring out-of-time-ordered correlators at finite temperature with coupled spin chains, New J. Phys. 24, 023037 (2022).
  * Gärttner  _et al._ [2017] M. Gärttner, J. G. Bohnet, A. Safavi-Naini, M. L. Wall, J. J. Bollinger, and A. M. Rey, Measuring out-of-time-order correlations and multiple quantum spectra in a trapped-ion quantum magnet, Nat. Phys. 13, 781–786 (2017).
  * Li  _et al._ [2017b] J. Li, R. Fan, H. Wang, B. Ye, B. Zeng, H. Zhai, X. Peng, and J. Du, Measuring out-of-time-order correlators on a nuclear magnetic resonance quantum simulator, Phys. Rev. X 7, 031011 (2017b).
  * Braumüller  _et al._ [2022] J. Braumüller, A. H. Karamlou, Y. Yanay, B. Kannan, D. Kim, M. Kjaergaard, A. Melville, B. M. Niedzielski, Y. Sung, A. Vepsäläinen, R. Winik, J. L. Yoder, T. P. Orlando, S. Gustavsson, C. Tahan, and W. D. Oliver, Probing quantum information propagation with out-of-time-ordered correlators, Nat. Phys. 18, 172 (2022).
  * Mi  _et al._ [2021] X. Mi, P. Roushan, C. Quintana, S. Mandrà, J. Marshall, C. Neill, F. Arute, K. Arya, J. Atalaya, R. Babbush, J. C. Bardin, R. Barends, J. Basso, A. Bengtsson, S. Boixo, A. Bourassa, M. Broughton, B. B. Buckley, D. A. Buell, B. Burkett, N. Bushnell, Z. Chen, B. Chiaro, R. Collins, W. Courtney, S. Demura, A. R. Derk, A. Dunsworth, D. Eppens, C. Erickson, E. Farhi, A. G. Fowler, B. Foxen, C. Gidney, M. Giustina, J. A. Gross, M. P. Harrigan, S. D. Harrington, J. Hilton, A. Ho, S. Hong, T. Huang, W. J. Huggins, L. B. Ioffe, S. V. Isakov, E. Jeffrey, Z. Jiang, C. Jones, D. Kafri, J. Kelly, S. Kim, A. Kitaev, P. V. Klimov, A. N. Korotkov, F. Kostritsa, D. Landhuis, P. Laptev, E. Lucero, O. Martin, J. R. McClean, T. McCourt, M. McEwen, A. Megrant, K. C. Miao, M. Mohseni, S. Montazeri, W. Mruczkiewicz, J. Mutus, O. Naaman, M. Neeley, M. Newman, M. Y. Niu, T. E. O’Brien, A. Opremcak, E. Ostby, B. Pato, A. Petukhov, N. Redd, N. C. Rubin, D. Sank, K. J. Satzinger, V. Shvarts, D. Strain, M. Szalay, M. D. Trevithick, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, I. Aleiner, K. Kechedzhi, V. Smelyanskiy, and Y. Chen, Information scrambling in quantum circuits, Science 374, 1479 (2021).
  * Sevinçli and Pohl [2014] S. Sevinçli and T. Pohl, Microwave control of Rydberg atom interactions, New J. Phys. 16, 123036 (2014).
  * Petrosyan and Mølmer [2014] D. Petrosyan and K. Mølmer, Binding potentials and interaction gates between microwave-dressed Rydberg atoms, Phys. Rev. Lett. 113, 123003 (2014).
  * van Bijnen and Pohl [2015] R. M. W. van Bijnen and T. Pohl, Quantum magnetism and topological ordering via Rydberg dressing near Förster resonances, Phys. Rev. Lett. 114, 243002 (2015).
  * Lu  _et al._ [2021] S. Lu, M. C. Bañuls, and J. I. Cirac, Algorithms for Quantum Simulation at Finite Energies, PRX Quantum 2, 020321 (2021).
  * Davis  _et al._ [2016] E. Davis, G. Bentsen, and M. Schleier-Smith, Approaching the Heisenberg limit without single-particle detection, Phys. Rev. Lett. 116, 053601 (2016).
  * Fröwis  _et al._ [2016] F. Fröwis, P. Sekatski, and W. Dür, Detecting Large Quantum Fisher Information with Finite Measurement Precision, Phys. Rev. Lett. 116, 090801 (2016).
  * Macrì  _et al._ [2016] T. Macrì, A. Smerzi, and L. Pezzè, Loschmidt echo for quantum metrology, Phys. Rev. A 94, 010102 (2016).
  * Note [2] This strategy has been employed in a different context in Ref. [57].
  * Sajjan  _et al._ [2023] M. Sajjan, V. Singh, R. Selvarajan, and S. Kais, Imaginary components of out-of-time-order correlator and information scrambling for navigating the learning landscape of a quantum machine learning model, Phys. Rev. Res. 5, 013146 (2023).
  * Browaeys and Lahaye [2020] A. Browaeys and T. Lahaye, Many-body physics with individually controlled Rydberg atoms, Nat. Phys. 16, 132 (2020).
  * Graham  _et al._ [2022] T. M. Graham, Y. Song, J. Scott, C. Poole, L. Phuttitarn, K. Jooya, P. Eichler, X. Jiang, A. Marra, B. Grinkemeyer, M. Kwon, M. Ebert, J. Cherek, M. T. Lichtman, M. Gillette, J. Gilbert, D. Bowman, T. Ballance, C. Campbell, E. D. Dahl, O. Crawford, N. S. Blunt, B. Rogers, T. Noel, and M. Saffman, Multi-qubit entanglement and algorithms on a neutral-atom quantum computer, Nature 604, 457 (2022).
  * Bluvstein  _et al._ [2023] D. Bluvstein, S. J. Evered, A. A. Geim, S. H. Li, H. Zhou, T. Manovitz, S. Ebadi, M. Cain, M. Kalinowski, D. Hangleiter, J. P. B. Ataides, N. Maskara, I. Cong, X. Gao, P. S. Rodriguez, T. Karolyshyn, G. Semeghini, M. J. Gullans, M. Greiner, V. Vuletić, and M. D. Lukin, Logical quantum processor based on reconfigurable atom arrays, Nature 626, 58 (2023).
  * Gil  _et al._ [2014] L. I. R. Gil, R. Mukherjee, E. M. Bridge, M. P. A. Jones, and T. Pohl, Spin squeezing in a Rydberg lattice clock, Phys. Rev. Lett. 112, 103601 (2014).
  * Jau  _et al._ [2016] Y.-Y. Jau, A. M. Hankin, T. Keating, I. H. Deutsch, and G. W. Biedermann, Entangling atomic spins with a Rydberg-dressed spin-flip blockade, Nat. Phys. 12, 71 (2016).
  * Zeiher  _et al._ [2016] J. Zeiher, R. van Bijnen, P. Schauß, S. Hild, J.-y. Choi, T. Pohl, I. Bloch, and C. Gross, Many-body interferometry of a Rydberg-dressed spin lattice, Nat. Phys. 12, 1095 (2016).
  * Zeiher  _et al._ [2017] J. Zeiher, J.-y. Choi, A. Rubio-Abadal, T. Pohl, R. van Bijnen, I. Bloch, and C. Gross, Coherent many-body spin dynamics in a long-range interacting Ising chain, Phys. Rev. X 7, 041063 (2017).
  * Guardado-Sanchez  _et al._ [2021] E. Guardado-Sanchez, B. M. Spar, P. Schauss, R. Belyansky, J. T. Young, P. Bienias, A. V. Gorshkov, T. Iadecola, and W. S. Bakr, Quench Dynamics of a Fermi Gas with Strong Nonlocal Interactions, Phys. Rev. X 11, 021036 (2021).
  * Hollerith  _et al._ [2022] S. Hollerith, K. Srakaew, D. Wei, A. Rubio-Abadal, D. Adler, P. Weckesser, A. Kruckenhauser, V. Walther, R. van Bijnen, J. Rui, C. Gross, I. Bloch, and J. Zeiher, Realizing Distance-Selective Interactions in a Rydberg-Dressed Atom Array, Phys. Rev. Lett. 128, 113602 (2022).
  * Steinert  _et al._ [2023] L.-M. Steinert, P. Osterholz, R. Eberhard, L. Festa, N. Lorenz, Z. Chen, A. Trautmann, and C. Gross, Spatially Tunable Spin Interactions in Neutral Atom Arrays, Phys. Rev. Lett. 130, 243001 (2023).
  * Eckner  _et al._ [2023] W. J. Eckner, N. Darkwah Oppong, A. Cao, A. W. Young, W. R. Milner, J. M. Robinson, J. Ye, and A. M. Kaufman, Realizing spin squeezing with Rydberg interactions in an optical clock, Nature 621, 734 (2023).
  * Weber  _et al._ [2017] S. Weber, C. Tresp, H. Menke, A. Urvoy, O. Firstenberg, H. P. Büchler, and S. Hofferberth, Calculation of Rydberg interaction potentials, J. Phys. B: At. Mol. Opt. Phys. 50, 133001 (2017).
  * García-Mata  _et al._ [2023] I. García-Mata, R. A. Jalabert, and D. A. Wisniacki, Out-of-time-order correlations and quantum chaos, Scholarpedia 18, 55237 (2023).
  * González Alonso  _et al._ [2022] J. R. González Alonso, N. Shammah, S. Ahmed, F. Nori, and J. Dressel, Diagnosing quantum chaos with out-of-time-ordered-correlator quasiprobability in the kicked-top model (2022), arXiv:2201.08175 .
  * Wang and Pérez-Bernal [2019] Q. Wang and F. Pérez-Bernal, Probing an excited-state quantum phase transition in a quantum many-body system via an out-of-time-order correlator, Phys. Rev. A 100, 062113 (2019).
  * Geier  _et al._ [2024] S. Geier, A. Braemer, E. Braun, M. Müllenbach, T. Franz, M. Gärttner, G. Zürn, and M. Weidemüller, Time-reversal in a dipolar quantum many-body spin system (2024), arXiv:2402.13873 .
  * Uhrich  _et al._ [2017] P. Uhrich, S. Castrignano, H. Uys, and M. Kastner, Noninvasive measurement of dynamic correlation functions, Phys. Rev. A 96, 022127 (2017).