11institutetext: National Key Laboratory for Novel Software Technology,
Nanjing University, China
11email<EMAIL_ADDRESS><EMAIL_ADDRESS>22institutetext:
Samsung Research America, Mountain View CA, USA
22email<EMAIL_ADDRESS>
# ESBM: An Entity Summarization BenchMark

Qingxia Liu 11 Gong Cheng 11 Kalpa Gunaratna 22 Yuzhong Qu 11

###### Abstract

Entity summarization is the problem of computing an optimal compact summary
for an entity by selecting a size-constrained subset of triples from RDF data.
Entity summarization supports a multiplicity of applications and has led to
fruitful research. However, there is a lack of evaluation efforts that cover
the broad spectrum of existing systems. One reason is a lack of benchmarks for
evaluation. Some benchmarks are no longer available, while others are small
and have limitations. In this paper, we create an Entity Summarization
BenchMark (ESBM) which overcomes the limitations of existing benchmarks and
meets standard desiderata for a benchmark. Using this largest available
benchmark for evaluating general-purpose entity summarizers, we perform the
most extensive experiment to date where 9 existing systems are compared.
Considering that all of these systems are unsupervised, we also implement and
evaluate a supervised learning based system for reference.

###### Keywords:

Entity summarization Triple ranking Benchmarking.

##  1 Introduction

RDF data describes entities with triples representing property values. In an
RDF dataset, the description of an entity comprises all the RDF triples where
the entity appears as the subject or the object. An example entity description
is shown in Fig. 1. Entity descriptions can be large. An entity may be
described in dozens or hundreds of triples, exceeding the capacity of a
typical user interface. A user served with all of those triples may suffer
information overload and find it difficult to quickly identify the small set
of triples that are truly needed. To solve the problem, an established
research topic is _entity summarization_ [15], which aims to compute an
optimal compact summary for the entity by selecting a size-constrained subset
of triples. An example entity summary under the size constraint of 5 triples
is shown in the bottom right corner of Fig. 1.

Figure 1: Description of entity Tim Berners-Lee and a summary thereof.

Entity summarization supports a multiplicity of applications [6, 21]. Entity
summaries constitute entity cards displayed in search engines [9], provide
background knowledge for enriching documents [26], and facilitate research
activities with humans in the loop [3, 4]. This far-reaching application has
led to fruitful research as reviewed in our recent survey paper [15]. Many
entity summarizers have been developed, most of which generate summaries for
general purposes.

Research Challenges. However, two challenges face the research community.
First, there is a _lack of benchmarks_ for evaluating entity summarizers. As
shown in Table 1, some benchmarks are no longer available. Others are
available [22, 7, 8] but they are small and have limitations. Specifically,
[22] has a task-specific nature, and [7, 8] exclude classes and/or literals.
These benchmarks could not support a comprehensive evaluation of general-
purpose entity summarizers. Second, there is a _lack of evaluation efforts_
that cover the broad spectrum of existing systems to compare their performance
and assist practitioners in choosing solutions appropriate to their
applications.

Contributions. We address the challenges with two contributions. First, we
create an Entity Summarization BenchMark (ESBM) which overcomes the
limitations of existing benchmarks and meets the desiderata for a successful
benchmark [18]. ESBM has been published on GitHub with extended documentation
and a permanent identifier on w3id.org111https://w3id.org/esbm under the ODC-
By license. As the largest available benchmark for evaluating general-purpose
entity summarizers, ESBM contains 175 heterogeneous entities sampled from two
datasets, for which 30 human experts create 2,100 general-purpose ground-truth
summaries under two size constraints. Second, using ESBM, we evaluate 9
existing general-purpose entity summarizers. It represents the most extensive
evaluation effort to date. Considering that existing systems are unsupervised,
we also implement and evaluate a supervised learning based entity summarizer
for reference.

In this paper, for the first time we comprehensively describe the creation and
use of ESBM. We report ESBM v1.2—the latest version, while early versions have
successfully supported the entity summarization shared task at the EYRE 2018
workshop222https://sites.google.com/view/eyre18/sharedtasks and the EYRE 2019
workshop.333https://sites.google.com/view/eyre19/sharedtasks We will also
educate on the use of ESBM at an ESWC 2020 tutorial on entity
summarization444https://sites.google.com/view/entity-summarization-
tutorials/eswc2020.

The remainder of the paper is organized as follows. Section 2 reviews related
work and limitations of existing benchmarks. Section 3 describes the creation
of ESBM, which is analyzed in Section 4. Section 5 presents our evaluation. In
Section 6 we discuss limitations of our study and perspectives for future
work.

Table 1: Existing benchmarks for evaluating entity summarization. | Dataset | Number of entities | Availability
---|---|---|---
WhoKnows?Movies! [22] | Freebase | 60 | Available111http://yovisto.com/labs/iswc2012
Langer et al. [13] | DBpedia | 14 | Unavailable
FRanCo [1] | DBpedia | 265 | Unavailable
Benchmark for evaluating RELIN [2] | DBpedia | 149 | Unavailable
Benchmark for evaluating DIVERSUM [20] | IMDb | 20 | Unavailable
Benchmark for evaluating FACES [7] | DBpedia | 50 | Available222http://wiki.knoesis.org/index.php/FACES
Benchmark for evaluating FACES-E [8] | DBpedia | 80 | Available222http://wiki.knoesis.org/index.php/FACES

##  2 Related Work

We review methods and evaluation efforts for entity summarization.

Methods for Entity Summarization. In a recent survey [15] we have categorized
the broad spectrum of research on entity summarization. Below we briefly
review _general-purpose_ entity summarizers which mainly rely on generic
technical features that can apply to a wide range of domains and applications.
We will not address methods that are domain-specific (e.g., for movies [25] or
timelines [5]), task-specific (e.g., for facilitating entity resolution [3] or
entity linking [4]), or context-aware (e.g., contextualized by a document [26]
or a query [9]).

RELIN [2] uses a weighted PageRank model to rank triples according to their
statistical informativeness and relatedness. DIVERSUM [20] ranks triples by
property frequency and generates a summary with a strong constraint that
avoids selecting triples having the same property. SUMMARUM [24] and LinkSUM
[23] mainly rank triples by the PageRank scores of property values that are
entities. LinkSUM also considers backlinks from values. FACES [7], and its
extension FACES-E [8] which adds support for literals, cluster triples by
their bag-of-words based similarity and choose top-ranked triples from as many
different clusters as possible. Triples are ranked by statistical
informativeness and property value frequency. CD [28] models entity
summarization as a quadratic knapsack problem that maximizes the statistical
informativeness of the selected triples and in the meantime minimizes the
string, numerical, and logical similarity between them. In ES-LDA [17], ES-
LDAext [16], and MPSUM [27], a Latent Dirichlet Allocation (LDA) model is
learned where properties are treated as topics, and each property is a
distribution over all the property values. Triples are ranked by the
probabilities of properties and values. MPSUM further avoids selecting triples
having the same property. BAFREC [12] categorizes triples into meta-level and
data-level. It ranks meta-level triples by their depths in an ontology and
ranks data-level triples by property and value frequency. Triples having
textually similar properties are penalized to improve diversity. KAFCA [11]
ranks triples by the depths of properties and values in a hierarchy
constructed by performing the Formal Concept Analysis (FCA). It tends to
select triples containing infrequent properties but frequent values, where
frequency is computed at the word level.

Limitations of Existing Benchmarks. For evaluating entity summarization,
compared with task completion based _extrinsic evaluation_ , ground truth
based _intrinsic evaluation_ is more popular because it is easy to perform and
the results are reproducible. Its idea is to create a benchmark consisting of
human-made ground-truth summaries, and then compute how much a machine-
generated summary is close to a ground-truth summary.

Table 1 lists known benchmarks, including dedicated benchmarks [22, 13, 1] and
those created for evaluating a particular entity summarizer [2, 20, 7, 8]. It
is not surprising that these benchmarks are not very large since it is
expensive to manually create high-quality summaries for a large set of
entities. Unfortunately, some of these benchmarks are not publicly available
at this moment. Three are available [22, 7, 8] but they are relatively small
and have limitations. Specifically, WhoKnows?Movies! [22] is not a set of
ground-truth summaries but annotates each triple with the ratio of movie
questions that were correctly answered based on that triple, as an indicator
of its importance. This kind of task-specific ground truth may not be suitable
for evaluating general-purpose entity summarizers. The other two available
benchmarks were created for evaluating FACES/-E [7, 8]. Classes and/or
literals are not included because they could not be processed by FACES/-E and
hence were filtered out. Such benchmarks could not comprehensively evaluate
most of the existing entity summarizers [2, 20, 28, 27, 12, 11] that can
handle classes and literals. These limitations of available benchmarks
motivated us to create a new ground truth consisting of _general-purpose
summaries_ for a _larger set of entities_ involving _more comprehensive
triples_ where property values can be entities, classes, or literals.

##  3 Creating ESBM

To overcome the above-mentioned limitations of existing benchmarks, we created
a new benchmark called ESBM. To date, it is the largest available benchmark
for evaluating general-purpose entity summarizers. In this section, we will
first specify our design goals. Then we describe the selection of entity
descriptions and the creation of ground-truth summaries. We partition the data
to support cross-validation for parameter fitting. Finally we summarize how
our design goals are achieved and how ESBM meets standard desiderata for a
benchmark.

###  3.1 Design Goals

The creation of ESBM has two main design goals. First, a successful benchmark
should meet seven desiderata [18]: accessibility, affordability, clarity,
relevance, solvability, portability, and scalability, which we will detail in
Section 3.5. Our design of ESBM aims to satisfy these basic requirements.
Second, in Section 2 we discussed the limitations of available benchmarks,
including task specificness, small size, and triple incomprehensiveness.
Besides, all the existing benchmarks use a single dataset and hence may weaken
the generalizability of evaluation results. We aim to overcome these
limitations when creating ESBM. In Section 3.5 we will summarize how our
design goals are achieved.

###  3.2 Entity Descriptions

To choose entity descriptions to summarize, we sample entities from selected
datasets and filter their triples. The process is detailed below.

Datasets. We sample entities from two datasets of different kinds: an
encyclopedic dataset and a domain-specific dataset. For the encyclopedic
dataset we choose DBpedia [14], which has been used in other benchmarks [13,
1, 2, 7, 8]. We use the English version of DBpedia
2015-10555http://wiki.dbpedia.org/dbpedia-dataset-version-2015-10—the latest
version when we started to create ESBM. For the domain-specific dataset we
choose LinkedMDB [10], which is a popular movie database. The movie domain is
also the focus of some existing benchmarks [22, 20] possibly because this
domain is familiar to the lay audience so that it would be easy to find
qualified human experts to create ground-truth summaries. We use the latest
available version of
LinkedMDB.666http://www.cs.toronto.edu/~oktie/linkedmdb/linkedmdb-latest-
dump.zip

Entities. For DBpedia we sample entities from five large classes: Agent,
Event, Location, Species, and Work. They collectively contain 3,501,366
entities (60%) in the dataset. For LinkedMDB we sample from Film and Person,
which contain 159,957 entities (24%) in the dataset. Entities from different
classes are described by very different properties as we will see in Section
4.3, and hence help to assess the generalizability of an entity summarizer.
According to the human efforts we could afford, from each class we randomly
sample 25 entities. The total number of selected entities is 175. Each
selected entity should be described in at least 20 triples so that
summarization would not be a trivial task. This requirement follows common
practice in the literature [1, 2, 20, 7] where a minimum constraint in the
range of 10–20 was posed.

(a) Average number of triples describing an entity.

(b) Average number of distinct properties describing an entity.

Figure 2: Composition of entity descriptions (the left bar in each group),
top-5 ground-truth summaries (the middle bar), and top-10 ground-truth
summaries (the right bar), grouped by class in DBpedia (D) and LinkedMDB (L).

