#  in Proc. of EMNLP 2021 (short)
RockNER: A Simple Method to Create Adversarial Examples
for Evaluating the Robustness of Named Entity Recognition Models

Bill Yuchen Lin Wenyang Gao Jun Yan Ryan Moreno Xiang Ren
<EMAIL_ADDRESS>
Department of Computer Science and Information Sciences Institute,
University of Southern California

###### Abstract

To audit the robustness of named entity recognition (NER) models, we propose
RockNER, a simple yet effective method to create natural adversarial examples.
Specifically, at the entity level, we replace target entities with other
entities of the same semantic class in Wikidata; at the context level, we use
pre-trained language models (e.g., BERT) to generate word substitutions.
Together, the two levels of attack produce natural adversarial examples that
result in a shifted distribution from the training data on which our target
models have been trained. We apply the proposed method to the OntoNotes
dataset and create a new benchmark named OntoRock for evaluating the
robustness of existing NER models via a systematic evaluation protocol. Our
experiments and analysis reveal that even the best model has a significant
performance drop, and these models seem to memorize in-domain entity patterns
instead of reasoning from the context. Our work also studies the effects of a
few simple data augmentation methods to improve the robustness of NER models.
111Our code and data are publicly available at the project website:
https://inklab.usc.edu/rockner.

##  1 Introduction

Recent named entity recognition (NER) models have achieved great performance
on many conventional benchmarks such as CoNLL2003 Tjong Kim Sang (2002) and
OntoNotes 5.0 Weischedel et al. (2013). However, it is not clear whether they
are reliable in realistic applications in which entities and/or context words
can be out of the distribution of the training data. It is thus important to
audit the robustness of NER systems via natural adversarial attacks. Most
existing methods for generating adversarial attacks in NLP focus on sentence
classification (Jin et al., 2020; Li et al., 2020; Minervini and Riedel, 2018)
and question answering (Jia and Liang, 2017; Ribeiro et al., 2018; Gan and Ng,
2019), and these methods lack special designs reflecting the underlying
compositions of the NER examples — i.e., entity structures and their context
words. In this paper, we focus on creating general natural adversarial
examples (i.e., real-world entities and human-readable context) for evaluating
the robustness of NER models.

Figure 1: Illustration of RockNER attacking pipeline.

As shown in Figure 1, given a NER example, our method first generates entity-
level attacks by replacing the original entities with entities from Wikidata
and then uses a pre-trained masked language model like BERT Devlin et al.
(2019a) to generate context-level attacks. We choose the OntoNotes dataset
Weischedel et al. (2013)222The proposed attacking method is also applicable to
other general NER datasets. to showcase RockNER because of the dataset’s high
annotation quality and wide coverage of entity types. Thus, we create a novel
benchmark, named OntoRock, for evaluating the robustness of a wide range of
modern NER models.

We analyze the robustness of popular existing NER models on the OntoRock
benchmark in order to answer three research questions as follows: (Q1) How
robust are current NER models? (Q2) Where are the NER models brittle? (Q3) Can
we improve the robustness of NER models via data augmentation? Our experiments
and analysis provide these main findings: 1) even the best model is still
brittle to our natural adversarial examples, resulting in a significant
performance drop (92.4% $\rightarrow$ 58.5% in F1); 2) current NER models tend
to memorize entity patterns instead of reasoning based on the context; also,
there are specific patterns for entity typing mistakes; 3) simple data
augmentation methods can indeed help us improve the robustness to some extent.
We believe the proposed RockNER method, the OntoRock benchmark, and our
analysis will benefit future research to improve the robustness of NER models.

##  2 Natural Adversarial Attacks for NER

We present RockNER, a simple yet effective method to generate high-quality
natural adversarial examples for evaluating the robustness of NER models by
perturbing both the entities and contexts of original examples. We apply the
method to the development set and test set of OntoNotes to create the OntoRock
benchmark.

###  2.1 Entity-Level Attacks

To generate relevant entities for modifying existing NER data, we collect a
dictionary of natural adversarial entities of different fine-grained classes
via Wikidata. As shown in Figure 2, our three-stage pipeline is introduced as
follows:

  * •

(1) Entity Linking: We first use BLINK Wu et al. (2020) to link each entity in
the original examples from its surface form to a canonical entry in Wikidata
with a unique identifier (QID), e.g., “Beijing” $\rightarrow Q956$.

  * •

(2) Fine-grained Classification: Then, we execute a query to get its fine-
grained class via the InstanceOf relation (P31), e.g.,
$Q956\xrightarrow[]{P31}Q1549591$ (“big city”).

  * •

(3) Dictionary Expansion: Finally, we retrieve additional Wikidata entities
within each individual entity class. Given a particular entity such as
“Beijing”, we collect additional out-of-distribution entities, such as “Bari”.
They are both big cities (Gpe type), while the latter one is much less
correlated with the context in the training data333We assure this by applying
tested NER systems (§3) on sentences where each sentence is the an individual
entity name, and only keep the ones the target models predict incorrectly..

To ensure the quality, we manually curate the fine-grained entity classes and
remove entities linked incorrectly. We use a different approach for collecting
Person attack entities because adversarial names can be more efficiently
created as random combinations of first names, middle names, and last names,
which are collected from the Wikidata person-name list444We used the method
described in https://github.com/EdJoPaTo/wikidata-person-names.

To create an evaluation benchmark based on existing datasets (e.g.,
OntoNotes), we iterate over every original entity and replace it with a
randomly sampled adversarial entity from our dictionary sharing the same fine-
grained class. We argue that the resulting attacks are both natural — i.e.,
containing real, valid entities, and adversarial — i.e., the entities are of
the same class as the original entities while being out-of-distribution from
the training data. Specifically, OntoRock has a much larger vocabulary of
entity words than OntoNotes, and these words are rarely seen in the training
set (Table 4 in Appendix §B). For example, for Gpe and Product, OntoRock has
$\sim$3x the number of unique entity words as OntoNotes has (Gpe: $461$ vs.
$1202$, Product: $54$ vs. $158$). The ratio of seen entity words is also much
lower (Gpe: $75.92\%$ vs. $17.30\%$, Product: $44.44\%$ vs. $7.59\%$).

Figure 2: Building adversarial entity dictionary.

###  2.2 Context-level Attacks

To investigate the robustness of NER models against changes to the context, we
also create natural attacks on the context words. Our intuition is to replace
context words with words that are semantically related and syntactically valid
but out of the distribution of the training data. To this end, we perturb the
original context by sampling adversarial tokens via a masked-language model
such as BERT. Specifically, for each sentence, we choose semantic-rich words —
nouns, verbs, adjectives, and adverbs — as the target tokens to replace. Then,
we generate masked sentences with random numbers (at most 3) of [mask] tokens.
These masked sentences are then fed into BERT, which decodes the masked
positions one by one from left to right. We use the predicted tokens ranking
between 100$\sim$200, such that the words create more challenging context yet
the sentence is still syntactically valid. As there are multiple sampled
sentences, we take the one which is the least correlated with the training
data. Specifically, we test all candidate sentences on the trained BLSTM-CRF
model (which performs the worst among the target NER models) and we select the
sentences that cause a performance drop.

|  None |  E |  C |  E+C
---|---|---|---|---
BLSTM-CRF | 84.6 | 40.5 ($\downarrow$ 52%) | 77.3 ($\downarrow$ 9%) | 32.4 ($\downarrow$ 62%)
SpaCy | 87.3 | 43.9 ($\downarrow$ 50%) | 81.8 ($\downarrow$ 6%) | 40.1 ($\downarrow$ 54%)
Stanza | 87.9 | 56.1 ($\downarrow$ 36%) | 83.0 ($\downarrow$ 6%) | 51.7 ($\downarrow$ 41%)
BERT-CRF | 90.6 | 59.2 ($\downarrow$ 35%) | 85.8 ($\downarrow$ 5%) | 54.6 ($\downarrow$ 40%)
Flair | 90.7 | 59.6 ($\downarrow$ 34%) | 86.1 ($\downarrow$ 5%) | 55.3 ($\downarrow$ 39%)
RoBERTa-CRF |  92.4 |  63.4 ($\downarrow$ 31%) |  87.2 ($\downarrow$ 6%) |  58.5 ($\downarrow$ 37%)
\+ Ent. Switch. | 91.4 | 64.7 ($\downarrow$ 29%) | 85.7 ($\downarrow$ 6%) | 59.1 ($\downarrow$ 35%)
\+ Rand. Mask. | 92.6 |  66.3 ($\downarrow$ 28%) | 86.4 ($\downarrow$ 7%) |  60.0 ($\downarrow$ 35%)
\+ Mixing Up | 92.0 | 61.1 ($\downarrow$ 34%) |  86.9 ($\downarrow$ 6%) | 56.5 ($\downarrow$ 39%)
Table 1:  F1 scores of models trained on OntoNotes’ training data and
evaluated in different settings:  none (original test of OntoNotes) and three
variants of our OntoRock benchmark: ( E for entity-only attacks,  C for
context-only attack, and  E+C for the full version). Relative F1 drops shown
as ($\downarrow x$).

###  2.3 OntoRock as a Robustness Benchmark

We create the most challenging version of our RockNER attack by applying both
entity-level and context-level attacks on the original development and test
sets of OntoNotes, forming our OntoRock benchmark. The overall statistics of
OntoRock are shown in Table 3 (Appendix §B), alongside the statistics of the
original OntoNotes dataset. We showcase RockNER using OntoNotes in this paper
because of the dataset’s high annotation quality and comprehensive entity-type
coverage. However, this method of attack is also applicable to other datasets.

##  3 Evaluating Robustness of NER Models

In this section, we use our OntoRock dataset to evaluate the robustness of
popular NER models including spaCy Honnibal et al. (2020), Stanza Qi et al.
(2020), Flair Akbik et al. (2018a), BLSTM-CRF Lample et al. (2016), BERT-CRF
Devlin et al. (2019b), and RoBERTa-CRF Liu et al. (2019). Model details are
described in Appendix §C. We organize our results and analysis as three main
research questions and their answers.

[couleur= msftBlue!15, arrondi=0, logo=, marge=2, couleurBord=msftBlue!10,
sousTitre =Q1: How robust are current NER models?]

#### Main results.

We show the F1 scores on the test sets555Full results on dev and test are
reported in Appendix §D. in Table 1. We can see that all NER models have a
significant performance drop in the attacked settings (i.e., entity attack
only, context attack only, and both); there is a 35% $\sim$ 62% relative
decrease (in the models’ F1) in the fully-attacked setting as compared to
their results666All models are trained on the OntoNotes’ training data.  on
the original test set. We find the performance on the original test set is
positively correlated with the robustness against our attacks. Thus, models
that perform better on in-domain data tend to be also better at handling out-
of-distribution examples.

#### Pre-training & Robustness.

BLSTM-CRF is trained solely on the training set of OntoNotes; The NER toolkits
such as spaCy and Stanza are trained on more datasets (e.g., CoNLL03); BERT-
CRF, Flair, and RoBERTa-CRF are based on pre-trained language models. We can
see that, in terms of robustness, NER models with pre-training tend to
outperform models without pre-training but with more NER data access, which
outperform those trained only on the OntoNotes training set. This observation
indicates that pre-training (on corpora or other NER data) leads to better
robustness, and better pre-trained models (RoBERTa vs. BERT) have a lower
(relative) performance drop. Interestingly, we find that the improved
robustness from pre-training mainly comes from the improvement on the entity-
level attacks, possibly because of the increased exposure to entities and
increased ability to reason using context (see our 1st point in Q2).

