$\displaystyle\frac{1}{1-\gamma}\sum_{s}\left[d_{\rho}^{\pi_{\theta}}(s)\cdot\lambda\cdot
D_{\mathrm{KL}}\left(\pi_{\theta}(\cdot\mid s)\|\pi_{\theta^{*}}(\cdot\mid
s)\right)\right]$ $\displaystyle\geq$
$\displaystyle\frac{1}{1-\gamma}\sum_{s}\left[d_{\rho}^{\pi_{\theta}}(s)\cdot\lambda\cdot\frac{1}{2\ln
2}\|\pi_{\theta}(\cdot\mid s)-\pi_{\theta^{*}}(\cdot\mid s)\|_{1}^{2}\right]$
$\displaystyle\geq$ $\displaystyle\frac{\lambda}{2\ln
2}\sum_{s}\left[{\rho}(s)\cdot\|\pi_{\theta}(\cdot\mid
s)-\pi_{\theta^{*}}(\cdot\mid s)\|_{1}^{2}\right]$ $\displaystyle\geq$
$\displaystyle\frac{\lambda}{2\ln
2}\sum_{s}\left[{\rho}(s)\cdot\|\pi_{\theta}(\cdot\mid
s)-\pi_{\theta^{*}}(\cdot\mid s)\|_{2}^{2}\right]$ $\displaystyle\geq$
$\displaystyle\frac{\lambda}{2\ln 2}\left[\rho(s)\|\pi_{\theta}(\cdot\mid
s)-\pi_{\theta^{*}}(\cdot\mid s)\|_{2}^{2}\right]\quad\forall s\in\mathcal{S}$
$\displaystyle\geq$ $\displaystyle\frac{\lambda\min_{s}\rho(s)}{2\ln
2}\left|\pi_{\theta}({a}\mid{s})-\pi_{\theta^{*}}({a}\mid{s})\right|^{2},\quad\forall
s\in\mathcal{S},a\in\mathcal{A},$

where the first inequality is due to Theorem 11.6 in [12] stating that

$D_{\text{KL}}\left[P(\cdot)\mid Q(\cdot)\right]\geq\frac{1}{2\ln
2}\|P(\cdot)-Q(\cdot)\|_{1}^{2}$

for every two discrete distributions $P(\cdot)$ and $Q(\cdot)$. Moreover, the
second inequality is due to $d_{\rho}^{\pi_{\theta}}(s)\geq(1-\gamma)\rho(s)$
and the third inequality is due to the equivalence between $\ell_{1}$-norm and
$\ell_{2}$-norm. This completes the proof.

######  Lemma 11.3.

$\min_{s,a}\pi_{\lambda}^{*}(a|s)\geq\exp(\frac{-\bar{r}}{(1-\gamma)\lambda})$.

######  Proof 11.4.

According to Theorem 1 in [30], we have $\log\pi_{\lambda}^{*}(a\mid
s)=\frac{1}{\lambda}\left({Q}^{\pi_{\lambda}^{*}}(s,a)-{V}^{\pi_{\lambda}^{*}}(s)\right)\geq\frac{-\bar{r}}{(1-\gamma)\lambda},\
\forall(s,a)\in\mathcal{S}\times\mathcal{A}.$ Thus,
$\min_{s,a}\pi_{\lambda}^{*}(a|s)\geq\exp(\frac{-\bar{r}}{(1-\gamma)\lambda})$
as claimed.


# Detecting Lexical Borrowings from Dominant Languages
in Multilingual Wordlists

John E. Miller
Artificial Intelligence/Engr.
Pontificia Universidad Católica del Perú
San Miguel, Lima, Peru
<EMAIL_ADDRESS>
&Johann-Mattis List
Chair of Multil. Comput. Linguistics / DLCE
University of Passau / MPI-EVA
Passau / Leipzig, Germany
<EMAIL_ADDRESS>

###### Abstract

Language contact is a pervasive phenomenon reflected in the borrowing of words
from donor to recipient languages. Most computational approaches to borrowing
detection treat all languages under study as equally important, even though
dominant languages have a stronger impact on heritage languages than vice
versa. We test new methods for lexical borrowing detection in contact
situations where dominant languages play an important role, applying two
classical sequence comparison methods and one machine learning method to a
sample of seven Latin American languages which have all borrowed extensively
from Spanish. All methods perform well, with the supervised machine learning
system outperforming the classical systems. A review of detection errors shows
that borrowing detection could be substantially improved by taking into
account donor words with divergent meanings from recipient words.

##  1 Introduction

Language contact is one of the most pervasive linguistic phenomena. It is the
first factor that needs to be excluded when searching for genetic relations
among the languages of the world, and it needs to be controlled for when
searching for cross-linguistic universals. Any study trying to explain how
humans use language must take language contact into account. It is also a
unique witness of ancient contacts in human prehistory.

Language contact is most prominently reflected in _lexical borrowing_ , the
_transfer_ of words from a donor language to a recipient language. Although
research on the computational handling of lexical borrowing has made some
progress of late, computational approaches to the investigation of language
contact are still in their infancy (List, 2019). Specifically methods that
could infer the direction of borrowings have not been proposed so far. While
numerous case studies investigate the influence of dominant languages on
heritage languages (Prochazka and Vogl, 2017; Meisel, 2018), we lack automated
methods that could be used to study the influence of particular dominant
languages in linguistically diverse areas of the world.

The number of standardized cross-linguistic wordlist collections has greatly
increased over the past years (Rzymski et al., 2020; List et al., 2022a), with
standard formats (Forkel et al., 2018) accompanied by software tools that
allow scholars to prepare and curate standardized wordlists in an efficient
manner (Forkel and List, 2020). It would be useful to have a computer assisted
tool for linguists to detect which words in a cross-linguistic region have
been borrowed from a dominant language and with further advances, a tool for
inclusion in language contact assessment or in computational cladistics
workflows.

Here, we compare the suitability of three different systems to address this
task – two systems based on classical algorithms for automated sequence
comparison that can be applied in supervised and unsupervised settings, and
one supervised system based on extended machine learning techniques. We test
these systems on a newly derived dataset of seven Latin American languages
(Fig. 1) in which Spanish is a dominant donor language. Our results show that
the supervised machine-learning system outperforms the classical systems.

##  2 Previous Work

Although still few in number, automatic methods for borrowing detection have
been increasingly applied and developed in the past years. Early studies by
van der Ark et al. (2007) and later Mennecier et al. (2016) compute edit
distances between words from genetically unrelated languages and compare
distances to thresholds, in order to detect borrowed words in multilingual
wordlists.

Besides edit distance, which directly calculates distances between phonetic
sequences, sound class based methods cluster phonetic segments into sound
classes and then compute distances between sound class sequences. The sound-
class based alignment method (SCA) (List, 2012) provides sound class
categories, scoring functions for distance measures, and modifiable gap scores
based on prosodic context.

Zhang et al. (2021) compare edit distance performance against SCA (List, 2012)
distance performance, finding that SCA outperforms edit distance in accuracy.
Hantgan et al. (2022) build on this work, using dedicated methods for
automated cognate detection applied to languages from different language
families in order to identify clusters of related words resulting from lexical
borrowing. List and Forkel (2022a) expand this work further, by applying a
two-stage workflow in which they first identify language-family-internal
cognates, using a method specifically apt for the detection of deep cognates,
and then compute SCA distances between cognate sets from genetically unrelated
languages in order to infer sets of words related by lexical transfer.

Miller et al. (2020) compute language models for inherited and borrowed words
for individual languages from the World Loanword Database (WOLD, Haspelmath
and Tadmor 2009) using Markov Chains and Recursive Neural Networks and compare
cross-entropies for inherited and borrowed language models in order to
identify borrowings from monolingual information alone.

Kaiping and Klamer (2022) use automated methods for cognate detection (List et
al., 2017) on a target set of Timor-Alor-Pantar languages. In order to infer
borrowings from Indonesian and Tetun (not in the target set), they include
both languages in their sample and treat all cognate sets that involves words
from either of the two languages as borrowings. Moro et al. (2023) apply a
similar approach to investigate borrowings in Alorese.

Mi et al. (2020) and Nath et al. (2022) train binary classifiers, mainly
neural based, on large wordlists to predict borrowed words, and achieve F1
scores in the 0.75 to 0.85 range. Their workflows seem cumbersome, compute
intensive, and not minimalist, but the results are promising.

##  3 Materials and Methods

###  3.1 Materials