Triples. For DBpedia, entity descriptions comprise triples in the following
dump files: _instance types_ , _instance types transitive_ , _YAGO types_ ,
_mappingbased literals_ , _mappingbased objects_ , _labels_ , _images_ ,
_homepages_ , _persondata_ , _geo coordinates mappingbased_ , and _article
categories_. We do not import dump files that provide metadata about Wikipedia
articles such as _page links_ and _page length_. We do not import _short
abstracts_ and _long abstracts_ as they provide handcrafted textual entity
summaries; it would be inappropriate to include them in a benchmark for
evaluating entity summarization. For LinkedMDB we import all the triples in
the dump file except sameAs links which do not express facts about entities
but are of more technical nature. Finally, as shown in Fig. 2a (the left bar
in each group), the mean number of triples in an entity description is in the
range of 25.88–52.44 depending on the class, and the overall mean value is
37.62.

###  3.3 Ground-Truth Summaries

We invite 30 researchers and students to create ground-truth summaries for
entity descriptions. All the participants are familiar with RDF.

Task Assignment. Each participant is assigned 35 entities consisting of 5
entities randomly selected from each of the 7 classes in ESBM. The assignment
is controlled to ensure that each entity in ESBM is processed by 6
participants. A participant creates two summaries for each entity description
by selecting different numbers of triples: a _top-5 summary_ containing 5
triples, and a _top-10 summary_ containing 10 triples. Therefore, we will be
able to evaluate entity summarizers under different size constraints. The
choice of these two numbers follows previous work [2, 7, 8]. Participants work
independently and they may create different summaries for an entity. It is not
feasible to ask participants to reach an agreement. It is also not reasonable
to merge different summaries into a single version. So we keep different
summaries and will use all of them in the evaluation. The total number of
ground-truth summaries is $175\cdot 6\cdot 2=2,100$.

Figure 3: User interface for creating ground-truth entity summaries.

Procedure. Participants are instructed to create _general-purpose summaries_
that are not specifically created for any particular task. They read and
select triples using a Web-based user interface shown in Fig. 3. All the
triples in an entity description are listed in random order but those having a
common property are placed together for convenient reading and comparison. For
IRIs, their human-readable labels (rdfs:label) are shown if available. To help
participants understand a property value that is an unfamiliar entity, a click
on it will open a pop-up showing a short textual description extracted from
the first paragraph of its Wikipedia/IMDb page. Any triple can be selected
into the top-5 summary, the top-10 summary, or both. The top-5 summary is not
required to be a subset of the top-10 summary.

###  3.4 Training, Validation, and Test Sets

Some entity summarizers need to tune hyperparameters or fit models. To make
their evaluation results comparable with each other, we specify a split of our
data into training, validation, and test sets. We provide a partition of the
175 entities in ESBM into 5 equally sized subsets $P_{0},\ldots,P_{4}$ to
support 5-fold cross-validation. Entities of each class are partitioned evenly
among the subsets. For $0\leq i\leq 4$, the $i$-th fold uses
$P_{i},P_{i+1\text{ mod }5},P_{i+2\text{ mod }5}$ as the training set (e.g.,
for model fitting), uses $P_{i+3\text{ mod }5}$ for validation (e.g., tuning
hyperparameters), and retains $P_{i+4\text{ mod }5}$ as the test set.
Evaluation results are averaged over the 5 folds.

###  3.5 Conclusion

ESBM overcomes the limitations of available benchmarks discussed in Section 2.
It contains 175 entities which is 2–3 times as large as available benchmarks
[22, 7, 8]. In ESBM, property values are not filtered as in [7, 8] but can be
any entity, class, or literal. Different from the task-specific nature of
[22], ESBM provides general-purpose ground-truth summaries for evaluating
general-purpose entity summarizers.

Besides, ESBM meets the seven desiderata proposed in [18] as follows.

  * •

Accessibility. ESBM is publicly available and has a permanent identifier on
w3id.org.

  * •

Affordability. ESBM is with an open-source program and example code for
evaluation. The cost of using ESBM is minimized.

  * •

Clarity. ESBM is documented clearly and concisely.

  * •

Relevance. ESBM samples entities from two real datasets that have been widely
used. The summarization tasks are natural and representative.

  * •

Solvability. An entity description in ESBM has at least 20 triples and a mean
number of 37.62 triples, from which 5 or 10 triples are to be selected. The
summarization tasks are not trivial and not too difficult.

  * •

Portability. ESBM can be used to evaluate any general-purpose entity
summarizer that can process RDF data.

  * •

Scalability. ESBM samples 175 entities from 7 classes. It is reasonably large
and diverse to evaluate mature entity summarizers but is not too large to
evaluate research prototypes.

However, ESBM has its own limitations, which we will discuss in Section 6.

##  4 Analyzing ESBM

In this section, we will first characterize ESBM by providing some basic
statistics and analyzing the triple composition and heterogeneity of entity
descriptions. Then we compute inter-rater agreement to show how much consensus
exists in the ground-truth summaries given by different participants.

###  4.1 Basic Statistics

The 175 entity descriptions in ESBM collectively contain 6,584 triples, of
which 37.44% are selected into at least one top-5 summary and 58.15% appear in
at least one top-10 summary, showing a wide selection by the participants.
However, many of them are selected only by a single participant; 20.46% and
40.23% are selected by different participants into top-5 and top-10 summaries,
respectively. We will further analyze inter-rater agreement in Section 4.4.

We calculate the overlap between the top-5 and the top-10 summaries created by
the same participant for the same entity. The mean overlap is in the range of
4.80–4.99 triples depending on the class, and the overall mean value is 4.91,
showing that the top-5 summary is usually a subset of the top-10 summary.

###  4.2 Triple Composition

In Fig. 2 we present the composition of entity descriptions (the left bar in
each group) and their ground-truth summaries (the middle bar for top-5 and the
right bar for top-10) in ESBM, in terms of the average number of triples
describing an entity (Fig. 2a) and in terms of the average number of distinct
properties describing an entity (Fig. 2b). Properties are divided into
literal-valued, class-valued, and entity-valued. Triples are divided
accordingly.

In Fig. 2a, both class-valued and entity-valued triples occupy a considerable
proportion of the entity descriptions in DBpedia. Entity-valued triples
predominate in LinkedMDB. Literal-valued triples account for a small
proportion in both datasets. However, they constitute 30% in top-5 ground-
truth summaries and 25% in top-10 summaries. Entity summarizers that cannot
process literals [24, 23, 7, 17] have to ignore these notable proportions,
thereby significantly influencing their performance.

In Fig. 2b, in terms of distinct properties, entity-valued and literal-valued
triples have comparable numbers in entity descriptions since many entity-
valued properties are multi-valued. Specifically, an entity is described by
13.24 distinct properties, including 5.31 literal-valued (40%) and 6.93
entity-valued (52%). Multi-valued properties appear in every entity
description and they constitute 35% of the triples. However, in top-5 ground-
truth summaries, the average number of distinct properties is 4.70 and is very
close to 5, indicating that the participants are not inclined to select
multiple values of a property. Entity summarizers that prefer diverse
properties [20, 7, 8, 28, 27, 12] may exhibit good performance.

Figure 4: Jaccard similarity between property sets describing different
classes. Table 2: Popular properties in ground-truth summaries.

In top-5 summaries | In top-10 summaries
---|---
Agent | Event | Location | Species | Work | Film | Person | Agent | Event | Location | Species | Work | Film | Person
type | type | type | type | type | director | type | type | type | type | family | type | director | type
birthDate | date | country | family |  | type | actor | subject | subject | country | type | subject | actor | actor
|  |  |  |  |  |  | birthDate | date | subject | order | genre | type | label
|  |  |  |  |  |  |  | label |  | class |  | writer | page
|  |  |  |  |  |  |  |  |  | genus |  | producer |
|  |  |  |  |  |  |  |  |  | subject |  | date |
|  |  |  |  |  |  |  |  |  | kingdom |  | language |

###  4.3 Entity Heterogeneity

Entities from different classes are described by different sets of properties.
For each class we identify the set of properties describing at least one
entity from the class. The Jaccard similarity between properties sets for each
pair of classes is very low, as shown in Fig. 4. Such heterogeneous entity
descriptions help to assess the generalizability of an entity summarizer.

Table 2 shows popular properties that appear in at least 50% of the ground-
truth summaries for each class. Some universal properties like rdf:type and
dct:subject are popular for most classes. We also see class-specific
properties, e.g., dbo:birthDate for Agent, dbo:family for Species. However,
the results suggest that it would be unrealistic to generate good summaries by
manually selecting properties for each class. For example, among 13.24
distinct properties describing an entity, only 1–2 are popular in top-5
ground-truth summaries. The importance of properties is generally
contextualized by concrete entities.

###  4.4 Inter-Rater Agreement

Recall that each entity in ESBM has six top-5 ground-truth summaries and six
top-10 summaries created by different participants. We calculate the average
overlap between these summaries in terms of the number of common triples they
contain. As shown in Table 3, the results are generally comparable with those
reported for other benchmarks in the literature. There is a moderate degree of
agreement between the participants.

Table 3: Inter-rater agreement. | ESBM | [2] | [7] | [8]
---|---|---|---|---
Overlap between top-5 summaries | 1.99 (39.8$\%$) | 2.91 (58.2$\%$) | 1.92 (38.4$\%$) | 2.12 (42.4$\%$)
Overlap between top-10 summaries | 5.42 (54.2$\%$) | 7.86 (78.6$\%$) | 4.64 (46.4$\%$) | 5.44 (54.4$\%$)
Ground-truth summaries per entity | 6 | 4.43 |  $\geq$ 7 |  $\geq$ 4

##  5 Evaluating with ESBM

We used ESBM to perform the most extensive evaluation of general-purpose
entity summarizers to date. In this section, we will first describe evaluation
criteria. Then we introduce the entity summarizers that we evaluate. Finally
we present evaluation results.

###  5.1 Evaluation Criteria

Let $S_{m}$ be a machine-generated entity summary. Let $S_{h}$ be a human-made
ground-truth summary. To compare $S_{m}$ with $S_{h}$ and assess the quality
of $S_{m}$ based on how much $S_{m}$ is close to $S_{h}$, it is natural to
compute precision (P), recall (R), and F1. The results are in the range of
0–1:

$\text{P}=\frac{|S_{m}\cap S_{h}|}{|S_{m}|}\,,\quad\text{R}=\frac{|S_{m}\cap
S_{h}|}{|S_{h}|}\,,\quad\text{F1}=\frac{2\cdot\text{P}\cdot\text{R}}{\text{P}+\text{R}}\,.$
(1)

In the experiments we configure entity summarizers to output at most $k$
triples and we set $k=|S_{h}|$, i.e., $k=5$ and $k=10$ are our two settings
corresponding to the sizes of ground-truth summaries. We will trivially have
P$=$R$=$F1 if $|S_{m}|=|S_{h}|$. However, some entity summarizers may output
less than $k$ triples. For example, DIVERSUM [20] disallows an entity summary
to contain triples having the same property. It is possible that an entity
description contains less than $k$ distinct properties and hence DIVERSUM has
to output less than $k$ triples. In this case, P$\neq$R and one should rely on
F1.

In the evaluation, for each entity in ESBM, we compare a machine-generated
summary with each of the 6 ground-truth summaries by calculating F1, and take
their aggregation value. Finally we report the mean F1 over all the entities.
For aggregation function, we report the results of average, to show an overall
match with all the different ground truths; on the website we also give the
results of maximum, to show the best match with each individual ground truth.

###  5.2 Participating Entity Summarizers

We not only evaluate existing entity summarizers but also compare them with
two special entity summarizers we create: an oracle entity summarizer which is
used to show the best possible performance on ESBM, and a new supervised
learning based entity summarizer.

Existing Entity Summarizers. We evaluate 9 out of the 12 general-purpose
entity summarizers reviewed in Section 2. We re-implement RELIN [2], DIVERSUM
[20], LinkSUM [23], FACES [7], FACES-E [8], and CD [28], while MPSUM [27],
BAFREC [12], and KAFCA [11] are open source. We exclude SUMMARUM [24], ES-LDA
[17], and ES-LDAext [16] because LinkSUM represents an extension of SUMMARUM,
and MPSUM represents an extension of ES-LDA and ES-LDAext.