Figure 3:  Error analysis of RoBERTa-CRF. Left: Difference of predictions on
OntoNotes and OntoRock. Right: Difference of confusion matrices.

[couleur= msftBlue!15, arrondi=0, logo=, marge=2, couleurBord=msftBlue!10,
sousTitre =Q2: Where are the NER models brittle?]

#### Memorizing or Reasoning?

Note that our entity-level attacks aim to test the ability to use the context
to infer the entities, as the novel entities themselves are out-of-
distribution — i.e., if a model can reason about the context, it should be
robust against entity changes. In turn, the context-level attacks audit the
ability to memorize entity patterns, as the context is changed, making it more
challenging to infer from. From Table 1, we can see that all models have a
smaller performance drop in context-level attacks and a larger performance
drop in entity-level attacks. Therefore, we conclude that NER models are apt
to memorize entity patterns presented in the training data and are more
brittle when emerging, out-of-distribution entities exist in the inputs. This
also suggests that current NER models tend infer the type and boundary of
entities without properly using the context. To make NER models more robust,
we believe an important future direction is to develop context-based reasoning
approaches, taking advantage of inductive biases such as entity triggers Lin
et al. (2020).

#### Error Analysis.

To analyze the additional errors caused by our attacks, we look at each truth
entity and inspect the changes of model behaviors in this position. We pair
each original entity with its overlapped prediction and categorize it as
follows: (1) whether the predicted type matches (Correct/Wrong); (2) the
number of different tokens between the prediction and truth ($d$). In Figure 3
(left), RoBERTa-CRF’s predictions on OntoNotes and OntoRock and find that most
additional error cases (86.4% vs. 62.3%) are caused by typing errors — the
model either predicts a wrong type (4.5% vs. 14.3%), or None (7.1% vs. 10.8%).
Concrete cases are shown in Figure 5 (Appendix §E).

We take a closer look by calculating the difference between the models’
confusion matrices on the attacked and the original test data (i.e.,
OntoRock’s minus OntoNotes’), as shown in Figure 3 (right). This confusion-
difference matrix reveals the model’s weakness in handling novel entities,
especially when making decisions between closely related categories. For
example, the biggest difference is the typing error from Loc to Gpe (increased
by 30 points)777Gpe (Geo-Political Entity) is defined to include “countries,
cities, states”, while Loc (Location) is defined as “non-GPE locations,
mountain ranges, bodies of water”. — indicating that the model struggles to
recognize names of countries/cities/states that are not covered by the
distribution of training data.

Apart from that, we find that the entity-level and context-level attacks
succeed in different parts of examples. We denote the sets of entity spans
that are mistakenly predicted in entity-only attacks and context-only attacks
as $S_{\text{E}}$ and $S_{\text{C}}$. Their Jaccard similarity is only $0.04$,
which shows that these two attacks target different kinds of weaknesses.

[couleur= msftBlue!15, arrondi=0, logo=, marge=2, couleurBord=msftBlue!10,
sousTitre =Q3: Can we improve the robustness of NER models via data
augmentation?]

Figure 4: Three simple methods for augmenting training data to improve the
robustness of NER.

#### Methods.

The most straightforward method to improve NER robustness is to augment our
examples used for training models. Here we use three intuitive data
augmentation methods for the analysis. 1) Entity Switching: we replace each
entity in the target sentence with a different entity of the same type from
another sentence. 2) Random Masking: for each entity, we replace every one of
its letters with a random one. We retain the same capitalization pattern and
keep all stopwords unchanged. 3) Mixing up: inspired by Guo et al. (2019), we
randomly pick one entity from the target sentence and find another sentence
that includes an entity of the same type; then we generate an adversarial
sentence by merging the first half of the target sentence (up to and including
the entity) with the second half of the second sentence (everything after the
entity). They are illustrated with examples in Figure 4.

#### Results & Analysis.

The results of the three methods on the RoBERTa-CRF model are shown in Table
1. Surprisingly, the most straightforward method, Random Masking, offers the
best improvement against entity-level attacks. We conjecture it is because it
provides more entity patterns, which enhances its entity-level generalization
ability and makes models focus more on the context for inference, resulting in
a better performance on entity-level attacks (63.4% $\rightarrow$ 66.3%). As
the Entity Switching repeats original entities in the different context of the
training set, it aims to improve the performance in using context to infer
entities. The entity-level attacks are indeed better handled (63.4%
$\rightarrow$ 64.7%). The Mixing up method, however, loses the robustness on
all settings, possibly due to potential noise from sentences that are not
syntactically valid.

##  4 Related Work

There are other recent works which also turn their attention from achieving a
new state-of-the-art of NER model towards studying NER models’ robustness and
generalization ability. Agarwal et al. (2020a) create entity-switched datasets
by replacing entities with others of the same type but different national
origin. They find that NER models perform worse on entities from certain
countries. Mayhew et al. (2020) and Bodapati et al. (2019) focus on the
robustness when inputs are not written in the standard casing (e.g., “he is
from us” $\rightarrow$ “US”). Fu et al. (2020) analyze the generalization
ability of current NER models by evaluating them across datasets. Agarwal et
al. (2020b) further analyze the roles of context and names in entity
predictions made by models and humans. Although these works begin to
understand the robustness issue of NER models, they do not build an automated
pipeline to generate natural adversarial instances with large coverage (e.g.
thousands of fine-grained classes) at scale.

There are also works in other domains aiming to evaluate models’ robustness
with perturbed inputs. For example, Jia and Liang (2017) attack reading
comprehension models by adding word sequences to the input. Gan and Ng (2019)
and Iyyer et al. (2018) paraphrase the input to test models’ over-sensitivity.
Jones et al. (2020) target adversarial typos. Si et al. (2021) propose a
benchmark for reading comprehension with diverse types of test-time
perturbation. These works focus on different domains than our research does,
and they do not consider the composition of NER examples. Little attention is
drawn to the entities in the sentences, and many attacks (e.g. character
swapping, word injection) may make the perturbed sentences invalid. To the
best of our knowledge, this work is among the first to propose a
straightforward, dedicated pipeline for generating natural adversarial
examples for the NER task, which takes into account the compositions of NER
examples — i.e., entity structures and their context.

##  5 Conclusion

Our contributions in this short paper are two-fold. 1) resource-wise: we
develop RockNER, a straightforward method for generating natural adversarial
attacks for NER, which produces OntoRock, a benchmark for auditing the
robustness of NER models. 2) evaluation-wise: our experimental results and
analysis provides answers supported by experimental results to three main
research questions on the robustness of current mainstream NER models. We
believe RockNER and its produced attacks (e.g., the OntoRock benchmark) can
benefit the community working to increase the robustness and out-of-
distribution generalization of NER.888 We leave our full results, more
implementation details, and additional analyses in the appendix.

## Acknowledgements

This research is supported in part by the Office of the Director of National
Intelligence (ODNI), Intelligence Advanced Research Projects Activity (IARPA),
via Contract No. 2019-19051600007, the DARPA MCS program under Contract No.
N660011924033, the Defense Advanced Research Projects Agency with award
W911NF-19-20271, NSF IIS 2048211, NSF SMA 1829268, and gift awards from
Google, Amazon, JP Morgan and Sony. We would like to thank the reviewers for
their constructive feedback.

## References

  * Agarwal et al. (2020a) Oshin Agarwal, Yinfei Yang, Byron C. Wallace, and A. Nenkova. 2020a.  Entity-switched datasets: An approach to auditing the in-domain robustness of named entity recognition models.  _ArXiv preprint_ , abs/2004.04123.
  * Agarwal et al. (2020b) Oshin Agarwal, Yinfei Yang, Byron C. Wallace, and A. Nenkova. 2020b.  Interpretability analysis for named entity recognition to understand system predictions and how they can improve.  _ArXiv preprint_ , abs/2004.04564.
  * Akbik et al. (2018a) Alan Akbik, Duncan Blythe, and Roland Vollgraf. 2018a.  Contextual string embeddings for sequence labeling.  In _Proceedings of the 27th International Conference on Computational Linguistics_ , pages 1638–1649, Santa Fe, New Mexico, USA. Association for Computational Linguistics.
  * Akbik et al. (2018b) Alan Akbik, Duncan Blythe, and Roland Vollgraf. 2018b.  Contextual string embeddings for sequence labeling.  In _Proceedings of the 27th International Conference on Computational Linguistics_ , pages 1638–1649, Santa Fe, New Mexico, USA. Association for Computational Linguistics.
  * Bodapati et al. (2019) Sravan Bodapati, Hyokun Yun, and Yaser Al-Onaizan. 2019.  Robustness to capitalization errors in named entity recognition.  In _Proceedings of the 5th Workshop on Noisy User-generated Text (W-NUT 2019)_ , pages 237–242, Hong Kong, China. Association for Computational Linguistics.
  * Devlin et al. (2019a) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019a.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Devlin et al. (2019b) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019b.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Fu et al. (2020) Jinlan Fu, Pengfei Liu, and Qi Zhang. 2020.  Rethinking generalization of neural models: A named entity recognition case study.  In _The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020_ , pages 7732–7739. AAAI Press.
  * Gan and Ng (2019) Wee Chung Gan and Hwee Tou Ng. 2019.  Improving the robustness of question answering systems to question paraphrasing.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 6065–6075, Florence, Italy. Association for Computational Linguistics.
  * Guo et al. (2019) Hongyu Guo, Yongyi Mao, and Richong Zhang. 2019.  Augmenting data with mixup for sentence classification: An empirical study.  _ArXiv preprint_ , abs/1905.08941.
  * Honnibal et al. (2020) Matthew Honnibal, Ines Montani, Sofie Van Landeghem, and Adriane Boyd. 2020.  spaCy: Industrial-strength Natural Language Processing in Python.
  * Iyyer et al. (2018) Mohit Iyyer, John Wieting, Kevin Gimpel, and Luke Zettlemoyer. 2018.  Adversarial example generation with syntactically controlled paraphrase networks.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)_ , pages 1875–1885, New Orleans, Louisiana. Association for Computational Linguistics.
  * Jia and Liang (2017) Robin Jia and Percy Liang. 2017.  Adversarial examples for evaluating reading comprehension systems.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_ , pages 2021–2031, Copenhagen, Denmark. Association for Computational Linguistics.
  * Jin et al. (2020) Di Jin, Zhijing Jin, Joey Tianyi Zhou, and Peter Szolovits. 2020.  Is BERT really robust? A strong baseline for natural language attack on text classification and entailment.  In _The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020_ , pages 8018–8025. AAAI Press.
  * Jones et al. (2020) Erik Jones, Robin Jia, Aditi Raghunathan, and Percy Liang. 2020.  Robust encodings: A framework for combating adversarial typos.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 2752–2765, Online. Association for Computational Linguistics.
  * Lample et al. (2016) Guillaume Lample, Miguel Ballesteros, Sandeep Subramanian, Kazuya Kawakami, and Chris Dyer. 2016.  Neural architectures for named entity recognition.  In _Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 260–270, San Diego, California. Association for Computational Linguistics.
  * Li et al. (2020) Linyang Li, Ruotian Ma, Qipeng Guo, Xiangyang Xue, and Xipeng Qiu. 2020.  BERT-ATTACK: Adversarial attack against BERT using BERT.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 6193–6202, Online. Association for Computational Linguistics.
  * Lin et al. (2020) Bill Yuchen Lin, Dong-Ho Lee, Ming Shen, Ryan Moreno, Xiao Huang, Prashant Shiralkar, and Xiang Ren. 2020.  TriggerNER: Learning with entity triggers as explanations for named entity recognition.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 8503–8511, Online. Association for Computational Linguistics.
  * 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_ , abs/1907.11692.
  * Mayhew et al. (2020) Stephen Mayhew, Nitish Gupta, and Dan Roth. 2020.  Robust named entity recognition with truecasing pretraining.  In _The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020_ , pages 8480–8487. AAAI Press.
  * Minervini and Riedel (2018) Pasquale Minervini and Sebastian Riedel. 2018.  Adversarially regularising neural NLI models to integrate logical background knowledge.  In _Proceedings of the 22nd Conference on Computational Natural Language Learning_ , pages 65–74, Brussels, Belgium. Association for Computational Linguistics.
  * Pradhan et al. (2013) Sameer Pradhan, Alessandro Moschitti, Nianwen Xue, Hwee Tou Ng, Anders Björkelund, Olga Uryupina, Yuchen Zhang, and Zhi Zhong. 2013.  Towards robust linguistic analysis using OntoNotes.  In _Proceedings of the Seventeenth Conference on Computational Natural Language Learning_ , pages 143–152, Sofia, Bulgaria. Association for Computational Linguistics.
  * Qi et al. (2020) Peng Qi, Yuhao Zhang, Yuhui Zhang, Jason Bolton, and Christopher D. Manning. 2020\.  Stanza: A python natural language processing toolkit for many human languages.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics: System Demonstrations_ , pages 101–108, Online. Association for Computational Linguistics.
  * Ribeiro et al. (2018) Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. 2018.  Semantically equivalent adversarial rules for debugging NLP models.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 856–865, Melbourne, Australia. Association for Computational Linguistics.
  * Si et al. (2021) Chenglei Si, Ziqing Yang, Yiming Cui, Wentao Ma, Ting Liu, and Shijin Wang. 2021\.  Benchmarking robustness of machine reading comprehension models.  In _Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021_ , pages 634–644, Online. Association for Computational Linguistics.
  * Tjong Kim Sang (2002) Erik F. Tjong Kim Sang. 2002.  Introduction to the CoNLL-2002 shared task: Language-independent named entity recognition.  In _COLING-02: The 6th Conference on Natural Language Learning 2002 (CoNLL-2002)_.
  * Weischedel et al. (2013) Ralph Weischedel, Martha Palmer, Mitchell Marcus, Eduard Hovy, Sameer Pradhan, Lance Ramshaw, Nianwen Xue, Ann Taylor, Jeff Kaufman, Michelle Franchini, et al. 2013.  Ontonotes release 5.0 ldc2013t19.  _Linguistic Data Consortium, Philadelphia, PA_ , 23.
  * Wu et al. (2020) Ledell Wu, Fabio Petroni, Martin Josifoski, Sebastian Riedel, and Luke Zettlemoyer. 2020.  Scalable zero-shot entity linking with dense entity retrieval.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 6397–6407, Online. Association for Computational Linguistics.

