# Monte Carlo Tree Search for Interpreting Stress in Natural Language

Kyle Swanson⋆, Joy Hsu⋆, Mirac Suzgun⋆
Department of Computer Science
Stanford University
{swansonk, joycj<EMAIL_ADDRESS>

###### Abstract

Natural language processing can facilitate the analysis of a person’s mental
state from text they have written. Previous studies have developed models that
can predict whether a person is experiencing a mental health condition from
social media posts with high accuracy. Yet, these models cannot explain why
the person is experiencing a particular mental state. In this work, we present
a new method for explaining a person’s mental state from text using Monte
Carlo tree search (MCTS). Our MCTS algorithm employs trained classification
models to guide the search for key phrases that explain the writer’s mental
state in a concise, interpretable manner. Furthermore, our algorithm can find
both explanations that depend on the particular context of the text (e.g., a
recent breakup) and those that are context-independent. Using a dataset of
Reddit posts that exhibit stress, we demonstrate the ability of our MCTS
algorithm to identify interpretable explanations for a person’s feeling of
stress in both a context-dependent and context-independent manner.††⋆Denotes
equal contribution.111Code and models are available at
https://github.com/swansonk14/MCTS_Interpretability.

##  1 Introduction

Disabilities associated with mental health conditions pose a significant
challenge for many people around the world Stauder et al. (2010); De Choudhury
et al. (2013); Chen et al. (2018). To help people suffering from these
conditions, it is crucial to identify those who are experiencing a mental
health condition and understand the underlying causes.

Natural language processing (NLP) can help by analyzing a person’s mental
state based on the text they have written. Previous studies Turcan and McKeown
(2019); Demszky et al. (2020); Gjurković et al. (2020); Ansari et al. (2021)
have demonstrated the ability of NLP models to process social media posts and
predict stress, depression, and a range of emotions. These methods, however,
are not able to explain why the person might be feeling the way they are, even
if that information is clearly contained in the text analyzed by the model.

In this work, we seek to explain the underlying causes of a person’s mental
state from their writing. We formulate such an explanation as a small set of
phrases from the text that is sufficient to explain the person’s mental state.
We wish to identify two complementary types of explanations: those that are
particular to the situation the person is in, which we call _context-
dependent_ , and those that could appear across different contexts, which we
call _context-independent_. Figure 1 shows an illustrating example.
Identifying both types of explanations not only enhances our understanding of
the underlying sources of a person’s mental state but also provides insights
into how one’s mental state can be affected by general and specific causes.

r/Relationships: I can’t believe this. My boyfriend just cheated on me and
then he bragged about it on twitter. What kind of a messed up person would do
that? I’m so angry with him and I’m sure we’re going to have a huge fight
about this when I see him tomorrow. Figure 1: A fictitious example of text
exhibiting stress in the relationships context and two explanations for that
stress. The explanation in blue is _context-dependent_ (specific to
relationships) while the explanation in red is _context-independent_ (general
to any disagreement).

To this end, we develop a novel Monte Carlo tree search (MCTS) algorithm that
can effectively identify explanations that are either context-dependent or
context-independent by leveraging the semantic capabilities of trained NLP
models. We, both quantitatively and qualitatively, demonstrate the efficacy of
this approach to explain a person’s mental state using a dataset of Reddit
posts that exhibit stress Turcan and McKeown (2019).

##  2 Related Work

Mental Health Prediction. Previous studies have tackled the task of mental
health disability classification, using methods ranging from classical
supervised techniques such as SVMs, logistic regression, Naive Bayes, MLPs,
and decision trees to deeper models such as CNNs and GRUs Turcan and McKeown
(2019); Gjurković et al. (2020); Ansari et al. (2021); Sampath et al. (2022).
Other approaches utilize pre-trained, large language models with fine-tuning
on specific mental health datasets Ji et al. (2021); Matoševic et al. (2021);
Mauriello et al. (2021), which takes advantage of models trained on
significantly larger datasets to speed up training and increase accuracy.
Turcan and McKeown (2019) specifically focus on the task of stress prediction
in Reddit posts, and they show that large BERT-based models outperform smaller
models such as CNNs and logistic regression.

NLP Explainability. Explainability in NLP is an emerging topic of interest as
language models have become larger and more accurate at the expense of reduced
interpretability. Common methods for explainability include feature importance
reporting across lexical or latent features Danilevsky et al. (2020), model-
agnostic approaches that extract post-hoc explanations Ribeiro et al. (2016),
and analogy-based explanations Croce et al. (2019). Prior works have also
focused on rationale identification Lei et al. (2016) and text matching
rationalization Swanson et al. (2020), where models are designed to select
small, interpretable segments of text when making predictions. Attention has
also been used as a form of interpretability, but attention weights do not
always correlate with impact on the model’s prediction, potentially limiting
their usefulness Serrano and Smith (2019). In this work, we propose to use
Monte Carlo tree search Silver et al. (2016); Chaudhry and Lee (2018); Jin et
al. (2020); Albrecht et al. (2021); Yuan et al. (2021) as a post-hoc
explainability method that can be applied to any model to flexibly identify
multiple types of explanations for a model’s predictions.

##  3 The Dreaddit Dataset

The Dreaddit dataset Turcan and McKeown (2019) contains 3,553 Reddit posts
that have human-annotated binary stress labels denoting whether a given text
contains evidence of stress. Each post belongs to one of ten subreddits (e.g.,
“r/Relationships”), which we consider to be the context of the post. The posts
are split into 2,838 train posts and 715 test posts. Figures 8 and 9 (see
Appendix) show the distributions of the stress labels and subreddit categories
for the train and test sets.

##  4 Method

Figure 2: A portion of the tree of explanations searched by MCTS for an
example text. Red indicates the text that is currently included in the
explanation. The root of the tree is an explanation with a single phrase
containing all the text. Each node in the tree can be expanded by removing the
first or last token of a phrase or by removing a token in the middle of the
phrase (constrained by certain MCTS parameters). Once a minimum number of
tokens has been reached, the resulting explanation is given a reward based on
the predictions of the stress and context models.

We assume that we have access to a training corpus
$\mathcal{D}_{\text{train}}$ and a test corpus $\mathcal{D}_{\text{test}}$ to
train and evaluate our models, respectively. The training corpus,
$\mathcal{D}_{\text{train}}=(\mathbf{t}_{i},\mathbf{s}_{i},\mathbf{c}_{i})_{i\in[1,n]}$,
is a set of tuples, where each tuple contains a text
$\mathbf{t}_{i}=\\{t_{i}^{1},\cdots,t_{i}^{l_{i}}\\}\in\mathbf{T}$ consisting
of $l_{i}$ tokens, its corresponding stress indicator
$\mathbf{s}_{i}\in\mathbf{S}=\\{0,1\\}$ denoting whether $\mathbf{t}_{i}$
contains evidence of stress, and a context label $\mathbf{c}_{i}\in\mathbf{C}$
indicating the subreddit category the text belongs to. Similarly, we assume
$\mathcal{D}_{\text{test}}=(\mathbf{t}_{i},\mathbf{s}_{i},\mathbf{c}_{i})_{i\in[1,m]}$.

###  4.1 Classification of Stress and Context

We consider two types of classification tasks, namely binary stress
classification and multi-class context (subreddit) classification. We refer to
a model trained for the former task as a stress classifier, which can be
thought of as a function mapping a piece of text $\mathbf{t}\in\mathbf{T}$ to
a likelihood $p\in[0,1]$. We refer to a model trained for the latter as a
context classifier, which can be thought of as a function mapping a piece of
text $\mathbf{t}\in\mathbf{T}$ to a probability simplex
$\triangle^{|\mathbf{C}|-1}$.

We build simple stress and context prediction models using Bernoulli and
Multinomial Naive Bayes, Support Vector Machine Platt (1999), and Multilayer
Perceptron Hinton (1989). All of these models use vectors of word counts222We
use CountVectorizer from scikit-learn fit on the training set with all default
parameters. as inputs. We also build large BERT-based models by adding a
classification layer on top of the MentalRoBERTa model of Ji et al. (2021) and
then fine-tuning the model on the training set.

###  4.2 Definition of an Explanation

An interpretable explanation for a person’s stress should consist of a small
set of phrases from the full text that captures the core reasons behind the
stress discussed within the text.

Formally, for a given piece of text in the corpus $\mathbf{t}\in\mathbf{T}$
that is labeled as stressed ($\mathbf{s}=1$), we define an _explanation_ as a
set of phrases
$\mathbf{E}=\\{\mathbf{p}_{1},\mathbf{p}_{2},\dots,\mathbf{p}_{k}\\}$ where
each phrase $\mathbf{p}_{j}$ is a set of $n_{j}$ contiguous tokens in the
text, that is, $\mathbf{p}_{j}=\\{t_{l},t_{l+1},\dots,t_{l+{n_{j}}-1}\\}$ for
some $l\in\\{1,2,\dots,|\mathbf{t}|-n_{j}+1\\}$. Furthermore, the phrases must
be non-overlapping, which means that
$\mathbf{p}_{j}\cap\mathbf{p}_{j^{\prime}}=\emptyset\quad\forall j\neq
j^{\prime}\in\\{1,2,\dots,|\mathbf{E}|\\}$. In order to ensure
interpretability, the explanation $\mathbf{E}$ must satisfy three conditions.

a. Phrase count: $|\mathbf{E}|\leq N_{phrases}$, meaning the explanation must
contain at most $N_{\textrm{phrases}}$ phrases. Too many phrases would impede
interpretability.

b. Phrase length: $|\mathbf{p_{j}}|\geq N_{length}\quad\forall
j\in\\{1,2,\dots,|\mathbf{E}|\\}$, meaning each phrase must have at least
$N_{length}$ tokens, preventing phrases that are too short to carry any
meaning.

c. Proportion of tokens: $r_{min}\leq r(\mathbf{E})\leq r_{max}$ where
$r(\mathbf{E})=\frac{1}{|\mathbf{t}|}\sum_{j=1}^{|\mathbf{E}|}|\mathbf{p_{j}}|$
is the proportion of tokens in the text that are included in the explanation
and $0\leq r_{min}\leq r_{max}\leq 1$ are lower and upper bounds on the
proportion of tokens in the explanation. This constrains the overall verbosity
of the explanation to a reasonable range.

###  4.3 Context-Dependent and Independent Explanations of Stress

We are interested in identifying two specific types of explanations for
stress: one that depends on the context of the text and one that is
independent of that context. We will refer to the context-dependent
explanation as $\mathbf{E}_{dep}$ and to the context-independent explanation
as $\mathbf{E}_{ind}$.

In both cases, since the explanation must explain the stress in the text, the
stress must be evident from just the text contained in the phrases of the
explanation. We can verify this by using our stress classification model.
Specifically, we want an explanation such that the average stress prediction
across the phrases of the explanation is close to $1$. Hence for both
$\mathbf{E}_{dep}$ and $\mathbf{E}_{ind}$, we want

$S(\mathbf{E})=\frac{1}{|\mathbf{E}|}\sum_{j=1}^{|\mathbf{E}|}\texttt{stress}(\mathbf{p}_{j})\approx
1$

where $S(\mathbf{E})$ is the average stress across the phrases of the
explanation.

However, the phrases of the context-dependent explanation $\mathbf{E}_{dep}$
should indicate the context of the text while the context-independent
explanation $\mathbf{E}_{ind}$ should not. We enforce this by examining the
entropy of the predictions of our context classification model. If the phrases
of an explanation have low entropy, then the model is relatively sure of the
context; hence, that explanation is context-dependent. If the entropy is high,
then the model is unsure of the context and the explanation is context-
independent. Formally, if we define

$H(\mathbf{E})=\frac{1}{|\mathbf{E}|}\sum_{j=1}^{|\mathbf{E}|}\texttt{entropy}(\texttt{context}(\mathbf{p}_{j}))$

as the average Shannon entropy of the context predictions across phrases, we
want $H(\mathbf{E_{dep}})\approx 0$ and $H(\mathbf{E_{ind}})\approx
e_{\textrm{max}}$ where $e_{\textrm{max}}$ is the maximum entropy (viz.,
entropy of a uniform distribution over contexts).

###  4.4 Finding Explanations with MCTS

We use the MCTS framework established in Silver et al. (2016), but we modify
the search tree and the reward function to suite our purposes (see Figure 2).
Each node in the tree represents an explanation
$\mathbf{E}=\\{\mathbf{p}_{1},\mathbf{p}_{2},\dots,\mathbf{p}_{k}\\}$. The
root of the tree represents the whole text piece as a single phrase, i.e.,
$\mathbf{E}_{root}=\\{\mathbf{t}\\}$. When the search is at a given node in
the tree, there are two options for expanding the next node: (i) remove the
first or last token in any phrase, as long as the shortened phrase still
contains at least $N_{length}$ tokens, or (ii) remove a token in the middle of
a phrase, thus breaking it into two phrases, as long as both resulting phrases
have at least $N_{length}$ tokens and the total number of phrases does not
exceed $N_{phrases}$.

The search continues to expand nodes in the tree until either the current node
cannot be expanded using either of the two rules above or the explanation at
the current node contains too few tokens, i.e., $r(\mathbf{E})\leq r_{min}$.
This node serves as a leaf node and is given a reward equal to

$R(\mathbf{E})=S(\mathbf{E})+I\cdot\alpha\cdot H(\mathbf{E})$

for some $I\in\\{-1,+1\\}$ and $\alpha\geq 0$. We use $I=+1$ to select for
high entropy (context-independent) explanations and $I=-1$ to select for low
entropy (context-dependent) explanations. This reward is propagated back to
all the nodes on the path from the root to this leaf node according to the
update rules from Silver et al. (2016). After the search is complete, the best
explanation $\mathbf{\hat{E}}$ is selected as

$\mathbf{\hat{E}}=\underset{\mathbf{E}}{\textrm{argmax}}\ R(\mathbf{E})\ \
\textrm{s.t.}\ r(\mathbf{E})\leq r_{max},$

which means $\mathbf{\hat{E}}$ is the explanation in the search tree that
maximizes the reward while satisfying the condition on the maximum proportion
of tokens. The other interpretability conditions are guaranteed by the rules
of the search tree expansion.

Model | Precision | Recall | F-1 | Accuracy
---|---|---|---|---
Bernoulli NB | 0.69 | 0.84 | 0.75 | 0.72
Multinomial NB | 0.68 | 0.87 | 0.76 | 0.72
SVM | 0.71 | 0.77 | 0.74 | 0.72
MLP | 0.71 | 0.74 | 0.73 | 0.71
MentalRoBERTaFT | 0.78 | 0.90 | 0.84 | 0.82

Table 1: Performances of stress classifiers on the test set of Dreaddit. While
non-neural classifiers could not surpass 72% accuracy, the MentalRoBERTaFT
model fine-tuned on the Dreaddit train set yielded 82% accuracy. Here, the
superscript FT denotes that the model was fine-tuned.

##  5 Experiments

All of our experiments were run on the Dreaddit dataset. We report results of
our stress and context classification models and share findings of our MCTS
explanation algorithm.

Model | Precision | Recall | F-1 | Accuracy
---|---|---|---|---
Bernoulli NB | 0.81 | 0.75 | 0.76 | 0.80
Multinomial NB | 0.77 | 0.75 | 0.75 | 0.79
SVM | 0.76 | 0.72 | 0.74 | 0.76
MLP | 0.78 | 0.78 | 0.78 | 0.79
MentalRoBERTaFT | 0.85 | 0.86 | 0.86 | 0.87

Table 2: Performances of context classifiers. We restricted our focus to three
subreddits: “anxiety,” “assistance,” “relationships.” The fine-tuned
MentalRoBERTaFT model yielded the best results with 87% accuracy.

###  5.1 Classification

As Table 1 illustrates, basic stress classification models, such as Naive
Bayes classifiers, SVMs, and MLPs, performed reasonably on the test set of
Dreaddit. The MentalRoBERTaFT model for stress fine-tuned on the training set
of Dreaddit for five epochs, however, was able to outperform all the other
models, achieving an accuracy score of 82% and demonstrating the efficacy of
the pre-training on mental health data333In contrast, the RoBERTa model
trained from scratch achieved an accuracy score of almost 80%.. Our results on
the stress classification task are consistent with those of Turcan and McKeown
(2019). Table 2 reports the performance of various models on the multi-class
subreddit category classification. Here, we limited our attention to three
categories, namely “anxiety,” “assistance,” and “relationships.” The Reddit
posts in these categories embody various distinct everyday, financial, and
interpersonal stress factors, but at the same time, they seem to have common
(context-independent) stress elements. In this context classification task,
all models were able to go beyond the 75% accuracy level, but MentalRoBERTaFT
yielded the highest accuracy.

###  5.2 Explainability

We demonstrate our MCTS approach to explainability using the same three
categories as above. We use stress and context classification models
implemented with Multinomial NB, MLP, and MentalRoBERTaFT. For each of these
models, we apply MCTS to identify explanations for each of the 166 test texts
that is labeled as stressed and belongs to one of our three categories. We use
the interpretability conditions $N_{phrases}=3$, $N_{length}=5$,
$r_{min}=0.2$, and $r_{max}=0.5$ for all experiments444These choices are
arbitrary and could easily be changed., and we use $\alpha=10$ except where
otherwise noted.

|  | Original | Dependent | Independent
---|---|---|---|---
MNB | S | 0.850 $\pm$ 0.317 | 0.706 $\pm$ 0.190 | 0.617 $\pm$ 0.124
E | 0.047 $\pm$ 0.140 | 0.274 $\pm$ 0.181 | 0.942 $\pm$ 0.086
MLP | S | 0.725 $\pm$ 0.383 | 0.512 $\pm$ 0.194 | 0.546 $\pm$ 0.145
E | 0.214 $\pm$ 0.274 | 0.766 $\pm$ 0.163 | 1.067 $\pm$ 0.022
MRB | S | 0.878 $\pm$ 0.324 | 0.830 $\pm$ 0.220 | 0.430 $\pm$ 0.273
E | 0.042 $\pm$ 0.124 | 0.019 $\pm$ 0.018 | 0.640 $\pm$ 0.171

Table 3: Stress (S) and context entropy (E) for original text, context-
dependent explanation, and context-independent explanation for the Multinomial
Naive Bayes (MNB), Multilayer Perceptron (MLP), and Mental RoBERTa (MRB)
models. Results were generated through MCTS with stress and context entropy
averaged over the test set. The Wilcoxon signed rank test Wilcoxon (1945)
between dependent and independent entropy is $p<0.0001$ for all models,
indicating a very significant difference as desired. Figure 3: Histogram of
stress scores for the original text and for the context-dependent and context-
independent explanations extracted by our MCTS algorithm using an MLP model.
Although stress is often higher in the original text than in the extracted
explanations, the explanations still maintain a meaningful amount of stress.
Figure 4: Histogram of context entropy for the original text and for the
context-dependent and context-independent explanations extracted by our MCTS
algorithm using an MLP model. The context-independent explanations clearly
have much higher context entropy than the context-dependent explanations as
desired.

We quantitatively evaluate the explanations produced by MCTS. In Table 3, we
show the average stress and context entropy scores of the original text and of
the context-dependent and context-independent explanations. Our method is able
to maintain a reasonably high and consistent level of stress across the
explanations while modulating the context entropy appropriately for the two
different types of explanations. This indicates that our approach can identify
both context-dependent and context-independent sources of stress.

Figures 3 and 4 further illustrate this result for the MLP model by showing
the full distribution of stress and context entropy scores across the test
examples. Figures 5, 6, and 7 in the Appendix show the stress and context
entropy distributions for all three models and for different values of
$\alpha$. Lower $\alpha$ increases stress but decreases the difference in
entropy between the two types of explanations while higher $\alpha$ decreases
stress but increases the difference in entropy. This shows the flexibility of
MCTS to select different types of explanations without retraining the
classifiers.

Furthermore, we qualitatively demonstrate our approach. Tables A.4, A.4, and
A.4 in the Appendix show examples from each of the three subreddits that
illustrate how our method captures different underlying sources of stress in
an interpretable manner.

##  6 Conclusion

We propose a novel interpretability method for explaining stress in context-
dependent and independent manners using Monte Carlo tree search. We
demonstrate the effectiveness of our method by extracting both types of
explanations from Reddit posts that exhibit stress. Although this work focuses
on stress, our MCTS-based explanation framework is extremely flexible and can
be applied to a wide variety of NLP models and prediction problems simply by
specifying the appropriate reward function and interpretability conditions for
the search tree. As in our work, the reward function can include multiple
objectives with different weights, making it possible to extract a variety of
explanations for added interpretability. Future work should further explore
the range of explanations enabled by our framework. We hope that our
explanation framework can improve understanding of the root causes of mental
health conditions as well as provide interpretability for a variety of NLP
tasks.

## Acknowledgements

We would like to thank Margalit Glasgow, Masha Karelina, Megha Patel, Biscuit
Russell, and Tayfun M. H. Mezarci for helpful comments and discussions.
Swanson and Hsu gratefully acknowledge the support of the Knight-Hennessy
Scholarship, Hsu gratefully acknowledges the support of the NSF GRFP, and
Suzgun gratefully acknowledges the support of a Johann, Thales, Williams & Co.
Graduate Fellowship. The authors also thank Dan Jurafsky for his support. The
experiments presented in this paper were run on the Stanford NLP Cluster. Any
opinions, findings, and conclusions expressed in this material are those of
the authors and do not necessarily reflect the views of Stanford University.
All errors remain our own.

## References

  * Albrecht et al. (2021) Stefano V Albrecht, Cillian Brewitt, John Wilhelm, Balint Gyevnar, Francisco Eiras, Mihai Dobre, and Subramanian Ramamoorthy. 2021.  Interpretable goal-based prediction and planning for autonomous driving.  In _2021 IEEE International Conference on Robotics and Automation (ICRA)_ , pages 1043–1049. IEEE.
  * Ansari et al. (2021) Gunjan Ansari, Muskan Garg, and Chandni Saxena. 2021.  Data augmentation for mental health classification on social media.  _arXiv preprint arXiv:2112.10064_.
  * Chaudhry and Lee (2018) Muhammad Umar Chaudhry and Jee-Hyong Lee. 2018.  Feature selection for high dimensional data using monte carlo tree search.  _IEEE Access_ , 6:76036–76048.
  * Chen et al. (2018) Xuetong Chen, Martin D Sykora, Thomas W Jackson, and Suzanne Elayan. 2018.  What about mood swings: Identifying depression on twitter with temporal measures of emotions.  In _Companion Proceedings of the The Web Conference 2018_ , pages 1653–1660.
  * Croce et al. (2019) Danilo Croce, Daniele Rossini, and Roberto Basili. 2019.  Auditing deep learning processes through kernel-based explanatory models.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 4037–4046.
  * Danilevsky et al. (2020) Marina Danilevsky, Kun Qian, Ranit Aharonov, Yannis Katsis, Ban Kawas, and Prithviraj Sen. 2020.  A survey of the state of explainable ai for natural language processing.  _arXiv preprint arXiv:2010.00711_.
  * De Choudhury et al. (2013) Munmun De Choudhury, Scott Counts, and Eric Horvitz. 2013.  Social media as a measurement tool of depression in populations.  In _Proceedings of the 5th annual ACM web science conference_ , pages 47–56.
  * Demszky et al. (2020) Dorottya Demszky, Dana Movshovitz-Attias, Jeongwoo Ko, Alan Cowen, Gaurav Nemade, and Sujith Ravi. 2020.  Goemotions: A dataset of fine-grained emotions.  _arXiv preprint arXiv:2005.00547_.
  * Gjurković et al. (2020) Matej Gjurković, Mladen Karan, Iva Vukojević, Mihaela Bošnjak, and Jan Šnajder. 2020.  Pandora talks: Personality and demographics on reddit.  _arXiv preprint arXiv:2004.04460_.
  * Hinton (1989) Geoffrey Hinton. 1989.  Connectionist learning procedures.  _Artificial intelligence_ , 40:185–234.
  * Ji et al. (2021) Shaoxiong Ji, Tianlin Zhang, Luna Ansari, Jie Fu, Prayag Tiwari, and Erik Cambria. 2021.  Mentalbert: Publicly available pretrained language models for mental healthcare.  _arXiv preprint arXiv:2110.15621_.
  * Jin et al. (2020) Wengong Jin, Regina Barzilay, and Tommi Jaakkola. 2020.  Multi-objective molecule generation using interpretable substructures.  In _International conference on machine learning_ , pages 4849–4859. PMLR.
  * Lei et al. (2016) Tao Lei, Regina Barzilay, and Tommi Jaakkola. 2016.  Rationalizing neural predictions.  _arXiv preprint arXiv:1606.04155_.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  Roberta: A robustly optimized bert pretraining approach.  _arXiv preprint arXiv:1907.11692_.
  * Matoševic et al. (2021) Lovro Matoševic, Filip Sosa, and Marko Gašparac. 2021.  Stressformers: Transfering knowledge for stress analysis in social media.  _Text Analysis and Retrieval 2021 Course Project Reports_ , page 56.
  * Mauriello et al. (2021) Matthew Louis Mauriello, Thierry Lincoln, Grace Hon, Dorien Simon, Dan Jurafsky, and Pablo Paredes. 2021.  Sad: A stress annotated dataset for recognizing everyday stressors in sms-like conversational systems.  In _Extended Abstracts of the 2021 CHI Conference on Human Factors in Computing Systems_ , pages 1–7.
  * Platt (1999) John C. Platt. 1999.  Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods.  In _ADVANCES IN LARGE MARGIN CLASSIFIERS_ , pages 61–74. MIT Press.
  * Ribeiro et al. (2016) Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. 2016.  Model-agnostic interpretability of machine learning.  _arXiv preprint arXiv:1606.05386_.
  * Sampath et al. (2022) Kayalvizhi Sampath, Thenmozhi Durairaj, Bharathi Raja Chakravarthi, and Jerin Mahibha C. 2022.  Findings of the shared task on Detecting Signs of Depression from Social Media.  In _Proceedings of the Second Workshop on Language Technology for Equality, Diversity and Inclusion_. Association for Computational Linguistics.
  * Serrano and Smith (2019) Sofia Serrano and Noah A Smith. 2019.  Is attention interpretable?  _arXiv preprint arXiv:1906.03731_.
  * Silver et al. (2016) David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. 2016.  Mastering the game of go with deep neural networks and tree search.  _nature_ , 529(7587):484–489.
  * Stauder et al. (2010) Adrienne Stauder, Barna Konkolÿ Thege, Mónika Erika Kovács, Piroska Balog, Virginia P Williams, and Redford B Williams. 2010.  Worldwide stress: different problems, similar solutions? cultural adaptation and evaluation of a standardized stress management program in hungary.  _International Journal of Behavioral Medicine_ , 17(1):25–32.
  * Swanson et al. (2020) Kyle Swanson, Lili Yu, and Tao Lei. 2020.  Rationalizing text matching: Learning sparse alignments via optimal transport.  _arXiv preprint arXiv:2005.13111_.
  * Turcan and McKeown (2019) Elsbeth Turcan and Kathleen McKeown. 2019.  Dreaddit: A reddit dataset for stress analysis in social media.  _arXiv preprint arXiv:1911.00133_.
  * Wilcoxon (1945) Frank Wilcoxon. 1945.  Individual comparisons by ranking methods.  _Biometrics Bulletin_ , 1:80–83.
  * Yuan et al. (2021) Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji. 2021.  On explainability of graph neural networks via subgraph explorations.  In _Proceedings of the 38th International Conference on Machine Learning_ , volume 139 of _Proceedings of Machine Learning Research_ , pages 12241–12252. PMLR.

##  Appendix A Appendix

###  A.1 Additional Stress and Context Entropy Results

Figures 5, 6, and 7 show the stress and context entropy distributions of the
original text and the context-dependent and context-independent explanations
across the 166 stressed test examples in the “anxiety,” “assistance,” and
“relationships” subreddits for the Multinomial Naive Bayes, Multilayer
Perceptron, and MentalRoBERTaFT models, respectively. For the Multinomial
Naive Bayes and Multilayer Perceptron models, we experimented with
$\alpha\in\\{0.1,1,10\\}$, with higher $\alpha$ weighting context entropy more
than stress in the MCTS reward function. For the MentalRoBERTaFT model, we
used $\alpha=10$.

Figure 5: Histograms of stress and context entropy scores from the Multinomial
Naive Bayes model for the original text and for the context-dependent and
context-independent explanations extracted by our MCTS algorithm. The left
column shows stress scores while the right column shows context entropy
scores. From top to bottom, the rows show $\alpha=0.1$, $\alpha=1$, and
$\alpha=10$, where $\alpha$ controls the balance between stress and context
entropy in the MCTS reward function. Higher $\alpha$ places less emphasis on
stress and more emphasis on context entropy, resulting in a greater difference
between context-dependent and context-independent entropy scores at the cost
of lower stress.

Figure 6: Histograms of stress and context entropy scores from the Multilayer
Perceptron model for the original text and for the context-dependent and
context-independent explanations extracted by our MCTS algorithm. The left
column shows stress scores while the right column shows context entropy
scores. From top to bottom, the rows show $\alpha=0.1$, $\alpha=1$, and
$\alpha=10$, where $\alpha$ controls the balance between stress and context
entropy in the MCTS reward function. Higher $\alpha$ places less emphasis on
stress and more emphasis on context entropy, resulting in a greater difference
between context-dependent and context-independent entropy scores at the cost
of lower stress.

Figure 7: Histograms of stress and context entropy scores from the
MentalRoBERTaFT model for the original text and for the context-dependent and
context-independent explanations extracted by our MCTS algorithm. The left
plot shows stress scores while the right plot shows context entropy scores,
both for $\alpha=10$. Interestingly, the distributions are somewhat different
from those of the Multinomial Naive Bayes (Figure 5) and Multilayer Perceptron
(Figure 6) models. MentalRoBERTaFT is capable of selecting different context-
dependent and context-independent explanations as measured by entropy, but the
model generally assigns more stress to context-dependent explanations than
context-independent explanations, perhaps hinting at a meaningful difference
between the types of explanations in terms of stress content.

###  A.2 Data Distribution

In Figure 8 and Figure 9, we show the data distribution of our stress and
context (subreddit) labels.

Figure 8: Training and test set stress label distribution. Figure 9: Training
and test set subreddit label distribution.

###  A.3 MentalRoBERTa

MentalRoBERTa is a RoBERTa-based language model Liu et al. (2019) that was
pre-trained on a corpus of 13.7M sentences from Reddit that were posted on
mental health-related subreddits, including, but not limited to, “r/Anxiety”
and “r/Depression”. When training classifiers for stress and context
classification tasks, we used the pre-trained MentalRoBERTa model on Hugging
Face’s model repository, available at https://huggingface.co/mental, and fine-
tuned the model on the Dreaddit dataset, using either the stress or context
labels, for five epochs with a learning rate of 1e-4.

###  A.4 Qualitative Examples

In Tables A.4, A.4, and A.4, we show qualitative examples of our MCTS method
for explainability, with examples from each of three subreddits—“anxiety,”
“assistance,” and “relationships”—from both the MLP and MentalRoBERTaFT
models.

Model | Category |  Text (subreddit = “r/Anxiety”) | Stress | Entropy
---|---|---|---|---
|  Original |  Lately I’ve just been having that terrible feeling in the pit of my stomach and also a feeling of nausea like I constantly need to throw up. I’m sleeping normal but still feeling so tired and drained and can’t really focus at work and because of that I feel like my work performance is slipping up. I am constantly afraid that I’m going to lose my job and that my manager hates me. This has been happening so much more frequently. About a week ago my doc gave me prozac (once a day) and xanax (only as needed) prescriptions and I feel like it’s helped with the bigger attacks and some dark thoughts but now its almost like just a little constant anxiety all the time and it sucks. |  1.000 |  0.000
MLP |  Dependent |  Lately I’ve just been having that terrible feeling in the pit of my stomach and also a feeling of nausea like I constantly need to throw up. I’m sleeping normal but still feeling so tired and drained and can’t really focus at work and because of that I feel like my work performance is slipping up. I am constantly afraid that I’m going to lose my job and that my manager hates me. This has been happening so much more frequently. About a week ago my doc gave me prozac (once a day) and xanax (only as needed) prescriptions and I feel like it’s helped with the bigger attacks and some dark thoughts but now its almost like just a little constant anxiety all the time and it sucks. |  0.933 |  0.300
2-5 |  Independent |  Lately I’ve just been having that terrible feeling in the pit of my stomach and also a feeling of nausea like I constantly need to throw up. I’m sleeping normal but still feeling so tired and drained and can’t really focus at work and because of that I feel like my work performance is slipping up. I am constantly afraid that I’m going to lose my job and that my manager hates me. This has been happening so much more frequently. About a week ago my doc gave me prozac (once a day) and xanax (only as needed) prescriptions and I feel like it’s helped with the bigger attacks and some dark thoughts but now its almost like just a little constant anxiety all the time and it sucks. |  0.489 |  1.045
Mental RoBERTaFT |  Dependent |  Lately I’ve just been having that terrible feeling in the pit of my stomach and also a feeling of nausea like I constantly need to throw up. I’m sleeping normal but still feeling so tired and drained and can’t really focus at work and because of that I feel like my work performance is slipping up. I am constantly afraid that I’m going to lose my job and that my manager hates me. This has been happening so much more frequently. About a week ago my doc gave me prozac (once a day) and xanax (only as needed) prescriptions and I feel like it’s helped with the bigger attacks and some dark thoughts but now its almost like just a little constant anxiety all the time and it sucks. |  0.998 |  0.006
2-5 |  Independent |  Lately I’ve just been having that terrible feeling in the pit of my stomach and also a feeling of nausea like I constantly need to throw up. I’m sleeping normal but still feeling so tired and drained and can’t really focus at work and because of that I feel like my work performance is slipping up. I am constantly afraid that I’m going to lose my job and that my manager hates me. This has been happening so much more frequently. About a week ago my doc gave me prozac (once a day) and xanax (only as needed) prescriptions and I feel like it’s helped with the bigger attacks and some dark thoughts but now its almost like just a little constant anxiety all the time and it sucks. |  0.670 |  0.627

Table 4: Qualitative examples from our MCTS explainability method for a post
in the “r/Anxiety” subreddit. We show the full original text along with the
context-dependent and context-independent explanations selected by MCTS using
both the MLP and MentalRoBERTaFT classifiers.

Model | Category |  Text (subreddit = “r/Assistance”) | Stress | Entropy
---|---|---|---|---
|  Original |  I can’t ask my family because they don’t have the kind of money to help me. If anyone can help me even just a little bit, I would be ridiculously grateful. I just can’t even express what this has done to us. Yes, the bills are paid, but now we’re so anxious that we barely leave the house due to panic attacks. I’ve done things like ubereats but $15 here and there isn’t even making a dent in what I need. |  0.995 |  0.616
MLP |  Dependent |  I can’t ask my family because they don’t have the kind of money to help me. If anyone can help me even just a little bit, I would be ridiculously grateful. I just can’t even express what this has done to us. Yes, the bills are paid, but now we’re so anxious that we barely leave the house due to panic attacks. I’ve done things like ubereats but $15 here and there isn’t even making a dent in what I need |  0.723 |  0.640
2-5 |  Independent |  I can’t ask my family because they don’t have the kind of money to help me. If anyone can help me even just a little bit, I would be ridiculously grateful. I just can’t even express what this has done to us. Yes, the bills are paid, but now we’re so anxious that we barely leave the house due to panic attacks. I’ve done things like ubereats but $15 here and there isn’t even making a dent in what I need. |  0.584 |  1.064
Mental RoBERTaFT |  Dependent |  I can’t ask my family because they don’t have the kind of money to help me. If anyone can help me even just a little bit, I would be ridiculously grateful. I just can’t even express what this has done to us. Yes, the bills are paid, but now we’re so anxious that we barely leave the house due to panic attacks. I’ve done things like ubereats but $15 here and there isn’t even making a dent in what I need. |  0.999 |  0.005
2-5 |  Independent |  I can’t ask my family because they don’t have the kind of money to help me. If anyone can help me even just a little bit, I would be ridiculously grateful. I just can’t even express what this has done to us. Yes, the bills are paid, but now we’re so anxious that we barely leave the house due to panic attacks. I’ve done things like ubereats but $15 here and there isn’t even making a dent in what I need. |  0.478 |  0.518

Table 5: Qualitative examples from our MCTS explainability method for a post
in the “r/Assistance” subreddit. We show the full original text along with the
context-dependent and context-independent explanations selected by MCTS using
both the MLP and MentalRoBERTaFT classifiers.

Model | Category |  Text (subreddit = “r/Relationships”) | Stress | Entropy
---|---|---|---|---
|  Original |  We seem to be talking and accidentally being together more often in school, making what I think are feelings towards her only stronger. I can’t bring myself to bring this up with her because I’m scared that we will have a repeat of February again. I love her so much but I feel that if I have these feelings about other girls am I really devoted to her? This is in no way her fault, she has done nothing to deserve my questioning of my decision, this is my problem and mine alone. I am reluctant to bring this up with her because I’m worried that she might break up with me because I do truly still love her I’m just wondering if this other girl is a passing thought more focused than earlier and something I can overcome. |  0.999 |  0.000
MLP |  Dependent |  We seem to be talking and accidentally being together more often in school, making what I think are feelings towards her only stronger. I can’t bring myself to bring this up with her because I’m scared that we will have a repeat of February again. I love her so much but I feel that if I have these feelings about other girls am I really devoted to her? This is in no way her fault, she has done nothing to deserve my questioning of my decision, this is my problem and mine alone. I am reluctant to bring this up with her because I’m worried that she might break up with me because I do truly still love her I’m just wondering if this other girl is a passing thought more focused than earlier and something I can overcome. |  0.734 |  0.437
2-5 |  Independent |  We seem to be talking and accidentally being together more often in school, making what I think are feelings towards her only stronger. I can’t bring myself to bring this up with her because I’m scared that we will have a repeat of February again. I love her so much but I feel that if I have these feelings about other girls am I really devoted to her? This is in no way her fault, she has done nothing to deserve my questioning of my decision, this is my problem and mine alone. I am reluctant to bring this up with her because I’m worried that she might break up with me because I do truly still love her I’m just wondering if this other girl is a passing thought more focused than earlier and something I can overcome. |  0.510 |  1.043
Mental RoBERTaFT |  Dependent |  We seem to be talking and accidentally being together more often in school, making what I think are feelings towards her only stronger. I can’t bring myself to bring this up with her because I’m scared that we will have a repeat of February again. I love her so much but I feel that if I have these feelings about other girls am I really devoted to her? This is in no way her fault, she has done nothing to deserve my questioning of my decision, this is my problem and mine alone. I am reluctant to bring this up with her because I’m worried that she might break up with me because I do truly still love her I’m just wondering if this other girl is a passing thought more focused than earlier and something I can overcome. |  0.998 |  0.030
2-5 |  Independent |  We seem to be talking and accidentally being together more often in school, making what I think are feelings towards her only stronger. I can’t bring myself to bring this up with her because I’m scared that we will have a repeat of February again. I love her so much but I feel that if I have these feelings about other girls am I really devoted to her? This is in no way her fault, she has done nothing to deserve my questioning of my decision, this is my problem and mine alone. I am reluctant to bring this up with her because I’m worried that she might break up with me because I do truly still love her I’m just wondering if this other girl is a passing thought more focused than earlier and something I can overcome. |  0.712 |  0.444

Table 6: Qualitative examples from our MCTS explainability method for a post
in the “r/Relationships” subreddit. We show the full original text along with
the context-dependent and context-independent explanations selected by MCTS
using both the MLP and MentalRoBERTaFT classifiers.


# Stochastic error cancellation in analog quantum simulation

Yiyi Cai  Institute for Quantum Information and Matter, California Institute
of Technology, Pasadena, CA, USA  Department of Electrical Engineering,
California Institute of Technology, Pasadena, CA, USA  Yu Tong  Institute for
Quantum Information and Matter, California Institute of Technology, Pasadena,
CA, USA  John Preskill  Institute for Quantum Information and Matter,
California Institute of Technology, Pasadena, CA, USA  AWS Center for Quantum
Computing, Pasadena, CA, USA

###### Abstract

Analog quantum simulation is a promising path towards solving classically
intractable problems in many-body physics on near-term quantum devices.
However, the presence of noise limits the size of the system and the length of
time that can be simulated. In our work, we consider an error model in which
the actual Hamiltonian of the simulator differs from the target Hamiltonian we
want to simulate by small local perturbations, which are assumed to be random
and unbiased. We analyze the error accumulated in observables in this setting
and show that, due to stochastic error cancellation, with high probability the
error scales as the square root of the number of qubits instead of linearly.
We explore the concentration phenomenon of this error as well as its
implications for local observables in the thermodynamic limit.

##  1 Introduction

Quantum computers are expected to outperform classical computers at solving
certain problems of interest in physics, chemistry, and materials science.
Simulating the dynamics of many-body quantum systems is an especially hard
problem for classical computers, making quantum dynamics a particularly
promising arena for seeking quantum advantage. Eventually, scalable fault-
tolerant quantum computers will be able to perform accurate simulations of
quantum dynamics, but these robust large-scale quantum machines are not likely
to be available for many years. Meanwhile, what are the prospects for reaching
quantum advantage using near-term quantum simulators that are not error-
corrected?

Circuit-based quantum algorithms for quantum simulation offer great
flexibility and can be error-corrected, but with current quantum technology
analog quantum simulators may offer substantial advantage in the system size
and time that can be achieved in simulation [1, 2, 3]. Analog quantum
processors have tunable Hamiltonians running on quantum platforms, but need
not have universal local control to perform informative simulations [3, 4, 5].
However, because these devices are not error-corrected, it is especially
important to understand how errors accumulate during analog simulations of
quantum dynamics.

Recently Trivedi et al. used the Lieb-Robinson bound to show that the errors
in expectation values of local observables can be independent of system size
for short time evolution [6]. They used an error model in which the actual
Hamiltonian realized in the device differs from the desired target Hamiltonian
by small local perturbations. More precisely, they considered a geometrically
local Hamiltonian on a $d$-dimensional lattice with $N$ sites (each occupied
by a qubit), and assumed that the actual Hamiltonian $H^{\prime}$ and the
target Hamiltonian $H$ are related through

$H^{\prime}=H+\delta\sum_{i=1}^{M}V_{i}.$ (1)

Here each $V_{i}$ is a local term with $\|V_{i}\|\leq 1$, $M=\mathcal{O}(N)$
denotes the number of independent error terms, and $\delta$ is a small number
characterizing the magnitude of the local perturbations. One of their main
conclusions is that the error in the expectation value of a local observable
at time $t$ is at most $\mathcal{O}(t^{d+1}\delta)$, where $t^{d+1}$ is
essentially the volume of the local observable’s Lieb-Robinson past light
cone, and is independent of the system size. For a general observable that is
not necessarily local, or for $t$ large enough so that information has the
time to reach every part of the system, the error is at most
$\mathcal{O}(Nt\delta)$ as expected from first-order perturbation theory.

This result can be seen as a worst-case bound, which applies even if the small
local perturbations are chosen adversarially to produce the largest possible
error. However, this worst-case choice is unlikely to occur in practice. For
estimating the accumulated error that should be anticipated under realistic
conditions, it is often beneficial to consider a probabilistic error model
rather than an adversarial one. To be concrete, we consider the error model

$H^{\prime}=H+\sum_{i=1}^{M}g_{i}V_{i}.$ (2)

where in contrast to (1), we assume that the local perturbations are
stochastic and statistically independent, e.g., each $g_{i}$ is an independent
Gaussian random variable with mean $0$ and standard deviation $\delta$.
Instead of the worst case, we may now consider the accumulation of error in
the average case. That is, we envision sampling $H^{\prime}$ from an ensemble
of possible Hamiltonians that might be realized in the device, estimating the
error for each sample, and then averaging the error over all samples. In other
scenarios, for example in the analysis of the Trotter error in digital quantum
simulations [7, 8], the average-case error is found to be much better than the
worst case, and the same can be expected in this analog setting. As an
example, Fig. 1 shows the difference between the worst-case and average-case
error accumulation for time evolution in a one-dimensional Heisenberg spin
system perturbed by a site-dependent magnetic field.

Figure 1: Numerical study of observable error of a 18-qubit system time-
evolving under a Heisenberg XXX Hamiltonian
$H=-J\sum_{i}\vec{\sigma}_{i}\cdot\vec{\sigma}_{i+1}+\sum_{i}(h+g_{i})X_{i}$.
Local observable $Y_{2}$ is measured on the second qubit at time $t$, with the
system initial state being $\ket{0}^{\otimes N}$, and the local perturbations
are $V_{i}=X_{i}$. The coupling strength $J$ between qubits is set to be
$(0.2)\pi$, and $h=2\pi$. We compare the case of $g_{i}=\delta=0.01$
(symmetric error), with a Gaussian model of random local perturbations, where
$g_{i}\sim\mathcal{N}(0,\delta^{2})$ (random error). The rapid oscillations of
the error as a function of time are discussed in Appendix A

Simple classical reasoning provides an intuitive understanding of this
finding. The cumulative effect of $M$ error sources, each contributing a
Gaussian error with standard deviation $\delta$ and mean $0$, produces a total
Gaussian error with mean $0$ and standard deviation $\sqrt{M}\delta$. For
$M\gg 1$, this $\mathcal{O}(\sqrt{M})$ cumulative error, resulting from
stochastic error cancellations, is significantly suppressed compared to the
$\mathcal{O}(M)$ cumulative error which would occur in the absence of such
cancellations. Because of the stochastic cancellations, we can tolerate more
hardware error (large $\delta$) than the worst-case error bound suggests.

In this paper, we explore the role of such error cancellations in analog
quantum simulators and show that with high probability an error bound with
square-root dependence on the system size $N$ can be achieved for general
observables, in contrast to the linear $N$-dependence for the worst-case error
bound. That is, the error bound is improved from $\mathcal{O}(Nt\delta)$ to
$\mathcal{O}(\sqrt{N}t\delta)$. From this result, we derive an improved bound
for local observables in the thermodynamic limit as well. Using the Lieb-
Robinson bound, we show that the average-case error of local observables in
the thermodynamic limit is bounded above by $\mathcal{O}(t^{d/2+1}\delta)$ as
opposed to the $\mathcal{O}(t^{d+1}\delta)$ bound on the worst-case error.

We are only aware of a few works besides [6] that analyze the error in analog
simulation. In [9] the error is analyzed by averaging over Haar random states,
while in [10] the leading-order error in a Gibbs state is expressed in terms
of Fisher information. In contrast, we study how errors accumulate during time
evolution of a quantum state.

##  2 Main results

Following (2), we consider a generalized setup of the local perturbation
model, where each $g_{i}$ in (2) is a $\chi$-deformed Gaussian defined as
follows:

######  Definition 1 ($\chi$-deformed Gaussian random variable).

A random variable $g$ is a $\chi$-deformed Gaussian random variable if there
exists $\theta\sim\mathcal{N}(0,1)$ such that $g=\chi(\theta)$, and
$\chi:\mathbb{R}\to\mathbb{R}$ is a strictly monotonic increasing
differentiable function satisfying

$\displaystyle|\mathrm{d}\chi(\theta)/\mathrm{d}\theta|\leq\delta,$ (3)
$\displaystyle\chi(0)=0,$ $\displaystyle\chi(+\infty)=\Gamma,\
\chi(-\infty)=-\Gamma,$ $\displaystyle\mathbb{E}[\chi(\theta)]=0.$

Such a random variable $g$ has the nice properties that $|g|\leq\Gamma$ with
probability $1$, and $|g|\leq\delta|\theta|$. We allow choosing
$\Gamma=+\infty$. This definition helps us generalize beyond the Gaussian
noise model. Notably, we have the following examples that can be obtained as
$\chi$-deformed Gaussian: (1) the uniform distribution
$g_{i}\sim\mathcal{U}([-\delta^{\prime},\delta^{\prime}])$ where
$\delta=\sqrt{2/\pi}\delta^{\prime}$,
$\chi(\theta)=\delta^{\prime}\operatorname{erf}(\theta/\sqrt{2})$, and
$\Gamma=\delta^{\prime}$; (2) the truncated Gaussian distribution for which
$g_{i}$ obeys the Gaussian distribution $\mathcal{N}(0,\delta^{\prime 2})$
conditional on $|g_{i}|\leq\Gamma$, where $\delta=\delta^{\prime}$ (one can in
fact choose $\delta$ to be slightly smaller than $\delta^{\prime}$), and
$\chi(\theta)=\text{erf}^{-1}(\text{erf}(\frac{\theta}{\sqrt{2}})\text{erf}(\frac{\gamma}{\sqrt{2}\delta^{\prime}}))\sqrt{2}\delta^{\prime}$.

Denoting $H$ as a target Hamiltonian to be simulated and $H^{\prime}$ as the
actual Hamiltonian implemented, we show in Section 3 and 4 that

######  Theorem 1.

thm:bound_gen_obs On a lattice consisting of $N$-sites, for Hamiltonians $H$
and $H^{\prime}$ related through (2), with each $g_{i}$ being an independent
$\chi$-deformed Gaussian with
$|\mathrm{d}\chi(\theta)/\mathrm{d}\theta|\leq\delta$, $\Gamma\in(0,+\infty]$,
and $\sqrt{N}t\delta\leq\mathcal{O}(1)$, we have

$\big{|}\mathrm{tr}[\rho e^{iH^{\prime}t}Oe^{-iH^{\prime}t}]-\mathrm{tr}[\rho
e^{iHt}Oe^{-iHt}]\big{|}\leq
2a\sqrt{N}t\delta\|O\|+\mathcal{O}(Nt^{2}\delta^{2}\|O\|)$ (4)

with probability $1-2e^{-ca^{2}}$, for arbitrary $a>0$ and some absolute
constant $c>0$.

Note that thm:bound_gen_obs holds even when $\Gamma=\infty$. We assume
$\sqrt{N}t\delta\leq\mathcal{O}(1)$, which gives the time scale in which the
simulation provides meaningful results. This result is stronger than the
$\mathcal{O}(Nt\delta\|O\|)$ scaling one would get without error cancellation,
i.e. $g_{i}=\delta.$ This indicates that for given system size $N$ and time
$t$, we can tolerate higher local perturbations up to $\frac{1}{\sqrt{N}t}$
instead of $\frac{1}{Nt}.$

Additionally, one may be interested in the thermodynamic limit
($N\rightarrow\infty$) as opposed to a finite system [11] and explore quantum
simulation tasks that are stable against extensive errors. More precisely, for
a local observable $O$ that is supported only on a constant number of sites,
and a geometrically local Hamiltonian $H$, we want the error bound to be
independent of the size of the system. With such an error bound, computing the
expectation value of local observables in time evolution falls into the
category of “stable quantum simulation tasks” as defined in [6, Prop. 4].

An system-size independent error bound implies that the hardware error
($\delta$) does not need to be scaled down with system size, which is highly
desirable for analog simulators. Specifically, we consider a bound for local
observables acting on $\mathcal{O}(1)$ adjacent sites in a quantum system on a
lattice $\mathbb{Z}_{L}^{d}$, where $d$ is the lattice dimension and $L$ is
the number of sites in each direction. Combining thm:bound_gen_obs with the
Lieb-Robinson bound [12], we show in Section 5 that the stability of the
quantum task can be stated:

######  Theorem 2.

thm:bound_local_obs We consider a geometrically local Hamiltonian $H$ on a
$d$-dimensional lattice $\mathbb{Z}_{L}^{d}$ with $L$ sites in each direction,
and a local observable $O$ supported on $\mathcal{O}(1)$ sites. The
Hamiltonian can be written as
$H=\sum_{\alpha\in\mathbb{Z}_{L}^{d}}H_{\alpha}$, where
$\|H_{\alpha}\|=\mathcal{O}(1)$ and $H_{\alpha}$ acts non-trivially only on
sites that are within distance $r_{0}$ from $\alpha$, with
$r_{0}=\mathcal{O}(1)$. For a $H^{\prime}$ related to $H$ through (2), with
each $g_{i}$ being an independent $\chi$-deformed Gaussian with
$|\mathrm{d}\chi(\theta)/\mathrm{d}\theta|\leq\delta$,
$\Gamma=\mathcal{O}(1)$, $t^{d/2+1}\delta\leq\mathcal{O}(1)$, and each site
being acted on by only $\mathcal{O}(1)$ of the error terms $V_{i}$, we have

$\big{|}\mathrm{tr}[\rho e^{iH^{\prime}t}Oe^{-iH^{\prime}t}]-\mathrm{tr}[\rho
e^{iHt}Oe^{-iHt}]\big{|}=\mathcal{O}\left(at^{\frac{d}{2}+1}\delta\|O\|\right)+\mathcal{O}\left(at\delta\log^{d/2}(\delta^{-1})\|O\|\right)$
(5)

with probability $1-2e^{-ca^{2}}$, for any $a>0$ and some absolute constant
$c>0$.

This is a stronger bound than the previously established one without error
cancellation with leading term of $\mathcal{O}\left(t^{d+1}\delta\right)$ [6].

##  3 The average error from random noise

We first consider the average observable error accumulated during time
evolution and bound

$\big{|}\mathbb{E}_{\\{g_{i}\\}}[\mathrm{tr}[\rho
O^{\prime}(t)]]-\mathrm{tr}[\rho O(t)]\big{|}$ (6)

with the notation

$O(t)=e^{iHt}Oe^{-iHt},\quad
O^{\prime}(t)=e^{iH^{\prime}t}Oe^{-iH^{\prime}t},\quad\rho(t)=e^{-iHt}\rho
e^{iHt},\quad\rho^{\prime}(t)=e^{-iH^{\prime}t}\rho e^{iH^{\prime}t}.$ (7)

We use the evolution under the target Hamiltonian $H$ as a reference frame,
and consider the local perturbation in the interaction picture:

$e^{-iH^{\prime}t}=e^{-iHt}\mathcal{T}e^{-i\int_{0}^{t}\sum_{i}g_{i}V_{i}(s)\mathrm{d}s}$
(8)

where $V_{i}(s)=e^{iHs}V_{i}e^{-iHs}$ and $\mathcal{T}$ denotes time ordering.

We assume that $\delta\leq\mathcal{O}(1/(\sqrt{N}t))$ in the analysis below.
We use the Dyson expansion to analyze the accumulation of error:

$\displaystyle\mathbb{E}[\mathrm{tr}[\rho O^{\prime}(t)]]-\mathrm{tr}[\rho
O(t)]$ (9)
$\displaystyle=\sum_{k=1}^{\infty}(i)^{k}\int_{0}^{t}\mathrm{d}t_{1}\int_{0}^{t_{1}}\mathrm{d}t_{2}\cdots\int_{0}^{t_{k-1}}\mathrm{d}t_{k}\sum_{i_{1},\cdots,i_{k}}\mathbb{E}[g_{i_{1}}\cdots
g_{i_{k}}]\underbrace{\mathrm{tr}\big{[}\rho(t)[V_{i_{1}}(t_{1}),[\cdots[V_{i_{k}}(t_{k}),O]\cdots]\big{]}}_{C_{i_{1}i_{2}\cdots
i_{k}}^{(k)}}.$

With $\|\rho(t)\|_{\mathrm{tr}}\leq 1$,111Here $\|\cdot\|_{\mathrm{tr}}$
denotes the trace norm. and $||[A,B]||\leq\|AB\|+\|BA\|\leq 2||AB||,$

$\big{|}C_{i_{1}i_{2}\cdots
i_{k}}^{(k)}\big{|}\leq||\rho(t)||_{\mathrm{tr}}||[V_{i_{1}}(t_{1}),[\cdots[V_{i_{k}}(t_{k}),O]\cdots]]||\leq
2^{k}\|O\|.$ (10)

Therefore

$\displaystyle\big{|}\mathbb{E}[\mathrm{tr}[\rho
O^{\prime}(t)]]-\mathrm{tr}[\rho O(t)]\big{|}$
$\displaystyle\leq\sum_{k=1}^{\infty}\frac{t^{k}}{k!}\mathbb{E}\left[\left(\sum_{i}g_{i}\right)^{k}\right]2^{k}\|O\|$
(11) $\displaystyle=\mathbb{E}[e^{2t\sum_{i=1}^{N}g_{i}}-1]\|O\|$
$\displaystyle=\left(\prod_{i=1}^{N}\mathbb{E}[e^{2tg_{i}}]-1\right)\|O\|.$

Without loss of generality we assume that $\|O\|\leq 1$ hereafter. From the
above bound we can see that we only need to focus on bounding
$\mathbb{E}[e^{2tg_{i}}]-1$ for each $i$. Using the fact that
$\mathbb{E}[g_{i}]=\mathbb{E}[\chi(\theta_{i})]=0$ from (3) and
$|g_{i}|\leq\delta|\theta_{i}|$, we have

$\displaystyle\mathbb{E}[e^{2tg_{i}}]$
$\displaystyle=\sum_{k=0}^{\infty}\frac{(2t)^{k}}{k!}\mathbb{E}[g_{i}^{k}]\leq
1+\sum_{k=2}^{\infty}\frac{(2\delta
t)^{k}}{k!}\mathbb{E}[|\theta_{i}|^{k}]=\mathbb{E}[e^{2\delta
t|\theta_{i}|}]-2\delta t\mathbb{E}[|\theta_{i}|].$ (12)

Using Taylor’s theorem in the Lagrange form, with the fact that

$\frac{\mathrm{d}^{k}}{\mathrm{d}a^{k}}\mathbb{E}[e^{a|\theta_{i}|}]=\mathbb{E}[e^{a|\theta_{i}|}|\theta_{i}|^{k}],$
(13)

we have

$\mathbb{E}[e^{2\delta t|\theta_{i}|}]-2\delta t\mathbb{E}[|\theta_{i}|]\leq
1+2\delta^{2}t^{2}\mathbb{E}[e^{2\delta t|\theta_{i}|}|\theta_{i}|^{2}].$ (14)

Because $\theta_{i}\sim\mathcal{N}(0,1)$, for any $a\geq 0$,

$\mathbb{E}[e^{a|\theta_{i}|}|\theta_{i}|^{2}]=(4a^{2}e^{a^{2}})(1+\operatorname{erf}{a})+4\sqrt{\frac{2}{\pi}}ae^{-a^{2}/2}-\sqrt{\frac{2}{\pi}}ae^{a^{2}/2}=1+\mathcal{O}(a),$
(15)

we have (using $\delta\leq\mathcal{O}(1/(\sqrt{N}t))$)

$\mathbb{E}[e^{2\delta t|\theta_{i}|}]-2\delta t\mathbb{E}[|\theta_{i}|]\leq
1+2\delta^{2}t^{2}+\mathcal{O}(\delta^{3}t^{3})=1+2\delta^{2}t^{2}+\mathcal{O}(N^{-3/2}).$
(16)

By (11), (12), and $\|O\|\leq 1$ we then have

$\big{|}\mathbb{E}[\mathrm{tr}[\rho O^{\prime}(t)]]-\mathrm{tr}[\rho
O(t)]\big{|}\leq\left(1+2\delta^{2}t^{2}+\mathcal{O}(N^{-3/2})\right)^{N}-1=2N\delta^{2}t^{2}+\mathcal{O}(N^{-1/2}).$
(17)

The above derivation leads us to the following theorem:

######  Theorem 3 (Average error bound).

On a lattice consisting of $N$-sites, for Hamiltonians $H$ and $H^{\prime}$
related through (2), with each $g_{i}$ being an independent $\chi$-deformed
Gaussian with $|\mathrm{d}\chi(\theta)/\mathrm{d}\theta|\leq\delta$,
$\Gamma\in(0,+\infty]$, and $\sqrt{N}t\delta\leq\mathcal{O}(1)$, we have
thm:avg_error_bound

$\big{|}\mathbb{E}_{\\{g_{i}\\}}[\mathrm{tr}[\rho
O^{\prime}(t)]]-\mathrm{tr}[\rho
O(t)]\big{|}=\mathcal{O}(N\delta^{2}t^{2}\|O\|)$ (18)

This error bound shows that, if we average over multiple instances of the
noise, then for the simulation to yield meaningful result up to time $t$ for a
system with size $N$, we need local perturbation to be
$\delta=\mathcal{O}(1/(\sqrt{N}t))$, whereas the naive error bound of
$\mathcal{O}(Nt\delta)$ would only guarantee a meaningful result only when
$\delta=\mathcal{O}(1/(Nt))$. Therefore we can significantly extend the time
and system size of the simulation that can be performed with guarantee at the
same level of noise.

##  4 Concentration of the error

In the above section we focused on the expected error, but can the error be
significantly larger than its expectation value? This is a question about the
concentration of the probability measure, and our main tool is the following
lemma:

######  Lemma 1 (Gaussian concentration inequality for Lipschitz functions,
Ref. [13]).

Let $f:\mathbb{R}^{M}\rightarrow\mathbb{R}$ be a function which is Lipschitz-
continuous with constant $1$ (i.e. $|f(x)-f(y)|\leq|x-y|$ for all
$x,y\in\mathbb{R}^{M}$), then for any $t$,

$\mathbb{P}\left[|f(X)-\mathbb{E}[f(X)]|\geq t\right]\leq 2\exp(-ct^{2})$ (19)

for all $t>0$ and some absolute constant $c>0$, where
$X\sim\mathcal{N}(0,1)^{M}.$

Recall that the expectation value $\mathrm{tr}[\rho O^{\prime}(t)]$ is a
function of the noise $\\{g_{i}\\}$, which is in turn a function of Gaussian
random variables $\\{\theta_{i}\\}$ through $g_{i}=\chi(\theta_{i})$. We
therefore view $\mathrm{tr}[\rho O^{\prime}(t)]$ as a function of
$\\{\theta_{i}\\}$ which we denote by $h(\vec{\theta})$, where
$\vec{\theta}=(\theta_{1},\theta_{2},\cdots,\theta_{M})$. Similarly we denote
$\vec{g}=(g_{1},g_{2},\cdots,g_{M})$. We will next proceed to obtain a
Lipschitz constant for this function. Note that

$\frac{\partial}{\partial\theta_{i}}h(\vec{\theta})=\frac{\mathrm{d}g_{i}}{\mathrm{d}\theta_{i}}\partial_{g_{i}}\mathrm{tr}[Oe^{-iH^{\prime}(\vec{g})t}\rho
e^{iH^{\prime}(\vec{g})t}],$ (20)

where we make explicit the $\vec{g}$-dependence in $H^{\prime}$ defined in
(2). Because $|\mathrm{d}g_{i}/\mathrm{d}\theta_{i}|\leq\delta$ by (3), we
only need to bound
$\partial_{g_{i}}\mathrm{tr}[Oe^{-iH^{\prime}(\vec{g})t}\rho
e^{iH^{\prime}(\vec{g})t}]$:

$\displaystyle|\partial_{g_{i}}\mathrm{tr}[Oe^{iH^{\prime}(\vec{g})t}\rho
e^{-iH^{\prime}(\vec{g})t}]|$
$\displaystyle\leq\|(\partial_{g_{i}}e^{iH^{\prime}(\vec{g})t})Oe^{-iH^{\prime}(\vec{g})t}\|+\|e^{iH^{\prime}(\vec{g})t}O(\partial_{g_{i}}e^{-iH^{\prime}(\vec{g})t})\|$
(21) $\displaystyle\leq
2\|O\|\|\partial_{g_{i}}e^{-iH^{\prime}(\vec{g})t}\|\leq 2\|O\|t,$

where we have used $\|V_{i}\|\leq 1$. We therefore have
$|\partial_{\theta_{i}}h(\vec{\theta})|\leq 2\|O\|t\delta$. The Lipschitz
constant can then be chosen as

$\sqrt{\sum_{i=1}^{M}|\partial_{\theta_{i}}h|^{2}}\leq
2\|O\|\sqrt{M}t\delta=C_{\mathrm{Lip}}.$ (22)

$h(\vec{\theta})/C_{\mathrm{Lip}}$ then has Lipschitz constant $1$. Through a
direction application of Lemma 1, we obtain that for some absolute constant
$c>0$ and any $a>0$,

$\displaystyle\mathbb{P}[|h(\vec{\theta})-\mathbb{E}[h(\vec{\theta})]|\geq
aL]\leq 2e^{-ca^{2}}.$ (23)

We then have the following result, where we also use $M=\mathcal{O}(N)$:

######  Theorem 4 (Concentration bound of observable error).

thm:concentration_bound On a lattice consisting of $N$-sites, for Hamiltonians
$H$ and $H^{\prime}$ related through (2), with each $g_{i}$ being an
independent $\chi$-deformed Gaussian with
$|\mathrm{d}\chi(\theta)/\mathrm{d}\theta|\leq\delta$, $\Gamma\in(0,+\infty]$,
and $\sqrt{N}t\delta\leq 1$, we have

$\big{|}\mathrm{tr}[\rho O(t)]-\mathbb{E}[\mathrm{tr}[\rho
O^{\prime}(t)]]\big{|}\leq 2a\|O\|\sqrt{N}t\delta$ (24)

with probability $1-2e^{-ca^{2}}$, for arbitrary $a>0$ and some absolute
constant $c>0$.

Combining thm:avg_error_bound and thm:concentration_bound, we arrive at the
result stated in thm:bound_gen_obs.

##  5 Local observables

In this section, we will take locality into consideration to obtain an error
bound for local observables that is independent of the system size. Such an
error bound is needed to make the simulation meaningful in the thermodynamic
limit. We restrict ourselves to spin systems with spatial locality, i.e.
systems with Hamiltonians defined on a $d$-dimensional lattice with $N$ sites
in total and $L$ sites in each direction, written as

$H=\sum_{\alpha\in\mathbb{Z}_{L}^{d}}H_{\alpha}$ (25)

where $\|H_{\alpha}\|\leq\zeta$ and $H_{\alpha}$ only acts on spins within a
distance $r_{0}$ from $\alpha$, and $r_{0}=\mathcal{O}(1)$. A key tool we are
going to use is the Lieb-Robinson bound:

######  Lemma 2 (Lieb-Robinson Bound, Refs. [14, 15, 6]).

For any local operator $O$ with support $S_{O}$, and for any $R>0$, there
exist positive constants $u,v$ that depend only on the lattice such that

$\|O(t)-O_{R}(t)\|\leq\|O\||S_{O}|e^{-\mu R}(e^{v\zeta t}-1)$ (26)

where $O_{R}(t)=e^{iH_{R}t}Oe^{-iH_{R}t}$ with
$H_{R}=H-\sum_{\alpha|d(S_{H^{\alpha}},S_{O})\geq R}H_{\alpha}$ being the
restriction of the Hamiltonian to a region within distance $R$ of $S_{O}.$

We can then apply the Lieb-Robinson bound (Lemma 2) to approximate the
Heisenberg picture evolution of local observables with that corresponding to
the Hamiltonian truncated within their light cones. Specifically, we consider
the Heisenberg picture of observable $O$ under the truncated Hamiltonian
$H_{R}$ and $H_{R}^{\prime}$, denoted as:

$O_{R}(t)=e^{iH_{R}t}Oe^{-iH_{R}t},\quad
O_{R}^{\prime}(t)=e^{iH_{R}^{\prime}t}Oe^{-iH_{R}^{\prime}t}$ (27)

where we denote $H_{R}$ as the truncated Hamiltonian acting non-trivially only
on sites within distance $R$ from $S_{O}$, and $H_{R}^{\prime}$ as the
Hamiltonian obtained from $H^{\prime}$ through the same procedure. Assuming
$|S_{O}|\leq\mathcal{O}(1)$, and with $\|H_{\alpha}\|\leq\zeta$ and $e^{-\mu
k}\geq 0$, we arrive at

$\big{|}O^{\prime}(t)-O_{R}^{\prime}(t)\big{|}\leq\mathcal{O}(\|O\|e^{-\mu
R+v\zeta t}),\quad\big{|}O(t)-O_{R}(t)\big{|}\leq\mathcal{O}(\|O\|e^{-\mu
R+v\zeta t})$ (28)

Since now $H_{R}$ and $H_{R}^{\prime}$ acts non-trivially only on
$\mathcal{O}(R^{d})$, making this the effective system size. We also need to
assume that the noise is spread evenly across the whole system, which can be
rigorously stated as each site being acted on by only $\mathcal{O}(1)$ of the
error terms $V_{i}$. Therefore there are only $\mathcal{O}(R^{d})$ terms
$V_{i}$ that come into the difference between $H_{R}$ and $H_{R}^{\prime}$.
Consequently we can apply thm:bound_gen_obs to get

$\displaystyle\big{|}O_{R}^{\prime}(t)-O_{R}(t)\big{|}$ $\displaystyle\leq
2a\sqrt{R^{d}}t\delta\|O\|+\mathcal{O}(R^{d}t^{2}\delta^{2}\|O\|)$ (29)

with probability $1-2e^{-ca^{2}},$ for some absolute constant $c>0$ and any
$a>0.$ Combining the above bounds (28) and (28) together, we obtain

$\big{|}O^{\prime}(t)-O(t)\big{|}\leq\mathcal{O}(aR^{d/2}t\delta\|O\|+\|O\|e^{-\mu
R+v\zeta t})$ (30)

Note that if we choose $R=\frac{1}{\mu}(v\zeta t+\log(\delta^{-1}))$, then we
get

$\big{|}O^{\prime}(t)-O(t)\big{|}\leq\mathcal{O}\left(a\|O\|\left(\frac{v\zeta}{\mu}t+\frac{1}{\mu}\log(\delta^{-1})\right)^{d/2}t\delta+\delta\|O\|\right)$
(31)

Using the fact that $(\alpha+\beta)^{d}\leq\mathcal{O}(\alpha^{d}+\beta^{d})$
when $\alpha,\beta$ are constants, we arrive at

$\big{|}\mathbb{E}[O^{\prime}(t)]-\mathbb{E}[O(t)]\big{|}\leq\mathcal{O}\left(at^{\frac{d}{2}+1}\delta\|O\|\right)+\mathcal{O}\left(at\delta\log^{d/2}(\delta^{-1})\|O\|\right)$
(32)

with probability $1-2e^{-ca^{2}}.$ thm:bound_local_obs then follows.

##  6 Conclusion

In this work, we considered the observable error bounds for analog quantum
simulation under random coherent noise coming from independent sources. We
showed that such randomness leads to improved scaling in error bounds due to
stochastic error cancellation. We studied general observables without locality
constraints as well as local observables, finding in both cases that average-
case error bounds scale more favorably than worst-case error bounds. Such
cancellation indicates a higher tolerance of noise for simulation tasks on
near-term analog quantum simulators than suggested by the worst-case bound.

Although our result substantially improves the previous state-of-the-art error
bounds, there are still many factors that are not taken into consideration in
our analysis. For example, in many-body localized systems [16, 17, 18, 19, 20,
21, 22], our error bound based on the Lieb-Robinson light cone will not be
able to capture the slow propagation of information, thus leading to an over-
estimation of the error. In general, a tight analysis of the error would
require understanding how operators spread in the system, which is a highly
non-trivial and system-specific problem [23, 24, 25, 26]. Phenomena such as
thermalization should also play an important role, because if a subsystem
thermalizes then the error on local operators in the subsystem should no
longer accumulate over time. Symmetry has also been shown to be helpful in
reducing error in both analog and digital quantum simulations [27, 28], and so
has randomness in the simulation algorithm and the initial state [7, 29, 30].
Our results for geometrically local Hamiltonians should be generalizable to
the situation with power-law decaying interactions [31, 32, 33, 34, 35, 36,
37], where the Lieb-Robinson bound is still available when the decay is fast
enough. These observations indicate that we may still be able to obtain more
accurate characterizations of error accumulation in practical analog
simulators.

In this work we focused on quantum systems consisting of qubits or qudits, but
many realistic quantum systems involve involve finitely many local degrees of
freedom and unbounded operators in the Hamiltonian, which makes analysis more
difficult [38, 39]. We hope to tackle this problem in future works.

Furthermore, we note that an approximate ground-state projection operator can
be written as a linear combination of time evolution operators (a fact which
is instrumental in the proof of the exponential clustering theorem and 1D area
law [40, 41, 42]) and that approximate ground-state projectors may be used in
algorithms for preparing the ground state [43, 44, 45]. We therefore expect
our results to be useful for analyzing how errors in the Hamiltonian affect
expectation values of observables in the ground state. We also hope to extend
our result to thermal states using the techniques employed in [6].

## Acknowledgements

We thank Minh Tran, Matthias Caro, Mehdi Soleimanifar, Hsin-Yuan Huang,
Andreas Elben, ChunJun Cao, and Christopher Pattison for helpful discussions.
Y.C. acknowledges funding from Arthur R. Adams Summer Undergraduate Research
Fellowship. Y.T. acknowledges funding from U.S. Department of Energy Office of
Science, Office of Advanced Scientific Computing Research (DE-SC0020290), and
from U.S. Department of Energy, Office of Science, Basic Energy Sciences,
under Award Number DE-SC0019374. J.P. acknowledges support from the U.S.
Department of Energy Office of Science, Office of Advanced Scientific
Computing Research (DE-NA0003525, DE-SC0020290), the U.S. Department of
Energy, Office of Science, National Quantum Information Science Research
Centers, Quantum Systems Accelerator, and the National Science Foundation
(PHY-1733907). The Institute for Quantum Information and Matter is an NSF
Physics Frontiers Center.

## References

  * [1] J. Preskill, “Quantum Computing in the NISQ era and beyond,” Quantum, vol. 2, p. 79, Aug. 2018.
  * [2] A. Daley, I. Bloch, C. Kokail, S. Flannigan, N. Pearson, M. Troyer, and P. Zoller, “Practical quantum advantage in quantum simulation,” Nature, vol. 607, pp. 667–676, July 2022.
  * [3] J. I. Cirac and P. Zoller, “Goals and opportunities in quantum simulation,” Nature Physics, vol. 8, pp. 264–266, 2012.
  * [4] D. S. França and R. García-Patrón, “Limitations of optimization algorithms on noisy quantum devices,” Nature Physics, vol. 17, pp. 1221–1227, Oct. 2021.
  * [5] G. De Palma, M. Marvian, C. Rouzé, and D. S. França, “Limitations of variational quantum algorithms: A quantum optimal transport approach,” PRX Quantum, vol. 4, p. 010309, Jan. 2023\.
  * [6] R. Trivedi, A. F. Rubio, and J. I. Cirac, “Quantum advantage and stability to errors in analogue quantum simulators,” arXiv preprint arXiv:2212.04924, 2022.
  * [7] C.-F. Chen and F. G. Brandão, “Concentration for trotter error,” arXiv preprint arXiv:2111.05324, 2021.
  * [8] Q. Zhao, Y. Zhou, A. F. Shaw, T. Li, and A. M. Childs, “Hamiltonian simulation with random inputs,” Physical Review Letters, vol. 129, no. 27, p. 270502, 2022.
  * [9] P. M. Poggi, N. K. Lysne, K. W. Kuper, I. H. Deutsch, and P. S. Jessen, “Quantifying the sensitivity to errors in analog quantum simulation,” PRX Quantum, vol. 1, no. 2, p. 020308, 2020.
  * [10] M. Sarovar, J. Zhang, and L. Zeng, “Reliability of analog quantum simulation,” EPJ quantum technology, vol. 4, no. 1, pp. 1–29, 2017.
  * [11] D. Aharonov and S. Irani, “Hamiltonian complexity in the thermodynamic limit,” in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pp. 750–763, 2022.
  * [12] E. H. Lieb and D. W. Robinson, “The finite group velocity of quantum spin systems,” Communications in Mathematical Physics, vol. 28, no. 3, pp. 251–257, 1972.
  * [13] B. Maurey, “Some deviation inequalities,” Geometric & Functional Analysis GAFA, vol. 1, no. 2, pp. 188–197, 1991.
  * [14] M. B. Hastings, “Lieb-schultz-mattis in higher dimensions,” Physical review b, vol. 69, no. 10, p. 104431, 2004.
  * [15] S. Bravyi, M. B. Hastings, and F. Verstraete, “Lieb-robinson bounds and the generation of correlations and topological quantum order,” Physical review letters, vol. 97, no. 5, p. 050401, 2006.
  * [16] P. W. Anderson, “Absence of diffusion in certain random lattices,” Phys. Rev., vol. 109, pp. 1492–1505, Mar 1958.
  * [17] L. Fleishman and P. W. Anderson, “Interactions and the anderson transition,” Phys. Rev. B, vol. 21, pp. 2366–2377, Mar 1980.
  * [18] I. V. Gornyi, A. D. Mirlin, and D. G. Polyakov, “Interacting electrons in disordered wires: Anderson localization and low-$t$ transport,” Phys. Rev. Lett., vol. 95, p. 206603, Nov 2005.
  * [19] D. Basko, I. Aleiner, and B. Altshuler, “Metal–insulator transition in a weakly interacting many-electron system with localized single-particle states,” Annals of Physics, vol. 321, no. 5, pp. 1126–1205, 2006.
  * [20] D. A. Abanin and Z. Papić, “Recent progress in many-body localization,” Annalen der Physik, vol. 529, no. 7, p. 1700169, 2017.
  * [21] R. Nandkishore and D. A. Huse, “Many-body localization and thermalization in quantum statistical mechanics,” Annual Review of Condensed Matter Physics, vol. 6, no. 1, pp. 15–38, 2015.
  * [22] D. A. Abanin, E. Altman, I. Bloch, and M. Serbyn, “Colloquium: Many-body localization, thermalization, and entanglement,” Rev. Mod. Phys., vol. 91, p. 021001, May 2019.
  * [23] C.-F. Chen and A. Lucas, “Operator growth bounds from graph theory,” Communications in Mathematical Physics, vol. 385, no. 3, pp. 1273–1323, 2021\.
  * [24] D. E. Parker, X. Cao, A. Avdoshkin, T. Scaffidi, and E. Altman, “A universal operator growth hypothesis,” Physical Review X, vol. 9, no. 4, p. 041017, 2019.
  * [25] T. Schuster and N. Y. Yao, “Operator growth in open quantum systems,” arXiv preprint arXiv:2208.12272, 2022.
  * [26] T. Schuster, B. Kobrin, P. Gao, I. Cong, E. T. Khabiboulline, N. M. Linke, M. D. Lukin, C. Monroe, B. Yoshida, and N. Y. Yao, “Many-body quantum teleportation via operator spreading in the traversable wormhole protocol,” Physical Review X, vol. 12, no. 3, p. 031013, 2022.
  * [27] M. C. Tran, Y. Su, D. Carney, and J. M. Taylor, “Faster digital quantum simulation by symmetry protection,” PRX Quantum, vol. 2, no. 1, p. 010323, 2021.
  * [28] C. G. Rotello, Symmetry Protected Subspaces in Quantum Simulations.  PhD thesis, Colorado School of Mines, 2022.
  * [29] A. M. Childs, A. Ostrander, and Y. Su, “Faster quantum simulation by randomization,” Quantum, vol. 3, p. 182, 2019.
  * [30] D. An, D. Fang, and L. Lin, “Time-dependent unbounded hamiltonian simulation with vector norm scaling,” Quantum, vol. 5, p. 459, 2021.
  * [31] M. C. Tran, A. Y. Guo, Y. Su, J. R. Garrison, Z. Eldredge, M. Foss-Feig, A. M. Childs, and A. V. Gorshkov, “Locality and digital quantum simulation of power-law interactions,” Physical Review X, vol. 9, no. 3, p. 031006, 2019\.
  * [32] X. Chen and T. Zhou, “Quantum chaos dynamics in long-range power law interaction systems,” Physical Review B, vol. 100, no. 6, p. 064305, 2019\.
  * [33] Z.-X. Gong, M. Foss-Feig, S. Michalakis, and A. V. Gorshkov, “Persistence of locality in systems with power-law interactions,” Physical review letters, vol. 113, no. 3, p. 030602, 2014.
  * [34] D. J. Luitz and Y. B. Lev, “Emergent locality in systems with power-law interactions,” Physical Review A, vol. 99, no. 1, p. 010105, 2019.
  * [35] M. C. Tran, A. Y. Guo, C. L. Baldwin, A. Ehrenberg, A. V. Gorshkov, and A. Lucas, “Lieb-robinson light cone for power-law interactions,” Physical review letters, vol. 127, no. 16, p. 160401, 2021.
  * [36] M. C. Tran, C.-F. Chen, A. Ehrenberg, A. Y. Guo, A. Deshpande, Y. Hong, Z.-X. Gong, A. V. Gorshkov, and A. Lucas, “Hierarchy of linear light cones with long-range interactions,” Physical Review X, vol. 10, no. 3, p. 031009, 2020.
  * [37] C.-F. Chen and A. Lucas, “Finite speed of quantum scrambling with long range interactions,” Physical review letters, vol. 123, no. 25, p. 250605, 2019\.
  * [38] Y. Tong, V. V. Albert, J. R. McClean, J. Preskill, and Y. Su, “Provably accurate simulation of gauge theories and bosonic systems,” Quantum, vol. 6, p. 816, 2022.
  * [39] T. Kuwahara, T. Van Vu, and K. Saito, “Optimal light cone and digital quantum simulation of interacting bosons,” arXiv preprint arXiv:2206.14736, 2022\.
  * [40] M. B. Hastings and T. Koma, “Spectral gap and exponential decay of correlations,” Communications in mathematical physics, vol. 265, pp. 781–804, 2006.
  * [41] M. B. Hastings, “An area law for one-dimensional quantum systems,” Journal of statistical mechanics: theory and experiment, vol. 2007, no. 08, p. P08024, 2007.
  * [42] I. Arad, A. Kitaev, Z. Landau, and U. Vazirani, “An area law and sub-exponential algorithm for 1d systems,” arXiv preprint arXiv:1301.1162, 2013.
  * [43] Y. Ge, J. Tura, and J. I. Cirac, “Faster ground state preparation and high-precision ground energy estimation with fewer qubits,” Journal of Mathematical Physics, vol. 60, no. 2, 2019.
  * [44] L. Lin and Y. Tong, “Near-optimal ground state preparation,” Quantum, vol. 4, p. 372, 2020.
  * [45] L. Lin and Y. Tong, “Heisenberg-limited ground-state energy estimation for early fault-tolerant quantum computers,” PRX Quantum, vol. 3, no. 1, p. 010318, 2022.

##  Appendix A Separation of oscillation and growth in the observable error

Figure 2: (Left) Comparing the oscillation part $|\braket{F(t)}|$ and the
growth part $|\braket{G(t)}|$ in Eq. (33) that describes the evolution of the
error operator. The setup is the same as in Figure 1 except that the system
now contains $8$ qubits and the observable is $(1/N)\sum_{i=1}^{N}Y_{i}$.
(Right) Error in the observable expectation value for symmetric and random
local errors. The simulation is performed with the same parameter setup as in
Fig. 1, except with $h=(0.5)\pi$.

In Fig. 1 we observed that the error displays rapid oscillation in time. In
this appendix we will investigate the cause of it.

We will examine how the operator $O$, the operator whose expectation value we
want to estimate at the end of the evolution, evolves differently under the
target Hamiltonian $H$ and the actual Hamiltonian $H^{\prime}$. Using the
notation introduced in Eq. (7), we denote by $O(t)$ the time-evolved operator
$O$ at time $t$ in the Heisenberg picture under the target Hamiltonian $H$,
and by $O^{\prime}(t)$ the corresponding operator under the actual Hamiltonian
$H^{\prime}$. We can write down an equation governing the error
$O^{\prime}(t)-O(t)$, from taking the time derivative in Eq. (7):

$\frac{\mathrm{d}}{\mathrm{d}t}(O^{\prime}(t)-O(t))=\underbrace{i[H,O^{\prime}(t)-O(t)]}_{F(t)}+\underbrace{i\sum_{i=1}^{M}g_{i}[V_{i},O^{\prime}(t)]}_{G(t)}.$
(33)

We will show that only the second part $G(t)$ contributes to the growth of the
error. Writing down the solution to the above differential equation using
Duhammel’s principle, for $0<s<t$ we have

$O^{\prime}(t)-O(t)=e^{iH(t-s)}(O^{\prime}(s)-O(s))e^{-iH(t-s)}+\int_{s}^{t}e^{iH(t-u)}G(u)e^{-iH(t-u)}\mathrm{d}u.$
(34)

We observe that if $G(u)=0$ for $s<u<t$, then we would have
$\|O^{\prime}(t)-O(t)\|=\|O^{\prime}(s)-O(s)\|$, and the error would not grow
in magnitude. This shows that $G(t)$ is solely responsible for the growth of
the error. The first term on the right-hand side of (33) only rotates
$O^{\prime}(t)-O(t)$.

While $F(t)$ does not contribute to the growth of the error, it nevertheless
plays a part in how the derivative changes, as can be seen from (33), which
tells us that
$\frac{\mathrm{d}}{\mathrm{d}t}\braket{O^{\prime}(t)-O(t)}=\braket{F(t)}+\braket{G(t)}$.
If $|\braket{F(t)}|\gg|\braket{G(t)}|$, then the error
$\braket{O^{\prime}(t)-O(t)}$ will be changing at a rate much faster than its
growth, which indicates an oscillatory behavior. We numerically found that
this is indeed the case. In Fig. 2, we compare the magnitude of the
oscillation part $|\braket{F(t)}|$ and the growth part $|\braket{G(t)}|$. We
can see from the figure that $|\braket{F(t)}|\gg|\braket{G(t)}|$, which
explains the rapid oscillation we see in Fig. 1. In particular, in the
parameter setup of Fig. 1, we applied a large $X$-field whose strength is ten
times the coupling constants. This $X$-field only contributes to $F(t)$ but
not $G(t)$, which resulted in $|\braket{F(t)}|\gg|\braket{G(t)}|$. When we
decrease the $X$-field strength the oscillation frequency decreases
accordingly, as can be seen from the right panel of Fig. 2.