# CC-circuits and the expressive power of nilpotent algebras

Michael Kompatscher  Department of Computer Science, University of Oxford, UK
<EMAIL_ADDRESS>http://www.logic.at/staff/kompatscher

###### Abstract.

We show that CC-circuits of bounded depth have the same expressive power as
circuits over finite nilpotent algebras from congruence modular varieties. We
use this result to phrase a new algebraic version of Barrington, Straubing and
Thérien’s conjecture, which states that CC-circuits of bounded depth need
exponential size to compute AND.

Furthermore we investigate the complexity of deciding identities and solving
equations in a fixed nilpotent algebra. Under the assumption that the
conjecture is true, we obtain quasipolynomial algorithms for both problems. On
the other hand, if AND is computable by uniform CC-circuits of bounded depth
and polynomial size, we can construct a nilpotent algebra in which checking
identities is coNP-complete, and solving equations is NP-complete.

This work was supported by grant 18-20123S of the Czech Science Foundation,
grant UNCE/SCI/022 of the Charles University Research Centre, and INTER-
EXCELLENCE project LTAUSA19070 of the Czech Ministry of Education MŠMT

##  1\. Introduction

Proving lower bounds on the size of Boolean circuits needed to compute
explicit functions is a fundamental, but also notoriously hard problem in
theoretical computer science. A rare exception with known sharp lower bounds
is the parity function: In [FSS84] it was shown that parity cannot be computed
by bounded depth circuits of polynomial size; [Yao85] then provided
exponential lower bounds, which were further improved by Håstad [Hås86] to the
almost optimal $2^{\Omega(n^{(d-1)^{-1}})}$, where $d$ stands for the depth of
the circuits.

These results led to the question how much computational power we gain, if we
also allow gates that describe parity or other counting functions in the
construction of bounded depth circuits. More precisely, by such ‘counting
gates’ we mean $\operatorname{MOD}_{m}$-gates (for some $m\in{\mathbb{N}}$) of
unbounded fan-in that output $1$, if the inputs sum up to $0$ modulo $m$, and
$0$ otherwise.111this follows the convention used e.g. in [Vol99] or [MPT91];
we remark that other authors such as [CGPT06] actually denote the _negation_
of this function by $\operatorname{MOD}_{m}$. The class of functions that can
be expressed by polynomially growing such bounded depth circuits is denoted by
$\operatorname{AC}^{0}[m]$, and its union by
$\operatorname{ACC}^{0}=\bigcup_{m>1}\operatorname{AC}^{0}[m]$.

An important step towards a characterization of $\operatorname{ACC}^{0}$ is to
understand circuits that _only_ consist of $\operatorname{MOD}_{m}$-gates
first. Such circuits are called $\operatorname{CC}[m]$-circuits. The functions
that can be computed by bounded depth $\operatorname{CC}[m]$-circuits of
polynomial size are denoted by $\operatorname{CC}^{0}[m]$, and their union
over all $m$ by $\operatorname{CC}^{0}=\bigcup_{m>1}\operatorname{CC}^{0}[m]$.
Despite being studied extensively, many questions about
$\operatorname{CC}[m]$-circuits are still wide open. For instance their
relationship for different values of $m$ is not well-understood, although this
would be central for proving or disproving a conjecture of Smolensky [Smo87],
which says that constant depth circuits having only $\operatorname{AND}$,
$\operatorname{OR}$ and $\operatorname{MOD}_{m}$ gates cannot compute
$\operatorname{MOD}_{q}$ in sub-exponential size, when $m$ is a prime power,
and $q$ is coprime to it.

Another big open question is whether bounded depth
$\operatorname{CC}[m]$-circuits can efficiently compute $\operatorname{AND}$
or not. If it is not the case, it would signify that there is a fundamental
difference between circuits that use logical versus circuits that use counting
gates. Barrington, Straubing and Thérien first conjectured this, using a
formulation that mirrors Håstad’s result:

######  Conjecture 1 (Barrington, Straubing and Thérien [BST90]).

Let $m\in{\mathbb{N}}$ and let $(C_{n})_{n\in{\mathbb{N}}}$ be a family of
bounded depth $\operatorname{CC}[m]$-circuits that compute
$\operatorname{AND}$. Then $C_{n}$ is of size $2^{\Omega(n^{q})}$ for some
$q>0$.

Note that for non-prime $m$ one can construct $\operatorname{CC}[m]$-circuits
$(C_{n})_{n\in{\mathbb{N}}}$ of depth $d$ and size
$\mathcal{O}(2^{n^{(d-1)^{-1}}})$ that compute $\operatorname{AND}$ (see for
instance the construction in [IKK20]), thus one could further conjecture (in
analogy to Håstad’s result) that a value of $q$ close to $(d-1)^{-1}$ gives us
optimal lower bound.

Also a weaker version of Conjecture 1 can be found in the literature, e.g.
[MPT91] conjectured that $\operatorname{AND}$ is not in
$\operatorname{CC}^{0}$. Both the strong and the weak version of Conjecture 1
are open until today, with the best known lower bound for $\operatorname{AND}$
being superlinear [CGPT06]. It was shown in [HK10] that $\operatorname{AND}$
can be computed by probabilistic $\operatorname{CC}^{0}$ in polynomial time,
which could be interpreted as evidence contrary to the conjecture.

However, for some special cases Conjecture 1 is confirmed: It is well known
that $\operatorname{CC}[m]$-circuits of bounded depth _cannot_ compute
$\operatorname{AND}$ if $m$ is a prime power [BST90]. If $m$ is the product of
two primes, Conjecture 1 is confirmed for circuits of depth 2 [Cau96].

The first results about $\operatorname{CC}$-circuits arose from a
characterization of them in the language of groups/monoids: In [BST90]
Barrington, Straubing and Thérien used the notion of NUDFA (non uniform
deterministic finite automata, introduced in [Bar89]) to show that a language
is in $\operatorname{ACC}^{0}$ if and only if it is accepted by a NUDFA over a
solvable monoid, and in $\operatorname{CC}^{0}$ if and only if it is accepted
by a NUDFA over a solvable group. NUDFAs proved not only to be a fruitful tool
in circuit complexity [MPT91], but also led to new developments in algebra,
regarding the study of equations in monoids and groups [BMM+00].

In this paper we give a new algebraic description of
$\operatorname{CC}$-circuits, using concepts from universal algebra, more
specifically _commutator theory_. We show that, in some sense,
$\operatorname{CC}$-circuits of bounded depth can be represented by the
circuits over a nilpotent algebra from a congruence modular variety and vice-
versa. As a corollary we obtain the following theorem:

######  Theorem 2.

Conjecture 1 is true, if and only if in every finite nilpotent algebra
$\mathbf{A}$ from a congruence modular variety, and every $0\in A$ there is a
$q>0$, such that every sequence $(p_{n})_{n\in{\mathbb{N}}}$ of nonconstant
$0$-absorbing circuits $p_{n}(x_{1},\ldots,x_{n})$ has size at least
$2^{\Omega(n^{q})}$.

Here, for a set $A$ and an element $0\in A$ we call an operation $f\colon
A^{n}\to A$ $0$-_absorbing_ if
$0=f(0,a_{2},\ldots,a_{n})=f(a_{1},0,a_{3},\ldots,a_{n})=\cdots=f(a_{1},\ldots,a_{n-1},0)$
holds for all values $a_{1},\ldots,a_{n}\in A$. Note on the Boolean domain
$A=\\{0,1\\}$ the only $n$-ary operations that are $0$-absorbing are the
$n$-ary conjunction and the constant $0$-function. Thus nonconstant
$0$-absorbing operations can be seen as a a natural generalization of
conjunctions to arbitrary domains $A$. We remark that $0$-absorbing operations
are of independent interest in commutator theory, as they characterize
properties of the so called higher commutator [AM10].

In the course of the proof of Theorem 2 we are actually going to prove a
stronger, but more technical result in Theorem 11, which allows us to compute
explicit bounds for $\operatorname{AND}$ from bounds on nonconstant
$0$-absorbing circuits in nilpotent algebras, and vice-versa. We are further
going to discuss how known results about $\operatorname{CC}[m]$-circuits
correspond to known results about nilpotent algebras: the fact that for primes
$p$, $\operatorname{CC}[p]$-circuits of bounded depth cannot compute
$\operatorname{AND}$, corresponds for instance to the result that finite
nilpotent algebras of prime power size have only nonconstant $0$-absorbing
polynomial operations up to some arity [BB87]. The fact that Conjecture 1
holds for $\operatorname{MOD}_{p}$-$\operatorname{MOD}_{q}$ circuits [BST90]
was essentially reproven in the language of nilpotent algebras in [IKK18].

At last we discuss the impact of Conjecture 1 on two computational problems,
namely the circuit satisfaction problem
$\operatorname{\mathsf{CSAT}}(\mathbf{A})$ and the circuit equivalence problem
$\operatorname{\mathsf{CEQV}}(\mathbf{A})$ for fixed nilpotent algebras
$\mathbf{A}$. Here $\operatorname{\mathsf{CSAT}}(\mathbf{A})$ models the
decision problem, whether an equation over the algebra $\mathbf{A}$ (encoded
by two circuits) has a solution, while
$\operatorname{\mathsf{CEQV}}(\mathbf{A})$ asks, whether two circuits are
equivalent. In [IK18] Idziak and Krzaczkowski gave an almost complete
complexity classification of both problems for algebras from congruence
modular varieties, relating the complexity to the commutator theoretical
properties of the given algebra. Essentially the only case left open are
nilpotent, but not supernilpotent algebras (Problem 2 in [IK18]). We show
that, assuming of Conjecture 1, there are quasipolynomial algorithms for both
$\operatorname{\mathsf{CSAT}}$ and $\operatorname{\mathsf{CEQV}}$ of such
algebras. On the other hand we show that, if $\operatorname{AND}$ is in
_$\operatorname{\mathsf{P}}$ -uniform_ $\operatorname{CC}^{0}$, then there is
a nilpotent algebra with $\operatorname{\mathsf{NP}}$-complete circuit
satisfaction problem, and $\operatorname{\mathsf{coNP}}$-complete circuit
equivalence problem.

We remark that, since this paper first appeared as a preprint, there were some
new developments in the study of $\operatorname{\mathsf{CSAT}}$ and
$\operatorname{\mathsf{CEQV}}$ for nilpotent algebras. Under the assumption of
the Exponential Time Hypothesis (ETH), there are nilpotent algebras, for which
both problems have proper quasipolynomial lower bounds [IKK20]. Together with
the results in this paper, this implies that, under the ETH and Conjecture 1,
there are some nilpotent algebras, in which $\operatorname{\mathsf{CSAT}}$ and
$\operatorname{\mathsf{CEQV}}$ can be solved in quasipolynomial, but not
polynomial time. In particular no
$\operatorname{\mathsf{P}}$/$\operatorname{\mathsf{NP}}$-c dichotomy result
holds for $\operatorname{\mathsf{CSAT}}$. This is an interesting contrast to
the problem of solving _systems_ of equations in a given algebra $\mathbf{A}$,
since for every $\mathbf{A}$, this problem is equivalent to a finite
constraint satisfaction problem and hence either in
$\operatorname{\mathsf{P}}$ or $\operatorname{\mathsf{NP}}$-complete by the
CSP dichotomy theorem (independently proven by Zhuk [Zhu17, Zhu20] and Bulatov
[Bul17]).

The structure of this paper is as follows: In Section 2 we discuss some
necessary background from universal algebra and give a characterization of
nilpotent algebras. In Section 3 we prove Theorem 2 and discuss its
implications on $\operatorname{CC}$-circuits and nilpotent algebras. In
Section 4 we derive the complexity results for $\operatorname{\mathsf{CSAT}}$
and $\operatorname{\mathsf{CEQV}}$ of nilpotent algebras.

##  2\. Background from universal algebra

###  2.1. Polynomials and circuits over algebras

An algebra $\mathbf{A}$ is a pair $(A,(f_{i}^{\mathbf{A}})_{i\in I})$, where
$A$ is a set (the _universe_ of $\mathbf{A}$), and every element of the family
$(f_{i}^{\mathbf{A}})_{i\in I}$ is a finitary operation
$f_{i}^{\mathbf{A}}\colon A^{k_{i}}\to A$ (the _basic operations_ of
$\mathbf{A}$). The _signature_ of $\mathbf{A}$ is the family $(k_{i})_{i\in
I}$, i.e. it describes which basic operations are of which arity. In this
paper we are only going to consider _finite algebras_ , so algebras that have
a finite universe and only finitely many basic operations. By
$\operatorname{ar}(\mathbf{A})$ we denote the maximal arity of the basic
operations of $\mathbf{A}$.