##  Appendix A Statistics of the Entity Dictionary

In Table 2, we show statistics of the adversarial entity dictionary built for
the test set. We generate 279,290 adversarial entities out of 7,433 original
entities. The amount of generated entities is 36 times larger than the
original ones, which extremely enriches candidates for conducting entity-level
attacks. Moreover, there is one class for every 2$\sim$10 entities according
to their type, and each class includes hundreds of adversarial entities. This
indicates that we have enough adversarial entities to conduct entity-level
attacks.

Type | # Original | # Classes | # Adversarial
---|---|---|---
GPE | 2,203 | 237 | 42,912
ORG | 1,750 | 402 | 75,259
FAC | 135 | 84 | 29,041
LOC | 179 | 75 | 20,354
NORP | 830 | 117 | 27,033
LAW | 40 | 14 | 3,920
EVENT | 63 | 33 | 9,636
WOA | 165 | 73 | 39,508
PRODUCT | 74 | 48 | 17,986
LANG | 22 | 7 | 4,119
PERSON | 1,972 | N/A | 9,522
Total | 7,433 | 1,090 | 279,290
Table 2: Statistics of the adversarial entity dictionary.

##  Appendix B Statistics of the Dataset

| Train | Dev | Test
---|---|---|---
# Sentences | 59,924 | 8,528 | 8,262
# Tokens | 1.1M | 148k | 153k
# Entities | 55,008 | 7,482 | 7,433
# Attacked Entities | N/A | 6,962 | 6,939
% Attacked Entities | N/A | 93.05 | 93.35
# Attacked Context Words | N/A | 16,155 | 15,664
% Attacked Sentences | N/A | 98.03 | 97.53
Table 3: Overall statistics of OntoRock benchmark. | Train | OntoNotes Test | OntoRock Test
---|---|---|---
| # ent_words | # ent_words | seen (%) | # ent_words | seen (%)
GPE | 1615 | 461 | 75.92 | 1202 | 17.30
ORG | 4037 | 1056 | 67.42 | 2399 | 26.18
FAC | 681 | 125 | 55.20 | 287 | 19.16
LOC | 527 | 118 | 66.95 | 224 | 22.32
NORP | 565 | 160 | 78.13 | 330 | 8.18
LAW | 343 | 74 | 45.95 | 116 | 26.72
EVENT | 439 | 91 | 64.84 | 132 | 23.48
WOA | 1107 | 264 | 37.12 | 351 | 17.95
PERSON | 5367 | 1102 | 61.62 | 1011 | 31.95
PRODUCT | 381 | 54 | 44.44 | 158 | 7.59
LANGUAGE | 33 | 7 | 71.43 | 25 | 4.00
ALL_TYPES | 12174 | 3028 | 68.13 | 5522 | 31.44
Table 4: Entity statistics of OntoNotes and OntoRock benchmarks.

We adopt the train/dev/test splits of OntoNotes used by Pradhan et al. (2013)
in our experiments. Table 3 presents the statistics of our OntoRock benchmark,
which consists of the original OntoNotes training set and our attacked (full
version) development and test sets. Table 4 shows the statistics of entities
in the training set, OntoNotes’ test set and OntoRock’s test set.

##  Appendix C Model Details

For spaCy, we load the “en_core_web_lg” model with the white-space tokenizer.

For the Stanza model, we use the English model and set processors as
“tokenize, ner” with tokenize_pretokenized= True.

When we train the Flair model with a GPU, we set mini_batch_size as 64,
train_with_dev as False and embeddings_storage_mode as “none”.

For training BLSTM-CRF, BERT-CRF and RoBERTa-CRF models, we set batch_size as
20. We use early stopping and set patience=10 for BLSTM-CRF and 5 for the
other two.

##  Appendix D Full Results

Precision/Recall/F1 scores for each model on the original OntoNotes and our
OntoRock benchmark are presented in Table 6 (test set) and Table 7
(development set).

Robustness Analysis (by prediction) | RoBERTa-CRF (%) | RB-CRF+ES (%) | RB-CRF+RM (%) | RB-CRF+M (%)
---|---|---|---|---
Attacked | Unattacked | Attacked | Unattacked | Attacked | Unattacked | Attacked | Unattacked
Correct Type | d=0 (SameSpan) | 62.55 | 86.44 | 64.78 | 83.40 | 66.41 | 86.23 | 60.59 | 84.41
| d=1
---
6.46 | 0.20 | 5.76 | 0.00 | 6.49 | 0.20 | 7.09 | 1.42
| d=2
---
1.02 | 0.61 | 0.60 | 1.01 | 1.07 | 0.81 | 0.73 | 1.01
| d$\geqslant$3
---
1.77 | 1.01 | 1.69 | 2.53 | 1.75 | 1.21 | 1.51 | 1.42
Wrong Type | d=0 (SameSpan) | 14.27 | 4.45 | 14.20 | 4.45 | 12.88 | 4.25 | 14.43 | 4.25
| d=1
---
1.69 | 0.00 | 1.50 | 0.00 | 1.59 | 0.00 | 1.77 | 0.00
| d=2
---
0.59 | 0.20 | 0.72 | 0.00 | 0.55 | 0.20 | 0.59 | 0.20
| d$\geqslant$3
---
0.83 | 0.00 | 1.19 | 0.10 | 1.15 | 0.20 | 1.28 | 0.20
No Prediction | 10.82 | 7.09 | 9.57 | 8.50 | 8.10 | 6.88 | 12.02 | 7.09
Table 5: Error analysis of RoBERTa-CRF and with three different data
augmentation methods. d indicates the number of different indices between
ground-truth entity and the overlapped predictions (ES for Entity Switching,
RM for Random Masking, and M for Mixing up).

##  Appendix E Cases

Figure 5: Example cases for the entity-level attacks.

In Fig. 5, we show examples of entity-level attacks on the RoBERTa. These
examples should be easily solved based on the context. For example, "a host
of" in sentence $1$ and "holiday" in sentence $4$ are both explicit clues. If
NER models are capable of inferring from context, those clues could have
assisted them to achieve better performance. It qualitatively validates our
hypothesis that NER models tend to remember entity patterns instead of
inferring entity labels from context.

Figure 6: F1 scores for the RoBERTa-CRF model under entity-level attacks with
different coverage.

##  Appendix F More Details of Error Analysis

In Figure 7, we present the confusion matrices for RoBERTa-CRF model on the
OntoNotes’ and OntoRock’s teset sets. We use them to calculate the confusion
difference matrix (Figure 3 (right)).

Following Figure 3 (left), we categorize the error cases of predictions by the
RoBERTa-CRF model and its variants that are trained with augmented data. The
results are presented in Table 5. Among three augmentation methods, random
masking gets the highest F1 score on both attacked and original test sets. The
robustness gain mainly comes from more accurate typing (Wrong Type, $d=0$:
14.27% $\rightarrow$ 12.88%).

(a) Confusion matrix for ground truth and predictions
of RoBERTa-CRF model on the OntoNotes test set.

(b) Confusion matrix for ground truth and predictions of RoBERTa-CRF model on
the OntoRock test set.

