figurec

# Pseudoentanglement Ain’t Cheap

Sabee Grewal<EMAIL_ADDRESS>The University of Texas at Austin. Vishnu
Iyer<EMAIL_ADDRESS>The University of Texas at Austin. William
Kretschmer<EMAIL_ADDRESS>Simons Institute for the Theory of Computing,
UC Berkeley. Daniel Liang<EMAIL_ADDRESS>Rice University.

###### Abstract

We show that any pseudoentangled state ensemble with a gap of $t$ bits of
entropy requires $\Omega(t)$ non-Clifford gates to prepare. This bound is
tight up to polylogarithmic factors if linear-time quantum-secure pseudorandom
functions exist. Our result follows from a polynomial-time algorithm to
estimate the entanglement entropy of a quantum state across any cut of qubits.
When run on an $n$-qubit state that is stabilized by at least $2^{n-t}$ Pauli
operators, our algorithm produces an estimate that is within an additive
factor of $\frac{t}{2}$ bits of the true entanglement entropy.

##  1 Introduction

Recent work [ABF+24] introduced the notion of pseudoentangled quantum states,
in analogy with pseudorandomness in classical computation. An ensemble of
quantum states is said to be pseudoentangled if states in the ensemble have
low entanglement across every bipartition, but they are difficult to
distinguish from states with much larger entanglement. A more formal
definition is the following:

######  Definition 1.1.

A pseudoentangled ensemble with gap $f(n)$ vs. $g(n)$ (where $f(n)>g(n)$)
consists of two ensembles of $n$-qubit states
$\\{\ket{\Psi_{k}},\ket{\Phi_{k}}\\}_{k}$ indexed by a key
$k\in\\{0,1\\}^{\mathrm{poly}(n)}$ such that

  * •

$\ket{\Psi_{k}}$ and $\ket{\Phi_{k}}$ are preparable in quantum polynomial
time.

  * •

With probability at least $1-\mathrm{poly}(n)$ over the choice of $k$, the
entanglement entropy across every cut of size $\Omega(f(n))$ of
$\ket{\Psi_{k}}$ (respectively, $\ket{\Phi_{k}}$) is $\Theta(f(n))$
(respectively, $\Theta(g(n))$).

  * •

For any polynomial $p(n)$, no polynomial-time quantum adversary can
distinguish

$\rho\coloneqq\mathop{\bf
E\/}_{k}\left[\ket{\Psi_{k}}\\!\\!\bra{\Psi_{k}}^{\otimes
p(n)}\right]\qquad\text{and}\qquad\sigma=\mathop{\bf
E\/}_{k}\left[\ket{\Phi_{k}}\\!\\!\bra{\Phi_{k}}^{\otimes p(n)}\right]$

with better than negligible success probability.

[ABF+24] showed that pseudoentangled states can be instantiated in polynomial
time and logarithmic depth, assuming the existence of quantum-secure one-way
functions. So, under a standard cryptographic assumption, there exists an
efficient construction of pseudoentanglement. Nevertheless, in applications,
we sometimes need constructions that are even simpler and more efficient, due
to constraints beyond total gate complexity. For example, [ABF+24] suggested
that a construction of “holographic” pseudoentangled states might imply that
the AdS/CFT dictionary is hard to compute. However, it remains open to build
such pseudoentangled states that are compatible with the laws of AdS/CFT.
There are also various other measures of quantum state complexity, beyond
circuit depth. For example, a counting argument shows that stabilizer states
and free-fermionic states can require super-logarithmic depth, but these
states are also “easy” in the sense that their evolutions are efficiently
classically simulable [AG04, Val02] and they are efficiently learnable [AG08,
Mon17, AG23].

In this work, we study the relationship between pseudoentanglement and non-
Clifford complexity. The Clifford group is a remarkably useful object in
quantum information that consists of all quantum circuits generated by
Hadamard, Phase, and CNOT gates. Clifford gates are almost universal for
quantum computing: the addition of any single-qubit non-Clifford gate gives
rise to a universal gate set, as shown by Shi [Shi02]. Generally speaking,
Clifford gates are “cheaper” than non-Clifford gates, in a sense that can be
formalized in a variety of applications. Examples where the cost of a quantum
operation is dominated by non-Clifford gates include quantum fault tolerance
based on magic state distillation [BK05], near-Clifford classical simulation
algorithms [AG04, BG16, RLCK19, BBC+19], and quantum learning algorithms based
on the stabilizer formalism [LC22, GIKL23a, GIKL23b, GIKL23c, GIKL23d, LOLH22,
LOH23, HG23, CLL23].

A related work by Grewal, Iyer, Kretschmer, and Liang [GIKL23d, GIKL23c]
investigated the stabilizer complexity of a different cryptographic object
called pseudorandom quantum states. These are ensembles of quantum states that
cannot be distinguished from Haar-random by any polynomial-time adversary. The
main result of [GIKL23c], improving upon earlier work by the same authors,
shows that $n$-qubit pseudorandom states require at least $\Omega(n)$ non-
Clifford gates. The present work asks whether a similar lower bound on non-
Clifford resources holds for quantum pseudoentanglement.

As it happens, several of the known pseudoentangled state ensembles are also
pseudorandom states ensembles, including the only known instantiations of
pseudoentanglement that achieve an optimal gap of $\Theta(n)$ vs. $\omega(\log
n)$ [ABF+24, GTB23]. However, [ABF+24] further observed that a pseudoentangled
ensemble need not be pseudorandom, nor vice-versa. Hence, it is not clear that
the computational resources needed to construct pseudoentangled states mirror
those for pseudorandom states.

On the other hand, existing work has made clear that that some amount of non-
Cliffordness is needed to generate pseudoentangled states. Fattal, Cubitt,
Yamamoto, Bravyi, and Chuang [FCY+04] gave an efficient algorithm for
computing the entanglement entropy across any bipartition of a stabilizer
state (i.e., a state preparable using Clifford gates only). Combined with
Montanaro’s algorithm for learning an unknown stabilizer state [Mon17], this
implies that any ensemble $\\{\ket{\Psi_{k}},\ket{\Phi_{k}}\\}_{k}$ of
stabilizer states cannot be pseudoentangled.

Our main result is an algorithm with a much stronger guarantee than the
combination of [FCY+04, Mon17]. In short, our algorithm estimates the
entanglement entropy of an unknown quantum state across any cut of qubits,
where the accuracy of the estimate scales with the number of Pauli operators
that stabilize the state (i.e., the number of Pauli operators for which the
state is a $+1$-eigenvector).

######  Theorem 1.2 (Informal version of Corollary 4.4).

There is a polynomial-time quantum algorithm that takes as input

  1. 1.

$O(n^{3})$ copies of an $n$-qubit quantum state $\ket{\psi}$ that is
stabilized by at least $2^{n-t}$ Pauli operators, and

  2. 2.

A bipartition $A\sqcup B=[n]$ of qubits,

and outputs an estimate of the entanglement entropy of $\ket{\psi}$ across the
partition. The estimate is within an additive factor of $\frac{t}{2}$ bits of
the true entanglement entropy, with high probability.

We remark that the set of states for which this is applicable is rather large
and includes states prepared by a Clifford circuit with up to
$\lfloor\frac{t}{2}\rfloor$ auxiliary single-qubit non-Clifford gates (such as
the $T$-gate). When the algorithm is run on a stabilizer state (i.e., when
$t=0$), then our algorithm outputs the entanglement entropy across any cut of
qubits _exactly_ , recovering the aforementioned result of [FCY+04, Mon17]. On
the other hand, the bounds degrade as $t$ becomes too close to $n$.

As a straightforward consequence, we show that pseudoentangled state ensembles
require a number of non-Clifford gates that scales linearly in the
pseudoentanglement gap.

######  Theorem 1.3 (Restatement of Corollary 4.5).

Any family of Clifford circuits that produces a pseudoentangled ensemble
$\\{\ket{\Psi_{k}},\ket{\Phi_{k}}\\}_{k}$ with entropy gap $f(n)\text{ vs.
}g(n)$ satisfying $f(n)-g(n)\geq t$ must use $\Omega(t)$ auxiliary non-
Clifford single-qubit gates.

So, pseudoentangled ensembles with the optimal $\Theta(n)$ vs. $\omega(\log
n)$ gap require a linear number of non-Clifford gates. Interestingly, this
matches the lower bound on non-Clifford gates needed for pseudorandom states
[GIKL23c].

Corollary 4.5 is optimal up to polylogarithmic factors under plausible
computational assumptions. In particular, Ma [Ma24] constructs pseudoentangled
state ensembles in $O(n\ \mathrm{polylog}(n))$ time under the assumption that
linear-time quantum-secure pseudorandom functions exist.111The details will be
included in a forthcoming work due to Ma [Ma24]. This is to say that under
this assumption, pseudoentangled state ensembles on $n$ qubits require at most
$O(n\ \mathrm{polylog}(n))$ non-Clifford gates in total. It is widely
conjectured that linear-time _classically_ -secure pseudorandom functions
exist [IKOS08, FLY22], and it is plausible that these (or other) constructions
are also secure against quantum adversaries.

Prior to this work, it was unknown if even $O(1)$ non-Clifford gates sufficed
to construct pseudoentangled states. While one can efficiently learn states
prepared by $O(\log n)$ non-Clifford gates [GIKL23a, GIKL23b], it is unclear
how to leverage those algorithms to estimate entanglement entropy. Following
intuition from simulation algorithms for near-Clifford circuits, whose running
times scale exponentially in the number of non-Clifford gates, it was also
conceivable that a super-logarithmic number of non-Clifford gates would be
sufficient to construct pseudoentangled states.

#### Concurrent Work

While finalizing this work, we became aware of independent and concurrent work
by Gu, Oliveiro, and Leone [GOL24]. Their [GOL24, Lemma 7] resembles our
Theorem 3.1. However, we only prove bounds for the von Neumann entropy,
whereas [GOL24] prove similar bounds for any $\alpha$-Rényi entanglement
entropy, which captures the von Neumann entropy as a special case.

###  1.1 Main Ideas

For an $n$-qubit quantum state $\ket{\psi}$, let $\mathrm{Weyl}(\ket{\psi})$
denote the Pauli operators $P$ for which $P\ket{\psi}=1$.222See Definition
2.10 for a formal definition. We find it convenient to work with Weyl
operators, a subset of Pauli operators that form a basis of
$\mathbb{C}^{2^{n}\times 2^{n}}$. One can think of $\mathrm{Weyl}(\ket{\psi})$
as the stabilizer group of $\ket{\psi}$ with all of the phase information
removed. For example, for any computational basis state $\ket{x}$,
$\mathrm{Weyl}(\ket{x})\equiv\\{I,Z\\}^{\otimes n}$. Let $A\sqcup B=[n]$ be a
bipartition of qubits. Denote $\mathrm{Weyl}(\ket{\psi})_{A}$ as the subset of
Pauli operators in $\mathrm{Weyl}(\ket{\psi})$ that act only the qubits
indexed by $A$, and define $\mathrm{Weyl}(\ket{\psi})_{B}$ analogously. We use
$\dim(G)$ to refer to the minimum number of generators of a group $G$. It is
easy to verify that $\mathrm{Weyl}(\ket{\psi})$,
$\mathrm{Weyl}(\ket{\psi})_{A}$, and $\mathrm{Weyl}(\ket{\psi})_{B}$ are
abelian subgroups of the Pauli group. We prove the following bounds on the
entanglement entropy across $(A,B)$, which hold for any quantum state.

######  Theorem 1.4 (Restatement of Theorem 3.1).

Let $\rho=\ket{\psi}\\!\\!\bra{\psi}$ be an $n$-qubit quantum state and let
$A\sqcup B=[n]$ be a partition of qubits. Then

$\dim\left(\mathrm{Weyl}(\ket{\psi})\right)-\dim\left(\mathrm{Weyl}(\ket{\psi})_{B}\right)-\lvert
A\rvert\leq\mathsf{S}(\rho_{A})\leq\lvert
A\rvert-\dim\left(\mathrm{Weyl}(\ket{\psi})_{A}\right),$