A _term operation_ of $\mathbf{A}$ is an operation that can be obtained as a
composition of basic operations of $\mathbf{A}$. A _polynomial operation_
allows also the use of elements of $A$ in its construction. For the ring of
integers $({\mathbb{Z}},+,\cdot)$ for instance, the polynomial operations are
just the polynomial operations in the conventional sense (e.g. the operation
$p\colon{\mathbb{Z}}^{3}\to{\mathbb{Z}}$ defined by
$p(x_{1},x_{2},x_{3})=(2x_{1}\cdot x_{3}+4)\cdot x_{1}\cdot x_{2}+1$). The set
of all polynomial operations of $\mathbf{A}$ is denoted by
$\operatorname{Pol}(\mathbf{A})$. Let $\mathbf{A}$ and $\mathbf{B}$ be two
algebras with the same universe; if
$\operatorname{Pol}(\mathbf{A})=\operatorname{Pol}(\mathbf{B})$ we say that
$\mathbf{A}$ and $\mathbf{B}$ are _polynomially equivalent_ , if
$\operatorname{Pol}(\mathbf{A})\subseteq\operatorname{Pol}(\mathbf{B})$, we
say $\mathbf{B}$ is a _polynomial extension_ of $\mathbf{A}$.

Given a finite algebra, there are different ways of encoding its polynomial
operations. The naive way is to just encode them by the string defining them.
Such a string is usually referred to as a _polynomial_ over $\mathbf{A}$.
However, in an effort to compress the input, one can also consider _circuits_
over $\mathbf{A}$, i.e. $A$-valued circuits with a unique output gate, whose
gates are labelled by the basic operation of $\mathbf{A}$. We say that two
circuits (respectively two polynomials) are _equivalent_ , if they define the
same operation.

By the following folklore result, the circuit approach does not only allow for
a more concise, but also more stable representation of polynomial operations:

######  Lemma 3.

Let $\mathbf{A}$ and $\mathbf{B}$ be two finite algebras with the same
universe and
$\operatorname{Pol}(\mathbf{A})\subseteq\operatorname{Pol}(\mathbf{B})$. Then
we can rewrite every circuit $C(\bar{x})$ over $\mathbf{A}$ to an equivalent
circuit $C^{\prime}(\bar{x})$ over $\mathbf{B}$ in linear time.

The circuit $C^{\prime}$ in Lemma 3 can be easily obtained, by substituting
every gate in $C$ by a circuit over $\mathbf{B}$ defining the corresponding
basic operation of $\mathbf{A}$. Note that it follows from Lemma 3 that the
size of $C^{\prime}$ is linear in the size of $C$. An analogue statement is
however not true for the encoding by polynomials; in fact, the results in
[HS12] imply that under the assumption
$\operatorname{\mathsf{P}}\neq\operatorname{\mathsf{NP}}$ it even fails for
quite well-behaved algebras such as the alternating group $A_{4}$. In this
paper we are therefore only going to discuss the circuit encoding of
polynomial operations (explaining the names CSAT and CEQV for our
computational problems).

For a circuit $C$ over $\mathbf{A}$ with input gates
$\bar{x}=(x_{1},\ldots,x_{n})$ we will write $C(\bar{x})$ both for the
circuit, and the $n$-ary polynomial operation induced by it, but this should
never cause any confusion. We call a circuit $C$ constant/$0$-absorbing/etc.,
if the polynomial operation $C(\bar{x})$ defined by it is
constant/$0$-absorbing/etc.

###  2.2. Nilpotent algebras from congruence modular varieties

Commutator theory is a field of universal algebra that generalizes concepts
from the commutator theory of groups to arbitrary algebras. In particular
there is the notion of a central series of congruences, which allows to define
nilpotent algebras (as a generalization of nilpotent groups and nilpotent
rings). Since we are only interested in nilpotent algebras from congruence
modular varieties, we refrain from giving the original definition (via the so
called _term congruence commutator_) and refer to [FM87] for background.

Algebras from _congruence modular varieties_ form a quite broad class that
contains many examples of interest in classical algebra and computer science,
such as: lattices, Boolean algebras, fields, rings, modules, groups,
quasigroups, and all their polynomial extensions. Commutator theory works
especially well in the congruence modular case.

In a congruence modular varieties, an algebra is _Abelian_ (or _1-nilpotent_)
if and only if it is polynomially equivalent to a _module_. Here, a module
$\mathbf{A}$ is an algebra $\mathbf{A}=(A,+,0,-,(r)_{r\in R})$, where
$(A,+,0,-)$ is the underlying Abelian group and every ring element $r\in R$ is
considered as a unary operation $r(x)=r\cdot x$. Therefore all operations of
such an Abelian algebra $\mathbf{A}$ are affine operations
$p(x_{1},\ldots,x_{n})=\sum_{i=1}^{n}r_{i}x_{i}+c$ for some scalars $r_{i}\in
R$ and a constant $c\in A$.

General nilpotent algebras from congruence modular varieties can, in some
sense, be decomposed into Abelian algebras (this follows from Proposition 7.1.
in [FM87]). We are going to treat this characterization as a definition of
nilpotence:

######  Definition 4.

An algebra $\mathbf{A}=(A,(f^{\mathbf{A}})_{f\in I})$ from a congruence
modular variety is

  * •

_1-nilpotent_ (or _Abelian_) if and only if it is polynomially equivalent to a
module;

  * •

_$n$ -nilpotent_, if there are algebras $\mathbf{L}=(L,(f^{\mathbf{L}})_{f\in
I})$ and $\mathbf{U}=(U,(f^{\mathbf{U}})_{f\in I})$ in the same signature as
$\mathbf{A}$ such that

    * –

$\mathbf{L}$ is Abelian and $\mathbf{U}$ is $(n-1)$-nilpotent,

    * –

$A=L\times U$, where $L$ and $U$ are the universes of $\mathbf{L}$ and
$\mathbf{U}$ respectively,

    * –

Every basic operation $f^{\mathbf{A}}$ of $\mathbf{A}$ is of the form

$f^{\mathbf{A}}((l_{1},u_{1}),\ldots,(l_{k},u_{k}))=(f^{\mathbf{L}}(l_{1},\ldots,l_{k})+\hat{f}(u_{1},\ldots,u_{k}),f^{\mathbf{U}}(u_{1},\ldots,u_{k})),$

for a function $\hat{f}\colon U^{k}\to L$.

Here $+$ denotes the addition of the module that is polynomially equivalent to
$\mathbf{L}$. We write $\mathbf{A}=\mathbf{L}\otimes\mathbf{U}$ for the
decomposition of $\mathbf{A}$ into $\mathbf{L}$ and $\mathbf{U}$.

When talking about nilpotent algebras in this paper, we will from now on
always implicitly assume that they are from a congruence modular variety.

Note that by Definition 4, $n$-nilpotent algebras can be regarded as an
$(n-1)$-nilpotent algebra $\mathbf{U}$ ‘acting’ on the Abelian algebra
$\mathbf{L}$ by the operations $\hat{f}\colon U^{k}\to L$. The _degree of
nilpotency_ of $\mathbf{A}$ is the smallest $n$, such that $\mathbf{A}$ is
$n$-nilpotent. Note that this degree is always bounded by
$\lfloor\log_{2}|A|\rfloor$.

By a recent result of Aichinger every nilpotent algebra has a nicely behaved
extension by some Abelian group operations:

######  Theorem 5 (Corollary of Theorem 4.2. in [Aic19a]).

Let $\mathbf{A}$ be a finite nilpotent algebra from a congruence modular
variety and let $0\in A$. Then there exists a nilpotent algebra $\mathbf{B}$
with the same universe $A$, such that

  * •

$\operatorname{Pol}(\mathbf{A})\subseteq\operatorname{Pol}(\mathbf{B})$,

  * •

$\mathbf{B}=\mathbf{L}_{1}\otimes(\mathbf{L}_{2}\otimes(\cdots\otimes\mathbf{L}_{n}))$,
such that

    * –

every $\mathbf{L}_{i}$ is polynomially equivalent to a module
with group $(L_{i},+,0,-)={\mathbb{Z}}_{q_{i}}^{k_{i}}$, where $q_{i}$ is
prime and a ring $R\leq\operatorname{End}({\mathbb{Z}}_{q_{i}}^{k_{i}})$

    * –

$\mathbf{B}$ contains basic operations $+$, $0$, $-$ such that
$(A,+,0,-)=\prod_{i=1}^{n}(L_{i},+,0,-)$.

We remark that Theorem 4.2. in [Aic19a] is phrased in a different way from our
statement: it states that to every central series of congruences
$0_{A}=\alpha_{0}<\alpha_{1}<\ldots<\alpha_{n}=1_{A}$ of $\mathbf{A}$ and
constant $0\in A$, we can associate an Abelian group $(A,+,0,-)$, such that
$(\alpha_{i})_{i=0}^{n}$ is still a central series of $\mathbf{B}$, the
extension of $\mathbf{A}$ by $+,0,-$. By applying Proposition 7.1. from [FM87]
iteratively to $\mathbf{B}$, we then obtain the algebras $\mathbf{L}_{i}$ such
that
$\mathbf{B}=\mathbf{L}_{1}\otimes(\mathbf{B}/\alpha_{1})=\mathbf{L}_{1}\otimes(\mathbf{L}_{2}\otimes(\mathbf{B}/\alpha_{2}))=\cdots=\mathbf{L}_{1}\otimes(\mathbf{L}_{2}\otimes(\cdots\otimes\mathbf{L}_{n}))$
such that $(A,+,0,-)=\prod_{i=1}^{n}(L_{i},+,0,-)$. If we pick the central
series to be of maximal length, it holds that
$(L_{i},+,0,-)={\mathbb{Z}}_{q_{i}}^{k_{i}}$ for some prime $q_{i}$ by Lemma
4.1. in [Aic19a].

By Lemma 3 every circuit over $\mathbf{A}$ can be rewritten in linear time to
a circuit over its polynomial extension $\mathbf{B}$ given by Theorem 5;
working in the extension $\mathbf{B}$ instead of $\mathbf{A}$ will simplify
our proof. In particular, we are going to use that every element $x\in A$ can
be identified with a tuple in
$(A,+,0,-)=\prod_{i=1}^{n}(L_{i},+,0,-)=\prod_{j=1}^{s}{\mathbb{Z}}_{p_{j}}$
such that $|A|=\prod_{j=1}^{s}{p_{j}}$ is the prime decomposition of $|A|$
(possibly containing repetitions).

We want to stress, that here only the group $(A,+,0,-)$ can be decomposed into
a direct product of prime sized algebras, but not the entire algebra
$\mathbf{B}$. Moreover, the Abelian algebras $\mathbf{L}_{i}$ can in general
not be further decomposed with respect to $\otimes$; an example is the Abelian
algebra $({\mathbb{Z}}_{2}\times{\mathbb{Z}}_{2},+,0,-,r)$, where $r$ is the
unary function $r((a,b))=(b,a)$.

##  3\. The equivalence of CC-circuits and circuits over nilpotent algebras

Our proof of Theorem 2 is based on expressing circuits over a fixed nilpotent
algebra $\mathbf{A}$ as $\operatorname{CC}[m]$-circuits, and vice-versa. It is
however a priori not clear if and how this is possible, as
$\operatorname{CC}[m]$-circuits are Boolean valued, whereas the universe of
$\mathbf{A}$ can be arbitrary. Because of this, most of the time we are not
going to work with $\operatorname{CC}[m]$-circuits themselves, but an
$m$-valued analogue, which we call $\operatorname{CC}^{+}[m]$-circuits. We
define $\operatorname{CC}^{+}[m]$-circuits and discuss some of their
properties in the next subsection. This is then followed by the proof and
discussion of Theorem 11, which in particular implies Theorem 2.

###  3.1. $\operatorname{CC}^{+}[m]$-circuits

######  Definition 6.

A _$\operatorname{CC}^{+}[m]$ -circuit_ $C$ over the set
${\mathbb{Z}}_{m}=\\{0,1,\ldots,m-1\\}$ containing $+$-gates, constant gates,
and $\operatorname{MOD}_{m}$-gates of arbitrary fan in. We interpret $+$ as
addition modulo $m$. As in the Boolean case, $\operatorname{MOD}_{m}$-gates
output $1$, if their inputs sum up to $0$ modulo $m$, and $1$ otherwise.

Without loss of generality we can assume that in such a
$\operatorname{CC}^{+}[m]$-circuit $C$ there are at most $m$ wires between two
gates (otherwise we take their number modulo $m$). Furthermore, every wire
from a $+$-gate to some $\operatorname{MOD}_{m}$-gate can be substituted by
wires that go directly from the inputs of the $+$-gate to the
$\operatorname{MOD}_{m}$-gate. By doing this substitution for all such wires
(and reducing their number in each step modulo $m$) we obtain an equivalent
circuit, whose size is linear in the size of the original. Thus, from now on,
we assume that every $\operatorname{CC}^{+}[m]$-circuit has at most one
$+$-gate, and this is the output gate.