Figure 7: Confusion matrices for RoBERTa-CRF on OntoNotes’ and OntoRock’s test sets. Evaluation Metrics $\longrightarrow$ | Precision (%) | Recall (%) | F1 (%)
---|---|---|---
Models $\downarrow$ Attack Methods $\rightarrow$ |  None |  E |  C |  E+C |  None |  E |  C |  E+C |  None |  E |  C |  E+C
BLSTM-CRF Lample et al. (2016) | 86.3 | 40.8 | 78.7 | 32.7 | 82.9 | 40.2 | 76.1 | 32.0 | 84.6 | 40.5 | 77.3 | 32.4
spaCy Honnibal et al. (2020) | 88.3 | 43.9 | 82.0 | 40.1 | 86.2 | 44.0 | 81.6 | 40.1 | 87.3 | 43.9 | 81.8 | 40.1
Stanza Qi et al. (2020) | 89.5 | 55.3 | 83.9 | 51.2 | 86.3 | 57.1 | 82.1 | 52.2 | 87.9 | 56.1 | 83.0 | 51.7
BERT-CRF Devlin et al. (2019a) | 91.9 | 59.8 | 86.7 | 55.7 | 89.3 | 58.5 | 84.9 | 53.5 | 90.6 | 59.2 | 85.8 | 54.6
Flair Akbik et al. (2018b) | 91.3 | 59.4 | 86.0 | 55.3 | 90.2 | 59.8 | 86.1 | 55.2 | 90.7 | 59.6 | 86.1 | 55.3
RoBERTa-CRF Liu et al. (2019) |  92.9 |  63.1 |  87.4 |  58.5 |  91.8 |  63.7 |  87.0 |  58.5 |  92.4 |  63.4 |  87.2 |  58.5
RB-CRF+Entity Switching | 92.2 | 64.2 | 85.7 | 58.7 | 90.6 | 65.2 | 85.7 | 59.5 | 91.4 | 64.7 | 85.7 | 59.1
RB-CRF+Random Masking |  92.8 |  65.3 | 86.1 |  59.2 |  92.4 |  67.3 | 86.8 |  60.8 |  92.6 |  66.3 | 86.4 |  60.0
RB-CRF+Mixing Up | 92.5 | 60.7 |  86.7 | 56.3 | 91.4 | 61.5 |  87.0 | 56.8 | 92.0 | 61.1 |  86.9 | 56.5
Table 6: Results of NER models on the test set of OntoNotes with  none changes and three variants of the OntoRock benchmark ( E for entity-only attacks,  C for context-only attacks, and  E+C for the full version). Evaluation Metrics $\longrightarrow$ | Precision (%) | Recall (%) | F1 (%)
---|---|---|---
Models $\downarrow$ Attack Methods $\rightarrow$ |  None |  E |  C |  E+C |  None |  E |  C |  E+C |  None |  E |  C |  E+C
BLSTM-CRF Lample et al. (2016) | 85.4 | 40.0 | 77.2 | 33.2 | 82.5 | 39.9 | 75.2 | 32.6 | 83.9 | 40.0 | 76.2 | 32.9
spaCy Honnibal et al. (2020) | 86.0 | 43.2 | 79.7 | 40.3 | 84.8 | 44.0 | 79.7 | 40.4 | 85.4 | 43.6 | 79.7 | 40.3
Stanza Qi et al. (2020) | 87.5 | 52.6 | 81.1 | 48.8 | 84.2 | 55.2 | 79.2 | 50.8 | 85.8 | 53.9 | 80.1 | 49.8
BERT-CRF Devlin et al. (2019a) | 91.2 | 58.1 | 84.8 | 54.3 | 88.9 | 57.3 | 83.1 | 52.7 | 90.0 | 57.7 | 84.0 | 53.5
Flair Akbik et al. (2018b) | 89.4 | 56.6 | 83.6 | 52.5 | 89.0 | 58.1 | 84.1 | 53.2 | 89.2 | 57.3 | 83.9 | 52.9
RoBERTa-CRF Liu et al. (2019) |  91.3 |  60.9 |  84.9 |  56.1 |  90.4 |  62.2 |  84.8 |  56.9 |  90.0 |  61.6 |  84.8 |  56.5
RB-CRF+Entity Switching | 90.3 | 61.8 | 83.5 | 56.1 | 89.5 | 64.5 | 83.8 | 58.1 | 89.9 | 63.1 | 83.7 | 57.1
RB-CRF+Random Masking | 90.6 |  62.5 | 83.7 |  56.4 |  90.7 |  65.2 | 84.9 |  58.5 |  90.7 |  63.8 | 84.3 |  57.4
RB-CRF+Mixing Up |  90.8 | 58.1 |  84.4 | 53.5 | 90.6 | 60.0 |  85.5 | 55.2 |  90.7 | 59.0 |  85.0 | 54.4
Table 7: Results of NER models on the development set of OntoNotes with  none
changes and three variants of the OntoRock benchmark ( E for entity-only
attacks,  C for context-only attacks, and  E+C for the full version).

##  Appendix G Attacking Curve

For the entity-level attacks, we conduct 5 separate attacks by replacing 20%,
40%, 60%, 80%, and 100% of the entities in the test set. For each model, we
evaluate it on the 5 generated test sets and plot a curve of the F1 scores for
each attack, shown in Fig. 6. The descending trend is intuitive, and the
performance of weak models drops more rapidly than the performance of strong
models.


Istituto Nazionale di Fisica Nucleare, Laboratori Nazionali di Frascati,
Frascati, Italy. ROR: 049jf1a25 ENEA Frascati, Italy. ROR: 01026pq66 Eastern
Mennonite University, Harrisonburg, VA 22802, USA ROR: 059xmmg10 Università
degli studi ”G.Marconi”, Rome, Italy. ROR: 00j0rk173 Sapienza Università di
Roma, Rome, Italy. ROR: 02be6w209

# Status of the production of GEM chambers for the CMS experiment at Large
Hadron Collider

L. Benussiins:a  S. Biancoins:a  R. Campagnolains:a Corresponding author and
presenter M. Caponeroins:ains:b  S. Colafranceschiins:c  S. Meolains:ains:d
E. Paolettiins:a  L. Passamontiins:a  D. Piccoloins:a  D. Pierluigiins:a  A.
Russoins:a  G. Savianoins:ains:e  R. Tesauroins:a
ins:ains:ains:bins:bins:cins:cins:dins:dins:eins:e

###### Abstract

The High Luminosity LHC phase includes an upgrade to the muon stations for the
CMS Experiment. CMS trigger and muon identification performance will be
crucial, and it is, therefore, necessary to install new GEM stations to extend
acceptance in the high-$\eta$ region. An explanation of the quality control
test and an update on the status of production will be provided.

##  1 Introduction

High Luminosity LHC (HL-LHC) will increase the integrated luminosity up to
3000 $fb^{-1}$, tenfold compared to the design value of LHC, and instantaneous
luminosity up to 5 - 7.5 $\cdot 10^{34}{\rm cm^{-2}}{\rm s^{-1}}$ [1]. To
enhance CMS trigger and muon identification performance in high-rate
environment, a second GEM (Gas electron multiplier)-based muon endcap station
will be installed [2]. CMS performance improvements aim to extend acceptance
in the $1.6\;<\;\mid\eta\mid\;<\>2.4$ region111where $\eta$ is pseudorapidity,
defined as: $\eta=-ln[tan(\frac{\theta}{2})]$, with $\theta$ the angle between
the particle three-momentum $\mathbf{p}$ and the beam axis by adding new
detectors in GE2/1 position[3] achieving a rate capability of $2\;{\rm
kHz}/{\rm cm}^{2}$, a time resolution of $8-10\;{\rm ns}$ and an angular
resolution of $500\;{\rm\mu}{\rm rad}$. The construction of GE2/1 station,
begun in 2021, incorporates advanced quality controls and performance checks
[4].

Figure 1: Positioning of GE2/1 chambers in CMS

##  2 Detector assembly and Quality Control

A GEM is a $50\;{\rm\mu m}$ Kapton foil, metal-coated on both sides with a
$5\;{\rm\mu m}$ copper layer and pierced with a high density of holes. With a
voltage applied across the two sides of the foil, a strong electric field
(60-100 kV/cm) is produced inside the GEM holes. By cascading the foils, it is
possible to contain the amplification per individual stage, avoiding
discharges while maintaining high gains (order of $10^{4}$).
The module for GE2/1 station consists of a stack of three GEM foils, enclosed
between a drift and a readout electrode, held together by an external frame.
The internal volume is filled with a mixture of ${\rm Ar}/{\rm CO_{2}}$
(70/30). Three GEM foils are stacked at their edges using thin internal
frames. Foils are segmented in strips to protect them from irreversible
damages, reducing the energy released by a possible discharge. Module ROBs
(Readout Boards) are also divided in 12 sectors, each with 128 strips.

Modules are assembled partly at CERN, partly at external production sites
(Frascati, Bari, Aachen-Ghent, Beijing). The collaboration adopted this
decentralized production approach to guarantee timely mass production with
inherent redundancy. All modules undergo rigorous Quality Control (QC) divided
into 8 phases: QC1-2 at CERN, QC3-5 at CERN and external production sites,
QC6-8 at CERN.

QC1 involves the preliminary inspection of the module main components: the
foil surface conditions, the HV lines and the SMD resistors, the Printed
Circuit Boards (PCBs) that host the drift and readout electrodes, the internal
and external frames.
QC2 involves the qualification of the GEM foils, that are electrically cleaned
from dust or chemical contaminants. The foils resistance is checked: if the
final impedance is higher than $10\,G\Omega$ the foil is accepted.
Subsequently, the leakage current and discharge rate are monitored for several
hours with the GEM foil stored stored in a $N_{2}$ box and powered with HV.
The observed leakage current must be less than $20\,{\rm\mu}{\rm A}$ with HV
between 100 and 600 V for 90 minutes, and less than $2\,{\rm\mu}{\rm A}$ with
HV at 600 V for 14 hours [5].
After QC1 and QC2, construction kits are shipped to the production sites for
assembly. After assembly, the first test to be performed is the QC3 gas
tightness check. The pressure drop inside the module is monitored as a
function of time. Efficient gas tightness also prevents contamination from
external source that may affect the detector performance ($O_{2}$, other
electronegative elements and dust can compromise charge amplification and
foils integrity). The maximum allowable pressure drop is $\Delta p(t)<7\,{\rm
mbar}/{\rm h}$ [4].

QC4 aims to establish the I-V characteristic of the detector to identify any
malfunctions and defects in the HV circuit that powers the module.

The module is flushed with $CO_{2}$, powered up to 4900 V, and the current
through the powering circuit is measured as a function of applied voltage. The
test is considered successful if the I-V curve shows a linear behavior. Non-
linearity would indicate a parasitic impedance, caused by a defect in the HV
circuit or an issue with the GEM foils.

(a) Internal over-pressure, atmospheric pressure and temperature as a function
of time.

(b) High voltage vs. divider current curve and spark rate for a GE2/1 detector
[5]

Figure 2: Results plot for QC3 and QC4.

The final QC5 step of in-site tests is divided into two parts and includes the
effective gain measurement as a function of the divider current and gain
uniformity test across the entire module. An X-ray source is used to irradiate
the whole module and generate a primary current, then subject to
amplification; the test is conducted using an ${\rm Ar}/{\rm CO_{2}}$ mixture
(70/30). The charge collected by each strip segmented on the ROB is measured.
If the charge distribution has the same shape for each strip, then the
detector is uniform.

Figure 3: Effective gain vs. divider current curve and spark rate for a GE2/1
detector

Once all test at the production sites are completed, the modules are shipped
back to CERN for final quality tests on the electronics and validation of
module performance (QC6, QC7, QC8).

##  3 Results and conclusion