where $\rho_{A}=\mathrm{tr}_{B}(\rho)$ is the reduced density matrix of $\rho$
after tracing out the qubits in $B$ and $\mathsf{S}(\rho_{A})$ is the
entanglement entropy across $(A,B)$.

Crucially, the quantities in Theorem 1.4 can be (approximately) computed
efficiently, given a polynomial number of copies of $\ket{\psi}$. First, we
learn generators for $\mathrm{Weyl}(\ket{\psi})$ with Bell difference
sampling, a quantum measurement that consumes four copies of a state and
produces a Pauli operator (see the end of Section 2.1 for further detail).
Bell difference sampling many times, along with some classical post-
processing, suffices to (approximately) learn generators of
$\mathrm{Weyl}(\ket{\psi})$, as proven in prior work [GIKL23c, GIKL23a]. Then,
using these generators of $\mathrm{Weyl}(\ket{\psi})$, we can compute
(approximations of) $\mathrm{Weyl}(\ket{\psi})_{A}$ and
$\mathrm{Weyl}(\ket{\psi})_{B}$ in polynomial time by solving a system of
linear constraints. We note that these approximations suffice, due to a result
of Audenaert [Aud07, Theorem 1], which relates the entanglement entropy of
states that are close in trace distance.

Let us now explain how the upper and lower bounds in Theorem 1.4 are proved,
and then explain some applications. At a high level, we argue that there exist
Clifford circuits acting locally on either $A$ or $B$ that exhibit
entanglement (or the lack thereof) in the system. Because the Clifford
circuits are local, we conclude that the original state must have the same
entanglement (or lack thereof). The formal proofs are given in Section 3.

We begin with the upper bound. Trivially, the entanglement entropy is at most
$\lvert A\rvert$. To simplify the presentation, define
$a\coloneqq\dim(\mathrm{Weyl}(\ket{\psi})_{A})$. By known techniques, one can
construct a Clifford circuit acting only on $A$ that maps
$\mathrm{Weyl}(\ket{\psi})_{A}$ to Pauli-$Z$ strings on a subset of $a$
qubits.333It is well known that Clifford unitaries map Pauli operators to
Pauli operators, see Section 2.1 for more detail. This has the effect of
mapping the state $\ket{\psi}$ to a _product state_ where a subset of $a$
qubits in $A$ are in a computational basis state and the remaining qubits are
in some arbitrary state. The $a$ qubits cannot be entangled with the rest of
the system, and our upper bound follows.

For the lower bound, we argue that there exist Clifford circuits acting
locally on $A$ and $B$, respectively, that distill EPR pairs across qubits of
$A$ and $B$. Observe that the EPR state is stabilized by the Pauli operators
generated by $X\otimes X$ and $Z\otimes Z$. While these two Pauli operators
commute with one another, they locally anticommute (i.e., $X$ and $Z$ do not
commute). Clifford circuits acting locally on $A$ (or $B$, respectively) do
not affect the global or local commutation relations. As such, any pair of
locally anticommuting Pauli operators in $\mathrm{Weyl}(\psi)$ can be mapped,
via local Clifford circuits on $A$ and $B$, respectively, to $X\otimes X$ and
$Z\otimes Z$, creating an EPR pair on one qubit of $A$ and $B$ each. Our lower
bound follows from counting the number of EPR pairs we can produce in this
way.

For both the upper and lower bounds, the Clifford circuits can be found
efficiently. Indeed, a similar approach played a crucial role in the
tomography algorithms given in [GIKL23a, GIKL23b]. Additionally, one can view
our lower bound as an efficient algorithm for entanglement distillation of
quantum states with large stabilizer dimension (Definition 2.11), which may be
of independent interest.

We conclude by explaining how to apply Theorem 1.4 to get our entanglement
estimation algorithm (Theorem 1.2) and the pseudoentanglement lower bound
(Theorem 1.3). Our algorithm outputs upper and lower bounds $(u,\ell)$,
essentially by computing the quantities appearing in Theorem 1.4. When run on
a quantum state $\ket{\psi}$ that is stabilized by least $2^{n-k}$ Pauli
operators, we prove that $u-\ell\leq k$. Therefore, $\frac{u+\ell}{2}$ will
always be within an additive factor of $\frac{k}{2}$ bits of the true
entanglement entropy. As a corollary, we obtain a lower bound on preparing
pseudoentangled states. Suppose we have two state ensembles
$\\{\ket{\Psi_{k}}\\}_{k}$ and $\\{\ket{\Phi_{k}}\\}_{k}$ that are prepared
with at most $t$ non-Clifford gates. If we run our entropy estimation
algorithm on copies drawn from either ensemble, we will recover upper and
lower bounds $(u,\ell)$ such that $u-\ell\leq 2t$. Therefore, the
pseudoentanglment gap between these ensembles is at most $2t$.

##  2 Preliminaries

For a positive integer $n$, $[n]\coloneqq\\{1,2,\dots,n\\}$. For
$x=(a,b)\in\mathbb{F}_{2}^{2n}$, $a$ and $b$ always denote the first and last
$n$ coordinates of $x$, respectively. For vectors $v_{1},\ldots,v_{k}$,
$\langle v_{1},\ldots,v_{k}\rangle$ denotes their span. For matrix
$X\in\mathbb{C}^{d\times d}$, $\lVert X\rVert_{1}$ denotes the sum of the
absolute values of its singular values (known as the trace norm, nuclear norm,
or Schatten 1-norm). For quantum mixed states $\rho,\sigma$,
$\mathrm{dist}_{\rm{tr}}\coloneqq\frac{1}{2}\lVert\rho-\sigma\rVert_{1}$ is
the trace distance. For us, $\log$ denotes the logarithm with base $2$, and
$\ln$ is the logarithm with base $e\approx 2.718$.

Let $A\sqcup B$ be a partition of $[n]$. We refer to $(A,B)$ as a _cut_ of $n$
qubits. Let $\rho$ be an $n$-qubit quantum state. The entanglement entropy
across $(A,B)$ is defined as

$\mathsf{S}(\rho_{A})\coloneqq-\mathrm{tr}(\rho_{A}\log\rho_{A})=-\mathrm{tr}(\rho_{B}\log\rho_{B}),$

where $\rho_{A}=\mathrm{tr}_{B}(\rho)$ and $\rho_{B}=\mathrm{tr}_{A}(\rho)$
are the states obtained by tracing out $B$ and $A$, respectively.

Define the binary entropy function $\mathsf{H}(p)$ by

$\mathsf{H}(p)=-p\log(p)-(1-p)\log(1-p).$

The following is a well-known upper bound on $\mathsf{H}(p)$.

######  Fact 2.1.

$\mathsf{H}(p)\leq\left(4p(1-p)\right)^{1/\ln 4}\leq e\cdot p^{1/\ln 4}\leq
e\cdot p^{0.72}.$

If two states are close in trace distance, then so is their entanglement
entropy.

######  Lemma 2.2 (Fannes-Audenaert inequality [Aud07, Theorem 1]).

Let $\rho=\ket{\psi}\\!\\!\bra{\psi}$ and $\sigma=\ket{\phi}\\!\\!\bra{\phi}$
be $n$-qubit states satisfying
$\mathrm{dist}_{\mathrm{tr}}(\ket{\psi},\ket{\phi})\leq\varepsilon$, and let
$A\sqcup B=[n]$ be a partition. Then

$|\mathsf{S}(\rho_{A})-\mathsf{S}(\sigma_{A})|\leq\varepsilon
n+\mathsf{H}(\varepsilon)$

###  2.1 Symplectic Vector Spaces and Weyl Operators

There is a deep connection between quantum information and symplectic vector
spaces over $\mathbb{F}_{2}$ that we leverage throughout this work. Many in
the quantum information and theoretical computer science communities may not
be familiar with this connection, so we take care to review these notions
here.

To obtain a symplectic vector space, one must equip a vector space with a
symplectic form.

######  Definition 2.3 (Symplectic form).

Let $V$ be a vector space over a field $\mathbb{F}$. A symplectic form is a
mapping $\omega:V\times V\to\mathbb{F}$ that satisfies the following
conditions.

  1. 1.

Bilinear: $\omega$ is linear in each argument separately.

  2. 2.

Alternating: For all $v\in V$, $\omega(v,v)=0$.

  3. 3.

Non-degenerate: If for all $v\in V$, $\omega(u,v)=0$, then $u=0$.

A symplectic vector space is a pair $(V,\omega)$, where $V$ is a vector space
and $\omega$ is a symplectic form. We will equip $\mathbb{F}_{2}^{2n}$ with
the standard symplectic form, which we refer to as the symplectic product.

######  Definition 2.4 (Symplectic product).

For $x,y\in\mathbb{F}_{2}^{2n}$, we define the symplectic product as
$[x,y]=x_{1}\cdot y_{n+1}+x_{2}\cdot y_{n+2}+\dots+x_{n}\cdot
y_{2n}+x_{n+1}\cdot y_{1}+x_{n+2}\cdot y_{2}+\dots+x_{2n}\cdot y_{n}$.

In this work, one should always view $\mathbb{F}_{2}^{2n}$ as a symplectic
vector space equipped with the symplectic product.

The symplectic product allows us to define the symplectic complement.

######  Definition 2.5 (Symplectic complement).

Let $T\subseteq F_{2}^{2n}$ be a subspace. The symplectic complement of $T$,
denoted by $T^{\perp}$, is defined by

$T^{\perp}\coloneqq\\{a\in\mathbb{F}_{2}^{2n}:\forall x\in T,[x,a]=0\\}.$

We will also need the notion of isotropic and symplectic subspaces.

######  Definition 2.6 (Isotropic subspace).

A subspace $W\subseteq\mathbb{F}_{2}^{2n}$ is isotropic when $W\subseteq
W^{\perp}$. Equivalently, $W$ is isotropic if and only if $[w_{1},w_{2}]=0$
for all $w_{1},w_{2}\in W$.

######  Definition 2.7 (Symplectic subspace).

A subspace $W\subseteq\mathbb{F}_{2}^{2n}$ is symplectic when $W\cap
W^{\perp}=\\{0\\}$.

Every symplectic space has a standard basis, which we refer to as the
_symplectic basis_.

######  Fact 2.8.

Any $2d$-dimensional symplectic space over $\mathbb{F}_{2}$ has a basis
$\\{x_{1},\dots,x_{d},z_{1},\dots,z_{d}\\}$ such that

$[x_{i},z_{j}]=\delta_{ij}\qquad\text{and}\qquad[x_{i},x_{j}]=[z_{i},z_{j}]=0.$

Any basis with the above form is referred to as a symplectic basis.

The direct sum of two symplectic vector spaces is also symplectic. This is a
basic fact, but we include a proof for completeness.

######  Fact 2.9.

If $V,W$ are symplectic vector spaces over $\mathbb{F}_{2}$, so is their
direct sum.

###### Proof.

Denote the symplectic forms on $V$ and $W$ by $\omega_{V}$ and $\omega_{W}$,
respectively. Let $A\coloneqq V\oplus W$, where $V\oplus W=\\{(v,w):v\in
V,w\in W\\}$. Define the form $\omega_{A}$ on $A$ by
$\omega_{A}(a_{1},a_{2})=\omega_{V}(v_{1},v_{2})+\omega_{W}(w_{1},w_{2})$
where $a_{i}=v_{i}+w_{i}$. We will prove that $(A,\omega_{A})$ is symplectic.

It is obvious that $A$ is a vector space, so it remains to prove that
$\omega_{A}$ is a symplectic form. Recall from Definition 2.3 that we must
show that $\omega_{A}$ is bilinear, alternating, and non-degenerate. It is
clear that $\omega_{A}$ is bilinear because it is the sum of two bilinear
forms. For $a=(v,w)\in A$, we have
$\omega_{A}(a,a)=\omega_{V}(v,v)+\omega_{W}(w,w)=0$, so $\omega_{A}$ is
alternating.