We next discuss the relationship between nonconstant $0$-absorbing
$\operatorname{CC}^{+}[m]$\- and $\operatorname{CC}[m]$-circuits. Note that an
$n$-ary $\operatorname{CC}[m]$-circuits $C$ is nonconstant and $0$-absorbing
if and only if $C(\bar{x})=1$ if $\bar{x}=(1,1,\ldots,1)$ and $C(\bar{x})=0$
else. So it defines the $n$-ary $\operatorname{AND}$ operation.

######  Lemma 7.

  1. (1)

For every nonconstant $0$-absorbing $\operatorname{CC}^{+}[m]$-circuit
$C(\bar{x})$ of depth $d$ we can compute in linear time a
$\operatorname{CC}[m]$-circuit $C^{\prime}(\bar{x})$ of depth $d$ that defines
$\operatorname{AND}$.

  2. (2)

For every $\operatorname{CC}[m]$-circuit $C(\bar{x})$ of depth $d$ defining
$\operatorname{AND}$ we can compute in linear time a nonconstant $0$-absorbing
$\operatorname{CC}^{+}[m]$-circuit $C^{\prime}(\bar{x})$ of depth $d+1$.

###### Proof.

For (1), let $C(x_{1},\ldots,x_{n})$ be a circuit of depth $d$ that defines a
nonconstant $0$-absorbing function. Thus there is some tuple
$\bar{a}\in({\mathbb{Z}}_{m}\setminus\\{0\\})^{n}$ such that $C(\bar{a})\neq
0$. Without loss of generality we can assume that $\bar{a}=(1,1,\ldots,1)$,
otherwise we duplicate every wire connected to the input gate $x_{i}$
$a_{i}$-many times. Without loss of generality we can further assume that $C$
has only constant gates labelled by $1$ (otherwise we substitute the constant
gate $c$ by $c$-many copies of $1$). If $C$ contains no $+$-gate at all, we
set $C=C^{\prime}$ and are done. If $C$ has a $+$-gate as an output gate that
sums up $g_{1},\ldots,g_{k}$ we construct $C^{\prime}$ by substituting this
$+$-gate by a $\operatorname{MOD}_{m}$-gate that has $g_{1},\ldots,g_{k}$ and
$m-C(\bar{a})$ as input.

For (2) note that $C$ itself might not be $0$-absorbing when evaluated over
${\mathbb{Z}}_{m}$. However the circuit
$C^{\prime}(\bar{x})=C(\operatorname{MOD}_{m}(1-x_{1}),\ldots,\operatorname{MOD}_{m}(1-x_{n}))$
is. ∎

As a consequence of Lemma 7 (1), lower bounds on the size of
$\operatorname{CC}[m]$-circuit of depth $d$ defining $\operatorname{AND}$ are
also lower bounds on the size of nonconstant $0$-absorbing
$\operatorname{CC}^{+}[m]$-circuit of depth $d$. By Lemma 7 (2) also the
reverse statement holds, up to decreasing the depth by 1.

We continue by discussing representations of arbitrary functions by
$\operatorname{CC}^{+}[m]$-circuits. A useful concept for it is the _essential
depth_ of a $\operatorname{CC}^{+}[m]$-circuit $C$, which we define to be the
depth of $C$, not counting its $+$-gates.

######  Lemma 8.

  1. (1)

If $m>2$, then every function $f\colon{\mathbb{Z}}_{m}^{n}\to{\mathbb{Z}}_{m}$
can be represented by a $\operatorname{CC}^{+}[m]$-circuit of essential depth
$\lceil\log_{2}(n)\rceil+1$.

  2. (2)

If $m$ has two distinct prime factors, then every function
$f\colon{\mathbb{Z}}_{m}^{n}\to{\mathbb{Z}}_{m}$ can be represented by a
$\operatorname{CC}^{+}[m]$-circuit of essential depth $3$.

###### Proof.

In order to prove (1), we define the series
$C_{1}(x_{1})=\operatorname{MOD}_{m}(x_{1})$, and
$C_{2^{k+1}}(x_{1},\ldots,x_{2^{k+1}})=\operatorname{MOD}_{m}(C_{2^{k}}(x_{1},\ldots,x_{2^{k}}),C_{2^{k}}(x_{2^{k}+1},\ldots,x_{2^{k+1}}),m-2)$,
for every $k\in{\mathbb{N}}$. Note that $C_{2^{k+1}}$ outputs $1$ if all
inputs are equal to $0$ and $0$ otherwise. We can further such circuits
$C_{n}$ for all other arities $2^{k}<n\leq 2^{k+1}$ by identifying some of the
variables of $C_{2^{k+1}}$. Now (1) follows from the fact that every function
$f\colon{\mathbb{Z}}_{m}^{n}\to{\mathbb{Z}}_{m}$ can be obtained as the sum of
translations of $C_{n}$ by constant tuples, i.e. $f(\bar{x})=\sum_{\bar{a}\in
A^{n}}f(\bar{a})\cdot C_{n}(\bar{x}-\bar{a})$ (where $f(\bar{a})\cdot y$ is a
shorthand for the sum of $f(\bar{a})$-many copies of $y$).

For (2) recall that all Boolean operations, in particular the $n$-ary
$\operatorname{AND}$, can be written as $\operatorname{CC}[m]$-circuits of
depth 2 (see [BST90]). Thus
$C_{n}(\bar{x})=\operatorname{AND}(\operatorname{MOD}_{m}(x_{1}),\ldots,\operatorname{MOD}_{m}(x_{n}))$
is a $\operatorname{CC}^{+}[m]$-circuit of depth $3$ that describes the
characteristic function of $(0,\ldots,0)$. As in the proof of (1), we can
obtain all other functions as linear combinations $f(\bar{x})=\sum_{\bar{a}\in
A^{n}}f(\bar{a})\cdot C_{n}(\bar{x}-\bar{a})$. ∎

###  3.2. The main result

Recall that in Definition 4 we considered the operations of $n$-nilpotent
algebras as ‘actions’ of an $(n-1)$-nilpotent algebra on an Abelian one. Also
in a $\operatorname{CC}^{+}[m]$-circuit we can think of a
$\operatorname{MOD}_{m}$-gates as receiving inputs from gates of lower depth
and having an output in the Abelian group ${\mathbb{Z}}_{m}$. This viewpoint
allows us to construct a nilpotent algebra in which we can interpret all
$\operatorname{CC}^{+}[m]$-circuits of fixed depth $d$:

######  Lemma 9.

For all $m,d\in{\mathbb{N}}$ there is a $(d+1)$-nilpotent algebra
$\mathbf{D}=({\mathbb{Z}}_{m}^{d+1},+,0,-,h,*,(f_{i})_{i=1}^{d})$, such that
for every $\operatorname{CC}^{+}[m]$-circuit $C$ of essential depth $d$, there
is a circuit $C^{\prime}$ over $\mathbf{D}$ with
$C^{\prime}(x_{1},\ldots,x_{n})=(C(\pi_{d+1}(x_{1}),\ldots,\pi_{d+1}(x_{n})),0,\ldots,0)$
(where $\pi_{i}$ denotes the projection of $D$ to the $i$-th component of
$({\mathbb{Z}}_{m})^{d+1}$). Further $C^{\prime}$ can be computed from $C$ in
linear time.

###### Proof.

As usual, $+,0,-$ denote the Abelian group operation on
${\mathbb{Z}}_{m}^{d+1}$. Further we define the unary operation
$h(x)=(0,\ldots,0,\pi_{d+1}(x))$, the binary operation
$x_{1}*x_{2}=(\sum_{i=1}^{d+1}\pi_{i}(x_{1})+\pi_{i}(x_{2}),0,\ldots,0)$, and
the unary operations $(f_{i})_{i=1}^{d}$ by

$f_{i}(x)=\begin{cases}(0,\ldots,0,1,0,\ldots,0)\text{ if
}\pi_{i+1}(x)+\pi_{i+2}(x)+\cdots+\pi_{d+1}(x)=0,\\\ (0,0,\ldots,0)\text{
else;}\end{cases}$

here $1$ lies on the $i$-th coordinate. Note that
$\mathbf{D}=\mathbf{L}_{1}\otimes(\mathbf{L}_{2}\otimes\cdots(\mathbf{L}_{d}\otimes\mathbf{L}_{d+1})\cdots)$,
such that every $\mathbf{L}_{i}$ is polynomially equivalent to
${\mathbb{Z}}_{m}$. Since $\mathbf{D}$ contains Abelian group operations, it
is from a congruence modular variety. Thus, by Definition 4, $\mathbf{D}$ is
$d+1$-nilpotent. Let $C(y_{1},\ldots,y_{n})$ now be a
$\operatorname{CC}^{+}[m]$-circuit of essential depth $d$. Without loss of
generality we can assume that $C(y_{1},\ldots,y_{n})$ has at most one $+$-gate
at its output level.

By the depth $r$ of a gate $g$ of $C$ we denote the distance of $g$ from one
of the input or constant gates. Further let $C_{g}$ be the subcircuit of $C$,
consisting of all vertices that have a directed path to $g$. We are going to
show by induction over the depth $r=0,1,\ldots,d$ that for every gate $g$ of
depth $r$ there is a circuit $C_{g}^{\prime}$ over $\mathbf{A}$, such that
$\pi_{d+1-r}C_{g}^{\prime}(x_{1},\ldots,x_{n})=C_{g}(\pi_{d+1}(x_{1}),\ldots,\pi_{d+1}(x_{n}))$
and $\pi_{j}C_{g}^{\prime}(x_{1},\ldots,x_{n})=0$, for all $j\neq d+1-r$. Note
that for $r=d$, this is essentially the statement of the lemma.

The gates $g$ of depth $r=0$ are either input gates or constant gates. For
every constant gate $C_{g}=c$ of $C$ we set $C_{g}^{\prime}=(0,0,\ldots,c)$
and every input gate $C_{g}=y_{i}$ of $C$ we set $C_{g}^{\prime}=h(x_{i})$.
Clearly $C_{g}^{\prime}$ then satisfies the our claim.