A total of 288 modules (144 each endcap) is planned to be assembled. As this
report is being prepared, 98 modules have been assembled (64 modules at CERN,
20 modules at Frascati and Bari sites). The CMS Frascati group has also
contributed to the implementation of the FBG (Fiber Bragg Grating) sensors [6]
used for monitoring the operating temperature, a critical parameter for
detector efficiency [7]. Production of the GEM modules will continue
throughout 2024, followed by installation in the CMS detector.

## References

  * [1] Apollinari G., Béjar Alonso I., Brüning O., Fessia P., Lamont M., Rossi L. Tavian L., High-Luminosity Large Hadron Collider (HL-LHC): Technical Design Report V. 0.1, CERN Yellow Reports: Monographs (CERN, Geneva) 2017.
URL https://cds.cern.ch/record/2284929

  * [2] Sauli F., Nuclear Instruments and Methods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associated Equipment3861997531.
  * [3] Tech. Rep. CERN, CERN, Geneva (2017).
URL https://cds.cern.ch/record/2283189

  * [4] Abbas M., Abbrescia M., Abdalla H., Abdelalim A., AbuZeid S., Agapitos A., Ahmad A., Ahmed A., Ahmed W., Aimè C. et al., Nuclear Instruments and Methods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associated Equipment10342022166716.
  * [5] Kim M. R., Production and quality control of the GEM GE2/1 detector for the upgrade of the CMS endcap muon system,, presented at PoS ICHEP2022 (2023), Vol. 414 2023.
  * [6] Benussi L. et al., Phys. Procedia372012483.
  * [7] Abbas M., Abbrescia M., Abdalla H., Zeid S. A., Agapitos A., Ahmad A., Ahmed A., Ahmed W., Amarjeet S., Asghar I. et al., Two years’ test of a temperature sensing system based on fibre bragg grating technology for the CMS GE1/1 detectors, in proc. of Journal of Physics: Conference Series, Vol. 1561 (IOP Publishing) 2020, p. 012006.


# Constructing Optimal Contraction Trees for Tensor Network Quantum Circuit
Simulation

Cameron Ibrahim2, Danylo Lykov 1, Zichang He 3, Yuri Alexeev 1, Ilya Safro2
1Computational Science Division, Argonne National Laboratory, Argonne IL, USA
2Department of Computer and Information Sciences, University of Delaware,
Newark DE, USA  3University of California Santa Barbara, Santa Barbara,
California, USA

###### Abstract

One of the key problems in tensor network based quantum circuit simulation is
the construction of a contraction tree which minimizes the cost of the
simulation, where the cost can be expressed in the number of operations as a
proxy for the simulation running time. This same problem arises in a variety
of application areas, such as combinatorial scientific computing,
marginalization in probabilistic graphical models, and solving constraint
satisfaction problems. In this paper, we reduce the computationally hard
portion of this problem to one of graph linear ordering, and demonstrate how
existing approaches in this area can be utilized to achieve results up to
several orders of magnitude better than existing state of the art methods for
the same running time. To do so, we introduce a novel polynomial time
algorithm for constructing an optimal contraction tree from a given order.
Furthermore, we introduce a fast and high quality linear ordering solver, and
demonstrate its applicability as a heuristic for providing orderings for
contraction trees. Finally, we compare our solver with competing methods for
constructing contraction trees in quantum circuit simulation on a collection
of randomly generated Quantum Approximate Optimization Algorithm Max Cut
circuits and show that our method achieves superior results on a majority of
tested quantum circuits.
Reproducibility: Our source code and data are available at
https://github.com/cameton/HPEC2022_ContractionTrees.

###### Index Terms:

Contraction Tree, Tensor Network, Quantum Circuit Simulation, QAOA

##  I Introduction

Tensor networks have become a ubiquitous tool for describing high dimensional,
data-sparse tensors in a space efficient manner[8, 15, 30]. In quantum circuit
simulation, tensor networks can be used to model circuits with far more qubits
than a more direct approach such as state vector simulation, so long as the
circuit is sufficiently simple [25]. As such, tensor network based simulation
methods will remain vital for the study of quantum algorithms that require a
large number of qubits until sufficient advances are made with quantum
hardware [25]. Moreover, even with the advanced hardware, such simulation
methods will be important for such tasks as finding suitable parameters in
variational quantum algorithms that utilize both quantum and classical
machines [22]. These networks arise naturally in a variety of disciplines such
as Combinatorial Scientific Computing [hendrickson2006combinatorial],
Probabilistic Modelling [30], Constraint Satisfaction [20], Machine Learning
and Data Mining [12], Physics Modelling [28], and Quantum & Classical Circuit
Simulation[15, 27].

A tensor network is most easily conceptualized as a collection of high-order
matrices called tensors which are connected by edges. These networks are often
used to represent tensors which are impractical to store explicitly in
memory[8]. The fundamental operation performed on these networks is called a
tensor contraction, where two tensors are combined to create a third tensor. A
series of tensor contractions performed on the network is called a tensor
network contraction, which is used to reduce the overall size of the network
in order to evaluate entries of the underlying tensor that the network
represents.

It is useful to represent a tensor network contraction as a contraction tree,
a binary tree whose leaves are tensors in the network, where each internal
vertex represents the tensor contraction of its two children. In the general
case, the cost of any single tensor contraction is exponential in the number
of dimensions of its inputs, as is the size of its output[29]. As such, a
vital part of performing a tensor network contraction is choosing a
contraction tree which minimizes some cost, such as minimizing the size of any
intermediary tensor or the total number of operations performed during your
tensor network contraction[15]. However, it is NP-hard to construct an optimal
contraction tree in the general case for these objectives [29], meaning no
optimal solution can been found deterministically in polynomial time.

Our contribution In this paper, we will show how the computationally hard
portion of constructing a contraction tree can be reduced to a problem of
linear ordering, and give algorithms for constructing an optimal contraction
tree for a given ordering. Furthermore, we will give a useful heuristic for
choosing orderings which will result in high quality contraction trees. This
algorithm is being developed with integration with the QTensor quantum circuit
simulation library in mind [23, 26, 25, 24]. In general, in order to run
simulations of quantum circuits with large numbers of qubits, we must be able
to find a good quality contraction order. As such, finding optimal or near
optimal contraction orders is critical for the development and testing of new
quantum algorithms, benchmarking and profiling upcoming quantum devices, and
verification of quantum advantage and supremacy claims to name a few
applications [3] _Even small improvements to the quality of the contraction
tree will lead to a significant acceleration of quantum simulation. We
demonstrate an improvement over competitive solvers by orders of magnitude on
some instances for a comparable running time._

The paper is structured the following way. Section II provides an introduction
to tensor networks and linear orderings. Section III introduces existing
solvers used for constructing contraction trees for quantum circuit
simulation, which we use for benchmarking the proposed algorithm. In Section
IV, we present a novel polynomial time algorithm for constructing an optimal
contraction tree from a given order and explain the ordering heuristic that
was used. In Section V, we evaluate the developed tree structure optimization
algorithm against Tamaki-2017, FlowCutter, and Cotengra on a collection of
QAOA circuits on different comparison metrics. Finally, Section VI discusses
possible areas for future work, while Section VII offers a conclusion.

##  II Background and notation

###  II-A Matrix Chains and Tensor Networks

An $m$ by $n$ matrix $M$ is a 2 dimensional array of scalar numbers from some
field $\mathbb{F}$ (e.g. $\mathbb{R}$, $\mathbb{C}$). We say this matrix has
two indices, $i$ and $j$, where $\operatorname{size}(i)=m$ and
$\operatorname{size}(j)=n$. The size of $M$ is
$\operatorname{size}(M)=\operatorname{size}(i)\operatorname{size}(j)$.

A matrix $M_{1}$ with indices $\\{i,j\\}$ and a matrix $M_{2}$ with indices
$\\{j,k\\}$ can be combined to form a matrix $M_{1}\ast M_{2}$ with indices
$\\{i,k\\}$ using an operation known as matrix multiplication. Note that the
output has the indices of both its inputs with the shared index removed. The
number of operations required to perform a matrix multiplication is
$\operatorname{size}(i)\operatorname{size}(j)\operatorname{size}(k)$.

Say we are given matrices $M_{1},M_{2},\ldots,M_{n-1},M_{n}$ with indices
$\\{i_{1},i_{2}\\},\\{i_{2},i_{3}\\},\ldots,\\{i_{n-1},i_{n}\\},\\{i_{n},i_{n+1}\\}$.
The Matrix Chain Ordering Problem aims to find the optimal parenthesization of
the matrix chain expression

$\displaystyle M_{1}\ast M_{2}\ast\cdots\ast M_{n-1}\ast M_{n}$

which minimizes the cost of computing this product [9]. Note that this setup
assumes each matrix shares indices only with its neighbors. A given
parenthesization can be expressed as a binary tree with leaves labeled with
matrices. For example, the binary tree in Fig. 1 corresponds to the
parenthesized matrix chain

$\displaystyle((A\ast B)\ast C)\ast(D\ast E).$

We define tensors analogously. A tensor $X$ is an N-dimensional array of
scalar numbers from some field $\mathbb{F}$ with indices
$I=\\{i_{1},\ldots,i_{N}\\}$ (for other perspectives, see [5]).

For a tensor $X$ and an index $i$, we say that $X$ and $i$ are incident to one
another if $i$ is an index of $X$. We define $\operatorname{inc}(X)$ as the
set of indices incident to $X$ and $\operatorname{inc}(i)$ as the set of
tensors incident to $i$. The size of a tensor $X$ is given by

$\displaystyle\operatorname{size}(X)$
$\displaystyle=\prod_{i\in\operatorname{inc}(X)}\operatorname{size}(i)$

Figure 1: An example contraction tree with labeled leaves.

Two tensors $X_{1}$ with indices $I_{1}$ and $X_{2}$ with indices $I_{2}$ can
similarly be combined using an operation known as tensor contraction. The
output $X_{1}\ast X_{2}$ will have indices $I_{1}\triangle I_{2}$, where
$\triangle$ denotes symmetric difference. That is, the output has indices
equal to the union of the input indices, with the intersection removed.
$I_{1}\triangle I_{2}$ are known as output indices, while $I_{1}\cap I_{2}$
are known as the shared indices. The number of scalar operations required to
perform a tensor contraction is given by

$\displaystyle\operatorname{ops}(X,Y)$
$\displaystyle=\operatorname{size}(X\ast Y)\operatorname{share}(X,Y)$

where

$\displaystyle\operatorname{share}(X,Y)$ $\displaystyle=\prod_{i\in
S}\operatorname{size}(i),$ $\displaystyle S$
$\displaystyle=\operatorname{inc}(X)\cap\operatorname{inc}(Y).$

A set of tensors $\mathcal{T}=\\{X_{1},\ldots,X_{n}\\}$ with indices

$\mathcal{I}=\bigcup_{X\in\mathcal{T}}\operatorname{inc}(X)$

is known as a tensor network. Defining $\mathcal{T}^{(0)}=\mathcal{T}$, a
tensor network contraction iteratively picks
$X^{(k)},Y^{(k)}\in\mathcal{T}^{(k)}$ to produce

$\mathcal{T}^{(k+1)}=\left(\mathcal{T}^{(k)}\setminus\left\\{X^{(k)},Y^{(k)}\right\\}\right)\cup\left\\{X^{(k)}\ast
Y^{(k)}\right\\},$