Finally, we prove that $\omega_{A}$ is non-degenerate. Suppose we have an
element $a=(v,w)$ such that for all $a^{\prime}\in A$ we have
$\omega_{A}(a,a^{\prime})=\omega_{V}(v,v^{\prime})+\omega_{W}(w,w^{\prime})=0$.
Now choose a $v^{\prime}\in V$ such that $[v,v^{\prime}]=0$ (one must exist
since $V$ is symplectic).
$\omega_{A}(a,a^{\prime})=\omega_{V}(v,v^{\prime})+\omega_{W}(w,w^{\prime})=0$
by assumption, and, because $\omega_{V}(v,v^{\prime})=0$, it follows that
$\omega_{W}(w,w^{\prime})=0$ for all $w^{\prime}\in W$. Since $\omega_{W}$ is
non-degenerate, $w=0$. A similar argument shows that $v=0$. Therefore,
$\omega_{A}$ is non-degenerate. ∎

Each element of $\mathbb{F}_{2}^{2n}$ can be identified with a _Weyl
operator_. For $x=(a,b)\in\mathbb{F}_{2}^{2n}$, let $a^{\prime},b^{\prime}$ be
the embeddings of $a,b$ into $\mathbb{Z}^{n}$, respectively. Then the Weyl
operator $W_{x}$ is defined as

$W_{x}\coloneqq i^{a^{\prime}\cdot
b^{\prime}}(X^{a_{1}}Z^{a_{1}})\otimes\dots\otimes(X^{a_{n}}Z^{b_{n}}).$

The symplectic structure of $\mathbb{F}_{2}^{2n}$ respects the commutation
relations of the Weyl operators. Specifically, for
$x,y\in\mathbb{F}_{2}^{2n}$, $[x,y]=0$ iff $W_{x}W_{y}=W_{y}W_{x}$. Therefore,
working with symplectic vector spaces lets us discard cruft while retaining
relevant algebraic structure. We also note that Weyl operators form an
orthogonal basis of $\mathbb{C}^{2^{n}\times 2^{n}}$ with respect to the
Hilbert-Schmidt inner product, so every quantum state and unitary
transformation can be written as a linear combination of Weyl operators.

We define $\mathcal{Z}\coloneqq 0^{n}\times\mathbb{F}_{2}^{n}$ as the subset
of $\mathbb{F}_{2}^{2n}$ corresponding to Pauli-$Z$ strings. We define the
unsigned stabilizer group of a quantum state as the subspace of
$\mathbb{F}_{2}^{2n}$ that stabilizes or anti-stabilizes the state.

######  Definition 2.10 (Unsigned stabilizer group).

Given an $n$-qubit quantum state $\ket{\psi}$,
$\mathrm{Weyl}(\ket{\psi})\coloneqq\\{x\in\mathbb{F}_{2}^{2n}:W_{x}\ket{\psi}=\pm\ket{\psi}\\}$
is the unsigned stabilizer group of $\ket{\psi}$.

It is easy to verify that $\mathrm{Weyl}(\ket{\psi})$ is an isotropic
subspace. We define the stabilizer dimension, which quantifies the size of the
Pauli group stabilizing a given state.

######  Definition 2.11 (Stabilizer dimension).

Let $\ket{\psi}$ be a $n$-qubit pure state. The _stabilizer dimension_ of
$\ket{\psi}$ is the dimension of $\mathrm{Weyl}(\ket{\psi})$ as a subspace of
$\mathbb{F}_{2}^{2n}$.

The stabilizer dimension of a state is closely related to the number of non-
Clifford gates required to prepare it.

######  Fact 2.12 ([GIKL23c, Lemma 4.2]).

Let $\ket{\psi}$ be an $n$-qubit state which is the output of a Clifford
circuit with at most $t$ single-qubit non-Clifford gates. Then $\ket{\psi}$
has stabilizer dimension at least $n-2t$.

For a Clifford circuit $C$ and any $x\in\mathbb{F}_{2}^{2n}$, we define $C(x)$
to be the $y\in\mathbb{F}_{2}^{2n}$ such that $W_{y}=\pm CW_{x}C^{\dagger}$.
We can extend this notation to subsets $S$ of $\mathbb{F}_{2}^{2n}$ by writing
$C(S)=\\{C(x):x\in S\\}$. Conjugation by any Clifford circuit is an
automorphism of the Pauli group. Furthermore, $C(x)$ preserves the symplectic
form.

######  Fact 2.13.

For any Clifford circuit $C$ and $x,y\in\mathbb{F}_{2}^{2n}$,
$[C(x),C(y)]=[x,y]$.

###### Proof.

Recall that $W_{C(x)}W_{C(y)}=(-1)^{[C(x),C(y)]}W_{C(y)}W_{C(x)}$. Suppose
that $W_{C(x)}=(-1)^{c_{1}}CW_{x}C^{\dagger}$ and
$W_{C(y)}=(-1)^{c_{2}}CW_{y}C^{\dagger}$. We have

$\displaystyle W_{C(x)}W_{C(y)}$
$\displaystyle=(-1)^{c_{1}+c_{2}}CW_{x}C^{\dagger}CW_{y}C^{\dagger}$
$\displaystyle=(-1)^{c_{1}+c_{2}}CW_{x}W_{y}C^{\dagger}$
$\displaystyle=(-1)^{[x,y]}(-1)^{c_{1}+c_{2}}CW_{y}W_{x}C^{\dagger}$
$\displaystyle=(-1)^{[x,y]}(-1)^{c_{1}+c_{2}}CW_{y}C^{\dagger}CW_{x}C^{\dagger}$
$\displaystyle=(-1)^{[x,y]}W_{C(y)}W_{C(x)}.$

Thus $[C(x),C(y)]=[x,y]$. ∎

Since the inverse of any Clifford circuit is itself a Clifford circuit, we
have the following as a simple corollary:

######  Corollary 2.14.

Given a subspace $H\subseteq\mathbb{F}_{2}^{2n}$ and a Clifford circuit $C$,
$H$ is isotropic (resp. symplectic) if and only if $C(H)$ is isotropic (resp.
symplectic).

Finally, we remark on Bell difference sampling [Mon17, GNW21], an algorithmic
primitive used in this work. Define $p_{\psi}(x)\coloneqq
2^{-n}\braket{\psi}{W_{x}}{\psi}^{2}$. Bell difference sampling is a quantum
measurement that takes four copies of a state $\ket{\psi}$, and produces a
sample $x\in\mathbb{F}_{2}^{2n}$ drawn from the distribution $q_{\psi}$ which
is defined as

$q_{\psi}(x)\coloneqq\sum_{a\in\mathbb{F}_{2}^{2n}}p_{\psi}(a)p_{\psi}(x+a).$

This process takes $O(n)$ time. We refer readers to [GIKL23c, Section 2] for
further detail.

##  3 Entanglement Entropy Bounds

We prove upper and lower bounds on the entanglement entropy across any cut of
qubits for any $n$-qubit quantum state $\ket{\psi}$. The quality of our bounds
depends on $\mathrm{Weyl}(\ket{\psi})$. For example, if
$\dim(\mathrm{Weyl}(\ket{\psi}))=0$, our bounds become trivial, and, if
$\dim(\mathrm{Weyl}(\ket{\psi}))=n$ (i.e., $\ket{\psi}$ is a stabilizer
state), our bounds are tight, recovering the main result of [FCY+04].

To state our bounds, we must introduce some notation. Let $A\subseteq[n]$ be a
subset of qubits, and let $S$ be a subspace of $\mathbb{F}_{2}^{2n}$. We
denote by $S_{A}$ the intersection of $S$ with operators that act only on
qubits indexed by $A$. In symbols, we can express this as follows:

$S_{A}\coloneqq\\{(x,z)\in S:\forall i\in[n]\setminus A,x_{i}=z_{i}=0\\}.$

So, for example,

$\mathcal{Z}_{A}\coloneqq\\{(0^{n},z)\in\mathbb{F}_{2}^{2n}:\forall
i\in[n]\setminus A,z_{i}=0\\}$

are essentially the Pauli-$Z$ strings that act on the qubits indexed by $A$.

Computationally speaking, one can compute $S_{A}$ efficiently, given a basis
of $S$, by solving a system of linear constraints to zero all coordinates
corresponding to $i\in[n]\setminus A$.

In the remainder of this section, we prove the following theorem.

######  Theorem 3.1.

Let $\rho=\ket{\psi}\\!\\!\bra{\psi}$ be an $n$-qubit quantum state and let
$A\sqcup B=[n]$ be a partition of qubits. Then

$\dim\left(\mathrm{Weyl}(\ket{\psi})\right)-\dim\left(\mathrm{Weyl}(\ket{\psi})_{B}\right)-\lvert
A\rvert\leq\mathsf{S}(\rho_{A})\leq\lvert
A\rvert-\dim\left(\mathrm{Weyl}(\ket{\psi})_{A}\right).$

###  3.1 Proof of Upper Bound

######  Lemma 3.2.

Let $\rho=\ket{\psi}\\!\\!\bra{\psi}$ be an $n$-qubit quantum state and let
$A\subseteq[n]$ be a partition of qubits. Then

$\mathsf{S}(\rho_{A})\leq\lvert
A\rvert-\dim\left(\mathrm{Weyl}(\ket{\psi})_{A}\right).$

###### Proof.

Let $A^{\prime}\subseteq A$ be any set of size
$\dim(\mathrm{Weyl}(\ket{\psi})_{A})$. By known techniques, one can find a
Clifford circuit $C$ acting only on $A$ that maps the Paulis in
$\mathrm{Weyl}(\ket{\psi})_{A}$ to $\mathcal{Z}_{A^{\prime}}$.444An explicit
algorithm for computing this $C$ can be found in [GIKL23a, Section 3]. As a
consequence, this $C$ behaves as
$C\ket{\psi}=\ket{x}_{A^{\prime}}\ket{\phi}_{[n]\setminus A^{\prime}}$, where
$\ket{x}_{A^{\prime}}$ is a computational basis state on $A^{\prime}$ and
$\ket{\phi}_{[n]\setminus A^{\prime}}$ is an arbitrary state on the remaining
qubits. Because $C$ is local to $A$, it does not affect the entanglement
entropy across the partition. Furthermore, it is clear that the qubits
$\ket{x}_{A^{\prime}}$ are unentangled from the rest of the system. As such,
only the qubits in $A\setminus A^{\prime}$ can exhibit entanglement across the
partition, and there are $\lvert A\rvert-\lvert A^{\prime}\rvert=\lvert
A\rvert-\dim\left(\mathrm{Weyl}(\ket{\psi})_{A}\right)$ many such qubits. So,
the entanglement entropy across the partition is bounded above by $\lvert
A\rvert-\dim\left(\mathrm{Weyl}(\ket{\psi})_{A}\right)$. ∎

###  3.2 Proof of Lower Bound

######  Lemma 3.3.

Let $V\subseteq\mathbb{F}_{2}^{2n}$ be a symplectic subspace of dimension $2v$
and have $S\subseteq V$ be a subspace of dimension $v+k$. There exists a
symplectic subspace $T\subseteq S$ with dimension at least $2k$.

###### Proof.

Take any nonzero $e_{1}\in S$. Because $\dim(S)>v$, there exists some
$f_{1}\in S$ such that $[e_{1},f_{1}]=1$. Let $W_{1}$ be the span of $e_{1}$
and $f_{1}$. We will prove that $S=W_{1}\oplus\left(W_{1}^{\perp}\cap
S\right)$ is a direct sum. First, we argue that
$W_{1}\cap\left(W_{1}^{\perp}\cap S\right)=\\{0\\}$.555In fact, because
$W_{1}$ is symplectic, even $W_{1}\cap W_{1}^{\perp}=\\{0\\}$. Take $z\in
W_{1}$. Since $W$ is the span of $e_{1}$ and $f_{1}$, we can write $z=\alpha
e_{1}+\beta f_{1}$. If $z$ is also in $W^{\perp}\cap S\subseteq W^{\perp}$,
then $0=[x,z]=\beta$ and $0=[y,z]=\alpha$, so $z=0$. Next, we prove that any
$v\in S$ can be written as a sum of $w_{1}\in W_{1}$ and $w_{1}^{c}\in
W_{1}^{\perp}\cap S$. Clearly $w_{1}\coloneqq[v,e_{1}]f_{1}+[v,f_{1}]e_{1}\in
W_{1}$, and define $w_{1}^{c}\coloneqq v+[v,e_{1}]f_{1}+[v,f_{1}]e_{1}$. It is
easy to check $[e_{1},w_{1}^{c}]=[f_{1},w_{1}^{c}]=0$, so $w_{1}^{c}\in
W_{1}^{\perp}$. Furthermore, if since $e_{1},f_{1}\in W_{1}\subset S$,
$w_{1}^{c}\in S$ as well. It is clear that $v=w_{1}+w_{1}^{c}$.

