$\displaystyle\theta_{j.k_{j}}^{(N)}:=e^{({\boldsymbol{q}})}_{k_{j}}\big{(}\theta_{N_{j-1}+1}^{(N)},\ldots,\theta_{N_{j}}^{(N)}\big{)},\qquad
1\leq k_{j}\leq n_{j},\qquad 1\leq j\leq r-1.$

Give a geometric interpretation of the commutative subalgebra
$QH_{n_{1},\ldots,n_{r}}(\beta,{\boldsymbol{h}})\subset
3QT_{n}(\beta,{\boldsymbol{h}})$ generated by the set of elements
$\theta_{j,k_{j}}^{(N)}$, $1\leq k_{j}\leq n_{j}$, $j=1,\ldots,r-1$.

###  A.4 Koszul dual of quadratic algebras and Betti numbers

Let $k$ be a field of zero characteristic, $F^{(n)}:=k\langle
x_{1},\ldots,x_{n}\rangle=\bigoplus_{j\geq 0}F_{j}^{(n)}$ be the free
associative algebra generated by $\\{x_{i},\,1\leq i\leq n\\}$. Let
$A=F^{(n)}/I$ be a quadratic algebra, i.e., the ideal of relations $I$ is
generated by the elements of degree $2$, $I\subset F_{2}^{(n)}$. Let
$F^{(n)*}=\operatorname{Hom}(F_{n},k)=\bigoplus_{j\geq 0}F_{j}^{(n)*}$ with a
multiplication induced by the rule $fg(ab)=f(a)g(b)$, $f\in F_{i}^{(n)*}$,
$g\in F_{j}^{(n)*}$, $a\in F_{i}^{(n)}$, $b\in F_{j}^{(n)}$. Let
$I_{2}^{\bot}=\\{f\in F_{2}^{(n)*},f(I_{2})=0\\}$, and denote by $I^{\bot}$
the two-sided ideal in $F^{(n)*}$ generated by the set $I_{2}^{\bot}$.

######  Definition A.22.

The Koszul $($or quadratic$)$ dual $A^{!}$ of a quadratic algebra $A$ is
defined to be $A^{!}:=F^{(n)*}/I^{\bot}$.

The Koszul dual of a quadratic algebra $A$ is a quadratic algebra and
$(A^{!})^{!}=A$.

######  Examples A.23.

(1) Let $A=F^{(n)}$ be the free associative algebra, then the quadratic dual

$\displaystyle A^{!}=k\langle y_{1},\ldots,y_{n}\rangle/(y_{i}y_{j},\,1\leq
i,j\leq n).$

(2) If $A=k[x_{1},\ldots,x_{n}]$ is the ring of polynomials, then

$\displaystyle A^{!}=k[y_{1},\ldots,y_{n}]/([y_{i},y_{j}]_{-},\,1\leq i,j\leq
n),$

where we put by definition $[y_{i},y_{j}]_{-}=y_{i}y_{j}+y_{j}y_{i}$ if
$i\not=j$, and $[y_{i},y_{i}]_{\\_}=y_{i}^{2}$.

(3) Let $A=F^{(n)}/(f_{1},\ldots,f_{r})$, where $f_{i}=\sum\limits_{1\leq
j,k\leq n}a_{ijk}x_{j}x_{k}$, $i=1,\ldots,r$ are linear independent elements
of degree $2$ in $F^{(n)}$. Then the quadratic dual of $A$ is equal to the
quotient algebra $A^{!}=k\langle y_{1},\dots,y_{n}\rangle/J$, where the ideal
$J=\langle g_{1},\ldots,g_{s}\rangle$, $s=n^{2}-r$, is generated by elements
$g_{m}=\sum\limits_{1\leq j,k\leq n}b_{mjk}y_{j}y_{k}$. The coefficients
$b_{mjk}$, $m=l,\ldots,s$, $1\leq j,k\leq n$, can be defined from the system
of linear equations $\sum\limits_{1\leq j,k\leq n}a_{ijk}b_{mjk}=0$,
$i=1,\ldots,r$, $m=1,\ldots,s$ (cf. [95, Chapter 5]).

Let $A=\bigoplus_{j\geq 0}A_{j}$ be a graded finitely generated algebra over
field $k$.

######  Definition A.24.

The Hilbert series of a graded algebra $A$ is defined to be the generating
function of dimensions of its homogeneous components: ${\rm
Hilb}(A,t)=\sum\limits_{k\geq 0}\dim A_{k}t^{k}$.

The Betti–Poincaré numbers $B_{A}(n,m)$ of a graded algebra $A$ are defined to
be $B_{A}(i,j):=\dim\operatorname{Tor}_{i}^{A}(k,k)_{j}$. The Poincaré series
of algebra $A$ is defined to be the generating function for the Betti numbers:
$P_{A}(s,t):=\sum\limits_{i\geq 0,j\geq 0}B_{A}(i,j)s^{i}t^{j}$.

Let $B$ is a $k$-module and $A$ is a $B$-module. The Betti number
$\beta_{ij}^{B(A)}$ of $A$ over $B$ is the rank of the free module $B[-j]$ the
$i$th module of a minimal resolution of $A$ over $B$ that is
$\beta_{ij}^{B}(A)=\dim_{k}{\rm Ext}_{i}^{B}(A,k)_{j}$. The graded Betti
series of $A$ over $B$ is the generating function

$\displaystyle{\rm
Betti}_{B}(A,x,y):=\sum_{i\in\mathbb{N},\,j\in\mathbb{Z}}\beta_{ij}^{B}(A)x^{i}y^{-j}\in\mathbb{Z}[y,y^{-1}][[x]].$

######  Definition A.25.

A quadratic algebra $A$ is called Koszul iff the Betti numbers $B_{A}(i,j)$
are equal to zero unless $i=j$.

It is well-known that ${\rm Hilb}(A,t)P_{A}(-1,t)=1$, and a quadratic algebra
$A$ is Koszul, if and only if $B_{A}(i,j)=0$ for all $i\not=j$. In this case
${\rm Hilb}(A,t)~{}{\rm Hilb}(A^{!},-t)=1$.

######  Example A.26.

Let $F_{n}^{(0)}$ be a quotient of the free associative algebra $F_{n}$ over
field $k$ with the set of generators $\\{x_{1},\ldots,x_{n}\\}$ by the two-
sided ideal generated by the set of elements
$\\{x_{1}^{2},\ldots,x_{n}^{2}\\}$. Then the algebra $F^{(0)}_{f}n$ is Koszul,
and ${\rm Hilb}\big{(}F_{n}^{(0)},t\big{)}={1+t\over 1-(n-1)t}$.

We refer the reader to a nice written book by A. Polishchuk and L. Positselski
[116] to read more widely in the theory of quadratic algebras, see also [94].

###  A.5 On relations in the algebra $\boldsymbol{Z_{n}^{0}}$

Let us define algebra $Z_{n}^{0}$ to be the subalgebra in $3T_{n}^{0}$
generated by the elements $u_{i,n}$, $1\leq i\leq n-1$. It is clear that
$Z_{n}^{0}$ is a ${\mathbb{S}}_{n-1}$-module,and well-known [46] that if one
sets ${\rm Hilb}(Z_{k}^{0},t):=Z_{k}(t)$, then

$\displaystyle{\rm Hilb}\big{(}3T_{n}^{(0)},t\big{)}=\prod_{k=2}^{n}Z_{k}(t).$

There exists a natural action of algebra $3T_{n-1}^{0}$ on that $Z_{n}^{0}$.
To define it, it’s convenient to put $x_{i}:=u_{i,n}$, $1\leq i\leq n-1$.

######  Definition A.27 (cf. [67] and Section 2.3.4).

Define operators $\nabla_{i,j},1\leq i<j\leq n-1$, which act on $Z_{n}^{0}$,
by the following rules

  * •

$\nabla_{i,j}(x_{k})=0$ if $k\not=i,j$,

  * •

$\nabla_{i,j}(x_{i})=x_{i}x_{j},\nabla_{i,j}(x_{j})=-x_{j}x_{i}$,

  * •

twisted Leibniz rule:

$\displaystyle\nabla_{i,j}(x\cdot y)=\nabla_{i,j}(x)\cdot
y+s_{i,j}(x)\cdot\nabla_{i,j}(y)$

for $x,y\in Z_{n}^{0}$ and all $1\leq i<j\leq n-1$. Here
$s_{i,j}\in{\mathbb{S}}_{n-1}$ denotes the transposition that interchanges $i$
and $j$ and fixes each $k\not=i,j$.

######  Proposition A.28.

The operators $\nabla_{i,j}$, $1\leq i<j\leq n-1$, satisfy all defining
relations of algebra $3T_{n-1}^{0}$.

In particular, the operators $\nabla_{i,j}$, satisfy the Coxeter and
Yang–Baxter relations:

  * •

Yang–Baxter relations:

$\displaystyle\nabla_{i,j}\nabla_{i,k}\nabla_{j,k}=\nabla_{j,k}\nabla_{i,k}\nabla_{i,j},$

  * •

Coxeter relations. Let $\nabla_{j}=\nabla_{j,j+1}$, $1\leq j\leq n-2$, then

$\displaystyle\nabla_{j}\nabla_{j+1}\nabla_{j}=\nabla_{j+1}\nabla_{j}\nabla_{j+1},\qquad[\nabla_{i},\nabla_{j}]=0\qquad\text{if}\quad|i-j|\geq
2.$

Therefore, for each $w\in{\mathbb{S}}_{n-1}$ one can define the operator
$\nabla_{w}=\nabla_{a_{1}}\cdots\nabla_{a_{l}}$, where the sequence
$(a_{1},\dots,a_{l})$ is a reduce decomposition of the element $w$.

Denote by ${\cal R}_{n}$ the kernel of the epimorphism $\iota\colon
Z_{n}\longrightarrow F_{n-1}$ given by $\iota(u_{k,n})=x_{k}$, where
$F_{n-1}:=\mathbb{Q}\langle x_{1},\dots,x_{n-1}\rangle$ denotes the free
associative algebra generated by the elements $x_{1},\dots$, $x_{n-1}$. There
exists the decomposition ${\cal R}_{n}=\bigoplus_{k\geq 2}{\cal R}_{n,k}$,
where ${\cal R}_{n,k}$ denotes the degree $k$ part of ${\cal R}_{n}$. We
denote by $r_{n,k}$ the dimension of the space ${\cal
R}_{n,k}/\sum\limits_{j=1}^{n-1}(x_{j,n}{\cal R}_{n,k-1}+{\cal
R}_{n,k-1}x_{j,n})$, and put $r_{n}:=(r_{n,2},r_{n,3},\dots)$.

######  Example A.29.

$\displaystyle r_{3}=(2,1),\qquad r_{4}=(3,3,2),\qquad r_{5}=(4,6,8,6,3),$
$\displaystyle r_{6}=(5,10,20,30,39,40,39,30,20,10,4).$

######  Remark A.30.

The same formulas for the action of $\nabla_{i,j}$ on $Z_{n}^{0}$ given in
Definition A.27, define an action of operators $\nabla_{i,j}$ on the free
algebra $F_{n-1}$. In this way we obtain a representation of the algebra
$3T_{n-1}$ on that $F_{n-1}$, cf. Section 2.3.4.

Let us denote by ${\widehat{F}}_{n}$ the quotient of the free associative
algebra $F_{n}=\langle x_{1},\ldots,x_{n}\rangle$ by the two-sided ideal
generated by the elements $\\{x_{i}^{2}x_{j}-x_{j}x_{i}^{2},\,1\leq i,j\leq
n\\}$. It is not difficult to see that the operators $\nabla_{i,j}$, $1\leq
i<j\leq n$, define a representation of the algebra $3T_{n}^{0}$ on that
${\widehat{F}}_{n}$. Note that

$\displaystyle{\widehat{F}}_{n}\backsimeq
F_{n-1}\otimes\mathbb{Z}[y_{1},y_{2},\ldots,y_{n}],$

where $\deg(y_{1})=1$, $\deg(y_{j})=2$, $j=2,\ldots,n$. Therefore,

$\displaystyle{\rm
Hilb}\big{(}{\widehat{F}}_{n},t\big{)}={1\over(1-t)(1-(n-1)t)(1-t^{2})^{n-1}}.$

######  Conjecture A.31.

The kernel ${\cal R}_{n}$ coincides with the two-sided ideal in the free
algebra $F_{n-1}$ generated by elements of the form
$\prod\limits_{k=1}^{s}\nabla_{i_{k},j_{k}}(x_{a}^{2})$ for some positive
integers $s$ and $1\leq a\leq n-1$.

In other words, the all relations in the algebra $Z_{n}^{0}$ are consequence
of the following relations $u\nabla_{w}(x_{1}^{2})=0$ for some
$u,w\in{\mathbb{S}}_{n-1}$.

######  Challenge A.32.

  1. (1)

Compute the numbers $r_{n,k}$.

  2. (2)

Prove (or disprove) that there exists a positive integer
$k_{\max}:=k_{\max}^{(n)}$ such that $r_{n,k_{\max}}\not=0$, but $r_{n,k}=0$
for all integers $k>k_{\max}^{(n)}$.

  3. (3)

These examples suggest that there might be exist a certain symmetry
$r_{n,k}=r_{n,k_{\max}-k+2}$, if $3\leq k<k_{\max}$, between the numbers
$r_{n,k}$, and moreover, $r_{n,k_{\max}}=r_{n,2}-1$. If so, how to explain
these properties of the numbers $r_{n,k}$?

We expect that if $n\geq 4$, then $k_{\max}^{(n)}=2{n-2\choose[(n-2)/2]}$.