We follow the original implementation and suggested configuration of existing
entity summarizers as far as possible. However, for RELIN, we replace its
Google-based relatedness measure with a string metric [19] because Google’s
search API is no longer free. We also use this metric to replace the
unavailable UMBC’s SimService used in FACES-E. For DIVERSUM, we ignore its
witness count measure since it does not apply to ESBM. For LinkSUM, we obtain
backlinks between entities in LinkedMDB via their corresponding entities in
DBpedia.

RELIN, CD, and LinkSUM compute a weighted combination of two scoring
components. We tune these hyperparameters in the range of 0–1 in 0.01
increments. Since these summarizers are unsupervised, we use both the training
set and the validation set described in Section 3.4 for tuning
hyperparameters.

Oracle Entity Summarizer. We implement an entity summarizer denoted by ORACLE
to approximate the best possible performance on ESBM and form a reference
point used for comparisons. ORACLE simply outputs $k$ triples that are
selected by the most participants into ground-truth summaries.

Supervised Learning Based Entity Summarizer. Existing general-purpose entity
summarizers are unsupervised. We implement a supervised learning based entity
summarizer with features that are used by existing entity summarizers. A
triple with property $p$ and value $v$ describing entity $e$ is represented by
the following features:

  * •

$\mathtt{gf}_{\mathbb{T}}$: the number of triples in the dataset where $p$
appears [23, 12],

  * •

$\mathtt{lf}$: the number of triples in the description of $e$ where $p$
appears [20, 23],

  * •

$\mathtt{vf}_{\mathbb{T}}$: the number of triples in the dataset where $v$
appears [7, 8, 12], and

  * •

$\mathtt{si}$: the self-information of the triple [2, 7, 8, 28].

We also add three binary features:

  * •

$\mathtt{isC}$: whether $v$ is a class,

  * •

$\mathtt{isE}$: whether $v$ is an entity, and

  * •

$\mathtt{isL}$: whether $v$ is a literal.

Based on the training and validation sets described in Section 3.4, we
implement and tune 6 pointwise learning to rank models provided by Weka:
SMOreg, LinearRegression, MultilayerPerceptron, AdditiveRegression, REPTree,
and RandomForest. Each model outputs $k$ top-ranked triples as a summary.

###  5.3 Evaluation Results

We first report the overall evaluation results to show which entity summarizer
generally performs better. Then we break down the results into different
entity types (i.e., classes) for detailed comparison. Finally we present and
analyze the performance of our supervised learning based entity summarizer.

Table 4: Average F1 over all the entities in a dataset. For the nine existing
entity summarizers, significant improvements and losses over each other are
indicated by $\blacktriangle$ and $\blacktriangledown$ ($p<0.05$),
respectively. Insignificant differences are indicated by $\circ$.

| DBpedia | LinkedMDB
---|---|---
| $k=5$ | $k=10$ | $k=5$ | $k=10$
RELIN | 0.242 ${}^{\text{-}\circ\circ\blacktriangledown\blacktriangledown\blacktriangledown\blacktriangledown\blacktriangledown\blacktriangledown}$ | 0.455 ${}^{\text{-}\blacktriangledown\circ\circ\blacktriangledown\circ\blacktriangledown\blacktriangledown\blacktriangledown}$ | 0.203 ${}^{\text{-}\circ\circ\blacktriangledown\circ\blacktriangle\blacktriangledown\circ\blacktriangledown}$ | 0.258 ${}^{\text{-}\blacktriangledown\circ\blacktriangledown\blacktriangledown\circ\blacktriangledown\blacktriangledown\blacktriangledown}$
DIVERSUM | 0.249 ${}^{\circ\text{-}\circ\circ\blacktriangledown\blacktriangledown\blacktriangledown\blacktriangledown\blacktriangledown}$ | 0.507 ${}^{\blacktriangle\text{-}\blacktriangle\circ\circ\circ\circ\circ\circ}$ | 0.207 ${}^{\circ\text{-}\circ\blacktriangledown\circ\blacktriangle\blacktriangledown\circ\blacktriangledown}$ | 0.358 ${}^{\blacktriangle\text{-}\blacktriangle\circ\circ\blacktriangle\blacktriangledown\circ\blacktriangledown}$
FACES | 0.270 ${}^{\circ\circ\text{-}\circ\circ\circ\blacktriangledown\blacktriangledown\blacktriangledown}$ | 0.428 ${}^{\circ\blacktriangledown\text{-}\blacktriangledown\blacktriangledown\blacktriangledown\blacktriangledown\blacktriangledown\blacktriangledown}$ | 0.169 ${}^{\circ\circ\text{-}\blacktriangledown\blacktriangledown\circ\blacktriangledown\blacktriangledown\blacktriangledown}$ | 0.263 ${}^{\circ\blacktriangledown\text{-}\blacktriangledown\blacktriangledown\circ\blacktriangledown\blacktriangledown\blacktriangledown}$
FACES-E | 0.280 ${}^{\blacktriangle\circ\circ\text{-}\circ\circ\blacktriangledown\blacktriangledown\blacktriangledown}$ | 0.488 ${}^{\circ\circ\blacktriangle\text{-}\circ\circ\circ\circ\circ}$ | 0.313 ${}^{\blacktriangle\blacktriangle\blacktriangle\text{-}\blacktriangle\blacktriangle\blacktriangledown\blacktriangle\circ}$ | 0.393 ${}^{\blacktriangle\circ\blacktriangle\text{-}\blacktriangle\blacktriangle\circ\circ\circ}$
CD | 0.283 ${}^{\blacktriangle\blacktriangle\circ\circ\text{-}\circ\blacktriangledown\circ\circ}$ | 0.513 ${}^{\blacktriangle\circ\blacktriangle\circ\text{-}\circ\circ\circ\circ}$ | 0.217 ${}^{\circ\circ\blacktriangle\blacktriangledown\text{-}\blacktriangle\blacktriangledown\circ\blacktriangledown}$ | 0.331 ${}^{\blacktriangle\circ\blacktriangle\blacktriangledown\text{-}\blacktriangle\blacktriangledown\blacktriangledown\blacktriangledown}$
LinkSUM | 0.287 ${}^{\blacktriangle\blacktriangle\circ\circ\circ\text{-}\blacktriangledown\circ\circ}$ | 0.486 ${}^{\circ\circ\blacktriangle\circ\circ\text{-}\circ\circ\circ}$ | 0.140 ${}^{\blacktriangledown\blacktriangledown\circ\blacktriangledown\blacktriangledown\text{-}\blacktriangledown\blacktriangledown\blacktriangledown}$ | 0.279 ${}^{\circ\blacktriangledown\circ\blacktriangledown\blacktriangledown\text{-}\blacktriangledown\blacktriangledown\blacktriangledown}$
BAFREC | 0.335 ${}^{\blacktriangle\blacktriangle\blacktriangle\blacktriangle\blacktriangle\blacktriangle\text{-}\circ\circ}$ | 0.503 ${}^{\blacktriangle\circ\blacktriangle\circ\circ\circ\text{-}\circ\circ}$ | 0.360 ${}^{\blacktriangle\blacktriangle\blacktriangle\blacktriangle\blacktriangle\blacktriangle\text{-}\blacktriangle\blacktriangle}$ | 0.402 ${}^{\blacktriangle\blacktriangle\blacktriangle\circ\blacktriangle\blacktriangle\text{-}\circ\circ}$
KAFCA | 0.314 ${}^{\blacktriangle\blacktriangle\blacktriangle\blacktriangle\circ\circ\circ\text{-}\circ}$ | 0.509 ${}^{\blacktriangle\circ\blacktriangle\circ\circ\circ\circ\text{-}\circ}$ | 0.244 ${}^{\circ\circ\blacktriangle\blacktriangledown\circ\blacktriangle\blacktriangledown\text{-}\circ}$ | 0.397 ${}^{\blacktriangle\circ\blacktriangle\circ\blacktriangle\blacktriangle\circ\text{-}\circ}$
MPSUM | 0.314 ${}^{\blacktriangle\blacktriangle\blacktriangle\blacktriangle\circ\circ\circ\circ\text{-}}$ | 0.512 ${}^{\blacktriangle\circ\blacktriangle\circ\circ\circ\circ\circ\text{-}}$ | 0.272 ${}^{\blacktriangle\blacktriangle\blacktriangle\circ\blacktriangle\blacktriangle\blacktriangledown\circ\text{-}}$ | 0.423 ${}^{\blacktriangle\blacktriangle\blacktriangle\circ\blacktriangle\blacktriangle\circ\circ\text{-}}$
ORACLE | 0.595 | 0.713 | 0.619 | 0.678
SMOreg | 0.279 | 0.543 | 0.403 | 0.472
LinearRegression | 0.319 | 0.556 | 0.401 | 0.471
MultilayerPerceptron | 0.340 | 0.560 | 0.390 | 0.477
AdditiveRegression | 0.345 | 0.558 | 0.415 | 0.510
REPTree | 0.392 | 0.570 | 0.455 | 0.538
RandomForest | 0.399 | 0.576 | 0.449 | 0.506

Overall Results of Existing Entity Summarizers. Table 4 presents the results
of all the participating entity summarizers on two datasets under two size
constraints. We compare nine existing summarizers using one-way ANOVA post-hoc
LSD and we show whether the difference between each pair of them is
statistical significant at the 0.05 level. Among existing summarizers, BAFREC
achieves the highest F1 under $k=5$. It significantly outperforms six existing
summarizers on DBpedia and outperforms all the eight ones on LinkedMDB. It is
also among the best under $k=10$. MPSUM follows BAFREC under $k=5$ but
performs slightly better under $k=10$. Other top-tier results belong to KAFCA
on DBpedia and FACES-E on LinkedMDB.

The F1 scores of ORACLE are in the range of 0.595–0.713. It is impossible for
ORACLE or any other summarizer to reach $\text{F1}=1$, because for each entity
in ESBM there are six ground-truth summaries which are often different and
hence cannot simultaneously match a machine-generated summary. However, the
gap between the results of ORACLE and the best results of existing summarizers
is still as large as 0.20–0.26, suggesting that there is much room for
improvement.

Results on Different Entity Types. We break down the results of existing
entity summarizers into 7 entity types (i.e., classes). When $k=5$ in Fig. 5,
there is no single winner on every class, but BAFREC and MPSUM are among top
three on 6 classes, showing relatively good generalizability over different
entity types. Some entity summarizers have limited generalizability and they
perform not well on certain classes. For example, RELIN and CD mainly rely on
the self-information of a triple, while for Location entities their latitudes
and longitudes are often unique in DBpedia but such triples with large self-
information rarely appear in ground-truth summaries. Besides, most summarizers
generate low-quality summaries for Agent, Film, and Person entities. This is
not surprising since these entities are described in more triples and/or by
more properties according to Fig. 2. Their summarization is inherently more
difficult. When $k=10$ in Fig. 6, MPSUM is still among top three on 6 classes.
KAFCA also shows relatively good generalizability—among top three on 5
classes.

Figure 5: Average F1 over all the entities in each class under $k=5$. Figure
6: Average F1 over all the entities in each class under $k=10$.

Results of Supervised Learning. As shown in Table 4, among the six supervised
learning based methods, RandomForest and REPTree achieve the highest F1 on
DBpedia and LinkedMDB, respectively. Four methods (MultilayerPerceptron,
AdditiveRegression, REPTree, and RandomForest) outperform all the existing
entity summarizers on both datasets under both size constraints, and two
methods (SMOreg and LinearRegression) only fail to outperform in one setting.
The results demonstrate the powerfulness of supervised learning for entity
summarization. Further, recall that these methods only use standard models and
rely on features that are used by existing entity summarizers. It would be
reasonable to predict that better results can be achieved with specialized
models and more advanced features. However, creating a large number of ground-
truth summaries for training is expensive, and the generalizability of
supervised methods for entity summarization still needs further exploration.