Repeat this process to collect pairs $(e_{1},f_{1}),\dots,(e_{r},f_{r})$ until
we have that $S\cap_{j=1}^{r}W_{j}^{\perp}$ doesn’t contain an $e_{r+1}$ and
$f_{r+1}$ such that $[e_{r+1},f_{r+1}]=1$. Observe by linearity that any
object in $x\in\cap_{j=1}^{r}W_{j}^{\perp}$ must have $[x,y]=0$ for all
$y\in\bigoplus_{i=1}^{r}W_{i}$. Consequently,
$S\cap_{j=1}^{r}W_{j}^{\perp}\oplus\langle e_{1},\ldots,e_{r}\rangle$ is an
isotropic subspace of dimension $v+k-r$. Since all isotropic subspaces within
$V$ must have dimension at most $v$,

$v+k-r\leq v\implies r\geq k.$

Hence, $\bigoplus_{i=1}^{r}W_{i}$ has dimension at least $2k$. Since each
$W_{i}$ is symplectic, their direct sum is symplectic by 2.9. ∎

######  Lemma 3.4.

Let $\rho=\ket{\psi}\\!\\!\bra{\psi}$ be an $n$-qubit quantum state and let
$A\sqcup B=[n]$ be a partition of qubits. Then

$\mathsf{S}(\rho_{A})\geq\dim\left(\mathrm{Weyl}(\ket{\psi})\right)-\dim\left(\mathrm{Weyl}(\ket{\psi})_{B}\right)-\lvert
A\rvert.$

###### Proof.

Let $\\{b_{i}\\}_{i}$ be a basis for $\mathrm{Weyl}(\ket{\psi})_{B}$, and let
$\\{e_{i}\\}_{i}$ be an extension such that, together, they span
$\mathrm{Weyl}(\ket{\psi})$. Define the subspace
$S\coloneqq\langle\\{e_{i}\\}_{i}\rangle$. Clearly
$\dim(S)=\dim(\mathrm{Weyl}(\ket{\psi}))-\dim(\mathrm{Weyl}(\ket{\psi})_{B})$
and $S\cap\left(\mathbb{F}_{2}^{2n}\right)_{B}=\\{0\\}$. Define
$e^{A}_{i}\in\left(\mathbb{F}_{2}^{2n}\right)_{A}$ to be $e_{i}$ except with
the coordinates not in $A$ set to $0$.

Define $S^{A}\coloneqq\langle\\{e^{A}_{i}\\}_{i}\rangle$.

  * ######  Claim 3.5.

$\dim(S^{A})=\dim(S)=\dim(\mathrm{Weyl}(\ket{\psi}))-\dim(\mathrm{Weyl}(\ket{\psi})_{B})$

###### Proof.

$\dim(S)\geq\dim(S^{A})$ is trivial, so we just need to argue that the vectors
$\\{e_{i}^{A}\\}_{i}$ are linearly independent. For the sake of contradiction,
assume they’re not, i.e., that there exists some set of indices
$I\subseteq[\dim(S)]$ such that $\sum_{i\in I}e^{A}_{i}=0$. Note that
$\sum_{i\in I}e_{i}\neq 0$ because is $\\{e_{i}\\}_{i}$ is a basis by
construction. Therefore, $\sum_{i\in I}e_{i}$ will be zero on the coordinates
of $A$, but not $B$. That is, $\sum_{i\in
I}e_{i}\in\mathrm{Weyl}(\ket{\psi})_{B}$, a contradiction. We conclude that
$\dim(S^{A})=\dim(\mathrm{Weyl}(\ket{\psi}))-\dim(\mathrm{Weyl}(\ket{\psi})_{B})$.
∎

$(\mathbb{F}_{2}^{2n})_{A}$ is a symplectic subspace, and each
$e^{A}_{i}\in(\mathbb{F}_{2}^{2n})_{A}$. Therefore, $S^{A}$ is a subspace of a
$2\lvert A\rvert$-dimensional symplectic subspace. By Lemma 3.3, there must
exist some symplectic subspace $T^{A}\subseteq S^{A}$ of dimension at least
$2\left(\dim\left(S^{A}\right)-\lvert
A\rvert\right)=2\left(\dim\left(\mathrm{Weyl}(\ket{\psi})\right)-\dim\left(\mathrm{Weyl}(\ket{\psi})_{B}\right)-\lvert
A\rvert\right)$. Let $\\{t_{i}^{A}\\}_{i}$ be a symplectic basis of $T^{A}$.
We can express each basis element as $t_{i}^{A}=\sum_{j}\alpha_{j}e^{A}_{j}$
for some setting of $\alpha_{j}\in\\{0,1\\}$. Define
$t_{i}\coloneqq\sum_{j}\alpha_{j}e_{j}$, and observe that their span defines a
subspace $T\subseteq\mathbb{F}_{2}^{2n}$ that shares the same dimension as
$T^{\prime}$. We can then similarly define
$t^{B}_{i}\in\left(\mathbb{F}_{2}^{2n}\right)_{B}$ to be $t_{i}$ except with
the coordinates not in $B$ set to $0$. Observe that
$t_{i}=t^{A}_{i}+t^{B}_{i}$. By the linearity of the symplectic product and
the fact that $\mathrm{Weyl}(\ket{\psi})$ is isotropic,

$0=[t_{i},t_{j}]=[t^{A}_{i},t^{A}_{j}]+[t^{B}_{i},t^{B}_{j}]\implies[t^{A}_{i},t^{A}_{j}]=[t^{B}_{i},t^{B}_{j}].$

Therefore, $\\{t_{i}^{B}\\}$ is also a symplectic basis for a symplectic
subspace of $\left(\mathbb{F}_{2}^{2n}\right)_{B}$.

Using a Clifford circuit $C^{A}$ acting locally on the qubits in $A$, we can
perform the symplectic map that takes $\\{t_{i}^{A}\\}$ to the symplectic
basis of $\left(\mathbb{F}_{2}^{2n}\right)_{A^{\prime}}$ where
$A^{\prime}\subset A$ and $\lvert A^{\prime}\rvert=\dim(T)$.666Again, this
mapping is described in detail in [GIKL23a, Section 3]. Note that
$C^{A}(t_{i}^{B})=t_{i}^{B}$. Using a second Clifford circuit $C^{B}$ acting
locally on the qubits in $B$, we can take $\\{t_{i}^{B}\\}$ to the symplectic
basis of $\left(\mathbb{F}_{2}^{2n}\right)_{B^{\prime}}$ where
$B^{\prime}\subset B$ and $\lvert B^{\prime}\rvert=\lvert
A^{\prime}\rvert=\dim(T)$. Note $C^{B}(C^{A}(t_{i}^{A}))=C^{A}(t_{i}^{A})$.

  * ######  Claim 3.6.

$C^{B}(C^{A}(T))$ is a Lagrangian subspace of
$\left(\mathbb{F}_{2}^{2n}\right)_{A^{\prime}\sqcup B^{\prime}}$.

###### Proof.

It is clear from the actions of $C^{A}$ and $C^{B}$ that each
$C^{B}(C^{A}(t_{i}))$ is a member of
$\left(\mathbb{F}_{2}^{2n}\right)_{A^{\prime}\sqcup B^{\prime}}$. Furthermore,
$\dim\left(C^{B}(C^{A}(T))\right)=\dim(T)$, which is half the dimension of
$\left(\mathbb{F}_{2}^{2n}\right)_{A^{\prime}\sqcup B^{\prime}}$. Finally,
since $C^{B}\left(C^{A}\left(\mathrm{Weyl}(\ket{\psi})\right)\right)$ is
isotropic, so too must $C^{B}(C^{A}(T))$ as a subset of
$C^{B}\left(C^{A}\left(\mathrm{Weyl}(\ket{\psi})\right)\right)$. ∎

We conclude that the state of the qubits indexed by $A^{\prime}\sqcup
B^{\prime}$ is a stabilizer state $\ket{\phi}$ of $2\dim(T)$ qubits that is
unentangled from the rest of the system.

Our last step is to prove that $C^{B}(C^{A}(T))_{B^{\prime}}=\\{0\\}$, which
will imply that the entanglement across $(A^{\prime},B^{\prime})$ is
$\dim(T)/2$ by [FCY+04, Eq. 1]. First recall that
$S\cap\left(\mathbb{F}_{2}^{2n}\right)_{B}=\\{0\\}$ by construction, which
implies $T\cap\left(\mathbb{F}_{2}^{2n}\right)_{B}=\\{0\\}$ because
$T\subseteq S$. Next, we note that $C^{A}$ has no effect on
$\left(\mathbb{F}_{2}^{2n}\right)_{B}$ since its action is local to $A$.
Furthermore, $C^{B}$ simply permutes $\left(\mathbb{F}_{2}^{2n}\right)_{B}$
(and cannot map elements into $(\mathbb{F}_{2}^{2n})_{B})$. Hence,