######  Example A.33 (cyclic relations in the algebra $Z_{n}^{0}$).

The following relation

$\displaystyle\prod_{j=1}^{n-1}\nabla_{n-j,n-j+1}\big{(}x_{1}^{2}\big{)}=\sum_{i=1}^{n}x_{i}\left(\prod_{a=i+1}^{n}x_{a}\prod_{a=1}^{i-1}x_{a}\right)x_{i}$

holds in the free algebra $F_{n}$. Therefore in the algebra $Z_{n}^{0}$ one
has the following cyclic relation of the degree $n$ and length $n-1$:

$\displaystyle\sum_{i=1}^{n-1}x_{i}\left(\prod_{a=i+1}^{n-1}x_{a}\prod_{a=1}^{i-1}x_{a}\right)x_{i}=0.$

If $n\geq 5$, then by applying to monomials of the form
$\prod\limits_{j=2}^{n-1}\nabla_{n-j,n-j+1}(x_{1}^{2})$ the action of either
operators $\nabla_{a,n-1}$, $2\leq a\leq n-3$, or those $\nabla_{a,b}$, $1\leq
a\leq b-2\leq n-4$, new, more complicated relations in the algebra
$Z_{n}^{0}$, i.e., non-cyclic relations, can appear. These are relations of
the length $2n$ and degree $n+1$ in the algebra $Z_{n}^{0}$. Conjecturally all
relations in the algebra $Z_{n}^{0}$ can be obtained by this method.

######  Proposition A.34.

$\displaystyle r_{n,k}=(k-2)!{n-1\choose k-1},\qquad 2\leq k\leq 5,$
$\displaystyle r_{n,6}=4!{n-1\choose 5}+3{n-1\choose 4},\qquad
r_{n,7}=5!{n-1\choose 6}+40{n-1\choose 5},$ $\displaystyle
r_{n,8}=6!{n-1\choose 7}+430{n-1\choose 6}+39{n-1\choose 5}.$

####  A.5.1 Hilbert series $\boldsymbol{{\rm Hilb}\big{(}3T_{n}^{0},t\big{)}}$
and $\boldsymbol{{\rm Hilb}\big{(}\big{(}3T_{n}^{0}\big{)}^{!},t\big{)}}$:
Examples646464All computations in this section were performed by using the
computer system Bergman, except computations of ${\rm Hilb}(3T_{6}^{0},t)$ in
degrees from twelfth till fifteenth. The last computations were made by J.
Backelin, S. Lundqvist and J.-E. Roos from Stockholm University, using the
computer algebra system aalg mainly developed by S. Lundqvist.

######  Examples A.35.