For an induction step $r-1\to r$, let $g$ be a gate of depth $r$. Note that
$g$ must be a $\operatorname{MOD}_{m}$-gate, and thus
$C_{g}=\operatorname{MOD}_{m}(C_{g_{1}}+C_{g_{2}}+\ldots+C_{g_{n}})$, where
all $g_{i}$ are gates of depth $r-1$ or lower. By induction assumption, for
every $g_{i}$ there exists a circuit $C_{g_{i}}^{\prime}$ over $\mathbf{A}$
satisfying the induction hypothesis. We then define
$C_{g}^{\prime}=f_{d+1-r}(C_{g_{1}^{\prime}}+C_{g_{2}^{\prime}}+\ldots+C_{g_{n}^{\prime}})$.
By the definition of the function $f_{d+1-r}$, this circuit satisfies
$\pi_{d+1-r}C_{g}^{\prime}(x_{1},\ldots,x_{n})=C_{g}(\pi_{d+1}(x_{1}),\ldots,\pi_{d+1}(x_{n})$
and $\pi_{j}C_{g}^{\prime}=0$ for all $j\neq d+1-r$, which is what we wanted
to prove.

If $C$ has a $\operatorname{MOD}_{m}$-gate $g$ of depth $d$ as output gate,
then we simply set $C^{\prime}=C_{g}^{\prime}$ and are done. In the other case
$C^{\prime}$ has a $+$-gate (of depth $d+1$) as output gate. Hence
$C=C_{g_{1}}+C_{g_{2}}+\ldots+C_{g_{n}}$, for gates $g_{1},\ldots,g_{n}$ of
depth at most $d$. We then define
$C^{\prime}=C_{g_{1}}^{\prime}*C_{g_{2}}^{\prime}*\ldots*C_{g_{n}}^{\prime}$.
By the definition of $*$, this $C^{\prime}$ also satisfies the statement of
the Lemma. ∎

The other direction, i.e. showing that circuits over a fixed nilpotent algebra
$\mathbf{A}$ can be expressed by bounded depth $\operatorname{CC}^{+}[m]$
circuits requires some more work.

Recall that by Theorem 5 every nilpotent algebra $\mathbf{A}$ can be extended
by group operations $+,0,-$ such that $(A,+,0,-)$ is the direct product of
prime order groups $\prod_{i=1}^{s}{\mathbb{Z}}_{p_{i}}$, with
$|A|=\prod_{j=1}^{s}p_{j}$. So we can identify an element $a\in A$ with the
tuple $(\pi_{1}(a)\ldots,\pi_{s}(a))\in\prod_{j=1}^{s}{\mathbb{Z}}_{p_{j}}$.
Let $m$ be the product of all _distinct_ prime factors of $|A|$. Every factor
${\mathbb{Z}}_{p_{j}}$ clearly embeds into ${\mathbb{Z}}_{m}$ (by the map
$x\mapsto(mp_{j}^{-1})x$). Therefore there is also a natural embedding
$e\colon(A,+,0,-)=\prod_{j=1}^{s}{\mathbb{Z}}_{p_{j}}\to({\mathbb{Z}}_{m})^{s}$.

Our goal is to interpret circuits over the algebra $\mathbf{A}$ as
$\operatorname{CC}^{+}[m]$-circuits using this embedding. So for a circuit $C$
over $\mathbf{A}$, we want to find a $\operatorname{CC}^{+}[m]$-circuit
$C^{\prime}$ such that
$C^{\prime}(e(x_{1}),\ldots,e(x_{k}))=eC(x_{1},\ldots,x_{k})$. Note that for
every input gate $x_{i}$ of $C$, the $\operatorname{CC}^{+}[m]$-circuit
$C^{\prime}$ needs to have $s$ input gates for
$e(x_{i})=(\pi_{1}(x_{i})\ldots,\pi_{s}(x_{i}))$. For the same reason
$C^{\prime}$ will also have $s$ output gates.

######  Proposition 10.

Let $\mathbf{A}$ be a finite nilpotent algebra, and $\mathbf{B}$ be its
extension by the Abelian group operations $+,0,-$, given by Theorem 5.
Let $m>2$ be the product of prime divisors of $|A|$, and
$e\colon(A,+,0,-)\to({\mathbb{Z}}_{m})^{s}$ the natural group embedding. Then
there is a $d\in{\mathbb{N}}$ such that for every circuit $C$ over
$\mathbf{B}$ there is a $\operatorname{CC}^{+}[m]$-circuit $C^{\prime}$ of
essential depth $d$ with
$C^{\prime}(e(x_{1}),\ldots,e(x_{k}))=eC(x_{1},\ldots,x_{k})$.

  1. (1)

In general
$d\leq(\lceil\log_{2}(s\cdot\operatorname{ar}(\mathbf{B}))\rceil+1)\cdot(\log_{2}|A|-1)$,

  2. (2)

If $m$ is not a prime, then $d\leq 3(\log_{2}|A|-1)$.

Furthermore $C^{\prime}$ can be computed from $C$ in linear time.

###### Proof.

Recall that, by Theorem 5,

$\mathbf{B}=\mathbf{L}_{1}\otimes(\mathbf{L}_{2}\otimes\cdots(\mathbf{L}_{n-1}\otimes\mathbf{L}_{n})\cdots),$

such that every $\mathbf{L}_{i}$ is polynomially equivalent to a module, whose
group is ${\mathbb{Z}}_{p_{i}}^{k_{i}}$ for a prime $p_{i}$. With respect to
this representation, every basic operation of $\mathbf{B}$ is of the form

$f=(f^{\mathbf{L}_{1}}+\hat{f}_{1},f^{\mathbf{L}_{2}}+\hat{f}_{2},\ldots,f^{\mathbf{L}_{n-1}}+\hat{f}_{n-1},f^{\mathbf{L}_{n}}),$

where $f^{\mathbf{L}_{i}}$ is an operation of $\mathbf{L}_{i}$ and
$\hat{f}_{i}$ only depends on the projection of $A$ to
$L_{i+1}\times\cdots\times L_{n}$. Without loss of generality we can assume
that each basic operation of $\mathbf{B}$ is either ‘of affine type’, meaning
that
$f=(f^{\mathbf{L}_{1}},f^{\mathbf{L}_{2}},\ldots,f^{\mathbf{L}_{n-1}},f^{\mathbf{L}_{n}})$,
or of ‘hat type’ meaning that $f=(0,\ldots,0,\hat{f}_{j},0,\ldots,0)$. If this
is not the case we substitute $f$ by the basic operations
$(f^{\mathbf{L}_{1}},\ldots,f^{\mathbf{L}_{n}})$ and
$(0,\ldots,0,\hat{f}_{j},0,\ldots,0)$ for every $j=1,\ldots,n-1$. The
resulting algebra is also $n$-nilpotent and a polynomial extension of
$\mathbf{B}$. Note further that this extension has the same maximal arity as
$\mathbf{B}$.

Every basic affine operation $f^{\mathbf{L}_{i}}\colon L_{i}^{l}\to L_{i}$ of
$L_{i}$ is equal to an affine combination
$f^{\mathbf{L}_{i}}(z_{1},\ldots,z_{l})=\sum_{j=1}^{l}r_{i}\cdot z_{i}+c$,
where the $r_{i}$ are linear maps. Therefore we can consider
$f^{\mathbf{L}_{i}}$ as an affine map from the vector space
${\mathbb{Z}}_{p_{i}}^{l\cdot k_{i}}$ to ${\mathbb{Z}}_{p_{i}}^{k_{i}}$. As
such, it can be represented by a circuit over ${\mathbb{Z}}_{p_{i}}$ with
$lk_{i}$ inputs and $k_{i}$ outputs, consisting only of $+$-gates. By
duplicating every wire in this circuit $mp^{-1}$-many times, we obtain a
corresponding $+$-circuit over ${\mathbb{Z}}_{m}$. By doing this for every
projections $f^{\mathbf{L}_{i}}$ of a basic operation
$f=(f^{\mathbf{L}_{1}},\ldots,f^{\mathbf{L}_{n}})$ of ‘affine type’, we can
show that there is a $\operatorname{CC}^{+}[m]$ circuits $C_{f}$ only
consisting of $+$-gates, such that
$C_{f}(e(x_{1}),\ldots,e(x_{l}))=ef(x_{1},\ldots,x_{l})$.

Next, for every operation of ‘hat type’ $f\colon A^{l}\to A$, we take an
arbitrary extension of it to a function
$g\colon({\mathbb{Z}}_{m}^{s})^{l}\to{\mathbb{Z}}_{m}^{s}$. Since
$l\leq\operatorname{ar}(\mathbf{B})$, by Lemma 8 (1), this $g$ can be
represented by a $\operatorname{CC}^{+}[m]$-circuit $C_{f}$ of essential depth
$\lceil\log_{2}(s\cdot\operatorname{ar}(\mathbf{B}))\rceil+1$. If $m$ is the
product of two or more prime factors, then by Lemma 8 (2), $C_{f}$ can even be
written as a $\operatorname{CC}^{+}[m]$-circuits of essential depth $3$.

Now let $C$ be an arbitrary circuit of the algebra $\mathbf{B}$. For every
basic operation of hat-type $f$, there is a $j\in\\{1,\ldots,n-1\\}$ such that
$\hat{f}_{j}$ only depends on $L_{j+1}\times\cdots\times L_{n}$, and all other
coordinates are $0$. For any other operation $g$ that is of of hat-type with
respect to a smaller index $p\leq j$ the identity $f(x_{1},\ldots,x_{k}+c\cdot
g(\bar{y}),\ldots,x_{l})=f(x_{1},\ldots,x_{k},\ldots,x_{l})$ holds, for all
$k=1,\ldots,l$. Using these identities, the circuit $C$ can be rewritten in
linear time to a circuit, in which no directed path contains more than $n-1$
gates of hat type.

If we then substitute all gates $f$ of $C$ by the corresponding
$\operatorname{CC}^{+}[m]$-circuits $C_{f}$ as described above, we obtain a
$\operatorname{CC}^{+}[m]$-circuit $C^{\prime}$ of essential depth
$(\lceil\log_{2}(s\cdot\operatorname{ar}(\mathbf{B}))\rceil+1)(n-1)$. In the
case, in which $m$ has two or more prime factors, the same argument gives us a
circuit of essential depth $3(n-1)$.

Since $n\leq\log_{2}|A|$, this proves the proposition. ∎

Note that the $sk$-ary $\operatorname{CC}^{+}[m]$-circuit
$C^{\prime}(y_{1},\ldots,y_{sk})$ in Proposition 10 does not need to be
$0$-absorbing, if $C$ is $0$-absorbing. However we can obtain a $0$-absorbing
circuit with the same range as $eC$ by taking the circuit
$C^{\prime\prime}(y_{1},\ldots,y_{sk})$ that computes
$C^{\prime}(c_{1}y_{1},c_{2}y_{2},\ldots,c_{s}y_{sk})$, with
$c_{i}=mp_{i}^{-1}$.

We are now ready to prove the main result.

######  Theorem 11.

For a fixed nilpotent algebra $\mathbf{A}$ and $0\in A$, let
$f_{\mathbf{A}}(n)$ denote the minimal size of a nonconstant $0$-absorbing
$n$-ary circuit over $\mathbf{A}$. For two integers $d,m$, let $g_{m,d}(n)$ be
the smallest size of an $n$-ary $\operatorname{CC}[m]$-circuit of depth $d$
computing $\operatorname{AND}$. Then:

  1. (1)

Let $\mathbf{A}$ be a finite nilpotent algebra, and $m$ be the product of
prime divisors of $|A|$. If $m$ is not a prime, then $f_{\mathbf{A}}(n)\geq
Kg_{m,d}(n)$ for $d=3\lfloor\log_{2}|A|\rfloor-2$ and some $K>0$.

  2. (2)

Vice versa, for every $d>1$ and every product of two or more distinct primes
$m$, there is a $(d+2)$-nilpotent algebra $\mathbf{B}$ with $g_{m,d}(n)\geq
K^{\prime}f_{\mathbf{B}}(n)$ for some $K^{\prime}>0$.

###### Proof.

To see (1), let $(C_{n})_{n\in{\mathbb{N}}}$ be a sequence of nonconstant
$0$-absorbing circuits over $\mathbf{A}$ such that
$|C_{n}|=f_{\mathbf{A}}(n)$. We can regard every $C_{n}$ also as a circuit
over the nilpotent extension $\mathbf{B}$ of $\mathbf{A}$ given by Theorem 5.
This extension $\mathbf{B}$ is nilpotent and contains a group operation $+$
such that $(A,+,0,-)=\prod_{j=1}^{s}{\mathbb{Z}}_{p_{j}}$. By Proposition 10,
for every $n$ there is a $sn$-ary $\operatorname{CC}^{+}[m]$-circuit
$C_{n}^{\prime}$ of essential depth at most $3\lfloor\log_{2}|A|\rfloor-3$
such that
$C_{n}^{\prime}(e(x_{1}),\ldots,e(x_{n}))=eC_{n}(x_{1},\ldots,x_{n})$. Note
that, by eliminating all $+$-gates, except the output gates, we obtain a
$\operatorname{CC}^{+}[m]$-circuit $C_{n}^{\prime}$ of depth at most
$d=3\lfloor\log_{2}|A|\rfloor-2$.

Since $C_{n}$ is $0$-absorbing, the circuit
$C_{n}^{\prime}(c_{1}y_{1},\ldots,c_{s}y_{sn})$, for $c_{i}=(mp_{i}^{-1})$ is
$0$-absorbing and has the same range as $eC_{n}$. As $C_{n}$ is not constant,
there is an output gate of $C_{n}^{\prime}$ that induces a nonconstant
$0$-absorbing operation. By Lemma 7 (1) we can compute in linear time a
$\operatorname{CC}[m]$-circuit of the same depth, that defines the $sn$-ary
$\operatorname{AND}$. Therefore there is a $K$, such that
$f_{\mathbf{A}}(n)\geq Kg_{m,d}(sn)\geq Kg_{m,d}(n)$; the constant $K$ results
from the fact that all computations only required linear time.

For (2) note that by Lemma 7 (2), for every $\operatorname{CC}[m]$-circuit $C$
of depth $d$ defining $\operatorname{AND}$, we can construct in linear time a
nonconstant, $0$-absorbing $\operatorname{CC}^{+}[m]$-circuit $C^{\prime}$ of
depth $d+1$. Let us define $\mathbf{B}$ to be the $(d+2)$-nilpotent algebra
$\mathbf{D}$ given by Lemma 9 for depth $d+1$. We then can compute a circuit
$C^{\prime\prime}$ over $\mathbf{B}$ such that
$C^{\prime\prime}(x_{1},\ldots,x_{n})$ evaluates to
$(C^{\prime}(\pi_{d+2}(x_{1}),\ldots,\pi_{d+2}(x_{n})),0,\ldots,0)$.
$C^{\prime\prime}$ is clearly nonconstant and $0$-absorbing. This concludes
the proof of (2). ∎

Theorem 11 directly implies that Conjecture 1 is true, if and only if
nonconstant $0$-absorbing polynomial operations in nilpotent algebras require
circuits of exponential size. So we obtain Theorem 2 as a direct corollary.

Moreover Theorem 11 implies that also the weak version of Conjecture 1, which
states that $\operatorname{AND}$ is not in $\operatorname{CC}^{0}$, has an
algebraic counterpart by the following equivalence:

######  Corollary 12.

$\operatorname{AND}$ is in $\operatorname{CC}^{0}$ if and only if there is a
nilpotent algebra $\mathbf{A}$ (from a congruence modular variety) and a
series of circuits $(C_{n}(\bar{x}))_{n\in{\mathbb{N}}}$ over $\mathbf{A}$
that grows polynomially and defines nonconstant $0$-absorbing polynomials of
all arities.

We further remark that, if $m$ is an odd prime, Proposition 10 allows us to
reprove results about nilpotent algebras: Since we know that bounded depth
$\operatorname{CC}[m]$-circuits are not able to define $\operatorname{AND}$,
Proposition 10 implies that finite nilpotent algebras of prime power order
only have nonconstant $0$-absorbing polynomials up to some arity. This was
independently already shown in [BB87]. In fact, finite nilpotent algebras that
have nonconstant $0$-absorbing polynomials only up to some fixed arity (so
called _supernilpotent_ algebras) are characterized by being direct products
of nilpotent algebras of prime power size [Kea99]. Nilpotent groups and rings
are examples of supernilpotent algebras.

In [IKK18] it was further shown that, if $\mathbf{A}$ is 2-nilpotent and
$\mathbf{A}=\mathbf{L}\otimes\mathbf{U}$, where $\mathbf{L}$ and $\mathbf{U}$
are two vector spaces of different characteristics $p$ and $q$, there are
nonconstant $0$-absorbing polynomial operations that can be computed by
circuits of exponential size $\mathcal{O}(c^{n})$; however they cannot be
computed by circuits of smaller size. In the spirit of Theorem 11, this can be
also seen as the algebraic counterpart of the well-known fact that
$\operatorname{MOD}_{p}-\operatorname{MOD}_{q}$ need at least size
$\mathcal{O}(c^{n})$ to compute $\operatorname{AND}$ [BST90].

##  4\. Circuit satisfiability and equivalence

In this section we discuss the complexity of the circuit satisfiability and
the circuit equivalence problem for nilpotent algebras. The circuit
satisfiability $\operatorname{\mathsf{CSAT}}(\mathbf{A})$ models the question,
whether a single equation over the algebra $\mathbf{A}$ has a solution; the
circuit equivalence problem $\operatorname{\mathsf{CEQV}}(\mathbf{A})$ asks
whether an equation holds for all assignments of variables. Both problems were
introduced in [IK18] and are formally defined as follows:

Circuit satisfiability $\operatorname{\mathsf{CSAT}}(\mathbf{A})$
Input: Two circuits $C,C^{\prime}$ over $\mathbf{A}$ with input gates
$\bar{x}=(x_{1},\ldots,x_{n})$
Question: Is there a tuple $\bar{a}\in A^{n}$ such that
$C(\bar{a})=C^{\prime}(\bar{a})$?

Circuit equivalence $\operatorname{\mathsf{CEQV}}(\mathbf{A})$
Input: Two circuits $C,C^{\prime}$ over $\mathbf{A}$ with input gates
$\bar{x}=(x_{1},\ldots,x_{n})$
Question: Is $C(\bar{a})=C^{\prime}(\bar{a})$ for all $\bar{a}\in A^{n}$?

Circuits over finite algebras can be evaluated in polynomial time. Therefore
$\operatorname{\mathsf{CSAT}}(\mathbf{A})$ is always in
$\operatorname{\mathsf{NP}}$ and $\operatorname{\mathsf{CEQV}}(\mathbf{A})$ in
$\operatorname{\mathsf{coNP}}$. The major question then is, for which algebras
$\operatorname{\mathsf{CSAT}}$ and $\operatorname{\mathsf{CEQV}}$ are
tractable, and for which they are $\operatorname{\mathsf{NP}}$-complete,
respectively $\operatorname{\mathsf{coNP}}$-complete. In particular this is
still open for nilpotent algebras from congruence modular varieties. We first
show that - under the assumption that Conjecture 1 is true - there are
algorithms for both $\operatorname{\mathsf{CEQV}}(\mathbf{A})$ and
$\operatorname{\mathsf{CSAT}}(\mathbf{A})$ that run in quasipolynomial time.
This gives us a conditional answer to Problem 2 in [IK18].

######  Theorem 13.

Assume that Conjecture 1 is true. Then, for every finite nilpotent algebra
$\mathbf{A}$ from a congruence modular variety
$\operatorname{\mathsf{CSAT}}(\mathbf{A})$ and
$\operatorname{\mathsf{CEQV}}(\mathbf{A})$ can be solved in quasipolynomial
time $\mathcal{O}(e^{(\log n)^{t}})$ (where $t>0$ depends on $\mathbf{A}$).

###### Proof.

We start with the equivalence problem
$\operatorname{\mathsf{CEQV}}(\mathbf{A})$. Without loss of generality we
assume that $\mathbf{A}$ contains a group operation $+$, such that
$(A,+,0,-)=\prod_{i=1}^{s}{\mathbb{Z}}_{p_{i}}$ (otherwise we reduce to such
an algebra by Theorem 5 and Lemma 3). When solving
$\operatorname{\mathsf{CEQV}}(\mathbf{A})$ it is sufficient to find an
algorithm to check whether some input circuit is equivalent to the constant
$0$-circuit (as $C=C^{\prime}$ if and only if $C-C^{\prime}=0$). Thus we are
only considering inputs $C$ and $0$ to
$\operatorname{\mathsf{CEQV}}(\mathbf{A})$.

By Proposition 10 we can identify $C(x_{1},\ldots,x_{n})$ with a
$\operatorname{CC}^{+}[m]$-circuit $C^{\prime}(y_{1},\ldots,y_{sn})$ having a
depth $d$ and $s$ output gates, where $d$ and $s$ only depend on $\mathbf{A}$.
Then $C(x_{1},\ldots,x_{n})$ is equivalent to $0$ if and only if
$C^{\prime}(c_{1}y_{1},\ldots,c_{s}y_{sn})$ is constant and equivalent to
$(0,0,\ldots,0)$ (see also the discussion after Proposition 10). Let us denote
the output gates of this circuit by $C_{1},\ldots,C_{s}$.

In the case where one of the output gates $C_{i}$ does not compute the
constant $0$ function, there is a tuple $\bar{a}=(a_{1},\ldots,a_{sn})$ such
$C_{i}(\bar{a})\neq 0$. Let us pick $\bar{a}$ such that the number of
coordinates $j$ with $a_{j}=0$ is maximal. For the sake of simplicity, let us
assume that $a_{j}=0$ iff $j>k$ for some $k$. Then, the circuit
$C_{i}(x_{1},\ldots,x_{k},0,\ldots,0)$ defines a nonconstant $0$-absorbing
operations. Since we assume that Conjecture 1 is true, we have that the size
$|C_{i}|$ of this circuit is bigger than $e^{k^{q}}$ for some $q>0$. In other
words $k\leq\log(|C_{i}|)^{l}$, with $l=q^{-1}$.

Thus in order to check, whether $C(\bar{x})$ is equivalent to $0$, we only
need to check, whether all $C_{i}$ evaluates to $0$ for all tuples that have
at most $\log(|C_{i}|)^{l}$-many non-0 elements. There are
$\binom{|C_{i}|}{\log(|C_{i}|)^{l}}=\mathcal{O}(|C_{i}|^{\log(|C_{i}|)^{l}})$
many such tuples. Since $|C_{i}|$ is linear in the size of $C$ we obtain an
algorithm that runs in time
$\mathcal{O}(|C|^{\log(|C|)^{l}})=\mathcal{O}(e^{\log(|C|)^{l+1}})$. Thus the
lemma holds for $t=l+1$.

The satisfiability problem $\operatorname{\mathsf{CSAT}}$ can similarly be
reduced to the problem of checking whether the bounded depth
$\operatorname{CC}^{+}[m]$-circuit $C^{\prime}(c_{1}y_{1},\ldots,c_{s}y_{sn})$
outputs the $s$-ary tuple $(0,0,\ldots,0)$ for some input $\bar{a}$. Let
$f\colon{\mathbb{Z}}_{m}^{s}\to{\mathbb{Z}}_{m}$ the function that outputs $0$
if and only if $x\neq(0,0,\ldots,0)$, and $1$ else. By Lemma 8 (2), $f$ can be
computed by a $\operatorname{CC}^{+}[m]$-circuit of essential depth $3$. So
clearly $C(\bar{x})=0$ has no solution, if and only if
$f(C^{\prime}(c_{1}y_{1},\ldots,c_{s}y_{sm}))$ is constant and equal to $0$.
Thus we reduced $\operatorname{\mathsf{CSAT}}(\mathbf{A})$ to the equivalence
problem for $\operatorname{CC}^{+}[m]$-circuit of a fixed depth, which has a
quasipolynomial algorithm by the above. Note that the depth of this circuit
was bigger than in the argument for $\operatorname{\mathsf{CEQV}}$, thus we
might obtain a bigger value for the constant $t$. ∎

We remark that already [BMM+00] used the same approach to show that the
program satisfiability problem over solvable monoids has a quasipolynomial
algorithm (supposed that Conjecture 1 holds). Moreover the algorithm described
in Theorem 13 was already studied for the special case where $|A|$ is power of
some prime $p$. As already mentioned, then $\operatorname{CC}[p]$-circuits of
bounded depth cannot compute $\operatorname{AND}$, which corresponds to
$\mathbf{A}$ only having nonconstant $0$-absorbing polynomials of arity
smaller than some constant $k$. So, in this case we only need to evaluate the
circuits at tuples with $k$-many non $0$-entries, which gives us an algorithm
that runs in polynomial time $\mathcal{O}(|C|^{k})$. For
$\operatorname{\mathsf{CEQV}}$ this was observed in [AM10], algorithms for
$\operatorname{\mathsf{CSAT}}$ were constructed in [Kom18], [IK18] and
[Aic19b].

Finite nilpotent algebras of prime power order and their direct products are
provably the only finite nilpotent algebras, where we have a bound on the
arity of nonconstant $0$-absorbing polynomials. Thus the algorithm described
in Theorem 13 cannot be refined to run in polynomial time for general
nilpotent algebras. However we remark that there are examples of 2-nilpotent,
not supernilpotent algebras for which we can obtain other polynomial-time
algorithms: It was shown in [IKK18] that for nilpotent algebras
$\mathbf{L}\otimes\mathbf{U}$, where both $\mathbf{L}$ and $\mathbf{U}$ are
polynomially equivalent to finite vector space, $\operatorname{\mathsf{CEQV}}$
and $\operatorname{\mathsf{CSAT}}$ are in $\operatorname{\mathsf{P}}$. For
$\operatorname{\mathsf{CEQV}}$ this was generalized to all 2-nilpotent
algebras in [KKK19].

At last we show that, under the assumption that there is an efficient way of
_uniformly_ computing $\operatorname{AND}$ by bounded depth
$\operatorname{CC}[m]$-circuits, there is a nilpotent algebra with intractable
$\operatorname{\mathsf{CSAT}}$ and $\operatorname{\mathsf{CEQV}}$ problem
(note however that this is a stronger assumption than $\operatorname{AND}$
being in $\operatorname{CC}^{0}$).

######  Theorem 14.

Assume that there is a family $(C_{n})_{n\in\mathbb{N}}$ of
$\operatorname{CC}[m]$-circuits of depth $d$, that defines
$\operatorname{AND}$, and is enumerable by a polynomial time Turing machine
(i.e. it outputs $C_{n}(x_{1},\ldots,x_{n})$ on input $1^{n}$). Then there
exists a finite nilpotent algebra $\mathbf{A}$ such that
$\operatorname{\mathsf{CSAT}}(\mathbf{A})$ is
$\operatorname{\mathsf{NP}}$-complete and
$\operatorname{\mathsf{CEQV}}(\mathbf{A})$ is
$\operatorname{\mathsf{coNP}}$-complete.

###### Proof.

Since $(C_{n})_{n\in\mathbb{N}}$ defines $\operatorname{AND}$, $m$ cannot be a
prime. In particular $m>2$. We are first going to reduce the graph-colouring
problem with $m$-colors to the circuit satisfiability problem for
$\operatorname{CC}^{+}[m]$-circuits of depth bounded by $d+1$.

So let $G=(V,E)$ a graph. We are going to identify every vertex $v\in V$ with
a variable $x_{v}$ over ${\mathbb{Z}}_{m}$, representing the color of $v$.
Note that the $\operatorname{CC}^{+}[m]$-circuit
$1-\operatorname{MOD}_{m}(x_{v}-x_{w})$ outputs $1$ if $x_{v}\neq x_{w}$, and
$0$ else. Thus, if we define the circuit $H((x_{v})_{v\in
V})=C_{|E|}((1-\operatorname{MOD}_{m}(x_{v}-x_{w}))_{(v,w)\in E})$, then $H$
outputs $1$ if the assignment $v\mapsto x_{v}$ is a proper coloring of the
graph and $0$ else. So $G$ is yes-instance to the $m$-coloring problem if and
only if $H((x_{v})_{v\in V})=1$ has a solution.

By our assumption $H$ can be computed in polynomial time from $G$, thus we
reduced $m$-coloring to the satisfiability problem for
$\operatorname{CC}^{+}[m]$-circuits of depth bounded by $d+1$. Furthermore,
note that there is no $m$-coloring of $G$ if and only if $H((x_{v})_{v\in V})$
is constant and equal to $0$. Therefore the complement of the $m$-coloring
problem, reduces to checking the equivalence of $CC^{+}[m]$-circuits of depth
$d+1$.

By Lemma 9 there is a nilpotent algebra $\mathbf{A}$, such that we can encode
the $\operatorname{CC}^{+}[m]$-circuit $H$ by a circuit $H^{\prime}$ over
$\mathbf{A}$. Thus $m$-coloring reduces to
$\operatorname{\mathsf{CSAT}}(\mathbf{A})$ and its complement to
$\operatorname{\mathsf{CEQV}}(\mathbf{A})$. ∎

The proof of Theorem 14 uses a reduction of the coloring problems to
$\operatorname{\mathsf{CSAT}}$ with the help of $0$-absorbing polynomials; we
remark that this idea was used in several other results in the relevant
literature [BL93, GR02, HS11].

If $\operatorname{AND}$ satisfies the criterion in Theorem 14, we also say
that $\operatorname{AND}$ is in _$\operatorname{\mathsf{P}}$ -uniform
$\operatorname{CC}^{0}$_, for short. Note that, by Theorem 11, there is an
equivalent criterion talking about nilpotent algebras:

######  Corollary 15.

$\operatorname{AND}$ is in $\operatorname{\mathsf{P}}$-uniform
$\operatorname{CC}^{0}$ if and only if there is a finite nilpotent algebra
$\mathbf{A}$ from a congruence modular variety, a family of nonconstant
$0$-absorbing circuits $(C_{n}(x_{1},\ldots,x_{n}))_{n\in{\mathbb{N}}}$ over
$\mathbf{A}$, and a polynomial time Turing machine that outputs
$C_{n}(x_{1},\ldots,x_{n})$ on input $1^{n}$.

###### Proof.

This follows directly from the proof of Theorem 11, since we showed how to
compute an $n$-ary circuit computing $\operatorname{AND}$ from a circuit
$(C_{n}(x_{1},\ldots,x_{n}))_{n\in{\mathbb{N}}}$ over $\mathbf{A}$ in linear
time; and vice-versa. ∎

In Corollary 15 it is essential that the nilpotent algebra is finite. If we
however also look at nilpotent algebras with infinite signature, it is quite
easy to construct examples that have nonconstant $0$-absorbing circuits, which
are enumerable in polynomial time. Theorem 6.1 in [IKK18] gives an example of
a 2-nilpotent algebra $\mathbf{A}=(A,(f_{n})_{n\in\mathbb{N}})$, for which
this is the case, and which has hard $\operatorname{\mathsf{CSAT}}$ and
$\operatorname{\mathsf{CEQV}}$ problems. Interestingly this algebra
$\mathbf{A}$ is also polynomially equivalent to a fine nilpotent algebra
$\mathbf{A}^{\prime}$, which in turn however fails to efficiently enumerate
the same polynomial operations and satisfies
$\operatorname{\mathsf{CSAT}}(\mathbf{A}^{\prime})\in\operatorname{\mathsf{P}}$
and
$\operatorname{\mathsf{CEQV}}(\mathbf{A}^{\prime})\in\operatorname{\mathsf{P}}$.

## References

  * [Aic19a] Erhard Aichinger.  Bounding the free spectrum of nilpotent algebras of prime power order.  Israel Journal of Mathematics, (230):919–947, 2019.
  * [Aic19b] Erhard Aichinger.  Solving Systems of Equations in Supernilpotent Algebras.  In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019), volume 138, pages 72:1–72:9, 2019.
  * [AM10] Erhard Aichinger and Nebojša Mudrinski.  Some applications of higher commutators in Mal’cev algebras.  Algebra universalis, 63(4):367–403, 2010.
  * [Bar89] David A Barrington.  Bounded-width polynomial-size branching programs recognize exactly those languages in NC1.  Journal of Computer and System Sciences, 38(1):150–164, 1989.
  * [BB87] Joel Berman and W.J. Blok.  Free spectra of nilpotent varieties.  Algebra Universalis, 24(3):279–282, 1987.
  * [BL93] Stanley Burris and John Lawrence.  The equivalence problem for finite rings.  Journal of Symbolic Computation, 15(1):67–71, 1993.
  * [BMM+00] David Mix Barrington, Pierre McKenzie, Cris Moore, Pascal Tesson, and Denis Thérien.  Equation satisfiability and program satisfiability for finite monoids.  In Proceedings of the 25th International Symposium on Mathematical Foundations of Computer Science (MFCS), pages 172–181. Springer, 2000.
  * [BST90] David Mix Barrington, Howard Straubing, and Denis Thérien.  Non-uniform automata over groups.  Information and Computation, 89(2):109–132, 1990.
  * [Bul17] Andrei A Bulatov.  A dichotomy theorem for nonuniform CSPs.  In Proceedings of the 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 319–330. IEEE, 2017.
  * [Cau96] Hervé Caussinus.  A note on a theorem of Barrington, Straubing and Thérien.  Information Processing Letters, 58(1):31–33, 1996.
  * [CGPT06] Arkadev Chattopadhyay, Navin Goyal, Pavel Pudlák, and Denis Thérien.  Lower bounds for circuits with MODm gates.  In Proceedings of the 47th Annual Symposium on Foundations of Computer Science (FOCS), pages 709–718. IEEE, 2006.
  * [FM87] Ralph Freese and Ralph McKenzie.  Commutator theory for congruence modular varieties, volume 125.  CUP Archive, 1987.
  * [FSS84] Merrick Furst, James B. Saxe, and Michael Sipser.  Parity, circuits, and the polynomial-time hierarchy.  Mathematical systems theory, 17(1):13–27, 1984.
  * [GR02] Mikael Goldmann and Alexander Russell.  The complexity of solving equations over finite groups.  Information and Computation, 178(1):253–262, 2002.
  * [Hås86] Johan Håstad.  Almost optimal lower bounds for small depth circuits.  In Proceedings of the 18th annual ACM symposium on Theory of computing (STOC), pages 6–20, 1986.
  * [HK10] Kristoffer Arnsfelt Hansen and Michal Kouckỳ.  A new characterization of ACC0 and probabilistic CC0.  Computational Complexity, 19(2):211–234, 2010.
  * [HS11] Gábor Horváth and Csaba Szabó.  The extended equivalence and equation solvability problems for groups.  Discrete Mathematics & Theoretical Computer Science, 13(4):23–32, 2011.
  * [HS12] Gábor Horváth and Csaba Szabó.  Equivalence and equation solvability problems for the alternating group $A_{4}$.  Journal of Pure and Applied Algebra, 2012.
  * [IK18] Paweł M. Idziak and Jacek Krzaczkowski.  Satisfiability in multi-valued circuits.  In Proceedings of the 33rd Annual Symposium on Logic in Computer Science (LICS), pages 550–558. ACM, 2018.
  * [IKK18] Pawel M. Idziak, Piotr Kawalek, and Jacek Krzaczkowski.  Expressive power, satisfiability and equivalence of circuits over nilpotent algebras.  In Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.
  * [IKK20] Pawel M. Idziak, Piotr Kawałek, and Jacek Krzaczkowski.  Intermediate problems in modular circuits satisfiability.  In Proceedings of the 35th Annual Symposium on Logic in Computer Science (LICS), pages 578–590, 2020.
  * [Kea99] Keith Kearnes.  Congruence modular varieties with small free spectra.  Algebra Universalis, 42(3):165–181, 1999.
  * [KKK19] Michael Kompatscher, Jacek Krzaczkowski, and Piotr Kawałek.  Circuit equivalence in 2-nilpotent algebras.  aXiv preprint, arXiv:1909.12256, 2019.
  * [Kom18] Michael Kompatscher.  The equation solvability problem over supernilpotent algebras with Mal’cev term.  International Journal of Algebra and Computation, 28(06):1005–1015, 2018.
  * [MPT91] Pierre McKenzie, Pierre Péladeau, and Denis Thérien.  NC1: The automata-theoretic viewpoint.  Computational Complexity, 1(4):330–359, 1991.
  * [Smo87] Roman Smolensky.  Algebraic methods in the theory of lower bounds for boolean circuit complexity.  In Proceedings of the 19th annual ACM symposium on Theory of computing (STOC, pages 77–82. ACM, 1987.
  * [Vol99] Heribert Vollmer.  Introduction to circuit complexity: a uniform approach.  Springer Science & Business Media, 1999.
  * [Yao85] Andrew Chi-Chih Yao.  Separating the polynomial-time hierarchy by oracles.  In Proceedings of the 26th Annual Symposium on Foundations of Computer Science (SFCS), pages 1–10. IEEE, 1985.
  * [Zhu17] Dmitriy Zhuk.  A proof of CSP dichotomy conjecture.  In Proceedings of the 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 331–342. IEEE, 2017.
  * [Zhu20] Dmitriy Zhuk.  A proof of the CSP dichotomy conjecture.  Journal of the ACM (JACM), 67(5):1–78, 2020.


In more detail, if $Q = Q_{\bs j} = \left(\zeta_{1,j_1}, \zeta_{1,j_1+1}\right) \times \left(\zeta_{2,j_2}, \zeta_{2,j_2+1}\right)$ for some $\bs j \in \bs J$, there are polar angles $\varphi_{j_2}, \varphi_{j_2+1} \in [0,2\pi]$ such that $\mathring{Q} =  \left(\zeta_{1,j_1}, \zeta_{1,j_1+1}\right) \times \left(\varphi_{j_2}, \varphi_{j_2+1}\right)$. This can be proven using the bijectivity of the parameterizations away from the singular edge $\{(0,\zeta_2) : \zeta_2 \in [0,1]\}$.

§ ACKNOWLEDGMENTS

The authors thank Thomas Takacs, Alessandro Reali and Volker Kempf for motivating and insightful scientific discussions which helped to place the results of this paper within the existing literature context.

sort   compress


$\displaystyle\sum_{\boldsymbol{q}}\dfrac{1}{4Nd^{2}}e^{-\gamma|t-t^{\prime}|}\left(\cos(\overline{\omega}_{\boldsymbol{q}}|t-t^{\prime}|)-\dfrac{\gamma}{\overline{\omega}_{\boldsymbol{q}}}\sin(\overline{\omega}_{\boldsymbol{q}}|t-t^{\prime}|)\right)\
.$ (162)

###  C.5 Summary of phonons marginalization

Let us summarize the main results obtained so far. We started from the
equations of motion for a system of spin degrees of freedom following a
precession dynamics and interacting with the vibrational degrees of freedom of
the lattice. We explicitly solved the equations for the phonons, as a function
of the spins. This procedure lead, after some approximations, to the following
effective equations of motion for the spins only111We set the initial
condition $t_{0}=-\infty$ and write the two cases, isolated system and phonons
coupled to an external bath, in the same way.,

$\dfrac{d\boldsymbol{\sigma}_{i}}{dt}=\\{H_{0},\boldsymbol{\sigma}_{i}\\}-\hbar^{-1}\left(\dfrac{\alpha^{2}}{\hbar
K}\right)\sum_{j}\Lambda_{ij}\int_{-\infty}^{t}dt^{\prime}2{\cal
R}(t-t^{\prime})\left(\dfrac{\partial
H_{0}}{\partial\boldsymbol{\sigma}_{j}}\right)_{t^{\prime}}+\boldsymbol{\xi}_{i},$
(163)

where $\boldsymbol{\xi}_{i}$ is a Gaussian noise, with zero mean and
correlation given by,

$\langle\xi^{\mu}_{i}(t)\xi^{\nu}_{j}(t^{\prime})\rangle=2k_{B}T\hbar^{-1}\left(\dfrac{\alpha^{2}}{\hbar
K}\right)\Lambda_{ij}\delta_{\mu\nu}{\cal R}(t-t^{\prime})\ .$ (164)

${\cal R}(t-t^{\prime})$ is a dimensionless non-Markovian memory kernel
dependent on the details of the phonons. For an isolated system, we have,

$\displaystyle{\cal R}(t-t^{\prime})=$
$\displaystyle\sum_{\boldsymbol{q}}\dfrac{1}{4Nd^{2}}\cos(\omega_{\boldsymbol{q}}t-t^{\prime})\
,$ (165)

while for a system where phonons (but not spins) are in contact with a thermal
bath, we have,

$\displaystyle{\cal R}(t-t^{\prime})=$
$\displaystyle\sum_{\boldsymbol{q}}\dfrac{1}{4Nd^{2}}e^{-\gamma|t-t^{\prime}|}\left(\cos(\overline{\omega}_{\boldsymbol{q}}|t-t^{\prime}|)-\dfrac{\gamma}{\overline{\omega}_{\boldsymbol{q}}}\sin(\overline{\omega}_{\boldsymbol{q}}|t-t^{\prime}|)\right).$
(166)

###  C.6 Discrete-time Markovian approximation

Because of the memory kernel in Eq.(163), what we have obtained so far is a
non-Markovian thermostat, while the DLT presented in the main text is
Markovian. In this section we show that, under appropriate conditions, we can
recover a Markovian dynamics by discretizing the continuous stochastic process
over a sufficiently long time scale. Every stochastic differential equation
must ultimately be brought back to its discrete time version for it to make
sense, so we rewrite (163) as,

$d\boldsymbol{\sigma}_{i}=\\{H_{0},\boldsymbol{\sigma}_{i}\\}dt-\left[\hbar^{-1}\left(\dfrac{\alpha^{2}}{\hbar
K}\right)\sum_{j}\Lambda_{ij}\int_{-\infty}^{t}dt^{\prime}2{\cal
R}(t-t^{\prime})\left(\dfrac{\partial
H_{0}}{\partial\boldsymbol{\sigma}_{j}}\right)_{t^{\prime}}\right]dt+d\boldsymbol{{w}}_{i},$
(167)

where $d\boldsymbol{{w}}_{i}={\boldsymbol{\xi}}_{i}dt$ is the noise on scale
$dt$. The microscopic timescale $dt$ has to be interpreted as the minimal
physical time increment over which the system’s dynamics takes place. The
derivation of the previous sections shows that on this minimal timescale the
noise correlator has memory, i.e. $\langle d\boldsymbol{{w}}_{i}(t)\cdot
d\boldsymbol{{w}}_{i}(t^{\prime})\rangle\sim{\cal R}(t-t^{\prime})dt^{2}$. We
can however ask whether, when considering the dynamics on scales larger than
this minimal increment, a Markovian process can be recovered. Let us assume
that the spins vary in time slowly compared with the time span of ${\cal
R}(t-t^{\prime})$. In this case, we immediately see that a simplification
occurs in Eq. (167), because the quantity $\partial
H_{0}/\partial{\boldsymbol{\sigma}_{j}}$ only depends on the spin variables
and can be brought out of the integral. If we then define,

$\tau_{\mathrm{m}}=\int_{-\infty}^{+\infty}ds{\cal
R}(s)=\int_{-\infty}^{0}ds2{\cal R}(s),$ (168)

Eq. (167) can be rewritten as,

$d\boldsymbol{\sigma}_{i}=\\{H_{0},\boldsymbol{\sigma}_{i}\\}dt-\left[\hbar^{-1}\left(\dfrac{\alpha^{2}}{\hbar
K}\right)\tau_{\mathrm{m}}\sum_{j}\Lambda_{ij}\left(\dfrac{\partial
H_{0}}{\partial\boldsymbol{\sigma}_{j}}\right)_{t}\right]dt+d\boldsymbol{{w}}_{i}.$
(169)

Consistently with the above assumption, it is reasonable to look at the spin
dynamics over a lower time resolution, because changes in the spins are
negligible on the minimal scale $dt$. We can then consider a discrete time
increment $\Delta t\gg\tau_{\mathrm{m}}$, which is much larger than the decay
time of ${\cal R}$, but also much smaller than the time scale over which the
spins vary significantly. The dynamical evolution of the spins on this coarse-
grained timescale can be easily obtained by integrating Eq. (169) between $t$
and $t+\Delta t$, and considering the spins to be constant in this integration
interval. We get,

$\Delta\boldsymbol{\sigma}_{i}=\\{H_{0},\boldsymbol{\sigma}_{i}\\}\Delta
t-\left[\hbar^{-1}\left(\dfrac{\alpha^{2}}{\hbar
K}\right)\tau_{\mathrm{m}}\sum_{j}\Lambda_{ij}\left(\dfrac{\partial
H_{0}}{\partial\boldsymbol{\sigma}_{j}}\right)_{t}\right]\Delta
t+\Delta\boldsymbol{{w}}_{i},$ (170)

where,

$\Delta\boldsymbol{{w}}_{i}=\int_{t}^{t+\Delta t}d\boldsymbol{{w}}_{i}$ (171)

Eq. (170) is now the lower time resolution version of Eq. (167). Memory is not
present anymore in the relaxational term and $\Delta\boldsymbol{{w}}_{i}$ is
the coarse-grained noise over scale $\Delta t$. From (171) we find,

$\langle\Delta{w}^{\mu}_{i}(t_{1})\Delta{w}^{\nu}_{j}(t_{2})\rangle=2k_{B}T\hbar^{-1}\left(\dfrac{\alpha^{2}}{\hbar
K}\right)\Lambda_{ij}\delta_{\mu\nu}\int_{t_{1}}^{t_{1}+\Delta
t}dt\int_{t_{2}}^{t_{2}+\Delta t}dt^{\prime}{\cal R}(t-t^{\prime})\ ,$ (172)

where $t_{1}$ and $t_{2}$ are multiples of the new time resolution $\Delta t$.
Now, since $\Delta t$ is much larger than the decay time of ${\cal R}$, if
$t_{1}\neq t_{2}$ Eq. (172) gives 0; on the other hand, if $t_{1}=t_{2}$, all
the times where the function is significantly different from 0 are inside the
integration range, thus yielding the aforementioned $\tau_{\mathrm{m}}$.
Therefore, we have

$\langle\Delta{w}^{\mu}_{i}(t_{1})\Delta{w}^{\nu}_{j}(t_{2})\rangle=2k_{B}T\hbar^{-1}\left(\dfrac{\alpha^{2}}{\hbar
K}\right)\tau_{\mathrm{m}}\Lambda_{ij}\delta_{\mu\nu}\Delta
t\;\delta_{t_{1},t_{2}}\ .$ (173)

We then recover white uncorretaled noise (i.e. $\Delta{w}^{\mu}_{i}(t)$ is a
Wiener process on scale $\Delta t$), together with the correct FD relation
between its correlation and the relaxational coefficient.

Equation (170) is therefore Markovian and it has the very same structure on
scale $\Delta t$ as the DLT equation used in the main text. This can be seen
explicitly by discretizing Eq. (11) of the main text on scale $\Delta t$,
which becomes

$\Delta\boldsymbol{\sigma}_{i}=\\{H_{0},\boldsymbol{\sigma}_{i}\\}\Delta
t-\left[\hbar^{-1}\lambda\sum_{j}\Lambda_{ij}\left(\dfrac{\partial
H_{0}}{\partial\boldsymbol{\sigma}_{j}}\right)_{t}\right]\Delta
t+\Delta\boldsymbol{w}_{i}\ ,$ (174)

with

$\langle\Delta{w}^{\mu}_{i}(t_{1})\Delta{w}^{\nu}_{j}(t_{2})\rangle=2k_{B}T\hbar^{-1}\lambda\Lambda_{ij}\delta_{\mu\nu}\Delta
t\;\delta_{t_{1},t_{2}}\ .$ (175)

By comparing these two equations with Eqs. (170) (173) we can finally identify
the relaxational coefficient $\lambda$ as,

$\lambda=\left(\dfrac{\alpha^{2}}{\hbar K}\right)\tau_{\mathrm{m}},$ (176)

which is (finally) equation (53) of the main text.


# Noise estimation in an entanglement distillation protocol

Ananda G. Maity${}^{\text{*}}$

Joshua C. A. Casapao

Naphan Benchasattabuse

Networked Quantum Devices Unit, Okinawa Institute of Science and Technology
Graduate University,  Onna-son, Okinawa 904-0495, Japan  Networked Quantum
Devices Unit, Okinawa Institute of Science and Technology Graduate University,
Onna-son, Okinawa 904-0495, Japan  Keio University Shonan Fujisawa Campus,
5322 Endo, Fujisawa, Kanagawa 252-0882, Japan  Michal Hajdušek

Rodney Van Meter

David Elkouss

Keio University Shonan Fujisawa Campus,  5322 Endo, Fujisawa, Kanagawa
252-0882, Japan  Keio University Shonan Fujisawa Campus,  5322 Endo, Fujisawa,
Kanagawa 252-0882, Japan  Networked Quantum Devices Unit, Okinawa Institute of
Science and Technology Graduate University,  Onna-son, Okinawa 904-0495, Japan

###### Abstract

Estimating noise processes is an essential step for practical quantum
information processing. Standard estimation tools require consuming valuable
quantum resources. Here we ask the question of whether the noise affecting
entangled states can be learned solely from the measurement statistics
obtained during a distillation protocol. As a first step, we consider states
of the Werner form and find that the Werner parameter can be estimated
efficiently from the measurement statistics of an idealized distillation
protocol. Our proposed estimation method can find application in scenarios
where distillation is an unavoidable step.

###### keywords:

Entanglement distillation, Pauli-noise, Parameter estimation

##  1 Introduction

The quantum Internet will provide an avenue for creating quantum information
shared among distant nodes of a network, allowing distributed information
processing and communication tasks which are beyond the capabilities of
classical networks [6, 5, 4]. Some notable examples are: quantum key
distribution, higher-precision clock synchronization, and distributed quantum
computing.

However, realisation of the above tasks requires the distribution of high
quality entanglement between the distant nodes. Long-distance remote
entanglement distribution remains a challenge as entanglement attenuates
exponentially with distance and cannot be amplified because of the no-cloning
theorem; quantum repeaters [1] and entanglement distillation protocols [2] can
be used to overcome the effects of noise and loss. In particular, an
entanglement distillation protocol transforms a number of low-quality
entangled states into a smaller number of entangled states with higher
quality.

Thus, designing methods for estimating the noise processes efficiently is of
foremost importance. Approaches include tomography, randomized benchmarking,
self-testing, quantum gate set tomography and so on [3]. However, most of
these estimation methods fully measure the quantum resources, making them
useless for further information processing tasks.

In this work, we ask whether the noise parameters can be efficiently
characterized from the measurement statistics obtained during a distillation
protocol. This is particularly relevant for those information processing tasks
where distillation is an unavoidable step. For example in a quantum network,
for establishing high quality entanglement, one may need to perform
distillation. Moreover, eliminating noise estimation as a separate task might
also simplify the quantum network management.

In the following, we describe a procedure for estimating the noise parameter
from the measurement statistics of a distillation protocol. We investigate the
number of samples required for estimating the state parameters of the Werner
state in a usual tomography method and in a distillation protocol. We find
that the distillation-based estimation protocol can be more efficient than
state tomography for some parameter regimes. We also propose an algorithm for
experimental realisation of the distillation based estimation protocol.

##  2 Preliminaries

Distillation protocol: We consider the distillation protocol proposed by
Bennett et. al [2], where two distant parties (Alice and Bob) cooperate to
improve the fidelity of shared quantum states. The protocol proceeds as
follows:

1) Alice and Bob start with two copies of a noisy entangled state. Here, we
assume that the state is a Werner state and characterized by the Werner
parameter $w$:

$\displaystyle\rho_{w}=$
$\displaystyle(1-w)\ket{\Phi^{+}}\bra{\Phi^{+}}+\frac{w}{4}\mathbb{I}$ (1)

The fidelity of such a Werner state as a function of $w$ with $\ket{\Phi^{+}}$
is $F=1-\frac{3w}{4}$.

2) Each applies local XOR operations on the local parts of their two copies,
with one copy as the control and another one as the target.

3) Each of them measures the target qubit in the $Z$-basis and communicates
the results classically.

4) If they obtain correlated outcomes i.e, $00,11$ they keep the unmeasured
copy, otherwise they discard the state.

After doing this protocol, the fidelity of the new state becomes
$F^{\prime}=\frac{F^{2}+\frac{1}{9}(1-F)^{2}}{F^{2}+\frac{2}{3}F(1-F)+\frac{5}{9}(1-F)^{2}}$
where $F^{\prime}>F$ if $F>\frac{1}{2}$ [2]. One may in general repeat the
above protocol recursively and obtain a perfect $\ket{\Phi^{+}}$
asymptotically.

Statistical tools used for the parameter estimation: An important question in
probability theory is: given a random variable $X$ and its expectation
$\mathbb{E}(X)$, how likely is $X$ to be close to $\mathbb{E}(X)$ i.e,
$\text{Pr}(|X-\mathbb{E}(X)|\geq t)$ for some $t\geq 0$? For this purpose,
here we use Hoeffding’s inequality. Suppose $X_{1},...,X_{n}$ are independent
random variables and $a\leq X_{i}\leq b$, then for any $t>0$,