$C^{B}(C^{A}(T))\cap\left(\mathbb{F}_{2}^{2n}\right)_{B}=C^{B}(C^{A}(T))\cap
C^{B}(C^{A}(\left(\mathbb{F}_{2}^{2n}\right)_{B})=T\cap\left(\mathbb{F}_{2}^{2n}\right)_{B}=\\{0\\}.$

Finally, since
$\left(\mathbb{F}_{2}^{2n}\right)_{B^{\prime}}\subseteq\left(\mathbb{F}_{2}^{2n}\right)_{B}$,

$C^{B}(C^{A}(T))_{B^{\prime}}=C^{B}(C^{A}(T))\cap\left(\mathbb{F}_{2}^{2n}\right)_{B^{\prime}}=\\{0\\}.$

Because $C^{A}$ and $C^{B}$ act locally on $A$ and $B$ respectively, they do
not change the entanglement between $A$ and $B$, thus completing the proof. ∎

##  4 The Algorithm

We present and analyze our algorithm for estimating the entanglement entropy
across any bipartition of qubits. At a high level, our algorithm computes the
upper and lower bounds given in Theorem 3.1. The details are presented below
in Algorithm 1.

Input: $\frac{8\ln(1/\delta)+16n}{\varepsilon^{2}}$ copies of
$\rho=\ket{\psi}\\!\\!\bra{\psi}$, $A\sqcup B=[n]$, $\varepsilon\in(0,3/8)$,
and $\delta\in(0,1]$

Promise : $\ket{\psi}$ has stabilizer dimension at least $n-k$

Output: $\ell,u\in\mathbb{R}$ such that $\ell\leq\mathsf{S}(\rho_{A})\leq u$
and $0\leq u-\ell\leq k+\max\\{0,2(\varepsilon
n+\mathsf{H}(\varepsilon))-1\\}$, with probability at least $1-\delta$

1

2Perform Bell difference sampling to draw
$\frac{2\ln(1/\delta)+4n}{\varepsilon^{2}}$ samples from $q_{\psi}$.

3Let $S$ be the symplectic complement of the subspace spanned by the samples.

4Let $r\coloneqq\begin{cases}0&\dim(S)=n-k,\\\ \varepsilon
n+\mathsf{H}(\varepsilon)&\dim(S)>n-k.\end{cases}$

5Let $u\coloneqq\min\\{|A|-\dim S_{A},|B|-\dim S_{B}\\}+r$.

6Let $\ell\coloneqq\max\\{\dim S-\dim S_{B}-|A|,\dim S-\dim S_{A}-|B|\\}-r$.

7return _$(\ell,u)$_

Algorithm 1 Estimating Entanglement Entropy

Let us make a few remarks on Algorithm 1. Note that the bounds $(u,\ell)$
produced by our algorithm are within a range of $k+\max\\{0,2\left(\varepsilon
n+\mathsf{H}(\varepsilon)\right)-1\\}$ rather than $k+2\left(\varepsilon
n+\mathsf{H}(\varepsilon)\right)$ as one might naïvely expect. This comes from
a subtle case in our analysis, the details of which are contained in the proof
of Theorem 4.3. We observe that in the case where our sampling procedure
happens to find the exact subspace $\mathrm{Weyl}(\ket{\psi})$, we no longer
need to apply Lemma 2.2. Conversely, when our sampling procedure fails to find
$\mathrm{Weyl}(\ket{\psi})$ exactly, the distance between the bounds in Lemmas
3.4 and 3.2 decreases by at least $1$.

We also note that the Bell difference sampling procedure only needs to be
performed once. After that, one can compute entanglement entropy bounds across
any cut of qubits with only classical post-processing.

To prove the correctness of Algorithm 1, we use the following two statements.
The first is about the time complexity of computing symplectic complements.
The second says that Bell difference sampling suffices to approximately
recover $\mathrm{Weyl}(\ket{\psi})$.

######  Fact 4.1 ([GIKL23a, Lemma 3.1]).

Given a set of $m$ vectors whose span is a subspace
$H\subseteq\mathbb{F}_{2}^{2n}$, there is an algorithm that outputs a basis
for $H^{\perp}$ in $O\left(mn\cdot\min(m,n)\right)$ time.

######  Lemma 4.2 ([GIKL23a, Proof of Theorem 5.1]).

Let $\ket{\psi}$ have stabilizer dimension at least $n-k$, and let $S$ be the
symplectic complement of the space spanned by
$\frac{2\ln(1/\delta)+4n}{\varepsilon}$ samples from $q_{\psi}$, for some
$\varepsilon\in(0,3/8)$. Then with probability at least $1-\delta$, there
exists a state $\ket{\phi}$ such that
$S=\mathrm{Weyl}(\ket{\phi})\supseteq\mathrm{Weyl}(\ket{\psi})$ and
$\lvert\braket{\psi}{\phi}\rvert^{2}\geq 1-\varepsilon$.

We now show our main result, namely that Algorithm 1 is correct as specified.

######  Theorem 4.3.

Algorithm 1 is correct and runs in time
$O\left(\frac{n^{3}+n^{2}\log(1/\delta)}{\varepsilon^{2}}\right)$.

###### Proof.

Let $S$ be the symplectic complement of the subspace spanned by our
$\frac{2\ln(1/\delta)+4n}{\varepsilon^{2}}$ samples from $q_{\psi}$. We note
that these samples take $4$ copies of $\rho$ and $O(n)$ time each, and that
$S$ can be computed in time
$O\left(\frac{n^{3}+n^{2}\log(1/\delta)}{\varepsilon^{2}}\right)$ by 4.1.

By Lemma 4.2, with probability at least $1-\delta$, there exists a state
$\ket{\phi}$ such that
$S=\mathrm{Weyl}(\ket{\phi})\supseteq\mathrm{Weyl}(\ket{\psi})$ and
$\lvert\braket{\psi}{\phi}\rvert^{2}\geq 1-\varepsilon^{2}$, and therefore
$\mathrm{dist}_{\mathrm{tr}}(\ket{\psi},\ket{\phi})\leq\varepsilon$. Assume
henceforth that $S$ and $\ket{\phi}$ satisfy these criteria. In fact, we can
further assume $\mathrm{dist}_{\mathrm{tr}}(\ket{\psi},\ket{\phi})\leq d$,
where

$d\coloneqq\begin{cases}0&\dim(S)=n-k,\\\ \varepsilon&\dim(S)>n-k,\end{cases}$

because if $\dim(S)=n-k$, we must have $S=\mathrm{Weyl}(\ket{\psi})$, and
hence we can choose $\ket{\phi}=\ket{\psi}$.

Let $\sigma=\ket{\phi}\\!\\!\bra{\phi}$. By Lemma 3.2, we have

$u^{\prime}\coloneqq\min\\{|A|-\dim S_{A},|B|-\dim
S_{B}\\}\geq\mathsf{S}(\sigma_{A}).$

Similarly, Lemma 3.4 implies

$\ell^{\prime}\coloneqq\max\\{\dim S-\dim S_{B}-|A|,\dim S-\dim
S_{A}-|B|\\}\leq\mathsf{S}(\sigma_{A}).$

Note that $r=dn+\mathsf{H}(d)$, $\ell=\ell^{\prime}-r$, and $u=u^{\prime}+r$.
Recalling that $\mathrm{dist}_{\mathrm{tr}}(\ket{\psi},\ket{\phi})\leq d$,
Lemma 2.2 implies that $\ell\leq\mathsf{S}(\rho_{A})\leq u$. So, this
establishes that $u$ and $\ell$ are upper and lower bounds, respectively, on
the entanglement entropy.

It remains to bound the difference between $u$ and $\ell$. Observe that

$\displaystyle u-\ell$ $\displaystyle=(u^{\prime}+r)-(\ell^{\prime}-r)$
$\displaystyle\leq(|A|-\dim S_{A})-(\dim S-\dim S_{A}-|B|)+2r$
$\displaystyle=|A|+|B|-\dim S+2r$ $\displaystyle=n-\dim S+2r.$

In the case where $\dim S=n-k$, we have $u-\ell\leq k$. Otherwise, when
$\dim(S)>n-k$, we have

$\displaystyle n-\dim S+2r$ $\displaystyle\leq n-(n-k+1)+2r$
$\displaystyle=k+2r-1$ $\displaystyle=k+2(\varepsilon
n+\mathsf{H}(\varepsilon))-1.$

In both cases, for all $S\supseteq\mathrm{Weyl}(\ket{\psi})$, we have

$u-\ell\leq k+\max\left\\{0,2r-1\right\\},$

which completes the proof. ∎

If we take $\varepsilon$ to be sufficiently small, we can disregard the
additional additive error $2r-1$.

######  Corollary 4.4.

By setting $\varepsilon=\frac{1}{8n}$, Algorithm 1 outputs upper and lower
bounds on the entanglement entropy $(u,\ell)$ such that $u-\ell\leq k$ with
probability at least $1-\delta$. It now uses $1024n^{3}+512n^{2}\ln(1/\delta)$
samples of $\ket{\psi}$ and runs in time
$O\left(n^{5}+n^{4}\log(1/\delta)\right)$.

###### Proof.

Assume $n\geq 2$, because we don’t need to compute the entanglement of a
single qubit state. 2.1 tells us that $\mathsf{H}(\varepsilon)<0.37$, and
therefore $2(\varepsilon n+H(\varepsilon))-1<2(1/8+0.37)-1<0$. So,
$\max\left\\{0,2(\varepsilon n+H(\varepsilon))-1\right\\}=0$. We then appeal
to Theorem 4.3. ∎

As a corollary, we can show a lower bound on the number of non-Clifford gates
necessary to prepare pseudoentangled states.

######  Corollary 4.5.

Any family of Clifford circuits that produces a pseudoentangled ensemble
$\\{\ket{\Psi_{k}},\ket{\Phi_{k}}\\}_{k}$ with entropy gap $f(n)\text{ vs.
}g(n)$ satisfying $f(n)-g(n)\geq t$ must use $\Omega(t)$ auxiliary non-
Clifford single-qubit gates.

###### Proof.

Suppose $t^{\prime}$ non-Clifford gates are used to construct
$\\{\ket{\Psi_{k}}\\}_{k}$ and $\\{\ket{\Phi_{k}}\\}_{k}$. We argue that if
$2t^{\prime}<t$, these state ensembles can be distinguished with non-
negligible advantage in polynomial time.

All such states $\ket{\Psi_{k}}$ and $\ket{\Phi_{k}}$ have stabilizer
dimension at least $n-2t^{\prime}$, by 2.12. The distinguisher, then, is the
following: given copies of an unknown $\ket{\psi}$ belonging to one of the two
ensembles, run Algorithm 1 according to Corollary 4.4, assuming stabilizer
dimension at least $n-2t^{\prime}$ and $\delta=1/3$. This produces bounds
$(u,\ell)$ on the entanglement entropy of $\ket{\psi}$ across some fixed cut
$(A,B)$ of size $n/2$. Then, output that
$\ket{\psi}\in\\{\ket{\Psi_{k}}\\}_{k}$ if $\ell\leq f(n)\leq u$, and output
$\ket{\psi}\in\\{\ket{\Phi_{k}}\\}_{k}$ otherwise. The algorithm guesses
correctly with probability at least $2/3$, because $u-\ell\leq 2t^{\prime}$,
so at most one of $f(n)$ and $g(n)$ can lie between $u$ and $\ell$. ∎

## Acknowledgments

We thank Tony Metger for suggesting this problem to us, and Fermi Ma for
helpful conversations.

SG is supported (via Scott Aaronson) by a Vannevar Bush Fellowship from the US
Department of Defense, the Berkeley NSF-QLCI CIQC Center, a Simons
Investigator Award, and the Simons “It from Qubit” collaboration. VI is
supported by an NSF Graduate Research Fellowship. WK acknowledges support from
the U.S. Department of Energy, Office of Science, National Quantum Information
Science Research Centers, Quantum Systems Accelerator. DL is supported by NSF
award FET-2243659.

This work was done in part while SG, VI, and DL were visiting the Simons
Institute for the Theory of Computing.

## References

  * [ABF+24] Scott Aaronson, Adam Bouland, Bill Fefferman, Soumik Ghosh, Umesh Vazirani, Chenyi Zhang, and Zixin Zhou.  Quantum Pseudoentanglement.  In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024), volume 287 of Leibniz International Proceedings in Informatics (LIPIcs), pages 2:1–2:21, 2024.  doi:10.4230/LIPIcs.ITCS.2024.2.
  * [AG04] Scott Aaronson and Daniel Gottesman.  Improved Simulation of Stabilizer Circuits.  Physical Review A, 70(5), 2004.  doi:10.1103/physreva.70.052328.
  * [AG08] Scott Aaronson and Daniel Gottesman.  Identifying Stabilizer States, 2008.  https://pirsa.org/08080052.
  * [AG23] Scott Aaronson and Sabee Grewal.  Efficient Tomography of Non-Interacting-Fermion States.  In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023), volume 266 of Leibniz International Proceedings in Informatics (LIPIcs), pages 12:1–12:18, 2023.  doi:10.4230/LIPIcs.TQC.2023.12.
  * [Aud07] Koenraad M. R. Audenaert.  A sharp continuity estimate for the von Neumann entropy.  Journal of Physics A: Mathematical and Theoretical, 40(28):8127, 2007.  doi:10.1088/1751-8113/40/28/S18.
  * [BBC+19] Sergey Bravyi, Dan Browne, Padraic Calpin, Earl Campbell, David Gosset, and Mark Howard.  Simulation of quantum circuits by low-rank stabilizer decompositions.  Quantum, 3:181, 2019.  doi:10.22331/q-2019-09-02-181.
  * [BG16] Sergey Bravyi and David Gosset.  Improved Classical Simulation of Quantum Circuits Dominated by Clifford Gates.  Phys. Rev. Lett., 116:250501, 2016.  doi:10.1103/PhysRevLett.116.250501.
  * [BK05] Sergey Bravyi and Alexei Kitaev.  Universal quantum computation with ideal Clifford gates and noisy ancillas.  Phys. Rev. A, 71:022316, 2005.  doi:10.1103/PhysRevA.71.022316.
  * [CLL23] Nai-Hui Chia, Ching-Yi Lai, and Han-Hsuan Lin.  Efficient learning of $t$-doped stabilizer states with single-copy measurements, 2023.  arXiv:2308.07014.
  * [FCY+04] David Fattal, Toby S. Cubitt, Yoshihisa Yamamoto, Sergey Bravyi, and Isaac L. Chuang.  Entanglement in the stabilizer formalism, 2004.  arXiv:quant-ph/0406168.
  * [FLY22] Zhiyuan Fan, Jiatu Li, and Tianqi Yang.  The Exact Complexity of Pseudorandom Functions and the Black-Box Natural Proof Barrier for Bootstrapping Results in Computational Complexity.  In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, page 962–975, 2022.  doi:10.1145/3519935.3520010.
  * [GIKL23a] Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang.  Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates, 2023.  arXiv:2305.13409.
  * [GIKL23b] Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang.  Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates II: Single-Copy Measurements, 2023.  arXiv:2308.07175.
  * [GIKL23c] Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang.  Improved Stabilizer Estimation via Bell Difference Sampling, 2023.  arXiv:2304.13915.
  * [GIKL23d] Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang.  Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom.  In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), volume 251 of Leibniz International Proceedings in Informatics (LIPIcs), pages 64:1–64:20, 2023.  doi:10.4230/LIPIcs.ITCS.2023.64.
  * [GNW21] David Gross, Sepehr Nezami, and Michael Walter.  Schur–Weyl duality for the Clifford group with applications: Property testing, a robust Hudson theorem, and de Finetti representations.  Communications in Mathematical Physics, 385(3):1325–1393, 2021.  doi:10.1007/s00220-021-04118-7.
  * [GOL24] Andi Gu, Salvatore F. E. Oliviero, and Lorenzo Leone.  Magic-induced computational separation in entanglement theory, 2024.  arXiv:2403.19610.
  * [GTB23] Tudor Giurgica-Tiron and Adam Bouland.  Pseudorandomness from subset states, 2023.  arXiv:2312.09206.
  * [HG23] Dominik Hangleiter and Michael J. Gullans.  Bell sampling from quantum circuits, 2023.  arXiv:2306.00083v1.
  * [IKOS08] Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai.  Cryptography with Constant Computational Overhead.  In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC ’08, page 433–442, 2008.  doi:10.1145/1374376.1374438.
  * [LC22] Ching-Yi Lai and Hao-Chung Cheng.  Learning Quantum Circuits of Some $T$ Gates.  IEEE Transactions on Information Theory, 68(6):3951–3964, 2022.  doi:10.1109/TIT.2022.3151760.
  * [LOH23] Lorenzo Leone, Salvatore F. E. Oliviero, and Alioscia Hamma.  Learning t-doped stabilizer states, 2023.  arXiv:2305.15398v1.
  * [LOLH22] Lorenzo Leone, Salvatore F. E. Oliviero, Seth Lloyd, and Alioscia Hamma.  Learning efficient decoders for quasi-chaotic quantum scramblers, 2022.  arXiv:2212.11338.
  * [Ma24] Fermi Ma.  Personal communication, 2024.
  * [Mon17] Ashley Montanaro.  Learning stabilizer states by Bell sampling, 2017.  arXiv:1707.04012.
  * [RLCK19] Patrick Rall, Daniel Liang, Jeremy Cook, and William Kretschmer.  Simulation of qubit quantum circuits via Pauli propagation.  Phys. Rev. A, 99:062337, 2019.  doi:10.1103/PhysRevA.99.062337.
  * [Shi02] Yaoyun Shi.  Both Toffoli and Controlled-NOT need little help to do universal quantum computation, 2002.  arXiv:quant-ph/0205115.
  * [Val02] Leslie G. Valiant.  Quantum Circuits That Can Be Simulated Classically in Polynomial Time.  SIAM Journal on Computing, 31(4):1229–1254, 2002.  doi:10.1137/S0097539700377025.


