11institutetext: Department of Mathematics and Statistics, Masaryk University
Kotlářská 2, 611 37 Brno, Czech Republic
11email<EMAIL_ADDRESS><EMAIL_ADDRESS>
# Well Quasi-Orders Arising from Finite
Ordered Semigroups ††thanks: The research was supported by Grant 19-12790S of
the Grant Agency of the Czech Republic.

Ondřej Klíma  Jonatan Kolegar

###### Abstract

In 1985, Bucher, Ehrenfeucht and Haussler studied derivation relations
associated with a given set of context-free rules. Their research motivated a
question regarding homomorphisms from the semigroup of all words onto a finite
ordered semigroup. The question is which of these homomorphisms induce a well
quasi-order on the set of all words. We show that this problem is decidable
and the answer does not depend on the homomorphism, but it is a property of
the ordered semigroup.

###### Keywords:

finite semigroups well quasi-order unavoidable words

##  1 Introduction

The notion of well quasi-order (wqo) is a well-established tool in mathematics
and in many areas of theoretical computer science that was rediscovered by
many authors (see [7] by Kruskal). A comprehensive overview of the
applications of the notion in theory of formal languages and combinatorics on
words can be found in the book [9] by de Luca and Varricchio or in the survey
paper [2] by D’Alessandro and Varricchio. Since our contribution belongs to
formal language theory, we recall the central notion of wqo directly for the
set of all words over a finite alphabet $A$. A quasi-order $\leq$ on a set
$A^{*}$ is wqo if it has no infinite antichains and no decreasing infinite
chain (the latter property is often called _well-foundness_). There are
several equivalent conditions of the notion (see, _e.g._ , [9, Theorem
6.1.1]); among them we recall the following: for every infinite sequence of
words $w_{1},w_{2},\dots$ there exist integers $0<i<j$ such that $w_{i}\leq
w_{j}$. We point out that the important property which makes the notion of wqo
a useful tool is that every upper closed subset of $A^{*}$ with respect to a
wqo $\leq$ is a regular language (see [9, Theorem 6.3.1]).

The first example of wqo in the area of formal languages was given by Higman
[5]. We mention the simplest consequence of the general statement, namely the
result that the _embedding_ relation $\unlhd$ on $A^{*}$ is wqo. The embedding
relation $\unlhd$ is often called subword ordering, because a word $u$
_embeds_ in a word $v$ if $u$ is a scattered subword of $v$, _i.e._ , $u\unlhd
v$ if there are factorizations of the same length $u=a_{1}\dots a_{k}$ and
$v=v_{1}\dots v_{k}$ such that, for all $i\in\\{1,\dots,k\\}$, we have
$a_{i}\in A$, $v_{i}\in A^{+}$, and $a_{i}$ appears in $v_{i}$.

The considered notion of embedding relation can be modified by requiring
different conditions on the factorizations. For example, if the alphabet $A$
is quasi-ordered by $\preceq$, then we may replace the condition that $a_{i}$
appears in $v_{i}$ by the condition that there is $j$ such that $a_{i}\preceq
a_{j}$ and $a_{j}$ appears in $v_{i}$. In this way we obtain a quasi-order
which is a well known (and more general) instance of Higman result. Another
variant is the following _gap embedding_ considered by Schütte and S. G.
Simpson in [13] for an alphabet equipped by linear order $\sqsubseteq$: the
defining condition that $a_{i}$ appears in $v_{i}$ is replaced by the
condition that the letter $a_{i}$ is the last letter in $v_{i}$ and it is a
minimal letter in $v_{i}$ with respect to $\sqsubseteq$. Notice that yet
another modification of gap embedding is the _priority embedding_ in [4] by
Haase, Schmitz, and Schnoebelen.

Our paper concentrates on an application of wqos motivated by the work of
Bucher, Ehrenfeucht and Haussler [1], which leads to a purely algebraic
question in the realm of ordered semigroups. Notice that the topic is nicely
overviewed in the recent survey paper [12] by Pin.

Before we introduce the primary question, we briefly recall the role of
ordered semigroups in the algebraic theory of regular languages. At first,
when we talk about an ordered semigroup $(S,\cdot,\leq)$, we assume that the
partial order $\leq$ is stable, i.e., compatible with the multiplication
$\cdot$ in the sense that, for arbitrary $x,y,s\in S$, the inequality $x\leq
y$ implies both $s\cdot x\leq s\cdot y$ and $x\cdot s\leq y\cdot s$. The
finite ordered semigroups are used to recognize regular languages similarly to
unordered semigroups – see, e.g., the fundamental survey on the algebraic
theory of regular languages [11] by Pin. The modification is natural as the
syntactic semigroup of a regular language is implicitly ordered in the
following way. In the syntactic congruence of the regular language, words are
related if they have the same set of contexts putting the words into the
language. Then one may also compare these sets of contexts by the inclusion
relation; this comparison gives the syntactic quasi-order and consequently the
partial order on the syntactic semigroup of the considered regular language.
Let us note that in the literature the syntactic quasi-order is not always
defined in this way, but the dual quasi-order is considered instead, e.g., in
[11].

The starting point in the study of well quasi-orders in [1] was a research by
Ehrenfeucht, Haussler, and Rozenberg [3] concerning certain rewriting systems
preserving regularity, where a well quasi-order plays a role of a sufficient
condition guaranteeing the required property of the rewriting system.
Particular attention in that research is paid to rewriting systems $R$ with
rules of the form $a\rightarrow u$ with $a$ being a letter and $u$ being a
word. For such a rewriting system, in [1], there are stated equivalent
conditions to the fact that the derivation relation $\ext@arrow
0359\Rightarrowfill@{}{*}_{R}$ is a well quasi-order. For example, one of the
equivalent conditions is that the set $L=\\{aua\mid a\in A,u\in
A^{*},a\ext@arrow 0359\Rightarrowfill@{}{*}_{R}aua\\}$ is unavoidable (in the
sense that every infinite word over the alphabet $A$ contains a finite factor
from the language $L$). Unfortunately, they did not give algorithms to test
the conditions. They also showed that a derivation relation that is a wqo
comes from a rewriting system induced by a semigroup homomorphism
$\sigma:A^{+}\rightarrow S$ onto a finite ordered semigroup $(S,\cdot,\leq)$
by the following formula:

$R_{\sigma}=\\{a\rightarrow u\mid a\in A,u\in
A^{+},\sigma(a)\leq\sigma(u)\\}.$

Finally, the open question is to characterize homomorphisms $\sigma$ such that
$\ext@arrow 0359\Rightarrowfill@{}{*}_{R_{\sigma}}$ is a well quasi-order.
Another research goal is a characterization of those finite ordered semigroups
$S$, such that the relation $\ext@arrow
0359\Rightarrowfill@{}{*}_{R_{\sigma}}$ is a wqo for every alphabet $A$ and a
homomorphism $\sigma:A^{+}\rightarrow S$. For the purpose of this paper we
call these ordered semigroups _congenial_.

Let us note that the examples of wqo mentioned earlier also fit to the
introduced scheme of relations arising from a homomorphism onto a finite
ordered semigroup. Indeed, for an alphabet $A$ we may consider an ordered
semigroup $(P(A),\cup,\subseteq)$ consisting of non-empty subsets of $A$
equipped with the operation of union, and ordered by the inclusion relation.
Taking then the homomorphism $\sigma:A^{+}\rightarrow P(A)$, where
$\sigma(a)=\\{a\\}$, the above considered relation $\ext@arrow
0359\Rightarrowfill@{}{*}_{R_{\sigma}}$ coincides with the embedding relation
$\unlhd$. Similarly, we can consider an appropriate homomorphism onto an
ordered semigroup in the other mentioned examples.111For a variant of Higman’s
Lemma where the alphabet $A$ is equipped with the quasi-order $\preceq$, we
take for the ordered semigroup $S$ the subsemigroup of $P(A)$ consisting of
all downward closed subsets of $A$ with respect to the considered quasi-order
$\preceq$. For the gap embedding, one may construct the semigroup $A\times A$
(ordered by equality), where the multiplication is given by
$(a,b)\cdot(c,d)=(min(a,c),d)$, where $min$ is taken with respect to
$\sqsubseteq$ (and the homomorphism $\sigma\colon A\to A\times A$ is the
diagonal mapping).

Up to our knowledge, and also according to the survey paper [12], there is
just one significant contribution to the mentioned open questions. Namely, in
the paper [8] by Kunc, the questions are solved for the semigroups ordered by
the equality relation. It is stated in [8] (implicitly contained in the proof
of Theorem 10) that the property depends only on the semigroup $S$, not on the
actual homomorphism $\sigma$. The congenial semigroups ordered by the equality
relation are characterized as finite chains of finite simple semigroups. One
of the equivalent characterizations of this transparent structural property is
the following condition which can be checked in polynomial time: for every
$s,t\in S$, we have $(s\cdot t)^{\omega}\cdot s=s$ or $t\cdot(s\cdot
t)^{\omega}=t$, where $(s\cdot t)^{\omega}$ is the power of $s\cdot t$ which
is idempotent.

Our research aims to give an analogous characterization in the general case;
however, we do not fulfill that program yet, and our contribution brings
tentative results. As the main result, we show that the problem of whether a
homomorphism induces a well quasi-order is decidable. The proof is almost a
straightforward application of the mentioned characterization from [1].
Furthermore, we give some necessary conditions related to the studied
property, and, on the other hand, we establish other conditions which ensure
the property. Next, we show that the mentioned side result from [8] holds in
the full generality: the property is indeed a property of an ordered semigroup
and does not depend on the homomorphism.

The proofs of results marked by the symbol $\spadesuit$ are available in
Appendix.

##  2 Preliminaries

We briefly recall basic notions and fix notation used in the paper. We start
with that from semigroup theory. When we talk about ordered semigroup or
semigroup, we write simply $S$ instead of formal notation $(S,\cdot,\leq)$ and
$(S,\cdot)$. Throughout the paper we work with finite semigroups with the
exception of the free monoid $A^{*}$ (the free semigroup $A^{+}$) formed by
(non-empty) words over an alphabet $A$. We use the symbol $\varepsilon$ for
the empty word. An element $e$ in a semigroup $S$ is called _idempotent_ if
$e\cdot e=e$. For all $s\in S$, the set $\\{s^{n}\,|\,n\in\mathbb{N}\\}$
contains exactly one idempotent, which is denoted $s^{\omega}$. We put
$s^{\omega+1}=s^{\omega}\cdot s$ which equals (by definition) to $s\cdot
s^{\omega}$. By $S^{1}$ we mean the monoid $S\cup\\{1\\}$ with a new neutral
element $1$ added when $S$ is not a monoid and $S^{1}=S$ otherwise. We denote
$\operatorname{eval}_{S}\colon S^{+}\to S$ the evaluation homomorphism from
the free semigroup over $S$ defined by the rule $\operatorname{eval}_{S}(s)=s$
for all $s\in S$. Here, an element $w\in S^{+}$ is a word $w=s_{1}s_{2}\dots
s_{k}$, where $s_{i}\in S$ for $i\in\\{1,\dots,k\\}$, and for such $w$ we have
$\operatorname{eval}_{S}(w)=\operatorname{eval}_{S}(s_{1}s_{2}\dots
s_{k})=s_{1}\cdot s_{2}\cdots s_{k}$.

Furthermore, we use the Green relations, a basic notion in the theory of
semigroups (see [6] by Howie). For the reader’s convenience we recall that an
ideal of a semigroup $S$ is a non-empty subset $I\subseteq S$ such that for
all $t\in I$ and $s\in S$ we have $t\cdot s\in I$ and $s\cdot t\in I$. The
ideal generated by an element $s\in S$ is equal to $S^{1}sS^{1}=\\{x\cdot
s\cdot y\,|\,x,y\in S^{1}\\}$. Then the Green relation $\mathscr{J}$ is
defined by the rule $s\,\mathscr{J}\,t\Longleftrightarrow
S^{1}sS^{1}=S^{1}tS^{1}$. We say that a semigroup is simple if it has no
proper ideal, i.e., if all elements of the semigroup are
$\mathscr{J}$-equivalent.

The following lemma is well known (see, e.g., [10, Theorem 1.11] by Pin).

###### Lemma 1

Let $S$ be a finite semigroup. There exists $n\in\mathbb{N}$ such that for
every sequence of elements $s_{1},\dots,s_{n}\in S$ there are indices
$i,j\in\\{1,\dots,n\\},i\leq j$ for which the product $s_{i}\cdot
s_{i+1}\cdots s_{j}$ is an idempotent.