Moreover, we are interested in how much the seven features contribute to the
good performance of supervised learning. Table 5 shows the results of
RandomForest after removing each individual feature. Considering statistical
significance at the 0.05 level, two features $\mathtt{gf}_{\mathbb{T}}$ and
$\mathtt{lf}$ show effectiveness on both datasets under both size constraints,
and two features $\mathtt{vf}_{\mathbb{T}}$ and $\mathtt{si}$ are only
effective on LinkedMDB. The usefulness of the three binary features
$\mathtt{isC}$, $\mathtt{isE}$, and $\mathtt{isL}$ is not statistically
significant.

Table 5: F1 of RandomForest after removing each individual feature, its
difference from using all features ($\Delta\%$), and the significance level
for the difference ($p$).

DBpedia | LinkedMDB
---|---
$k=5$ | $k=10$ | $k=5$ | $k=10$
| F1 | $\Delta\%$ | $p$ |  | F1 | $\Delta\%$ | $p$ |  | F1 | $\Delta\%$ | $p$ |  | F1 | $\Delta\%$ | $p$
All | 0.399 | — | — | All | 0.576 | — | — | All | 0.449 | — | — | All | 0.506 | — | —
-$\mathtt{gf}_{\mathbb{T}}$ | 0.346 |  $-$5.360 | 0.000 | -$\mathtt{lf}$ | 0.546 |  $-$0.030 | 0.000 | -$\mathtt{gf}_{\mathbb{T}}$ | 0.383 |  $-$0.066 | 0.000 | -$\mathtt{lf}$ | 0.473 |  $-$0.033 | 0.008
-$\mathtt{lf}$ | 0.366 |  $-$3.307 | 0.000 | -$\mathtt{gf}_{\mathbb{T}}$ | 0.551 |  $-$0.025 | 0.000 | -$\mathtt{lf}$ | 0.413 |  $-$0.036 | 0.025 | -$\mathtt{vf}_{\mathbb{T}}$ | 0.477 |  $-$0.029 | 0.010
-$\mathtt{isC}$ | 0.392 |  $-$0.720 | 0.261 | -$\mathtt{vf}_{\mathbb{T}}$ | 0.569 |  $-$0.007 | 0.198 | -$\mathtt{vf}_{\mathbb{T}}$ | 0.414 |  $-$0.035 | 0.022 | -$\mathtt{gf}_{\mathbb{T}}$ | 0.479 |  $-$0.027 | 0.007
-$\mathtt{isE}$ | 0.397 |  $-$0.267 | 0.720 | -$\mathtt{isE}$ | 0.570 |  $-$0.006 | 0.262 | -$\mathtt{si}$ | 0.442 |  $-$0.007 | 0.574 | -$\mathtt{si}$ | 0.486 |  $-$0.020 | 0.009
-$\mathtt{si}$ | 0.400 |  $+$0.027 | 0.973 | -$\mathtt{isC}$ | 0.571 |  $-$0.005 | 0.303 | -$\mathtt{isE}$ | 0.455 |  $+$0.005 | 0.651 | -$\mathtt{isL}$ | 0.491 |  $-$0.015 | 0.079
-$\mathtt{isL}$ | 0.401 |  $+$0.160 | 0.816 | -$\mathtt{si}$ | 0.572 |  $-$0.004 | 0.402 | -$\mathtt{isL}$ | 0.456 |  $+$0.007 | 0.504 | -$\mathtt{isE}$ | 0.492 |  $-$0.014 | 0.148
-$\mathtt{vf}_{\mathbb{T}}$ | 0.407 |  $+$0.720 | 0.346 | -$\mathtt{isL}$ | 0.578 |  $+$0.002 | 0.683 | -$\mathtt{isC}$ | 0.463 |  $+$0.013 | 0.281 | -$\mathtt{isC}$ | 0.514 |  $+$0.008 | 0.396

Conclusion. Among existing entity summarizers, BAFREC generally shows the best
performance on ESBM while MPSUM seems more robust. However, none of them are
comparable with our straightforward implementation of supervised learning,
which in turn is still far away from the best possible performance represented
by ORACLE. Therefore, entity summarization on ESBM is a non-trivial task. We
invite researchers to experiment with new ideas on ESBM.

##  6 Discussion and Future work

We identify the following limitations of our work to be addressed in future
work.

Evaluation Criteria. We compute F1 score in the evaluation, which is based on
common triples but ignores semantic overlap between triples. A triple $t$ in a
machine-generated summary $S$ may partially cover the information provided by
some triple $t^{\prime}$ in the ground-truth summary. It may be reasonable to
not completely penalize $S$ for missing $t^{\prime}$ but give some reward for
the presence of $t$. However, it is difficult to quantify the extent of
penalization for all possible cases, particularly when multiple triples
semantically overlap with each other. In future work, we will explore more
proper evaluation criteria.

Representativeness of Ground Truth. The ground-truth summaries in ESBM are not
supposed to represent the view of the entire user population. They are
intrinsically biased towards their creators. Besides, these ground-truth
summaries are created for general purposes. Accordingly, we use them to
evaluate general-purpose entity summarizers. However, for a specific task,
these summaries may not show optimality, and the participating systems may not
represent the state of the art. Still, we believe it is valuable to evaluate
general-purpose systems not only because of their wide range of applications
but also because their original technical features have been reused by task-
specific systems. In future work, we will extend ESBM to a larger scale, and
will consider benchmarking task-specific entity summarization.

Form of Ground Truth. ESBM provides ground-truth summaries, whereas some other
benchmarks offer ground-truth scores of triples [22, 13, 1]. Scoring-based
ground truth may more comprehensively evaluate an entity summarizer than our
set-based ground truth because it not only considers the triples in a machine-
generated summary but also assesses the rest of the triples. However, on the
other hand, a set of top-scored triples may not equal an optimal summary
because they may cover limited aspects of an entity and show redundancy.
Therefore, both methods have their advantages and disadvantages. In future
work, we will conduct scoring-based evaluation to compare with the current
results.

## Acknowledgments

This work was supported in part by the NSFC under Grant 61772264 and in part
by the Qing Lan Program of Jiangsu Province.

## References

  * [1] Bobic, T., Waitelonis, J., Sack, H.: FRanCo - A ground truth corpus for fact ranking evaluation. In: SumPre 2015 & HSWI 2015 (2015)
  * [2] Cheng, G., Tran, T., Qu, Y.: RELIN: relatedness and informativeness-based centrality for entity summarization. In: ISWC 2011, Part I. pp. 114–129 (2011). https://doi.org/10.1007/978-3-642-25073-6_8
  * [3] Cheng, G., Xu, D., Qu, Y.: C3D+P: A summarization method for interactive entity resolution. J. Web Sem. 35, 203–213 (2015). https://doi.org/10.1016/j.websem.2015.05.004
  * [4] Cheng, G., Xu, D., Qu, Y.: Summarizing entity descriptions for effective and efficient human-centered entity linking. In: WWW 2015. pp. 184–194 (2015). https://doi.org/10.1145/2736277.2741094
  * [5] Gottschalk, S., Demidova, E.: EventKG - the hub of event knowledge on the web \- and biographical timeline generation. Semantic Web 10(6), 1039–1070 (2019). https://doi.org/10.3233/SW-190355
  * [6] Gunaratna, K.: Semantics-based Summarization of Entities in Knowledge Graphs. Ph.D. thesis, Wright State University (2017)
  * [7] Gunaratna, K., Thirunarayan, K., Sheth, A.P.: FACES: diversity-aware entity summarization using incremental hierarchical conceptual clustering. In: AAAI 2015. pp. 116–122 (2015)
  * [8] Gunaratna, K., Thirunarayan, K., Sheth, A.P., Cheng, G.: Gleaning types for literals in RDF triples with application to entity summarization. In: ESWC 2016. pp. 85–100 (2016). https://doi.org/10.1007/978-3-319-34129-3_6
  * [9] Hasibi, F., Balog, K., Bratsberg, S.E.: Dynamic factual summaries for entity cards. In: SIGIR 2017. pp. 773–782 (2017). https://doi.org/10.1145/3077136.3080810
  * [10] Hassanzadeh, O., Consens, M.P.: Linked movie data base. In: LDOW 2009 (2009)
  * [11] Kim, E.K., Choi, K.S.: Entity summarization based on formal concept analysis. In: EYRE 2018 (2018)
  * [12] Kroll, H., Nagel, D., Balke, W.T.: BAFREC: Balancing frequency and rarity for entity characterization in linked open data. In: EYRE 2018 (2018)
  * [13] Langer, P., Schulze, P., George, S., Kohnen, M., Metzke, T., Abedjan, Z., Kasneci, G.: Assigning global relevance scores to DBpedia facts. In: ICDE Workshops 2014. pp. 248–253 (2014). https://doi.org/10.1109/ICDEW.2014.6818334
  * [14] Lehmann, J., Isele, R., Jakob, M., Jentzsch, A., Kontokostas, D., Mendes, P.N., Hellmann, S., Morsey, M., van Kleef, P., Auer, S., Bizer, C.: DBpedia - A large-scale, multilingual knowledge base extracted from Wikipedia. Semantic Web 6(2), 167–195 (2015). https://doi.org/10.3233/SW-140134
  * [15] Liu, Q., Cheng, G., Gunaratna, K., Qu, Y.: Entity summarization: State of the art and future challenges. CoRR abs/1910.08252 (2019), http://arxiv.org/abs/1910.08252
  * [16] Pouriyeh, S.A., Allahyari, M., Kochut, K., Cheng, G., Arabnia, H.R.: Combining word embedding and knowledge-based topic modeling for entity summarization. In: ICSC 2018. pp. 252–255 (2018). https://doi.org/10.1109/ICSC.2018.00044
  * [17] Pouriyeh, S.A., Allahyari, M., Kochut, K., Cheng, G., Arabnia, H.R.: ES-LDA: entity summarization using knowledge-based topic modeling. In: IJCNLP 2017, Volume 1. pp. 316–325 (2017)
  * [18] Sim, S.E., Easterbrook, S.M., Holt, R.C.: Using benchmarking to advance research: A challenge to software engineering. In: ICSE 2003. pp. 74–83 (2003). https://doi.org/10.1109/ICSE.2003.1201189
  * [19] Stoilos, G., Stamou, G.B., Kollias, S.D.: A string metric for ontology alignment. In: ISWC 2005. pp. 624–637 (2005). https://doi.org/10.1007/11574620_45
  * [20] Sydow, M., Pikula, M., Schenkel, R.: The notion of diversity in graphical entity summarisation on semantic knowledge graphs. J. Intell. Inf. Syst. 41(2), 109–149 (2013). https://doi.org/10.1007/s10844-013-0239-6
  * [21] Thalhammer, A.: Linked Data Entity Summarization. Ph.D. thesis, Karlsruher Institut für Technologie (2017)
  * [22] Thalhammer, A., Knuth, M., Sack, H.: Evaluating entity summarization using a game-based ground truth. In: ISWC 2012, Part II. pp. 350–361 (2012). https://doi.org/10.1007/978-3-642-35173-0_24
  * [23] Thalhammer, A., Lasierra, N., Rettinger, A.: LinkSUM: Using link analysis to summarize entity data. In: ICWE 2016. pp. 244–261 (2016). https://doi.org/10.1007/978-3-319-38791-8_14
  * [24] Thalhammer, A., Rettinger, A.: Browsing DBpedia entities with summaries. In: ESWC 2014 Satellite Events. pp. 511–515 (2014). https://doi.org/10.1007/978-3-319-11955-7_76
  * [25] Thalhammer, A., Toma, I., Roa-Valverde, A.J., Fensel, D.: Leveraging usage data for linked data movie entity summarization. In: USEWOD 2012 (2012)
  * [26] Tonon, A., Catasta, M., Prokofyev, R., Demartini, G., Aberer, K., Cudré-Mauroux, P.: Contextualized ranking of entity types based on knowledge graphs. J. Web Sem. 37-38, 170–183 (2016). https://doi.org/10.1016/j.websem.2015.12.005
  * [27] Wei, D., Gao, S., Liu, Y., Liu, Z., Huang, L.: MPSUM: Entity summarization with predicate-based matching. In: EYRE 2018 (2018)
  * [28] Xu, D., Zheng, L., Qu, Y.: CD at ENSEC 2016: Generating characteristic and diverse entity summaries. In: SumPre 2016 (2016)