$\displaystyle{\rm Hilb}\big{(}3T_{3}^{0},t\big{)}=[2]^{2}[3],\qquad{\rm
Hilb}\big{(}3T_{4}^{0},t\big{)}=[2]^{2}[3]^{2}[4]^{2},\qquad{\rm
Hilb}\big{(}3T_{5}^{0},t\big{)}=[4]^{4}[5]^{2}[6]^{4},$ $\displaystyle{\rm
Hilb}\big{(}3T_{6}^{0},t\big{)}=(1,15,125,765,3831,16605,64432,228855,755777,2347365,6916867,$
$\displaystyle\hphantom{{\rm
Hilb}\big{(}3T_{6}^{0},t\big{)}=(}{}19468980,52632322,137268120,346652740,850296030,\dots)$
$\displaystyle\hphantom{{\rm Hilb}\big{(}3T_{6}^{0},t\big{)}}{}={\rm
Hilb}\big{(}3T_{5}^{0},t\big{)}(1,5,20,70,220,640,1751,4560,11386,27425,64015,$
$\displaystyle\hphantom{{\rm
Hilb}\big{(}3T_{5}^{0},t\big{)}=(}{}145330,321843,696960,1478887,3080190,\dots),$
$\displaystyle{\rm Hilb}\big{(}3T_{7}^{0},t\big{)}={\rm
Hilb}\big{(}3T_{6}^{0},t\big{)}(1,6,30,135,560,2190,8181,29472,103032,$
$\displaystyle\hphantom{{\rm
Hilb}\big{(}3T_{7}^{0},t\big{)}=(}{}351192,1170377,\dots),$ $\displaystyle{\rm
Hilb}\big{(}3T_{8}^{0},t\big{)}={\rm
Hilb}\big{(}3T_{7}^{0},t\big{)}(1,7,42,231,1190,5845,27671,127239,571299,2514463,$
$\displaystyle{\rm
Hilb}\big{(}\big{(}3T_{3}^{0}\big{)}^{!},t\big{)}(1-t)=(1,2,2,1),\qquad{\rm
Hilb}\big{(}\big{(}3T_{4}^{0}\big{)}^{!},t\big{)}(1-t)^{2}=(1,4,6,2,-5,-4,-1),$
$\displaystyle{\rm
Hilb}\big{(}\big{(}3T_{5}^{0}\big{)}^{!},t\big{)}(1-t)^{2}=(1,8,26,40,19,-18,-22,-8,-1),$
$\displaystyle{\rm
Hilb}\big{(}\big{(}3T_{6}^{0}\big{)}^{!},t\big{)}(1-t)^{3}=(1,12,58,134,109,-112,-245,-73,68,50,12,1),$
$\displaystyle{\rm
Hilb}\big{(}\big{(}3T_{7}^{0}\big{)}^{!},t\big{)}(1-t)^{3}=(1,\\!18,136,545,1169,1022,\\!-624,\\!-1838,\\!-837,312,374,123,\\!18,1).$

We expect that ${\rm Hilb}((3T_{n}^{0})^{!},t)$ is a rational function with
the only pole at $t=1$ of order $[n/2]$, and the polynomial ${\rm
Hilb}((3T_{n}^{0})^{!},t)(1-t)^{[n/2]}$ has degree equals to $[5n/2]-4$, if
$n\geq 2$.

###  A.6 Summation and Duality transformation formulas [63]

Summation formula. Let $a_{1}+\cdots+a_{m}=b$. Then

$\displaystyle\sum_{i=1}^{m}[a_{i}]\left(\prod_{j\not=i}{{[x_{i}-x_{j}+a_{j}]\over[x_{i}-x_{j}]}}\right){{[x_{i}+y-b]\over[x_{i}+y]}}=[b]\prod_{1\leq
i\leq m}{{[y+x_{i}-a_{i}]\over[y+x_{i}]}}.$

Duality transformation, case $N=1$. Let
$a_{1}+\cdots+a_{m}=b_{1}+\cdots+b_{n}$. Then

$\displaystyle\sum_{i=1}^{m}[a_{i}]\prod_{j\not=i}{{[x_{i}-x_{j}+a_{j}]\over[x_{i}-x_{j}]}}\prod_{1\leq
k\leq n}{{[x_{i}+y_{k}-b_{k}]\over[x_{i}+y_{k}]}}$
$\displaystyle\qquad{}=\sum_{k=1}^{n}[b_{k}]\prod_{l\not=k}{{[y_{k}-y_{l}+b_{l}]\over[y_{k}-y_{l}]}}\prod_{1\leq
i\leq m}{{[y_{k}+x_{i}-a_{i}]\over[y_{k}+x_{i}]}}.$

### Acknowledgments

I would like to express my deepest thanks to Professor Toshiaki Maeno for many
years fruitful collaboration. I’m also grateful to Professors Yu. Bazlov, I.
Burban, B. Feigin, S. Fomin, A. Isaev, M. Ishikawa, M. Noumi, B. Shapiro and
Dr. Evgeny Smirnov for fruitful discussions on different stages of writing
[72].

My special thanks are to Professor Anders Buch for sending me the programs for
computation of the $\beta$-Grothendieck and double $\beta$-Grothendieck
polynomials. Many results and examples in the present paper have been checked
by using these programs, and Professor Ole Warnaar (University of Queenslad)
for a warm hospitality and a kind interest and fruitful discussions of some
results from [72] concerning hypergeometric functions.

These notes represent an update version of Section 5 of my notes [72], which
have been designed as an extended version of [66], and are based on my talks
given at656565To save place I will mention only the Universities and
Institutions which I visited and gave talks/lectures, starting from the year
2010. I want to thank the all Universities and Institutions which I visited,
for warm hospitality and financial support.

  * •

The Simons Center for Geometry and Physics, Stony Brook University, USA,
January 2010;

  * •

Department of Mathematical Sciences at the Indiana University – Purdue
University Indianapolis (IUPUI), USA, Departmental Colloquium, January 2010;

  * •

The Research School of Physics and Engineering, Australian National University
(ANU), Canberra, ACT 0200, Australia, April 2010;

  * •

The Institut de Mathématiques de Bourgogne, CNRS U.M.R. 5584, Université de
Bourgogne, France, October 2010;

  * •

The School of Mathematics and Statistics University of Sydney, NSW 2006,
Australia, November 2010;

  * •

The Institute of Advanced Studies at NTU, Singapore, 5th Asia-Pacific Workshop
on Quantum Information Science in conjunction with the Festschrift in honor of
Vladimir Korepin, May 2011;

  * •

The Center for Quantum Geometry of Moduli Spaces, Faculty of Science, Aarhus
University, Denmark, August 2011;

  * •

The Higher School of Economy (HES), and The Moscow State University, Russia,
November 2011;

  * •

The Research Institute for Mathematical Sciences (RIMS), the Conference
Combinatorial representation theory, Japan, October 2011;

  * •

The Korean Institute for Advanced Study (KIAS), Seoul, South Korea, May/June,
2012, August 2014;

  * •

The Kavli Institute for the Physics and Mathematics of the Universe (IPMU),
Tokyo, August 2013, August 2015;

  * •

The University of Queensland, Brisbane, Australia, October–November 2013;

  * •

The University of Warwick, the University of Nottingham and the University of
York, Clay Mathematics Institute, Oxford, United Kingdom, May/June 2015.

I would like to thank Professors Leon Takhtajan and Oleg Viro (Stony Brook),
Jørgen E. Andersen (CGM, Aarhus University), Bumsig Kim (KIAS, Seoul),
Vladimir Matveev (Université de Bourgogne), Vitaly Tarasov (IUPUI, USA),
Vladimir Bazhanov (ANU), Alexander Molev (University of Sydney), Sergey Lando
(HES, Moscow), Sergey Oblezin (Nottingham, UK), Maxim Nazarov (York, UK),
Kyoji Saito (IPMU, Tokyo), Kazuhiro Hikami (Kyushu University), Reiho Sakamoto
(Tokyo University of Science), Junichi Shiraishi (University of Tokyo) for
invitations and hospitality during my visits of the Universities and the
Institutes listed above.

Part of results stated in Section 2, II has been obtained during my visit of
the University of Sydney, Australia. I would like to thank Professors A. Molev
and A. Isaev for the keen interest and useful comments on my paper.

## References

  * [1] Aguiar M., On the associative analog of Lie bialgebras, J. Algebra 244 (2001), 492–532.
  * [2] Albenque M., Nadeau P., Growth function for a class of monoids, in 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), Discrete Math. Theor. Comput. Sci. Proc., AK, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2009, 25–38.
  * [3] Arnold V.I., The cohomology ring of the colored braid group, Math. Notes 5 (1969), 138–140.
  * [4] Astashkevich A., Sadov V., Quantum cohomology of partial flag manifolds $F_{n_{1}\cdots n_{k}}$, Comm. Math. Phys. 170 (1995), 503–528, hep-th/9401103.
  * [5] Bardakov V.G., The virtual and universal braids, Fund. Math. 184 (2004), 1–18, math.GR/0407400.
  * [6] Bar-Natan D., Vassiliev and quantum invariants of braids, in The Interface of Knots and Physics (San Francisco, CA, 1995), Proc. Sympos. Appl. Math., Vol. 51, Amer. Math. Soc., Providence, RI, 1996, 129–144, q-alg/9607001.
  * [7] Bartholi L., Enriquez B., Etingof P., Rains E., Groups and algebras corresponding to the Yang–Baxter equations, J. Algebra 305 (2006), 742–764, math.RA/0509661.
  * [8] Bazlov Yu., Nichols–Woronowicz algebra model for Schubert calculus on Coxeter groups, J. Algebra 297 (2006), 372–399, math.QA/0409206.
  * [9] Belavin A.A., Drinfeld V.G., Triangle equations and simple Lie algebras, Classic Reviews in Mathematics and Mathematical Physics, Vol. 1, Harwood Academic Publishers, Amsterdam, 1998.
  * [10] Benson B., Chakrabarty D., Tetali P., $G$-parking functions, acyclic orientations and spanning trees, Discrete Math. 310 (2010), 1340–1353, arXiv:0801.1114.
  * [11] Berget A., Products of linear forms and Tutte polynomials, European J. Combin. 31 (2010), 1924–1935, arXiv:0906.4774.
  * [12] Bershtein M., Dotsenko V., Khoroshkin A., Quadratic algebras related to the bi-Hamiltonian operad, Int. Math. Res. Not. 2007 (2007), rnm122, 30 pages, math.RA/0607289.
  * [13] Billey S.C., Jockusch W., Stanley R.P., Some combinatorial properties of Schubert polynomials, J. Algebraic Combin. 2 (1993), 345–374.
  * [14] Birman J.S., Brendle T.E., Braids: a survey, in Handbook of Knot Theory, Elsevier B.V., Amsterdam, 2005, 19–103, math.GT/0409205.
  * [15] Birman J.S., Ko K.H., Lee S.J., A new approach to the word and conjugacy problem in the braid groups, Adv. Math. 139 (1998), 322–353, math.GT/9712211.
  * [16] Blasiak J., Liu R.I., Mészáros K., Subalgebras of the Fomin–Kirillov algebra, arXiv:1310.4112.
  * [17] Bourbaki N., Lie groups and Lie algebras, Chapters 4–6, Elements of Mathematics (Berlin), Springer-Verlag, Berlin, 2002.
  * [18] Bressoud D.M., Proofs and confirmations. The story of the alternating sign matrix conjecture, MAA Spectrum, Mathematical Association of America, Washington, DC, Cambridge University Press, Cambridge, 1999.
  * [19] Brualdi R., Kirkland S., Aztec diamonds and digraphs, and Hankel determinants of Schröder numbers, J. Combin. Theory Ser. B 94 (2005), 334–351.
  * [20] Chan C.S., Robbins D.P., On the volume of the polytope of doubly stochastic matrices, Experiment. Math. 8 (1999), 291–300, math.CO/9806076.
  * [21] Chan C.S., Robbins D.P., Yuen D.S., On the volume of a certain polytope, Experiment. Math. 9 (2000), 91–99, math.CO/9810154.
  * [22] Chaumont L., Liu R., Coding multitype forests: application to the law of the total progeny of branching forests and to enumeration, arXiv:1302.0195.
  * [23] Chen W.Y.C., A general bijective algorithm for trees, Proc. Nat. Acad. Sci. USA 87 (1990), 9635–9639.
  * [24] Cherednik I., Double affine Hecke algebras, London Mathematical Society Lecture Note Series, Vol. 319, Cambridge University Press, Cambridge, 2005.
  * [25] Chervov A., Falqui G., Manin matrices and Talalaev’s formula, J. Phys. A: Math. Theor. 41 (2008), 194006, 28 pages, arXiv:0711.2236.
  * [26] Clark E., Ehrenborg R., Explicit expressions for the extremal excedance set statistics, European J. Combin. 31 (2010), 270–279.
  * [27] Cohen F.R., Pakianathan J., Vershinin V.V., Wu J., Basis-conjugating automorphisms of a free group and associated Lie algebras, in Groups, Homotopy and Configuration Spaces, Geom. Topol. Monogr., Vol. 13, Geom. Topol. Publ., Coventry, 2008, 147–168, math.GR/0610946.
  * [28] Cordovil R., A commutative algebra for oriented matroids, Discrete Comput. Geom. 27 (2002), 73–84.
  * [29] Deift P., Li L.C., Nanda T., Tomei C., The Toda flow on a generic orbit is integrable, Comm. Pure Appl. Math. 39 (1986), 183–232.
  * [30] Deligne P., Les immeubles des groupes de tresses généralisés, Invent. Math. 17 (1972), 273–302.
  * [31] Deutsch E., Sagan B.E., Congruences for Catalan and Motzkin numbers and related sequences, J. Number Theory 117 (2006), 191–215, math.CO/0407326.
  * [32] Di Francesco P., A refined Razumov–Stroganov conjecture, J. Stat. Mech. Theory Exp. 2004 (2004), P08009, 16 pages, cond-mat/0407477.
  * [33] Di Francesco P., Zinn-Justin P., The quantum Knizhnik–Zamolodchikov equation, generalized Razumov–Stroganov sum rules and extended Joseph polynomials, J. Phys. A: Math. Gen. 38 (2005), L815–L822, math-ph/0508059.
  * [34] Di Francesco P., Zinn-Justin P., Inhomogeneous model of crossing loops and multidegrees of some algebraic varieties, Comm. Math. Phys. 262 (2006), 459–487, math-ph/0412031.
  * [35] Dunkl C.F., Differential-difference operators associated to reflection groups, Trans. Amer. Math. Soc. 311 (1989), 167–183.
  * [36] Dunkl C.F., Harmonic polynomials and peak sets of reflection groups, Geom. Dedicata 32 (1989), 157–171.
  * [37] Eğecioğlu Ö., Redmond T., Ryavec C., From a polynomial Riemann hypothesis to alternating sign matrices, Electron. J. Combin. 8 (2001), no. 1, 36, 51 pages.
  * [38] Erdélyi A., Etherington I.M.H., Some problems of non-associative combinatorics (2), Edinburgh Math. Notes 32 (1940), 7–14.
  * [39] Escobar L., Mészáros K., Subword complexes via triangulations of root polytopes, arXiv:1502.03997.
  * [40] Felder G., Pasquier V., A simple construction of elliptic $R$-matrices, Lett. Math. Phys. 32 (1994), 167–171, hep-th/9402011.
  * [41] Fomin S., Gelfand S., Postnikov A., Quantum Schubert polynomials, J. Amer. Math. Soc. 10 (1997), 565–596.
  * [42] Fomin S., Kirillov A.N., Yang–Baxter equation, symmetric functions and Grothendieck polynomials, hep-th/9306005.
  * [43] Fomin S., Kirillov A.N., The Yang–Baxter equation, symmetric functions, and Schubert polynomials, Discrete Math. 153 (1996), 123–143.
  * [44] Fomin S., Kirillov A.N., Reduced words and plane partitions, J. Algebraic Combin. 6 (1997), 311–319.
  * [45] Fomin S., Kirillov A.N., Quadratic algebras, Dunkl elements, and Schubert calculus, in Advances in Geometry, Progr. Math., Vol. 172, Birkhäuser Boston, Boston, MA, 1999, 147–182.
  * [46] Fomin S., Procesi C., Fibered quadratic Hopf algebras related to Schubert calculus, J. Algebra 230 (2000), 174–183.
  * [47] Fulton W., Universal Schubert polynomials, Duke Math. J. 96 (1999), 575–594, alg-geom/9702012.
  * [48] Ganter N., Ram A., Generalized Schubert calculus, J. Ramanujan Math. Soc. 28A (2013), 149–190, arXiv:1212.5742.
  * [49] Gel’fand I.M., Rybnikov G.L., Algebraic and topological invariants of oriented matroids, Soviet Math. Dokl. 40 (1990), 148–152.
  * [50] Gessel I.M., A combinatorial proof of the multivariable Lagrange inversion formula, J. Combin. Theory Ser. A 45 (1987), 178–195.
  * [51] Gessel I.M., Sagan B.E., The Tutte polynomial of a graph, depth-first search, and simplicial complex partitions, Electron. J. Combin. 3 (1996), no. 2, 9, 36 pages.
  * [52] Ginzburg V., Kapranov M., Vasserot E., Elliptic algebras and equivariant elliptic cohomology, q-alg/9505012.
  * [53] Givental A., Stationary phase integrals, quantum Toda lattices, flag manifolds and the mirror conjecture, in Topics in singularity theory, Amer. Math. Soc. Transl. Ser. 2, Vol. 180, Amer. Math. Soc., Providence, RI, 1997, 103–115, alg-geom/9612001.
  * [54] Gorbounov V., Rimányi R., Tarasov V., Varchenko A., Quantum cohomology of the cotangent bundle of a flag variety as a Yangian Bethe algebra, J. Geom. Phys. 74 (2013), 56–86, arXiv:1204.5138.
  * [55] Haiman M.D., Conjectures on the quotient ring by diagonal invariants, J. Algebraic Combin. 3 (1994), 17–76.
  * [56] Hikami K., Wadati M., Topics in quantum integrable systems, J. Math. Phys. 44 (2003), 3569–3594.
  * [57] Hivert F., Novelli J.-C., Thibon J.-Y., Commutative combinatorial Hopf algebras, J. Algebraic Combin. 28 (2008), 65–95, math.CO/0605262.
  * [58] Hurtado F., Noy M., Graph of triangulations of a convex polygon and tree of triangulations, Comput. Geom. 13 (1999), 179–188.
  * [59] Isaev A.P., Kirillov A.N., Bethe subalgebras in Hecke algebra and Gaudin models, Lett. Math. Phys. 104 (2014), 179–193, arXiv:1302.6495.
  * [60] Isaev A.P., Kirillov A.N., Tarasov V.O., Bethe subalgebras in affine Birman–Murakami–Wenzl algebras and flat connections for $q$-KZ equations, arXiv:1510.05374.
  * [61] Jensen C., McCammond J., Meier J., The integral cohomology of the group of loops, Geom. Topol. 10 (2006), 759–784, arXiv:0903.0140.
  * [62] Jucys A.-A.A., Symmetric polynomials and the center of the symmetric group ring, Rep. Math. Phys. 5 (1974), 107–112.
  * [63] Kajihara Y., Noumi M., Multiple elliptic hypergeometric series. An approach from the Cauchy determinant, Indag. Math. (N.S.) 14 (2003), 395–421, math.CA/0306219.
  * [64] Kaneko M., Poly-Bernoulli numbers, J. Théor. Nombres Bordeaux 9 (1997), 221–228.
  * [65] Kawahara Y., On matroids and Orlik–Solomon algebras, Ann. Comb. 8 (2004), 63–80.
  * [66] Kirillov A.N., On some quadratic algebras, in L.D. Faddeev’s Seminar on Mathematical Physics, Amer. Math. Soc. Transl. Ser. 2, Vol. 201, Amer. Math. Soc., Providence, RI, 2000, 91–113, q-alg/9705003.
  * [67] Kirillov A.N., On some quadratic algebras: Jucys–Murphy and Dunkl elements, in Calogero–Moser–Sutherland Models (Montréal, QC, 1997), CRM Ser. Math. Phys., Springer, New York, 2000, 231–248.
  * [68] Kirillov A.N., $t$-deformations of quantum Schubert polynomials, Funkcial. Ekvac. 43 (2000), 57–69, math.QA/9802001.
  * [69] Kirillov A.N., Ubiquity of Kostka polynomials, in Physics and Combinatorics 1999 (Nagoya), World Sci. Publ., River Edge, NJ, 2001, 85–200, math.QA/9912094.
  * [70] Kirillov A.N., On some algebraic and combinatorial properties of Dunkl elements, Internat. J. Modern Phys. B 26 (2012), 1243012, 28 pages.
  * [71] Kirillov A.N., Notes on Schubert, Grothendieck and Key polynomials, arXiv:1501.07337.
  * [72] Kirillov A.N., On some quadratic algebras. II, unpublished.
  * [73] Kirillov A.N., Maeno T., Noncommutative algebras related with Schubert calculus on Coxeter groups, European J. Combin. 25 (2004), 1301–1325, math.CO/0310068.
  * [74] Kirillov A.N., Maeno T., Braided differential structure on Weyl groups, quadratic algebras, and elliptic functions, Int. Math. Res. Not. 2008 (2008), no. 14, rnn046, 23 pages, arXiv:0709.4599.
  * [75] Kirillov A.N., Maeno T., Extended quadratic algebra and a model of the equivariant cohomology ring of flag varieties, St. Petersburg Math. J. 22 (2011), 447–462, arXiv:0712.2580.
  * [76] Kirillov A.N., Maeno T., A note on quantum $K$-theory of flag varieties, in preparation.
  * [77] Knutson A., Miller E., Gröbner geometry of Schubert polynomials, Ann. of Math. 161 (2005), 1245–1318, math.AG/0110058.
  * [78] Knutson A., Miller E., Yong A., Gröbner geometry of vertex decompositions and of flagged tableaux, J. Reine Angew. Math. 630 (2009), 1–31, math.AG/0502144.
  * [79] Koornwinder T.H., On the equivalence of two fundamental theta identities, Anal. Appl. (Singap.) 12 (2014), 711–725, arXiv:1401.5368.
  * [80] Kostant B., The solution to a generalized Toda lattice and representation theory, Adv. Math. 34 (1979), 195–338.
  * [81] Krattenthaler C., Determinants of (generalised) Catalan numbers, J. Statist. Plann. Inference 140 (2010), 2260–2270, arXiv:0709.3044.
  * [82] Kreweras G., Une famille de polynômes ayant plusieurs propriétés énumeratives, Period. Math. Hungar. 11 (1980), 309–320.
  * [83] Kuperberg G., Symmetry classes of alternating-sign matrices under one roof, Ann. of Math. 156 (2002), 835–866, math.CO/0008184.
  * [84] Lascoux A., Anneau de Grothendieck de la variété de drapeaux, in The Grothendieck Festschrift, Vol. III, Progr. Math., Vol. 88, Birkhäuser Boston, Boston, MA, 1990, 1–34.
  * [85] Lascoux A., Leclerc B., Thibon J.-Y., Flag varieties and the Yang–Baxter equation, Lett. Math. Phys. 40 (1997), 75–90, q-alg/9607015.
  * [86] Lascoux A., Schützenberger M.P., Symmetry and flag manifolds, in Invariant Theory (Montecatini, 1982), Lecture Notes in Math., Vol. 996, Springer, Berlin, 1983, 118–144.
  * [87] Lascoux A., Schützenberger M.P., Symmetrization operators in polynomial rings, Funct. Anal. Appl. 21 (1987), 324–326.
  * [88] Lazard M., Sur les groupes de Lie formels à un paramètre, Bull. Soc. Math. France 83 (1955), 251–274.
  * [89] Liu R.I., On the commutative quotient of Fomin–Kirillov algebras, arXiv:1409.4872.
  * [90] Loday J.-L., Inversion of integral series enumerating planar trees, Sém. Lothar. Combin. 53 (2005), B53d, 16 pages, math.CO/0403316.
  * [91] Loday J.-L., The multiple facets of the associahedron, available at hptt://www-irma.u-strasbg.fr/~loday/PAPERS/MultFAsENG2.pdf.
  * [92] Macdonald I.G., Notes on Schubert polynomials, Publications du LaCIM, Vol. 6, Université du Québec à Montréal, 1991.
  * [93] Macdonald I.G., Symmetric functions and Hall polynomials, 2nd ed., Oxford Mathematical Monographs, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York, 1995.
  * [94] Manin Yu.I., Some remarks on Koszul algebras and quantum groups, Ann. Inst. Fourier (Grenoble) 37 (1987), 191–205.
  * [95] Manin Yu.I., Quantum groups and noncommutative geometry, Université de Montréal, Centre de Recherches Mathématiques, Montreal, QC, 1988.
  * [96] Mathieu O., The symplectic operad, in Functional Analysis on the Eve of the 21st Century, Vol. 1 (New Brunswick, NJ, 1993), Progr. Math., Vol. 131, Birkhäuser Boston, Boston, MA, 1995, 223–243.
  * [97] Matsumoto S., Novak J., Unitary matrix integrals, primitive factorizations, and Jucys–Murphy elements, in 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010), Discrete Math. Theor. Comput. Sci. Proc., AN, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2010, 403–411, arXiv:1005.0151.
  * [98] Merino C., Ramírez-Ibáñez M., Rodríguez-Sánchez G., The Tutte polynomial of some matroids, Int. J. Comb. 2012 (2012), 430859, 40 pages, arXiv:1203.0090.
  * [99] Mészáros K., Root polytopes, triangulations, and the subdivision algebra. I, Trans. Amer. Math. Soc. 363 (2011), 4359–4382, arXiv:0904.2194.
  * [100] Mészáros K., Root polytopes, triangulations, and the subdivision algebra. II, Trans. Amer. Math. Soc. 363 (2011), 6111–6141, arXiv:0904.3339.
  * [101] Mészáros K., Product formula for volumes of flow polytopes, 2015, Proc. Amer. Math. Soc. 143 (2015), 937–954, arXiv:1111.5634.
  * [102] Mészáros K., $h$-polynomials via reduced forms, arXiv:1407.2685.
  * [103] Mészáros K., Morales A.H., Flow polytopes of signed graphs and the Kostant partition function, Int. Math. Res. Not. 2015 (2015), 830–871, arXiv:1208.0140.
  * [104] Mészáros K., Panova G., Postnikov A., Schur times Schubert via the Fomin–Kirillov algebra, Electron. J. Combin. 21 (2014), 1.39, 22 pages, arXiv:1210.1295.
  * [105] Miller E., Sturmfels B., Combinatorial commutative algebra, Graduate Texts in Mathematics, Vol. 227, Springer-Verlag, New York, 2005.
  * [106] Molev A., Yangians and classical Lie algebras, Mathematical Surveys and Monographs, Vol. 143, Amer. Math. Soc., Providence, RI, 2007.
  * [107] Motegi K., Sakai K., Vertex models, TASEP and Grothendieck polynomials, J. Phys. A: Math. Theor. 46 (2013), 355201, 26 pages, arXiv:1305.3030.
  * [108] Mukhin E., Tarasov V., Varchenko A., Bethe subalgebras of the group algebra of the symmetric group, Transform. Groups 18 (2013), 767–801, arXiv:1004.4248.
  * [109] Mutafyan G.S., Feigin B.L., Characters of representations of the quantum toroidal algebra $\widehat{\widehat{\mathfrak{gl}}}_{1}$: plane partitions with “stands”, Funct. Anal. Appl. 48 (2014), 36–48.
  * [110] Novelli J.-C., Thibon J.-Y., Hopf algebras of $m$-permutations, $(m+1)$-ary trees, and $m$-parking functions, arXiv:1403.5962.
  * [111] Okada S., Enumeration of symmetry classes of alternating sign matrices and characters of classical groups, J. Algebraic Combin. 23 (2006), 43–69, math.CO/0408234.
  * [112] Orellana R., Ram A., Affine braids, Markov traces and the category ${\mathcal{O}}$, in Algebraic Groups and Homogeneous Spaces, Tata Inst. Fund. Res. Stud. Math., Tata Inst. Fund. Res., Mumbai, 2007, 423–473, math.RT/0401317.
  * [113] Orlik P., Terao H., Arrangements of hyperplanes, Grundlehren der Mathematischen Wissenschaften, Vol. 300, Springer-Verlag, Berlin, 1992.
  * [114] Orlik P., Terao H., Commutative algebras for arrangements, Nagoya Math. J. 134 (1994), 65–73.
  * [115] Polishchuk A., Classical Yang–Baxter equation and the $A_{\infty}$-constraint, Adv. Math. 168 (2002), 56–95, math.AG/0008156.
  * [116] Polishchuk A., Positselski L., Quadratic algebras, University Lecture Series, Vol. 37, Amer. Math. Soc., Providence, RI, 2005.
  * [117] Postnikov A., On a quantum version of Pieri’s formula, in Advances in geometry, Progr. Math., Vol. 172, Birkhäuser Boston, Boston, MA, 1999, 371–383.
  * [118] Postnikov A., Shapiro B., Shapiro M., Algebras of curvature forms on homogeneous manifolds, in Differential Topology, Infinite-Dimensional Lie algebras, and Applications, Amer. Math. Soc. Transl. Ser. 2, Vol. 194, Amer. Math. Soc., Providence, RI, 1999, 227–235, math.AG/9901075.
  * [119] Postnikov A., Stanley R.P., Deformations of Coxeter hyperplane arrangements, J. Combin. Theory Ser. A 91 (2000), 544–597, math.CO/9712213.
  * [120] Proctor R.A., Bruhat lattices, plane partition generating functions, and minuscule representations, European J. Combin. 5 (1984), 331–350.
  * [121] Proctor R.A., New symmetric plane partition identities from invariant theory work of De Concini and Procesi, European J. Combin. 11 (1990), 289–300.
  * [122] Proctor R.A., Product evaluations of Lefschetz determinants for Grassmannians and of determinants of multinomial coefficients, J. Combin. Theory Ser. A 54 (1990), 235–247.
  * [123] Pyatov P., Raise and peel models of fluctuating interfaces and combinatorics of Pascal’s hexagon, J. Stat. Mech. Theory Exp. 2004 (2004), P09003, 30 pages, math-ph/0406025.
  * [124] Ryom-Hansen S., On the representation theory of an algebra of braids and ties, J. Algebraic Combin. 33 (2011), 57–79, arXiv:0801.3633.
  * [125] Saito K., Growth function of Artin monoids, Proc. Japan Acad. Ser. A Math. Sci. 85 (2009), no. 7, 84–88.
  * [126] Schenck H., Tohǎneanu Ş.O., The Orlik–Terao algebra and 2-formality, Math. Res. Lett. 16 (2009), 171–182, arXiv:0901.0253.
  * [127] Schuetz A., Whieldon G., Polygonal dissections and reversions of series, arXiv:1401.7194.
  * [128] Serrano L., Stump C., Generalized triangulations, pipe dreams, and simplicial spheres, in 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), Discrete Math. Theor. Comput. Sci. Proc., AO, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2011, 885–896.
  * [129] Shapiro B., Shapiro M., On ring generated by Chern $2$-forms on ${\rm SL}_{n}/B$, C. R. Acad. Sci. Paris Sér. I Math. 326 (1998), 75–80.
  * [130] Shibukawa Y., Ueno K., Completely ${\bf Z}$ symmetric $R$ matrix, Lett. Math. Phys. 25 (1992), 239–248.
  * [131] Sloan N., The on-line encyclopedia of integer sequences, available at https://oeis.org/.
  * [132] Stanley R.P., Acyclic flow polytopes and Kostant’s partition function, Conference transparencies, 2000, available at http://www-math.mit.edu/~rstan/transparencies/kostant.ps.
  * [133] Stanley R.P., Catalan addendum, version of April 30, 2011, available at htpp:/www-math.mit.edu/~rstan/ec/catadd.pdf.
  * [134] Stanley R.P., Enumerative combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, Vol. 62, Cambridge University Press, Cambridge, 1999.
  * [135] Stump C., A new perspective on $k$-triangulations, J. Combin. Theory Ser. A 118 (2011), 1794–1800, arXiv:1009.4101.
  * [136] Sulanke R.A., Counting lattice paths by Narayana polynomials, Electron. J. Combin. 7 (2000), 40, 9 pages.
  * [137] Tamvakis H., Arithmetic intersection theory on flag varieties, Math. Ann. 314 (1999), 641–665, alg-geom/9611006.
  * [138] Uglov D., Finite-difference representations of the degenerate affine Hecke algebra, Phys. Lett. A 199 (1995), 353–359, hep-th/9409155.
  * [139] Wachs M.L., Flagged Schur functions, Schubert polynomials, and symmetrizing operators, J. Combin. Theory Ser. A 40 (1985), 276–289.
  * [140] Welsh D., The Tutte polynomial, Random Structures Algorithms 15 (1999), 210–228.
  * [141] Whittaker E.T., Watson G.N., A course of modern analysis, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1996.
  * [142] Woo A., Catalan numbers and Schubert polynomials for $w=1(n+1)\cdots 2$, math.CO/0407160.


Work done while working at Meta

Pre-trained models with dual and cross encoders have shown remarkable success in propelling the landscape of several tasks in vision and language in Visual Question Answering (VQA). However, since they are limited by the requirements of gold annotated data, most of these advancements do not see the light of day in other languages beyond English. We aim to address this problem by introducing a curriculum based on the source and target language translations to finetune the pre-trained models for the downstream task. Experimental results demonstrate that script plays a vital role in the performance of these models. Specifically, we show that target languages that share the same script perform better ($\sim$ 6%) than other languages and mixed-script code-switched languages perform better than their counterparts ($\sim$ 5-12%).

§ INTRODUCTION

The remarkable ability of pre-trained language models has demonstrated their competence in several downstream tasks <cit.>. The same trend continued in vision-and-language tasks including Visual Question Answering (VQA) <cit.>. While the benefits of the tasks are indisputable ranging from assisting visually impaired people to situated interactions, these advancements are limited to a single language. On top of this, these models are also not inherently capable of predicting code-mixed questions.

However, these models are more than ever data hungry and demand large-scale multilingual vision and language datasets to achieve similar performance as demonstrated in English. The rapid advancements in monolingual vision-and-language tasks along with the strides in translation models can be leveraged to combine their powers for cross-lingual VQA <cit.>. This brings the benefit of not needing to create parallel annotated  data which is expensive, as long as there is a translation model that can create weak translations to this target language.

To address this cross-lingual transfer, we perform data augmentation based on self-training to fine-tune multimodal models for the given task in a target language. Specifically, this repetition of fine-tuning is designed as a curriculum from the source language, to a concatenation of source and target languages, to finally predicting in the target language. The intermediate step of concatenating with the target language is based on a loose translation from a pre-trained unimodal translation model.

The preliminary results with different cross-modal encoders and dual encoders show that the performance of the target languages that share the same script as that of the pre-training languages is higher compared to the languages with different scripts. Similarly, the performance on code-mixed languages with mixed script that is Romanized performs better than their monolingual counterparts.

The main contributions of this paper are:

* We introduce a curriculum learning strategy for modeling multilingual questions with access to gold-annotated data in a single language. The curriculum is based on scheduling different languages between the source and the target in multiple stages of finetuning. We devise experiments to compare the performance of dual and cross encoders in monolingual and code-switched scenarios.

* We show that the models fare relatively well in the target languages that share the same script as that of English, i.e., Roman script in comparison to languages with different scripts.

* We experimentally demonstrate that the partially Romanized context in code-switched cases contributes to increased performance compared to their monolingual counterparts.

This study is preliminary work on exploring the curriculum based on scripts of the source and the target languages. Based on these results, we believe that the curriculum of scripts has a lot more potential to explore.

§ CURRICULUM SCRIPT DISTILLATION

The main idea of this method is to distill task-specific external knowledge from a large pre-trained English model to improve the performance of VQA in non-English languages. Specifically, we introduce a curriculum based on the combination of the scripts and languages of the source and target languages. The overall approach is presented in Figure <ref>. We experiment with multiple pre-trained models and the core pre-trained model is abstracted out in this Figure. The algorithm is presented clearly in Algorithm <ref>. We select a pre-trained model $\CMcal{A}(\theta$), parameterized by $\theta$, and annotated data in any one language, which is English in our case.

Input:  Pre-trained Model $\CMcal{A}(\theta$), Labeled Data in English
$\CMcal{L}^{e}$, Translation Model $\CMcal{T}(\alpha$), Unlabeled Data $\CMcal{U}^{x}$

Output:  Trained End-Task Model $\CMcal{A}(\phi$) (finetuned on $\CMcal{A}$)

1. $\CMcal{A}(\theta^{'}$) $\leftarrow$ Fine-tune model $\CMcal{A}(\theta$) on $\CMcal{L}^{e}$

2. $\CMcal{W}^{t}$ $\leftarrow$ Translate $\CMcal{L}^{e}$ to the target language using $\CMcal{T}(\alpha$)

3. $\CMcal{L}^{t}$ $\leftarrow$ Label answers to $\CMcal{W}^{t}$ using $\CMcal{A}(\theta^{'}$) on concatenated $\CMcal{L}^{e}$ $\bigoplus$ $\CMcal{W}^{t}$

4. $\mathbb{L}^{t}$ $\leftarrow$ Subselect answers with high confidence from $\CMcal{L}^{t}$

5. $\CMcal{A}(\phi$) $\leftarrow$ Fine-tune model $\CMcal{A}(\theta$) with $\mathbb{L}^{t}$

Self Training for Cross-lingual VQA

Task Finetuning:  The first step is to finetune a selected pre-trained model with annotated data in one language where the task-specific annotations are available. Owing to the ease of accessibility of English-paired annotations, this task-specific finetuning is performed on English data. This step adapts the model to the task in one language, which is not necessarily the target language that we want to test the performance on. We now have a pre-trained language model finetuned for a specific task. The initial pre-trained model $\CMcal{A}(\theta$) is now parameterized by the VQA specific parameters $\theta^{'}$ resulting in the model $\CMcal{A}(\theta^{'}$). Task finetuning is at one end of the spectrum where the languages or scripts from the target language remain unused, as it is completely based on the source language.

Cross-lingual Weak Annotation:
The next step is to adapt the model to the target language, which requires annotations from the target language. In order to annotate them, we first need questions in the target language. We  automatically translate them into the target language. The labeled examples in English $\CMcal{L}^{e}$ are translated to the target language, resulting in $\CMcal{W}^{t}$ which are weakly labeled translations in the target language. Note that the translations done here are unimodal machine translations rather than multimodally translated questions. These target language questions are concatenated with their English counterparts to assist the model adjust its parameters to the target language. The fine-tuned model from the previous step is used to annotate the concatenated questions along with an image to arrive at answer predictions. The English questions primed to the model act as a prompt to answer the queries by concatenating $\CMcal{L}^{e}$ with the distantly translated $\CMcal{W}^{t}$ questions. Then we use the previously fine-tuned A($\theta^{'}$) to predict the answers to the questions $\CMcal{W}^{t}$ to form $\CMcal{L}^{t}$. This falls in the middle ground of the two ends of the translation spectrum. The first end is using the fine-tuned model of English to predict the answers to questions from another language. The second end is using an off-the-shelf tool to translate the questions into the target language, which is used to fine-tune the model. While the first carries the language-uninformed zero-shot prediction, the second approach carries the burden of translation biases. We balance both of these cons in our approach by including the target language to enrich target language prediction beyond zero-shot and by priming with the question from the source language to counter translationese artifacts.

Selection:  We now have weakly translated questions and weakly annotated answers for the subset of the above questions. Instead of using the entire data, we select $\sim$ 5k questions which are high confidence answers i.e, among the weakly predicted answers above $\CMcal{L}^{t}$, we select $\mathbb{L}^{t}$ high confidence predictions. This weakly annotated data is added to the training data and model A($\theta^{'}$) is fine-tuned again to arrive at the final model $\CMcal{A}(\phi$). In our continued experiments, we repeated this entire process multiple times; however, we observed the results after the first iteration.

Overall training setup

§ EXPERIMENTS AND RESULTS

Dataset:  We conduct experiments on MuCO VQA dataset <cit.> (Multilingual and Code-mixed) which is built on top of the VQA dataset <cit.>. As the name suggests, the data includes both multilingual code-mixed questions and the answers remain in English. While our approach can be extended to a generation-based model, we plan to explore that in the future. With the discriminative-based model, the answers are present in English. Including English, the dataset includes questions from 6 different mono-languages and 5 different code-mixed languages. All the mixed languages are mixed with English. Aside from English, the other languages in the dataset are German, Spanish, French, Hindi, and Bengali. The monolingual translations are automatically obtained from Google Machine Translation, and the code-mixed questions are generated using the matrix language frame theory <cit.>.

We combined experiments to analyze performance using multiple cross and dual encoders.

$\bigcdot$ Cross-encoders: The cross-encoder models use the image regions and language features to combine with a self-attention capable of discovering the alignments between the visual and the textual descriptions implicitly. Oftentimes, these models are trained with variants of masked language modeling extended to visual representations such as masked region classification.

$\bigcdot$ Dual-encoders:  In contrast to cross-encoding where the inputs from both the modalities or languages are processed by the same encoder, dual encoders have 2 distinct encoders with separate parameters to process different modalities. The latent representations are then fused with late fusion techniques or extended to task specific model architectures.

For pre-trained cross-encoders, we experimented with ViLT <cit.>, VisualBERT <cit.>, LXMERT <cit.>, CLIPViT. For pre-trained dual-encoders, we performed a sweep on combinations of visual encoders including ViT <cit.>, BEiT <cit.>, DEiT <cit.>
and textual encoders including XLM <cit.>, XGLM <cit.>, mT5 <cit.>, and CANINE <cit.>.

We used the official evaluation script provided by the VQA challenge.

The trends of the results across languages are shown in Figure <ref>. We ran each model 5 times for each language and the scores were averaged across the models and the runs.

Overall accuracy of VQA across multiple monolingual and code-switched questions

From our preliminary results with cross and dual encoders, performance with Roman scripts  is better than those with non-roman scripted languages. Across the aforementioned model configurations, the performance between Roman and non-Roman languages has a  minimum difference of at least $\sim$ 6%. Since the base model is primarily pre-trained on English which is in the Roman script, this preferred trend continues in other languages as well. Naturally, an open question arises if the performance gap can be reduced with increasing scripts from other languages during pre-training, which does not mandate expensive parallel data.

Additionally, the performance on switched concepts in English with code-switching is better than their counterparts, (by about $\sim$ 5-12%). This shows that the  knowledge from large English pretrained language model can be constructively used to improve performance in other languages. Our model selects the data based on the performance of the first fine-tuned model on the combined questions of the source and the target languages, thereby selecting examples that are performing well on mixed yet combined questions. The natural extension here is to understand the performance based on the selection of instances performing better in one language but not the other, which we plan to explore in the future.

§ RELATED WORK

Multilingual VQA:  Several research works extended existing monolingual VQA dataset to other languages <cit.>. Similar to these efforts, <cit.> also generated synthetic data to perform fact-based spoken VQA. While the above datasets are synthetically generated, <cit.> crowdsourced datasets directly in languages other than English.

Multilingual Multimodal Modeling:  A detailed account of various modeling approaches was outlined categorically in the recent survey paper <cit.>. They described categories of modeling approaches as modular, projecting embeddings, and mapping which includes popular approaches like alignment and attention. Our work mostly falls in the category of embedding projection. We build on the fusion-based approach as embedding projection of the cross-attention to schedule a curriculum of language mixing, by concatenating the source language with the target language. This approach is inspired by the translation objective introduced by <cit.>. The knowledge from one language is distilled to train a student network to perform visual question answering by <cit.>. The student network that learns to perform the task in several languages is trained to imitate the teacher network that is trained on English-annotated data at all the intermediate layers instead of the final layer alone.

Augmentation with self-training:
Prior research widely used annotation of data with human or weak distant labels to use as augmented data for training in low-resource settings. In some cases, the additional data is augmented not in the form of end task but to provide additional information about the context such as providing object labels <cit.>.
<cit.> performed self-training with switch-point based selection of instances to repurpose large pre-trained models to code-switched sequence labeling tasks. Instead of selecting biased examples based on the poor-performing switch point, we select the examples that the model performs well on  the concatenated sentences of the source and the target languages.

§ CONCLUSIONS AND FUTURE WORK

Relaying the technologies developed in high-resource languages to several languages other than English has always taken a back seat. A critical reason hindering the smooth relay is the lack of annotated resources of the same scale as that of English in other languages. This is particularly evident in resource-heavy tasks that include multimodal tasks such as Visual Question Answering.
However, independent of these multimodal tasks, machine translation has made commendable strides in the field. Our work leverages these unimodal machine translation models to build a curriculum of the scripts and languages in the training process. Specifically, we performed self-training on a pre-trained multimodal model to learn the task-specific parameters first on the source language, then use a concatenated source and weakly translated target language question to make the predictions. Using these answer predictions as weak labels, the model was finetuned for the target language and eventually tested on the target language. In this way, we are not relying on the ground truth gold annotations of the target language, but rather seek help from the source language of the questions to predict answers for the target language questions. Our experimental results emphasize two main conclusions. First, the performance on languages with a similar script as that of the languages in the pretrained model is better than different scripts. Second, the performance on code-switched languages is better than their counterparts. Our work presents preliminary results on the potential of mixed scripts in training multilingual and cross-lingual models. We plan to explore fine-grained improvements contributed by scripts on dual and cross encoders in different stages of self-training in the future.


††thanks<EMAIL_ADDRESS><EMAIL_ADDRESS>
#  Advancing Hybrid Quantum-Classical Algorithms via Mean-Operators

Donggyu Kim  Department of Physics, Korea Advanced Institute of Science and
Technology (KAIST), Daejeon 34141, Korea  Pureum Noh  Department of Physics,
Korea Advanced Institute of Science and Technology (KAIST), Daejeon 34141,
Korea  Hyun-Yong Lee  Department of Applied Physics, Graduate School, Korea
University, Sejong 30019, Korea  Division of Display and Semiconductor
Physics, Korea University, Sejong 30019, Korea  Interdisciplinary Program in
E$\cdot$ICT-Culture-Sports Convergence, Korea University, Sejong 30019, Korea
Eun-Gook Moon  Department of Physics, Korea Advanced Institute of Science and
Technology (KAIST), Daejeon 34141, Korea

###### Abstract

Entanglement in quantum many-body systems is the key concept for future
technology and science, opening up a possibility to explore uncharted realms
in an enormously large Hilbert space. The hybrid quantum-classical algorithms
have been suggested to control quantum entanglement of many-body systems, and
yet their applicability is intrinsically limited by the numbers of qubits and
quantum operations. Here we propose a theory which overcomes the limitations
by combining advantages of the hybrid algorithms and the standard mean-field-
theory in condensed matter physics, named as mean-operator-theory. We
demonstrate that the number of quantum operations to prepare an entangled
target many-body state such as symmetry-protected-topological states is
significantly reduced by introducing a mean-operator. We also show that a
class of mean-operators is expressed as time-evolution operators and our
theory is directly applicable to quantum simulations with 87Rb neutral atoms
or trapped 40Ca+ ions.

Introduction :  Remarkable quantum entanglement phenomena are uncovered by
experimental advances in quantum science and technology. Systems with about
fifty qubits have been manipulated, and quantum entanglement achieves
computational tasks well beyond classical computations as known as quantum
supermacy Preskill (2018); Arute et al. (2019). Enormously entangled many-body
states such as topologically ordered states have been realized in a 31-qubit
superconducting quantum processor et al. (2021) and a 219-atom programmable
quantum simulator of Rydberg atom arrays Semeghini et al. (2021) recently.
Signatures of fractionalized particles also have been reported in systems with
about the Avogadro number of electrons Zhou et al. (2017); Savary and Balents
(2017); Knolle and Moessner (2019); Takagi et al. (2019), which manifests
massive entanglement of many-body systems.

Theoretical efforts also have been made to utilize quantum entanglement, and
the variational hybrid quantum-classical algorithms such as the quantum-
approximate-optimization-algorithm (QAOA) have been proposed Farhi et al.
(2014); McClean et al. (2016). The main idea is to employ classical
computations to complement expensive quantum operations and design a
variational circuit to prepare a target quantum state. Applicability of the
algorithm is already demonstrated in trapped ion experiments Moll et al.
(2018); Britton et al. (2012); Kokail et al. (2019). However, the numbers of
qubits and quantum operations are seriously limited in NISQ technology. Recent
theoretical works even find a fundamental limitation of QAOA that a deep
circuit proportional to a system size is necessary to achieve a non-trivial
quantum state Ho and Hsieh (2019); Bravyi et al. (2020). Thus, a theory, which
reduces the number of quantum operations and applies to a system with an
arbitrary number of qubits, is in great demand.

Figure 1:  (a) Construction of a variational state by acting mean-operator and
symmetric operator on a trivial state. (b) The mean-operators directly access
the non-trivial phases such as the symmetry breaking, the symmetry protected
topological and/or topologically ordered phases. The symmetric operator
increases quantum entanglement, and its action is analogous to the standard
hybrid quantum-classical algorithm such as QAOA.

In this work, we provide a variational theory which overcomes the limitations
by combining advantages of the hybrid algorithms and the standard mean-field-
theory (MFT), named as mean-operator-theory (MOT). Our main strategy is to let
an operator with judicious guess, called a mean-operator, to capture essential
characteristics of an entangled many-body state such as symmetry properties
and entanglement patterns. And then, the conventional QAOA is performed to
refine a variational state quantitatively as illustrated in Fig 1. The mean-
operator plays a similar role of a mean-field order parameter in the standard
MFT. To find an explicit form of a mean-operator, it is particularly useful to
employ intuitions from quantum many-body states in condensed matter such as
symmetry and entanglement properties.

We demonstrate that our theory significantly reduces the number of quantum
operations to prepare target states and is even applicable to spatial
dimensions higher than two. Furthermore, a class of mean-operators may be
realized as time-evolution operators because they are chosen to be unitary
operators, and thus our theory may be directly applicable to experiments of
near-term quantum simulations including Rydberg atoms and trapped ions. Our
theory may also serve as a theoretical tool to investigate general quantum
many-body problems outperforming conventional mean-field type methods.

Mean-Operator-Theory :  The MOT adopts the variational method of quantum
mechanics and an ansatz state of a system with a symmetry group $\mathbb{G}$,

$\displaystyle|\Psi;\\{\alpha,\beta\\}_{p},\\{\phi\\}\rangle=\hat{S}(\\{\alpha,\beta\\}_{p})\cdot\hat{M}(\\{\phi\\})\cdot|0\rangle,$
(1)

consists of the three main objects,

  * •

$\hat{M}(\\{\phi\\})$ : Mean-operator with a set of parameters $\\{\phi\\}$,
which is non-trivial under $\mathbb{G}$ for a generic $\phi$

  * •

$\hat{S}(\\{\alpha,\beta\\}_{p})$ : Symmetric operator with a set of
parameters $\\{\alpha,\beta\\}_{p}$, which is trivial under $\mathbb{G}$

  * •

$|0\rangle=\prod_{j}|+\rangle_{j}$ : Symmetric product state with a site index
$j$, where $|+\rangle_{j}$ is trivial under $\mathbb{G}$.

Here, $p$ is an integer determining the complexity and accuracy of the ansatz
and is referred to as the depth level of MOT. In this work, we assume the
translational symmetry and that the representation of $\mathbb{G}$ is
decomposed into the on-site unitary. By minimizing the energy expectation
value of a Hamiltonian $H$,
$\langle\Psi|H|\Psi\rangle/\langle\Psi|\Psi\rangle$, a better approximated
ground state is obtained with more parameters.

A symmetric operator, $\hat{S}(\\{\alpha,\beta\\}_{p})$, employs the hybrid
quantum-classical algorithms such as QAOA McClean et al. (2016) and refines a
variational state quantitatively. As usual, the total Hamiltonian is
decomposed as $H=H_{1}+H_{2}$, where $H_{1}$ and $H_{2}$ do not commute each
other, and the symmetric operator may be written as
$U_{S}(\\{\alpha,\beta\\}_{p})=\prod_{a=1}^{p}e^{-i\alpha_{a}H_{1}}e^{-i\beta_{a}H_{2}}$
with parameters $(\alpha_{a},\beta_{a})$ with a certain depth $p$. By
construction, $H_{1}$ and $H_{2}$ are symmetric under $\mathbb{G}$.

A mean-operator, $\hat{M}(\\{\phi\\})$, significantly reduces the number of
quantum operations to access non-trivial states, including topological or
symmetry-broken states. The non-trivial property under $\mathbb{G}$ allows us
to explore a much wider region in the Hilbert space effectively than the
standard QAOA. In particular, there exists a special subset of
$\\{\phi_{s}\\}$ which makes the variational state
$\hat{M}(\\{\phi_{s}\\})|0\rangle$ both entangled and symmetric. It is obvious
that the state is hard to be constructed by using the conventional QAOA. In
what follows, we apply our MOT to three different cases.

Figure 2:  Magnetization obtained by MOT in (a) one-dimensional, (b) two-
dimensional and (c) three-dimensional transverse-field-Ising model,
$H_{1}(g)$. Here, the green dotted lines stand for the exact critical points,
i.e., $g_{c}^{\rm exact}=1$ in 1D, $g^{\rm exact}_{c}=3.044$ in 2D, and
$g^{\rm CMC}_{c}=5.158$ in 3D Blöte and Deng (2002). The depth-two MOT in 1D
finds $g_{c}^{(2)}\simeq 1.18$, and the depth-one MOT finds $g_{c}^{(1)}\simeq
3.14$ and $g_{c}^{(1)}\simeq 5.03$ for 2D and 3D, respectively.

Case 1) Spontaneously-symmetry-broken state :  Let us first consider
spontaneous-symmetry-breaking. To be specific, we consider the transverse-
field-Ising model Sachdev (2011); Zeng et al. (2015) with a dimensionless
coupling constant, $g$,

$\displaystyle H_{1}(g)=-\sum_{\langle i,j\rangle}Z_{i}Z_{j}-g\sum_{j}X_{j},$
(2)

where Pauli matrices $X_{j},Y_{j},Z_{j}$ at site $j$ on a hypercubic lattice
are used. The exchange energy scale is set to be unity, and the Hamiltonian
enjoys the $\mathbb{Z}_{2}$ symmetry with $\\{I,\prod_{j}X_{j}\\}$. The
identity operator, $I$, is introduced, and the symmetric product state,
$|0\rangle=\prod_{j}|+\rangle_{j}$ with $X_{j}|+\rangle_{j}=|+\rangle_{j}$, is
the ground state of $H_{1}(\infty)$.

We consider the operators,

$\displaystyle\hat{M}_{1}(\phi)=e^{-i\sum_{j}\phi Y_{j}}$
$\displaystyle\hat{S}_{1}(\\{\alpha,\beta\\}_{p})=\prod_{a=1}^{p}e^{-i\alpha_{a}\sum_{j}X_{j}}e^{-i\beta_{a}\sum_{\langle
i,j\rangle}Z_{i}Z_{j}}.$ (3)

For the depth-zero ($p=0$), the expectation values of the order parameter and
energy density are $m(\phi)=\langle\Psi|Z_{j}|\Psi\rangle=-S_{2\phi}$ and
$\epsilon(\phi)\equiv\langle\Psi|H|\Psi\rangle/N=-S_{2\phi}^{2}-gC_{2\phi}$
with the total site number $N$. The short-handed notations,
$C_{\theta}\equiv\cos(\theta)$ and $S_{\theta}\equiv\sin(\theta)$, are used
hereafter. Minimizing the energy density determines the order parameter,
$m^{(0)}=\pm\sqrt{1-\left(\frac{g}{2d}\right)^{2}}$, in spatial dimension $d$
, which gives the critical coupling constant, $g_{c}^{(0)}=2d$. Applying
$\hat{S}_{1}$ with a non-zero $p$, systematic improvements are achieved. Fig.
2 presents the order parameter obtained by MOT for $d=1,2$ and $3$, of which
the critical points are significantly improved with the non-zero depth.
Details on the computation of $\epsilon$ and $m$ are provided in Supplemental
Materials (SM).

Few remarks are as follows. First, the $p=0$ calculations are equivalent to
the ones of the standard MFT. In other words, our MOT may be understood as a
general extension of MFT, and its systematic improvement is achieved by
introducing the symmetric operator. Second, the $p=0$ calculation does not
capture any quantum entanglement because both the mean-operator and the
trivial state are of the product forms. We emphasize that the mechanism of the
improvement in MOT is the entangled nature of the exchange interaction term in
$\hat{S}_{1}$. Third, our discussions may be easily generalized to a system
with a larger group structure where MFT is well developed. Knowledge of the
MFT may be used to choose a mean-operator.

Case 2) Symmetry-protected-topological state :  Our MOT is applicable to
topological states. One prime example is a symmetry-protected-topological
(SPT) ground state of the cluster model under a transverse magnetic field in
one spatial dimensionZeng et al. (2015),

$\displaystyle
H_{2}(g)=-(1-g)\sum_{j=1}^{L-2}Z_{j}X_{j+1}Z_{j+2}-g\sum_{j=1}^{L}X_{j}.$ (4)

The $\mathbb{Z}_{2}\times\mathbb{Z}_{2}$ symmetry with
$\\{I,\prod_{e}X_{j},\prod_{o}X_{j},\prod_{e,o}X_{j}\\}$ exists, where the
subscripts $e$ and $o$ for even and odd sites. A trivial product state is
$|0\rangle=\prod_{j}|+\rangle_{j}$ with $X_{j}|+\rangle_{j}=|+\rangle_{j}$,
which is the ground state of $H_{2}(g=1)$.

We choose the operators,

$\displaystyle\hat{M}_{2}(\phi_{1},\phi_{2})=e^{-i\phi_{2}\sum_{j}Z_{j}Z_{j+1}}e^{-i\phi_{1}\sum_{j}Z_{j}}$
$\displaystyle\hat{S}_{2}(\\{\alpha,\beta\\}_{p})=\prod_{a=1}^{p}e^{-i\beta_{a}\sum_{j}Z_{j}{X}_{j+1}Z_{j+1}}e^{-i\alpha_{a}\sum_{j}{X}_{j}},$

and the zero depth level ($p=0$) calculation gives the ground state energy,

$\displaystyle\epsilon^{(0)}(\phi_{1},\phi_{2})=(1-g)C_{2\phi_{1}}S_{2\phi_{2}}^{2}-gC_{2\phi_{1}}C_{2\phi_{2}}^{2}.$
(5)

Minimizing the energy density, a quantum phase transition is obtained at
$g_{c}^{(0)}=1/2$, which is the same as the exact one Doherty and Bartlett
(2009). The trivial product state with $(\phi_{1}=\phi_{2}=0)$ appears as the
ground states in $1/2<g<1$, while an entangled state with
$(\phi_{1}=\pi/2,\phi_{2}=\pm\pi/4)$ optimizes the model below $g<1/2$.

We stress that the mean-operator, $\hat{M}_{2}(\phi_{1},\phi_{2})$, is
entangled because it cannot be written as a product of local operators unless
$\phi_{2}=0$. The higher-order term $Z_{j}Z_{j+1}$ is essential and becomes
the source of anomalous symmetry action at boundaries. We present entanglement
spectrums of our variational ground states with $p=1$ in Fig. 3 (a), where all
levels exhibit the four-fold degeneracy below the critical value $g_{c}\simeq
0.56$ while the four-fold degeneracy disappears above $g_{c}$ Pollmann et al.
(2012). Note that the number of variational parameters are four. To
demonstrate advantages of our MOT, we perform conventional QAOA calculations
and illustrate their entanglement spectrums in Fig. 3 (b). To use four
variational parameters, the conventional depth-two QAOA are performed with
different initial states. In the left (right) figure, the ground state of
$H_{2}(g)$ with $g=0$ ($g=1$) is chosen as the initial state, respectively.
The absence of quantum phase transitions is manifest, indicating that the MOT
outperforms the conventional QAOA.

Note that the mean operator breaks $\mathbb{G}$ for generic values of
$(\phi_{1},\phi_{2})$, but the one with $(\pi/2,\pi/4)$ produces a symmetric
state. Therefore, the ground state with the mean-operator becomes not only
entangled but also symmetric under $\mathbb{G}$. This is equivalent to the
well-known fact that a SPT state cannot be obtained by acting local symmetric
transformations on a trivial state.

Figure 3:  (a) Entanglement spectrum,
$\varepsilon_{\alpha}=e^{-\xi_{\alpha}}$, of $H_{2}(g)$ obtained by the depth-
one MOT with four variational parameters. The topological phase transition at
$g_{c}$ is well captured by the number of degeneracy of the spectrum, where
the four-fold degeneracy for $g<g_{c}$ is the characteristic of the SPT phase.
(b) Entanglement spectrums of the depth-two QAOA states with four variational
parameters. The initial states are chosen to be the ground states of
$H_{2}(g=0)$ (left) and $H_{2}(g=1)$ (right), respectively. Numerical
calculations are performed with 20 qubits, and the periodic boundary condition
is imposed.

Case 3) Competition physics:  One significant advantage of our MOT is the
expressive power to describe both symmetry-broken and topological states,
which allows us to access intriguing phenomena such as competition physics
between spontaneously-symmetry-broken and topological states.

As a proof-of-principle, we consider the Levin-Gu model Levin and Gu (2012)
with a ferromagnetic exchange interaction term and a transverse-field term
with two parameters ($g,\lambda$) on a triangular lattice,

$\displaystyle H_{3}(\lambda,g)$ $\displaystyle=$
$\displaystyle(1-\lambda)H_{LG}+gH_{ex}+\lambda H_{PM}.$ (6)

The Levin-Gu Hamiltonian, trivial paramagnetic Hamiltonian, and the
ferromagnetic exchange Hamiltonians are

$\displaystyle H_{LG}$ $\displaystyle=$
$\displaystyle-\sum_{j}B_{j},\,\,H_{ex}=-\sum_{\langle
jk\rangle}Z_{j}Z_{k},\,\,H_{PM}=-\sum_{j}X_{j},$

with the dressed qubit term, $B_{j}=-X_{j}\prod_{\langle
jkl\rangle}i^{(\frac{1-Z_{k}Z_{l}}{2})}$, where $\langle jkl\rangle$ is the
nearest neighbor three sites around the site $j$. The Hamiltonian enjoys the
$\mathbb{Z}_{2}$ symmetry, $\\{I,\prod_{j}X_{j}\\}$, and a trivial product
state is $|0\rangle=\prod_{j}|+\rangle_{j}$ with
$X_{j}|+\rangle_{j}=|+\rangle_{j}$, which is the ground state of $H(\infty,g)$
for a finite $g$. Note that each term of the three Hamiltonians captures
physics of symmetry-protected-topological, spontaneously-symmetry-broken, and
trivial states, respectively.

We choose the mean-operator,

$\displaystyle\hat{M}_{3}(\theta,\phi,\psi)=\prod_{\langle
jkl\rangle}e^{-i\theta
Z_{j}Z_{k}Z_{l}-i\phi(Z_{j}+Z_{k}+Z_{l})}e^{-i\psi\sum_{j}Y_{j}}.$

Each operator associated with the three parameters ($\theta,\phi,\psi$) breaks
the $\mathbb{Z}_{2}$ symmetry generically. The term with $\theta$ is made of
three adjacent qubits, describing non-trivial entanglement between adjacent
qubits. For simplicity, a symmetric operator is set to be the identity in this
work. It is straightforward to increase the depth, which may be used to
properties of a refined many-body wavefunction. For example, one can show that
the behaviors of the strange correlator You et al. (2014) persist around the
depth-zero calculations perturbatively.

Varying with ($\theta,\phi,\psi$), we find three different phases in the
$\lambda$-$g$ plane, as shown in Fig. 4. We stress that the spontaneously-
symmetry-broken state exists even without the exchange interaction ($g=0$),
and its region becomes larger with a bigger $g$. This clearly shows
competition physics between symmetry-protected-topological and spontaneously-
symmetry-broken states. It is an intriguing open question whether the
spontaneously-symmetry-broken state survives for calculations with a non-zero
depth, which we leave for future works. Also, another scenario associated with
a stripe-order is recently suggested Dupont et al. (2020), which may also be
interesting to test in the future.

Our model has the non-trivial duality ($\lambda\leftrightarrow 1-\lambda$),
which makes the phase boundary symmetric in the $\lambda$-$g$ plane (see SI).
The quantum phase transitions between spontaneously-symmetry-broken and
symmetry-protected-topological states and the ones between spontaneously-
symmetry-broken and trivial states are continuous, and we argue that both of
them are in the Ising universality class based on the duality. Though they are
in the same universality class in the thermodynamic limit, it is interesting
how their edge modes behave differently at the transitions.

Figure 4: Competition between symmetry-protected-topological and
spontaneously-symmetry-broken (SSB) states. (a) The depth-zero MOT phase
diagram of $H_{3}(\lambda,g)$. The critical values are $\lambda_{c1}=0.4$,
$\lambda_{c2}=0.6$, $g_{c1}=g_{c2}=1/6$. The trivial and SPT states are
characterized by $(\theta,\phi,\psi)=(0,0,0),(-\pi/8,\pi/24,0)$, respectively,
and the spontaneously-symmetry-broken state is characterized by $\psi\neq 0$.
(b) Illustration of the wave-functions of the three states.

Discussion :  Our MOT overcomes the fundamental limitations of QAOA and
enables to prepare a target state with a shallow circuit. A mean-operator
captures essential characteristics of the target state, and thus finding a
mean-operator is at the heart of MOT. Intuitions from condensed matter theory
such as symmetry and entanglement properties can be particularly useful, as
shown the above cases where the non-trivial property under a given symmetry
and the degree of entanglement of an operator are two important factors.
Investigation of a class of mean-operators may provide an alternative way to
classify quantum-many-body states.

Our MOT is applicable to near-term quantum simulations. The hybrid algorithms
have already been demonstrated in the one-dimensional trapped ion problems
Kokail et al. (2019), and its possibilities in a few qubits have been proposed
Ho and Hsieh (2019); Zhou et al. (2020). Since our MOT is a natural extension
of the hybrid algorithms, we believe that applications of MOT are plausible
and powerful, especially in 2D and 3D.

We propose that preparations of SPT states in quantum simulators of 87Rb
neutral atoms or trapped 40Ca+ ions may be particularly interesting. A
realization of the mean-operators for each SPT state is a key step, and our
results, for example $\hat{M}_{2}(\phi_{1},\phi_{2})$, may be a useful
guideline because an exchange interaction between adjacent qubits is a
dominant Hamiltonian term in both 87Rb neutral atoms or trapped 40Ca+ ions.
Since mean-operators may depend on microscopic properties, we leave specific
forms of mean-operators with propoer initial states for future works.

We anticipate that our MOT can be extended and applied in a variety of ways.
For instance, one can introduce the spatial fluctuations of the mean-operator
that may provide new insight into quantum field theories. Furthermore, a mean-
operator may be extended to be non-unitary, and then the MOT can access
topologically ordered states, similar to the recent realization of toric code
state et al. (2021) (see SI also). Our MOT may be implemented for studying
exotic interacting systems, including fractons Nandkishore and Hermele (2019)
and non-Fermi liquid states, which we leave for future works.

Acknowledgements :  This work was supported by National Research Foundation of
Korea under the grant numbers NRF-2019M3E4A1080411, NRF-2020R1A4A3079707,
NRF-2021R1A2C4001847 (DK, PN, EGM) and NRF-2020R1I1A3074769 (HYL).

## References

  * Preskill (2018) J. Preskill, Quantum 2, 79 (2018), ISSN 2521-327X, URL https://doi.org/10.22331/q-2018-08-06-79.
  * Arute et al. (2019) F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. Brandao, D. A. Buell, et al., Nature 574, 505 (2019).
  * et al. (2021) K. J. S. et al., arXiv preprint arXiv:2104.01180 (2021).
  * Semeghini et al. (2021) G. Semeghini, H. Levine, A. Keesling, S. Ebadi, T. T. Wang, D. Bluvstein, R. Verresen, H. Pichler, M. Kalinowski, R. Samajdar, et al., arXiv preprint arXiv:2104.04119 (2021).
  * Zhou et al. (2017) Y. Zhou, K. Kanoda, and T.-K. Ng, Rev. Mod. Phys. 89, 025003 (2017), URL https://link.aps.org/doi/10.1103/RevModPhys.89.025003.
  * Savary and Balents (2017) L. Savary and L. Balents, Rep. Prog. Phys. 80, 016502 (2017), URL http://stacks.iop.org/0034-4885/80/i=1/a=016502.
  * Knolle and Moessner (2019) J. Knolle and R. Moessner, Annual Review of Condensed Matter Physics 10, 451 (2019).
  * Takagi et al. (2019) H. Takagi, T. Takayama, G. Jackeli, G. Khaliullin, and S. E. Nagler, Nature Reviews Physics 1, 264 (2019), URL https://doi.org/10.1038/s42254-019-0038-2.
  * Farhi et al. (2014) E. Farhi, J. Goldstone, and S. Gutmann, arXiv preprint arXiv:1411.4028 (2014).
  * McClean et al. (2016) J. R. McClean, J. Romero, R. Babbush, and A. Aspuru-Guzik, New Journal of Physics 18, 023023 (2016), URL https://doi.org/10.1088/1367-2630/18/2/023023.
  * Moll et al. (2018) N. Moll, P. Barkoutsos, L. S. Bishop, J. M. Chow, A. Cross, D. J. Egger, S. Filipp, A. Fuhrer, J. M. Gambetta, M. Ganzhorn, et al., Quantum Science and Technology 3, 030503 (2018), URL https://doi.org/10.1088/2058-9565/aab822.
  * Britton et al. (2012) J. W. Britton, B. C. Sawyer, A. C. Keith, C.-C. J. Wang, J. K. Freericks, H. Uys, M. J. Biercuk, and J. J. Bollinger, Nature 484, 489 (2012).
  * Kokail et al. (2019) C. Kokail, C. Maier, R. van Bijnen, T. Brydges, M. K. Joshi, P. Jurcevic, C. A. Muschik, P. Silvi, R. Blatt, C. F. Roos, et al., Nature 569, 355 (2019), URL https://doi.org/10.1038/s41586-019-1177-4.
  * Ho and Hsieh (2019) W. W. Ho and T. H. Hsieh, SciPost Phys. 6, 29 (2019), URL https://scipost.org/10.21468/SciPostPhys.6.3.029.
  * Bravyi et al. (2020) S. Bravyi, A. Kliesch, R. Koenig, and E. Tang, Phys. Rev. Lett. 125, 260505 (2020), URL https://link.aps.org/doi/10.1103/PhysRevLett.125.260505.
  * Sachdev (2011) S. Sachdev, _Quantum Phase Transitions_ (Cambridge University Press, Cambridge, 2011), 2nd ed., ISBN 9780511973765.
  * Zeng et al. (2015) B. Zeng, X. Chen, D.-L. Zhou, and X.-G. Wen, arXiv preprint arXiv:1508.02595 (2015).
  * Doherty and Bartlett (2009) A. C. Doherty and S. D. Bartlett, Phys. Rev. Lett. 103, 020506 (2009), URL https://link.aps.org/doi/10.1103/PhysRevLett.103.020506.
  * Pollmann et al. (2012) F. Pollmann, E. Berg, A. M. Turner, and M. Oshikawa, Phys. Rev. B 85, 075125 (2012), URL https://link.aps.org/doi/10.1103/PhysRevB.85.075125.
  * Levin and Gu (2012) M. Levin and Z.-C. Gu, Phys. Rev. B 86, 115109 (2012), URL https://link.aps.org/doi/10.1103/PhysRevB.86.115109.
  * You et al. (2014) Y.-Z. You, Z. Bi, A. Rasmussen, K. Slagle, and C. Xu, Phys. Rev. Lett. 112, 247202 (2014), URL https://link.aps.org/doi/10.1103/PhysRevLett.112.247202.
  * Dupont et al. (2020) M. Dupont, S. Gazit, and T. Scaffidi, arXiv preprint arXiv:2008.06509 (2020).
  * Zhou et al. (2020) L. Zhou, S.-T. Wang, S. Choi, H. Pichler, and M. D. Lukin, Phys. Rev. X 10, 021067 (2020), URL https://link.aps.org/doi/10.1103/PhysRevX.10.021067.
  * Nandkishore and Hermele (2019) R. M. Nandkishore and M. Hermele, Annual Review of Condensed Matter Physics 10, 295 (2019), eprint https://doi.org/10.1146/annurev-conmatphys-031218-013604, URL https://doi.org/10.1146/annurev-conmatphys-031218-013604.
  * Sachdev (2019) S. Sachdev, Reports on Progress in Physics 82, 014001 (2019), URL http://stacks.iop.org/0034-4885/82/i=1/a=014001.
  * Blöte and Deng (2002) H. W. J. Blöte and Y. Deng, Phys. Rev. E 66, 066110 (2002), URL https://link.aps.org/doi/10.1103/PhysRevE.66.066110.

Supplementary Material for
“Advancing Hybrid Quantum-Classical Algorithms via Mean-Operators”

##  I 1\. Comparison between Mean-Field Theory and Mean-Operator Theory

Let us recall the standard approach of MFT in the transverse field Ising model
in $d$ spatial dimensions,

$\displaystyle H_{1}(g)=-\sum_{\langle i,j\rangle}Z_{i}Z_{j}-g\sum_{j}X_{j},$
(1)

where Pauli matrices $X_{j},Y_{j},Z_{j}$ at site $j$ are used with a
dimensionless coupling constant, $g$.

The conventional MFT starts with introducing a mean-field Hamiltonian,

$\displaystyle H_{1,MF}(g)$ $\displaystyle=$ $\displaystyle\sum_{j}h_{j},\quad
h_{j}=-2dmZ_{j}-gX_{j}+dm^{2},$ $\displaystyle=$
$\displaystyle\sum_{j}\big{(}-\sqrt{g^{2}+4d^{2}m^{2}}e^{-i\phi
Y_{j}}X_{j}e^{+i\phi Y_{j}}+dm^{2}\big{)},$

where the order parameter and energy density are

$\displaystyle m=\langle
G_{MF}|Z_{j}|G_{MF}\rangle,\quad\epsilon_{G}^{0}=\frac{E_{G}^{0}}{N}=-\sqrt{g^{2}+4d^{2}m^{2}}+dm^{2}.$

Solving the MF Hamiltonian, its ground state is

$\displaystyle|G_{MF}\rangle=e^{-i\phi_{0}\sum_{j}Y_{j}}|0\rangle,\quad\tan(2\phi_{0})=\frac{2dm}{g}.$
(2)

The stationary condition gives

$\displaystyle m_{0}=\pm\sqrt{1-\frac{g^{2}}{4d^{2}}},$

and the mean-field critical point is $g_{c}^{(0)}=2d$.

The MFT results are connected with MOT by choosing the operators,

$\displaystyle\hat{M}(\phi)=e^{-i\phi\sum_{j}Y_{j}},\quad\hat{S}=I,$ (3)

which manifest the equivalence between MFT and the lowest order calculation of
MOT.

##  II  2\. Finite-depth MOT

Figure 1:  Tensor network representations for the expectation value of a two-
site operator with respect to (a) the depth-one and (b) depth-two MTO.

We employ the tensor network (TN) representations of the wavefunctions and
various operators for a finite-depth MOT. For example, the trivial product
state $|0\rangle$ can be recast as a bond dimension $D=1$ TN state regardless
of the spatial dimension. Similarly, the tensor product of the local unitary
gates, e.g., the mean-operator $\hat{M}_{1}(\phi)=\prod_{i}e^{i\phi Y_{i}}$,
is also represented as a $D=1$ TN operator. On the other hand, the product of
the two-site or multi-site unitary gates requires a bond dimension larger than
$1$, which indicates the generation of quantum entanglement. To be more
concrete, the symmetric operator for SSB, $\hat{S}_{1}$, includes
$\prod_{\langle ij\rangle}e^{i\beta Z_{i}Z_{j}}$ that can be recast as

$\displaystyle\prod_{\langle ij\rangle}e^{i\beta Z_{i}Z_{j}}={\rm
tTr}\left(\prod_{i}T\prod_{\langle ij\rangle}B\right),$ (4)

where ${\rm tTr(\cdots)}$ stands for the tensor trace of the TN and $T$ ($B$)
denotes a site (bond) tensor sitting on each vertex (link) in the lattice:

$\displaystyle[T]_{\alpha_{1}\alpha_{2}\cdots\alpha_{z}}^{ss^{\prime}}=\begin{cases}I_{ss^{\prime}}\quad{\rm
if}\quad\alpha_{1}+\alpha_{2}+\cdots+\alpha_{z}={\rm even}\\\
Z_{ss^{\prime}}\quad{\rm if}\quad\alpha_{1}+\alpha_{2}+\cdots+\alpha_{z}={\rm
odd}\end{cases},$
$\displaystyle[B]_{\alpha_{i}\alpha_{j}}=\begin{pmatrix}\cos\beta&0\\\
0&-i\sin\beta\end{pmatrix}_{\alpha_{i}\alpha_{j}},$ (5)

where $z$ is the coordination number.

We stress that MOT is particularly powerful if mean-operators and symmetric
operators are unitary. It is because only local degrees of freedom are
necessary to evaluate the variational energy and local observables whose size
depends on the depth of employed operators. For example, the expectation value
$\langle Z_{i}Z_{j}\rangle$ f or the $p=1$ MOT for the two-dimensional
transverse field Ising model on the square lattice is illustrated in Fig. 1
(a). Here, the blue spheres on top and bottom stand for $e^{i\phi Y}|+\rangle$
and its complex conjugate, and the red cube and green sphere for the site and
bond tensors defined above. The yellow sphere denotes $e^{-i\alpha Z}$, and
the two-site operator is $Z_{i}Z_{j}$. Further, the size of the cluster
increases with the depth, and thus the TN becomes larger as presented in Fig.
1 (b) that represents the $p=2$ expression for $\langle Z_{i}Z_{j}\rangle$.
Its higher-dimensional generalization is straightforward.

Figure 2:  Optimized variational parameters in the MOT for the (a)-(b) one-
dimensional, (c) two-dimensional, and (d) three-dimensional transverse field
Ising model defined in Eq. (2) in the main text.

The TN representations allow obtaining the minimum of the variational energy
conveniently, varying with the parameters $\phi$ and
$\\{\alpha_{i},\beta_{i}\\}$. Fig. 2 presents the optimized parameters for the
transverse field Ising model in one, two, three spatial dimensions. Notice
that the variational parameter ($\phi$) of the mean operator $\hat{M}$ plays
the role of a mean-field order parameter as it should be.

##  III  3\. Symmetry Protected Topological Phase

We employ the MPS and MPO representations for the wavefunction ansatz and the
symmetric operators (or the time-evolution unitary operators) to study the
Hamiltonian $H_{2}$ exhibiting the transition between trivial and SPT phases.
As highlighted previously, the tensor network representation lowers the
computational costs significantly for evaluating the variational energy and
thus enables us to treat deeper MOTs. In particular, in this section, we
provide detailed information on the MPS and MPO. The initial state
$|\\{+\\}\rangle$ can be expressed by the following MPS representation:

$\displaystyle|\\{+\\}\rangle=\sum_{\\{\sigma_{i}\\}}{\rm
Tr}\left(A^{\sigma_{1}}\cdots
A^{\sigma_{L}}\right)|\sigma_{1}\cdots\sigma_{L}\rangle,$ (6)

with $A^{\sigma}=\frac{1}{\sqrt{2}}I$. Here, $I$ stands for the $(2\times
2)$-identity matrix. The unitary operators can be recast as

$\displaystyle U=\sum_{\\{\sigma_{i}\\}}{\rm
Tr}\left(T^{\sigma_{1}}_{\sigma_{1}^{\prime}}\cdots
T^{\sigma_{L}}_{\sigma_{L}^{\prime}}\right)|\sigma_{1}\cdots\sigma_{L}\rangle\langle\sigma_{1}^{\prime}\cdots\sigma_{L}^{\prime}|,$
(7)

where

$\displaystyle
T^{\sigma}_{\sigma^{\prime}}=\begin{cases}\cos\alpha\,[I]^{\sigma}_{\sigma^{\prime}}+i\sin\alpha\,[Z]^{\sigma}_{\sigma^{\prime}}\quad{\rm
for}\quad U=e^{i\alpha\sum_{i}Z_{i}}\\\
\cos\alpha\,[I]^{\sigma}_{\sigma^{\prime}}+i\sin\alpha\,[X]^{\sigma}_{\sigma^{\prime}}\quad{\rm
for}\quad U=e^{i\alpha\sum_{i}X_{i}}\end{cases},$ (8)

and

$\displaystyle T^{\sigma}_{\sigma^{\prime}}=$
$\displaystyle\left(\begin{array}[]{cc}\cosh(\alpha)[I]^{\sigma}_{\sigma^{\prime}}&\sqrt{\cosh(i\alpha)}\sqrt{\sinh(i\alpha)}[Z]^{\sigma}_{\sigma^{\prime}}\\\
\sqrt{\cosh(i\alpha)}\sqrt{\sinh(i\alpha)}[Z]^{\sigma}_{\sigma^{\prime}}&\cosh(i\alpha)[I]^{\sigma}_{\sigma^{\prime}}\end{array}\right)$
(11)

for $U=e^{i\alpha\sum_{i}Z_{i}Z_{i+1}}$. The time-evolution operator
$e^{i\alpha\sum_{i}Z_{i}X_{i+1}Z_{i+2}}$ is represented as a product of local
MPOs as illustrated Fig. 3. The three-site MPO of $e^{i\alpha
Z_{i}X_{i+1}Z_{i+2}}$ is written in the following way:

$\displaystyle\left({\begin{array}[]{cc}\cos(\alpha)I_{i}&i\sin(\alpha)Z_{i}\end{array}}\right)\left(\begin{array}[]{cc}I_{i+1}&0\\\
0&X_{i+1}\end{array}\right)\left(\begin{array}[]{c}I_{i+2}\\\
Z_{i+2}\end{array}\right).$ (17)

In order to obtain the entanglement entropy, we exploit the canonical form of
the ansatz by following the standard procedure.

Figure 3: Applying $e^{i\alpha Z_{i}X_{i+1}Z_{i+2}}$ to the MPS by using each
$e^{i\alpha Z_{i}X_{i+1}Z_{i+2}}$. $T_{i}$ is each site tensor of the MPS.

##  IV 4\. Depth-zero calculations of $H(g,\lambda)$

We provide detailed information on the zero-depth calculations of
$H(g,\lambda)$. The Hamiltonian enjoys the duality,

$\displaystyle
H(1-\lambda,g)=\Big{(}\hat{M}(-\frac{\pi}{8},\frac{\pi}{24},0)^{\dagger}\Big{)}H(\lambda,g)\Big{(}\hat{M}(-\frac{\pi}{8},\frac{\pi}{24},0)\Big{)},$

generalized from the original Levin-Gu model. The variational state with the
mean operator, $\hat{M}(\theta,\phi,\psi)$, gives the variational energy,

$\displaystyle
E_{G}(\theta,\phi,\psi;\lambda,g)\equiv\left\langle\theta,\phi,\psi\left|H(\lambda,g)\right|\theta,\phi,\psi\right\rangle$
$\displaystyle=(1-\lambda)\left[S_{12\phi}F_{1}\left(\frac{\pi}{4}-2\theta,2\psi\right)-C_{12\phi}F_{2}\left(\frac{\pi}{4}-2\theta,2\psi\right)\right]$
$\displaystyle-\lambda\left[C_{12\phi}F_{1}\left(-2\theta,2\psi\right)+S_{12\phi}F_{2}\left(-2\theta,2\psi\right)\right]-3gS^{2}_{2\psi},$

with

$\displaystyle F_{1}(\theta,\psi)$ $\displaystyle\equiv$
$\displaystyle\frac{1}{4}C_{\psi}\Big{(}C_{2\theta}(3+C_{2\theta}^{2})-C_{2\theta}S_{2\theta}^{2}(6S_{\psi}^{2}+9S_{\psi}^{4})\Big{)},$
$\displaystyle F_{2}(\theta,\psi)$ $\displaystyle\equiv$
$\displaystyle\frac{1}{8}C_{\psi}\Big{(}6S_{2\theta}(1+3C_{2\theta}^{2})S_{\psi}^{2}-S_{2\theta}^{3}(12S_{\psi}^{4}+2S_{\psi}^{6})\Big{)}.$

The variational energy satisfies useful properties including

$\displaystyle E_{G}(\theta,\phi,\psi;\lambda,g)$ $\displaystyle=$
$\displaystyle E_{G}(\theta+\frac{\pi}{2},\phi,\psi;\lambda,g),$
$\displaystyle E_{G}(\theta,\phi,\psi;\lambda,g)$ $\displaystyle=$
$\displaystyle E_{G}(\theta,\phi+\frac{\pi}{6},\psi;\lambda,g),$
$\displaystyle E_{G}(\theta,\phi,\psi;\lambda,g)$ $\displaystyle=$
$\displaystyle
E_{G}(\theta+\frac{\pi}{4},\phi+\frac{\pi}{12},\psi;\lambda,g),$
$\displaystyle E_{G}(\theta,\phi,\psi;\lambda,g)$ $\displaystyle=$
$\displaystyle
E_{G}(\frac{3\pi}{8}-\theta,\frac{\pi}{24}-\phi,\psi;1-\lambda,g),$

which allow us to restrict the range of the parameters. The phase boundaries
may be determined by using the properties. For example, the boundary between
the trivial and SSB phases is determined by the condition,
$E_{G}(0,0,0;\lambda,g)=E_{G}(0,0,\psi;\lambda,g)$, near the onset of SSB.
With a small parameter $\psi$, the equation becomes

$\displaystyle-\lambda=(1-\lambda)(-3\psi^{2})-\lambda(1-2\psi^{2})-12g\psi^{2}+O(\psi^{3}),$

for $\lambda\in[0.5,1]$. Thus, its boundary is

$\displaystyle g=\frac{5}{12}\lambda-\frac{3}{12},$ (18)

and the duality enforces another phase boundary between SPT and SSB,

$\displaystyle g=-\frac{5}{12}\lambda+\frac{2}{12},$ (19)

for $\lambda\in[0,0.5]$.

##  V 5\. mean-operator theory of $Z_{2}$ gauge theory

In this section, we show that our MOT can be employed to construct a
topologically ordered state, if one allows a non-unitary mean-operator. As an
illustrative exmaple, we consider the $\mathbb{Z}_{2}$ gauge theory in a
$d$-dimensional hypercubic lattice ($d\geq 2$) Sachdev (2019),

$\displaystyle H_{3}(g)=-\sum_{a^{*}}F_{a^{*}}-g\sum_{(ij)}X_{(ij)},$
$\displaystyle F_{a^{*}}\equiv\prod_{(ij)\in a^{*}}Z_{(ij)}.$ (20)

Qubits with Pauli matrices on each link $(ij)$ connecting sites $i$ and $j$
are considered, and the flux operator ($F_{a^{*}}$) is defined on a dual
lattice labeled as $a^{*}$. The Hamiltonian enjoys the local $\mathbb{Z}_{2}$
symmetry, whose element is a product of $X$’s on the links sharing the site
$i$, $G_{i}=\prod_{(kl)\in i}X_{(kl)}$. A symmetric product state is
$|0\rangle=\prod_{(ij)}|+\rangle_{(ij)}$ with
$X_{(ij)}|+\rangle_{(ij)}=|+\rangle_{(ij)}$, which is the ground state of
$H_{3}(\infty)$.

Figure 4:  MOT Phase diagram of the $\mathbb{Z}_{2}$ gauge theory, $H_{3}(g)$,
in two spatial dimensions. Here, $g_{c}^{\rm exact}\simeq 0.33$ Blöte and Deng
(2002) is the true critical point, while $g_{c}^{(0)}$ and $g_{c}^{(1)}$
denote the transition points estimated by the depth-zero and depth-one MOT,
respectively. The expectation values of the Wilson loop operator are
illustrated to distinguish the two phases with the perimeter and area laws.

We choose the operators,

$\displaystyle\hat{M}_{3}(\phi)={\rm P}_{G}\cdot
e^{-i\phi\sum_{(ij)}Y_{(ij)}}$
$\displaystyle\hat{S}_{3}(\\{\alpha,\beta\\}_{p})=\prod_{a=1}^{p}e^{-i\alpha_{a}\sum_{(ij)}X_{(ij)}}e^{-i\beta_{a}\sum_{a^{*}}F_{a^{*}}},$
(21)

with the gauge-symmetrization operator, ${\rm
P}_{G}\equiv\prod_{i}(1+G_{i})/2$. Even at the depth-zero level, numerical
evaluations are necessary, and the corner transfer matrix renormalization
group with the tensor network representation is employed for measuring the
variational energy and the observables, including the Wilson loop operator,
$W=\prod_{\square}Z_{j}$, on a square $\square$.

We find two phases that exhibit the area and perimeter laws of the Wilson loop
respectively as shown in Fig. 4. The accuracy of the estimated critical point
is improved significantly by increasing the depth from zero to one. We believe
that the estimation becomes better and finally converges to the actual
transition with a higher level depth as shown in Fig. 5. The expectation value
of the Pauli operator $X$ exhibits a discontinuity at the transition between
the confined and deconfined phases as shown in the left panel of Fig. 5,
meaning that the $p=0$ and $p=1$ MOT anticipate the first-order phase
transition. However, the discontinuity becomes weaker while the transition
point comes closer to the exact one $g_{c}\simeq 0.33$. We, therefore, believe
that the MOT with sufficiently large depth may describe the continuous
transition correctly. In order to optimize the variational parameters, we
divide the parameter space ($0\leq\phi,\alpha_{1},\beta_{1}\leq\pi/4$) equally
and optimize to minimize the energy. The optimized parameters for the $p=1$
MOT are presented in the right panel of Fig. 5. The uneven behavior of the
optimized parameters is due to the finite distance between parameters.

We stress that the mean-operator $\hat{M}_{3}(\phi)$ is not symmetric under
the local $\mathbb{Z}_{2}$ transformation, but $\hat{M}_{3}(\phi){\rm P}_{G}$
is symmetric for all $\phi$, indicating that the ansatz is guaranteed to be
symmetric regardless of $\phi$. This property is crucial to explore the
topologically ordered state because the action of the mean-operator opens a
possibility to access a topologically distinct state while its symmetry
remains intact. In a sense, it is similar to the case of spontaneously-
symmetry-broken states where the action of a mean-operator accesses a
symmetry-broken state. Strictly speaking, our choice of $\hat{M}_{3}(\phi)$
requires the number of quantum operations proportional to a system size
similar to the recent realization of a topological order in a superconducting
system with about twenty qubits et al. (2021), which manifests the Lieb-
Robinson bound with local unitary circuits Ho and Hsieh (2019). It is highly
desirable to find a non-local mean-operator with a reduced number of quantum
operators, and we leave this important matter for future works.

Figure 5:  Left: the expectation value of the Pauli operator $X$. Right: the
optimized variational parameters of the depth-one MOT as a function of the
coupling constant $g$ of the $Z_{2}$ gauge theory.