For words $w,x,y,z\in A^{*}$ such that $w=xyz$, we say that $x$ is a _prefix_
, $y$ is a _factor_ and $z$ is a _suffix_. We say that the prefix $x$ of $w$
is proper if $|x|<|w|$, where $|w|$ is the length of the word $w$. A language
$L\subseteq A^{*}$ is unavoidable if an arbitrary infinite word $u$ over $A$
has a factor $v$ in $L$. We denote the set of all infinite words over $A$ by
$A^{\infty}$.

A quasi-order $\leq$ on a set $X$ is a reflexive and transitive binary
relation. It is called a well quasi-order (wqo) if for an infinite sequence
$(x_{n})_{n\in\mathbb{N}}$ of elements of $X$ there exist indices
$m,n\in\mathbb{N}$ such that $m<n$ and $x_{m}\leq x_{n}$. Many equivalent
defining conditions are known (see, e.g., [9, Theorem 6.1.1]).

The next definition is partially motivated by results from [1]. We prefer to
follow the formalism and notation used in [8].

###### Definition 1

Let $\sigma\colon A^{+}\to S$ be a homomorphism onto a finite ordered
semigroup. We denote $\leq_{\sigma}$ a quasi-order on $A^{*}$ defined by
setting $u\leq_{\sigma}v$ if and only if there exist factorizations
$u=a_{1}\dots a_{n}$ and $v=v_{1}\dots v_{n}$, such that for all
$i\in\\{1,\dots,n\\}$ we have $a_{i}\in A,v_{i}\in A^{+}$ and
$\sigma(a_{i})\leq\sigma(v_{i})$.

We refer to the list of inequalities $\sigma(a_{j})\leq\sigma(v_{j})$ for
$j\in\\{1,\dots,n\\}$ as to the proof of $u\leq_{\sigma}v$, and we can use the
proof to form other inequalities. We say that $a_{i}\dots
a_{j}\leq_{\sigma}v_{i}\dots v_{j}$ is the consequence of the proof given by
the factor $a_{i}\dots a_{j}$. Note that $u\leq_{\sigma}v$ implies
$\sigma(u)\leq\sigma(v)$ and either $u=v=\varepsilon$ or $u,v\in A^{+}$.
Finally, it is clear that $\leq_{\sigma}$ is a stable quasi-order on $A^{*}$.

The main result from [1] has the following natural interpretation. To see it,
one needs other results [1, Section 3] concerning rewriting systems of the
form mentioned in the introduction (called OS scheme in [1]). If the relation
$\ext@arrow 0359\Rightarrowfill@{}{*}_{R}$ with rules of the form
$a\rightarrow u,a\in A,u\in A^{+}$ is a wqo, then there is a homomorphism
$\sigma:A^{+}\rightarrow S$ onto a finite ordered semigroup such that the
relations $\ext@arrow 0359\Rightarrowfill@{}{*}_{R}$ and $\leq_{\sigma}$
coincide. And vice versa, if $\leq_{\sigma}$ is a wqo, then there is a system
$R$ with the property $\ext@arrow 0359\Rightarrowfill@{}{*}_{R}\ =\
\leq_{\sigma}$.

######  Proposition 1 ([1])

Let $\sigma\colon A^{+}\to S$ be a homomorphism onto a finite ordered
semigroup. Then the following conditions are equivalent:

  1. 1.

The relation $\leq_{\sigma}$ is a well quasi-order on $A^{*}$.

  2. 2.

The language $L_{\sigma}=\\{awa\,|\,a\in A,w\in A^{*},a\leq_{\sigma}awa\\}$ is
unavoidable over $A$.

  3. 3.

The language $\\{aw\,|\,a\in A,w\in A^{*},a\leq_{\sigma}aw\\}$ is unavoidable
over $A$.

We say that an ordered semigroup $S$ is congenial if for every homomorphism
$\sigma\colon A^{+}\to S$ the corresponding relation $\leq_{\sigma}$ is a well
quasi-order. The class of congenial semigroups is denoted $\mathcal{C}$.

We finish this section with a basic observation that it is enough to consider
the case of the homomorphism $\operatorname{eval}_{S}$ when a congeniality of
$S$ is tested. We establish the following auxiliary lemma with the proof
essentially same as to the unordered case (see [8, Theorem 10,
(iii)$\Longrightarrow$(i)]).

###### Lemma 2

Let $\sigma\colon A^{+}\rightarrow S$ be a homomorphism to an ordered
semigroup $S$ such that $\leq_{\sigma}$ is a wqo. Let $B$ be an alphabet,
$\alpha:B^{+}\rightarrow A^{+}$ be a homomorphism of free semigroups such that
$\alpha(B)\subseteq A$, and $\varphi=\sigma\circ\alpha$. Then the quasi-order
$\leq_{\varphi}$ is a wqo. $\spadesuit$

The following statement is a direct consequence of Lemma 2, where we take
$A=S$ and $\sigma=\operatorname{eval}_{S}$.

###### Lemma 3

A semigroup $S$ is congenial if and only if $\leq_{\operatorname{eval}_{S}}$
is a wqo. $\spadesuit$

##  3 What Makes an Ordered Semigroup Congenial

Due to [8, Lemma 2], we know that a semigroup $S$ ordered by equality is
congenial if and only if for every $s,t\in S$ either $s=(s\cdot
t)^{\omega}\cdot s\text{ or }t=t\cdot(s\cdot t)^{\omega}.$ The natural
generalization of this condition for an ordered semigroup $S$ is

$\forall s,t\in S\colon s\leq(s\cdot t)^{\omega}\cdot s\text{ or }t\leq
t\cdot(s\cdot t)^{\omega}.$ (1)

We show that this condition is indeed necessary. Note that a semigroup
satisfying (1) also satisfies $s\leq s^{\omega+1}$ as it is just the condition
(1) with $s=t$.

###### Proposition 2

Every congenial semigroup satisfies the condition (1). $\spadesuit$

Note that for the condition $s\leq s^{\omega+1}$ leaving the realm of ordered
semigroups we get the equality $s=s^{\omega+1}$ defining the widely studied
class of finite completely regular semigroups.

The following example shows that the condition (1) is not a sufficient
condition. It indicates that the ordered situation is more complicated.

###### Example 1

Denote $\mathcal{F}_{LRB}(3)$ the free left-regular band (i.e., semigroup
satisfying the identities $xyx=xy$ and $x^{2}=x$) over three generators
$a,b,c$. The semigroup has 15 elements represented by words listed in Fig. 1,
where the order is depicted.