that the single-qubit rotation $R(\theta)$ can be interpreted as a block
encoding of the signal $x$ since $\left\langle
0\right|R(\theta)\left|0\right\rangle=x$. Ref. [57] showed that the first
diagonal matrix element of the unitary resulting from a $k-$fold iteration of
$G(\phi_{i})R(\theta)$ can be designed to be any degree $k$ complex-valued
fixed-parity polynomial $P(x)$ via a judicious choice of the angles
$\phi_{i}$. Formally,

$\displaystyle\mathcal{U}_{s}\equiv\left[\prod_{i=1}^{k}G(\phi_{i})R(\theta)\right]G(\phi_{0})$
$\displaystyle=\left(\begin{array}[]{cc}P(x)&iQ(x)\sqrt{1-x^{2}}\\\
iQ^{*}(x)\sqrt{1-x^{2}}&P(x)^{*}\end{array}\right),$ (41)

where $Q(x)\in\mathbf{C}$ is a degree $k-1$ polynomial whose parity is
opposite to that of $P(x)$. Unitarity introduces the constraint
$|P(x)|^{2}+(1-x^{2})|Q(x)|^{2}=1$ for $x\in[0,1]$.

While the above scheme seems to block-encode only fixed-parity polynomial
$P(x)$, it is straightforward to block-encode an arbitrary-parity polynomial
if we notice

$\displaystyle\left(\begin{array}[]{cc}P(x)&iQ(x)\sqrt{1-x^{2}}\\\
iQ^{*}(x)\sqrt{1-x^{2}}&P(x)^{*}\end{array}\right)$ (44)
$\displaystyle=A(x)\mathbf{1}+iB(x)\sigma_{z}+iC(x)\sigma_{x}+iD(x)\sigma_{y},$
(45)

where all coefficients are polynomials of fixed parity, with $A(x)$ and $B(x)$
having degree $k$, while $C(x)$ and $D(x)$ having degree $k-1$ (see Ref. [82]
for a full characterization). Hence, we can obtain block-encodings of
arbitrary parity polynomials by a simple rotation of the qubit. To summarize,
interweaving single-qubit rotations $G(\phi_{i})$ and $R(\theta)$ allows one
to construct a block-encoding of an arbitrary-parity polynomial of a block-
encoded signal $x$ given a suitable set of phases $\\{\phi_{i}\\}$. We note
that determining the desired set of phases $\\{\phi_{i}\\}$ is not a trivial
task. For instance, see Ref. [44] for concrete procedures for various examples
and its appendix for numerically optimized phase angles.

Ref. [42] further showed that the signal processing of scalar $x$ can be
extended to processing of multi-dimensional operators using only a single
additional ancilla qubit, which we will call the “exit” ancilla in the
following. Intuitively, by applying a conditional block-encoding of the signal
operator $H$, we can elevate the eigenvalues $\lambda_{i}$ of $A$ (e.g.,
$A\left|\lambda\right\rangle=\lambda\left|\lambda\right\rangle$) to rotation
angles $\theta_{i}$ for the exit ancilla.

Formally, given that the block-encoding unitary is Hermitian
$U^{2}=\mathbf{1}$, we can introduce an iterate
$W\equiv(2\left(\left|0\right\rangle\left\langle 0\right|\right)^{\otimes
n_{a}}-\mathbf{1})U$, which can be written as a direct sum over $SU(2)$
invariant subspaces associated with each eigenvalue of $H$

$\displaystyle
W=\bigoplus_{\lambda}\left(\begin{array}[]{cc}\lambda&-\sqrt{1-\lambda^{2}}\\\
\sqrt{1-\lambda^{2}}&\lambda\end{array}\right)_{\lambda},$ (48)

where the subscript $\lambda$ means that the matrix representation is written
in the following basis

$\displaystyle\left|G_{\lambda}\right\rangle=\left|0\right\rangle^{\otimes
n_{a}}\left|\lambda\right\rangle\quad\quad\left|G^{\perp}_{\lambda}\right\rangle=\frac{\lambda\left|G_{\lambda}\right\rangle-U\left|G_{\lambda}\right\rangle}{\sqrt{1-\lambda^{2}}}.$
(49)

Hence, the eigenvectors of $W$ are given by

$\displaystyle\left|G_{\lambda_{\pm}}\right\rangle=\frac{1}{\sqrt{2}}\left(\left|G_{\lambda}\right\rangle\pm\left|G^{\perp}_{\lambda}\right\rangle\right),$
(50)

with associated eigenvalues $e^{\pm i\theta_{\lambda}}$, where
$\theta_{\lambda}~{}\equiv~{}\arccos{(\lambda)}$.

Ref. [42] showed that using a controlled version of $W$ with the exit-ancilla
as the control, it is possible to implement the unitary,

$\displaystyle
U_{\phi}=\sum_{\lambda,\eta=\pm}R_{\phi}(\theta_{\lambda})\otimes\left|G_{\lambda\eta}\right\rangle\left\langle
G_{\lambda\eta}\right|,$ (51)

which rotates the exit-ancilla along a fixed axis on the $x-y$ plane as
determined by $\phi$ and by an angle determined by the phased of the
eigenvalue $e^{i\theta_{\lambda}}$. The decomposition of $U_{\phi}$ in terms
of a controlled version of $W$ and single-qubit rotations of the exit-ancilla
is the following:

$\displaystyle U_{\phi}$
$\displaystyle=(e^{-i\phi\sigma^{(\rm{ex})}_{z}/2}\otimes\mathbf{1})U_{0}(e^{-i\phi\sigma^{(\rm{ex})}_{z}/2}\otimes\mathbf{1})$
$\displaystyle U_{0}$ $\displaystyle\equiv\left|+\right\rangle_{\rm
ex}\left\langle+\right|\otimes\mathbf{1}+\left|-\right\rangle_{\rm
ex}\left\langle-\right|\otimes W$
$\displaystyle=\sum_{\lambda,\eta=\pm}e^{i\eta\theta_{\lambda}/2}R_{\rm
ex}(\eta\theta_{\lambda})\otimes\left|G_{\lambda\eta}\right\rangle\left\langle
G_{\lambda\eta}\right|,$ (52)

and $\sigma^{(\rm{ex})}_{z}$ is a Pauli operator acting on the exit ancilla.

Noting that the eigenvectors of $W$ satisfy

$\displaystyle\left\langle 0^{\otimes n_{a}}\right|\otimes\mathbf{1}_{\rm
sys})\left|G_{\lambda\pm}\right\rangle=\sqrt{\frac{1}{2}}\left|\lambda\right\rangle,$
(53)

an arbitrary-parity polynomial of a Hermitian signal operator can be block-
encoded. That is,

$\displaystyle\left\langle+\right|_{\rm ex}\left\langle 0\right|^{\otimes
n_{a}}\prod_{j=1}^{k/2}U_{\phi_{2j}}U^{\dagger}_{\phi_{2j+1}+\pi}\left|0\right\rangle^{\otimes
n_{a}}\left|+\right\rangle_{\rm ex}$ (54)
$\displaystyle=\sum_{\lambda}\tilde{P}(\lambda)\left|\lambda\right\rangle\left\langle\lambda\right|,$
(55)

where $\tilde{P}(x)$ is an arbitrary parity polynomial of degree $k$. As a
result, QSP provides an indispensable tool for processing block-encoded signal
operators. Most importantly, for the following discussion on Hamiltonian
simulation we would like to implement $\tilde{P}(\lambda)\approx e^{i\lambda
t}$.

##  Appendix B QSP-based optimal Hamiltonian simulation

The Hamiltonian simulation algorithm based on the QSP framework uses the
block-encoding of the Hamiltonian $H$ to construct a polynomial approximation
of $P(H)\approx e^{-iHt}$. Ref. [57] proved that this method results in an
optimal query complexity, which is

$\displaystyle k^{*}=O\left(\alpha
t+\frac{\log(1/\epsilon))}{\log\log{(1/\epsilon)}}\right),$ (56)

where we define $\alpha\equiv||H||=O(N)$, for a Hamiltonian composed of $N$
Pauli strings. The linear scaling of $k^{*}$ with respect to the spectral norm
of the Hamiltonian is due to the unitarity block-encoding utilized by QSP. We
also emphasize that the scaling of the query complexity with respect to error
tolerance $\epsilon$ is exponentially improved compared to the simulation
algorithms based on Trotterization [48]. Moreover, it is possible show that
the number of queries $k$ can be bound by the following inequality [43]

$\displaystyle k^{*}\leq e^{q}\alpha t+\frac{\ln{(1/\epsilon)}}{q}\quad\forall
q\in\mathbf{R}.$ (57)

The query complexity of the QSP-based Hamiltonian simulation can be related to
the time and error-bounded gate complexities, given a specific implementation
of the query. We emphasize that even if the time required to implement the
query is constant, the time complexity of Hamiltonian simulation of a system
of size $n_{\rm site}$ for a time $t=n_{\rm site}$ results in an
implementation time of $O(n_{\rm site}^{2})$, which is suboptimal. On the
other hand, implementing the query (i.e., the walk operator) with constant
EBGC implies an implementation optimal with respect to errors. In Section D,
we demonstrate that this optimal error complexity is achieved for our proposal
for $k$-local Hamiltonians.

##  Appendix C Optimal Quantum Hamiltonian simulation of local Hamiltonians

Since Ref. [79] argued that the optimal gate complexity of an algorithm
simulating local Hamiltonian simulations should scale roughly as the simulated
space-time volume, there has been a renewed interest in finding rigorous tight
bounds for optimal simulation of local Hamiltonians [78, 58]. In 2018, an
algorithm by Haah et al. [58], constructed an algorithm with a gate complexity
linear in the simulated $d+1$ dimensional space-time volume $O(nt{\rm
polylog}(n^{1/d}t/\epsilon))$, where $\epsilon$ is the total error tolerance
of Hamiltonian simulation, and proved the optimality of this bound. In this
section, we give a brief review of this work to motivate the constructions in
Appendix D.

From the bird’s eye view, the algorithm in Ref. [58] uses a block-decimation
of the time-evolution unitary $e^{-iHt}$ which guarantees that the error due
to the decomposition is bound by the Lieb-Robinson (LR) theorems [80, 81]. LR
theorems formalize the intuition that for local Hamiltonians, the maximum
speed that information can travel is a well-defined constant, called the Lieb-
Robinson velocity $v$. The overall structure of the algorithm in Ref. [58] is
depicted in Fig. 11 for the case of a one-dimensional system, which we
consider for sake of simplicity. Any block-decimation of the evolution
operator introduces local errors at each boundary. These errors can be
described as the emission of Hamiltonian terms $H_{bd}$ at the boundaries of
neighboring blocks. Upon time evolution by a local Hamiltonian, it is possible
to ensure that these errors propagate only within the associated light-cones
(depicted as yellow and blue triangles in Fig. 11) up to exponentially small
corrections. The knowledge of the local spread of such errors allows on to
design a spin-echo-like algorithm which reverses the spread of the errors,
leaving behind only the exponentially small corrections. Formally, one can
show that for a given a block decimation of the sites $X=A\bigcup B\bigcup C$,
a constant $\mu=O(1)$, Lieb-Robinson velocity $v$, and $vt\ll l=dist(B)$

$\displaystyle|U_{t}-e^{-iH_{A\bigcup B}t}e^{iH_{B}t}e^{-iH_{B\bigcup
C}t}|<O(|H_{bd}|\exp{(-\mu l)}),$ (58)

where $H_{X}$ denotes the sum of Hamiltonian terms which have a support on a
region $X$. Longer times can be simulated by applying the same decimated
evolution operator repeatedly $t$ times and obtain an error linearly
increasing with $t$.