terminating when $\lvert\mathcal{T}^{(k)}\rvert=1$. A contraction order used
for this tensor network contraction can again be represented as a binary tree
[29]. For example, the tree shown in Fig. 1 corresponds to the network
contraction

$\displaystyle\mathcal{T}^{(0)}$ $\displaystyle=\\{A,B,C,D,E\\}$
$\displaystyle\mathcal{T}^{(1)}$ $\displaystyle=\\{A\ast B,C,D,E\\}$
$\displaystyle\mathcal{T}^{(2)}$ $\displaystyle=\\{(A\ast B)\ast C,D,E\\}$
$\displaystyle\mathcal{T}^{(3)}$ $\displaystyle=\\{(A\ast B)\ast C,D\ast E\\}$
$\displaystyle\mathcal{T}^{(4)}$ $\displaystyle=\\{((A\ast B)\ast C)\ast(D\ast
E)\\}.$

Contraction of a tensor network is $\\#$P-Hard in the general case [29].
However, many tensor networks arising in practice may be contracted
efficiently given a good quality contraction order with respect to some cost
function. The costs we consider in this paper are the sum of the number of
scalar operations, maximum number of scalar operations, and maximum tensor
size, which are defined as follows:

$\displaystyle\sum_{k}\operatorname{ops}\left(X^{(k)},Y^{(k)}\right),$ (1)
$\displaystyle\max_{k}\operatorname{ops}\left(X^{(k)},Y^{(k)}\right),\qquad\max_{k}\operatorname{size}\left(X^{(k)}\ast
Y^{(k)}\right).$ (2)

The problem of finding an optimal contraction order is itself NP-Hard [29].

While minimizing the number of scalar operations required would seem to be
more useful than minimizing the maximum number of operations for any
contraction, the latter is actually useful in a parallel setting where many
contractions can be performed simultaneously [21].

###  II-B Quantum Circuits and QAOA

An overview to quantum circuits and quantum computing can be found here [43].
A particular type of quantum circuit which has garnered great deal of research
interest in recent years is the Quantum Approximate Optimization Algorithm
ansatz, particularly those developed to target the graph theoretic MaxCut
problem [13]. QAOA is a variational quantum-classical algorithm inspired by
the adiabatic evolution principle. It is essentially a quantum annealer with a
finite number of steps $p$. The quality of the final solution increases with
$p$, as does the complexity of the circuit.

In quantum circuit simulation, it is possible to represent a quantum circuit
as a high dimensional tensor over the complex numbers [44] or, equivalently,
as a tensor network[27]. In this perspective, each quantum gate is associated
with a tensor $X$ with indices corresponding to the inputs and outputs of the
gate. Two tensors in such a network will share an index only if it corresponds
to a value that has been passed from one corresponding gate to the other. For
the purposes of this paper, we will assume the size of every index in the
network is 2.

With this construction, the costs described in Eq 2 are related to older
literature which achieved similar estimations on the computational cost of
tensor network contractions via quantities called vertex congestion, edge
congestion, and treewidth [27, 29].

In particular, vertex congestion and treewidth are equal to the log of the
maximum number of operations needed for any contraction

$\displaystyle\max_{k}\log_{2}\operatorname{ops}\left(X^{(k)},Y^{(k)}\right),$
(3)

while edge congestion is equal to the log of the maximum size of any
intermediate tensor

$\displaystyle\max_{k}\log_{2}\operatorname{size}\left(X^{(k)}\ast
Y^{(k)}\right).$ (4)

###  II-C Tensor Networks as Graphs

An undirected graph $G=(V,E)$ with no loops and multi-edges, is a set $V$ of
vertices and a set $E\subseteq\binom{V}{2}$ of edges. The weights on the edges
of the graph are denoted by the weighting function $w\colon
E\to\mathbb{R}_{\geq 0}$. For an edge $uv\in E$, $w(uv)$ denotes its weight.
The set of incident edges of a vertex $v$ is the set of edges containing $v$,
denoted $\operatorname{inc}(v)=\\{e\in E\mid v\in e\\}$. The degree of $v$ is
the number of edges incident to $v$,
$\operatorname{deg}(v)=\lvert\operatorname{inc}(v)\rvert$.

Say we have a tensor network $\mathcal{T}$ with indices $\mathcal{I}$ where
$\lvert\operatorname{inc}(i)\rvert=2$ for all $i\in\mathcal{I}$. Then
$\mathcal{T}$ admits a representation as a weighted, undirected graph
$G=(V,E)$. Let $F$ be the function which assigns tensors to vertices and
indices to edges, such that $F(i)=\\{F(X),F(Y)\\}$ if and only if
$i\in\operatorname{inc}(X)\cap\operatorname{inc}(Y)$. The weight function $w$
is defined as $w(F(i))=\log_{2}\operatorname{size}(i)$.

A linear vertex ordering for a graph $G=(V,E)$ is a bijective mapping
$\sigma\colon V\to\\{1,\ldots,\lvert V\rvert\\}$. A linear ordering problem on
a graph generally aims to find a linear ordering which minimizes a given cost
function, such as the $p$-Sum objective, which is defined as

$\displaystyle\left(\sum_{uv\in
E}w(uv)\lvert\sigma(u)-\sigma(v)\rvert^{p}\right)^{1/p}$

[33]. For the special case where $p=1$, this problem is known as the Minimum
Linear Arrangement Problem [32].

###  II-D Multilevel algorithms and refinement

The multilevel approach is a big class of algorithms actively used in many
different areas of scientific computing, optimization, and machine learning
[6]. In the context of this work, we briefly describe a version of multilevel
algorithms for graph optimization problems [31, 7]. When the graph is large
and a fast solution of an optimization problem is required for a specific
application, it is often useful to compress the problem by (possibly
nonlinearly) aggregating variables into, so called, coarse variables. This is
done in a such way that a solution for each coarse variable can be effectively
interpolated back to those variables that participated in the aggregation. The
entire process of problem coarsening is performed gradually forming a
multilevel hierarchy of coarse problems. Each next coarser problem
approximates the previous finer problem from which it has been created. Thus,
the number of variables at each level of this hierarchy is decreasing which
allows to solve them faster that the original problem. When sufficiently small
coarsest level is created, the best possible (often exact) solution is
computed. The last stage of framework (called uncoarsening) is to gradually
solve the problems at each level of coarseness by (1) interpolating the
initial solution for the current fine level from the coarser level, and (2)
refining the interpolated solution.

If both coarsening and uncoarsening are computed locally (i.e., their
complexity is linear in the number of variables) then the entire multilevel
framework becomes of linear or nearly-linear complexity assuming that the
number of variables at each level is decreasing within a factor of 1.5-2.5. It
is important to mention that this approach is different than such one-shot
compression approaches as truncated SVD. Such problems on graphs as
partitioning [2, 34], various linear orderings [18, 35], and community
detection [41, 19] have benefited from the multilevel approaches to mention
just few of them [42].

##  III Related Work

###  III-A FlowCutter

FlowCutter is used collectively to refer to an algorithm for computing small,
balanced s-t cuts using Pareto optimization [17], as well as an algorithm
utilizing the former to construct a tree decomposition of the input graph via
recursive bisection [39], that is also a form of a multilevel algorithm.

FlowCutter was entered into heuristic track of the PACE 2017 Parameterized
Algorithms and Computational Experiments Challenge on minimizing treewidth,
where it placed second as the only solver to find a solution for all test
instances in the allotted 30 minutes [39, 10]. Moreover, FlowCutter is known
to be useful in finding high quality tensor network contraction [11].

###  III-B Tamaki-2017

The Tamaki-2017 solver is a tree decomposition solver with components
submitted to the exact and heuristic tracks for PACE 2017 [10]. On the
heuristic track, this solver ranked first place, tending to achieve better
results on smaller instances than the competitive approaches, while sometimes
failing to find an answer in the allotted time for larger instances [39].

The Tamaki-2017 algorithm is based on positive-instance driven dynamic
programming, and, similar to FlowCutter, operates recursively on minimal
separators of the instance graph[40].

###  III-C Cotengra

Cotengra is a library for the efficient contraction of tensor networks [16].
In their seminal paper on the subject, the authors introduce a method for
directly constructing contraction trees based on recursive bisection [15]. By
utilizing existing hypergraph partitioning solvers such as KaHyPar [36],
Cotengra is able to construct contraction trees utilizing the hypergraph
structure of some inputs that arise in Quantum Circuit Simulation [15].
Cotengra also utilizes the Bayesian optimization strategy, varying the
hyperparameters of the partitioning solver at various levels in order to
account for a changing graph structure as the algorithm progresses [15].

###  III-D cuTENSOR

cuTENSOR is a tensor network CUDA library in development by NVidia, which aims
to bring high performance tensor primatives to the GPU [1]. Because not much
information about their specific method for determining contraction orders is
publicly available at the time of writing, we will not be comparing to
cuTENSOR at this time.

##  IV Constructing a Contraction Tree

Our approach is founded on the observation that a parenthesization of a matrix
chain expression or a contraction order for a tensor network both admit
representations as binary trees with labelled leaves.

It is useful to introduce a more direct tensor variant of the Matrix Chain
Ordering Problem, known as the Tensor Chain Ordering Problem. Given tensors
$X_{1},\ldots,X_{n}$, find an optimal parenthesization of the tensor chain
expression

$\displaystyle X_{1}\ast\cdots\ast X_{n}$

which minimizes one of the costs introduced in Eqs 1,2. Notably, indices are
not restricted to immediate neighbors in the chain.

Given a binary tree $T$ representing a contraction order $O$ for a tensor
network $\mathcal{T}$, consider the linear ordering $\sigma$ of tensors
corresponding to a left to right traversal of the labelled leaves of $T$. Then
$T$ could be considered a possible solution to the Tensor Chain Ordering
Problem for the chain

$\displaystyle\sigma^{-1}(1)\ast\cdots\sigma^{-1}(n).$

Then finding a contraction order for a tensor network can actually be reframed
as finding a linear ordering of the tensors in the network, then solving the
Tensor Chain Order Problem.

$\displaystyle\min_{O}\operatorname{cost}(\mathcal{T},O)$
$\displaystyle=\min_{\sigma}\min_{T}\operatorname{cost}(\mathcal{T},\sigma,T).$

We call solving the Tensor Chain Order Problem for a fixed linear order
$\sigma$ tree structure optimization. Notably, an optimal contraction order of
the Tensor Chain Order Problem can be found deterministically in polynomial
time as demonstrated in the following section. This decouples the actual
computationally Hard task of finding an optimal order of the chain, from the
more tractable task of actually constructing the tree.

###  IV-A Tree Structure Optimization

In this section, we introduce a simple dynamic programming solution to the
Tensor Chain Order Problem. Say we are given the tensor chain expression
$X_{1}\ast\cdots\ast X_{n}$. Let $X_{i,j}=X_{i}\ast X_{i+1}\ast\cdots\ast
X_{j}$ for $i<j$.

From this, we find the following recursion for computing the minimal edge
congestion of any parenthesization of the tensor chain