# Romanization-based Large-scale Adaptation
of Multilingual Language Models

Sukannya Purkayastha1 Sebastian Ruder2 Jonas Pfeiffer2 Iryna Gurevych1 Ivan
Vulić3
1 Ubiquitous Knowledge Processing Lab,
Department of Computer Science and Hessian Center for AI (hessian.AI),
Technical University of Darmstadt
2 Google Research
3 Language Technology Lab, University of Cambridge
www.ukp.tu-darmstadt.de

###### Abstract

Large multilingual pretrained language models (mPLMs) have become the de facto
state of the art for cross-lingual transfer in NLP. However, their large-scale
deployment to many languages, besides pretraining data scarcity, is also
hindered by the increase in vocabulary size and limitations in their parameter
budget. In order to boost the capacity of mPLMs to deal with low-resource and
unseen languages, we explore the potential of leveraging transliteration on a
massive scale. In particular, we explore the uroman transliteration tool,
which provides mappings from UTF-8 to Latin characters for all the writing
systems, enabling inexpensive romanization for virtually any language. We
first focus on establishing how uroman compares against other language-
specific and manually curated transliterators for adapting multilingual PLMs.
We then study and compare a plethora of data- and parameter-efficient
strategies for adapting the mPLMs to romanized and non-romanized corpora of 14
diverse low-resource languages. Our results reveal that uroman-based
transliteration can offer strong performance for many languages, with
particular gains achieved in the most challenging setups: on languages with
unseen scripts and with limited training data without any vocabulary
augmentation. Further analyses reveal that an improved tokenizer based on
romanized data can even outperform non-transliteration-based methods in the
majority of languages.

##  1 Introduction

Massively multilingual language models (mPLMs) such as mBERT Devlin et al.
(2019) and XLM-R Conneau et al. (2020) have become the driving force for a
variety of applications in multilingual NLP Ponti et al. (2020); Hu et al.
(2020); Moghe et al. (2022). However, guaranteeing and maintaining strong
performance for a wide spectrum of low-resource languages is difficult due to
two crucial problems. The first issue is the vocabulary size, as the
vocabulary is bound to increase with the number of languages added if per-
language performance is to be maintained Hu et al. (2020); Artetxe et al.
(2020); Pfeiffer et al. (2022). Second, pretraining mPLMs with a fixed model
capacity improves cross-lingual performance up to a point after which it
starts to decrease; this is the phenomenon termed the curse of multilinguality
Conneau et al. (2020).

Figure 1: Romanization across different languages.

Transliteration refers to the process of converting language represented in
one writing system to another Wellisch et al. (1978). Latin script-centered
transliteration or romanization is the most common form of transliteration Lin
et al. (2018); Amrhein and Sennrich (2020); Demirsahin et al. (2022) as the
Latin/Roman script is by far the most widely adopted writing script in the
world Daniels and Bright (1996); van Esch et al. (2022).111According to
Encyclopedia Britannica, up to 70% of the world population is employing the
Latin script. Adapting mPLMs via transliteration can address the two
aforementioned critical issues. 1) Since the Latin script covers a dominant
portion of the mPLM’s vocabulary (e.g., $77\%$ in case of mBERT, see Ács ),
‘romanizing’ the remaining part of the vocabulary might mitigate the
vocabulary size issue and boost vocabulary sharing. 2) Since no new tokens are
added during the romanization process, reusing pretrained embeddings from the
mPLM’s embedding matrix helps reuse the information already present within the
mPLM, thereby allocating the model’s parameter budget more efficiently.

However, the main drawback of transliteration seems to be the expensive
process of creating effective language-specific transliterators, as they
typically require language expertise to curate dictionaries that map tokens
from one language and script to another. Therefore, previous attempts at mPLM
adaptation to unseen languages via transliteration Muller et al. (2021); Chau
and Smith (2021); Dhamecha et al. (2021); Moosa et al. (2022) were constrained
to a handful of languages due to the limited availability of language-specific
transliterators, or were applied only to languages that have ‘language
siblings’ with developed transliterators.

In this work, unlike previous work, we propose to use and then evaluate the
usefulness of a universal romanization tool, uroman Hermjakob et al. (2018),
for quick, large-scale and effective adaptation of mPLMs to low-resource
languages. The uroman tool disposes of language-specific curated dictionaries
and maps any UTF-8 character to the Latin script, increasing the portability
of romanization, with some examples in Figure 1.

We analyze language adaptation on a massive scale via uroman-based
romanization on a set of 14 diverse low-resource languages. We conduct
experiments within the standard parameter-efficient adapter-based cross-
lingual transfer setup on two tasks: Named Entity Recognition (NER) on the
WikiANN dataset Pan et al. (2017); Rahimi et al. (2019), and Dependency
Parsing (DP) with Universal Dependencies v2.7 Nivre et al. (2020). Our key
results suggest that uroman-based transliteration can offer strong performance
on par or even outperforming adaptation with language-specific
transliterators, setting up the basis for wider use of transliteration-based
mPLM adaptation techniques in future work. The gains with romanization-based
adaptation over standard adaptation baselines are particularly pronounced for
languages with unseen scripts ($\sim$8-22 performance points) without any
vocabulary augmentation.222Our code and data are available online at [URL].

##  2 Background

Why uroman-Based Romanization?  uroman-based romanization is not always fully
reversible, and its usage for transliteration has thus been limited in the
literature. However, due to its high portability, uroman can help scale the
process of transliteration massively and as such benefit low-resource
scenarios and wider adaptation of mPLMs. The main idea, as hinted in §1, is to
(learn to) map any UTF-8 character to the Latin script, without the use of any
external language-specific dictionaries (see Hermjakob et al. (2018) for
technical details).

Cross-Lingual Transfer to Low-Resource Languages. Parameter-efficient and
modular fine-tuning methods Pfeiffer et al. (2023) such as adapters Houlsby et
al. (2019); Pfeiffer et al. (2020b) have been used for cross-lingual transfer,
putting a particular focus on enabling transfer to low-resource languages and
scenarios, including languages with scripts ‘unseen’ by the base mPLM Pfeiffer
et al. (2021). Adapters are small lightweight components stitched into the
base mPLM, and then trained for particular languages and tasks while keeping
the parameters of the original mPLM frozen. This circumvents the issues of
catastrophic forgetting and interference McCloskey and Cohen (1989) within the
mPLM, and allows for extending its reach also to unseen languages Pfeiffer et
al. (2021); Ansell et al. (2021).

For our main empirical analyses, we adopt a state-of-the-art modular method
for cross-lingual transfer: MAD-X Pfeiffer et al. (2020b). In short, MAD-X is
based on language adapters (LA), task adapters (TA), and invertible adapters
(INV). While LAs are trained for specific languages relying on masked language
modeling, TAs are trained with high-resource languages relying on task-
annotated data and task-specific objectives. At inference, the source LA is
replaced with the target LA while the TA is kept. In order to do parameter-
efficient learning for the token-level embeddings across different languages
and to deal with the vocabulary mismatch between source and target languages,
Pfeiffer et al. (2020b) also propose INV adapters: they are placed on top of
the embedding layer and their inverses precede the output embedding
layer.333They are trained together with the LAs while the rest of the mPLM is
kept frozen. We adopt the better-performing MAD-X 2.0 setup Pfeiffer et al.
(2021) where the adapters in the last Transformer layer are dropped at
inference.444We refer the reader to the original papers for further technical
details regarding the MAD-X framework.

##  3 Experiments and Results

As the main means of analyzing the impact of transliteration in general and
uroman-based romanization in particular, we train different variants of
language adapters within the MAD-X framework, based on transliterated and non-
transliterated versions of target language data, outlined here.

Variants with Non-Transliterated Data. For the Non-TransLA+INV variant, we
train LAs and INV adapters together. This variant serves to examine the extent
to which mPLMs can adapt to unseen languages without any vocabulary
extension.555Since LAs without INV typically perform worse than with INV
Pfeiffer et al. (2020b), also confirmed in our preliminary experiments, we do
not ablate to the setup without INV. We compare this to Non-TransLA+EmbLex,
which trains a new tokenizer for the target language Pfeiffer et al. (2021):
the so-called ‘lexically overlapping’ tokens are initialized with mPLM’s
trained embeddings, while the remaining embeddings are initialized randomly.
All these embeddings (EmbLex) are fine-tuned along with LAs.