Given the above discussion, the choice of the smallest dimensions of each
block, denoted $l$ in the space axis and $t_{\square}$ in the time axis, is
determined by (i) the tolerance $\epsilon_{\rm LR}$ for errors resulting from
the block-decimation, (ii) the tolerance $\epsilon_{\square}$ for errors due
to the QSP-based approximate Hamiltonian simulation of each block, and (iii)
the number of blocks $m=O(nt/lt_{\square})$. In particular, given a total
error tolerance $\epsilon$, we would like the error associated with each block
to be $\epsilon_{\square}+\epsilon_{\rm LR}=O(\epsilon/m)$ [59, 41]. In the
following, we assume $\epsilon_{\square}=\epsilon_{\rm LR}$. Given Eq. (58),
we have $\epsilon_{\rm LR}=O(e^{-\mu l})$, and the spatial dimension of each
block is $l=O(\log{(nt/t_{\square}\epsilon)})$. We are then left with the
challenge of realizing the Hamiltonian simulation of a system of size
$O(\log{\left(nt/t_{\square}\epsilon\right)})$, with error tolerance
$\epsilon_{\square}=O(\epsilon\frac{lt_{\square}}{nT})$ using only
$O(\mathrm{polylog}{\left(nt/t_{\square}\epsilon\right)})$ gates. Fortunately,
the QSP-based Hamiltonian simulation algorithm discussed in Section B has a
query complexity that scales logarithmically with $\epsilon_{\square}^{-1}$,
resulting in a the gate complexity that scales almost linearly with the
simulated space-time volume

$\displaystyle O(nt\,{\rm polylog}(nt/t_{\square}\epsilon)).$ (59)

In summary, the optimal quantum Hamiltonian simulation algorithm by Haah et
al. uses the QSP-based query optimal Hamiltonian simulation algorithm in
combination with a clever block-decimation of the space-time evolution to
obtain a near optimal gate count for Hamiltonian simulation algorithm for
local Hamiltonians.

Figure 11: Overview of the algorithm in Ref. [58]. (a) the first approximation
depicts the principle relation between the initial and decimated circuits for
Hamiltonian simulation. On the other hand, the equivalence relation depicts
the spread and reversal of errors originating from the left (yellow) and right
(blue) edges of each block. At the first time step, the error due to the left
edge of a block simulating $e^{-iH_{BC}t}$ spreads within the light-cone
depicted in yellow. At the second step, the evolution operator $e^{iH_{B}t}$
fixes this error but it also introduces new errors due to the right boundary
of the block. The final evolution by $e^{-iH_{AB}t}$ reverses the error
introduced by $e^{iH_{B}t}$, and the approximation error is bounded by the
exponentially small error outside of the light cone given the intermediate
block is large enough to contain the light-cone. (b) Demonstration of how the
block decimation operator can be repeated in space and the pattern of errors
induced.

We emphasize that the aforementioned optimal gate count is not error-bounded
in the sense discussed in Section IV.1, as it does not take into account the
specific error model of the implementation. Moreover, the near optimal gate
count of the algorithm in Ref. [58] comes at a price of a high implementation
overhead [48], which makes it less efficient than the product-formula
algorithms for Hamiltonian simulation on near-term intermediate scale quantum
(NISQ) processors. In the next section, we calculate the overhead associated
with the Rydberg platform implementations of both the product formula and the
QSP-based Hamiltonian simulation protocols. While the overhead of the
algorithm in Ref. [58] makes it undesirable for NISQ devices, we find that the
EBGC of QSP-based Hamiltonian simulation of Ref. [57] has orders of magnitude
of smaller overhead for gate errors compared to its competitors.

##  Appendix D Concrete circuits and gate counts

Here, we use the results of the Section V to analyze the resource requirements
for the implementation of QSP-based and Hamiltonian simulation algorithms on
the Rydberg atom platform, and compare them to those needed to implement
Hamiltonian simulation based on product formula. To this end, we briefly
discuss the implementation of product-formula-based Hamiltonian simulation
algorithms on the Rydberg platform and calculate the associated EBGCs.

###  D.1 Hamiltonian simulation

Here, we explicitly calculate the resources needed for implementing algorithms
in the framework of QSP, using LCU-based block-encoding. In particular, for a
system of $n_{\rm site}$ qubits, we consider the number of error-bounded
gates, the runtime, and the number of ancillas required to implement a (i)
conditional version of LCU block-encoding, (ii) QSP-based Hamiltonian
simulation, (iii) Optimal simulation of local Hamiltonians in Ref. [58], and
finally (iv) Hamiltonian simulation using fourth order product formula. We
note that all of calculations in this section, we assume that the blockade
radius can be taken large enough such that the scalable protocols discussed in
Section VI are not necessary.

####  D.1.1 Implementing Haah’s Optimal Hamiltonian Simulation (Ref. [58])

To facilitate the calculation of resources needed for Hamiltonian simulation,
it is necessary to chose an explicit Hamiltonian to be simulated. Here, we
chose a the one-dimensional disordered Heisenberg Hamiltonian $H_{\rm DH}$ as
our target system

$\displaystyle H_{\rm DH}=\sum^{n_{\rm
site}}_{i<j}\sigma_{i}\cdot\sigma_{j}+\sum^{n_{\rm
site}}_{i}h_{i}\sigma_{i}^{(z)}.$ (60)

The choice of the disordered Heisenberg Hamiltonian as our target allows us to
directly compare the cost of our implementation of QSP-based Hamiltonian
simulation to that implied by the previous empirical studies that use product
formulas [48, 78].

Our first task is to find the dimensions of each block in the decimation given
the parameters $n_{\rm site}$, $t$, and the error tolerance $\epsilon$.

In one-dimensions, the number of blocks is

$\displaystyle m=4\left(\frac{2tn_{\rm site}}{t_{\square}l}\right),$ (61)

where $l$ and $t_{\square}$ are the shortest dimensions of each block along
space and time coordinates (see Fig. 12), respectively. Hence, we have $m/2$
blocks of length $l$ and $m/2$ blocks of length $2l$, and the overall factor
of $4$ in Eq. (61) is due to the normalization of the Hamiltonian for each
site (i.e., $H_{i,i+1}\leq 1$). For a given spatial extent $l$ of each block,
the parameter $t_{\square}$ can be determined by studying how the errors due
the decimation scale as a function of time for a single block. This was done
in Ref. [58] and the following relation was found

$\displaystyle
0.175\left(\frac{7.9t_{\square}}{l+0.95}\right)^{l+0.95}=\frac{\epsilon}{3m}\equiv\epsilon_{\rm
LR}.$ (62)

For the data presented here, we set $t=4n_{\rm site}$ and
$m\epsilon_{\square}=m\epsilon_{LR}=10^{-3}/2$.

Once the parameters $l$ and $t_{\square}$ are determined, we can also
calculate the order $k_{\square}$ of the polynomial appoximation to the
Hamiltonian evolution associated with each block using Eq. (57). For the
smaller blocks of spatial size $l$, we get

$\displaystyle
k_{\square}(l)=\min_{q}\left[e^{q}t_{\square}l+\ln\left(\frac{\epsilon_{\square}}{3m}\right)/q\right],$
(63)

while for blocks of spatial size $2l$, we replace $l\rightarrow 2l$.

The simultaneous implementation of Hamiltonian simulation in each block may
introduce unwanted cross-talk errors due to the algebraic decay of the dipolar
interactions, even if the blockade radii of adjacent blocks do not overlap
(see Fig. 12 a). We circumvent this problem by doubling the implementation
time required to simulate evolution for a time $t_{\square}$. The scheme is
depicted in Fig. 12 for a one dimensional system. For each time step, we
require that the blockade radii associated with different spatial blocks have
negligible overlap. We also note that, in principle, the block-encoding and
the QSP-based Hamiltonian simulation algorithms have the flexibility to
implement the simulation of a Hamiltonians with different boundary terms are
omitted at each step (see Fig. 11), as well as changing the overall sign of
the Hamiltonian $H\rightarrow-H$.

Figure 12: The overall schematic for the paralelized implementation the
optimal Hamiltonian simulation of [58] on the Rydberg platform. a) A depiction
of the sources of cross-talk errors due to the algebraic decay of the
interaction potential, which makes the definition of Rydberg blockade radius
$R_{b}$ fuzzy. The two system atoms at the boundary between the two blockade
volumes introduce errors due to unwanted blockade interactions. b) The
experimental configuration for the parallelized application of the algorithm
in Ref [58]. We use twice as many overlapping simulation regions (i.e.,
$A\,,B\,,C\,$,and $D$) as depicted in Fig. 11 to reduce the errors due to the
algebraic decay of the dipolar interactions. c) The schedule for applying the
QSP-based Hamiltonian simulation algorithm on 4 different simulation regions
to reduce the crosstalk errors. The crosstalk errors can be reduced
arbitrarily at the expense of an increase in the circuit depth.

Having determined $l$, $t_{\square}$, and $k_{\square}$, we next calculate the
depth and EBGCs for the CPHASE gate and LCU-based block-encoding using the
techniques discussed in Section V (see also Table 2), and assuming that we are
using the customized One-Hot encoding state-preparation protocol

$\displaystyle d_{\rm LCU}$ $\displaystyle=2d_{V_{\rm OHE}}+d_{\bar{U}_{\rm
OHE}}+1$ $\displaystyle=4(1+2L)+9L+1=124$ (64) $\displaystyle n_{\rm LCU}$
$\displaystyle=2n_{\tilde{V}_{\rm OHE}}+n_{\bar{U}_{\rm
OHE}}=\frac{16+10}{3}=\frac{26}{3}$ (65) $\displaystyle a_{\rm LCU}$
$\displaystyle=n_{\rm site}+L;\quad d_{\rm CPHASE}=3;\quad n_{\rm
CPHASE}=\frac{4}{3},$ (66)

where $d_{*}$, $n_{*}$, and $a_{*}$ denote the circuit depth, EBGC, and the
number of ancillae needed for implementing $``*"$. In order to calculate the
EBGC for $\bar{U}_{\rm OHE}$, we used Eq. (V.2), and set $L=2*3+1=7$ to
implement Pauli terms associated with the 3 axes of interactions and the
disordered field in Eq. 60. Lastly, here we assumed the implementation of an
$L$-qubit controlled phase rotation of an additional phase ancilla, which
introduces only a constant EBGC thanks to the One-Hot Encoding nature of the
ancillary registers.

Hence, implementing the conditional version of the iterate $W$ in Eq. (11)
costs depth $d_{CW}=2*2+d_{\rm CPHASE}+d_{\rm LCU}$, where we added depth 2
for each controlled version of the unitaries. On the other hand, the EBGC of
$CW$ is $n_{CW}=2*\frac{2}{3}+n_{\rm CPHASE}+n_{\rm LCU}$. As a result, the
QSP-based Hamiltonian simulation algorithm of Ref. [57] can be implemented
using

$\displaystyle d_{QSP}$ $\displaystyle=k^{*}(d_{CW}+1)$ $\displaystyle
a_{QSP}$ $\displaystyle=a_{LCU}+1$ $\displaystyle n_{QSP}$
$\displaystyle=k^{*}(n_{CW}+1),$ (67)

where $k^{*}$ is calculated using Eq. (57). Lastly, the computation resources
to implement the local Hamiltonian simulation algorithm of Ref. [58] are

$\displaystyle d_{\rm H1D}$
$\displaystyle=2\frac{t}{t_{\square}}(k_{\square}(l)+2k_{\square}(2l))(d_{CW}+1)$
$\displaystyle a_{\rm H1D}$ $\displaystyle=\frac{n_{\rm
site}}{2l}\left(4+2l+2\right)$ $\displaystyle n_{\rm H1D}$
$\displaystyle=\frac{m}{2}k_{\square}(2l)\left[n_{CW}+1\right].$

Notice that the overall factor of 2 in the depth of implementation comes from
our method of reducing the cross-talk between the blocks (see Fig. 12). The
number of ancillae is increased by an additional $O\left(\frac{n_{\rm
site}}{l}\right)$ ancillae compared to the requirements for QSP-based
Hamiltonian simulation in order to facilitate the parallelization by the
block-decimation.

####  D.1.2 Comparison to Hamiltonian simulation with product formulas

Here, we compare the resource requirements for our implementation of the QSP-
based Hamiltonian simulation algorithm on the Rydberg platform to those of
Hamiltonian simulation using product formulas [48, 78].