For this study, a new comparative wordlist was created by taking data for
seven Latin American languages from WOLD (https://wold.clld.org, Haspelmath
and Tadmor 2009) and combining them with a wordlist of Spanish derived from
the Intercontinental Dictionary Series (https://ids.clld.org, Key and Comrie
2015). Phonetic transcriptions for the Latin American languages were added to
WOLD by Miller et al. (2020). Latin American Spanish phonetic transcriptions
were added for this study (and could be later expanded by adding more
transcriptions from historical varieties of Spanish). The resulting dataset
conforms to the standards suggested by the Cross-Linguistic Data Formats
initiative (CLDF, https://cldf.clld.org, Forkel et al. 2018). The data
curation follows the Lexibank workflow (List et al., 2022a) and checks that
data conform to certain standards, with languages being linked to Glottolog
(https://glottolog.org, Hammarström et al. 2022, Version 4.7), concepts being
linked to Concepticon (https://concepticon.clld.org, List et al. 2022b,
Version 3.0), and transcriptions following the B(road)IPA conventions of the
Cross-Linguistic Transcription Systems reference catalog
(https://clts.clld.org, List et al. 2021, Version 2.2, see Anderson et al.
2018). Details of the resulting database are shown in the map of language
locations along with percentages for borrowings from Spanish in Fig. 1 and in
Tab. 1. Q’eqchi’ and Zincantán Tzotzil are both Mayan languages, but appear
substantially varied in the database.

Figure 1: Map of languages with Spanish borrowing class.

Language | Concepts | Lexemes | Segments | Vocab.
---|---|---|---|---
Imb. Quechua | 1,155 | 1,156 | 7,177 | 33
Mapudungun | 1,040 | 1,242 | 7,356 | 33
Otomi | 1,252 | 2,241 | 11,730 | 57
Q’eqchi’ | 1,211 | 1,773 | 10,367 | 49
Wichí | 1,128 | 1,219 | 8,233 | 44
Yaqui | 1,242 | 1,433 | 9,297 | 28
Zin. Tzotzil | 955 | 1,266 | 7,129 | 41
Spanish | 1,308 | 1,770 | 11,261 | 30
Aggregate | 1,308 | 12,100 | 72,550 | 112

Table 1: Database details for seven Latin American languages plus Latin
American Spanish.

###  3.2 Methods

#### Methods for Borrowing Detection.

We develop three different methods for the detection of borrowings _from_ a
dominant language _to_ non-dominant languages in multilingual wordlists.
Following historical linguistics comparative method practice (Campbell, 2013),
only word forms corresponding to the same concept are considered as candidates
for borrowing.

The first method, called _Closest Match_ borrowing detection in the following,
iterates over all word pairs that express the same concept in the dominant
language and the heritage languages and then computes phonetic distances. Word
pairs whose phonetic distance is below a certain threshold are judged to be
borrowings from the dominant language. We test two phonetic distances, the
normalized edit distance (NED) – the classical edit distance (Levenshtein,
1965) between two words, divided by the length of the longer word – and the
SCA distance (List, 2012).

The second method, called _Cognate-Based_ borrowing detection in the
following, follows the approach by Hantgan et al. (2022): it first computes
cognates using a cluster-based approach for automated cognate detection in
which words expressing the same concept whose average phonetic distance is
below a certain threshold are assigned to the same cognate set (List et al.,
2017), and then identifies all words assigned to cognate sets involving the
dominant language as borrowings. We tested again normalized edit and SCA
distances.

The third method, called _Classifier-Based_ borrowing detection in the
following, iterates over all word pairs with the same concept, but stores
phonetic distance scores for various distance measures as vectors, which can
then be used to train a classifier, firstly, a linear Support Vector Machine
(SVM) (Cristianini and Shawe-Taylor, 2000), in a supervised setting. We tested
various phonetic distance measures, but report only on the combination of
normalized edit and SCA distances, as they yielded the best results. Both
Closest Match and Cognate-Based methods require a fixed threshold which we
estimate from the training data. So all three methods are considered as
supervised.

#### Sampling.

Train-test splits are made based on concepts rather than individual word
entries. This permits matching of words for the same concept in in all methods
without loss of candidate words. Treating train-test split as a nuisance
variable takes into account differences between partitions across methods thus
controlling for effects of sampling by concepts with differing borrowing
behavior or statistical dependencies between test partitions due to sampling
without replacement. See (Dror et al., 2018) for mention of the dependency
problem with cross-validation. Our use of a fixed partition across treatments
and analysis of variance controlling for partition as a nuisance or ‘blocking’
variable accounts for this dependency, and takes advantage of any systematic
effects in borrowing behavior by partition.

#### Evaluation.

For the analysis of the cross-validation data, we use a randomized blocks
design where experiment is the treatment or factor, and test partition is the
randomized block or nuisance variable. A standard analysis of variance
partitions treatment effects, nuisance variable, and error, and permits a more
powerful test of treatment differences without the nuisance variable variance.
We follow up statistically significant findings for treatment (experiment),
with comparisons of experiments versus the overall average using a joint
(family) error rate.

#### Implementation.

Our methods are implemented in Python, making specifically use of the
CLDFBench package (https://pypi.org/project/cldfbench/, Forkel and List 2020,
Version 1.13.0) to provide commandline access to all methods described here.
For the computation of alignments and edit distances, LingPy
(https://pypi.org/project/lingpy, List and Forkel 2022b, Version 2.6.9) is
used. SVM and evaluation are realized with the help of Scikit-Learn
(https://pypi.org/project/scikit-learn/, Pedregosa et al. 2011, Version
1.2.1).

##  4 Results and Discussion

We tested our three methods with two distance measures in five experiments
(normalized edit and SCA distances individually in both Closest Match and
Cognate-Based methods, and combined in the Classifier-Based method) using a
10-fold cross-validation on our data and reporting precision, recall, F1
scores, accuracy, and execution times (mm:ss). F1 score is the primary result
measure; accuracy and execution time are informational. The 10-fold cross-
validation uses the same 10 fixed train and non-overlapping test splits for
all experiments. With few parameter estimates (1 threshold each for Closest
Match and Cognate-Based, 2 distance and 7 target language coefficients for
Classifier), a separate train split into fit/val is not necessary.

All methods perform well with less than 5 points separating the highest from
the lowest F1 scores. Tab. 2 shows the results of the ten-fold cross
validation of our three methods in five experiments. An analysis of
variance,111Statistical analyses with JMP (SAS Institute Inc., 2021). with
experiment as the effects variable and train-test split as the nuisance
variable, shows highly significant effects for precision
($\textrm{F}_{4,36}=25.74,p<0.0001$) and F1 score
($\textrm{F}_{4,36}=14.3,p<0.0001$).

Closest Match with normalized edit distance performs poorly, while Classifier-
Based with combined normalized edit and SCA distances performs well.
Classifier-Based performs better than the average of all experiments in F1
score, and substantially better in precision versus other experiments; the
method is conservative, with a low number of false positives. Performance on
remaining experiments is indistinguishable from the overall average of all
experiments combined. The Cognate-Based method is compute intensive performing
multiple alignment over all languages. Accuracy is well above the majority
decision accuracy of 84.8% ($100\%-15.2\%\textrm{ borrowing}$) in all
experiments.

Method | Prec. | Rec. | F1 | Acc. | mm:ss
---|---|---|---|---|---
Closest Match |  |  |  |
NED | 0.832 | 0.703 | 0.761 | 0.938 | 00:15
SCA | 0.869 | 0.720 | 0.787 | 0.945 | 00:29
Cognate-Based |  |  |  |
NED | 0.853 | 0.705 | 0.771 | 0.941 | 01:48
SCA | 0.862 | 0.719 | 0.783 | 0.944 | 04:49
Classifier-Based SVM (linear) |  |
NED, SCA | 0.931 | 0.713 | 0.806 | 0.952 | 00:37
Table 2: Ten-fold cross-validation for three methods with NED (normalized
edit) and SCA (Sound-Class based phonetic alignment) distance measures. Bolded
estimates are superior to and underlined estimates inferior to the the overall
average using analysis of means (Nelson et al., 2005) with joint error rate
$\alpha=0.05$.

A search for classifier improvements prompted several ad hoc experiments (see
tab. 3). We observe: (1) A radial basis function (rbf) SVM classifier performs
no better than our linear SVM. We suspect the estimated target language
parameters do not generalize well to held-out data. (2) A logistic regression
classifier performs on par with our linear SVM. (3) A weight balanced SVM
classifier trades an increase in recall for a larger drop in precision. We
also test whether using separate trials for each target language in Closest
Match, would perform as well as all languages together. A combined trial
performs better; a single threshold estimate appears to generalize better to
held-out data than using individual language estimates.

Experiment | Prec. | Rec. | F1 | Acc.
---|---|---|---|---
Classifier Variations - NED, SCA
SVM (rbf) | 0.945 | 0.694 | 0.799 | 0.951
Logistic regression | 0.914 | 0.728 | 0.809 | 0.952
SVM (balanced) | 0.613 | 0.826 | 0.704 | 0.902
Closest Match - SCA
Each language (avg) | 0.860 | 0.707 | 0.770 | 0.941
Table 3: Ten-fold cross-validation for several ad hoc experiments with NED
(normalized edit) and SCA (Sound-Class based phonetic alignment) distance
measures. Classifier experiments: SVM with radial basis function, Logistic
regression, linear SVM with balanced class weights. Descriptive statistics
only.

Tab. 4 shows the results of the Classifier-Based method for the seven target
languages in our sample with training and evaluation over the entire dataset.
There is some variation in performance by language, in particular, with recall
in $[0.615,0.778]$. We detect a linear relation between the performance and
the amount of borrowings from the dominant language in the target languages.
(Precision: $\textrm{r}=-0.39,\textrm{NS}$; Recall: $\textrm{r}=0.88,p<0.01$;
F1 score: $\textrm{r}=0.85,p<.01$; 1-sided Pearson correlation tests with
$df=5$). Recall and F1 scores improve as borrowing increases. This could be an
artifact of higher borrowing resulting in better estimation of a target
language coefficient, or more interestingly, a cultural process where more
dominant-donor borrowing corresponds to reduced phonetic adaption into the
target language.

Language | Prec. | Rec. | F1 | Acc. | Borr.
---|---|---|---|---|---
Imb. Quechua | 0.921 | 0.773 | 0.841 | 0.924 | 26%
Mapudungun | 0.944 | 0.716 | 0.814 | 0.950 | 15%
Otomi | 0.932 | 0.692 | 0.794 | 0.968 | 9%
Q’eqchi’ | 0.934 | 0.615 | 0.742 | 0.961 | 9%
Wichí | 0.952 | 0.658 | 0.778 | 0.953 | 12%
Yaqui | 0.938 | 0.778 | 0.851 | 0.941 | 22%
Zin. Tzotzil | 0.932 | 0.661 | 0.773 | 0.949 | 13%
Average | 0.934 | 0.714 | 0.810 | 0.952 | 15%

Table 4: Individual language results for the Classifier-Based borrowing
detection methods on the seven target languages in our sample. The last column
shows the proportion of Spanish borrowings. Figure 2: Example collection of
detection errors.

To get a better understanding about the different types of errors that our
best performing experimental combination commits, we conducted a detailed
error analysis from the Classifier-Based borrowing detection results. A
spreadsheet snippet (Fig. 2), serves as a reference for several error types.
For undetected borrowings (false negatives), we identified four error types:
(1) cases where the borrowed form was not present in the donor wordlist, e.g.,
Mapudungun peso “coin” is borrowed from Spanish peso “peso”, but our Spanish
wordlist only has moneda, (2) cases where the form was present in the donor
wordlist, but with a different concept, e.g., Wichi anio “age” is borrowed
from Spanish año “year”, while the Spanish word for “age” is edad, (3) cases
of large phonetic distance between donor and recipient forms, e.g., Wichi
alulis “adobe”, which is somewhat distant from Spanish adobe, and (4) cases of
unrecognized partial borrowing, e.g., Qeqchi aiunink-riS “abstain from food”,
which is partially borrowed from Spanish ajunar “fast”. For falsely detected
borrowings (false positives), we identified three error types: (1) cases where
the form was not borrowed from the dominant language but _vice versa_ , e.g.,
Spanish poroto “bean” was borrowed _from_ Quechua purutu, (2) cases of chance
similarities between word forms, e.g., Spanish animal “animal” and Zinacantan
Tzotzil tSanulil, and (3) cases so improbably similar that we suspect errors
in the original annotation, e.g., Spanish pelota “ball” and Wichi pelutaj.

For a large sample of concepts, we tallied 139 undetected (false negative) and
26 falsely detected (false positive) borrowings (see Tab. 5). Most errors were
in recall, with many of these borrowings from lexemes not within the same
concept.

Undetected Borrowings |
---|---
Error Type | Count | Pct
borrowed form not in donor list | 28 | 17
different concept than recipient form | 75 | 45
large phonetic distance | 31 | 19
partial borrowing as only reason | 5 | 3
Subtotal | 139 | 84
Falsely Detected as Borrowings |
Error Type | Count | Pct
direction not from dominant donor | 7 | 4
chance similarity of form | 10 | 6
likely dataset error | 9 | 5
Subtotal | 26 | 16
Total | 165 | 100
Table 5: Summary over sample of undetected (false negative) and falsely
detected (false positive) borrowings.

##  5 Conclusion

How well can we automatically detect borrowings from dominant languages based
on wordlist data? We devised three general methods to detect borrowed words
from dominant languages, two based on sequence comparison workflows and one
based on a classifier. The classifier-based method showed the best
performance, with F1 scores of 0.81, and high precision of 0.93. This method
could already prove very useful in computer-assisted workflows. Our
investigation of detection errors shows several opportunities for improvement.
Most undetected borrowings result from current methods’ restriction to
searching only for word forms for the same concept. We see great potential in
improvements that account for borrowing accompanied by _semantic shift_ ,
specifically: (1) augment donor wordlist coverage of possible forms, (2) relax
“same” to “similar” concept restriction for matching forms, or (3) fit
language models to wordlists and add word cross-entropy to the classifier
without restriction. Tests adding word cross-entropy, not reported here, look
very promising, but more research is needed.

## Limitations

In this study, we apply limited methods for detection of lexical borrowing to
the case of a single dominant donor language (Spanish) wordlist versus seven
Latin American language wordlists. This application uses relatively sparse
data, with an average of 1,512 lexemes per language wordlist, with very few
estimated parameters, and so apt for lower resource languages. Future work
will seek to remove the wordlist limitation.

## Ethics Statement

Our data are taken from publicly available sources. There are no ethical
issues or conflicts of interest in this work.

## Supplementary Material

The supplementary material accompanying this study contains the data and code
needed to replicate the results reported here, along with detailed information
on installing and using the software. It is curated on GitHub
(https://github.com/lexibank/sabor, Version 1.0) and has been archived with
Zenodo (https://doi.org/10.5281/zenodo.7591335).

## Acknowledgements

This research was supported by the Max Planck Society Research Grant CALC³
(JML, https://digling.org/calc/), the ERC Consolidator Grant ProduSemy (JML,
Grant No. 101044282, see https://cordis.europa.eu/project/id/101044282), and
by the Graduate School of the Pontificia Universidad Católica del Perú (PUCP)
through the Huiracocha-2019 scholarship program, see
https://posgrado.pucp.edu.pe (JEM). Views and opinions expressed are however
those of the author(s) only and do not necessarily reflect those of the
European Union or the European Research Council Executive Agency (nor any
other funding agencies involved). Neither the European Union nor the granting
authority can be held responsible for them. We thank the anonymous reviewers
for helpful comments and all people who share their data openly, so we can use
it in our research.

## References

  * Anderson et al. (2018) Cormac Anderson, Tiago Tresoldi, Thiago Costa Chacon, Anne-Maria Fehn, Mary Walworth, Robert Forkel, and Johann-Mattis List. 2018.  A Cross-Linguistic Database of Phonetic Transcription Systems.  _Yearbook of the Poznań Linguistic Meeting_ , 4(1):21–53.
  * Campbell (2013) L. Campbell. 2013.  _Historical Linguistics: An Introduction_.  Edinburgh University Press.
  * Cristianini and Shawe-Taylor (2000) Nello Cristianini and John Shawe-Taylor. 2000.  _An Introduction to Support Vector Machines and Other Kernel-based Learning Methods_.  Cambridge University Press.
  * Dror et al. (2018) Rotem Dror, Gili Baumer, Segev Shlomov, and Roi Reichart. 2018.  The hitchhiker’s guide to testing statistical significance in natural language processing.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1383–1392, Melbourne, Australia. Association for Computational Linguistics.
  * Forkel and List (2020) Robert Forkel and Johann-Mattis List. 2020.  Cldfbench. give your cross-linguistic data a lift.  In _Proceedings of the Twelfth International Conference on Language Resources and Evaluation_ , pages 6997–7004, Luxembourg. European Language Resources Association (ELRA).
  * Forkel et al. (2018) Robert Forkel, Johann-Mattis List, Simon J. Greenhill, Christoph Rzymski, Sebastian Bank, Michael Cysouw, Harald Hammarström, Martin Haspelmath, Gereon A. Kaiping, and Russell D. Gray. 2018.  Cross-Linguistic Data Formats, advancing data sharing and re-use in comparative linguistics.  _Scientific Data_ , 5(180205):1–10.
  * Hammarström et al. (2022) Harald Hammarström, Martin Haspelmath, Robert Forkel, and Sebastiaon Bank. 2022\.  _Glottolog [Dataset, Version 4.6]_.  Max Planck Institute for Evolutionary Anthropology, Leipzig.
  * Hantgan et al. (2022) A Hantgan, H Babiker, and J List. 2022.  First steps towards the detection of contact layers in bangime: a multi-disciplinary, computer-assisted approach [version 2; peer review: 2 approved].  _Open Res Europe_ , 2:10:1–25.
  * Haspelmath and Tadmor (2009) Martin Haspelmath and Uri Tadmor. 2009.  _World Loanword Database_.  Max Planck Institue for Evolutionary Anthropology, Leipzig.
  * Kaiping and Klamer (2022) Gereon A. Kaiping and Marian Klamer. 2022.  The dialect chain of the Timor-Alor-Pantar language family.  _Language Dynamics and Change_ , 2:1–53.
  * Key and Comrie (2015) Mary Ritchie Key and Bernard Comrie, editors. 2015.  _Intercontinental Dictionary Series (IDS)_.  Max Planck Institute for Evolutionary Anthropology, Leipzig.
  * Levenshtein (1965) V. I. Levenshtein. 1965.  Dvoičnye kody s ispravleniem vypadenij, vstavok i zameščenij simvolov [binary codes with correction of deletions, insertions and replacements].  _Doklady Akademij Nauk SSSR_ , 163(4):845–848.
  * List (2012) Johann-Mattis List. 2012.  Multiple sequence alignment in historical linguistics.  In _Proceedings of ConSOLE XIX_ , pages 241–260.
  * List (2019) Johann-Mattis List. 2019.  Automated methods for the investigation of language contact situations, with a focus on lexical borrowing.  _Language and Linguistics Compass_ , 13(e12355):1–16.
  * List et al. (2021) Johann-Mattis List, Cormac Anderson, Tiago Tresoldi, and Robert Forkel. 2021.  _Cross-Linguistic Transcription Systems [Dataset, Version 2.1.0]_.  Max Planck Institute for the Science of Human History, Jena.
  * List and Forkel (2022a) Johann-Mattis List and Robert Forkel. 2022a.  Automated identification of borrowings in multilingual wordlists [version 3; peer review: 4 approved].  _Open Research Europe_ , 1(79):1–11.
  * List and Forkel (2022b) Johann-Mattis List and Robert Forkel. 2022b.  _LingPy. A Python library for quantitative tasks in historical linguistics [Software Library, Version 2.6.9]_.  Max Planck Institute for Evolutionary Anthropology, Leipzig.
  * List et al. (2022a) Johann-Mattis List, Robert Forkel, Simon J. Greenhill, Christoph Rzymski, Johannes Englisch, and Russell D. Gray. 2022a.  Lexibank, a public repository of standardized wordlists with computed phonological and lexical features.  _Scientific Data_ , 9(356):1–16.
  * List et al. (2017) Johann-Mattis List, Simon J. Greenhill, and Russell D. Gray. 2017.  The potential of automatic word comparison for historical linguistics.  _PLOS ONE_ , 12(1):1–18.
  * List et al. (2022b) Johann-Mattis List, Annika Tjuka nd Christoph Rzymski, Simon J. Greenhill, Nathanael E. Schweikhard, and Robert Forkel. 2022b.  _CLLD Concepticon [Dataset, Version 2.6.0]_.  Max Planck Institute Evolutionary Anthropology, Leipzig.
  * Meisel (2018) Jürgen M. Meisel. 2018.  Early child second language acquisition: French gender in german children.  _Bilingualism: Language and Cognition_ , 21(4):656–673.
  * Mennecier et al. (2016) Phillipe Mennecier, John Nerbonne, Evelyne Heyer, and Franz Manni. 2016.  A Central Asian language survey.  _Language Dynamics and Change_ , 6(1):57–98.
  * Mi et al. (2020) Chenggang Mi, Lei Xie, and Yanning Zhang. 2020.  Loanword identification in low-resource languages with minimal supervision.  _ACM Trans. Asian Low-Resour. Lang. Inf. Process._ , 19(3).
  * Miller et al. (2020) John E. Miller, Tiago Tresoldi, Roberto Zariquiey, César A. Beltrán Castañón, Natalia Morozova, and Johann-Mattis List. 2020.  Using lexical language models to detect borrowings in monolingual wordlists.  _PLOS One_ , 15(12):e0242709.
  * Moro et al. (2023) Francesca R. Moro, Yunus Sulistyono, and Gereon A. Kaiping. 2023.  Detecting papuan loanwords in alorese: Combining quantitative and qualitative methods.  In _Traces of Contact in the Lexicon_ , pages 213–262. Brill.
  * Nath et al. (2022) Abhijnan Nath, Sina Mahdipour Saravani, Ibrahim Khebour, Sheikh Mannan, Zihui Li, and Nikhil Krishnaswamy. 2022.  A generalized method for automated multilingual loanword detection.  In _Proceedings of the 29th International Conference on Computational Linguistics_ , pages 4996–5013, Gyeongju, Republic of Korea. International Committee on Computational Linguistics.
  * Nelson et al. (2005) P. R. Nelson, P. S. Wludyka, and K. A. F. Copeland. 2005.  The analysis of means: A graphical method for comparing means, rates, and proportions.  _SIAM_.
  * Pedregosa et al. (2011) F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. 2011.  Scikit-learn: Machine learning in Python.  _Journal of Machine Learning Research_ , 12:2825–2830.
  * Prochazka and Vogl (2017) Katharina Prochazka and Gero Vogl. 2017.  Quantifying the driving factors for language shift in a bilingual region.  _Proceedings of the National Academy of Sciences_ , 114(17):4365–4369.
  * Rzymski et al. (2020) Christoph Rzymski, Tiago Tresoldi, Simon Greenhill, Mei-Shin Wu, Nathanael E. Schweikhard, Maria Koptjevskaja-Tamm, Volker Gast, Timotheus A. Bodt, Abbie Hantgan, Gereon A. Kaiping, Sophie Chang, Yunfan Lai, Natalia Morozova, Heini Arjava, Nataliia Hübler, Ezequiel Koile, Steve Pepper, Mariann Proos, Briana Van Epps, Ingrid Blanco, Carolin Hundt, Sergei Monakhov, Kristina Pianykh, Sallona Ramesh, Russell D. Gray, Robert Forkel, and Johann-Mattis List. 2020.  The Database of Cross-Linguistic Colexifications, reproducible analysis of cross- linguistic polysemies.  _Scientific Data_ , 7(13):1–12.
  * SAS Institute Inc. (2021) SAS Institute Inc. 2021.  Jmp®, version 16.1.0.  Software.
  * van der Ark et al. (2007) René van der Ark, Philippe Mennecier, John Nerbonne, and Franz Manni. 2007.  Preliminary identification of language groups and loan words in Central Asia.  In _Proceedings of the RANLP Workshop on Acquisition and Management of Multilingual Lexicons_ , pages 13–20.
  * Zhang et al. (2021) Liqin Zhang, Ray Fabri, John Nerbonne, and John Nerbonne. 2021.  Detecting loan words computationally.  In _Contact Language Library_ , pages 269–288. John Benjamins Publishing Company.


The application of diagrammatic reasoning techniques to large-scale quantum processes needs specific tools to describe families of diagrams of arbitrary size. For now, large-scale diagrammatic reasoning tools in ZH-calculus come in two flavours, !-boxes and scalable notations. This paper investigates the interactions between the two approaches by exhibiting correspondences through various examples from the literature, focusing on (hyper)graph states and diagrammatic transforms. In doing so, we set up a path toward a neat and tidy large-scale diagrammatic reasoning toolbox.

§ INTRODUCTION

Motivation: One of the most used models of quantum computation is quantum circuits; a circuit is a sequence of quantum logic gates applied
to a list of qubits. It is a useful framework for writing
quantum algorithms. However, it is challenging to rewrite circuits or
check if two of them perform the same operation. Among the methods to reason on circuits, ZX-calculus has risen from categorical theories [12] to provide
an intuitive and efficient framework for quantum computation. ZX-calculus
contains an equational theory which allows to rewrite diagrams
and enables smart circuit optimisations [19, 17, 3] and verification
[23] schemes. A set of rules for ZX-calculus have been
proven complete for Clifford+T quantum operations [16].
Its cousin ZH-calculus specialises in nonlinearity [2], but contains some useful
aspects [22, 23]
that are hard to transpose in ZX-calculus; as it
carries a native representation of Toffoli and CCZ gates,
it holds a multiplicative behaviour that is tough to
picture in ZX-calculus.

As quantum circuits become arbitrarily large, reasoning on them is harder since the different rules may not scale, for example, in ZH-calculus. To overcome this,
large-scale diagrammatic tools have been developed, such as
!-boxes [24, 18] or scalable calculus [9].
These two might look very different: the first keeps
the syntax of the base graphical calculus where some subdiagrams
can be repeated any number of times to model a family of diagrams;
the other adds new generators to picture any number of wires as
a single one. Our goal is to show that the two are very much alike
and that they have a similar expressivity. A translation between them
also allows to write diagrams using both, and would give
a new understanding of different works done in one or the other.

Contribution: In this paper, we compare and translate !-boxes and scalable notations on several relevant examples. First, we consider the matrix arrows generators
of scalable ZH-calculus. Translating theme into !-boxes gives a practical translation between the frameworks and allows direct diagrammatical proofs of arrows properties dramatically shorter than the proofs by induction of [9]. Then, the transformations expressed in [23] using !-boxes, namely hyper-local complementation and Fourier hyper pivot, are here pictured in scalable notations. We provide concise, scalable proofs of those transformations. However, in doing so we lose the readability of the topological structure allowed by !-boxes. Finally, by exhibiting the connection between matrix arrows and the trapezes of [22], we show that scalable notations are also well-suited for graphical transforms. Relying on this, we give alternative proofs of the spider nest identities of [25, 6] by direct transform computation.

Structure of the paper: We first ZH-calculus is introduced in its well-tempered form [4] in Section <ref>. Once both frameworks, namely !-boxes and SZH-calculus, are defined in Section <ref>, we describe heuristics to translate between the two in section <ref>. We then give concrete examples of applications of those heuristics to the hyper local complementation and regular hyper pivot [23]. Finally, in Section <ref>, we introduce graphical transforms in SZH-calculus and use them to derive the Fourier hyper pivot [23] and spider nest identities [25, 6].

§ ZH-CALCULUS

The ZH-calculus is a graphical language introduced by Backens and Kissinger [2]
to represent linear maps in a complex vector space through diagrams – which will will be
referred to as ZH-diagrams. A ZH-diagram is a collection of generators and wires
between them. When $a$ is a complex number, the generators are:

In colloquial speech, these can be called
respectively h-box and green dot, or more vaguely spiders.
The generators are given a semantics in complex matrices spaces, which
is in itself compositional and provides then a semantics for any ZH-diagram.
We consider in this paper the well-tempered [5] semantics:

$$\sem{\tikzfig{figures/z-basic}}=2^{\frac{m+n-2}{4}}\left(\ket 0^{\otimes n}\bra 0^{\otimes m}
+\ket 1^{\otimes n}\bra 1^{\otimes m}\right) \quad
\sem{\tikzfig{figures/h-basic}}=2^{\frac{-m-n}{4}}\sum_{x,y\in\{0,1\}^{m+n}}
a^{x_1\dots x_my_1\dots y_n}\ket y\bra x$$

Diagrams can be composed horizontally or vertically, meaning:

= \sem{\tikzfig{figures/diag}}\otimes \sem{\tikzfig{figures/diag-prime}}
\qquad\qquad
\sem{\tikzfig{figures/diag-composition}}
=\sem{\tikzfig{figures/diag}} \circ \sem{\tikzfig{figures/diag-prime}}$$

The tensor product is symmetric, meaning that we allow swapping wires, some
natural equations in the diagrammatic calculus arise:

Loose ends on the left and on the right are respectively inputs and outputs
of the diagram.
It follows that a single wire with no generator performs
the identity. Besides, we allow wires to bend:

$$\sem{\tikzfig{figures/id}} = \ketbra 0 + \ketbra 1 \qquad
\sem{\tikzfig{figures/cup}} = \ket{00}+\ket{11} \qquad
\sem{\tikzfig{figures/cap}} = \bra{00}+\bra{11}$$

The choice of well-tempered scalars is significant: some equations stated
in the following sections have application in the verification of
quantum circuits, for example, hence the necessity to keep
the scalars – which is not always the case in graphical calculi. Another useful spider is the X-spider – or red dot –
which is a generator from ZX-calculus and can be defined as a ZH diagram below.
An empty h-box is actually an h-box with phase $-1$, such that a two-wired
empty h-box pictures exactly the Hadamard gate.
The diagrammatic equivalent of the $\texttt{NOT}$ gate is defined below.

Diagrams are drawn until now with wires from left to right to easily understand
them as inputs and outputs w.r.t. the semantics, but they can as well be written
from bottom to top. Besides, only topology matters:

(ZS1)     $\tikzfig{figures/zs1}$             (ZS2)     $\tikzfig{figures/zs2}$

(HS1)     $\tikzfig{figures/hs1}$             (HS2)     $\tikzfig{figures/hs2}$

(BA1)     $\tikzfig{figures/ba1}$             (BA2)     $\tikzfig{figures/ba2}$

(M)     $\tikzfig{figures/m-axiom}$             (I)     $\tikzfig{figures/i-axiom}$

(A)     $\tikzfig{figures/a-axiom}$             (O)     $\tikzfig{figures/o-axiom}$

(U)     $\tikzfig{figures/u-axiom}$

Rules of the ZH-calculus [2]

ZH-calculus comes with a set of rules (see Fig. <ref>) that is complete, meaning that if two ZH-diagrams represent the same linear map, then those diagrams can be transformed into one another using these rules. There is no limit to how big a ZH-diagram can be; this paper takes a particular interest in two large-scale diagrammatic tools that allow to represent and manipulate unboundedly large diagrams.

§ LARGE-SCALE METHODS

This section introduces separately two large-scale diagrammatic tools,
namely !-boxes and scalable notations; to study and compare
them in the oncoming sections.

§.§ !-boxes

Many equations of diagrams benefit from being written with notation
that capture large-scale designs. Already some equations in Fig.<ref>
need dots "$\dots$" to fully picture their behavior. However the semantics of
the dots is not well defined and their expression capability is very limited;
they may as well become confusing. !-boxes – read "bang-boxes" – are an attempt at picturing large-scale diagrams more thoroughly. A !-box circling a part of a ZH-diagram means that this subdiagram	can be replicated any number of times; a diagram containing a !-box represents then a family of diagrams, as follows:

$$\tikzfig{figures/def-bang}\quad =\quad
\left\{\quad\tikzfig{figures/def-bang-0}\quad ;\quad
\tikzfig{figures/def-bang-1}\quad ;\quad
\tikzfig{figures/def-bang-2}\quad ;\quad
\tikzfig{figures/def-bang-3}\quad ;\quad \dots\quad
\right\}$$

If one requires to specify a diagram from the family, the !-box
can be annotated, and we get the diagram on the left below.
!-boxes can also be overlapped, resulting in a fully-connected bipartite graph on the right:

\qquad\qquad\tikzfig{figures/def-bang-overl}$$

A particular equation that requires graphical Fourier transform [22]
is pictured through !-boxes annotated with sets and parameters
that cover the sets, like in the upcoming example.
From now on, for any natural number $n$ we will write $[n]$ to denote the set

We will also use gray trapezes:	$\qquad\tikzfig{figures/def-trapeze2}$.

As an example of use, some rules of Fig.<ref> are better written with !-boxes:

\begin{align*}
\tikzfig{figures/zs1-bang} \qquad
\tikzfig{figures/hs1-bang} \\
\tikzfig{figures/ba1-bang} \qquad
\tikzfig{figures/ba2-bang}
\end{align*}

§.§ Scalable notations

The scalable notation have first been introduced in [11] before being formalised in [9]. As opposed to !-boxes, the idea is to stay inside the prop framework by introducing new kinds of wires and generators representing large-scale processes.

§.§.§ SZH

In SZH, for each $n\in \mathbb{N}^* $, where $\mathbb{N}^*$ are the natural integers without zero, we have a type of wire of size $n$ denoted $(n)$. Formally the corresponding categorical structure will then be a $\mathbb{N}^*$-colored prop and the generic types are of the form $(n_1) +\cdots +(n_i )+ \cdots + (n_m )$. The size of a type is inductively defined as: $|(n)|\df n$ and $|a + b|\df|a|+ |b|$. We use thin wires to denote wires of type $(1)$ and thick wires denote any $(n)$. We write $(m)^n$ for the tensor product of $n$ wires $(m)$ with the convention $(m)^0=(0)$. We have two new families of generators, the dividers and the gatherers, for each positive integer $n$ satisfying the following equations:

$\tikzfig{dd}$ 0.8$: (n+1)\to (1)+ (n)$ $\qquad$ $\tikzfig{gg}$0.8$: (1)+ (n)\to (n+1)$ $\qquad$ $\tikzfig{ex0}=\tikzfig{ex1}\qquad\tikzfig{el0}=\tikzfig{el1}$

For every generator $n\to m$ of ZH and every $k\in \mathbb{N}^*$ there is a generator $(k)^n \to (k)^m$ in SZH. Those scaled generators satisfy the same equations as the original ones:

$\tikzfig{z}:(k)^n\to (k)^m \qquad \tikzfig{h}:(k)^n\to (k)^m$

They interacting with dividers and gatherers as:

Note that here $\mathbf{a}\in \mathbb{C}^k $ is a list of $k$ complex parameters .$\mathbf{a}_0 $ is the head of $\mathbf{a}$ and $\mathbf{a}' $ its tail. We can generalize the following rules by taking addition and multiplication of lists pointwise:

It is shown in [10] that any diagram in SZH can be rewritten into normal form.

For each $f:a\to b$ in SZH there is a unique $|f|:|a|\to |b|$ in ZH such that:

This allows to extend the size map into the wire stripping functor $|\_|:SZH\to ZH$. We can then extend the interpretation of ZH into an interpretation of SZH, $\interp{\_}:SZH\to \mathbf{FHilb}_2$, defined as $\interp{D}=\interp{|D|}$. We have $\interp{(n)}\df\mathbb{C}^{2^n }$ and $\interp{a + b}\df \interp{a}\otimes\interp{b}$. The wires have interpretations:

$\interp{\tikzfig{n}}\df \sum\limits_{x\in \textbf{2}^n } \ket{x}\bra{x} \quad\interp{\tikzfig{swap}}\df \sum\limits_{x,y\in \textbf{2}^n } \ket{x}\ket{y}\bra{x}\bra{y}\quad\interp{\tikzfig{bcup}}\df \sum\limits_{x\in \textbf{2}^n}\ket{x}\ket{x}\quad\interp{\tikzfig{bcap}}\df \sum\limits_{x\in \textbf{2}^n}\bra{x}\bra{x}$.

The dividers and gatherers act trivially:
$\interp{\tikzfig{dd}}\df \sum\limits_{x\in \textbf{2}^{n+1} } \ket{x}\bra{x}$ and $\interp{\tikzfig{gg}}\df \sum\limits_{x\in \textbf{2}^{n+1} } \ket{x}\bra{x}$.

The arachnids of type $(k)^n\to (k)^m$ have interpretations:

$\interp{\tikzfig{z}}\df 2^{k\frac{n+m-2}{4}}\sum\limits_{x\in {\bf 2}^k} e^{i(x\cdot a)}\ket{x}^{\otimes n}\!\bra{x}^{\otimes m}\qquad\interp{\tikzfig{h}}\df 2^{-k\frac{n+m}{4}}\sum\limits_{x_i\in {\bf 2}^k} \prod\limits_{j=1}^{k} a_j^{\bigwedge\limits_{i=1}^{n+m} x_{i,j}}\ket{x_1 \cdots x_n}\!\bra{x_{n+1} \cdots x_{n+m}}$

Where the $x_i$ are binary words of size $k$ and $x_{i,j}$ is the $j$-th bit of $x_i$.

§.§.§ Matrix arrows

The main interest of scalable notations for ZH is the manipulation of matrix arrows, new kinds of generators encapsulating bipartite graph diagrams that were already present in [11]. There are two kinds, the red and the yellow ones:

Where $A\in \mathcal{M}_{m\times n}(\{0,1\})$ is a $\{0,1\}$-matrix corresponding to the bi-adjacency matrix of the green/red and green/yellow bipartite graphs respectively. In particular:

By convention if the matrix is not specified then it is considered to be full of $1$. Arrows are copied and erased by green nodes and co-copied and co-erased respectively by red and yellow nodes:

They can be composed in the following ways:

Where $BA$ is the matrix product taken over the field $\mathbb{F}_2 $ and $B\cdot A $ is the matrix product taken over the boolean ring $\mathbb{B}$ with $+ = \lor$ and $\times = \land $. Note that this last product is, in practice, easier to compute than the first one. The interpretation is then:

$\interp{\tikzfig{rarrow}}= \ket{x}\mapsto 2^{\frac{m-n}{4}}\ket{Ax}\qquad\interp{\tikzfig{yarrow}}= \ket{x}\mapsto 2^{\frac{m-n}{4}}\ket{A\cdot x}$

Finally, there are two properties that are very useful in practice, the Hadamard gate can flip red arrows and when the matrix $C$ has at most one $1$ in each row then red and yellow arrows are equivalent:

§ A DICTIONARY BETWEEN !-BOXES AND SCALABLE NOTATIONS

Now that the two styles of large-scale diagrammatic reasoning tools have been introduced, we will investigate their respective expressivity and efficiency by considering the translation from one formalism to the other in various cases. Here we will denote $\leftrightarrow$ to express that a scalable and a !-box diagram correspond to the same ZH diagram. A rigorous proof that !-boxes and scalable notations have the same expressiveness would require the development of a framework able to handle parametrized families of diagrams. Some work has been done on this matter [20, 21, 27, 18, 24], but they do not picture !-boxes in a compositional way and often do not encompass overlapping. We do not ambition to do it here. However, we provide translation heuristics that strongly support the conjecture that the expressiveness of the two approaches is indeed similar.

§.§ Boxes and arrows

The scaled generators have direct corresponding !-box diagrams up to permutations of the inputs and outputs:

An important remark that will be at the core of all our examples is that the matrix arrows are in fact very nicely expressed as !-boxes:

Knowing this one can for example easily show that matrix arrows are erased in one line of !-box manipulation:

The compactness and elegance of this proof must be compared with the lengthy proofs by induction of [9], typical of scalable notations.
Very similar proofs can be done for all properties of matrix arrows. We see that !-boxes allow for zooming in arrows to exploit their internal structure. In the other direction, it is now clear the trapezes are just arrows in disguise:

It is particularly striking that this structure appears to have been discovered independently for completely different reasons in [11] and [22]. This correspondence between arrows and !-boxes is particularly fruitful in the following simple cases:

Those expressions will be instrumental to reformulate !-box diagrams into similar scalable ones. The general heuristic goes as follows: from scalable to !-boxes, expand the scaled generators and arrows, and from !-boxes to scalable, identify the relevant structures appearing in the dictionary and replace them with arrows.

§.§ (Hyper)local complementation

Graph states form a particular family of states defined as follows: starting from a graph on $n$ vertices, we take a tensor product of $n$ $\ket{+}$ states, corresponding to green nodes. Then we apply $C$-$Z$ gates for each edge of the graph two the corresponding nodes. $C$-$Z$ gates are represented as: czgate, any graph state can then be represented as: graphstate. Where $K_n $ is a $\binom{n}{2}\times n $-matrix defined as $(K_n )_{v,e}= v\in e $, and $G$ is a $\{-1, 1\}$-vector that characterizes the edges in $G$ by $-1$ and the edges not in $G$ by $1$. Graph-states enjoy numerous interesting properties, and the interested reader can consult for example [15] for more details. Here we will focus on the local complementation rule, that can be expressed as:

This rule is the core of the following identity.

We have: $\quad\tikzfig{figures/hlc}$

Hyperlocal complementation cannot be fully pictured without
using dots, even with !-boxes. Dots could be avoided by creating
some new notation or a new definition for !-boxes, but it would not
fit naturally in the current diagrammatic language. A similar theorem can be formulated in scalable notations, with the following correspondence:

Here the scalable version is more general and less precise than the !-box version. Here the !-boxes exhibit an internal structure that is hidden inside the matrix arrows.

§.§ Regular hyper pivot

The regular hyper pivot is a generalisation of the pivot rule.
The latter was
formalized for ZX-calculus [13, 14] in order to
enhance quantum circuits optimisation. The hyper pivot rule arises from
applying the same graph-theoretic transformation as pivoting, but in a

The following equation holds in ZH-calculus:

It is interesting to note that (HS2), (BA1) and (BA2) from Fig.<ref> are
particular cases of the regular hyper pivot, as proven in [23].
The regular hyper pivot can easily be translated into SZH-calculus, considering the
correspondance shown in Section <ref>:

It gives the following theorem, proven in SZH-calculus.

The following equation holds in SZH-calculus, for any Boolean matrices $A,B$:

The proof is very short:

The second to last equality is given by the following lemma:

This equation holds in SZH-calculus, for any Boolean matrices $A,B$:

Besides, this proof is very similar to the one done with !-boxes: there is no
fundamental difference between !-boxes and scalable notation regarding the regular
hyper pivot. However, the following section tackles a set of diagrams that seem more
natural written in SZH-calculus.

§ DIAGRAMMATIC TRANSFORMS

Diagrammatic transforms have been introduced in [22] as an efficient way to transform ZX diagrams into ZH diagrams and vice versa. In this section, we present a different approach to diagrammatic transforms that allows us to consider them either with !-boxes or with scalable notations.

§.§ Transforms of boolean functions

An invertible linear map $D:2^n \to 2^n $ which is diagonal in the computational basis can be described by a boolean function $f: \{0,1\}^n \to \mathbb{C}^*$ such that $D\ket{x}=f(x)\ket{x}$. The pointwise multiplication of boolean functions $(fg)(x)=f(x)g(x)$ then corresponds to the composition of the underlying diagonal linear maps. We will write $f^\lambda (x)= f(x)^\lambda$ for any $\lambda\in \mathbb{Z}$ with the convention that $z^0 =1$. We call transform a group automorphisms of ${\mathbb{C}^*}^{\{0,1\}^n}$ that is, a map $T:\mathbb{C}^{\{0,1\}^n} \to \mathbb{C}^{\{0,1\}^n} $ such that $T(fg)=T(f)T(g)$ and $T(f^\lambda )= T(f)^\lambda $. We will mainly consider two such transforms, the Fourrier and the Mobius transforms:

The Fourrier  and Mobius transforms $\hat{f}$ and $\tilde{f}$ defined respectively as:

$ \hat{f}(s)=\prod\limits_{t} f(t)^{-2^{1-n}(-1)^{s\cdot t}}\quad$ and $\quad \tilde{f}(s)\doteq\prod\limits_{t\leq s} f(t)^{(-1)^{|t|+|s|}}$

$f(x)=f(\emptyset)\prod\limits_{s} \check{f}(s)^{s\cdot x }\quad$ and $\quad f(x)=\prod\limits_{s\leq x} \tilde{f}(s)$.

Where $|x|$ denotes the Hamming weight of $x$, which is the number of one in it, and $s\cdot t \doteq \bigoplus\limits_{i=0}^{2^n -1} x_i y_i$. One needs to be careful here, the power $2^{1-n}$ is no uniquely defined if $ 1< n$, in fact the decomposition is not unique and choosing any solution leads to a valid decomposition. More precisely for each $t$ we can choose any of the $2^{n-1)} $ solutions of the equation $X^{2^{n-1}}=f(t)$, this gives $2^{2n-1}$ possibilities for the Fourrier transform. However, all of those possibilities satisfies the inversion formula.

§.§ Transforms of diagram

The practical interest of those transforms is that they can be interpreted as a way to realize any diagonal map $D: 2^n \to 2^m $ as a composite of elementary gates. Given $s \subseteq \{1,\dots,n\}$ and $\lambda \in \mathbb{C}^* $ we define the phase-gadget $X_{s,\lambda}$ and the generalized hyper-edge $H_{s,\lambda}$ respectively as:

$X_{s,\lambda} \ket{x}\doteq \lambda^{s\cdot x} \ket{x} \qquad \interp{\tikzfig{phasegadget}}= X_{s,\lambda}\qquad
H_{s,\lambda} \ket{x}\doteq \lambda^{\delta_{s\leq x}}\ket{x} \qquad \interp{\tikzfig{hyperedge}}= H_{s,\lambda}$

We see that a composition of phase-gadgets or hyper-edges can be rewritten using arrows. Thus we have:

Given a diagonal linear map $D:2^n \to 2^n $ and the corresponding boolean function $f: \{0,1\}^n \to \mathbb{C}^* $ we have:

$\interp{\tikzfig{fourrierdiag}}=\interp{\tikzfig{mobiusdiag}}= D$, $\quad\tikzfig{fourrierdiag2}=\tikzfig{mobiusdiag2}\quad$ and
$\tilde{f}(x)=\prod\limits_{t\geq x}  \hat{f}(t)^{-2^{|x|-1}}$

$\hat{f}(x)=\prod\limits_{t\geq x}  \tilde{f}(t)^{-2^{1-|t|}(-1)^{|x|}}$

$f(\emptyset)=\tilde{f}(\emptyset)= \prod\limits_{t}  \hat{f}(t)^{-\frac{1}{2}}$

Where the $2^n \times n $-matrix $\Delta_n$ is defined as $(\Delta_n)_{i,s} \df \delta_{i\in s}$. This matrix contains all possible positions for the legs of hyper-edges and phase gadgets. This happens to be very useful in practice when we want to switch between weighted hyper-graph and phase-gadget nests. The matrix $S_n $ here is just a reformulation of the trapezes. What we see here is just a direct reformulation of the original formulation of diagrammatic transform introduced in [22].

§.§ Spider nest identities

Spider nest identities have been introduced in [6] useful rewriting rules to simplify quantum circuits. Formally, a spider nest identity is given by a composition of spider-like diagrams, typically generalized hyper-edges, and phase gadgets, with one big spider and a lot of tiny ones, which equals the identity. Those identities can be derived directly using the diagrammatic transforms. We here consider the special case of symmetric boolean functions, that is, when $f(x)$ only depends on the Hamming weight of $x$. We write $F:\textbf{n}\to \mathbb{R}$ the function such that $f(x)=F(|x|)$. We then have more compact transforms.

The Kravchuk and Binomial transforms $\hat{F}$ and $\tilde{F}$ defined respectively as:

$\hat{F}(m)\df \prod\limits_{k=0}^{n}F(k)^{-2^{1-n}K^n_k(m)}$
$\tilde{F}(m)\df\prod\limits_{k=0}^{m} F(k)^{\binom{m}{k} (-1)^{m-k}}$

where $K^n_k$ is the Kravchuk polynomial: $K^n_k(X)\df\sum\limits_{j=0}^{k}\binom{X}{j}\binom{n-X}{k-j}(-1)^j$, satisfy:

$\hat{f}(x)=\hat{F}(|x|)$, $\quad\tilde{f}(x)=\tilde{F}(|x|)$,  $\quad F(m)=\prod\limits_{k=0}^n \hat{F}(k)^{\frac{-1}{2}K^n_k(m)}\quad$ and
$\quad F(m)=\prod\limits_{k=0}^{m}\tilde{F}(k)^{\binom{m}{k}}$

See [7] for details on transforms of symmetric boolean functions. Note the $\frac{1}{2^n}$ in exponent for the Kravchuk transform, this means that the previous remark on the uniqueness of the Fourier transform also applies here. Direct computations using those transforms allow to derive the two following spider-nest identities:

We have:
$\quad\tikzfig{mobiusgadget}\quad$ and $\quad\tikzfig{spidernest}$

where $\omega=e^{\frac{i\pi}{4}}$ and $\hat{s}$ is a symmetric boolean function defined as:

$\hat{S}(0)=1$ $\hat{S}(1)=e^{\frac{i\pi(n-2)(n-3)}{16}}$ $\hat{S}(2)=e^{\frac{-i\pi(n-3)}{8}}$ $\hat{S}(3)=e^{\frac{i\pi}{8}}$ $\hat{S}(n)=e^{\frac{-i\pi}{8}}$  $\hat{S}(k)=1$ for $ k\neq 0,1,2,3,n$.

The first one has been derived using a proof by induction in [25], the second one introduced in [6] was first derived using the diagrammatic transform from <cit.> and successfully used to simplify quantum circuits. The method used to derive those equalities open the way to the automatic mining of spider-nest identities.

§.§ Fourier hyper pivot

The Fourier hyper pivot is a diagrammatic equation inspired by one of
the rewrite rules created by Amy [1]. Those rewrite
rules are not between diagrams but algebraic expressions, nevertheless both
frameworks carry the same expressiveness, as stated in [26, 23]. Amy generalized some quantum circuit equations to perform efficient verification; and the rule which came out of the Hadamard boxes cancellation is very successful on that matter. The Fourier hyper pivot is the direct translation of the latter. This diagrammatic equation is, in addition, a relevant example of the use of the graphical Fourier transform [22] and it motivates the use of !-boxes
instead of dots in ZH-calculus.

The following equation holds for any $n,m\in\N$, any family
of complex numbers $\lambda$ and where $\vert b\vert$ denotes
the weight of $b$:

The regular hyper pivot is a particular case of this equation. It can be seen
rather easily by replacing all the $\lambda_i$ with $-1$. SZH-calculus seems more adapted to picture the Fourier hyper pivot: a family of trapezes is directly an arrow, and we will see that it is a generalisation of Theorem <ref>.

The following equation holds in SZH-calculus, for any Boolean
matrices $A,B$ and complex vector $\fl\lambda$:

where $C= \Delta_{nm}\cdot \overrightarrow{I_n} \cdot A$, $D=\Delta_{nm}\cdot \overrightarrow{I_m} \cdot B$ and $\mu_{\emptyset}=\prod\limits_{i} \lambda_i^{\frac{-1}{2}}$, $\mu_s= \begin{cases}
\lambda_i^{-2^{|s|-1}} \text{ if } s\leq \overrightarrow{\{i\}}\\
1 \text{ else}
\end{cases}$ where $s\in \{0,1\}^{nm}$, and $\overrightarrow{\{i\}}$ is the binary words of $m$ copies of the binary word of size $n$ with only one $1$ at position $i$.

One can see here that the whole complexity of the expressions is almost hidden and lies in the matrices and the vectors that index the diagrams.

§ CONCLUSION

We have studied the interplay of !-boxes and scalable notations in many examples of large-scale graphical reasoning. It appears that the indexed trapeze box of [22] and [23] to present diagrammatic transforms exactly correspond to the arrows of scalable notations. Thus, all reasoning involving matrix arrows in scalable notations, for example in [8], can be straightforwardly carried out with !-boxes. Using this correspondence, we express graphical transforms in a very compact way using matrix arrows, leading to shorter proofs than the ones given in [22]. This new point of view allowed us to provide direct derivations of the spider nest rules of [6, 25]. Using a hypergraph inspired representation of graph-sates we also dramatically simplified the diagrammatical representation of local complementation from [9]. Turning !-boxes into scalable notations happens to be not so challenging given the proper heuristics. In general, finding a scalable diagram with the right shape is easy. The difficulty is in finding the adequate matrices to label the arrows. We experimented with this on the Fourier Hyper pivot of [23]. Relying on our new formulation of diagrammatic transforms and local complementation, we managed to provide alternative shorter proofs for most results from [23]. This translation exercise made it clear that what scalable notations win in compactness, they lose in faithfulness in exhibiting the internal structure of the diagram. While !-boxes, on the contrary, provide an interesting account of those medium-scale topological structures. To sum up, we conclude by emphasizing three key messages to take from those investigations:

* Large-scale diagrammatic reasoning tools provide powerful rewriting techniques to tidy up cumbersome diagrammatical proofs by exhibiting the relevant topological structure involved and abstracting away diagrammatical noise. Those tools form a bridge between low and higher-level reasoning on quantum processes.

* Given the translation heuristics we presented, it seems highly plausible that !-boxes and scalable notations have the same expressiveness. However, a proper formulation and proof of this conjecture requires developing a framework for parametrized families of diagrams able to encompass both models. Such a framework is also the condition for a hypothetical safe hybrid usage of both tools at once.

* The essential difference between the two frameworks is then at the level of practical efficiency. When to prefer one tool over the other is mainly a question of scale and coarse-graining. The !-boxes have the ability to exhibit the medium-scale topological structure of diagrams, while the scalable notations tend to encapsulate everything into very compact matrix arrows, the medium-scale topological structure being hidden in the indexing matrices.

[1]
authorMatthew Amy (year2019):
titleTowards Large-scale Functional Verification of
Universal Quantum Circuits.
journalElectronic Proceedings in Theoretical Computer
Science volume287, pp. pages1–21,

[2]
authorMiriam Backens &
authorAleks Kissinger
(year2019): titleZH: A Complete Graphical
Calculus for Quantum Computations Involving Classical Non-linearity.
In editorPeter Selinger &
editorGiulio Chiribella, editors: booktitleProceedings of the 15th International Conference on
Quantum Physics and Logic, Halifax, Canada, 3-7th June 2018, seriesElectronic Proceedings in Theoretical Computer Science
volume287, publisherOpen Publishing Association, pp.
pages23–42, 10.4204/EPTCS.287.2.

[3]
authorMiriam Backens,
authorHector Miller-Bakewell,
authorGiovanni de Felice,
authorLeo Lobski &
authorJohn van de Wetering
(year2021): titleThere and back again: A circuit
extraction tale.
journalQuantum volume5, p.
pages421, 10.22331/q-2021-03-25-421.

[4]
authorNiel de Beaudrap
(year2020): titleWell-tempered ZX and ZH
journalarXiv preprint arXiv:2006.02557.

[5]
authorNiel de Beaudrap
(year2021): titleWell-tempered ZX and ZH
journalElectronic Proceedings in Theoretical Computer
Science volume340, pp. pages13–45,

[6]
authorNiel de Beaudrap,
authorXiaoning Bian &
authorQuanlong Wang
(year2020): titleFast and Effective Techniques
for T-Count Reduction via Spider Nest Identities.
In: booktitle15th Conference on the Theory of Quantum
Computation, Communication and Cryptography.

[7]
authorAnne Canteaut &
authorMarion Videau
(year2005): titleSymmetric boolean functions.
journalIEEE Transactions on information theory
volume51(number8), pp. pages2791–2811.

[8]
authorTitouan Carette,
authorYohann D'Anello
& authorSimon Perdrix
(year2021): titleQuantum Algorithms and Oracles
with the Scalable ZX-calculus.
journalElectronic Proceedings in Theoretical Computer
Science volume343, pp. pages193–209,

[9]
authorTitouan Carette,
authorDominic Horsman &
authorSimon Perdrix
(year2019): titleSZX-Calculus: Scalable
Graphical Quantum Reasoning.
In: booktitle44th International Symposium on
Mathematical Foundations of Computer Science (MFCS 2019),
organizationSchloss Dagstuhl-Leibniz-Zentrum fuer Informatik.

[10]
authorTitouan Carette &
authorSimon Perdrix
(year2020): titleColored props for large scale
graphical reasoning.
journalarXiv preprint arXiv:2007.03564.

[11]
authorNicholas Chancellor,
authorAleks Kissinger,
authorJoschka Roffe,
authorStefan Zohren &
authorDominic Horsman
(year2016): titleGraphical structures for design
and verification of quantum error correction.
journalarXiv preprint arXiv:1611.08012.

[12]
authorBob Coecke & authorRoss
Duncan (year2011):
titleInteracting quantum observables: categorical algebra
and diagrammatics.
journalNew Journal of Physics
volume13(number4), p. pages043016.

[13]
authorRoss Duncan &
authorSimon Perdrix
(year2009): titleGraph states and the necessity
of Euler decomposition.
In: booktitleConference on Computability in Europe,
organizationSpringer, pp. pages167–177.

[14]
authorRoss Duncan &
authorSimon Perdrix
(year2013): titlePivoting Makes the
ZX-Calculus Complete for Real Stabilizers.
In: booktitleQPL 2013, seriesElectronic
Proceedings in Theoretical Computer Science, pp. pages50–62,

[15]
authorMarc Hein, authorWolfgang
Dür, authorJens Eisert, authorRobert Raussendorf, authorM Nest &
authorH-J Briegel
(year2006): titleEntanglement in graph states
and its applications.
journalProceedings of the International School of
Physics “Enrico Fermi” on “Quantum Computers, Algorithms and Chaos”,

[16]
authorEmmanuel Jeandel,
authorSimon Perdrix &
authorRenaud Vilmart
(year2018): titleA complete axiomatisation of
the ZX-calculus for Clifford+ T quantum mechanics.
In: booktitleProceedings of the 33rd Annual ACM/IEEE
Symposium on Logic in Computer Science (LICS), organizationACM,
pp. pages559–568.

[17]
authorA. Kissinger &
authorJohn van de Wetering
(year2018): titlePyZX.

[18]
authorAleks Kissinger &
authorDavid Quick
(year2015): titleA first-order logic for string
diagrams, 10.48550/ARXIV.1505.00343.

[19]
authorAleks Kissinger &
authorJohn van de Wetering
(year2019): titleReducing T-count with the
journalarXiv preprint arXiv:1903.10477.

[20]
authorAleks Kissinger &
authorVladimir Zamdzhiev
(year2015): title!-Graphs with Trivial Overlap
are Context-Free.
journalElectronic Proceedings in Theoretical Computer
Science volume181, pp. pages16–31,

[21]
authorAleks Kissinger &
authorVladimir Zamdzhiev
(year2015): titleEquational Reasoning with
Context-Free Families of String Diagrams.
In: booktitleGraph Transformation,
publisherSpringer International Publishing, pp.
pages138–154, 10.1007/978-3-319-21145-9_9.

[22]
authorStach Kuijpers,
authorJohn van de Wetering &
authorAleks Kissinger
(year2019): titleGraphical Fourier Theory and
the Cost of Quantum Addition.
journalarXiv preprint arXiv:1904.07551.

[23]
authorLouis Lemonnier,
authorJohn van de Wetering &
authorAleks Kissinger
(year2021): titleHypergraph Simplification:
Linking the Path-sum Approach to the ZH-calculus.
journalElectronic Proceedings in Theoretical Computer
Science volume340, p. pages188–212,

[24]
authorAlexander Merry
(year2014): titleReasoning with !-Graphs,

[25]
authorAnthony Munson, authorBob
Coecke & authorQuanlong Wang: titleAND-gates in ZX-calculus: spider nest
identities and QBC-completeness.

[26]
authorRenaud Vilmart
(year2021): titleThe Structure of
Sum-Over-Paths, its Consequences, and Completeness for Clifford.
journalFoundations of Software Science and
Computation Structures volume12650, pp. pages531 –

[27]
authorVladimir Zamdzhiev
(year2019): titleA Framework for Rewriting
Families of String Diagrams.
journalElectronic Proceedings in Theoretical Computer
Science volume288, pp. pages63–76,

§ PROOFS

First for the Fourier transform:

$f(\emptyset)\prod\limits_{s} \hat{f}(s)^{s\cdot x }=f(\emptyset)\prod\limits_{s} \left(\prod\limits_{t} f(t)^{-2^{1-n}(-1)^{s\cdot t}}\right)^{s\cdot x }
= f(\emptyset)\prod\limits_{t,s} f(t)^{-(s\cdot x)2^{1-n} (-1)^{s\cdot t}}
= f(\emptyset)\prod\limits_{t}  f(t)^{-2^{1-n}\sum\limits_{s} (s\cdot x) (-1)^{s\cdot t}}$

We evaluate $2^{1-n}\sum\limits_{s} (s\cdot x) (-1)^{s\cdot t}$. Using $s\cdot x= \frac{1-(-1)^{s\cdot x}}{2}$ and $\sum\limits_{t} (-1)^{s\cdot t}=2^n \delta_{s= \emptyset}$ we have:

$2^{1-n}\sum\limits_{s} (s\cdot x) (-1)^{s\cdot t}=2^{-n}\sum\limits_{s} (-1)^{s\cdot t} -2^{-n}\sum\limits_{s} (-1)^{s \cdot (x\oplus t)}=\delta_{t= \emptyset} -\delta_{x=t}$

$f(\emptyset)\prod\limits_{t} \hat{f}(t)^{s\cdot t }=f(\emptyset)\prod\limits_{t}  f(t)^{\delta_{x=t} -\delta_{t=\emptyset}}
= f(\emptyset)f(x)f(\emptyset)^{-1}
= f(x)$

For the Mobius transform:

$\prod\limits_{s\leq x} \tilde{f}(s)= \prod\limits_{s\leq x} \prod\limits_{t\leq s} f(t)^{(-1)^{|t|+|s|}}
= \prod\limits_{t\leq x} \quad \prod\limits_{t\leq s\leq x} f(t)^{(-1)^{|t|+|s|}}
= \prod\limits_{t\leq x} f(t)^{\sum\limits_{t\leq s\leq x}(-1)^{|t|+|s|}}$

We evaluate $\sum\limits_{t\leq s\leq x}(-1)^{|t|+|s|}$. If $t=x$ then $ \sum\limits_{t\leq s\leq x}(-1)^{|t|+|s|}=1 $, else there is a position $i$ with $t_i =0$ and $x_i =1 $, without loss of generality we assume that $i=0$.

$\sum\limits_{t\leq s\leq x}(-1)^{|t|+|s|}= \sum\limits_{t\leq 0s'\leq x}(-1)^{|t|+|s'|} + \sum\limits_{t\leq 1s'\leq x}(-1)^{|t|+1+|s'|} = 0$

So $\sum\limits_{t\leq s\leq x}(-1)^{|t|+|s|} = \delta_{t=x}$ and we have:

$\prod\limits_{s\leq x} \tilde{f}(s)= \prod\limits_{t\leq x} f(t)^{\sum\limits_{t\leq s\leq x}(-1)^{|t|+|s|}}
= \prod\limits_{t\leq x} f(t)^{\delta_{t=x}}
= f(x)$

The matrix $\Delta_n $ allows to compose all possible hyper-edges or phase-gadgets. The corresponding parameters $\lambda$s are given in the $H$-boxes. We then obtain diagonal gates that are compositions of elementary phase-gadgets and hyper-edges. This exactly corresponds to the inversion formula for the two transforms, hence the interpretation as the diagonal gate $D$. The equality of the two diagrams then follows by completeness. Now, for the formulas:

$\tilde{f}(x)=\prod\limits_{s\leq x} f(s)^{(-1)^{|s|+|x|}}
= \prod\limits_{s\leq x} \left(f(\emptyset)\prod\limits_{t} \hat{f}(t)^{s\cdot t }\right)^{(-1)^{|s|+|x|}}
= f(\emptyset)^{\sum\limits_{s\leq x} (-1)^{|s|+|x|}}\prod\limits_{t}  \hat{f}(t)^{\sum\limits_{s\leq x} (s\cdot t)(-1)^{|s|+|x|}}$

We evaluate $\sum\limits_{s\leq x} (-1)^{|s|+|x|}$. If $x=\emptyset$ then $\sum\limits_{s\leq x} (-1)^{|s|+|x|}= 1 $, else there is a position $i$ with $x_i =1$, without loss of generality we assume that $i=0$. Then:

$\sum\limits_{s\leq x} (-1)^{|s|+|x|}=\sum\limits_{0s'\leq 1x'} (-1)^{|0s'|+|x|}+\sum\limits_{1s'\leq 1x'} (-1)^{|1s'|+|x|}= \sum\limits_{s'\leq x'} (-1)^{|s'|+|x|}-\sum\limits_{s'\leq x'} (-1)^{|s'|+|x|}=0$

Thus we have: $\sum\limits_{s\leq x} (-1)^{|s|+|x|}=\delta_{x=\emptyset}$.

We now evaluate $\sum\limits_{s\leq x} (s\cdot t)(-1)^{|s|+|x|}=\frac{1}{2}\sum\limits_{s\leq x} (-1)^{|s|+|x|} - \frac{1}{2} \sum\limits_{s\leq x}(-1)^{s\cdot t + |s|+|x|}=\frac{1}{2}\delta_{x=\emptyset}-\frac{1}{2}\sum\limits_{s\leq x}(-1)^{s\cdot t + |s|+|x|}$.

It remains to compute $\sum\limits_{s\leq x}(-1)^{s\cdot t + |s|+|x|}$. First if $x=\emptyset$ we get $ 1$. If $x\neq \emptyset$ and we don't have $x\leq t$ then there is a position $i$ such that $t_i = 0$ and $x_i =1 $, assuming without loss of generality that $i=0$ we get:

\begin{align*}
\sum\limits_{s\leq x}(-1)^{s\cdot t + |s|+|x|}&= \sum\limits_{0s'\leq 1x'}(-1)^{(0s')\cdot (0t') + |0s'|+|1x'|}+\sum\limits_{1s'\leq 1x'}(-1)^{(1s')\cdot (0t') + |1s'|+|1x'|}\\
&= \sum\limits_{s'\leq x'}(-1)^{s'\cdot t' + |s'|+|1x'|}-\sum\limits_{s'\leq x'}(-1)^{s'\cdot t' + |s'|+|1x'|}\\ &=0
\end{align*}

Else if we assume, without loss of generality, that $t_0 = 1$ and $x_0 =1$ we get:

\begin{align*}
\sum\limits_{s\leq x}(-1)^{s\cdot t + |s|+|x|}&= \sum\limits_{0s'\leq 1x'}(-1)^{(0s')\cdot (1t') + |0s'|+|1x'|}+\sum\limits_{1s'\leq 1x'}(-1)^{(1s')\cdot (1t') + |1s'|+|1x'|}\\
&=2\sum\limits_{s'\leq x'}(-1)^{s'\cdot t' + |s'|+|1x'|}
\end{align*}

Then, a quick induction gives us the final result $\sum\limits_{s\leq x}(-1)^{s\cdot t + |s|+|x|}= 2^{|x|}\delta_{x\leq t} $.

So finally:

$\tilde{f}(x)= f(\emptyset)^{\sum\limits_{s\leq x} (-1)^{|s|+|x|}}\prod\limits_{t}  \hat{f}(t)^{\sum\limits_{s\leq x} (s\cdot t)(-1)^{|s|+|x|}}
= f(\emptyset)^{\delta_{x=\emptyset}}\prod\limits_{t}  \hat{f}(t)^{\frac{1}{2}\delta_{x=\emptyset}}\prod\limits_{t\geq x}  \hat{f}(t)^{-2^{|x|-1}}
=\prod\limits_{t\geq x}  \hat{f}(t)^{-2^{|x|-1}}$

Since $\prod\limits_{t}  \hat{f}(t)^{\frac{1}{2}}=\prod\limits_{t}  \prod\limits_{x} f(x)^{-2^{-n}(-1)^{t\cdot x}}= \prod\limits_{x} f(x)^{-2^{-n}\sum\limits_{t} (-1)^{t\cdot x}}=\prod\limits_{x} f(x)^{-\delta_{0=x}}=f(\emptyset)^{-1}$.

Now starting with the expression of the Fourrier transform:

$\hat{f}(x)= \prod\limits_{t} f(t)^{-2^{1-n}(-1)^{x\cdot t}}
= \prod\limits_{t}  \left(\prod\limits_{s\leq t}\tilde{f}(s)\right)^{-2^{1-n}(-1)^{x\cdot t}}
= \prod\limits_{s}\tilde{f}(s)^{-2^{1-n}\sum\limits_{t\geq s}(-1)^{x\cdot t}} $

We evaluate $\sum\limits_{t\geq s}(-1)^{x\cdot t}$, if $x \geq t$ then:

$\sum\limits_{t\geq s}(-1)^{x\cdot t}= (-1)^{|x\cap s|}\sum\limits_{t' }(-1)^{(x\cap \overline{s})\cdot t'}= (-1)^{|x\cap s|} 2^{n-|s|}\delta_{x\cap \overline{s}=\emptyset}= (-1)^{|x|} 2^{n-|s|}\delta_{x\leq s}$

Finally: $\hat{f}(x)= \prod\limits_{s}\tilde{f}(s)^{-(-1)^{|x|} 2^{1-|s|}\delta_{x\leq s}} = \prod\limits_{s\geq x}\tilde{f}(s)^{-2^{1-|s|}(-1)^{|x|}}$.

We start by computing the Fourrier transform:

$\hat{f}(s)=\prod\limits_{t} f(t)^{-2^{1-n}(-1)^{s\cdot t}}=\prod\limits_{k=0}^n F(k)^{-2^{1-n}\sum\limits_{|s|=k}(-1)^{s\cdot t}}$.

By considering $j$, the number of ones in common between $x$ and $s$ we get:

$\sum\limits_{|s|=k}(-1)^{s\cdot x}=\sum\limits_{j=0}^{k}\binom{|x|}{j}\binom{n-|x|}{k-j}(-1)^j = K^n_k(|x|)$.

For the inversion formula : $F(m)=F(0)\prod\limits_{k=0}^n \hat{F}(k)^{\frac{1}{2}\left(\binom{n}{k}-\sum\limits_{|s|=k}(-1)^{s\cdot t}\right)}=F(0)\prod\limits_{k=0}^n \hat{F}(k)^{\frac{1}{2}\left(\binom{n}{k}-K^n_k(m)\right)}$.

Then using $F(0)^{-1}=\prod\limits_{k=0}^n \hat{F}(k)^{\frac{1}{2}\binom{n}{k}}$, we have: $F(m)=\prod\limits_{k=0}^n \hat{F}(k)^{\frac{-1}{2}K^n_k(m)}$.

Now, for the Mobius transform, we compute: $\tilde{f}(x)=\prod\limits_{s\leq x} f(s)^{(-1)^{|s|+ |x|}}=\prod\limits_{k=0}^{|x|}F(k)^{\binom{|x|}{k}(-1)^{|x|-k}}$.

And for the inversion formula, we get : $F(m)=\prod\limits_{s\leq x}\tilde{F}^{\binom{m}{k}}$.

We start with the identity :

Here we show that it can be derived by a direct application of the Mobius diagrammatical transforms. To do so, we compute the Mobius transform of a phase gadget acting on $n$ qubits with parameter $\lambda$. The associated semi-boolean function, $X_{n,\lambda}: x \mapsto \lambda^{\frac{1-(-1)^{|x|}}{2}} $, is obviously symmetric.

The binomial transform of $G: m \mapsto \lambda^{\frac{1-(-1)^{m}}{2}}$ is then:

\begin{align*}
\tilde{G}(m)&=\prod\limits_{k=0}^{m} G(k)^{\binom{m}{k} (-1)^{m-k}}=\prod\limits_{k=0}^{m} \lambda^{\frac{1-(-1)^{k}}{2} \binom{m}{k} (-1)^{m-k}}\\
&=\lambda^{\frac{1}{2}\left(\sum\limits_{k=0}^{m} \binom{m}{k} (-1)^{m-k} - \sum\limits_{k=0}^{m} \binom{m}{k} (-1)^{m-k}(-1)^{k}\right)}=\lambda^{\frac{\delta_{m=0}-(-2)^{m}}{2}}=\lambda^{\delta_{m\neq0}(-2)^{m-1}}.
\end{align*}

Then, setting $\lambda= e^{\frac{i\pi}{4}}$ we get $\tilde{G}(0)=1$, so we have no floating scalars and also $\tilde{G}(m)=1$ for $m\geq 4$. The only non trivial terms are $\tilde{G}(1)=e^{\frac{i\pi}{4}}$, $\tilde{G}(2)=-i$ and $\tilde{G}(3)=-1$, directly giving the expected decomposition.

We can compute the transform of the phase function $H(m)\df \beta\delta_{m=n}$ which corresponds to the generalized hyper-edges on $n$ qubits with phase $\beta$ :

Combining this result with the previous spider-nest identity, it is possible to derive the spider-nest identity from [6] as it is done in [25]. However, we will here provide an alternative proof by inversion of the second identity.

We first sketch the general method to check such spider-nest identity. We want to show that for a symmetric phase function $\hat{s}:\textbf{2}^n \to \mathbb{R}$:

We know $\hat{S}$ by reading the coefficients in the phase gadgets. We compute $S$ using the inversion formula. Then we check if $S$ is constant. If this is the case, this means that the corresponding phase gadget is $S(0)I_n$. But this scalar is exactly the one appearing in the graphical Fourier transform. So simplifying on both sides gives us exactly what we want.

We apply this method to our specific case. Here, only the Kravchuk polynomials for $k=0,1,2,3$ and $n$ are needed:

$K^n_2(m)=2m^2 -2nm+\frac{n^2 -n}{2}$   $K^n_n(m)=(-1)^m$

4c$K^n_3(m)=-\frac{4}{3}m^3 +2nm^2  +(-n^2 +n -\frac{2}{3})m+\frac{n^3 - 3n^2 + 2n}{6}$

We want to inverse the phase function:

$\hat{S}(0)=1$ $\hat{S}(1)=e^{\frac{i\pi(n-2)(n-3)}{16}}$ $\hat{S}(2)=e^{\frac{-i\pi(n-3)}{8}}$ $\hat{S}(3)=e^{\frac{i\pi}{8}}$ $\hat{S}(n)=e^{\frac{-i\pi}{8}}$  $\hat{S}(k)=1$ for $ k\neq 0,1,2,3,n$.

and show that forall $m\in \interp{0,n}$, $S(m)= S(0)\mod 2$. The inversion formula gives us:

\begin{align*}
&=e^{i\pi\left(\frac{m^3}{12} -\frac{3m^2}{8} +\frac{5m}{12}- \frac{n^3}{96}+\frac{n^2}{16}-\frac{11n}{96} +\frac{(-1)^m}{16}\right)}
\end{align*}

Our goal is to check that $S$ is constant. Thus, we only need the part of the exponent that depends on $m$.

$E(m)\df\frac{m^3}{12} -\frac{3m^2}{8} +\frac{5m}{12}+\frac{(-1)^m}{16}$.

Since $E(0)=\frac{1}{16} \mod 2$, we want to check that for each $m\in \mathbb{N}$, $E(m)\equiv \frac{1}{16} \mod 2$. To do so we write $m=24k+l$ with $k\in \mathbb{N}$ and $l\in \interp{0,23}$.
We obtain:

$E(24k+l)=1152k^3 + 144lk^2 - 216k^2 + 6kl^2 - 18kl +10k+ \frac{l^3}{12} -\frac{3l^2}{8}+\frac{5l}{12}+\frac{(-1)^{l}}{16}$

We see that $E(24k+l) = \frac{l^3}{12} -\frac{3l^2}{8}+\frac{5l}{12}+\frac{(-1)^{l}}{16} \mod 2$, this only depends on $l$. Thus we can just check that for each $l\in \interp{0,23}$, $\frac{l^3}{12} -\frac{3l^2}{8}+\frac{5l}{12}+\frac{(-1)^{l}}{16}= \frac{1}{16} \mod 2$  (which is true).

We define $\Lambda(s)= \begin{cases}
\lambda_i \text{ if } \exists i,\quad s=\overrightarrow{\{i\}}	\\
1 \text{ else}
\end{cases}$, we then have: $\mu_s = \prod\limits_{t\geq s}  \Lambda(t)^{-2^{|s|-1}}$.