Variants with Transliterated Data. We evaluate a TransLA+INV variant, which
uses the same setup as Non-TransLA+INV but now with transliterated data. We
again note that in this efficient setup, we do not extend the vocabulary size,
and use the fewest trainable parameters. In the TransLA+mPLMft variant, we
train LAs along with fine-tuning the pretrained embeddings of mPLM (mPLMft).
This further enhances the model capacity by fine-tuning the embedding layer
instead of using invertible adapters.666We do not have this setup for non-
transliterated data since, for languages with unseen scripts, most of the
tokens are replaced by the generic ‘UNK’ token, and fine-tuning embeddings
hardly benefit downstream performance. For both variants, transliterated data
can be produced via different transliterators: (i) language-specific ones;
(ii) the ones from ‘language siblings’ (e.g., using a Georgian transliterator
for Mingrelian), or (iii) uroman.

###  3.1 Experimental Setup

Data, Languages and Tasks. Following Pfeiffer et al. (2021), we select mBERT
as our base mPLM. We experiment with $14$ typologically diverse low-resource
languages that are not part of mBERT’s pretraining corpora, with $5/14$
languages written in distinct scripts (see Appendix A for details). For LA
training, we use Wikipedia dumps for the target languages, which we also
transliterate (using different transliterators). Evaluation is conducted on
two standard cross-lingual transfer tasks in zero-shot setups: 1) the WikiAnn
NER dataset Pan et al. (2017) with the train, dev, and test splits from Rahimi
et al. (2019); 2) for dependency parsing, we rely on the UD Dataset v2.7 Nivre
et al. (2020).

LAs and TAs. English is the source language in all experiments, and is used
for training TAs. The English LA is obtained directly from Adapterhub.ml
Pfeiffer et al. (2020a), LAs and embeddings (when needed) are only trained for
target languages. The details of LA and TA training, including the chosen
hyperparameters are available in Appendix C.

Finally, for the Non-TransLA+EmbLex variant, we train a WordPiece tokenizer on
the target language data with a vocabulary size of $10$K.

Task Transliterator am ar ka ru hi sd avg NER (Macro F1) uroman 25.6 24.8 61.4
66.5 48.6 35.3 43.7 Other 25.5 23.7 57.3 63.9 56.7 35.9 43.8 UD (UAS / LAS)
uroman 36.1 / 6.6 33.0 / 19.8 - 47.3 / 32.4 33.8 /17.8 - 37.5 / 19.1 Other
29.9 / 5.4 32.6 / 19.9 - 45.0 / 19.9 33.2 / 17.9 - 35.2 / 15.8

Table 1: Comparison of uroman with language-specific transliterators.

Seen Script Unseen Script Method bh cdo ckb mhr sd ug xmf am bo dv km si avg
uroman 32.59 27.34 67.73 64.68 35.33 28.10 52.58 25.69 35.95 29.99 41.76 31.83
26.89 BORROW 53.42 (hi) - 12.46 (ar) 45.86 (ru) 16.79 (ar) 12.85 (ar) 24.77
(ru) - - - - - - RAND 25.42 19.51 53.55 42.02 27.20 25.18 35.82 18.00 18.95
21.19 32.75 20.01 21.59

Table 2: Comparison of various transliteration strategies on the NER task
(Macro-F1).

Seen Script Unseen Script Variant bh cdo sd xmf mhr ckb ug am bo dv km si avg
Non-TransLA+INV 55.14 24.19 31.31 49.74 70.31 45.54 33.53 3.26 19.86 18.72
13.81 23.14 18.39 TransLA + INV 32.59 27.34 35.33 52.58 64.68 67.73 28.10
25.69 35.95 29.99 41.76 31.83 26.89 Non-TransLA+EmbLex 60.00 28.91 42.47 51.99
61.05 79.12 50.42 47.60 40.96 31.21 53.94 45.89 49.01 TransLA + mPLMft 49.05
36.92 39.16 57.99 69.85 73.92 33.43 37.09 33.82 40.40 52.39 45.24 47.44

Table 3: Results (Macro-F1 scores) on WikiAnn NER averaged over 6 random
seeds.

Seen Script Unseen Script Variant bh myv ug bxr am avg Non-TransLA+INV 28.46 /
11.53 45.28 / 26.27 33.44 / 15.28 39.75 / 19.77 19.08 / 1.85 33.20 / 10.81
TransLA + INV 25.12 / 10.17 45.74 / 26.64 32.30 / 15.10 37.92 / 17.23 36.07 /
7.58 35.43 / 12.41 Non-TransLA+EmbLex 26.68 / 10.10 48.34 / 25.34 41.20 /
22.81 39.51 / 16.02 36.47 / 8.39 38.44 / 12.20 TransLA + mPLMft 28.04 / 11.13
41.97 / 20.29 50.89 / 16.56 35.03 / 20.29 39.10 / 9.00 39.01 / 14.65

Table 4: Results (UAS / LAS scores) in the DP task with UD, averaged over 6
random seeds.

###  3.2 Results and Discussion

uroman versus Other Transliterators and Transliteration Strategies. In order
to establish the utility of uroman as a viable transliterator, especially for
low-resource languages, we compare its performance with transliteration
options using the TransLA + INV setup as the most efficient scenario. First,
we compare uroman with language-specific transliterators available for
selected languages: amseg Yimam et al. (2021) for Amharic, ai4bharat-
transliteration Madhani et al. (2022) for Hindi and Sindhi, lang-trans for
Arabic, and transliterate for Russian and Georgian.777For reproducibility, the
links to the language-specific transliterators are available in Appendix B.
The results are provided in Table 1. On average, uroman performs better or
comparable to the language-specific transliterators. This provides
justification to use uroman for massive transliteration at scale.

Second, we compare uroman to two other transliteration strategies. (i) BORROW
refers to borrowing transliterators from languages within the same language
family and written in the same script.888E.g., a Hindi transliterator can be
borrowed for Bhojpuri since the two are related and written in Devanagari.
Since building transliterators are costly, this gives us an estimate of
whether it is possible to rely on the related transliterators when we do not
have a language-specific one at hand. (ii) RAND refers to a random setting
where we associate any non-ASCII character with any ASCII character, giving us
an estimate of whether we actually need knowledge of the language to build
transliterators. The results are provided in Table 2: uroman is largely and
consistently outperforming both BORROW and RAND, where the single exception is
BORROW (from Hindi to Bhojpuri). Surprisingly, RAND also yields reasonable
performance and on average even outperforms the Non-TransLA+INV variant with
non-transliterated data (21.59 vs 18.39 in Table 3 later). This provides
further evidence towards the utility of transliteration in general and uroman-
based romanization in particular to assist and improve language adaptation.

Performance on Low-Resource Languages is summarized in Table 3 and Table 4. We
note that TransLA+INV outperforms Non-TransLA+INV for all the languages with
unseen scripts, and achieves that with huge margins ($\sim$ 8-22 points for
NER and $\sim$ 17 points in UAS scores). We observe similar trends for some of
the languages with seen scripts such as Min Dong (cdo), Sindhi (sd),
Mingrelian (xmf) on NER tasks and Erzya (myv) on DP. The less efficient
TransLA+mPLMft, as expected, further improves the performance for all the
languages except for Tibetan (bo).999For Tibetan, longer words are composed
using shorter words separated by tsek (“.”) which is not a valid space
delimiter for the mBERT tokenizer; the number of produced subwords is thus
much higher than for the other languages. Non-TransLA+EmbLex, however, now
outperforms uroman-based methods for a majority of the languages. This
observation can be attributed to various factors related to mBERT’s tokenizer,
and we provide an in-depth analysis later in Appendix E. Nonetheless, we
observe strong and competitive performance of TransLA + mPLMft in both tasks,
again indicating that more attention should be put on transliteration-based
language adaptation in future work.

Figure 2: Sample efficiency in the NER task.

Sample Efficiency. Finally, we simulate a few-shot setup to study the
effectiveness of using transliterated versus non-transliterated data in data-
scarce scenarios. For NER, we evaluate performance on all the languages and on
languages with unseen scripts; for DP, we evaluate on all the languages.
Figure 2 indicates that TransLA+INV on average performs better than all the
other methods at sample sizes $100$ (i.e., $100$ sentences in the target
language) and $1,000$. However, from $10,000$ sentences onward, Non-
TransLA+EmbLex takes the lead. We observe similar trends in the DP task (see
Appendix D). This establishes the utility of transliteration for (extremely)
low-resource scenarios.

##  4 Conclusion

In this work, we have systematically analyzed and confirmed the potential of
romanization, implemented via the uroman tool, to help with adaptation of
multilingual pretrained language models. Given (i) its broad applicability and
(ii) strong performance overall and for languages with unseen scripts, we hope
our study will inspire more work on transliteration-based adaptation.

## Limitations

In this paper, we work with uroman Hermjakob et al. (2018) which is an
unsupervised romanization tool. While it is an effective tool for romanization
at scale, it still has potential drawbacks. Since it is only based on lexical
substitution, its transliterations may not semantically or phonetically align
with the source content and may differ from transliterations preferred by
native speakers. Moreover, uroman is not invertible—as we have highlighted—and
may thus be less appealing when text in the original script needs to be
exactly reproduced. Our proposed method, while it is parameter-efficient and
effective—particularly for low-resource languages—still underperforms
language-specific tokenizer-based non-transliteration methods. Future work may
focus on developing an improved and more efficient tokenizer for
transliteration-based methods as we highlight in the Appendix.

## Acknowledgements

This work has been funded by the German Research Foundation (DFG) as part of
the Research Training Group KRITIS No. GRK 2222. The work of Ivan Vulić has
been supported by a personal Royal Society University Research Fellowship (no
221137; 2022-).

We thank Indraneil Paul, Yongxin Huang, Ivan Habernal, and Massimo Nicosia for
their valuable feedback and suggestions on a draft of this paper.