In order to have a fair comparison for the disordered Heisenberg model, we
consider the ordering structure of the product formula proposed by Ref. [78].
In particular, we focus on the types of Hamiltonians that can be written in
the following form

$\displaystyle H=\sum_{i}^{n_{\rm site}-1}H_{i,i+1},$ (68)

where the terms $H_{i,i+1}$ can be decomposed into Pauli operators which act
non-trivially only on sites $i$ and $i+1$. Then the first order product
formula has the following form

$\displaystyle e^{-iH\delta t}\approx\mathcal{\rho}_{1}(\delta t)$
$\displaystyle=\prod_{k=1}^{n/2-1}e^{-i\delta
tH_{2k,2k+1}}\prod_{l=1}^{n/2}e^{-i\delta tH_{2k-1,2k}}$
$\displaystyle=e^{-i\delta tH_{\rm even}}e^{-i\delta tH_{\rm odd}}.$ (69)

Moreover, the higher order product formulas can be constructed as the
following [78]

$\displaystyle\mathcal{\rho}_{2}(\delta t)$ $\displaystyle=e^{-i\frac{\delta
t}{2}H_{\rm even}}e^{-i\delta tH_{\rm odd}}e^{-i\frac{\delta t}{2}H_{\rm
even}}$ (70) $\displaystyle\mathcal{\rho}_{2k}(\delta t)$
$\displaystyle=\mathcal{\rho}_{2k-2}(p_{k}\delta
t)^{2}\mathcal{\rho}_{2k-2}((1-4p_{k})\delta
t)\mathcal{\rho}_{2k-2}(p_{k}\delta t)^{2},$ (71)

where $p_{k}=1/4-4^{\frac{1}{2k-1}}$. In the following, we will only focus on
the 4th order product formula algoritm as it results in the best conventional
gate counts in Ref. [48]. The errors induced by the $4^{\rm st}$ order product
formula approximation to the evolution operator $e^{-iH_{H1D}\delta t}$ scale
as $O(n(\delta t)^{5})$ for small $\delta t$ [78]. In order to simulate larger
times, one conducts the simulation in $r=t/\delta t$ segments. Ref. [78]
utilized a numerical optimization algorithm which determined that the number
of segments $r$ for an error threshold $\epsilon=10^{-3}$ and 4th-order
product formula

$\displaystyle r_{4}\approx 4n_{\rm site}^{1.555}.$ (72)

In order to calculate the resource costs of implementing product formulas on
the Rydberg atom platform, we consider the specific protocols proposed in Ref.
[31]. This proposal is based on an implementation of the exponential of a
Pauli term in the Hamiltonian (i.e., $e^{-i\alpha_{j}P_{j}}$) using a single
ancilla $a$. In particular, the scheme uses the following gate sequence

$\displaystyle
e^{-i\alpha_{j}P_{j}}=G^{\dagger}e^{i\alpha_{j}\sigma_{z}^{a}}G,$ (73)

where

$\displaystyle G=e^{-i\pi/4\sigma_{x}^{(a)}}U_{j}e^{i\pi/4\sigma^{(a)}_{x}},$
(74)

and $U_{j}=\left|1\right\rangle_{a}\left\langle 1\right|\otimes
P_{j}+\left(\mathbf{I}-\left|0\right\rangle_{a}\left\langle
0\right|\right)\otimes\mathbf{I}$. Intuitively, the transformation $G$ maps
the eigenstates of the Pauli operator $P_{j}$ with eigenvalues $\pm 1$ onto
the $\left|\frac{1\pm 1}{2}\right\rangle_{\rm anc}$ states of the ancilla
qubit. The two eigenstates acquire phases with opposite signs using the
single-qubit phase rotation $e^{i\alpha_{j}\sigma_{z}^{a}}$. The
exponentiation requires 1 ancilla per two-qubit Pauli operator and can be
implemented in depth $8+\alpha_{j}/\pi$. The EBGC of the exponentiation step
is

$\displaystyle\frac{1}{3}\left[2\left(2+\frac{{\rm
supp}(P_{j})}{2}\right)+\frac{\alpha_{j}}{\pi}\right].$ (75)

Thus, the exponentiation of each two-qubit Pauli takes $2+\alpha_{j}/(3\pi)$
error-bounded gates.

The resources needed for the simulation of the 1D disordered Heisenberg model
using $1^{\rm th}$ order product formula for a single segment [48] that
implements a time evolution for $\delta t$ are the following

$\displaystyle d_{\rm PF}$ $\displaystyle=2*3*(8+\delta t/\pi)+\delta
t/\pi=48+7\delta t/\pi$ $\displaystyle a_{\rm PF}$ $\displaystyle=n_{\rm
site}/2$ $\displaystyle n_{\rm PF}$ $\displaystyle=n_{\rm
site}\left[3\left(2+\frac{\delta t}{3\pi}\right)+\frac{\delta
t}{3\pi}\right]=n_{\rm site}\left(6+\frac{4\delta t}{3\pi}\right),$

where we note the factors of 2 in the calculation of $d_{PF}$ arise from the
serial application of evolution by $H_{\rm even}$ and $H_{\rm odd}$, and we
assume that the local random field can be implemented using 1 single-qubit
rotation without any need for ancillas. Because the ancillae are uncomputed
after each step, $a_{PF}$ does not change with increasing $k$. Here, we
compare the QSP-based Hamiltonian simulation to the 4th order product formula
according to Eq. (71), as it results in the lowest gate counts in Ref. [48].
To calculate the resources for longer time evolution, the above expressions
should be multiplied by $r_{4}$ in Eq. $(\ref{eq:evenodd})$.