$\text{Pr}(|\frac{1}{n}\sum_{i}(X_{i}-\mathbb{E}(X_{i})|\geq t)\leq
2\exp{\left(-\frac{2nt^{2}}{(b-a)^{2}}\right)}.$ (2)

##  3 Werner parameter estimation

Given an unknown state of the Werner form, here we sketch how to estimate the
Werner parameter from the measurement outcomes of a distillation protocol. To
evaluate the potential interest of this approach, we compare the precision of
the estimate with the precision achieved with state tomography.

Werner parameter estimation in a distillation protocol: Assume that Alice and
Bob hold two copies of a two-qubit Werner state and perform the distillation
protocol described in the previous section. The probability of observing the
outcome $00$, $p_{00}$, can be computed as $p_{00}=\frac{1}{4}(2-2w+w^{2})$.
Or alternatively;

$w=1-\sqrt{4p_{00}-1}.$ (3)

The value of $p_{00}$ also corresponds to the expected value of a random
variable $P_{00}$ that assigns value 1 to the measurement outcomes $00$ and
value 0 to any other outcome i.e, $p_{00}=\mathbb{E}(P_{00})$.

Now in an experiment, one may estimate the probability of observing the
outcomes 00. We denote this estimate by $\hat{p}_{00}$. Then from Hoeffding’s
inequality, we have

$\text{Pr}(|\hat{p}_{00}-{p}_{00}|\geq\epsilon)\leq
2\exp{(-{2}n\epsilon^{2})}.$ (4)

From $\hat{p}_{00}$, it is possible to obtain an estimate $\hat{w}$ of the
Werner parameter with Equation 3. Let us now sketch how to bound the precision
of the estimated $\hat{w}$. If we desire to have
$|\hat{w}-w|\geq\epsilon^{\prime}$ then from Equation 3, we obtain
$|\sqrt{4p_{00}-1}-\sqrt{4\hat{p}_{00}-1}|\geq\epsilon^{\prime}$. After
explicit calculation above condition implies either
$\hat{p}_{00}-p_{00}\geq\frac{1}{4}(-\epsilon^{\prime
2}+2\epsilon^{\prime}(1-w))$ or
$-(\hat{p}_{00}-p_{00})\geq\frac{1}{4}(\epsilon^{\prime
2}+2\epsilon^{\prime}(1-w))$. Taking the loose bound, we can conclude that
when $|\hat{w}-w|\geq\epsilon^{\prime}$, then
$|\hat{p}_{00}-p_{00}|\geq\frac{1}{4}(-\epsilon^{\prime
2}+2\epsilon^{\prime}(1-w))$. Consequently,
$\text{Pr}(|\hat{w}-w|\geq\epsilon^{\prime})$ implies
$\text{Pr}(|\hat{p}_{00}-p_{00}|\geq\frac{1}{4}(-\epsilon^{\prime
2}+2\epsilon^{\prime}(1-w)))$. Using Hoeffding’s inequality leads to the bound

$\text{Pr}(|\hat{w}-w|\geq\epsilon^{\prime})\leq
2\exp{(-{\frac{1}{8}}n(-\epsilon^{\prime
2}+2\epsilon^{\prime}(1-w)){{}^{2}})}.$ (5)

We investigate the scaling of the number of samples with respect to the Werner
parameter $w$ when $\text{Pr}(|\hat{w}-w|\geq\epsilon^{\prime})=0.01$ in Fig.
1.

Werner parameter estimation in tomography: A Werner state can be written in
the locally decomposable form
$\rho_{w}=\frac{1}{4}[\mathbb{I}\otimes\mathbb{I}+(1-w)(X\otimes X-Y\otimes
Y+Z\otimes Z)]$.

In order to do tomography of a bipartite entangled state, Alice and Bob can
measure locally $\\{\mathbb{I},X,Y,Z\\}$ and depending on the joint
probability of $X\otimes X$, $Y\otimes Y$, $Z\otimes Z$ they can estimate the
Werner parameter. One may calculate the probability of getting $00$ (or $11$)
outcome, (when both of them measure in the $Z$ basis)
$p_{00}=p_{11}=\frac{2-w}{4}$. Now if $|\hat{w}-w|\geq\epsilon^{\prime}$, then
one may note that $|\hat{p}_{00}-p_{00}|\geq\frac{\epsilon^{\prime}}{4}$.
Using Hoeffding’s inequality, we get the bound

$\text{Pr}(|\hat{w}-w|\geq\epsilon^{\prime})\leq
2\exp{(-{\frac{1}{8}}n\epsilon^{\prime 2})}.$ (6)

Figure 1: Minimum number of samples $n$ required for estimating the Werner
parameter $w$ with failure probability
$\mathrm{Pr}(|\hat{w}-w|\geq\epsilon^{\prime})=0.01$. The solid (dashed)
curves correspond to the estimation via a noise-free distillation protocol
(via tomography). The dash-dotted curves correspond to the distillation
protocol in the presence of depolarizing noise, where $S=\exp(-1/5)$. For the
range $w\leq 1/2$, we find that the number of samples required for a
successful distillation-based estimation can be significantly less than that
for tomography.

Estimation of Werner parameter in the presence of depolarizing noise: As a
first step towards the application of these ideas in a realistic setting, we
consider that idling qubits undergo depolarizing noise with the depolarizing
operation given by

$\Lambda(\rho)=(1-x)\rho+\frac{x}{4}\mathbb{I}.$ (7)

Here $x=1-e^{-\frac{t}{T}}$ is the depolarizing parameter. The distillation
protocol under consideration requires two copies of the states. We model the
entanglement generation as a sequential process: after the first copy is
prepared, it undergoes depolarizing noise. However, the second copy can be
used for distillation as soon as it is generated and hence may be considered
to be noise free. We follow the same procedure as discussed earlier and
estimate the Werner parameter. Explicit calculation reveals that if
$|\hat{w}-w|\geq\epsilon^{\prime}$, then
$|\hat{p}_{00}-p_{00}|\geq\frac{S}{4}(-\epsilon^{\prime
2}+2\epsilon^{\prime}(1-w))$ with $S=\frac{1}{n}\sum_{i=1}^{n}(1-x_{i})$.
Hoeffding’s inequality leads to the bound

$\text{Pr}(|\hat{w}-w|\geq\epsilon^{\prime})\leq
2\exp{(-{\frac{1}{8}}nS^{2}(2\epsilon^{\prime}(1-w)-\epsilon^{\prime
2}){{}^{2}})}$ (8)

Note that for tomography the states can be used as soon as they are generated
and hence can be considered as noise free. Thus the bound on the number of
samples is independent of the depolarizing noise parameter.

##  4 Algorithmic estimation

Here we provide an algorithmic procedure that can be used in an idealized
experiment for estimating the Werner parameter. The overall process is
described in Algorithm 1.

The input for this procedure is the number of samples $N$ and the target
estimate precision $\epsilon_{w}$.

For each sample, Alice and Bob prepare two copies of the entangled state.
Then, they apply a local XOR operation on their respective local copies and
finally measure the second copy in the $Z$ basis.

After repeating the experiment $N$ times, they collect the measurement
statistics and estimate the probability of obtaining outcome $00$ as
$\hat{p}_{00}$. From $\hat{p}_{00}$, Alice and Bob can estimate $\hat{w}$ as
$\hat{w}=1-\sqrt{4\hat{p}_{00}-1}$.

The next step is to translate the target precision $\epsilon_{w}$ to a
precision on $\hat{p}_{00}$. The goal of Alice and Bob is to estimate the
probability that $\hat{w}$ is in the range
$[w_{m},w_{p}]=[\hat{w}-\epsilon_{w},\hat{w}+\epsilon_{w}]$. Using the
relation between the Werner parameter and $p_{00}$, this probability is
equivalent to the probability that $\hat{p}_{00}$ is in the range
$[p_{00m},p_{00p}]=[\frac{1}{4}(2-2w_{m}+w_{m}^{2}),\frac{1}{4}(2-2w_{p}+w_{p}^{2})]$.
We can finally let pessimistically
$\epsilon=\text{Max}[|\hat{p}_{00}-p_{00p}|,|\hat{p}_{00}-p_{00m}|]$ and from
Hoeffding’s inequality we conclude that
$\text{Pr}(|\hat{w}-w|\geq\epsilon_{w})\leq 2\exp(-{2}N\epsilon^{2})$.

1:

2:number of samples $N$

3:estimation precision $\epsilon_{w}$

4:

5:failure probability $\delta$

6:estimated Werner parameter $\hat{w}$

7:$n_{\text{count}}\leftarrow 0$

8:for $n=1$ to $N$ do

9: Prepare two copies of the unknown state $\rho_{w,c}$ and $\rho_{w,t}$

10: Alice and Bob locally perform XOR-operation

11: $(Z_{A},Z_{B})\leftarrow M_{Z}^{\otimes 2}\rho_{w,t}$ $\triangleright$
Each measures their half of $\rho_{w,t}$ in the $Z$-basis

12: if $Z_{A}=+1$ and $Z_{B}=+1$ then

13: $n_{\text{count}}\leftarrow n_{\text{count}}+1$

14:$\hat{p}_{00}\leftarrow n_{\text{count}}/N$

15:$\hat{w}\leftarrow 1-\sqrt{4\hat{p}_{00}-1}$

16:(Calculate the extreme values around $\hat{w}$)

17:$w_{p}\leftarrow\hat{w}+\epsilon_{w}$

18:$w_{m}\leftarrow\hat{w}-\epsilon_{w}$

19:(Calculate the extreme values around $p_{00}$)

20:$p_{00p}\leftarrow\frac{1}{4}(2-2w_{p}+w_{p}^{2})$

21:$p_{00m}\leftarrow\frac{1}{4}(2-2w_{m}+w_{m}^{2})$

22:(Calculate precision around $p_{00}$)

23:$\epsilon\leftarrow\text{max}(|\hat{p}_{00}-p_{00p}|,|\hat{p}_{00}-p_{00m}|)$

24:$\delta\leftarrow 2\exp(-{2}N\epsilon^{2})$.

25:Output $\delta$, $\hat{w}$

Algorithm 1 Experiment for estimation of Werner parameter.

##  5 Conclusion

Noise estimation is a key requirement for quantum technologies. In the case of
quantum networks, precise entanglement characterization allows us to optimize
task implementation or to maximize the end-to-end fidelity with entanglement
routing protocols. Existing methods consume valuable entanglement for the
purpose of estimation. In this work, we have shown that in an idealized
scenario, the measurement outcomes of distillation protocols allow us to
characterize efficiently an entangled state. In particular, whenever
distillation is a necessary step, this method works without consuming any
quantum resources. However, the models for noise and processes considered here
are ideal. Further work is necessary to establish the practical relevance of
this approach.

##  6 Acknowledgements

This work was supported by the JST Moonshot R&D program under Grants
JPMJMS226C.

## References

  * [1] Azuma, K., Economou, S. E., Elkouss, D., Hilaire, P., Jiang, L., Lo, H.-K., and Tzitrin, I. Quantum repeaters: From quantum networks to the quantum internet.  Rev. Mod. Phys. 95 (Dec 2023), 045006.
  * [2] Bennett, C. H., Brassard, G., Popescu, S., Schumacher, B., Smolin, J. A., and Wootters, W. K. Purification of noisy entanglement and faithful teleportation via noisy channels.  Phys. Rev. Lett. 76 (Jan 1996), 722–725.
  * [3] Eisert, J., Hangleiter, D., Walk, N., Roth, I., Markham, D., Parekh, R., Chabaud, U., and Kashefi, E. Quantum certification and benchmarking.  Nature Reviews Physics 2, 7 (June 2020), 382–390.
  * [4] Kozlowski, W., Wehner, S., Meter, R. V., Rijsman, B., Cacciapuoti, A. S., Caleffi, M., and Nagayama, S. Architectural Principles for a Quantum Internet.  RFC 9340, Mar. 2023.
  * [5] Van Meter, R., Satoh, R., Benchasattabuse, N., Teramoto, K., Matsuo, T., Hajdušek, M., Satoh, T., Nagayama, S., and Suzuki, S. A quantum internet architecture.  In 2022 IEEE International Conference on Quantum Computing and Engineering (QCE) (2022), pp. 341–352.
  * [6] Wehner, S., Elkouss, D., and Hanson, R. Quantum internet: A vision for the road ahead.  Science 362, 6412 (2018), eaam9288.