$\textstyle{acb\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{bac\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{cba\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{ac\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{abc\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{ba\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{bca\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{cb\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{cab\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{a}$$\textstyle{ab}$$\textstyle{b}$$\textstyle{bc}$$\textstyle{c}$$\textstyle{ca}$
Figure 1: The order $\leq$ of $\mathcal{F}_{LRB}(3)$.

For the product of a pair of elements, we simply concatenate the words and
then omit the second occurrence of each letter if it occurs. It is a routine
to check that $\mathcal{F}_{LRB}(3)$ satisfies the condition (1).

Now we take $\sigma\colon\\{a,b,c\\}^{+}\to\mathcal{F}_{LRB}(3)$ where
$\sigma(a)=a,\sigma(b)=b,\sigma(c)=c$. For the language $L_{\sigma}$ given by
Proposition 1, we see that $u\in L_{\sigma}$ if and only if
$\sigma(u)\in\\{a,ac,acb,b,ba,bac,c,cb,cba\\}$. The periodical infinite word
generated by $abc$, that is $(abc)^{\infty}=abcabc\dots$, has no factor in the
language $L_{\sigma}$ since $\sigma((abc)^{n}a)=abc$ (for $n\in\mathbb{N}$)
and similarly for factors starting and ending with $b$, resp. $c$. This means
that the language $L_{\sigma}$ is avoidable and
$\mathcal{F}_{LRB}(3)\notin\mathcal{C}$. Therefore, the condition (1) is not
the characterization of the class of congenial semigroups.

We also add an example of ordered semigroup which is not completely regular.

###### Example 2

We consider two ordered versions $B_{2}^{+}$ and $B_{2}^{-}$ of the Brandt
semigroup $B_{2}$. The semigroup is generated by two elements $a$ and $b$
satisfying $a^{2}=0$, $b^{2}=0$, $aba=a$, and $bab=b$. The semigroup has five
elements $a$, $b$, $ab$, $ba$, and $0$, where $ab,ba,0$ are idempotents. The
orders are given in Fig. 2.

$\textstyle{a\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{ab\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{ba\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{b\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{0}$$\textstyle{B_{2}^{+}:}$$\textstyle{B_{2}^{-}:}$$\textstyle{0}$$\textstyle{b\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{ba\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{ab\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{a\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$
Figure 2: Orders of $B_{2}^{+}$ and $B_{2}^{-}$.

In both cases we consider a homomorphism $\sigma\colon\\{a,b\\}^{+}\to B_{2},$
where $\sigma(a)=a,\,\sigma(b)=b$.

Firstly, we deal with $B_{2}^{+}$. Taking the sequence of words
$(a^{i})_{i\in\mathbb{N}}$, we get an infinite antichain with respect to
$\leq_{\sigma}$ showing that $\leq_{\sigma}$ is not a wqo and thus
$B_{2}^{+}\notin\mathcal{C}$. For the ordered semigroup $B_{2}^{-}$, we see
that $a\leq a^{2}=0,b\leq b^{2}=0$, and $a=aba$, and so $a^{2},b^{2},aba\in
L_{\sigma}$ for $L_{\sigma}$ from Proposition 1. The language
$\\{a^{2},aba,b^{2}\\}$ is unavoidable, which implies
$B_{2}^{-}\in\mathcal{C}$.

Motivated by the previous examples and basic observations, we show the first
sufficient condition ensuring the congeniality.

###### Proposition 3

Let $S$ be a finite ordered semigroup satisfying the inequality $x\leq
x\cdot(y\cdot x)^{\omega}$. Then $S$ is congenial.

###### Proof

Let $\sigma:A^{+}\rightarrow S$ be an arbitrary homomorphism. We show that the
language $L_{\sigma}=\\{awa\,|\,a\in A,w\in A^{*},\sigma(a)\leq\sigma(awa)\\}$
from Proposition 1 is unavoidable. Let $v$ be an infinite word over the
alphabet $A$. Since the alphabet is finite, some letter $a\in A$ has
infinitely many occurrences in $v$. We consider the factorization
$v=w_{0}aw_{1}aw_{2}aw_{3}\dots$, where the words $w_{i}$ do not contain the
letter $a$. We take the sequence
$s_{1}=\sigma(w_{1}a),s_{2}=\sigma(w_{2}a),\dots$ and use Lemma 1 to show that
there exist indices $i,j$ such that $\sigma(w_{i}a\dots w_{j}a)$ is an
idempotent. If we denote $x=\sigma(a)$, $y=\sigma(w_{i}a\dots w_{j})$, then we
get $y\cdot x=(y\cdot x)^{\omega}$ and $x\leq x\cdot(y\cdot x)^{\omega}=x\cdot
y\cdot x$. Therefore $a\leq_{\sigma}aw_{i}a\dots w_{j}a$ and the infinite word
$v$ has a factor in $L_{\sigma}$. ∎

Natural examples of ordered semigroups satisfying the assumption in the
previous statement can be found in Appendix.

##  4 Effective Characterization of the Class $\mathcal{C}$

In order to check the condition in Proposition 1, we introduce some technical
notation. Let $A$ be an alphabet, and $w\in A^{+}$ be a word. Then we write
${f(w)}$ for the first letter in $w$, i.e., the letter $a$ such that $w\in
aA^{*}$. Dually, ${\ell(w)}$ means the last letter in the word $w$. Moreover,
we denote the set of all factors and suffixes of a given word in a usual way
with an exception that we do not consider letters as factors and suffixes
here:

${Fac(w)}=\\{u\in A^{+}\setminus A\mid\exists p,q\in
A^{*},w=puq\\},\quad\text{and}$ ${Suf(w)}=\\{u\in A^{+}\setminus A\mid\exists
p\in A^{*},w=pu\\}.$

Now, let $\sigma:A^{+}\rightarrow S$ be a homomorphism onto a finite ordered
semigroup. We introduce the main technical notation: for $w\in A^{+}$ we put

${Fac_{\sigma}(w)}=\\{\left(\sigma(u),{f(u)},{\ell(u)}\right)\in S\times
A\times A\mid u\in{Fac(w)}\\},\quad\text{and}$
${Suf_{\sigma}(w)}=\\{(\sigma(u),{f(u)},{\ell(u)})\in S\times A\times A\mid
u\in{Suf(w)}\\}.$

Notice that ${Fac_{\sigma}(w)}={Suf_{\sigma}(w)}={Fac(w)}={Suf(w)}=\emptyset$
whenever $w\in A$. Furthermore, ${Suf_{\sigma}(w)}\subseteq S\times
A\times\\{{\ell(w)}\\}$ for every word $w$, that is a useful property
motivating the following definition. A non-empty subset $M$ of the set
$S\times A\times A$ is called _coherent_ if there is a letter $a\in A$ such
that $M\subseteq S\times A\times\\{a\\}$; if such a letter exists, we denote
it by ${\ell(M)}$.

Clearly, $w\in A^{+}$ does not avoid $L_{\sigma}=\\{ava\mid a\in A,v\in
A^{*},a\leq_{\sigma}ava\\}$ if and only if there exist
$w^{\prime},v,w^{\prime\prime}\in A^{*}$ such that
$w=w^{\prime}avaw^{\prime\prime}$ and $\sigma(a)\leq\sigma(ava)$. The latter
condition is equivalent to $(\sigma(ava),a,a)\in{Fac_{\sigma}(w)}$ with
$\sigma(a)\leq\sigma(ava)$. In other words, a word $w\in A^{+}$ avoids the set
$L_{\sigma}$ if and only if ${Fac_{\sigma}(w)}$ is disjoint with the set
$F=\\{(s,a,a)\in S\times A\times A\mid\sigma(a)\leq s\\}.$ Now, we are ready
to formulate a direct consequence of Proposition 1.

###### Lemma 4

Let $\sigma:A^{+}\rightarrow S$ be a homomorphism onto a finite ordered
semigroup $S$. Then the relation $\leq_{\sigma}$ is a well quasi-order if and
only if the set $\\{w\in A^{+}\setminus A\mid{Fac_{\sigma}(w)}\cap
F=\emptyset\\}$ is finite. ∎

To test whether the considered set is finite, we use that every
${Fac_{\sigma}(w)}$ is a subset of $S\times A\times A$, and therefore there
are only finitely many of them. In fact, we compute all possible
${Suf_{\sigma}(w)}$ disjoint with $F$ instead of computing all
${Fac_{\sigma}(w)}$. It is enough as ${Fac_{\sigma}(w)}$ is a union of all
${Suf_{\sigma}(u)}$ where $u$ is a prefix of $w$. Naturally, we compute sets
${Suf_{\sigma}(u)}$ recursively, since ${Suf_{\sigma}(wa)}$ can be determined
by ${Suf_{\sigma}(w)}$ in the following way. Informally speaking, we add $a$
at the end of all elements of ${Suf_{\sigma}(w)}$ and evaluate the suffix
${\ell({Suf_{\sigma}(w)})}a$ of $wa$ of length two. Therefore, we see the sets
${Suf_{\sigma}(w)}$ as states of the following finite deterministic incomplete
automaton $\mathcal{A}_{\sigma}$ over the alphabet $A$. Notice that the
automaton does not have final states.

We put $\mathcal{A}_{\sigma}=(Q,A,\delta,\iota)$ where
$Q=\\{\iota\\}\uplus\bar{A}\uplus\mathcal{P}$, $\bar{A}=\\{\bar{a}\,|\,a\in
A\\}$, and $\mathcal{P}=\\{M\subseteq S\times A\times
A\,|\,M\neq\emptyset,M\cap F=\emptyset,M\ \text{coherent}\\}$. For a given set
$M\in\mathcal{P}$ and a letter $a\in A$ we define

$M\ast a=\\{(s\cdot\sigma(a),b,a)\,|\,(s,b,c)\in
M\\}\cup\\{(\sigma(\ell(M)a),\ell(M),a)\\}.$

Similarly, for $\bar{b}\in\bar{A}$ we put $\bar{b}\ast
a=\\{(\sigma(ba),b,a))\\}$. Furthermore, we define the partial transition
function $\delta:Q\times A\rightarrow Q$ by $\delta(\iota,a)=\bar{a}$ for the
initial state $\iota$, and for $q\in Q\setminus\\{\iota\\}$ we put
$\delta(q,a)=q\ast a$ if $q\ast a\in\mathcal{P}$. Note that the condition
$q\ast a\in\mathcal{P}$ is equivalent to $q\ast a\cap F=\emptyset$ since
$q\ast a$ is always non-empty and coherent. In particular, we have $\ell(q\ast
a)=a$. As usual, the partial function $\delta$ can be extended to the partial
function $\delta:Q\times A^{+}\rightarrow Q$, which is denoted by $\delta$
too.

The following lemma summarises the properties of the previous constructions,
with an obvious proof by an induction with respect to the length of words.

###### Lemma 5

Let $\sigma:A^{+}\rightarrow S$ be a homomorphism onto a finite ordered
semigroup $S$, and $\mathcal{A}_{\sigma}$ be the automaton defined as above.
For every word $w\in A^{+}\setminus A$, the state $\delta(\iota,w)$ is defined
in $\mathcal{A}_{\sigma}$ if and only if ${Fac_{\sigma}(w)}\cap F=\emptyset$.
Moreover, if $\delta(\iota,w)$ is defined, then
$\delta(\iota,w)={Suf_{\sigma}(w)}$. ∎

Now, we are ready to state the main result. The proof is straightforward
consequence of Propositon 1 and the constructions and lemmas in this section.

###### Theorem 4.1

Let $\sigma:A^{+}\rightarrow S$ be a homomorphism onto a finite ordered
semigroup $S$. Then $\leq_{\sigma}$ is a wqo if and only if the automaton
$\mathcal{A}_{\sigma}$ does not contain an infinite path starting in the
initial state $\iota$. $\spadesuit$

The reader may look into Appendix for an illustrative example of the
construction of $\mathcal{A}_{\sigma}$. The purpose of Theorem 4.1 is the
following statement.

###### Corollary 1

Let $\sigma:A^{+}\rightarrow S$ be a homomorphism onto a finite ordered
semigroup $S$. Then it is decidable whether $\leq_{\sigma}$ is a well quasi-
order. ∎

Recall that all states in $\mathcal{P}$ are coherent subsets of $S\times
A\times A$. Since the automaton $\mathcal{A}_{\sigma}$ is finite, the
existence of an infinite path starting in the initial state $\iota$ is
equivalent to the existence of a loop reachable from $\iota$. If we assume
that there is a loop labeled by $u$ and reachable by $v$, then we have that
$vu^{\infty}=vuuu\dots$ avoids $L_{\sigma}$. Hence the periodical infinite
word $u^{\infty}$ avoids $L_{\sigma}$ too.

###### Corollary 2

Let $\sigma:A^{+}\rightarrow S$ be a homomorphism onto a finite ordered
semigroup $S$. Then there is an infinite word avoiding $L_{\sigma}$ if and
only if there is a periodic infinite word $u^{\infty}$ with that property. ∎

The number of states of the automaton $\mathcal{A}_{\sigma}$ is bounded by
$|A|\times 2^{|S|\times|A|}+|A|+1$, that gives the obvious exponential bound
for the time complexity of the algorithm based on Theorem 4.1.

One may modify the construction of $\mathcal{A}_{\sigma}$ if the condition (3)
from Proposition 1 replaces the condition (2). This means that Corollary 2
holds if we take the set $\\{aw\,|\,a\in A,w\in
A^{+},\sigma(a)\leq\sigma(aw)\\}$ instead of the set $L_{\sigma}$.

##  5 Other Necessary and Sufficient Conditions

The motivation for this section is to examine whether the condition that
$\leq_{\sigma}$ is a wqo depends on the homomorphism $\sigma$ or it is just a
property of the semigroup. Therefore, we try to prove necessary conditions
from Section 3 under the assumption that $\leq_{\sigma}$ is a wqo.

###### Proposition 4

Let $\sigma:A^{+}\rightarrow S$ be a homomorphism onto a finite ordered
semigroup $S$ such that $\leq_{\sigma}$ is a wqo. Then for every $u\in A^{+}$
there exists an integer $p>1$ such that $u\leq_{\sigma}u^{p}$.

###### Proof

We show the statement by induction with respect to the length of the word $u$.
For every $a\in A$ the definition of wqo implies that
$a^{k}\leq_{\sigma}a^{\ell}$ for some integers $k<\ell$, and by the definition
of $\leq_{\sigma}$ we have $a\leq_{\sigma}a^{p}$ for some $p>1$.

Assume that the statement is true for all words shorter than a given word
$u\in A^{+}\setminus A$. Similarly to the initial step, we have
$u^{k}\leq_{\sigma}u^{\ell}$ for some $k<\ell$. We consider the consequences
of the proof of $u^{k}\leq_{\sigma}u^{\ell}$ given by factors $u$ of $u^{k}$.
The first non-trivial inequality among these consequences in the order from
left to right is of the form $u\leq_{\sigma}u^{m}v$ where $v$ is a proper
prefix of $u$. Notice that for $v=\varepsilon$ we are done.

For the considered prefix $v$ of $u$ we may also have some inequality of the
form $v\leq_{\sigma}u^{j}w$ with $j\in\mathbb{N}$, in particular the proof of
the inequality $u^{k}\leq_{\sigma}u^{\ell}$ has such a consequence. We analyze
the inequalities of that form for all prefixes of $u$.

On the set $P=\\{v\in A^{*}\mid v\text{ is prefix of }u\\}$ we define the
relation $\rightarrow$ as follows: $v\rightarrow w$ if there is $j\geq 0$ such
that $v\leq_{\sigma}u^{j}w$ and $|v|<|u^{j}w|$. (Notice that if $w=v$, then
$j>0$.) Since $\leq_{\sigma}$ is a stable quasi-order the relation
$\rightarrow$ is transitive. As is discussed above, there is $v\in P$, $v\neq
u$ such that $u\rightarrow v$ and so at least one of the following cases
occurs.

Case I: $u\rightarrow\varepsilon$. This means $u\leq_{\sigma}u^{j}$ with $j>1$
and we are done.

Case II: there is $v\in P$ such that $u\rightarrow v\not=\varepsilon$, and
there is no $w$ such that $v\rightarrow w$. In particular, $v\not=u$. Let
$\bar{v}$ be the suffix of $u$ such that $v\bar{v}=u$. Since
$v\not=\varepsilon$, we have $|\bar{v}|<|u|$ and by the induction assumption
there is $p$ such that $\bar{v}\leq_{\sigma}\bar{v}^{p}$. If we consider the
proof of $u\leq_{\sigma}u^{j}v$, then the consequence given by the prefix $v$
is trivial equality (by the assumption that there is no inequality of the form
$v\leq_{\sigma}u^{j}w$ with $|v|<|u^{j}w|$). Then the consequence of the proof
given by the suffix $\bar{v}$ is in the form
$\bar{v}\leq_{\sigma}\bar{v}u^{j-1}v$. Now we use this inequality
$(p-1)$-times to get
$\bar{v}^{p-1}\leq_{\sigma}(\bar{v}u^{j-1}v)^{p-1}=\bar{v}u^{(p-1)j-1}v$. Then
we multiply the former inequality by $\bar{v}$ on the right and we get
$\bar{v}^{p}\leq_{\sigma}\bar{v}u^{(p-1)j}$. Since we assumed
$\bar{v}\leq_{\sigma}\bar{v}^{p}$, we also get
$\bar{v}\leq_{\sigma}\bar{v}u^{(p-1)j}$. Finally, we multiply by $v$ on the
left and obtain $u\leq_{\sigma}u^{(p-1)j+1}$.

Case III: there is $v\in P$ such that $u\rightarrow v\not=\varepsilon$, and
$v\rightarrow v$. This means that there is $j>0$ such that
$v\leq_{\sigma}u^{j}v$. Now, it is enough to multiply the former inequality by
the suffix $\bar{v}$ of $u$ on the right, and we get $u\leq_{\sigma}u^{j+1}$.
∎

We try to show that an ordered semigroup $S$ is congenial whenever we have an
onto homomorphism $\sigma:A^{+}\rightarrow S$ determining wqo $\leq_{\sigma}$.
This means that for every homomorphism $\varphi:B^{+}\rightarrow S$, the set
$L_{\varphi}=\\{bwb\mid b\in B,w\in B^{*},b\leq_{\varphi}bwb\\}$ has to be
unavoidable. Hence, every periodic infinite word $w^{\infty}$ must contain a
factor from $L_{\varphi}$. In particular, if $B$ contains $n$ letters
$b_{1},b_{2},\dots,b_{n}$, then, for the word $w=b_{1}b_{2}\dots b_{n}$, there
is an index $i\in\\{1,\dots,n\\}$ and an integer $p\in\mathbb{N}$ such that
$\varphi(b_{i})\leq\varphi(b_{i}(b_{i+1}\dots b_{i})^{p})$. Since the
homomorphism $\sigma$ is onto, we may consider words $w_{j}\in A^{+}$ such
that $\sigma(w_{j})=\varphi(b_{j})$. In this setting, we want to show that
$\sigma(w_{i})\leq\sigma(w_{i}(w_{i+1}\dots w_{i})^{p})$. In fact, we aim on
the stronger inequality $w_{i}\leq_{\sigma}w_{i}(w_{i+1}\dots w_{i})^{p}$.
Proposition 4 is a special case of this property for $n=1$. The following
statement fulfills the sketched program.

###### Theorem 5.1

Let $S$ be a finite ordered semigroup. Then the following conditions are
equivalent:

  * (i)

There exists an alphabet $A$ and an onto homomorphism $\sigma:A^{+}\rightarrow
S$ such that $\leq_{\sigma}$ is a well quasi-order.

  * (ii)

There exists an alphabet $A$ and an onto homomorphism $\sigma:A^{+}\rightarrow
S$ such that, for every $n\in\mathbb{N}$ and $a_{1},\dots,a_{n}\in A$, there
exists $i\in\\{1,\dots,n\\}$ and $p\in\mathbb{N}$ such that
$a_{i}\leq_{\sigma}a_{i}(a_{i+1}\dots a_{n}a_{1}\dots a_{i})^{p}$.

  * (iii)

There exists an alphabet $A$ and an onto homomorphism $\sigma:A^{+}\rightarrow
S$ such that, for every $n\in\mathbb{N}$ and $u_{1},\dots,u_{n}\in A^{+}$,
there exists $i\in\\{1,\dots,n\\}$ and $p\in\mathbb{N}$ such that
$u_{i}\leq_{\sigma}u_{i}(u_{i+1}\dots u_{n}u_{1}\dots u_{i})^{p}$.

  * (iv)

There exists an alphabet $A$ and an onto homomorphism $\sigma:A^{+}\rightarrow
S$ such that, for every $n\in\mathbb{N}$ and $u_{1},\dots,u_{n}\in A^{+}$,
there exists $i\in\\{1,\dots,n\\}$ and $p\in\mathbb{N}$ such that
$\sigma(u_{i})\leq\sigma\left(u_{i}(u_{i+1}\dots u_{n}u_{1}\dots
u_{i})^{p}\right)$.

  * (v)

For every $n\in\mathbb{N}$ and $s_{1},\dots,s_{n}\in S$, there exists
$i\in\\{1,\dots,n\\}$ and $p\in\mathbb{N}$ such that $s_{i}\leq
s_{i}\cdot(s_{i+1}\cdots s_{n}\cdot s_{1}\cdots s_{i})^{p}$.

  * (vi)

For every alphabet $B$ and a homomorphism $\varphi:B^{+}\rightarrow S$ the
relation $\leq_{\varphi}$ is a well quasi-order.

###### Proof

We show the implications from top to bottom. The omitted implications are easy
to see. In the conditions (i) – (iv), the same pair $(A,\sigma)$ is employed.

“(i)$\implies$(ii)”: We consider a new alphabet $B=\\{b_{1},\dots,b_{n}\\}$ of
size $n$ and a homomorphism $\alpha:B^{+}\rightarrow A^{+}$ such that
$\alpha(b_{i})=a_{i}$ for all $i\in\\{1,\dots,n\\}$. We denote the composition
$\sigma\circ\alpha$ by $\varphi$. By Lemma 2, we know that the relation
$\leq_{\varphi}$ is a wqo. In particular, the infinite word $(b_{1}b_{2}\dots
b_{n})^{\infty}$ has a factor in $L_{\varphi}=\\{bwb\,|\,b\in B,w\in
B^{*},b\leq_{\varphi}bwb\\}$. Therefore, there is $i\in\\{1,\dots,n\\}$ and
$p\in\mathbb{N}$ such that $b_{i}\leq_{\varphi}b_{i}(b_{i+1}\dots
b_{n}b_{1}\dots b_{i})^{p}$. Finally, we get
$\sigma(a_{i})=\varphi(b_{i})\leq\varphi(b_{i}(b_{i+1}\dots b_{n}b_{1}\dots
b_{i})^{p})=\sigma(a_{i}(a_{i+1}\dots a_{n}a_{1}\dots a_{i})^{p})$.

“(ii)$\implies$(iii)”: We apply the condition (ii) on the word
$u=u_{1}u_{2}\dots u_{n}$ which we see as a concatenation of individual
letters. So, there is $i\in\\{1,\dots,n\\}$, $p\in\mathbb{N}$ and
$u_{i}^{\prime},u_{i}^{\prime\prime}\in A^{*}$ such that
$u_{i}=u^{\prime}_{i}au^{\prime\prime}_{i}$ and
$a\leq_{\sigma}a(u^{\prime\prime}_{i}u_{i+1}\dots u_{n}u_{1}\dots
u_{i-1}u^{\prime}_{i}a)^{p}$. If we multiply this inequality by the word
$u^{\prime}_{i}$ on left and by the word $u^{\prime\prime}_{i}$ on right, we
get $u_{i}\leq_{\sigma}u_{i}(u_{i+1}\dots u_{n}u_{1}\dots u_{i-1}u_{i})^{p}$.

“(v)$\implies$(vi)”: It follows from Corollary 2. ∎

The condition (ii) from Theorem 5.1 was mentioned in [1] in the setting of
rewriting systems, namely it occurs as condition (c) in the concluding
section. Also, the condition in Proposition 4 is mentioned there as the
condition (b). It is mentioned in [1] without proof that the conditions (a),
(b) and (c) are equivalent.

The equivalence of the conditions $(i)$ and $(vi)$ in Theorem 5.1 gives the
following result saying that whether the induced quasi-order $\leq_{\sigma}$
is wqo does not depend on the homomorphism $\sigma$ and it is indeed a
property of the ordered semigroup.

###### Corollary 3

Let $\sigma:A^{+}\rightarrow S$ be a homomorphism onto a finite ordered
semigroup $S$. Then $\leq_{\sigma}$ is a wqo if and only if the semigroup $S$
is congenial. ∎

We get the following characterization of congeniality using the condition
$(v)$ of Theorem 5.1.

###### Corollary 4

Let $S$ be an ordered semigroup. Then $S$ is congenial if and only if for
every $n\in\mathbb{N}$ and $s_{1},\dots,s_{n}\in S$, there exists
$i\in\\{1,\dots,n\\}$ such that $s_{i}\leq s_{i}\cdot(s_{i+1}\cdots s_{n}\cdot
s_{1}\cdots s_{i})^{\omega}$. $\spadesuit$

Unfortunately, it is not possible to bound $n$ in Corollary 4. Indeed, there
is a sequence of ordered semigroups $S_{m}$ such that $S_{m}$ satisfies the
condition in Corollary 4 if $n<m$ and does not satisfy the condition for $n=m$

##  6 Conclusion

We have shown that for a homomorphism $\sigma\colon A^{+}\to S$ onto a finite
ordered semigroup, it is decidable whether $\leq_{\sigma}$ is a wqo. We also
proved that the question does not depend on $\sigma$, but it is indeed a
property of the given ordered semigroup. One may expect more effective or
transparent characterization similar to that of the unordered case in [8].
Nevertheless, our observations suggest that such a characterization could be
more difficult to obtain.

We conclude with a brief discussion of the applications of our results. We do
not see any direct impact of the research to the work done in [1]. On the
other hand, in [8], the wqo was applied to prove regularity of maximal
solutions of very general language equations and inequalities (see also [12]).
The theory developed in [8] may be naturaly extended to the ordered case, so
our new class of ordered semigroups inducing well quasi-orders may find the
application there.

### Acknowledgement

We are grateful to the referees for their numerous valuable suggestions which
improved the paper, in particular, its introductory part. We also thank to
Michal Kunc for inspiring discussions.

## Appendix

### The Proofs for Technical Lemmas from Section 2

  * Lemma 2. Let $\sigma\colon A^{+}\rightarrow S$ be a homomorphism to an ordered semigroup $S$ such that $\leq_{\sigma}$ is a wqo. Let $B$ be an alphabet, $\alpha:B^{+}\rightarrow A^{+}$ be a homomorphism of free semigroups such that $\alpha(B)\subseteq A$, and $\varphi=\sigma\circ\alpha$. Then the quasi-order $\leq_{\varphi}$ is a wqo.

###### Proof

Let $(w_{i})_{i\in\mathbb{N}}$ be a sequence of words over $B$. Then
$(\alpha(w_{i}))_{i\in\mathbb{N}}$ is a sequence of words over $A$. Since
$\leq_{\sigma}$ is a wqo, there exist $k$ and $\ell$ such that $k<\ell$ and
$\alpha(w_{k})\leq_{\sigma}\alpha(w_{\ell})$. Its proof consists of a list of
inequalities $a_{i}\leq_{\sigma}u_{i}$ where $i\in\\{1,\dots,m\\}$. The
considered factorizations correspond to the factorizations
$w_{k}=b_{1}b_{2}\dots b_{m}$ and $w_{\ell}=v_{1}v_{2}\dots v_{m}$ such that
$b_{i}\in B$, $v_{i}\in B^{+}$, $\alpha(b_{i})=a_{i}$, $\alpha(v_{i})=u_{i}$,
because $\alpha$ maps letters to letters. Now, $a_{i}\leq_{\sigma}u_{i}$ means
$\sigma(a_{i})\leq\sigma(u_{i})$, which can be written as
$\varphi(b_{i})\leq\varphi(v_{i})$, that is $b_{i}\leq_{\varphi}v_{i}$.
Composing these inequalities for $i\in\\{1,\dots,m\\}$, we get
$w_{k}\leq_{\varphi}w_{\ell}$ and we are done. ∎

  * Lemma 3. A semigroup $S$ is congenial if and only if $\leq_{\operatorname{eval}_{S}}$ is a wqo.

###### Proof

The implication “$\Longrightarrow$” is trivial.

Let $\varphi:B^{+}\rightarrow S$ be a homomorphism to a finite ordered
semigroup $S$ such that $\leq_{\operatorname{eval}_{S}}$ is a wqo. We denote
$C=\varphi(B)\subseteq S$ and consider the homomorphism
$\alpha:C^{+}\rightarrow S$ which is the restriction of
$\operatorname{eval}_{S}$ to $C^{+}$. Then $\leq_{\alpha}$ is a wqo, since
$\leq_{\alpha}$ is a restriction of $\leq_{\operatorname{eval}_{S}}$ on
$C^{+}$. Now, knowing that $\leq_{\alpha}$ is a wqo, we apply Lemma 2 and
obtain that $\leq_{\varphi}$ is wqo too.∎

### The Proof of Proposition 2

  * Proposition 2. Every congenial semigroup $S$ satisfies the condition

$\forall s,t\in S\colon s\leq(s\cdot t)^{\omega}\cdot s\text{ or }t\leq
t\cdot(s\cdot t)^{\omega}.$ (1)

###### Proof

Let $S$ be a congenial semigroup. Then $\leq_{\operatorname{eval}_{S}}$ is
wqo. However, it is useful to distiguish a role of letters and elements of the
semigroup $S$. Thus we replace $S^{+}$ by an isomorphic semigroup $A^{+}$ and
denote by $\sigma$ the homomorphism $\sigma\colon A^{+}\to S$. This
homomorphism has a useful property, namely, the restriction of $\sigma$ to $A$
is a bijection between $A$ and $S$. By the assumption, the relation
$\leq_{\sigma}$ is a wqo.

We start the proof by showing that a congenial semigroup $S$ satisfies $s\leq
s^{\omega+1}$ for every $s\in S$. Consider a sequence of words
$\\{(a^{i})\\}_{i=1}^{\infty}$, where $s=\sigma(a)$. Due to $\leq_{\sigma}$
being a wqo, there are some positive integers $k<\ell$ such that
$a^{k}\leq_{\sigma}a^{\ell}$. By definition of $\leq_{\sigma}$ we have
$a\leq_{\sigma}a^{n+1}$ for some $n\in\mathbb{N}$. This means $s\leq
s^{n+1}=s\cdot s^{n}\leq s^{2n+1}$ and by iteration we conclude that $s\leq
s^{\omega+1}$.

We continue the proof with elements $s,t\in S$ and letters $a,b\in A$ such
that $s=\sigma(a)$ and $t=\sigma(b)$. Consider the sequence of words
$\\{(ab)^{i}\\}_{i=1}^{\infty}$ over the alphabet $A$. Then for some positive
integers $k<\ell$ it holds that $(ab)^{k}\leq_{\sigma}(ab)^{\ell}$. Using the
definition of the order $\leq_{\sigma}$ we find the first non-trivial
inequality of the form $ab\leq_{\sigma}ab\dots$. This means that
$a\leq_{\sigma}au$ and $b\leq_{\sigma}v$ for some $u,v\in A^{*}$ such that
$auv$ is a prefix of $(ab)^{\ell}$ of the length at least $3$. Now, assume
that $u\not=\varepsilon$. Then from $a\leq_{\sigma}au$ it follows $s\leq
s\cdot t\cdots r$, where $r\in\\{s,t\\}$. In case of $r=s$, we have for some
$p\in\mathbb{N}$ that $s\leq s\cdot(t\cdot s\cdots t\cdot s)=s\cdot(t\cdot
s)^{p}$. Iterating this inequality, we get $s\leq s\cdot(t\cdot s)^{\omega}$.
In case of $r=t$, we have for some $p\in\mathbb{N}$ that $s\leq s\cdot t\cdot
s\cdots s\cdot t=(s\cdot t)^{p}$. Taking the $\omega\mathchar 45\relax$power
of both sides, we obtain $s^{\omega}\leq(s\cdot t)^{\omega}$. Now we multiply
by $s$ on the right to get $s^{\omega}\cdot s\leq(s\cdot t)^{\omega}\cdot s$.
Using $s\leq s^{\omega+1}$ we conclude that $s\leq(s\cdot t)^{\omega}\cdot
s=s\cdot(t\cdot s)^{\omega}$.

Assume that $u=\varepsilon$. Then we have $b\leq v$, where $v$ starts with $b$
and has the length at least $2$. Similar to the previous case we obtain $t\leq
t\cdot s\cdots r$, and we may proceed in the same way. ∎

### The Additional Material for Section 3

Example 2 gives a useful insight. Moreover, it inspires us to show that an
arbitrary finite $0\mathchar 45\relax$simple semigroup can be ordered in such
a way that it is congenial. Recall that, by a $0\mathchar 45\relax$simple
semigroup $S$ is a semigroup with zero element $0$ that has exactly two
distinct ideals: $\\{0\\}$ and $S$. Then in a finite $0\mathchar
45\relax$simple semigroup we take $0$ as the top element that covers the
antichain of all non-zero elements. We denote the class of such ordered
semigroups by $0\mathchar 45\relax\mathsf{CS}^{-}$.

###### Proposition 5

Every finite ordered semigroup in $0\mathchar 45\relax\mathsf{CS}^{-}$ is
congenial.

###### Proof

We check that every finite $0\mathchar 45\relax$simple semigroup satisfies the
inequality $x\leq x\cdot(y\cdot x)^{\omega}$, which gives the statement by
Proposition 3. Since $0$ is the top element, we have to discuss only the case
when $x\cdot(y\cdot x)^{\omega}\not=0$. However, in this case we have
$x\cdot(y\cdot x)^{\omega}=x$. ∎

Another class of ordered semigroups to which the example $B_{2}^{-}$ fits very
well is the class of inverse semigroups. This class is extensively studied as
it is a natural generalization of groups. For reader not familiar with that
theory, we just mention that every inverse semigroup may be represented as a
semigroup of partial bijections on an aprropriate set $X$ (the so-called
Vagner-Preston representation theorem). In this representation, every element
can be viewed as a relation, i.e., the element is a subset of $X\times X$.
Thus elements can be compared by the inclusion $\subseteq$ if they are
represented by relations. In this way, any inverse semigroup is implicitly
ordered, however we worked with the dual order in Example 2. We call this dual
order _anti-natural_. Since every considered ordered inverse semigroup
satisfies the inequality $x\leq x\cdot(y\cdot x)^{\omega}$, we obtain the next
consequence of Proposition 3.

###### Proposition 6

Let $S$ be a finite inverse semigroup ordered anti-naturally. Then $S$ is
congenial.∎

The following theorem describes a condition generalizing that from Proposition
3. The proof is based on the same ideas. After the proof we also explain that
a semigroup ordered by the equality satisfies the assumtions from the
statement if and only if the semigroup is a chain of simple semigroups.

Before we formulate the result, we need to recall the definition of the one
sided Green relation $\mathscr{L}$. For $s,t\in S$, we have $s\mathscr{L}t$ if
there are elements $x,y\in S^{1}$ such that $x\cdot s=t$ and $y\cdot t=s$.
Under this definiton, the relation $\mathscr{L}$ is an equivalence relation.
We also write $s\leq_{\mathscr{L}}t$ if there is $y\in S^{1}$ such that
$y\cdot t=s$. (The dual relations $\mathscr{R}$ and $\leq_{\mathscr{R}}$ are
not used in our paper.)

For a non-empty subset $X$ of a semigroup $S$ we write $\langle X\rangle$ for
a subsemigroup of $S$ generated by $X$. By $E(S)$ we mean the set of all
idempotents of a semigroup $S$.

###### Theorem 6.1

Let $S$ be a finite ordered semigroup. If the semigroup $S$ satisfies

$(\forall F\subseteq S,F\neq\emptyset)(\exists s\in F)(\forall e\in E(\langle
F\rangle)):e\leq_{\mathscr{L}}s\implies s\leq s\cdot e,$ (2)

then $S$ is congenial.

###### Proof

We deal with the situation when $A=S$ and $\operatorname{eval}_{S}$ is a
considered homomorphism. Let $v$ be an infinite word over an alphabet $A$.
Denote $v^{\prime}$ its suffix which contains every letter infinitely many
times. Now we take

$F=\\{\sigma(a)\,|\,a\in A,a\text{ occurs in }v^{\prime}\\}$

and the condition (2) gives us the choice of the letter $a$, which is
contained in $v^{\prime}$ infinitely many times. The rest of the proof is
analogous to the proof of Proposition 3. ∎

We explain the situation when the considered semigroup is the chain of simple
semigroups. For every $F$ we take $s\in F$ in the lowest $\mathscr{J}\mathchar
45\relax$class. The idempotent $e$ satisfies $e\geq_{\mathscr{J}}s$ and with
$e\leq_{\mathscr{L}}s$ we have $e\mathscr{L}s$. The idempotent $e$ is a right
neutral element in its $\mathscr{L}\mathchar 45\relax$class. We get $s\cdot
e=s$ and we see that every chain of simple semigroups satisfies the condition
(2).

On the other hand, if the semigroup $S$ is ordered by equality and satisfies
the condition (2), then we may take $F=\\{t,t^{\prime}\\}$. Let $s\in F$ be
the element satisfying the condition (2). If $s=t$ then we take
$e=(t^{\prime}\cdot t)^{\omega}$, for which $t\leq t\cdot(t^{\prime}\cdot
t)^{\omega}$ follows. If $s=t^{\prime}$ then we take $e=(t\cdot
t^{\prime})^{\omega}$, and obtain $t^{\prime}\leq t^{\prime}\cdot(t\cdot
t^{\prime})^{\omega}$. That means that the semigroup is a chain of simple
semigroups.

### The Additional Material for Section 4

  * Theorem 4.1. Let $\sigma:A^{+}\rightarrow S$ be a homomorphism onto a finite ordered semigroup $S$. Then $\leq_{\sigma}$ is a wqo if and only if the automaton $\mathcal{A}_{\sigma}$ does not contain an infinite path starting in the initial state $\iota$.

###### Proof

If $\leq_{\sigma}$ is not a wqo, then by Propositon 1 there exists an infinite
word avoiding $L_{\sigma}=\\{ava\mid a\in A,v\in A^{*},a\leq_{\sigma}ava\\}$.
Thus, for its each finite prefix $w$, we know that $\delta(\iota,w)$ is
defined in $\mathcal{A}_{\sigma}$ by Lemma 5. Hence there is an infinite path
in $\mathcal{A}_{\sigma}$ starting in the initial state.

On the contrary, assume that $\mathcal{A}_{\sigma}$ contains an infinite path
starting in the initial state $\iota$. Then the label of that path is an
infinite word avoiding the set of words $L_{\sigma}$ by Lemma 5. Again, by
Proposition 1, we get that $\leq_{\sigma}$ is not a wqo. ∎

We add an illustrative example of the construction of the automaton
$\mathcal{A}_{\sigma}$.

###### Example 3

In Example 2 we saw that $B_{2}^{+}\notin\mathcal{C}$. If we consider $\sigma$
as a canonical mapping sending a letter from $A=\\{a,b\\}$ onto the element in
the semigroup $B_{2}^{+}$ of the same name, then $S\times A\times A$ has 20
elements. The automaton $\mathcal{A}_{\sigma}$ consists of states
$\iota,\bar{a},\bar{b}$ and then states in $\mathcal{P}$. Every state
$M\in\mathcal{P}$ is coherent, non-empty and disjoint with
$F=\\{(a,a,a),(b,b,b)\\}$. If we remove these two elements from $S\times
A\times A$ and divide the resulting set into two parts by the last coordinate,
we obtain two nine-elements sets $M_{a}=\\{(s,x,a)\in S\times A\times A\mid
s\not=a\vee x\not=a\\}$, and $M_{b}=\\{(s,x,b)\in S\times A\times A\mid
s\not=b\vee x\not=b\\}$. Hence the number of states of $\mathcal{A}_{\sigma}$
is $3+2\cdot(2^{9}-1)=1025$.

However, we are not interested in all states, but only those reachable from
the initial state $\iota$. We see that only tripples of the form
$(\sigma(u),{f(u)},{\ell(u)})$, where $u\in A^{+}\setminus A$, may occur as
elements of these states. Hence, in the previous considerations, we may
replace $M_{a}$ by $\\{(0,a,a),(0,b,a),(ba,b,a)\\}$ and $M_{b}$ by
$\\{(0,a,b),(0,b,b),(ab,a,b)\\}$. This gives a better uper bound for the size
of the part of $\mathcal{A}_{\sigma}$ reachable from $\iota$. (The bound is
$3+2\cdot(2^{3}-1)=17$.)

$\textstyle{(0,a,a)\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{b}$$\scriptstyle{a}$$\textstyle{(0,a,b),(ab,a,b)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{b}$$\textstyle{\bar{a}\,\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{a}$$\scriptstyle{b}$$\textstyle{(ab,a,b)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{b}$$\textstyle{(0,a,b),(0,b,b)\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{a}$$\scriptstyle{b}$$\textstyle{\iota\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{a}$$\scriptstyle{b}$$\textstyle{(0,a,b),(0,b,b),(ab,a,b)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{b}$$\textstyle{(0,a,b),(0,b,a),(ba,b,a)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{a}$$\textstyle{\bar{b}\,\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{a}$$\scriptstyle{b}$$\textstyle{(ba,b,a)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{a}$$\textstyle{(0,a,a),(0,b,a)\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{b}$$\scriptstyle{a}$$\textstyle{(0,b,b)\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{a}$$\scriptstyle{b}$$\textstyle{(0,b,a),(0,b,b)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{a}$
Figure 3: Reachable states in the automaton $\mathcal{A}_{\sigma}$ for the
ordered semigroup $B_{2}^{+}$.

Fig. 3 describes that part of the automaton $\mathcal{A}_{\sigma}$ completely.
To simplify the notation, the states in $\mathcal{P}$ are labeled by the lists
of elements (i.e., without curly brackets).

### The proof of Corollary 4

  * Corollary 4. Let $S$ be an ordered semigroup. Then $S$ is congenial if and only if for every $n\in\mathbb{N}$ and $s_{1},\dots,s_{n}\in S$, there exists $i\in\\{1,\dots,n\\}$ such that $s_{i}\leq s_{i}\cdot(s_{i+1}\cdots s_{n}\cdot s_{1}\cdots s_{i})^{\omega}$.

###### Proof

With respect to Theorem 5.1, it is enough to show that the two following
conditions are equivalent for a given pair of elements $s,t\in S$:

$(a)\ \ \text{there exists }p\in\mathbb{N}\text{ such that }s\leq
s\cdot(t\cdot s)^{p};\qquad(b)\ \ s\leq s\cdot(t\cdot s)^{\omega}.$

If (a) holds, then we may iterate the inequality and obtain

$s\leq s\cdot(t\cdot s)^{p}\leq s\cdot(t\cdot s)^{p}\cdot(t\cdot
s)^{p}\leq\dots\leq s\cdot(t\cdot s)^{pk}$

for an arbitrary $k\in\mathbb{N}$. Since there is an integer $k\in\mathbb{N}$
such that $(t\cdot s)^{k}=(t\cdot s)^{\omega}$, we get the condition (b).

The existence of such $k$ gives the implication “(b)$\implies$(a)” directly. ∎

### The Sequence of Ordered Semigroups $S_{m}$

For $m\geq 2$ we construct an ordered semigroup $S_{m}$ as follows. We
describe the semigroup by the presentation over the $m$-letter alphabet
$A_{m}=\\{a_{1},\dots a_{m}\\}$:

$S_{m}=\langle\,a_{1},\dots,a_{m}\mid a_{i}a_{j}=0\ (\text{for
}i,j\in\\{1,\dots,m\\}\text{ such that }j-i\not\in\\{1,1-m\\}),$
$\phantom{asaddddfsdfas}(a_{i}\dots a_{m}a_{1}\dots a_{i-1})^{2}=a_{i}\dots
a_{m}a_{1}\dots a_{i-1}\ (\text{for }i\in\\{1,\dots,m\\})\rangle.$

We explain the meaning of the previous semigroup presentation informally. We
denote $u=a_{1}\dots a_{m}$. The non-zero elements of $S_{m}$ are words of
length at most $2m-1$ which are factors of $u^{\infty}$. Every word which is
not a factor of $u^{\infty}$ is identified with $0$ by the rule $a_{i}a_{j}=0$
for appropriate indices. Now, any word which is a factor of $u^{\infty}$ of
length at least $2m$ contains a factor $w$ of length $2m$ which is a conjugate
of $uu$. Each such factor $w$ may be shortened by the rule $(a_{i}\dots
a_{m}a_{1}\dots a_{i-1})^{2}=a_{i}\dots a_{m}a_{1}\dots a_{i-1}$. This
procedure may be repeated until the resulting word has length smaller than
$2m$. The important property of the previous reduction is that the prefixes
and suffixes of length $m$ are kept.

The description explains both the natural homomorphism
$\sigma_{m}:A_{m}\rightarrow S_{m}$ and the multiplication on $S_{m}$. For the
reader familiar with the structure theory of semigroups, we mention that
$S_{m}$ has the minimal ideal $\\{0\\}$, one regular class and irregular
singleton $\mathscr{J}$-classes consisting of factors of $uu$ of length
smaller than $m$. The regular class consists of factors of $uuu$ of length at
least $m$ and at most $2m-1$. It is a $m\times m$ box with singleton
$\mathscr{H}$-classes and exactly $m$ idempotents (conjugates of $u$).

Finally, we introduce the order on $S_{m}$. At first, we put $0$ to be the
largest element. Then for two factors $x,y$ of $u^{\infty}$ of length smaller
than $2m-1$, we have

$x\leq y\quad\text{if}\quad\left\\{\begin{array}[]{l}x=y\text{ or}\\\
1<|x|<m\leq|y|\ \wedge\ x\text{ is both the prefix and the suffix of
}y.\end{array}\right.$

One may check that the relation $\leq$ is a stable order on the semigroup $S$.
We point out that $a_{i}\leq y$ only for $y\in\\{a_{i},0\\}$.

In Corollary 4, we consider the following condition for a given integer $n$:

$(\forall s_{1},\dots,s_{n}\in S)(\exists i\in\\{1,\dots,n\\}):s_{i}\leq
s_{i}\cdot(s_{i+1}\cdots s_{n}\cdot s_{1}\cdots s_{i})^{\omega}.$ (3)

If we want to test whether $S_{m}$ satisfies the condition (3) for a given
$n$, we distinguish two cases depending on whether $m$ divides $n$ or not.

First assume that $m$ divides $n$. For every $i\in\\{1,\dots,n\\}$ we denote
$[i,m]$ the remainder after dividing $i$ by $m$ and put $s_{i}=a_{[i,m]}$.
Then $s_{1}\cdot s_{2}\cdots s_{n}=(a_{1}\cdots
a_{m})^{\frac{n}{m}}=a_{1}\dots a_{m}$ and we see that $S_{m}$ does not
satisfy the condition (3).

If we assume that $m$ does not divide $n$, then $(s_{i+1}\cdots s_{n}\cdot
s_{1}\cdots s_{i})^{\omega}\not=0$ only if $s_{1}s_{2}\dots s_{n}$ is
conjugate to some power of $a_{1}\dots a_{m}$. This is not possible when each
$s_{i}$ is an element in $A_{m}$. Thus there is an index $i$ such that
$s_{i}\not\in A_{m}$, and the condition (3) is valid.

We conclude with the statement that $S_{m}$ satisfies the condition (3) if and
only if $m$ does not divide $n$. In particular, $S_{m}$ satisfies the
condition (3) for $n<m$ and does not satisfy the condition for $n=m$.

## References

  * [1] Bucher, W., Ehrenfeucht, A., Haussler, D.: On total regulators generated by derivation relations. Theor. Comput. Sci. 40, 131–148 (1985). https://doi.org/10.1016/0304-3975(85)90162-8
  * [2] D’Alessandro, F., Varricchio, S.: Well quasi-orders in formal language theory. In: Ito, M., Toyama, M. (eds.) DLT 2008. LNCS, vol. 5257, pp. 84–95. Springer (2008). https://doi.org/10.1007/978-3-540-85780-8_6
  * [3] Ehrenfeucht, A., Haussler, D., Rozenberg, G.: On regularity of context-free languages. Theor. Comput. Sci. 27, 311–332 (1983). https://doi.org/10.1016/0304-3975(82)90124-4
  * [4] Haase, C., Schmitz, S., Schnoebelen, P.: The Power of Priority Channel Systems. Logical Methods in Computer Science 10(4) (2014). https://doi.org/10.2168/LMCS-10(4:4)2014
  * [5] Higman, G.: Ordering by divisibility in abstract algebras. Proceedings of the London Mathematical Society s3-2(1), 326–336 (1952). https://doi.org/10.1112/plms/s3-2.1.326
  * [6] Howie, J.M.: An Introduction to Semigroup Theory. Academic Press (1976)
  * [7] Kruskal, J.B.: The theory of well-quasi-ordering: A frequently discovered concept. J. Comb. Theory, Ser. A 13(3), 297–305 (1972). https://doi.org/10.1016/0097-3165(72)90063-5
  * [8] Kunc, M.: Regular solutions of language inequalities and well quasi-orders. Theor. Comput. Sci. 348, 277–293 (2005). https://doi.org/10.1016/j.tcs.2005.09.018
  * [9] de Luca, A., Varricchio, S.: Finiteness and Regularity in Semigroups and Formal Languages. Springer (1999). https://doi.org/10.1007/978-3-642-59849-4
  * [10] Pin, J.É.: Varieties of Formal Languages. Foundations of computer science, North Oxford Academic (1986)
  * [11] Pin, J.É.: Syntactic semigroups. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages. vol. 1, pp. 679–746. Springer (1997). https://doi.org/10.1007/978-3-642-59136-5_10
  * [12] Pin, J.É.: How to prove that a language is regular or star-free? In: Leporati, A., Martín-Vide, C., Shapira, D., Zandron, C. (eds.) LATA 2020\. LNCS, vol. 12038, pp. 68–88. Springer (2020). https://doi.org/10.1007/978-3-030-40608-0_5
  * [13] Schütte, K., Simpson, S.G.: Ein in der reinen zahlentheorie unbeweisbarer satz über endliche folgen von natürlichen zahlen. Arch. Math. Log. 25(1), 75–89 (1985). https://doi.org/10.1007/BF02007558


# Determining ground-state phase diagrams on quantum computers via a
generalized application of adiabatic state preparation

Akhil Francis  Department of Physics, North Carolina State University,
Raleigh, North Carolina 27695, USA  Ephrata Zelleke  Department of Physics,
Goucher College, Baltimore, Maryland 21204 USA  Ziyue Zhang  Department of
Physics, Georgetown University, Washington, DC 20057 USA  Alexander F. Kemper
Department of Physics, North Carolina State University, Raleigh, North
Carolina 27695, USA  J. K. Freericks  Department of Physics, Georgetown
University, Washington, DC 20057 USA

###### Abstract

Quantum phase transitions materialize as level crossings in the ground-state
energy when the parameters of the Hamiltonian are varied. The resulting
ground-state phase diagrams are straightforward to determine by exact
diagonalization on classical computers, but are challenging on quantum
computers because of the accuracy needed and the near degeneracy of competing
states close to the level crossings. In this work, we use a local adiabatic
ramp for state preparation to allow us to directly compute ground-state phase
diagrams on a quantum computer via time evolution. This methodology is
illustrated by examining the ground states of the XY model with a magnetic
field in the $z$-direction in one dimension. We are able to calculate an
accurate phase diagram on both two and three site systems using IBM quantum
machines.

##  I Introduction

Quantum computers are thought to enable calculations that cannot be carried
out on classical computers Lloyd (1996); Abrams and Lloyd (1997). One
challenging problem in many-body physics is to determine the zero-temperature
phase diagram of finite systems that have level crossings in the ground state
as parameters in the Hamiltonian are varied Qin  _et al._ (2021). Such phase
diagrams commonly occur when a system has competing order parameters Hubbard
(1963). One possible approach to solving this problem is to simply create
circuits for target wave functions that can have their parameters varied to
allow for a variational determination of the approximate ground state. Then,
one can determine the phase diagram by examining the quantum numbers and the
symmetries of the variational wave function. But, such an approach is likely
to fail or to be inaccurate; this is because there are low-lying states near
the level crossings and the variational calculations need to be done with high
accuracy to carry out such a program. This becomes especially complicated if
the variational state ansatz does not belong to the subspace corresponding to
ground state quantum numbers.

Another approach one could try is to use adiabatic state preparation: start
the system in an easy to prepare state that is the ground state of the
Hamiltonian for a given parameter, and then slowly change the parameters in
the Hamiltonian. If we change slowly enough, the adiabatic theorem guarantees
that we stay in the ground state. This approach may also have problems,
because the time evolution will preserve the symmetry of the wavefunction, and
level crossings can only occur between states with different symmetries.

However, we can modify the adiabatic state preparation protocol by adding a
small symmetry breaking field, and we can find the phase transition point by
monitoring the expectation value of quantum numbers corresponding to different
symmetries. Now, because the symmetries are only approximate, a sufficiently
slow time evolution will map out the ground-state phase diagram. We then
repeat with different magnitudes of the symmetry-breaking field and
extrapolate the results to the limit where the symmetry breaking field
vanishes. In this fashion, we can employ adiabatic state preparation to carry
out a mapping of the ground-state phase diagram. It is unlikely that fast
forwarding techniques such as QAOA (Farhi  _et al._ , 2014) or shortcuts to
adiabaticity (Chen  _et al._ , 2010; Guéry-Odelin  _et al._ , 2019), will help
with carrying out this approach because it may require very accurate
optimization near the level crossing, or knowledge of the eigenstates or
invariants of motion which maybe costly to find.

We test our approach on the ground state phase diagram of an isotropic 1D XY
model in a magnetic field along the $z$-direction. This system is a stringent
test for such an approach, because there are $N$ phase transitions for an N
site system in the region $|B_{z}|\leq|J|$. As the system size is made larger,
the problem becomes increasingly more challenging to solve. In fact, the model
may exhibit a devil’s staircase in the ground-state phase diagram (Bak and
Bruinsma, 1982). The conserved symmetry (quantum number) is the $z$-component
of total spin, so we can monitor the phase diagram by measuring the
magnetization of the system.

Our strategy is to start the system in a large $B_{z}$ field, and to add a
small symmetry-breaking field $B_{x}$ in a perpendicular direction. The
initial state will be taken to be polarized along the $z$-direction, which is
easy to prepare. We ramp the $z$-field down, keeping the $x$-field fixed,
using a local adiabatic ramp (Richerme  _et al._ , 2013a). This approach was
originally used to generate the ground state of the transverse-field Ising
model in ion trap quantum simulators. For the two site system we also
performed the experiment starting from all spins aligned down and ramping up
the $B_{z}$ field. We find that for two and three site system this approach
gives accurate phase diagram in IBM quantum machines.

Figure 1: Magnetization versus the $B_{z}$ field for a 10 site system. The
blue curve labeled exact shows the magnetization for the ground state without
any $B_{x}$ field. The red curve shows the magnetization of a local adiabatic
evolved state from an all up state with a local ramp of $\gamma=50$ and 1000
Trotter steps. Here, we have set $B_{x}=0.05J$.

##  II Methods

We work with the one-dimensional isotropic XY model with periodic boundary
conditions and a magnetic field along the $z$ direction as shown in Eq. (1)
for a system with $L$ spins:

$H=-\sum_{i=1}^{L}\left[\frac{J}{4}\left(\sigma_{i}^{x}\sigma_{i+1}^{x}+\sigma_{i}^{y}\sigma_{i+1}^{y}\right)+\frac{B_{z}}{2}\sigma_{i}^{z}\right].$
(1)

where $\sigma^{x,y,z}_{i}$ are the usual Pauli matrices obtained by setting
$(\hbar=1)$ in the spin operators of the $i^{th}$ site,
$S^{x,y,z}_{i}=\frac{\hbar}{2}\sigma^{x,y,z}_{i}$. This model can be solved
exactly by fermionization using a Jordan Wigner (JW) transformation Jordan and
Wigner (1928) and a subsequent Fourier transformation to work in momentum
space Lieb  _et al._ (1961). The boundary term needs more care as it still has
the Jordan Wigner string in it. Usually for a large system this term is
negligible. Alternatively, we simply consider the periodic term without a JW
string attached, so that the usual Fourier transform yields the fermionic
eigen energies. Then the fermionic Hamiltonian takes the form

$H=\sum_{k}\left(\omega_{k}c_{k}^{\dagger}c_{k}-\frac{B_{z}}{2}\right)$ (2)

where $\omega_{k}=\left(-J\cos k+B_{z}\right)$ and $k=\frac{2n\pi}{L}$, with
$n=-\frac{L}{2}+1,\cdots,0,\cdots,\frac{L}{2}$. For a finite-size system the
boundary term matters; this can be dealt with by making use of the fermionic
parity (Mbeng  _et al._ , 2020). We work in original spin representation
throughout this paper.

Figure 2: Energy diagram for a two site (top panel) and three site (bottom
panel) system. The dotted lines are for the ideal system with $B_{x}=0$; these
curves have level crossings. The solid lines are the energies with
$B_{x}=0.2J$, which leads to avoided crossings everywhere for the ground
state.

,

Figure 3: Local adiabatic ramp for a two site (top panel) and three site
(bottom panel) system. For the two site system, the solid line shows a ramp
with 200 time steps and the solid circles are for 20 time steps. Here, we have
set $B_{x}=0.02J$ and $\gamma=1.5$ for two sites. For the three site system,
we have taken $B_{x}=0.08J$ and $\gamma=2$ and the curves are similar (solid
line, 200 time steps; solid circles, 50 time steps). The horizontal axis is
the fractional time $t/t_{f}$ for the 200 step ramp. We use an Akima-spline
interpolator to obtain the ramp in uniform time steps from uniform magnetic
field steps used in evaluating the integral. One can see that the ramp goes
slower near the crossing regions.

The ground state has many level crossings as a function of the magnetic field
$B_{z}$. This is illustrated in Figs. 1 and 2. Fig. 1 shows the expectation
value of the $z$-component of spin (also known as the magnetization) as a
function of $B_{z}$. Each of the vertical steps on the exact curve corresponds
to a level crossing, where the quantum-number for the $z$-component of spin
shifts by one unit; the plot also shows an adiabatic time evolution, which
will be discussed later. In this work, we show how to obtain these quantum
phase transition points (critical $B_{z}$ values) on a quantum computer.

In adiabatic state preparation, we start from the ground state of a
Hamiltonian which is easy to prepare and then we slowly evolve the state using
time evolution with a Hamiltonian that interpolates from the initial
Hamiltonian to the target Hamiltonian. The amount of diabatic excitations are
determined by how fast the Hamiltonian changes near the avoided crossing
spectral gaps to higher excited states. The initial Hamiltonian can be thought
of as a Hamiltonian with $J=0$, or equivalently with $B_{z}\gg J$. Then, the
magnetic field is ramped down to let’s say zero, and where ideally we end up
in the ground state of the Hamiltonian with $B_{z}=0$. But, this cannot occur
if there is additional symmetry in the Hamiltonian. Here, because
$S^{z}=\sum_{i}\sigma_{i}^{z}/2$ commutes with $H$, we can simultaneously
diagonalize both operators and this means the quantum number corresponding to
the total $z$-component of spin (m) are unchanged during time evolution. Thus,
we only stay in the ground state of a system with definite $z$-component of
spin. This can be seen in Fig. 2 where the dotted lines showing level crossing
for a two and three site system.

In order to achieve adiabatic state preparation, we must break the symmetry.
We do so by adding a small $B_{x}$ field, upon which $[S_{z},H]\neq 0$. This
means states that used to have different $m$ quantum numbers are now coupled
together. This can be seen in Fig. 2 where the solid lines showing avoided
level crossing for a two and three site system with a $B_{x}$ field. This then
allows adiabatic state preparation to take place, and if we go slow enough, we
will have limited diabatic excitation out of the ground state. Fig. 1 shows
that with a $B_{x}$ field one can traverse through all the magnetization
sectors in a ten site system. However, the $B_{x}$ term changes the
Hamiltonian and its energy levels. We only have quantum phase transitions when
$B_{x}=0$, which implies we must extrapolate to the $B_{x}\to 0$ limit.

The time evolution is implemented with a local adiabatic ramp Roland and Cerf
(2002); Richerme  _et al._ (2013b), which is supposed to yield the same
diabatic excitation for each time step of the time evolution. It does so by
ramping faster when the gap to the first excited state is large and more
slowly when the gap is small. It is constructed by adjusting the rate
$\frac{dB_{z}}{dt}$ according to the instantaneous energy gap
${\Delta(B_{z})}$ such that $|\frac{dB_{z}}{dt}|\ll{\Delta^{2}(B_{z})}$
Richerme  _et al._ (2013b). This provides the highest fidelity ramp for a
given total time of evolution.

The total time for the local ramp is determined by an adiabaticity parameter
($\gamma$). We require $\gamma\gg 1$ for an adiabatic ramp, where
$\gamma=\left|\frac{\Delta^{2}(B_{z})dt}{d{B_{z}}(t)}\right|$. Starting from a
magnetic field $B_{z,\mathrm{initial}}$ and ramping down to a magnetic field
$B_{z,\mathrm{final}}$ the ramp time t is given by

$t=-\gamma\int_{B_{z,\mathrm{initial}}}^{B_{z,\mathrm{final}}}\frac{dB_{z}}{\Delta^{2}(B_{z})}.$
(3)

where $\Delta$ is the energy difference between first excited state and ground
state and the minus sign indicates that we are ramping down. One can either
choose the adiabaticity parameter first, and determine the total time, or one
can fix the total time and infer the adiabaticity parameter. A resulting local
adiabatic ramp for a two and three site system is shown in Fig. 3. The ramp
was obtained via a Trotter product formula. We select the adiabaticity
parameter and the number of Trotter steps such that we can accurately
determine the different steps in the magnetization, which signal the different
regions of the ground-state phase diagram.

The same strategy is used on a quantum computer. We use the Trotter product
formula for the time-evolution operator from $t_{0}$ to $t$:

$\mathbf{U}\left(t,t_{0}\right)\approx
e^{-i\mathbf{H}(t-dt)dt}e^{-i\mathbf{H}(t-2dt)dt}\ldots
e^{-i\mathbf{H}\left(t_{0}\right)dt}.$ (4)

Then each Trotter step further is decomposed into two qubit and single qubit
gates so that it can be implemented on the IBM machines using their native
gate set.

The determination of the phase diagram then proceeds as follows: (i) we
initialize the system in a state that is all up and with the magnetic field
equal to $B_{zinitial}$ and with a fixed value for $B_{x}$; (ii) we evolve the
system from $t_{0}$ to $t$ using the local adiabatic ramp for $B_{z}(t)$;
(iii) at each time step, we measure the magnetization; (iv) using the
magnetization, we determine the critical value of $B_{z}$, which corresponds
to the midpoint of the step in the magnetization between two successive $m$
quantum numbers; (v) we repeat these steps for a different value of $B_{x}$;
and (vi) we extrapolate the critical $B_{z}$ field to the limit where
$B_{x}\to 0$.

Extrapolation to find critical $B_{z}$ can be done by fitting polynomial
curves to the data. The $\sigma^{x}$ operator only connects states with
definite $m$ eigenvalues that are shifted by one: $n=m\pm 1$, for $\langle
n|\sum_{i}\sigma^{x}_{i}|m\rangle\neq 0$. Then, a simple argument using
perturbation theory shows that the perturbed energy eigenvalues are functions
of even powers of $B_{x}$ for small $B_{x}$ values. This means that when we
try to extrapolate the exact results for the critical $B_{z}$ field, we should
use a dependence on even powers of $B_{x}$ only. Hence, we include only
quadratic and quartic terms in the fitting curve for the data generated on a
classical computer via exact diagonalization.

For the data from a quantum computer, we instead fit with a linear regression,
because the noise on the quantum computer changes the behavior from even
powers of $B_{x}$ to a nearly linear dependence. When quantum computers become
capable of doing longer time runs, with less noise and decoherence, then we
can fit a quadratic polynomial without the linear term for smaller $B_{x}$
values to estimate the critical point in a more systematic way.

##  III Results

In order to demonstrate the technique we first examine a two-site system. At
large $B_{z}$, the ground state has all spins aligned in the up direction; the
calculation starts with this state. The system is time evolved using the
Trotter product formula using a local adiabatic ramp given in Eq. 3. The
integral produces $t(B_{z})$ with uniform steps in $B_{z}$. We convert to
$B_{z}(t)$ with uniform steps in $t$ by inverting the map and employing an
Akima spline, which preserves the shape (see Fig. 3). We choose $\gamma$ and
the number of time steps such that the time evolution spans the change in
magnetization by one full unit (see Fig. 5). We repeat the same procedure to
find the time evolution for each $B_{x}$ value. The time evolution is
implemented in the quantum simulation using two qubit and single qubit gates.
We decompose each Trotter step into the XY part, the $B_{x}$ part and the
$B_{z}$ part:

Figure 4: Quantum circuit for the evaluation of
$\exp\left(-i\mathcal{H}^{XY}_{12}dt\right)$. This is the time evolution
circuit for the XY part in each Trotter step for the two site system.
$w_{1}=\frac{{\mathbf{1}}-i\sigma^{x}}{\sqrt{2}}$, $w_{2}=w_{1}^{+}$,
$u=\exp{\left(i\frac{J}{4}\sigma^{x}dt\right)}$,
$v=\exp{\left(i\frac{J}{4}\sigma^{z}dt\right)}$.

$\displaystyle\mathbf{U}_{12}\left(t+dt,t\right)$
$\displaystyle=\exp{\left[-i[\frac{J}{4}\left(\sigma_{1}^{x}\sigma_{2}^{x}+\sigma_{1}^{y}\sigma_{2}^{y}\right)+\frac{1}{2}B_{x}\left(\sigma_{1}^{x}+\sigma_{2}^{x}\right)+\frac{1}{2}B_{z}(t)\left(\sigma_{1}^{z}+\sigma_{2}^{z}\right)]dt\right]}$
(5)
$\displaystyle\approx\exp{[-i\frac{B_{z}(t)}{2}\left(\sigma_{1}^{z}+\sigma_{2}^{z}\right)dt]}\exp{[-i\frac{B_{x}}{2}\left(\sigma_{1}^{x}+\sigma_{2}^{x}\right)dt]}\exp{[-i\frac{J}{4}\left(\sigma_{1}^{x}\sigma_{2}^{x}+\sigma_{1}^{y}\sigma_{2}^{y}\right)dt]}$
(6)

The XY part is further decomposed to implement in the quantum simulation using
two CNOTs (Vidal and Dawson, 2004) as shown in Fig. 4. The $B_{x}$ part and
$B_{z}$ part are implemented using single qubit gates.

For the two site case, we decrease $B_{z}$ from $B_{z}$ = 1.0J to $B_{z}$ =
0.0J to go through the first transition point (we have set $J=1$ in all our
calculations). We use $B_{x}$ values given by 0.02J, 0.03J, 0.04J, and 0.05J
(see Fig. 5). For the exact curve we use 1000 Trotter steps, but since we
cannot achieve high fidelity in currently available quantum quantum computers
for such large number of Trotter steps, we look for a similar trend in the
crossing point so that a fewer number of Trotter time steps is sufficient (see
Fig. 7). For a two site system the time evolution could be implemented with
three CNOTSVidal and Dawson (2004) to achieve high fidelity. But since these
short depth circuits are not available in general for large system size, we
consider explicit implementation of trotter circuit to enable comparison with
large system size. Later we also show results from a three CNOT version of the
circuit. With 20 Trotter steps the simulator data showed reasonable results.
We use an Akima spline to fit the magnetization versus $B_{z}$ data to have a
smooth curve allowing us to determine the transition point. From the simulator
data we find the crossing points where the magnetization is equal to 0.5. A
quartic fit was performed to the crossing points from the simulator data and
we obtain a critical value of $B_{z}=0.500J$. This result is reasonable, since
performing a quartic fit to the first four data points in the exact curve
yields an extrapolated value equal to 0.498J.

Figure 5: Magnetization versus $B_{z}$ data for a two-site system. We used a
local adiabatic ramp of 20 time steps with $\gamma$ =1.5, starting from the
all up state (left, middle) and all down state (right). Exact denotes the
magnetization curve with $B_{x}=0$. Data denotes the values obtained from the
IBM Santiago machine after readout error correction. Scaled data modifies the
error-corrected data so as to match the known end points. The leftmost panel
uses the optimal two-qubit circuit with three CNOTs for the positive
magnetization sector. The middle and rightmost panel uses the trotterised
circuit for the positive and negative magnetization sector respectively.
Figure 6: Experimental data (after readout error correction) for the
magnetization (positive) versus $B_{z}$ on a three-site system with a local
ramp starting from the ground state of all spins up on different machines; a)
IBM Yorktown b) IBM Montreal c) IBM Casablanca. We used 50 time steps and
$\gamma$ = 2 for the ramp.

We perform the quantum computer run on the IBM Santiago machine. The data
obtained from the quantum computer with readout error correction is shown in
Fig 5. As a secondary error mitigation technique, we scale the data to match
the known initial and final data points to the quantum computer data. This
stretches and shifts the data so that the end points have the correct values.
Such scaling is common to correct from decoherence and noise, and it improves
the data analysis. The experiment is repeated for different $B_{x}$ values and
the corresponding crossing points are plotted in the Fig. 7. Since the data
obtained was noisy we fitted a linear extrapolation curve to capture the trend
in the quantum computer data. The extrapolated critical $B_{z}$ value is
0.504J, which is close to the actual value of transition, which occurs at
0.5J.

Figure 7: Estimation of the quantum phase transition for a two-site model
using extrapolation to the $B_{x}\to 0$ limit. To obtain the critical value
for each $B_{x}$, we interpolate the data points (scaled) and determine where
the magnetization is equal to 0.5. For the exact simulation (green solid
circles), we have used local adiabatic ramp with 1000 time steps and $\gamma$
value 1.5. The simulator (blue triangles) and quantum computer (red solid
squares for circuit without optimization and black stars for circuit with
optimization) use 20 time steps. The exact value at $B_{x}=0.0$ is shown
explicitly (green solid circles) to indicate where the actual phase transition
is. The initial state has all up spins for the top panel and all down spins
for the bottom panel. The green dotted line shows the quartic fit of the exact
results to the first four data points. The blue dotted line is the quartic fit
to the simulator values. The red dotted line is the linear fit for the quantum
computer calculation with no circuit optimization. Black dotted line is the
quartic fit for optimized circuit data with three CNOTs. Figure 8: Estimation
of the quantum phase transition for three sites using extrapolation to the
$B_{x}\to 0$ limit. This case is for an initial state with all spins up. To
obtain the critical value for each $B_{x}$, we use an interpolation of the
scaled data points. Red squares corresponds to data from IBM Yorktown, brown
triangles for IBM Montreal and black circles for IBM Casablanca. The
corresponding colored dotted lines shows the linear fit for these data points.
For exact calculation (green circle), we use 1000 time steps and $\gamma=2$.
For the simulator (blue triangle) and the quantum computer, we use 50 steps.
The exact value at $B_{x}=0.0$ is shown explicitly (green circle) to indicate
where the phase transition is actually located. The quartic fit to the exact
and simulator data points is shown with the green and blue dotted lines
respectively.

For the second case, we examine the transition from $m=-1$ to $m=0$. While,
formally, this should be the same as the case for $m=1$ to $m=0$, because the
$|1\rangle$ state of a quantum computer is the excited state, decoherence
effects should be larger for this case. Here, the initial state has both spins
down. The procedure is similar to what we explained above. A quartic fit to
the simulator values gave the critical value to be -0.50 where as a quartic
fit to the first four data points of the exact crossings (for $\gamma$ =1.5
and 1000 Trotter steps) gave the extrapolated value to be $-0.498J$. The data
obtained from IBM quantum computer is shown in Fig. 5. The crossing points
were found from the scaled data for each $B_{x}$ values. A linear fit to the
the quantum computer data gave the critical value to be $-0.54J$.

For the two site model, we also performed the experiment in IBM Santiago
machine after optimising the circuits with a level three optimization in IBM
Qiskit transpiler. This reduced the number of CNOT gates to three for each
time. This is because any two qubit unitary operation can be represented using
three CNOT gates (Kraus and Cirac, 2001; Vidal and Dawson, 2004). The read-out
corrected data is shown in Fig. 5. The crossing points from these fixed depth
circuits are shown in Fig. 7. These values are more closer to the simulator
values than the trotter data as expected. A quartic fit to these data give the
critical $B_{z}$ value to be 0.491J for all spins aligned up case and -0.504J
for all spins aligned down situation. This kind of an efficient fixed depth
decomposition is not known in general for more than two qubits. But for
certain models efficient fixed depth circuit decompositions can be found
(Kökcü  _et al._ , 2021). These type of fixed depth circuits can improve
performance of our method by reducing the number of gates in adiabatic time
evolution.

Now, we move on to the three-site periodic system. We start with all spins up.
The time evolution circuit for the XY part is implemented pairwise using the
XY part of two qubit circuit for each Trotter step. The data obtained from the
quantum computer with readout error correction is shown in Fig. 6 along with
the scaled data so as to match the end points from the simulator data. The
extrapolations are shown in Fig. 8. A quartic fit to the exact values gives
the critical $B_{z}$ value to be 0.9987J. A quartic fit to the simulator
values gives the critical $B_{z}$ to be 0.982J. The linear fit to the
crossings from the scaled data of IBM quantum computer give the phase
transition point to be 1.11J for IBM Yorktown, 0.97J for IBM Montreal and
0.99J for the IBM Casablanca machines. The actual transition is at 1.0J. These
fitted values are reasonably close to the actual value.

##  IV Conclusion

In this work, we propose a method for finding zero-temperature phase diagrams
that is robust and can be carried out on quantum computers. The approach
requires us to introduce a symmetry breaking term into the Hamiltonian,
determine approximate phase diagrams for the symmetry-broken system, and then
extrapolate to the limit where the symmetry-breaking field vanishes. To verify
that this approach works, we have worked out practical details for how to run
these circuits on a quantum computer when the number of spins is 2 or 3. The
results from the quantum computers agree well with the exact results and are
able to predict the phase boundaries within a few percent. This illustrates
that the approach used here, based on adiabatic state preparation, can work on
NISQ machines and has the potential to be able to be applied to larger
systems, even ones where we do not know the phase diagram a priori.

Note that the case we examined here, the XY model in a $z$-oriented magnetic
field, is probably the most difficult problem to examine, because the number
of level crossings increases with the system size. For most quantum phase
transitions between different symmetry states, the number of phase boundaries
should depend only weakly on the system size.

In order to show that this approach also applies to larger systems, we
simulate the magnetization for a ten site system in Fig. 1 using a similar
local adiabatic time evolution for 1000 Trotter steps for $\gamma$ = 50.
Extracting the phase transitions using our methodology works well for such a
system, as can be seen by comparing the two lines in the figure.

## Acknowledgements

For this work, the planning, formal development, and circuit development
(A.F., J.K.F, and A.F.K.), as well as part of the manuscript writing (J.K.F.
and A.F.K.) was supported by the Department of Energy, Office of Basic Energy
Sciences, Division of Materials Sciences and Engineering under Grant No. DE-
SC0019469. The circuit execution and manuscript writing (A.F.) was supported
by the National Science Foundation under Grant No. DMR-1752713. E.Z. was
supported by the U.S. Department of Energy, Office of Science, Office of
Advanced Scientific Computing Research (ASCR), Quantum Computing Application
Teams (QCATS) program, under field work proposal number ERKJ347 for her work
in the summer of 2020 in developing the formalism and exact diagonalization
codes for this project. J. K. F. was also supported by the McDevitt bequest at
Georgetown. We acknowledge fruitful discussions with Brian Rost. We
acknowledge the use of IBMQ via the IBM Q Hub at NC State for this work. The
views expressed are those of the authors and do not reflect the official
policy or position of the IBM Q Hub at NC State, IBM or the IBM Q team. We
acknowledge the use of Qiskit software package (Aleksandrowicz  _et al._ ,
2019) for doing the quantum simulations. The data for the figures are
available at https://doi.org/10.5061/dryad.z8w9ghxdq

## References

  * Lloyd (1996) S. Lloyd, Science , 1073 (1996).
  * Abrams and Lloyd (1997) D. S. Abrams and S. Lloyd, Physical Review Letters 79, 2586 (1997).
  * Qin  _et al._ (2021) M. Qin, T. Schäfer, S. Andergassen, P. Corboz, and E. Gull, arXiv preprint arXiv:2104.00064 (2021).
  * Hubbard (1963) J. Hubbard, Proceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences 276, 238 (1963).
  * Farhi  _et al._ (2014) E. Farhi, J. Goldstone, and S. Gutmann, arXiv preprint arXiv:1411.4028 (2014).
  * Chen  _et al._ (2010) X. Chen, A. Ruschhaupt, S. Schmidt, A. del Campo, D. Guéry-Odelin, and J. G. Muga, Physical review letters 104, 063002 (2010).
  * Guéry-Odelin  _et al._ (2019) D. Guéry-Odelin, A. Ruschhaupt, A. Kiely, E. Torrontegui, S. Martínez-Garaot, and J. G. Muga, Reviews of Modern Physics 91, 045001 (2019).
  * Bak and Bruinsma (1982) P. Bak and R. Bruinsma, Physical Review Letters 49, 249 (1982).
  * Richerme  _et al._ (2013a) P. Richerme, C. Senko, S. Korenblit, J. Smith, A. Lee, R. Islam, W. C. Campbell, and C. Monroe, Physical review letters 111, 100506 (2013a).
  * Jordan and Wigner (1928) P. Jordan and E. Wigner, Z. Physik 47, 631 (1928).
  * Lieb  _et al._ (1961) E. Lieb, T. Schultz, and D. Mattis, Annals of Physics 16, 407 (1961).
  * Mbeng  _et al._ (2020) G. B. Mbeng, A. Russomanno, and G. E. Santoro, arXiv preprint arXiv:2009.09208 (2020).
  * Roland and Cerf (2002) J. Roland and N. J. Cerf, Physical Review A 65, 042308 (2002).
  * Richerme  _et al._ (2013b) P. Richerme, C. Senko, J. Smith, A. Lee, S. Korenblit, and C. Monroe, Physical Review A 88, 012334 (2013b).
  * Vidal and Dawson (2004) G. Vidal and C. M. Dawson, Physical Review A 69, 010301 (2004), arXiv: quant-ph/0307177.
  * Kraus and Cirac (2001) B. Kraus and J. I. Cirac, Physical Review A 63, 062309 (2001), arXiv: quant-ph/0011050.
  * Kökcü  _et al._ (2021) E. Kökcü, T. Steckmann, J. Freericks, E. F. Dumitrescu, and A. F. Kemper, arXiv preprint arXiv:2104.00728 (2021).
  * Aleksandrowicz  _et al._ (2019) G. Aleksandrowicz, T. Alexander, P. Barkoutsos, L. Bello, Y. Ben-Haim, D. Bucher, F. J. Cabrera-Hernández, J. Carballo-Franquis, A. Chen, C.-F. Chen, J. M. Chow, A. D. Córcoles-Gonzales, A. J. Cross, A. Cross, J. Cruz-Benito, C. Culver, S. D. L. P. González, E. D. L. Torre, D. Ding, E. Dumitrescu, I. Duran, P. Eendebak, M. Everitt, I. F. Sertage, A. Frisch, A. Fuhrer, J. Gambetta, B. G. Gago, J. Gomez-Mosquera, D. Greenberg, I. Hamamura, V. Havlicek, J. Hellmers, Ł. Herok, H. Horii, S. Hu, T. Imamichi, T. Itoko, A. Javadi-Abhari, N. Kanazawa, A. Karazeev, K. Krsulich, P. Liu, Y. Luh, Y. Maeng, M. Marques, F. J. Martín-Fernández, D. T. McClure, D. McKay, S. Meesala, A. Mezzacapo, N. Moll, D. M. Rodríguez, G. Nannicini, P. Nation, P. Ollitrault, L. J. O’Riordan, H. Paik, J. Pérez, A. Phan, M. Pistoia, V. Prutyanov, M. Reuter, J. Rice, A. R. Davila, R. H. P. Rudy, M. Ryu, N. Sathaye, C. Schnabel, E. Schoute, K. Setia, Y. Shi, A. Silva, Y. Siraichi, S. Sivarajah, J. A. Smolin, M. Soeken, H. Takahashi, I. Tavernelli, C. Taylor, P. Taylour, K. Trabing, M. Treinish, W. Turner, D. Vogt-Lee, C. Vuillot, J. A. Wildstrom, J. Wilson, E. Winston, C. Wood, S. Wood, S. Wörner, I. Y. Akhalwaya, and C. Zoufal, “Qiskit: An open-source framework for quantum computing,”  (2019).