## References

  * Brennen  _et al._ [1999] G. K. Brennen, C. M. Caves, P. S. Jessen, and I. H. Deutsch, Quantum logic gates in optical lattices, Physical Review Letters 82, 1060 (1999).
  * Briegel  _et al._ [2000] H.-J. Briegel, T. Calarco, D. Jaksch, J. I. Cirac, and P. Zoller, Quantum computing with neutral atoms, Journal of modern optics 47, 415 (2000).
  * Jaksch  _et al._ [2000] D. Jaksch, J. Cirac, P. Zoller, S. Rolston, R. Côté, and M. Lukin, Fast quantum gates for neutral atoms, Physical Review Letters 85, 2208 (2000).
  * Brion  _et al._ [2007] E. Brion, K. Mølmer, and M. Saffman, Quantum computing with collective ensembles of multilevel systems, Physical review letters 99, 260501 (2007).
  * Mølmer  _et al._ [2011] K. Mølmer, L. Isenhower, and M. Saffman, Efficient grover search with rydberg blockade, Journal of Physics B: Atomic, Molecular and Optical Physics 44, 184016 (2011).
  * Saffman [2016] M. Saffman, Quantum computing with atomic qubits and rydberg interactions: progress and challenges, Journal of Physics B: Atomic, Molecular and Optical Physics 49, 202001 (2016).
  * Weiss and Saffman [2017a] D. S. Weiss and M. Saffman, Quantum computing with neutral atoms, Physics Today 70, 44 (2017a), https://doi.org/10.1063/PT.3.3626 .
  * Adams  _et al._ [2019] C. S. Adams, J. D. Pritchard, and J. P. Shaffer, Rydberg atom quantum technologies, Journal of Physics B: Atomic, Molecular and Optical Physics 53, 012002 (2019).
  * Henriet  _et al._ [2020] L. Henriet, L. Beguin, A. Signoles, T. Lahaye, A. Browaeys, G.-O. Reymond, and C. Jurczak, Quantum computing with neutral atoms, Quantum 4, 327 (2020).
  * Bernien  _et al._ [2017] H. Bernien, S. Schwartz, A. Keesling, H. Levine, A. Omran, H. Pichler, S. Choi, A. S. Zibrov, M. Endres, M. Greiner, _et al._ , Probing many-body dynamics on a 51-atom quantum simulator, Nature 551, 579 (2017).
  * Browaeys and Lahaye [2020] A. Browaeys and T. Lahaye, Many-body physics with individually controlled rydberg atoms, Nature Physics 16, 132 (2020).
  * Omran  _et al._ [2019] A. Omran, H. Levine, A. Keesling, G. Semeghini, T. T. Wang, S. Ebadi, H. Bernien, A. S. Zibrov, H. Pichler, S. Choi, _et al._ , Generation and manipulation of schrödinger cat states in rydberg atom arrays, Science 365, 570 (2019).
  * Samajdar  _et al._ [2021] R. Samajdar, W. W. Ho, H. Pichler, M. D. Lukin, and S. Sachdev, Quantum phases of rydberg atoms on a kagome lattice, Proceedings of the National Academy of Sciences 118, 10.1073/pnas.2015785118 (2021), https://www.pnas.org/content/118/4/e2015785118.full.pdf .
  * Verresen  _et al._ [2020] R. Verresen, M. D. Lukin, and A. Vishwanath, Prediction of toric code topological order from rydberg blockade, arXiv preprint arXiv:2011.12310 (2020).
  * Semeghini  _et al._ [2021] G. Semeghini, H. Levine, A. Keesling, S. Ebadi, T. T. Wang, D. Bluvstein, R. Verresen, H. Pichler, M. Kalinowski, R. Samajdar, _et al._ , Probing topological spin liquids on a programmable quantum simulator, arXiv preprint arXiv:2104.04119 (2021).
  * Weiss and Saffman [2017b] D. S. Weiss and M. Saffman, Quantum computing with neutral atoms, Physics Today 70 (2017b).
  * Lukin  _et al._ [1999] M. D. Lukin, S. F. Yelin, M. Fleischhauer, and M. O. Scully, Quantum interference effects induced by interacting dark resonances, Phys. Rev. A 60, 3225 (1999).
  * Lukin  _et al._ [2000] M. D. Lukin, S. F. Yelin, and M. Fleischhauer, Entanglement of atomic ensembles by trapping correlated photon states, Physical Review Letters 84, 4232 (2000).
  * Bajcsy  _et al._ [2003] M. Bajcsy, A. S. Zibrov, and M. D. Lukin, Stationary pulses of light in an atomic medium, Nature 426, 638 (2003).
  * Choi  _et al._ [2008] K. S. Choi, H. Deng, J. Laurat, and H. Kimble, Mapping photonic entanglement into and out of a quantum memory, Nature 452, 67 (2008).
  * Urban  _et al._ [2009] E. Urban, T. A. Johnson, T. Henage, L. Isenhower, D. Yavuz, T. Walker, and M. Saffman, Observation of rydberg blockade between two atoms, Nature Physics 5, 110 (2009).
  * Lukin  _et al._ [2001] M. D. Lukin, M. Fleischhauer, R. Cote, L. Duan, D. Jaksch, J. I. Cirac, and P. Zoller, Dipole blockade and quantum information processing in mesoscopic atomic ensembles, Physical review letters 87, 037901 (2001).
  * Madjarov  _et al._ [2020] I. S. Madjarov, J. P. Covey, A. L. Shaw, J. Choi, A. Kale, A. Cooper, H. Pichler, V. Schkolnik, J. R. Williams, and M. Endres, High-fidelity entanglement and detection of alkaline-earth rydberg atoms, Nature Physics 16, 857 (2020).
  * Wilson  _et al._ [2022] J. T. Wilson, S. Saskin, Y. Meng, S. Ma, R. Dilip, A. P. Burgers, and J. D. Thompson, Trapping alkaline earth rydberg atoms optical tweezer arrays, Phys. Rev. Lett. 128, 033201 (2022).
  * Ma  _et al._ [2022] S. Ma, A. P. Burgers, G. Liu, J. Wilson, B. Zhang, and J. D. Thompson, Universal gate operations on nuclear spin qubits in an optical tweezer array of yb 171 atoms, Physical Review X 12, 021028 (2022).
  * Häffner  _et al._ [2008] H. Häffner, C. F. Roos, and R. Blatt, Quantum computing with trapped ions, Physics reports 469, 155 (2008).
  * Home  _et al._ [2009] J. P. Home, D. Hanneke, J. D. Jost, J. M. Amini, D. Leibfried, and D. J. Wineland, Complete methods set for scalable ion trap quantum information processing, Science 325, 1227 (2009).
  * Wallraff  _et al._ [2004] A. Wallraff, D. I. Schuster, A. Blais, L. Frunzio, R.-S. Huang, J. Majer, S. Kumar, S. M. Girvin, and R. J. Schoelkopf, Strong coupling of a single photon to a superconducting qubit using circuit quantum electrodynamics, Nature 431, 162 (2004).
  * Blais  _et al._ [2021] A. Blais, A. L. Grimsmo, S. M. Girvin, and A. Wallraff, Circuit quantum electrodynamics, Reviews of Modern Physics 93, 025005 (2021).
  * Bluvstein  _et al._ [2021] D. Bluvstein, H. Levine, G. Semeghini, T. T. Wang, S. Ebadi, M. Kalinowski, A. Keesling, N. Maskara, H. Pichler, M. Greiner, _et al._ , A quantum processor based on coherent transport of entangled atom arrays, arXiv preprint arXiv:2112.03923 (2021).
  * Weimer  _et al._ [2010] H. Weimer, M. Müller, I. Lesanovsky, P. Zoller, and H. P. Büchler, A rydberg quantum simulator, Nature Physics 6, 382 (2010).
  * Wilson  _et al._ [2019] J. Wilson, S. Saskin, Y. Meng, S. Ma, R. Dilip, A. Burgers, and J. Thompson, Trapped arrays of alkaline earth rydberg atoms in optical tweezers, arXiv preprint arXiv:1912.08754 (2019).
  * Barnes  _et al._ [2022] K. Barnes, P. Battaglino, B. J. Bloom, K. Cassella, R. Coxe, N. Crisosto, J. P. King, S. S. Kondov, K. Kotru, S. C. Larsen, _et al._ , Assembly and coherent control of a register of nuclear spin qubits, Nature Communications 13, 1 (2022).
  * Cong  _et al._ [2021] I. Cong, S.-T. Wang, H. Levine, A. Keesling, and M. D. Lukin, Hardware-efficient, fault-tolerant quantum computation with rydberg atoms, arXiv preprint arXiv:2105.13501 (2021).
  * Zhou  _et al._ [2020] Y. Zhou, E. M. Stoudenmire, and X. Waintal, What limits the simulation of quantum computers?, Phys. Rev. X 10, 041038 (2020).
  * Oh  _et al._ [2021] C. Oh, K. Noh, B. Fefferman, and L. Jiang, Classical simulation of lossy boson sampling using matrix product operators, Phys. Rev. A 104, 022407 (2021).
  * Pan  _et al._ [2022] F. Pan, K. Chen, and P. Zhang, Solving the sampling problem of the sycamore quantum circuits, Physical Review Letters 129, 090502 (2022).
  * Aharonov and Ben-Or [1997] D. Aharonov and M. Ben-Or, Fault-tolerant quantum computation with constant error, in  _Proceedings of the twenty-ninth annual ACM symposium on Theory of computing_ (1997) pp. 176–188.
  * Preskill [1998] J. Preskill, Reliable quantum computers, Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences 454, 385 (1998).
  * Knill [2005] E. Knill, Quantum computing with realistically noisy devices, Nature 434, 39 (2005).
  * Nielsen and Chuang [2002] M. A. Nielsen and I. Chuang,  _Quantum computation and quantum information_ (American Association of Physics Teachers, 2002).
  * Low [2017] G. H. Low,  _Quantum signal processing by single-qubit dynamics_ , Ph.D. thesis, Massachusetts Institute of Technology (2017).
  * Gilyén  _et al._ [2019] A. Gilyén, Y. Su, G. H. Low, and N. Wiebe, Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics, in  _Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing_ (2019) pp. 193–204.
  * Martyn  _et al._ [2021] J. M. Martyn, Z. M. Rossi, A. K. Tan, and I. L. Chuang, Grand unification of quantum algorithms, PRX Quantum 2, 040203 (2021).
  * Chakraborty  _et al._ [2019] S. Chakraborty, A. Gilyén, and S. Jeffery, The Power of Block-Encoded Matrix Powers: Improved Regression Techniques via Faster Hamiltonian Simulation, in  _46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)_, Leibniz International Proceedings in Informatics (LIPIcs), Vol. 132, edited by C. Baier, I. Chatzigiannakis, P. Flocchini, and S. Leonardi (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2019) pp. 33:1–33:14.
  * Levine  _et al._ [2019] H. Levine, A. Keesling, G. Semeghini, A. Omran, T. T. Wang, S. Ebadi, H. Bernien, M. Greiner, V. Vuletić, H. Pichler, and M. D. Lukin, Parallel implementation of high-fidelity multiqubit gates with neutral atoms, Phys. Rev. Lett. 123, 170503 (2019).
  * Childs and Wiebe [2012] A. M. Childs and N. Wiebe, Hamiltonian simulation using linear combinations of unitary operations, arXiv preprint arXiv:1202.5822 (2012).
  * Childs  _et al._ [2018] A. M. Childs, D. Maslov, Y. Nam, N. J. Ross, and Y. Su, Toward the first quantum simulation with quantum speedup, Proceedings of the National Academy of Sciences 115, 9456 (2018).
  * Lloyd [1996] S. Lloyd, Universal quantum simulators, Science , 1073 (1996).
  * Harrow  _et al._ [2009] A. W. Harrow, A. Hassidim, and S. Lloyd, Quantum algorithm for linear systems of equations, Physical review letters 103, 150502 (2009).
  * Note [1] See Ref. [43, 44] for further examples.
  * Note [2] In contrast, compiling time-dependent Hamiltonian simulation is difficult because then multiple functional transformations $f_{t}(\cdot)$ and their inputs $A_{t}$ need to be explicitly specified.
  * Müller  _et al._ [2009] M. Müller, I. Lesanovsky, H. Weimer, H. Büchler, and P. Zoller, Mesoscopic rydberg gate based on electromagnetically induced transparency, Physical Review Letters 102, 170502 (2009).
  * Boller  _et al._ [1991] K.-J. Boller, A. Imamoğlu, and S. E. Harris, Observation of electromagnetically induced transparency, Physical Review Letters 66, 2593 (1991).
  * Lukin and Imamoğlu [2000] M. Lukin and A. Imamoğlu, Nonlinear optics and quantum entanglement of ultraslow single photons, Physical Review Letters 84, 1419 (2000).
  * Rebentrost  _et al._ [2014] P. Rebentrost, M. Mohseni, and S. Lloyd, Quantum support vector machine for big data classification, Phys. Rev. Lett. 113, 130503 (2014).
  * Low and Chuang [2019] G. H. Low and I. L. Chuang, Hamiltonian simulation by qubitization, Quantum 3, 163 (2019).
  * Haah  _et al._ [2021] J. Haah, M. B. Hastings, R. Kothari, and G. H. Low, Quantum algorithm for simulating real time evolution of lattice hamiltonians, SIAM Journal on Computing , FOCS18 (2021).
  * Childs [2017] A. M. Childs, Lecture notes on quantum algorithms, Lecture notes at University of Maryland (2017).
  * Petrosyan  _et al._ [2017] D. Petrosyan, F. Motzoi, M. Saffman, and K. Mølmer, High-fidelity rydberg quantum gate via a two-atom dark state, Phys. Rev. A 96, 042306 (2017).
  * Löw  _et al._ [2012] R. Löw, H. Weimer, J. Nipper, J. B. Balewski, B. Butscher, H. P. Büchler, and T. Pfau, An experimental and theoretical guide to strongly interacting rydberg gases, Journal of Physics B: Atomic, Molecular and Optical Physics 45, 113001 (2012).
  * Yavuz  _et al._ [2006] D. Yavuz, P. Kulatunga, E. Urban, T. A. Johnson, N. Proite, T. Henage, T. Walker, and M. Saffman, Fast ground state manipulation of neutral atoms in microscopic optical traps, Physical Review Letters 96, 063001 (2006).
  * Morgado and Whitlock [2021] M. Morgado and S. Whitlock, Quantum simulation and computing with rydberg-interacting qubits, AVS Quantum Science 3, 023501 (2021), https://doi.org/10.1116/5.0036562 .
  * Unanyan and Fleischhauer [2002] R. G. Unanyan and M. Fleischhauer, Efficient and robust entanglement generation in a many-particle system with resonant dipole-dipole interactions, Phys. Rev. A 66, 032109 (2002).
  * Maxwell  _et al._ [2013] D. Maxwell, D. Szwer, D. Paredes-Barato, H. Busche, J. D. Pritchard, A. Gauguet, K. J. Weatherill, M. Jones, and C. S. Adams, Storage and control of optical photons using rydberg polaritons, Physical review letters 110, 103001 (2013).
  * Paredes-Barato and Adams [2014] D. Paredes-Barato and C. Adams, All-optical quantum information processing using rydberg gates, Physical review letters 112, 040501 (2014).
  * Vatan and Williams [2004] F. Vatan and C. Williams, Optimal quantum circuits for general two-qubit gates, Phys. Rev. A 69, 032315 (2004).
  * Petersen [2010] I. Petersen, Quantum control theory and applications: a survey, IET Control Theory $\&$ Applications 4, 2651 (2010).
  * Choi  _et al._ [2014] T. Choi, S. Debnath, T. Manning, C. Figgatt, Z.-X. Gong, L.-M. Duan, and C. Monroe, Optimal quantum control of multimode couplings between trapped ion qubits for scalable entanglement, Physical review letters 112, 190502 (2014).
  * Brown  _et al._ [2016] K. R. Brown, J. Kim, and C. Monroe, Co-designing a scalable quantum computer with trapped atomic ions, npj Quantum Information 2, 1 (2016).
  * Cruz  _et al._ [2019] D. Cruz, R. Fournier, F. Gremion, A. Jeannerot, K. Komagata, T. Tosic, J. Thiesbrummel, C. L. Chan, N. Macris, M.-A. Dupertuis, _et al._ , Efficient quantum algorithms for ghz and w states, and implementation on the ibm quantum computer, Advanced Quantum Technologies 2, 1900015 (2019).
  * Saeedi and Pedram [2013] M. Saeedi and M. Pedram, Linear-depth quantum circuits for $n$-qubit toffoli gates with no ancilla, Phys. Rev. A 87, 062318 (2013).
  * Note [3] We note that theoretical lower bound for the number of CNOT gates required for the $m$-bit Toffoli gate is $\Omega(m)$ [83].
  * James  _et al._ [2013] G. James, D. Witten, T. Hastie, and R. Tibshirani,  _An introduction to statistical learning_ , Vol. 112 (Springer, 2013).
  * Barredo  _et al._ [2018] D. Barredo, V. Lienhard, S. De Leseleuc, T. Lahaye, and A. Browaeys, Synthetic three-dimensional atomic structures assembled atom by atom, Nature 561, 79 (2018).
  * Deutsch [1989] D. E. Deutsch, Quantum computational networks, Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences 425, 73 (1989).
  * Suzuki [1991] M. Suzuki, General theory of fractal path integrals with applications to many-body theories and statistical physics, Journal of Mathematical Physics 32, 400 (1991).
  * Childs and Su [2019] A. M. Childs and Y. Su, Nearly optimal lattice simulation by product formulas, Physical review letters 123, 050503 (2019).
  * Jordan  _et al._ [2012] S. P. Jordan, K. S. M. Lee, and J. Preskill, Quantum algorithms for quantum field theories, Science 336, 1130 (2012), https://science.sciencemag.org/content/336/6085/1130.full.pdf .
  * Lieb and Robinson [1972] E. H. Lieb and D. W. Robinson, The finite group velocity of quantum spin systems, in  _Statistical mechanics_ (Springer, 1972) pp. 425–431.
  * Hastings [2010] M. B. Hastings, Locality in quantum systems, Quantum Theory from Small to Large Scales 95, 171 (2010).
  * Low  _et al._ [2016] G. H. Low, T. J. Yoder, and I. L. Chuang, Methodology of resonant equiangular composite quantum gates, Physical Review X 6, 041067 (2016).
  * Shende and Markov [2008] V. V. Shende and I. L. Markov, On the cnot-cost of toffoli gates, arXiv preprint arXiv:0803.2316 (2008).