$\displaystyle\begin{split}c(i,i)&=\operatorname{size}(X_{i})\\\
c(i,j)&=\min_{i\leq
k<j}\max\begin{cases}\log_{2}\operatorname{size}(X_{i,k}\ast X_{k+1,j})\\\
c(i,k)\\\ c(k+1,j)\end{cases}\end{split}$ (5)

as well as the minimal vertex congestion

$\displaystyle\begin{split}c(i,i)&=\operatorname{size}(X_{i})\\\
c(i,j)&=\min_{i\leq
k<j}\max\begin{cases}\log\operatorname{ops}(X_{i,k},X_{k+1,j})\\\ c(i,k)\\\
c(k+1,j)\end{cases}\end{split}$ (6)

It is beneficial to avoid attempting to calculate
$\operatorname{share}(X_{i,k},X_{k+1,j})$ at each iteration. Instead, we
introduce the subroutine Alg. 1 which more efficiently calculates every value
of shared as $k$ is varied across the sequence. If
$d=\max_{X\in\mathcal{T}}\lvert\operatorname{inc}(X)\rvert$ is the maximum
degree of any tensor in $\mathcal{T}$, this can be done in
$O(d\lvert\mathcal{T}\rvert)$ time.

Algorithm 1 CalcShared

0: A tensor chain $C=(X_{1},\ldots,X_{n})$, $1\leq i\leq j\leq n$

$shared\leftarrow[0\mid\text{for }i\leq k<j]$

$(upper,lower)\leftarrow(\\{X_{i},\ldots,X_{k-1}\\},\\{X_{k+1},\ldots,X_{j}\\})$

for $i\leq k<j$ do

$new\leftarrow
sum(\operatorname{size},\\{a\in\operatorname{inc}(X_{i})\mid\operatorname{inc}(a)\cap
upper\neq\emptyset\\})$

$old\leftarrow
sum(\operatorname{size},\\{b\in\operatorname{inc}(X_{i})\mid\operatorname{inc}(b)\cap
lower\neq\emptyset\\})$

$shared[k]\leftarrow shared[k]+new-old$

$shared[k+1]\leftarrow shared[k]$

end for

return $shared$

From these recursions, we introduce Alg. 2, a dynamic programming algorithm
for computing the minimal possible size of the largest tensor for any
contraction tree given an order. We make use of pruning in order to reduce the
number of needed computations, as there is no need to evaluate the second
subsequence in a split if the first has already exceeded the current best
result. Performance can be further improved by making use of memoization to
cache previous calls. Additional gains may be achieved by parallelizing the
evaluation of disjoint subproblem calls, which is an ongoing project.
Utilizing these techniques, the complexity of Alg. 2 is $O(\lvert
E\rvert\lvert V\rvert^{2}+d\lvert V\rvert^{3})$.

Algorithm 2 Tree Structure Optimization

0: A tensor chain $C=(X_{1},\ldots,X_{n})$, $1\leq i\leq j\leq n$

0: $x\oplus y=x+y\text{ or }\max(x,y)$

if $i==j$ then

return $(\operatorname{size}(X_{i}),i)$

end if

$shared\leftarrow CalcShared(C,i,j)$

$outsize\leftarrow\operatorname{size}(X_{i,j})$

$(c^{*},t^{*})\leftarrow\infty,i$

for $i\leq k<j$ do

$c\leftarrow COST(outsize,shared[k])$

if $c>c^{*}$ then

continue

end if

$(c_{l},l)\leftarrow TreeStructureOptimization(C,i,k)$

$c\leftarrow c\oplus c_{l}$

if $c>c^{*}$ then

continue

end if

$(c_{r},r)\leftarrow TreeStructureOptimization(C,k+1,j)$

$c\leftarrow c\oplus c_{r}$

if $c<c^{*}$ then

$(c^{*},t^{*})\leftarrow(c,(l,r))$

end if

end for

return $(c^{*},t^{*})$

A variant for the classical total number of operations can be achieved simply
by looking at the incremental sum of the left and right trees rather than the
max.

$\displaystyle\begin{split}c(i,i)&=\operatorname{size}(X_{i})\\\
c(i,j)&=\min_{i\leq
k<j}\operatorname{ops}(X_{i,k},X_{k+1,j})+c(i,k)+c(k+1,j)\end{split}$ (7)

###  IV-B Heuristic Order Choices

While we have introduced algorithms for constructing an optimal contraction
tree given a particular order, we must now tackle the problem of actually
choosing an order. We turn to a heuristic approach for solving this problem.
In particular, we select an order which minimizes the sum total of lengths of
stretched edges in the graph. This is known as the Minimal Linear Arrangement
of the vertices in the graph, and is defined as

$\displaystyle\sum_{uv\in E}w(uv)\lvert\sigma(u)-\sigma(v)\rvert$

This is motivated by the property of matrix chains sharing indices only with
their immediate neighbors. An order which minimizes MLA discourages long
stretched edges on the chain. We have empirically observed this to be
effective in reducing the congestion of the resulting contraction tree, which
will be discussed further in the Results section.

In order to calculate an order which effectively minimizes MLA, we utilize the
LinearOrdering.jl package, a Julia package for multilevel linear ordering that
is currently in development by the authors. This package utilizes a volume
based coarsening strategy as well as node by node minimization in order to
find a high quality arrangement [32]. The package can be found at
https://github.com/cameton/LinearOrdering.jl.

##  V Experimental Results

We evaluate tree structure optimization against existing state of the art
algorithms Tamaki-2017, FlowCutter, and Cotengra on a collection of randomly
generated QAOA circuits. To generate test results for tree structure
optimization, we find an order for the graph with a good Minimum Linear
Arrangement objective, then run tree structure optimization with the relevant
cost. This is done repeatedly while varying the random seed for a set amount
of time, returning the best result at the end. In most cases we observe a
significant improvement in the quality of results given a comparable running
time (that is usually negligible in comparison to the quantum simulation time
itself).

For our tests, for a fixed depth $p$ and degree $d$, we construct a $p$ layer
QAOA ansatz circuit targeting the Max Cut problem on a random 32 vertex
$d$-regular graph using the QTensor library[23]. Each circuit will have a
number of qubits equal to the number of vertices in the given graph. For each
combination of $d=3,4,5$ and QAOA depth $p=2,3,4,5$, we generate 10 random
circuits to form our test set. The source code and generated circuits are
available at https://github.com/cameton/HPEC2022_ContractionTrees. In doing
so, we sample a variety of circuits with a varying level of connectedness and
depth, which we use as a proxy for the complexity of the circuit; such
circuits are commonly used in evaluations of contraction order solvers for
quantum circuits as in [15].

Figure 2: Vertex Congestion achieved by Tamaki-2017 (left) and FlowCutter
(right) plotted against the vertex congestion found by our tree structure
optimization on a Minimum Linear Arrangement order. The blue line represents
the threshold at which both solvers achieved the same objective value. Points
above this threshold indicate that tree structure optimization found a
superior value.

###  V-A Vertex Congestion

We compare the vertex congestion (Eq. 3) of the solution found by our tree
structure optimizer for the test set against that found by Tamaki-2017 and
FlowCutter by finding the tree decomposition of the line graph. As Cotengra
has functionality to minimize edge congestion and number of FLOPS, it will be
evaluated separately. For these experiments, we ran each of these optimizers
for 5 seconds. Results for this test are given in Fig. 2.

Our tree structure optimization based approach performed strictly better than
Flowcutter on 96.4% of points and better than Tamaki on 90.0% of points, while
never achieving a worse cost. What’s more, the margin of improvement increases
significantly as the vertex congestion of the circuit increases.

As vertex and edge congestion represent the log of the maximum size and
maximum number of operations, even small improvements in congestion lead to
significant gains. As such, having such a large improvement on so many points
represents advantage of our solver over competitive solvers run for the same
amount of time.

###  V-B Edge Congestion and Operation Count

We compare the edge congestion (Eq. 4) and estimated number of operations (Eq.
1) of the solution found by our tree structure optimizer on the test set
against those found by Cotengra. For these tests, Cotengra was run for 5
seconds with default settings and the KaHyPar partitioner backend. Two tests
were run using Cotengra: one minimizing edge congestion and one minimizing the
total number of scalar operations. Results are given in Fig. 3.

Figure 3: Edge congestion of Cotengra minimizing edge congestion against tree
structure optimization (left) and Cotengra minimizing operation count against
tree structure optimization on a log-log scale (right). The blue line
represents the threshold at which both solvers achieved the same objective
value. Points above this threshold indicate that tree structure optimization
found a superior value.

From Fig. 3, we see that tree structure optimization is highly competitive
with Cotengra, in every case finding a solution which is close to or better
than Cotengra in terms of both estimated number of FLOPS and edge congestion.

Our solver bests Cotengra on a full 95% of points when minimizing total number
of operations, and on 84.1% of points when minimizing edge congestion. This
once again demonstrates the superiority of our solver for comparatively short
run times.

###  V-C Varying the Number of Qubits

We may also wish to compare these solvers as we vary the number of vertices in
the input graph, by extension varying the number of qubits. To avoid
redundancy, we restrict our comparison for this section to Cotengra and Total
FLOPS alone. For these tests, we construct a $2$ layer QAOA ansatz circuit
targeting the Max Cut problem for random $3$-regular graphs with $32,64,96$
and $128$ vertices. For each size, we generate 10 random circuits. Because
each circuit has a number of qubits equal to the size of the input graph, we
can examine circuits of a similar complexity across a variety of different
qubit counts. For these tests, we ran both Cotengra and the ordering solver
for 10 seconds for each input.

Figure 4: Cotengra minimizing operation count against tree structure
optimization on a log-log scale for circuits with 32, 64, 96, and 128 qubits.
The blue line represents the threshold at which both solvers achieved the same
objective value. Points above this threshold indicate that tree structure
optimization found a superior value.

The results of this test are shown in Fig. 4. Averaging over the 32 qubit
circuits, our tree structure optimization based approach produced results
around 28.6% better than Cotengra, improving to 74.1% when averaging over the
64 qubit circuits. For the 96 and 128 qubit circuits, nearly every result
produced by our tree structure optimization approach is several orders of
magnitude better than Cotengra for the 10 second running time.

##  VI Future Work

###  VI-A Width Refinement

The current refinement strategy used in this paper minimizes Minimum Linear
Arrangement by making local changes to the order at each level of the
algorithm [33]. While we have shown thus far that Minimum Linear Arrangement
works as a effective heuristic for the tested circuits, we may be able to
achieve further improvements through the development of refinement strategies
which directly target the width of the order. That is, we would like the
ability to make local changes which serve to reduce the width of the overall
order, potentially achieving better results than the more general Minimum
Linear Arrangement heuristic.

###  VI-B Performance & Scalability

The algorithms introduced here for tree structure optimization are currently
not parallelized. The development of a tree structure optimization algorithm
which takes advantage of the graph structure for improved performance is vital
to the application of this technique to fields outside of quantum circuit
simulation, such as in large scale shortest path acceleration[17].

Although the multilevel algorithm component is already fast, it will be
valuable to develop a strongly parallelized version of these algorithms which
may be better suited for a high performance computing environment,
particularly where such hardware is being used for circuit simulation already.

###  VI-C Higher Order Structures