## References

  * Amrhein and Sennrich (2020) Chantal Amrhein and Rico Sennrich. 2020.  On Romanization for model transfer between scripts in neural machine translation.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_ , pages 2461–2469, Online. Association for Computational Linguistics.
  * Ansell et al. (2021) Alan Ansell, Edoardo Maria Ponti, Jonas Pfeiffer, Sebastian Ruder, Goran Glavaš, Ivan Vulić, and Anna Korhonen. 2021.  MAD-G: Multilingual adapter generation for efficient cross-lingual transfer.  In _Findings of the Association for Computational Linguistics: EMNLP 2021_ , pages 4762–4781, Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Artetxe et al. (2020) Mikel Artetxe, Sebastian Ruder, and Dani Yogatama. 2020.  On the cross-lingual transferability of monolingual representations.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 4623–4637, Online. Association for Computational Linguistics.
  * Chau and Smith (2021) Ethan C. Chau and Noah A. Smith. 2021.  Specializing multilingual language models: An empirical study.  In _Proceedings of the 1st Workshop on Multilingual Representation Learning_ , pages 51–61, Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Conneau et al. (2020) Alexis Conneau, Kartikay Khandelwal, Naman Goyal, Vishrav Chaudhary, Guillaume Wenzek, Francisco Guzmán, Edouard Grave, Myle Ott, Luke Zettlemoyer, and Veselin Stoyanov. 2020.  Unsupervised cross-lingual representation learning at scale.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 8440–8451, Online. Association for Computational Linguistics.
  * Daniels and Bright (1996) Peter T. Daniels and William Bright. 1996.  _The world’s writing systems_.  Oxford University Press.
  * Demirsahin et al. (2022) Isin Demirsahin, Cibu Johny, Alexander Gutkin, and Brian Roark. 2022.  Criteria for useful automatic Romanization in South Asian languages.  In _Proceedings of the Thirteenth Language Resources and Evaluation Conference_ , pages 6662–6673, Marseille, France. European Language Resources Association.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Dhamecha et al. (2021) Tejas Dhamecha, Rudra Murthy, Samarth Bharadwaj, Karthik Sankaranarayanan, and Pushpak Bhattacharyya. 2021.  Role of Language Relatedness in Multilingual Fine-tuning of Language Models: A Case Study in Indo-Aryan Languages.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 8584–8595, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Dozat and Manning (2017) Timothy Dozat and Christopher D. Manning. 2017.  Deep biaffine attention for neural dependency parsing.  In _5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings_. OpenReview.net.
  * Glavaš and Vulić (2021) Goran Glavaš and Ivan Vulić. 2021.  Is supervised syntactic parsing beneficial for language understanding tasks? an empirical investigation.  In _Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume_ , pages 3090–3104, Online. Association for Computational Linguistics.
  * Hermjakob et al. (2018) Ulf Hermjakob, Jonathan May, and Kevin Knight. 2018.  Out-of-the-box universal Romanization tool uroman.  In _Proceedings of ACL 2018, System Demonstrations_ , pages 13–18, Melbourne, Australia. Association for Computational Linguistics.
  * Houlsby et al. (2019) Neil Houlsby, Andrei Giurgiu, Stanislaw Jastrzebski, Bruna Morrone, Quentin de Laroussilhe, Andrea Gesmundo, Mona Attariyan, and Sylvain Gelly. 2019.  Parameter-efficient transfer learning for NLP.  In _Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 2790–2799. PMLR.
  * Hu et al. (2020) Junjie Hu, Sebastian Ruder, Aditya Siddhant, Graham Neubig, Orhan Firat, and Melvin Johnson. 2020.  XTREME: A massively multilingual multi-task benchmark for evaluating cross-lingual generalisation.  In _Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 4411–4421. PMLR.
  * Lin et al. (2018) Ying Lin, Cash Costello, Boliang Zhang, Di Lu, Heng Ji, James Mayfield, and Paul McNamee. 2018.  Platforms for non-speakers annotating names in any language.  In _Proceedings of ACL 2018, System Demonstrations_ , pages 1–6, Melbourne, Australia. Association for Computational Linguistics.
  * Madhani et al. (2022) Yash Madhani, Sushane Parthan, Priyanka A. Bedekar, Ruchi Khapra, Vivek Seshadri, Anoop Kunchukuttan, Pratyush Kumar, and Mitesh M. Khapra. 2022.  Aksharantar: Towards building open transliteration tools for the next billion users.  _arXiv preprint_.
  * McCloskey and Cohen (1989) Michael McCloskey and Neal J. Cohen. 1989.  Catastrophic interference in connectionist networks: The sequential learning problem.  volume 24 of _Psychology of Learning and Motivation_ , pages 109–165. Academic Press.
  * Moghe et al. (2022) Nikita Moghe, Evgeniia Razumovskaia, Liane Guillou, Ivan Vulić, Anna Korhonen, and Alexandra Birch. 2022.  Multi3nlu++: A multilingual, multi-intent, multi-domain dataset for natural language understanding in task-oriented dialogue.  _arXiv preprint_.
  * Moosa et al. (2022) Ibraheem Muhammad Moosa, Mahmud Elahi Akhter, and Ashfia Binte Habib. 2022.  Does transliteration help multilingual language modeling? _arXiv preprint_.
  * Muller et al. (2021) Benjamin Muller, Antonios Anastasopoulos, Benoît Sagot, and Djamé Seddah. 2021.  When being unseen from mBERT is just the beginning: Handling new languages with multilingual language models.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 448–462, Online. Association for Computational Linguistics.
  * Nivre et al. (2020) Joakim Nivre, Marie-Catherine de Marneffe, Filip Ginter, Jan Hajič, Christopher D. Manning, Sampo Pyysalo, Sebastian Schuster, Francis Tyers, and Daniel Zeman. 2020.  Universal Dependencies v2: An evergrowing multilingual treebank collection.  In _Proceedings of the Twelfth Language Resources and Evaluation Conference_ , pages 4034–4043, Marseille, France. European Language Resources Association.
  * Pan et al. (2017) Xiaoman Pan, Boliang Zhang, Jonathan May, Joel Nothman, Kevin Knight, and Heng Ji. 2017.  Cross-lingual name tagging and linking for 282 languages.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1946–1958, Vancouver, Canada. Association for Computational Linguistics.
  * Pfeiffer et al. (2022) Jonas Pfeiffer, Naman Goyal, Xi Lin, Xian Li, James Cross, Sebastian Riedel, and Mikel Artetxe. 2022.  Lifting the curse of multilinguality by pre-training modular transformers.  In _Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 3479–3495, Seattle, United States. Association for Computational Linguistics.
  * Pfeiffer et al. (2020a) Jonas Pfeiffer, Andreas Rücklé, Clifton Poth, Aishwarya Kamath, Ivan Vulić, Sebastian Ruder, Kyunghyun Cho, and Iryna Gurevych. 2020a.  AdapterHub: A framework for adapting transformers.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pages 46–54, Online. Association for Computational Linguistics.
  * Pfeiffer et al. (2023) Jonas Pfeiffer, Sebastian Ruder, Ivan Vulić, and Edoardo Maria Ponti. 2023.  Modular deep learning.  _arXiv preprint_.
  * Pfeiffer et al. (2020b) Jonas Pfeiffer, Ivan Vulić, Iryna Gurevych, and Sebastian Ruder. 2020b.  MAD-X: An Adapter-Based Framework for Multi-Task Cross-Lingual Transfer.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 7654–7673, Online. Association for Computational Linguistics.
  * Pfeiffer et al. (2021) Jonas Pfeiffer, Ivan Vulić, Iryna Gurevych, and Sebastian Ruder. 2021.  UNKs everywhere: Adapting multilingual language models to new scripts.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 10186–10203, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Ponti et al. (2020) Edoardo Maria Ponti, Goran Glavaš, Olga Majewska, Qianchu Liu, Ivan Vulić, and Anna Korhonen. 2020.  XCOPA: A multilingual dataset for causal commonsense reasoning.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 2362–2376, Online. Association for Computational Linguistics.
  * Rahimi et al. (2019) Afshin Rahimi, Yuan Li, and Trevor Cohn. 2019.  Massively multilingual transfer for NER.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 151–164, Florence, Italy. Association for Computational Linguistics.
  * Rust et al. (2021) Phillip Rust, Jonas Pfeiffer, Ivan Vulić, Sebastian Ruder, and Iryna Gurevych. 2021.  How good is your tokenizer? on the monolingual performance of multilingual language models.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 3118–3135, Online. Association for Computational Linguistics.
  * van Esch et al. (2022) Daan van Esch, Tamar Lucassen, Sebastian Ruder, Isaac Caswell, and Clara Rivera. 2022.  Writing system and speaker metadata for 2,800+ language varieties.  In _Proceedings of the Thirteenth Language Resources and Evaluation Conference_ , pages 5035–5046, Marseille, France. European Language Resources Association.
  * Wellisch et al. (1978) Hans H Wellisch, Lee Breuer, Richard Foreman, and Robert Wilson. 1978.  _The conversion of scripts, its nature, history, and utilization_.  New York; Toronto: Wiley.
  * Yimam et al. (2021) Seid Muhie Yimam, Abinew Ali Ayele, Gopalakrishnan Venkatesh, Ibrahim Gashaw, and Chris Biemann. 2021.  Introducing various semantic models for amharic: Experimentation and evaluation with multiple tasks and datasets.  _Future Internet_ , 13(11).
  * (34) Judit Ács.  Exploring bert’s vocabulary.  _Blog Post_.

##  Appendix A Languages in Evaluation

Languages in our evaluation, along with their ISO 639-3 language codes are
provided in Table 5.

Language Family Script Bhojpuri (bh) Indo-Europ Devanagari Buryat (bxr)
Mongolic Cyrillic Erzya (myv) Uralic Cyrilic Meadow Mari (mhr) Uralic Cyrillic
Min Dong (cdo) Sino-Tibetan Chinese Mingrelian (xmf) Kartvelian Georgian
Sindhi (sd) Indo-Europ Arabic Sorani Kurdish (ckb) Indo-Europ Arabic Uyghur
(ug) Turkic Arabic Amharic (am) Afro-Asiatic Ge’ez Divehi (dv) Indo-Europ
Thaana Khmer (km) Austroasiatic Khmer Sinhala (si) Indo-Europ Sinhala Tibetan
(bo) Sino-Tibetan Tibetan

Table 5: Languages with their ISO 639-3 codes used in our evaluation, along
with their script and language family. The dashed line separates languages
with unseen scripts, placed in the bottom part of the table.

##  Appendix B Transliterators in Evaluation

Besides uroman, we also employ various language-specific transliterators which
are publicly available. We list them in Table 6.

Transliterator |  Used for languages | Available at
---|---|---
uroman |  All | github.com/isi-nlp/uroman
amseg |  am | pypi.org/project/amseg/
transliterate |  ru, ka | pypi.org/project/transliterate/
ai4bharat-transliteration |  hi, sd | pypi.org/project/ai4bharat-transliteration/
lang-trans |  ar | pypi.org/project/lang-trans/
Table 6: Transliterators used in this work.

##  Appendix C Training of Language and Task Adapters

We train all the language adapters for $50$ epochs or $\sim 50K$ update steps
based on the corpus size. The batch size is set to 64 and the learning rate is
$1e-4$.

We train English task adapters following the setup from Pfeiffer et al.
(2020b). For NER, we directly obtain the task adapter from Adapterhub.ml which
is trained with a learning rate of $1e-4$ for $10$ epochs. For DP, we train a
Transformer-based Glavaš and Vulić (2021) biaffine attention dependency parser
Dozat and Manning (2017). We use a learning rate of $5e-4$ and train for $10$
epochs as in Pfeiffer et al. (2021).

All the reported results in both tasks (NER and DP) are reported as averages
over 6 random seeds. All the models have been trained on A100 or V100 GPUs.
None of the training methods consumed more than 36 hours.

##  Appendix D Sample Efficiency for Dependency Parsing

The experiment on sample efficiency, where the samples are sentences in the
target language, has been conducted on both evaluation tasks. The results for
NER are available in the main paper (Figure 2), while the results for DP are
available in Figure 3, and we observe similar trends in both tasks.

Figure 3: Sample efficiency in the DP task.

##  Appendix E Further Analyses

(a)

(b)

(c)

Figure 4: Tokenizer quality analysis. a) % of UNKs before and after
transliteration, b) Fertility, and c) Proportion of continued subwords for
mBERT vs monolingual tokenizer.

Following previous work Ács ; Rust et al. (2021); Moosa et al. (2022), we
further analyze tokenization quality of the mBERT tokenizer using the
following established metrics: 1) % of “UNK”s measures the % of “UNK” tokens
produced by the tokenizer, and our aim is to compare their rate before and
after transliteration; 2) fertility measures the number of subwords that are
produced per tokenized word; 3) proportion of continued subwords measures the
proportion of words for which the tokenized word is split across at least two
subwords (denoted by the symbol ##).

From the results summarized in Figure 4, it is apparent that transliteration
drastically reduces % of UNKs. However, mBERT’s tokenizer underperforms as
compared to monolingual tokenizers based on fertility and the proportion of
continued subwords Rust et al. (2021). Transliteration performs better for
some languages where the quality of the mBERT tokenizer is similar to the
monolingual tokenizer such as for dv, km, and cdo. On the other hand,
transliteration methods perform worse on languages where the quality of the
underlying mBERT tokenizer is relatively poor.

In order to test the hypothesis that the tokenizer quality might be the
principal reason for the performance gap for the transliteration-based methods
in comparison to the non-transliteration based methods, we carried out an
additional experiment. For the experiment, we adapt the Non-TransLA+EmbLex to
operate on transliterated data, and call this variant TransLA+EmbLex. Here, we
train a new tokenizer on the transliterated data and initialize lexically
overlapping embeddings with mBERT’s pretrained embeddings.

We plot the performance in Figure 5. The new method, TransLA+EmbLex now
outperforms the non-transliteration-based variant on 8/12 languages and also
on average. Consequently, this validates our hypothesis and is in line with
the previous work Moosa et al. (2022). However, we found a drop in performance
in the case of mhr (-10.71) and cdo (-10.14) when compared to TransLA +
mPLMft. These drops may be attributed to the lower degree of lexical overlap
with mBERT’s vocabulary, and consequently a higher number of randomly
initialized embeddings for those target languages.

Figure 5: Comparison of Non-TransLA+EmbLex with TransLA+EmbLex on NER (left)
and DP (right).