Thus far we have primarily considered tensor networks representable as normal
undirected graphs. In this context, we associate each index in the circuit
with a corresponding edge in the graph. For some quantum circuits, a possible
cost-saving technique is to reconsider certain collections of indices as
hyperindices, in essence a single index connecting multiple gates [24]. This
introduces a hypergraph structure to our tensor network representation, a
higher order generalization of undirected graphs.

As it stands, our work has yet to be extended to accommodate these higher
order structures, something which Cotengra is currently able to handle by
making use of existing hypergraph partitioning software [15]. In particular,
attention needs to be paid to how the hypergraph structure may inform the
coarsening portion of the ordering problem. For example, this can be done by
evaluating various kernels and similarity measures on high order structures
such as in [14, 38, 4, 37]. Moreover, this necessitates a tree structure
optimization algorithm for higher order structures.

##  VII Conclusion

Accelerating quantum circuit simulation is a critical problem not only for
demonstrating quantum advantage but also for hybrid quantum-classical
algorithms which require computationally heavy parameter optimization backend
on the classical machine. In this paper, we presented novel algorithms for
constructing an optimal contraction tree from a given order. We introduced a
multilevel solver for the Minimum Linear Arrangement problem on graphs and
demonstrated its applicability as a heuristic for providing orderings for
contraction trees. We compared the performance of our solver against state-of-
the-art industry solvers Tamaki-2017, FlowCutter, and Cotengra on a collection
of randomly generated QAOA circuits. We have shown that our method achieves
results that are superior by orders of magnitude on some instances to
competitors when run for a comparable amount of time. There is work under way
to produce higher quality orders for producing contraction trees, and on
improving the speed of tree structure optimization.

## Acknowledgements

This material is based upon work supported by the Defense Advanced Research
Projects Agency (DARPA) ONISQ program under Contract No. HR001120C0068. This
research was partially supported by NSF, under award number 2122793. Y.A.’s
and D.L.’s work at Argonne National Laboratory was partially supported by the
U.S. Department of Energy, Office of Science, under contract DE-
AC02-06CH11357.

## References

  * [1] cuTENSOR.  https://docs.nvidia.com/cuda/cutensor/index.html, 2022.
  * [2] Amine Abou-Rjeili and George Karypis.  Multilevel algorithms for partitioning power-law graphs.  In Parallel and Distributed Processing Symposium, 2006. IPDPS 2006\. 20th International, pages 10–pp. IEEE, 2006.
  * [3] Yuri Alexeev, Dave Bacon, Kenneth R Brown, Robert Calderbank, Lincoln D Carr, Frederic T Chong, Brian DeMarco, Dirk Englund, Edward Farhi, Bill Fefferman, et al.  Quantum computer systems for scientific discovery.  PRX Quantum, 2(1):017001, 2021.
  * [4] Lu Bai, Edwin R Hancock, and Peng Ren.  A jensen-shannon kernel for hypergraphs.  In Joint IAPR International Workshops on Statistical Techniques in Pattern Recognition (SPR) and Structural and Syntactic Pattern Recognition (SSPR), pages 181–189. Springer, 2012.
  * [5] Jacob Biamonte and Ville Bergholm.  Tensor networks in a nutshell.  arXiv preprint arXiv:1708.00006, 2017.
  * [6] A. Brandt and D. Ron.  Chapter 1 : Multigrid solvers and multilevel optimization strategies.  In J. Cong and J. R. Shinnerl, editors, Multilevel Optimization and VLSICAD. Kluwer, 2003.
  * [7] Cédric Chevalier and Ilya Safro.  Comparison of coarsening schemes for multilevel graph partitioning.  Learning and Intelligent Optimization, pages 191–205, 2009.
  * [8] Andrzej Cichocki, Namgil Lee, Ivan Oseledets, Anh-Huy Phan, Qibin Zhao, and Danilo P. Mandic.  Tensor networks for dimensionality reduction and large-scale optimization: Part 1 low-rank tensor decompositions.  Foundations and Trends® in Machine Learning, 9(4-5):249–429, 2016.
  * [9] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein.  Introduction To Algorithms.  MIT Press, 2009.
  * [10] Holger Dell, Christian Komusiewicz, Nimrod Talmon, and Mathias Weller.  The PACE 2017 Parameterized Algorithms and Computational Experiments Challenge: The Second Iteration.  In Daniel Lokshtanov and Naomi Nishimura, editors, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017), volume 89 of Leibniz International Proceedings in Informatics (LIPIcs), pages 30:1–30:12, Dagstuhl, Germany, 2018. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * [11] Jeffrey M Dudek, Leonardo Duenas-Osorio, and Moshe Y Vardi.  Efficient contraction of large tensor networks for weighted model counting through graph decompositions.  arXiv preprint arXiv:1908.04381, 2019.
  * [12] Stavros Efthymiou, Jack Hidary, and Stefan Leichenauer.  Tensornetwork for machine learning.  arXiv preprint arXiv:1906.06329, 2019.
  * [13] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann.  A quantum approximate optimization algorithm.  arXiv preprint arXiv:1411.4028, 2014.
  * [14] Agata Fronczak, Janusz A Hołyst, Maciej Jedynak, and Julian Sienkiewicz.  Higher order clustering coefficients in barabási–albert networks.  Physica A: Statistical Mechanics and its Applications, 316(1-4):688–694, 2002.
  * [15] Johnnie Gray and Stefanos Kourtis.  Hyper-optimized tensor network contraction.  Quantum, 5:410, mar 2021.
  * [16] Johnny Gray.  Cotengra, 2020.
  * [17] Michael Hamann and Ben Strasser.  Graph bisection with pareto optimization.  ACM J. Exp. Algorithmics, 23, feb 2018.
  * [18] Y. F. Hu and J. A. Scott.  A multilevel algorithm for wavefront reduction.  SIAM J. Sci. Comput., 23(4):1352–1375, 2001.
  * [19] Isa Inuwa-Dutse, Mark Liptrott, and Ioannis Korkontzelos.  A multilevel clustering technique for community detection.  Neurocomputing, 441:64–78, 2021.
  * [20] Stefanos Kourtis, Claudio Chamon, Eduardo Mucciolo, and Andrei Ruckenstein.  Fast counting with tensor networks.  SciPost Physics, 7(5), nov 2019.
  * [21] H. Lee, J. Kim, S.J. Hong, and S. Lee.  Processor allocation and task scheduling of matrix chain products on parallel systems.  IEEE Transactions on Parallel and Distributed Systems, 14(4):394–407, 2003.
  * [22] Xiaoyuan Liu, Anthony Angone, Ruslan Shaydulin, Ilya Safro, Yuri Alexeev, and Lukasz Cincio.  Layer VQE: A variational approach for combinatorial optimization on noisy quantum computers.  IEEE Transactions on Quantum Engineering, 3:1–20, 2022.
  * [23] Danylo Lykov.  QTensor.  https://github.com/danlkv/qtensor, 2021.
  * [24] Danylo Lykov and Yuri Alexeev.  Importance of diagonal gates in tensor network simulations.  In 2021 IEEE Computer Society Annual Symposium on VLSI (ISVLSI), pages 447–452. IEEE, 2021.
  * [25] Danylo Lykov, Angela Chen, Huaxuan Chen, Kristopher Keipert, Zheng Zhang, Tom Gibbs, and Yuri Alexeev.  Performance evaluation and acceleration of the qtensor quantum circuit simulator on gpus.  In 2021 IEEE/ACM Second International Workshop on Quantum Computing Software (QCS), pages 27–34. IEEE, 2021.
  * [26] Danylo Lykov, Roman Schutski, Alexey Galda, Valerii Vinokur, and Yurii Alexeev.  Tensor network quantum simulator with step-dependent parallelization.  arXiv preprint arXiv:2012.02430, 2020.
  * [27] Igor L Markov and Yaoyun Shi.  Simulating quantum computation by contracting tensor networks.  SIAM Journal on Computing, 38(3):963–981, 2008.
  * [28] Simone Montangero, Montangero, and Evenson.  Introduction to Tensor Network Methods.  Springer, 2018.
  * [29] Bryan O’Gorman.  Parameterization of tensor network contraction.  arXiv preprint arXiv:1906.00013, 2019.
  * [30] Elina Robeva and Anna Seigal.  Duality of graphical models and tensor networks.  Information and Inference: A Journal of the IMA, 8(2):273–288, 2019\.
  * [31] Dorit Ron, Ilya Safro, and Achi Brandt.  Relaxation-based coarsening and multiscale graph organization.  Multiscale Modeling & Simulation, 9(1):407–423, 2011.
  * [32] Ilya Safro, Dorit Ron, and Achi Brandt.  Graph minimum linear arrangement by multilevel weighted edge contractions.  Journal of Algorithms, 60(1):24–41, 2006.
  * [33] Ilya Safro, Dorit Ron, and Achi Brandt.  Multilevel algorithms for linear ordering problems.  ACM J. Exp. Algorithmics, 13, feb 2009.
  * [34] Ilya Safro, Peter Sanders, and Christian Schulz.  Advanced coarsening schemes for graph partitioning.  ACM Journal of Experimental Algorithmics (JEA), 19:2–2, 2015.
  * [35] Ilya Safro and Boris Temkin.  Multiscale approach for the network compression-friendly ordering.  J. Discrete Algorithms, 9(2):190–202, 2011.
  * [36] Sebastian Schlag, Tobias Heuer, Lars Gottesbüren, Yaroslav Akhremtsev, Christian Schulz, and Peter Sanders.  High-quality hypergraph partitioning.  arXiv preprint arXiv:2106.08696, 2021.
  * [37] Ruslan Shaydulin, Jie Chen, and Ilya Safro.  Relaxation-based coarsening for multilevel hypergraph partitioning.  SIAM Multiscale Modeling & Simulation, 17(1):482–506, 2019.
  * [38] Ruslan Shaydulin and Ilya Safro.  Aggregative Coarsening for Multilevel Hypergraph Partitioning.  In Gianlorenzo D’Angelo, editor, 17th International Symposium on Experimental Algorithms (SEA 2018), volume 103 of Leibniz International Proceedings in Informatics (LIPIcs), pages 2:1–2:15, Dagstuhl, Germany, 2018\. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * [39] Ben Strasser.  Computing tree decompositions with flowcutter: Pace 2017 submission.  arXiv preprint arXiv:1709.08949, 2017.
  * [40] Hisao Tamaki.  Positive-instance driven dynamic programming for treewidth.  Journal of Combinatorial Optimization, 37(4):1283–1311, 2019.
  * [41] Hayato Ushijima-Mwesigwa, Ruslan Shaydulin, Christian F. A. Negre, Susan M. Mniszewski, Yuri Alexeev, and Ilya Safro.  Multilevel combinatorial optimization across quantum architectures.  ACM Transactions on Quantum Computing, 2(1), February 2021.
  * [42] C. Walshaw.  Multilevel refinement for combinatorial optimisation problems.  Annals Oper. Res., 131:325–372, 2004.
  * [43] John Watrous.  Guest column: An introduction to quantum information and quantum circuits 1.  SIGACT News, 42(2):52–67, jun 2011.
  * [44] Noson S Yanofsky.  An introduction to quantum computing.  In Proof, computation and agency, pages 145–180. Springer, 2011\.