# Efficient quantum algorithms for some instances of the semidirect discrete
logarithm problem

Muhammad Imran
Department of Algebra and Geometry,
Budapest University of Technology and Economics,
Egry József u. 1, H-1111 Budapest, Hungary.
E-mail<EMAIL_ADDRESS>Gábor Ivanyos
Research Institute for Computer Science and Control,
Hungarian Research Network,
Kende u. 13-17, H-1111 Budapest, Hungary.
E-mail<EMAIL_ADDRESS>
###### Abstract

The semidirect discrete logarithm problem (SDLP) is the following analogue of
the standard discrete logarithm problem in the semidirect product semigroup
$G\rtimes\operatorname{End}(G)$ for a finite semigroup $G$. Given $g\in
G,\sigma\in\operatorname{End}(G)$, and $h=\prod_{i=0}^{t-1}\sigma^{i}(g)$ for
some integer $t$, the SDLP$(G,\sigma)$, for $g$ and $h$, asks to determine
$t$. As Shor’s algorithm crucially depends on commutativity, it is believed
not to be applicable to the SDLP. Previously, the best known algorithm for the
SDLP was based on Kuperberg’s subexponential time quantum algorithm. Still,
the problem plays a central role in the security of certain proposed
cryptosystems in the family of semidirect product key exchange. This includes
a recently proposed signature protocol called SPDH-Sign. In this paper, we
show that the SDLP is even easier in some important special cases.
Specifically, for a finite group $G$, we describe quantum algorithms for the
SDLP in $G\rtimes{\mathrm{Aut}}(G)$ for the following two classes of
instances: the first one is when $G$ is solvable and the second is when $G$ is
a matrix group and a power of $\sigma$ with a polynomially small exponent is
an inner automorphism of $G$. We further extend the results to groups composed
of factors from these classes. A consequence is that SPDH-Sign and similar
cryptosystems whose security assumption is based on the presumed hardness of
the SDLP in the cases described above are insecure against quantum attacks.
The quantum ingredients we rely on are not new: these are Shor’s factoring and
discrete logarithm algorithms and well-known generalizations.

##  1 Introduction

The presumed difficulty of computing discrete logarithm problem (DLP) in
certain groups is essential for the security of the Diffie-Hellman key
exchange which is the basis for a number of communication protocols deployed
today. However, since the invention of Shor’s algorithm [Sho94], the problem
of computing discrete logarithm can be solved efficiently in the domain of
quantum computing.

Massive efforts have been done in order to construct alternative versions of
the discrete logarithm problem that allow for the Diffie-Hellman key exchange
without being vulnerable to Shor’s algorithm. Since that algorithm takes
advantage of the group structure underlying the problem, a DLP analogue in the
framework of commutative group actions has been proposed. It is an instance of
a constructive membership testing in orbits of commutative permutation groups
(on large finite sets), called _vectorization problem_. The framework
originally appears in [Cou06] and it becomes a central problem of isogeny-
based cryptography, CSIDH [CLM+18] for example. Another natural approach which
is worth consideration to escape from the quantum attack is a DLP analogue in
non-commutative groups. It is natural in a sense that Shor’s algorithm
crucially depends on the commutativity of the underlying groups. In this
direction, an analogue of the DLP in the semidirect product groups has been
proposed. The proposal firstly appears in its full generality in [HKKS13].
Specifically, let $G$ be a finite semigroup and $\operatorname{End}(G)$ be the
monoid of endomorphisms of $G$. Then we have the semidirect product
$G\rtimes\operatorname{End}(G)$ where the multiplication is defined by
$(g,\sigma)(h,\phi)=(g\sigma(h),\sigma\phi)$. Moreover, we have the formula
for exponentiation

$(g,\sigma)^{t}=\left(\prod_{i=0}^{t-1}\sigma^{i}(g),\sigma^{t}\right),$

where $\prod_{i=k}^{\ell}a_{i}$ stands for the product $a_{k}\cdot\ldots\cdot
a_{\ell}$ in $G$. This leads to an analogue of the standard discrete logarithm
problem in the semidirect product semigroup defined as follows. Given $g\in
G,\sigma\in\operatorname{End}(G),$ and $h=\prod_{i=0}^{t-1}\sigma^{i}(g)$ for
some integer $t$, determine $t$.

The SDLP is interesting as it allows us to perform a Diffie-Hellman key
exchange procedure, known as semidirect product key exchange (SPDKE). Suppose
two parties, Alice and Bob, agree on a public group $G$, an element $g\in G$,
and an endomorphism $\sigma\in\operatorname{End}(G)$. Then they can arrive at
the same $G-$element as follows.

  * 1.

Alice picks a random positive integer $x$ and computes
$(g,\sigma)^{x}=\left(A,\sigma^{x}\right)$. Then, Alice sends
$A=\prod_{i=0}^{x-1}\sigma^{i}(g)$ to Bob.

  * 2.

Bob also picks a random positive integer $y$, computes
$(g,\sigma)^{y}=(B,\sigma^{y})$ and sends $B=\prod_{i=0}^{y-1}\sigma^{i}(g)$
to Alice.

  * 3.

Alice computes its shared key $K_{A}=A\sigma^{x}(B)$.

  * 4.

Bob computes its shared key $K_{B}=B\sigma^{y}(A)$.

Note that $K_{A}=K_{B}$, as the following calculation shows.

$\displaystyle\mbox{~{}~{}~{}~{}~{}~{}~{}~{}~{}}A\sigma^{x}(B)$
$\displaystyle=$
$\displaystyle\prod_{i=0}^{x-1}\sigma^{i}(g)\prod_{i=0}^{y-1}\sigma^{x+i}(g)=\prod_{i=0}^{x+y-1}\sigma^{i}(g)$
$\displaystyle=$
$\displaystyle\prod_{i=0}^{y-1}\sigma^{i}(g)\prod_{i=0}^{x-1}\sigma^{y+i}(g)$
$\displaystyle=$ $\displaystyle B\sigma^{y}(A).$

The key recovery problem of SPDKE is the problem of computing the shared key
$K_{A}=K_{B}$ from the public information $g,A,B\in G$ and
$\sigma\in\operatorname{End}(G)$. Clearly, similar to the case of the standard
DLP and the corresponding Diffie-Hellman key exchange, the key recovery
problem of SPDKE and the difficulty of SDLP are heavily related. Particularly,
if one can solve an instance of the SDLP, then one is also able to break the
corresponding SPDKE.

In the description of the SDLP above, an instance of the SDLP in
$G\rtimes\operatorname{End}(G)$ is only specified by an endomorphism $\sigma$,
hence we can describe the SDLP in an alternative, more compact way.

First, we observe some properties of semidirect product semigroups that would
be useful for our purpose. Let $G$ and $T$ be semigroups and let
$\sigma:t\mapsto\sigma_{t}$ be a homomorphism from $T$ to the monoid of
endomorphisms of $G$. Then the semidirect product $G\rtimes_{\sigma}T$ is the
set $G\times T$ equipped with the multiplication
$(g,t)(g^{\prime},t^{\prime})=(g\sigma_{t}(g^{\prime}),tt^{\prime})$. It is
straightforward to check that $G\rtimes_{\sigma}T$ is a semigroup. Also, if
both $G$ and $T$ are finite groups and $\sigma_{1}$ is the identity map of
$G$, then $G\rtimes_{\sigma}T$ is also a group. There is a natural
representation $\rho:(g,t)\mapsto\rho_{(g,t)}$ of $G\rtimes_{\sigma}T$ as a
semigroup of transformations on $G$, given by
$\rho_{(g,t)}(g^{\prime})=g\sigma_{t}(g^{\prime})$. This is indeed a
representation, i.e., a homomorphism to the semigroup of transformations,
because we have
$(g,t)(g^{\prime},t^{\prime})=(\rho_{(g,t)}(g^{\prime}),tt^{\prime})$ and

$\rho_{(g,t)(g^{\prime},t^{\prime})}=\rho_{(\rho_{(g,t)}(g^{\prime}),tt^{\prime})}=\rho_{(g,t)}\circ\rho_{(g^{\prime},t^{\prime})}.$

If $G\rtimes_{\sigma}T$ is a group as above then $\rho$ gives a permutation
representation of the group $G\rtimes_{\sigma}T$.

Note that if $G$ is a monoid and $\sigma$ is a monoid endomorphims of $G$
(that is, $\sigma(1_{G})=1_{G}$), then we have
$(g,1)^{t}=(\rho_{(g,1)^{t}}(1_{G}),t)$. This shows that, as already observed
by Battarbee _et al._ in [BKPS22], the SDLP can be cast as a constructive
membership problem in an orbit of a transformation semigroup. Using the above
observation and notations we have the following definition for the semidirect
discrete logarithm that will be used throughout this paper.

######  Definition 1.

Let $\sigma$ be an endomorphism of the finite monoid $G$ with identity element
$1_{G}$ and consider the semigroup $G\rtimes_{\sigma}{\mathbb{Z}}_{\geq 0}$
where $\sigma_{t}=\sigma^{t}$ for every $t\in{\mathbb{Z}}_{\geq 0}$. Then
SDLP$(G,\sigma)$ is the following problem. Given elements $g$ and $h$ of $G$,
determine the set of non-negative integers $t$ such that

$h=\rho_{(g,1)^{t}}(1_{G}).$

The set to be determined is either the empty set, a singleton, or
$\\{x_{0}+ax:x\in{\mathbb{Z}}_{\geq 0}\\}$ for some integers $x_{0}\geq 0$ and
$a>0$. Indeed, an orbit of a semigroup generated by a single transformation on
a finite set consists of a tail of a certain length called the index, followed
by a recurrent cycle, whose length is called the period. The index can be zero
while the period is positive. Note that these parameters can be computed by a
slight modification of Shor’s period finding quantum algorithm, see [CI14]. In
our case, the transformation semigroup is generated by $\rho_{(g,1)}$ and our
objective is the orbit of it starting at $1_{G}$. The solution set is a
singleton if $h$ is in the tail, while in the case when $h$ is in the cycle,
it is $\\{x_{0}+ax:x\in{\mathbb{Z}}_{\geq 0}\\}$, where $a$ is the period and
$x_{0}$ is the position of $h$ in the cycle, shifted by the index.

We remark that the assumptions that $G$ is a monoid and that $\sigma$ is a
monoid endomorphism of $G$ are rather technical, though they offer some
notational conveniences. In the general semigroup case, one should solve the
equation $h=\rho_{(g,1)^{t-1}}(g)$.

Battarbee _et al._ [BKPS22] present a subexponential quantum algorithm for the
SDLP in so-called the easy family of semigroups $\\{G_{p}\\}_{p\in P}$ for
some countable set $P$. A family of semigroups $\\{G_{p}\\}_{p\in P}$ is
called easy if the size $|G_{p}|$ grows monotonically and polynomial in $p$,
and the evaluation costs of $gh$ and $\sigma(g)$ is $\mathcal{O}((\log
p)^{2})$ for any $p\in P$, $g,h\in G_{p}$, and
$\sigma\in\operatorname{End}(G_{p})$. Indeed, the critical problem is
determining the position of $h$ in the cycle, which is actually an instance of
the vectorization problem, and hence reduces to the abelian hidden shift
problem for which Kuperberg’s subexponential time algorithm [Kup05] is
available. On the other hand, there exist several efficient algorithms that
break the SPDKE protocols in some specific groups without solving the
corresponding SDLP, instead exploiting the structure of the platform groups to
directly solve the corresponding key recovery problem. See [BKS22] for a more
detailed survey on the semidirect product key exchange. The most recent work
in this direction is by Battarbee _et al._ [BKPS23]. They propose a post-
quantum signature scheme, called SPDH-Sign, where the security depends on the
presumed difficulty of the group case of the SDLP. Moreover, they propose non-
abelian groups of order $p^{3}$ for some odd prime $p$ as candidate groups for
SPDH-Sign.

In this paper, we work over black-box groups with non-necessarily unique
encoding of elements to obtain sufficiently general results. (Together with
assuming ability of evaluating powers of $\sigma$, this corresponds to the
easy families of [BKPS22].) The concept of black-box groups was introduced by
Babai and Szemerédi [BS84] for studying the structure of finite matrix groups.
Elements of a black-box group $G$ are represented by binary strings of a
certain length and the group itself is given by a list of generators. The
group operations are given by oracles. Here we also assume an oracle for
computing $\sigma^{j}(g)$ for $g\in G$ and $j\in{\mathbb{Z}}_{>0}$. In
general, it is not required that every group element is represented by a
unique code-word. Instead, there is also an oracle for testing whether two
strings represent the same group element. Here we assume a stronger oracle, a
labeling. It is a function $\lambda$ defined on the code-words for the group
elements where $x$ and $y$ represent the same group element if and only if
$\lambda(x)=\lambda(y)$. We use the term black-box group with unique labeling
for that sort of black-box groups. The labeling makes it possible to compute
the structure of $G$ when $G$ is a solvable black-box group by the quantum
algorithm of [IMS01, Theorem 7]. (In that paper the term secondary encoding is
used for the labeling.) The notion includes black-box groups with unique
encoding. We need the generalization in order to handle certain factor groups.
To illustrate how this can occur, assume that initially we work with a matrix
group $G$ and $\sigma$ is given as conjugation by a matrix (possibly outside
$G$) and we have another, non-faithful matrix representation $\phi$ of $G$
whose kernel is $\sigma$-invariant. Suppose further that we need to solve the
SDLP for $\phi(g)$ and $\phi(h)$ in $\mbox{Im}(\phi)$ and the automorphism
induced by $\sigma$. (Recall that this is the unique map
${\overline{\sigma}}:\mbox{Im}(\phi)\rightarrow\mbox{Im}(\phi)$ satisfying
$\psi(\sigma(x))={\overline{\sigma}}(x)$. It is well-defined as the kernel of
$\phi$ is required to be $\sigma$-invariant.) It turns out that we would have
difficulties with evaluating powers of the induced automorphism if we used the
natural unique encoding of the elements of $\mbox{Im}(\phi)$ by matrices. (In
general, this would require finding finding an element of the pre-image
$\phi^{-1}(x)$ for $\mbox{Im}(\phi)$.) We get around the issue by using the
original matrices to encode the elements of $\mbox{Im}(\phi)$ and to multiply
them; while considering $\phi$ as a labeling (and possibly also as further
help). This gives us a simple way to evaluate the induced automorphism.

The SDLP$(G,\sigma)$ is called the group-base case if $G$ is a group, and we
call it the (full) group case when $G$ is a group and $\sigma$ is an
automorphism of $G$. In this paper we focus on the group-base case. If, in
addition, $\sigma$ is an automorphism of $G$ then one could replace the monoid
${\mathbb{Z}}_{\geq 0}$ with an appropriate finite cyclic group
${\mathbb{Z}}_{m}={\mathbb{Z}}/m{\mathbb{Z}}$ where $m$ is a multiple of the
order of $\sigma$ and work over the finite semidirect product group of $G$ and
${\mathbb{Z}}_{m}$. This justifies the terminology.

#### Contributions.

In this paper, we provide an analysis of the SDLP in some interesting classes
of groups. Particularly, in section 2, we first give a reduction from the
group-base case to the group case of the SDLP. Moreover, using essentially the
same idea, we show that there exists a recursion from the SDLP in a group into
its quotient groups and subgroups. In section 3, we then propose efficient
quantum algorithms based on Shor’s algorithm for the group case
SDLP$(G,\sigma)$ for the following cases:

  * 1.

The automorphism $\sigma$ is of small order, i.e., polynomial in $\log|G|$;

  * 2.

The group $G$ is solvable;

  * 3.

The group $G$ is a matrix group over a finite field, i.e.,
$G\leq\operatorname{GL}_{d}({\mathbb{F}}_{q})$, where $q$ is a power of a
prime and $\sigma$ is an inner automorphism of $G$;

  * 4.

A flag $1=M_{0}<M_{1}<\ldots<M_{k}=G$ of $\sigma$-invariant normal subgroups
$M_{i}\lhd G$ is given together with homomorphisms $\psi_{i}$ from $M_{i}$
with kernel $M_{i-1}$ ($i=1,\ldots,k$), where for each $i$, $\psi_{i}$ maps
$M_{i}$ to either

    * 4.1

a black-box group with unique labeling and when automorphism of
$\mbox{Im}(\psi_{i})$ induced by $\sigma$ has polynomially small order; or

    * 4.2

a solvable black-box group with unique labeling; or

    * 4.3

a matrix group over a finite field, in which case we also assume that a power
of the induced automorphism with a polynomially small exponent coincides with
the conjugation by some matrix.

As a consequence, SPDH-Sign protocol in [BKPS23] and all other SPDKE
cryptographic protocols whose platform groups are in the above cases do not
belong to the realm of post-quantum cryptography. We remark that, a normal
series together with the homomorphisms having the properties required in item
4., can be efficiently computed for quite a wide class of finite groups using
advanced algorithms of computational group theory. These include matrix groups
over finite fields of odd characteristic making the innerness assumption of
item 3. unnecessary when $q$ is odd, see the Appendix for a sketch of proof.
We even think that it is difficult to propose any ”concrete” platform group
that item 4. is not applicable to, so a viable platform for SPDH-Sign protocol
should be a semigroup quite far from any group.

##  2 Reduction and recursion of SDLP

In this section, we provide the reduction of the group-base case to the group
case, and we also describe a recursion tool that passes the SDLP in a group to
its quotient groups and subgroups.

From $(g,1)^{t}=(\rho_{(g,1)^{t}}(1_{G}),t)$ we infer the following identity

$\rho_{(g,1)^{rt}}(1_{G})=\rho_{(\rho_{(g,1)^{r}}(1_{G}),r)^{t}}(1_{G}).$ (1)

We will frequently use this fact to reduce an instance of the SDLP for the
endomorphism $\sigma$ to an instance for $\sigma^{r}$ in place of $\sigma$
with suitable choices of $r$.

###  2.1 Reduction from the group-base case to the group case

Let $G$ be a finite group and $\sigma$ be an endomorphism of $G$. We will
describe a reduction from SDLP$(G,\sigma)$ to SDLP$(K,\sigma^{\prime})$ where
$K$ is a subgroup of $G$ and $\sigma^{\prime}$ is the restriction of $\sigma$
to $K$ which forms an automorphism.

Let $K=\cap_{t=0}^{\infty}\sigma^{t}(G)$ and let $k_{0}$ be the smallest non-
negative integer such that $K=\sigma^{k_{0}}(G)$. Obviously,
$k_{0}\leq\lceil\log|G|\rceil$. Let $k\geq k_{0}$, where such a $k$ can be
”blindly” chosen by taking an integer greater than a known upper bound for
$\log|G|$. (Such an upper bound can be $\ell$, where binary strings of length
$\ell$ encode the group elements.) Then $K=\sigma^{k}(G)$ and the restriction
of $\sigma$ to $K$ is an automorphism of $K$. Let $r$ be the length of the
orbit $\\{\rho_{(\sigma^{k}(g),1)^{t}}(1_{G}):t\in{\mathbb{Z}}_{\geq 0}\\}$
and put $M=\ker\sigma^{k}=\ker\sigma^{k_{0}}$. Then $K\cong G/M$, $K\cap
M=\\{1_{G}\\}$, and we have

$r=\min\\{t\in{\mathbb{Z}}_{>0}:\rho_{(\sigma^{k}(g),1)^{t}}(1_{G})=1_{G}\\}=\min\\{t\in{\mathbb{Z}}_{>0}:\rho_{(g,1)^{t}}(1_{G})\in
M\\}.$

Let $g^{\prime}=\rho_{(g,1)^{r}}(1_{G})$. Then
$\rho_{(g,1)^{rt}}(1_{G})=\rho_{(g^{\prime},r)^{t}}(1_{G})$. As $g^{\prime}\in
M=\ker\sigma^{k}$, for $rt\geq k$ we have $\sigma^{rt}(g^{\prime})=1_{G}$, and
hence
$\rho_{(g^{\prime},r)^{t+1}}(1_{G})=g^{\prime}\sigma^{r}(g^{\prime})\cdot\ldots\cdot\sigma^{rt}(g^{\prime})\sigma^{rt}(g^{\prime})=g^{\prime}\sigma^{r}(g^{\prime})\cdot\ldots\cdot\sigma^{r(t-1)}(g^{\prime})=\rho_{(g^{\prime},r)^{t}}(1_{G})$.
It follows that

$\rho_{(g,1)^{r(t+1)+s}}(1_{G})=\rho_{(g,1)^{rt+s}}(1_{G}),$ (2)

By equation (2), if the solution set of the SDLP in $K$ for $\sigma^{k}(g)$
and $\sigma^{k}(h)$ is $\\{s+rt:t\in{\mathbb{Z}}_{\geq 0}\\}$ for some $0\leq
s<r$, then the set of solutions of the SDLP in $G$ for $g$ and $h$ is either
the empty set, a singleton $\\{s+rt_{0}\\}$, or
$\\{s+rt:t\in{\mathbb{Z}}_{\geq t_{0}}\\}$, for some $t_{0}\leq\lceil
k_{0}/r\rceil\leq\lceil\log|G|\rceil$. Therefore, one can solve the
SDLP$(G,\sigma)$ for $g$ and $h$ by solving SDLP$(K,\sigma|_{K})$ for
$\sigma^{k}(g)$ and $\sigma^{k}(h)$, followed by an exhaustive search. This
gives the following theorem.

######  Theorem 1.

There is a classical polynomial time reduction from an instance of the group-
base case SDLP to an instance of the group case SDLP.

###  2.2 An easy reduction

In the group case, we have the following simple reduction based on brute
force. This will be useful when a power of the automorphism $\sigma$ with
polynomially small exponent has some desired property.

######  Proposition 2.

Assume that $\sigma$ is an automorphism of the group $G$. Then, for every
positive integer $k$, SDLP$(G,\sigma)$ can be reduced to $k$ instances of
SDLP$(G,\sigma^{k})$.

###### Proof.

We look for the smallest non-negative solution of the SDLP in the form $s+tk$
for $s=0,\ldots,k-1$. We have

$\begin{split}\rho_{(g,1)^{s+tk}}(1_{G})&=\rho_{(g,1)^{s}}(\rho_{(g,1)^{tk}}(1_{G}))\\\
&=\rho_{(g,1)^{s}}(\rho_{(g,1)^{k}}^{t}(1_{G})))\\\
&=\rho_{(g,1)^{s}}(\rho_{(\rho_{(g,1)^{k}}(1_{G}),k)}^{t}(1_{G}))),\end{split}$

whence $h=\rho_{(g,1)^{s+tk}}(1_{G})$ if and only if
$\rho_{(g,1)^{-s}}(h)=\rho_{(\rho_{(g,1)^{k}}(1_{G}),k)^{t}}(1_{G}))$. Let
$g^{\prime}=\rho_{(g,1)^{k}}(1_{G})$ and $h^{\prime}=\rho_{(g,1)^{-s}}(h)$.
Then, we need to solve the SDLP for $g^{\prime}$ and $h^{\prime}$, where we
replace $\sigma$ by $\sigma^{k}$. ∎

###  2.3 Recursion into quotient groups and subgroups

We will show that one can solve the SDLP$(G,\sigma)$, for a group $G$ and
$\sigma\in{\mathrm{Aut}}(G)$, by recursively solving an instance of the SDLP
in a quotient group and a subgroup of $G$. The main idea of recursion is
essentially the same as those used in the preceding subsections.

######  Theorem 3.

Let $G$ and $\overline{G}$ be black-box groups with unique labeling and let an
automorphism $\sigma$ of $G$ be given by a black box for evaluating the powers
$\sigma^{i}$ on codewords for group elements. Assume that we are given a
$\sigma$-invariant normal subgroup $M$ of $G$ and a group homomorphism
$\psi:G\rightarrow\overline{G}$ with kernel $M$. We assume that $\psi$ can be
evaluated efficiently and we have a black box for evaluating powers of the
automorphism $\overline{\sigma}$ of $\mbox{Im}(\psi)$ induced by $\sigma$.
Then SDLP$(G,\sigma)$ can be reduced to an instance of
SDLP$(\mbox{Im}(\psi),{\overline{\sigma}})$ and an instance of
SDLP$(M,\sigma_{|M}^{n_{0}})$ for some integer $n_{0}$.

###### Proof.

Every solution of SDLP$(G,\sigma)$ for $g$ and $h$ is a solution of the
SDLP$(\mbox{Im}(\psi),\overline{\sigma})$ for $\psi(g)$ and $\psi(h)$. If
there is no solution for the problem in $\mbox{Im}(\psi)$, then there is no
solution for the problem in $G$ either.

Otherwise, the set of solutions in $\mbox{Im}(\psi)$ is the residue class
$\\{t_{0}+n_{0}t\\}$ for some $0\leq t_{0}<n_{0}$, where
$n_{0}=|\\{\rho_{(\psi(g),1)^{t}}(1_{G}):t\in{\mathbb{Z}}\\}|$. Note that
$n_{0}$ is the smallest positive integer such that
$\rho_{(g,1)^{n_{0}}}(M)=M$. We have
$g^{\prime}=\rho_{(g,1)^{n_{0}}}(1_{G})\in M$ and also

$h^{\prime}=\rho_{(g,1)^{-t_{0}}}(h)=(\rho_{(g,1)^{-t_{0}}}\circ\rho_{(g,1)^{t_{0}+n_{0}t}})(1_{G})=\rho_{(g,1)^{n_{0}t}}(1_{G})\in
M.$

This gives that the solutions of SDLP$(G,\sigma)$ for $g$ and $h$ are exactly
the numbers of the form $t_{0}+n_{0}t$, where $t$ is a solution of
SDLP$(M,\sigma^{n_{0}})$ for $g^{\prime}$ and $h^{\prime}$. ∎

By considering the equivalent ”backward” version of the SDLP, that is, solving
$1_{G}=\rho_{(g,1)^{t}}(h)$, the recursion suggested by the proof of the
theorem can be interpreted as driving first to $M$ by solving the SDLP in
$\mbox{Im}(\psi)\cong G/M$ and then, inside $M$, driving further to the
identity element.

A general straightforward way to evaluate the induced automorphism (and its
powers) is based on computing an arbitrary element of the pre-image
$\psi^{-1}({\overline{x}})$ for each $x\in\mbox{Im}(\psi)$. This can be
facilitated by replacing $\overline{G}$ with the black-box group $H$ encoded
by pairs $(x,\psi(x))$, where $x$ is a code-word for an element of $G$. For
multiplication we use the oracle for $G$ and re-evaluate $\psi$ on the
product. For labeling, we use the labeling of $\overline{G}$. Of course, there
are many cases when this trick can be replaced by a simple direct method for
evaluating $\overline{\sigma}$. This holds in particular when
$\overline{G}={\mathbb{Z}}_{p}^{d}$ with the standard representation by column
vectors modulo $p$.

##  3 Quantum algorithms for the group case SDLP

In this section, we will prove the following main result of the paper.

######  Theorem 4.

Let $G$ be a group and $\sigma\in{\mathrm{Aut}}(G)$. We assume that $G$ is a
black-box group with a unique labeling of elements and we also have a black
box for computing $\sigma^{i}(g)$ ($i\in{\mathbb{Z}}{\geq 0},g\in G$). Suppose
that we are given a series $1=M_{0}<M_{1}<\ldots M_{k}=G$ of
$\sigma$-invariant normal subgroups $M_{i}\lhd G$ together with homomorphisms
$\psi_{i}:M_{i}\rightarrow{\overline{G}}_{i}$ ($i=1,\ldots,k$) with kernel
$M_{i-1}$ ($i=1,\ldots,k$). Let ${\overline{\sigma}}_{i}$ denote the
automorphism of $\mbox{Im}(\psi_{i})$ induced by $\sigma_{|M_{i}}$. Assume
further that, for each $i$, either

  1. (0)

$\mbox{Im}(\psi_{i})$ is of polynomial size; or

  2. (1)

${\overline{\sigma}}_{i}$ has polynomial order; or

  3. (2)

$\mbox{Im}(\psi_{i})$ is solvable;

  4. (3)

${\overline{G}}_{i}\leq\operatorname{GL}_{d_{i}}({\mathbb{F}}_{q_{i}})$ for
some positive integer $d_{i}$ and for some prime power $q_{i}$, moreover,
there exists a polynomially bounded integer $n_{i}$ and a matrix
$a_{i}\in\operatorname{GL}_{d_{i}}({\mathbb{F}}_{q_{i}})$ such that
${\overline{\sigma}}_{i}^{n_{i}}(x)=a_{i}^{-1}xa_{i}$ for every
$x\in\mbox{Im}(\psi_{i})$.

For items (0), (1) and (2), we assume that ${\overline{G}_{i}}$ is a black-box
group with unique labeling. For item (4), neither $n_{i}$ nor $a_{i}$ are
assumed to be given, their mere existence is sufficient. (By ”polynomial” we
mean polynomial in the maximum of the lengths of the bit strings used for
encoding and labeling the elements of the groups $G$ and ${\overline{G}}_{i}$
($i=1,\ldots,k$). Then SDLP$(G,\sigma)$ can be solved in quantum polynomial
time.

When $k=1$, condition of type (0) means that $G$ itself is of polynomial size,
that of type (1) means that $\sigma$ itself has polynomially small order, that
of type (2) means that $G$ is solvable. The standard descriptions of simple
groups of Lie type define them as factors of certain matrix groups over finite
field. The quotient is taken to be the center of the matrix group, so the
simple group has a representation as a matrix group by the conjugation action
on the matrix algebra spanned by the covering matrix group. Also, the outer
automorphism group of a finite simple group is of polynomial size. Therefore,
these groups are covered by conditions of type (3).

The algorithm for polynomially small groups is the straightforward trial and
error. In the first three subsections of this section we give efficient
algorithms for groups/automorphisms satisfying conditions (1), (2), or (3). In
the fourth subsection we show how to use these ingredients and Theorem 3 to
prove Theorem 4.

Note that the order of $\sigma$ can be computed in quantum polynomial time
using Shor’s period finding method applied to the functions
$t\mapsto\sigma^{t}(x_{i})$ for the generators $x_{i}$ of the group $G$ and
taking the least common multiple of these periods. The order can be factorized
using Shor’s factoring algorithm. The length of the orbit
$\\{\rho_{(g,1)^{t}}(1_{G}):t\in{\mathbb{Z}}\\}$ can be determined and
factorized in a similar way. Based on these observations, in the algorithms
below we assume that these numbers are already computed and factorized. The
solution set is either empty or the the residue class of an arbitrary solution
modulo the period. So it is sufficient to find any solution, e.g., the
smallest non-negative one.

###  3.1 The SDLP for small order automorphisms

In this subsection we prove the following result.

######  Proposition 5.

Let $G$ be a black-box group with unique labeling. Then SDLP$(G,\sigma)$ can
be solved by a quantum algorithm in time polynomial in the order of $\sigma$
and the length of the code-words together with the labels of the group
elements.

###### Proof.

By Proposition 2, it is sufficient to prove the case when $\sigma$ is trivial.
Then $\rho_{(g,1)}(x)=gx$, whence $\rho_{(g,1)^{t}}(1_{G})=g^{t}$ for every
integer $t$. Thus, solving the SDLP for $g$ and $h$ is the same as computing
the base-$g$ discrete logarithm of $h$, which can be accomplished by Shor’s
algorithm. ∎

###  3.2 The SDLP in solvable groups

In this part, we first present a quantum algorithm for the SDLP on elementary
abelian groups. We then show how Theorem 3 can be used to reduce the general
solvable case to instances of the elementary abelian case.

######  Theorem 6.

Let $G={\mathbb{Z}}_{p}^{d}$, the (additive) group of column vectors of length
$d$ over the integers modulo $p$, where $p$ is a prime number and let $\sigma$
be an automorphism of $G$, given as a $d$ by $d$ non-singular matrix. Then
SDLP$(G,\sigma)$ can be solved by a quantum algorithm in time polynomial in
$\log p$ and $d$.

###### Proof.

We consider $G$ as a vector space of dimension $d$ over the finite field
${\mathbb{Z}}_{p}$. We take a minimal nontrivial $\sigma$-invariant subspace
$M$ of $G$. This can be done, e.g., by a classical randomized method based on
computing the rational Jordan normal form of $\sigma$, see [Gie95]. Then the
factor space $M$ has no proper nontrivial $\sigma$-invariant subspace.
Iterating this in $G/M$, we eventually obtain a flag of subspaces
$(0)=M_{0}<M_{1}<\ldots<M_{k}=G$ such that there is no $\sigma$-invariant
subspace strictly between $M_{i-1}$ and $M_{i}$. Then, by Theorem 3, the
problem is reduced to the case when $G$ has no proper nontrivial
$\sigma$-invariant subspace. Suppose that we have an instance of that case.

If $1_{G}$ is an eigenvalue of $\sigma$ then $d=1$ and $\sigma$ is trivial. It
follows that $\rho_{(g,1)^{t}}(1_{G})=g^{t}$. Using the additive notation for
${\mathbb{Z}}/p{\mathbb{Z}}$, we need to solve $h=t\cdot g$. If $g=0$ and
$h=0$ then every integer is a solution, while if $g=0$ and $h\neq 0$ then
there is no solution. If $g\neq 0$ let $g^{\prime}$ stand for the
multiplicative inverse of $g$ in the field ${\mathbb{Z}}/p{\mathbb{Z}}$. Then
the solutions are $\\{hg^{\prime}+tp:t\in{\mathbb{Z}}\\}$. (Actually, the case
when $\sigma$ is trivial is a special case of the broader case already
discussed in Subsection 3.1.)

If $1_{G}$ is not an eigenvalue then we do the following. We compute the
matrix $B$ of $\sigma$ in the standard basis of
$({\mathbb{Z}}/p{\mathbb{Z}})^{d}$. Then, using again the additive notation,
we can write $\rho_{(g,1)^{t}}(1_{G})$ as

$\sum_{j=0}^{t-1}B^{j}g=(B^{t}-I)(B-I)^{-1}g.$

Let $\cal B$ be the matrix algebra generated by $B$. Then $\cal B$ is
isomorphic to the field ${\mathbb{F}}_{p^{d}}$ and the action of $B$ on
$({\mathbb{Z}}/p{\mathbb{Z}})^{d}$ can be identified with the multiplication
by the field element $B$ on the additive group of the field. Thus we can view
$g$ and $B$ as field elements. The solutions of the SDLP can be obtained by
solving a discrete log problem in this field by computing base-$B$ logarithm
of $I+(B-I)g^{-1}h$. This can be done by Shor’s quantum algorithm. ∎

The method for the elementary abelian case, in combination with the recursion
tool (Theorem 3), gives an efficient quantum algorithm for solving the SDLP in
solvable groups. More precisely, we obtain the following result.

######  Theorem 7.

Assume that $G$ is a solvable black-box group with unique labeling. Then
SDLP$(G,\sigma)$ can be solved in quantum polynomial time.

###### Proof.

Using the labeling, by [IMS01, Theorem 7] which is based on the Beals-Babai
algorithm [BB99], we can compute a composition series of $G$ with explicit
isomorphisms between the composition factors and additive groups
${\mathbb{Z}}_{p}$ for various primes $p$. In particular, we obtain a maximal
normal subgroup $N$ of $G$ together with a homomorphism
$\phi:G\mapsto{\mathbb{Z}}_{p}$. For any positive integer $j$, let
$N_{j}=\cap_{i=0}^{j-1}\sigma^{i}(N)$. Note that
$N_{j+1}=N_{j}\cap\sigma^{j}(N)$ and if $N_{j+1}=N_{j}$ then
$N_{j^{\prime}}=N_{j}$ for any integer $j^{\prime}>j$ and $N_{j}$ is
$\sigma$-invariant. This equality happens for an integer $j$ bounded by the
length $\ell$ of code-words for the group elements. We compute the map
$\psi:G\mapsto{\mathbb{Z}}_{p}^{\ell}$ defined as
$x\mapsto(\phi(x),\phi^{\sigma}(x),\ldots,\phi^{\sigma^{\ell-1}}(x))^{T}$.
Based on the above discussion, the kernel $M$ of $\psi$ is $\sigma$-invariant.
The image $\mbox{Im}(\psi)$ is a subspace $V$ of ${\mathbb{Z}}_{p}^{\ell}$.
Compute a basis for $V$ by taking a maximal linearly independent set of the
images of the generators for $G$ under the map $\psi$ and using them replace
$\psi$ with the composition of $\psi$ with the transpose of the matrix whose
columns are the bases elements for $V$. This new map, denoted again by $\psi$,
is a surjective homomorphism from $G$ to ${\mathbb{Z}}_{p}^{d}$ with kernel
$M$. Then, by Theorem 3, after solving the SDLP in the $\psi$-image
${\mathbb{Z}}_{p}^{d}$, SDLP$(G,\sigma)$ gets reduced to
SDLP$(M,\sigma^{\prime})$ where $\sigma^{\prime}$ is the restriction of a
power of $\sigma$ to $M$. ∎

###  3.3 The SDLP in matrix groups with an inner automorphism

In this part we prove the following result.

######  Theorem 8.

Let $G$ be a subgroup of $\operatorname{GL}_{d}({\mathbb{F}}_{q})$ where $d$
is a positive integer and $q$ is a power of a prime. Assume that $G$ is given
by a list of matrices that generate $G$ and that the automorphism $\sigma$ is
given on the generators. Suppose that $\sigma$ coincides with the conjugation
action of a matrix $a\in\operatorname{GL}_{d}({\mathbb{F}}_{q})$. Then
SDLP$(G,\sigma)$ can be solved by a quantum algorithm in time polynomial in
$d$ and $\log q$.

The matrix $a$ that implements the automorphism $\sigma$ does not need to be
given, such a matrix is computed by the algorithm. (It is unique up to the
centralizer of $G$.) Note that conjugation by $a$ is an inner automorphism of
the full matrix group $\operatorname{GL}_{d}({\mathbb{F}}_{q})$ (or just of
the matrix group generated by $G$ and $a$), justifying the title of the
subsection.

###### Proof.

We assume that $q\geq 2d$. (If not, we consider $G$ as a matrix group over an
extension field of ${\mathbb{F}}_{q}$ having at least $2d$ elements.) To find
a matrix $a$ with the desired property, we take the linear space of matrices
$y$ such that $yx_{i}=\sigma(x_{i})y$ for the generators $x_{i}$ of $G$, and
choose a random element $a$ of this space. Since $q\geq 2d$, by the Schwartz-
Zippel lemma [Sch79, Zip79], a random element of this matrix space will be
with high probability invertible as it contains at least one by the assumption
of the theorem. Conjugation by $a$ extends $\sigma$ to a linear automorphism
of the full matrix algebra $\mathcal{B}=\mbox{M}_{d}({\mathbb{F}}_{q})$ of the
$d$ by $d$ matrices. We denote this extension also by $\sigma$.

We have $\rho_{(g,1)}(x)=g\sigma(x)$, thus $\rho_{(g,1)}=\mu_{g}\circ\sigma$,
where $\mu_{g}$ denotes the multiplication by $g$ from the left. The map
$\mu_{g}$ can also be extended to an invertible linear transformation of $\cal
B$. Therefore the composition $\rho_{(g,1)}$ has an invertible linear
extension $\Phi$ to $\cal B$. Also, solving $h=\rho_{(g,1)}^{t}(1_{G})$ is
equivalent to solving $h=\Phi^{t}I_{d}$. The latter is an instance of the well
known Orbit Problem introduced by Harrison in [Har69]. It is the following
orbit membership problem. Given vectors $a,b$ of a finite dimensional vector
space $V$ over the field ${\mathbb{F}}$ and a linear transformation
$\Phi\in\operatorname{End}_{{\mathbb{F}}}(V)$, find $t\in{\mathbb{Z}}_{\geq
0}$, if there exists, such that $b=\Phi^{t}a$.

Kannan and Lipton in [KL86] gave a polynomial time solution of the Orbit
Problem for the case when ${\mathbb{F}}$ is the field of rationals. Here we
need to solve the finite field case. Kannan and Lipton gave a construction to
reduce the Orbit Problem to the so-called Matrix Power Problem, which is the
following. Given square matrices $A$ and $B$ over a field ${\mathbb{F}}$,
solve $B=A^{t}$, see [KL86, Theorem 1]. For completeness we briefly recall (a
version of) their construction. We compute the subspace $W$ spanned by
$\Phi^{t}a$ ($t=0,1,\ldots$). This can be done by computing the vectors
$a,\Phi a,\ldots,\Phi^{j-1}a$ until $\Phi^{j}a$ becomes linearly dependent of
the previous vectors. Then $W$ is the subspace with basis $a,\Phi
a,\ldots,\Phi^{j-1}a$. If $b\not\in W$, then the problem has no solution.
Otherwise $\Phi^{t}b\in W$ for every $t$. Write the vectors $\Phi^{i}a$ and
$\Phi^{i}b$ ($i=0,\ldots,j-1$) as column vectors in terms of a basis of $W$.
Let $A$ be the matrix of the restriction of $\Phi$ to $W$ in the same basis
and let $C$ resp. $D$ be the $j$ by $j$ matrices whose columns are $a,\Phi
a,\ldots,\Phi^{j-1}a$ and $b,\Phi b,\ldots,\Phi^{j-1}b$, respectively. Then
$b=A^{t}a$ if and only if $D=A^{t}C$. Let $B=DC^{-1}$ and we need to solve
$B=A^{t}$. If $\Phi$ is invertible then so is $A$.

The invertible case of the matrix power problem over a finite field can be
solved by Shor’s quantum discrete log algorithm. ∎

We remark that, using the Jordan blocks of $A$, one could classically reduce
the problem to the instances of the discrete logarithm problem in the
multiplicative group of extensions of ${\mathbb{F}}$. Also, in practice it
might be worth replacing $\cal B$ with the matrix algebra spanned by the
elements of $G$.

Proposition 2 gives the following extension.

######  Corollary 9.

Let $G$ be as in Theorem 8. Let $\sigma$ be an automorphism of $G$. Let $K$ be
a positive integer. We assume that for the divisors $k\leq K$ of the order of
$\sigma$, the action of $\sigma^{k}$ on the generators for $G$ is also given
and that among those divisors $k$, $\sigma^{k}$ coincides with the conjugation
action of a matrix. Then SDLP$(G,\sigma)$ can be solved by a quantum algorithm
in time polynomial in $K,d$ and $\log q$.

###  3.4 Putting things together

Our recursion tool (Theorem 3) can assemble the results proved in the
preceding subsections for various special cases of the SDLP to obtain Theorem
4.

###### Proof of Theorem 4.

Assume that we have the chain of subgroups $M_{i}$ and homomorphisms
$\psi_{i}$ ($i=0,\ldots,k)$ with properties as in the statement of the
theorem. For $i=k$ to $1$, using Theorem 3, by solving the SDLP in the
$\phi_{i}$-image of $M_{i}$ we reduce the problem to an instance in $M_{i-1}$.
In the small size case (0), we use brute force. When ${\overline{\sigma}}_{i}$
is of small order (case (1)) or when $\mbox{Im}(\psi_{i})$ is solvable (case
(2)), we use Proposition 5 or Theorem 7, respectively. In order to facilitate
using the oracle for evaluating the powers of $\sigma$ to evaluate those of
${\overline{\sigma}}_{i}$, we use the pairs $(x,\psi_{i}(x))$ to encode the
elements of $\mbox{Im}(\psi_{i})$, while as labeling we use the labeling for
${\overline{G}_{i}}$. In the matrix group case (4), we use the natural
encoding by matrices for the image. We compute the order $o_{i}$ of
${\overline{\sigma}}_{i}$ using the factorization of the order of $\sigma$ and
compute $\sigma^{t}$ for the smallest few divisors of $o_{i}$ and apply the
method of Corollary 9. ∎

#### Acknowledgments.

The research of the second author was supported by the Hungarian Ministry of
Innovation and Technology NRDI Office within the framework of the Artificial
Intelligence National Laboratory Program.

## References

  * [BB99] László Babai and Robert Beals.  A polynomial-time theory of black box groups i.  London Mathematical Society Lecture Note Series, pages 30–64, 1999\.
  * [BBS09] László Babai, Robert Beals, and Ákos Seress.  Polynomial-time theory of matrix groups.  In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, STOC ’09, page 55–64, New York, NY, USA, 2009. Association for Computing Machinery.
  * [BKPS22] Christopher Battarbee, Delaram Kahrobaei, Ludovic Perret, and Siamak F Shahandashti.  A subexponential quantum algorithm for the semidirect discrete logarithm problem.  In NIST Fourth PQC Standardization Conference, 2022.
  * [BKPS23] Christopher Battarbee, Delaram Kahrobaei, Ludovic Perret, and Siamak F. Shahandashti.  Spdh-sign: Towards efficient, post-quantum group-based signatures.  In Thomas Johansson and Daniel Smith-Tone, editors, Post-Quantum Cryptography, pages 113–138, Cham, 2023. Springer Nature Switzerland.
  * [BKS22] Christopher Battarbee, Delaram Kahrobaei, and Siamak F Shahandashti.  Semidirect product key exchange: the state of play.  arXiv preprint arXiv:2202.05178, 2022.
  * [BS84] László Babai and Endre Szemerédi.  On the complexity of matrix group problems i.  In 25th Annual Symposium onFoundations of Computer Science, 1984., pages 229–240. IEEE, 1984.
  * [CI14] Andrew M Childs and Gábor Ivanyos.  Quantum computation of discrete logarithms in semigroups.  Journal of Mathematical Cryptology, 8(4):405–416, 2014.
  * [CLM+18] Wouter Castryck, Tanja Lange, Chloe Martindale, Lorenz Panny, and Joost Renes.  Csidh: an efficient post-quantum commutative group action.  In Advances in Cryptology–ASIACRYPT 2018: 24th International Conference on the Theory and Application of Cryptology and Information Security, Brisbane, QLD, Australia, December 2–6, 2018, Proceedings, Part III 24, pages 395–427. Springer, 2018.
  * [Cou06] Jean-Marc Couveignes.  Hard homogeneous spaces.  Cryptology ePrint Archive, 2006.
  * [Gie95] Mark Giesbrecht.  Nearly optimal algorithms for canonical matrix forms.  SIAM Journal on Computing, 24(5):948–969, 1995.
  * [Har69] Michael A Harrison.  Lectures on linear sequential machines.  Academic Press New York, 1969.
  * [HKKS13] Maggie Habeeb, Delaram Kahrobaei, Charalambos Koupparis, and Vladimir Shpilrain.  Public key exchange using semidirect product of (semi) groups.  In Applied Cryptography and Network Security: 11th International Conference, ACNS 2013, Banff, AB, Canada, June 25-28, 2013. Proceedings 11, pages 475–486. Springer, 2013.
  * [IMS01] Gábor Ivanyos, Frédéric Magniez, and Miklos Santha.  Efficient quantum algorithms for some instances of the non-abelian hidden subgroup problem.  In Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures, pages 263–270, 2001.
  * [KL86] Ravindran Kannan and Richard J Lipton.  Polynomial-time algorithm for the orbit problem.  Journal of the ACM (JACM), 33(4):808–821, 1986.
  * [Kup05] Greg Kuperberg.  A subexponential-time quantum algorithm for the dihedral hidden subgroup problem.  SIAM Journal on Computing, 35(1):170–188, 2005.
  * [Sch79] Jacob T. Schwartz.  Probabilistic algorithms for verification of polynomial identities.  In Edward W. Ng, editor, Symbolic and Algebraic Computation, volume 72 of Lecture Notes in Computer Science, pages 200–215. Springer Berlin Heidelberg, 1979.
  * [Sho94] Peter W Shor.  Algorithms for quantum computation: discrete logarithms and factoring.  In Proceedings 35th annual symposium on foundations of computer science, pages 124–134. Ieee, 1994.
  * [Zip79] Richard Zippel.  Probabilistic algorithms for sparse polynomials.  In Edward W. Ng, editor, Symbolic and Algebraic Computation, volume 72 of LNCS, pages 216–226. Springer, 1979.

## Appendix: the matrix group case in odd characteristic

This part is devoted to a sketch of a proof of the following.

######  Corollary 10.

Let $\psi:K\rightarrow M_{d}({\mathbb{F}}_{q})$ be a representation of the
black-box group $K$ with our without a labeling. Assume that the automorphism
$\sigma$ is given by a black box to evaluate its powers on elements of $K$ and
that the kernel of $\psi$ is $\sigma$-invariant (e.g., when $\psi$ is
faithful). Then, $SDLP(\mbox{Im}(\psi),\overline{\sigma})$ can be solved in
quantum polynomial time.

###### Proof (sketch).

We encode the elements of $G=\mbox{Im}(\psi)$ by pairs $(x,\psi(x))$ and
labeling $\psi(x)$ so that we can evaluate powers of $\overline{\sigma}$ on
elements of the matrix group $G$. We use the notation $\sigma$ for
$\overline{\sigma}$. Below we outline how the result of the polynomial time
algorithm of Babai, Beals and Seress [BBS09] for computing the structure of
matrix groups over finite fields can be used to obtain a series of normal
subgroups together with representations of the factors making Theorem 4
applicable to these matrix groups.

Every finite group $G$ has a unique largest solvable normal subgroup, called
the solvable radical of $G$. It is denoted by $\operatorname{Rad}(G)$. The
factor group ${\overline{G}}=G/\operatorname{Rad}(G)$ is trivial if $G$ itself
is solvable. Even if $\overline{G}$ is a non-trivial group, it has no
nontrivial abelian subnormal subgroups. (Normal subgroups of a group are
subnormal, and, recursively, normal subgroups of subnormal subgroups are also
subnormal.) It follows that the minimal subnormal subgroups of $\overline{G}$
are non-commutative simple groups. They pairwise commute and the subgroup
$\operatorname{Soc}({\overline{G}})$ generated by them (called the socle of
$\overline{G}$) is the direct product of these simple groups. (It follows that
there are at most $\log\overline{G}$ simple constituents of
$\operatorname{Soc}({\overline{G}})$.) The full pre-image of
$\operatorname{Soc}({\overline{G}})$ at the projection
$G\rightarrow\overline{G}$ is denoted by $\operatorname{Soc}^{*}(G)$. The
subgroups $\operatorname{Rad}(G)$ and $\operatorname{Soc}^{*}(G)$ are
characteristic subgroups of $G$. The group $G$, by conjugation, acts as a
permutation group on the minimal subnormal subgroups of $\overline{G}$. The
kernel $\operatorname{Pker}(G)$ of this permutation representation, called the
permutation kernel, is a further characteristic subgroup. There are the
following inclusions between the subgroups introduced above.

$1\leq\operatorname{Rad}(G)\leq\operatorname{Soc}^{*}(G)\leq\operatorname{Pker}(G)\leq
G.$

$\operatorname{Pker}(G)$ acts by conjugation as an automorphism group on each
simple component of $\operatorname{Soc}(\overline{G})$. As the outer
automorphism group of any finite simple group is solvable, the factor group
$\operatorname{Pker}(G)/\operatorname{Soc}^{*}(G)$ is solvable. The algorithm
of Babai, Beals and Seress [BBS09] computes in classical randomized polynomial
time (generators for) the three subgroups above. They also compute a
permutation representation of $G$ with kernel $\operatorname{Pker}(G)$ (this
is actually the conjugation action of $G$ on the simple components of
$\operatorname{Soc}({\overline{G}})$); a (usually highly intransitive)
permutation representation of $\operatorname{Pker}(G)$ with kernel
$\operatorname{Soc}^{*}(G)$; and, most importantly, for each of the simple
components of $\operatorname{Soc}({\overline{G}})$, a sequence of elements of
$G$ that generate the component modulo $\operatorname{Rad}(G)$ together with
the images of these under an isomorphism with a standard version of the a
simple group. (The generators for each component $S$ are actually generators
for a perfect subgroup $S^{*}$ of $\operatorname{Soc}^{*}(G)$ such that
$(S^{*}/\operatorname{Rad}G)$ is the pre-image of $S$ by the projection map
$G\rightarrow G/\operatorname{Rad}(G)$.)

We compute refinement of the sequence
$1\leq\operatorname{Rad}(G)\leq\operatorname{Soc}^{*}(G)\leq\operatorname{Pker}(G)\leq
G$ between $\operatorname{Rad}(G)$ and $\operatorname{Soc}^{*}(G)$. To this
end we notice that $\sigma$ also permutes the simple components of
$\operatorname{Soc}{\overline{G}}$. We take a $\sigma$-orbit of a single
simple component $S$ and we compute
$S^{**}=\prod_{T}T^{*}\operatorname{Rad}(G)$, where the product is taken over
the $\sigma$-orbit of $S$. Let $r$ be the length of the orbit. Then
$\sigma^{r}$ acts as an automorphism on each member of the orbit. As the outer
automorphism group of a finite simple group is of size bounded by a polynomial
of the logarithm of the group size, we obtain that a polynomially small power
of $\sigma$ acts as an inner automorphism of $S^{**}/\operatorname{Rad}(G)$.
If $S$ is sporadic, we use the regular representation of $S$. If $S$ is of Lie
type, we take the isomorphism between $S$ and the standard copy of it computed
by the algorithm of [BBS09]. It realizes $S$ as the quotient group of a matrix
group by its center. We obtain a matrix representation of $S$ by taking the
conjugation action on the matrix algebra spanned by the elements of this
covering group. We do the same for each $T$ from the orbit (actually, these
are isomorphic to $S$, so the construction made for $S$ can be re-used.)
Finally we obtain a matrix representation of $S^{**}$ with kernel
$\operatorname{Rad}(G)$ on the direct sum of these representations. Then we
proceed with another orbit, construct the representation of the product of the
orbit members and add to $S^{**}$. This way we obtain a chain of
$\sigma$-invariant normal subgroups between $\operatorname{Rad}(G)$ and
$\operatorname{Soc}^{*}(G)$ together with the matrix representations of the
factors so that case (4) of Theorem 4 is applicable to them. For
$G/\operatorname{Pker}(G)$, we use the permutation representation which can be
naturally extended to a matrix representation. As $\sigma$ also permutes the
simple components, the induced automorphism will be conjugation by a
permutation, so case (4) is again applicable. For
$\operatorname{Pker}(G)/\operatorname{Soc}^{*}{G}$, we use the matrix
representation as a labeling and, by solvability, case (3) is applicable.
Finally, in $\operatorname{Rad}(G)$, again case (3) applies. ∎


distribution $P(X,Y)$ in the “Bow” diagram of Fig. 1(d). We collect $N=10^{3}$
observational samples $\bar{\bm{v}}=\\{x^{(n)},y^{(n)}\\}_{n=1}^{N}$ from an
SCM compatible with Fig. 1(d). Detailed parametrization of the SCM is defined
as follows:

$\begin{split}&U\sim\texttt{Normal}(0,1),\\\
&X\sim\texttt{Binomial}(1,\rho_{X}),\\\ &E\sim\texttt{Logistic}(0,1),\\\
&Y\leftarrow\mathds{1}_{X-U+E+0.1>0},\end{split}$ (96)

where probabilities $\rho_{X}$ are given by

$\displaystyle\rho_{X}=\frac{1}{1+\exp(U)}.$

Each observation $\left(x^{(n)},y^{(n)}\right)$ is an independent draw from
the observational distribution $P(X,Y)$. In this experiment, we set
hyperparameters $\alpha_{U}=d_{U}=8$.

#### Experiment 3: IST

International Stroke Trials (IST) was a large, randomized, open trial of up to
$14$ days of antithrombotic therapy after stroke onset (Carolei et al. 1997).
The aim was to provide reliable evidence on the efficacy of aspirin and of
heparin. The dataset is released under Open Data Commons Attribution License
(ODC-By). In particular, the treatment $X$ is a pair $(i,j)$ where $i=0$
stands for no aspirin allocation, $1$ otherwise; $j=0$ stands for no heparin
allocation, $1$ for median-dosage, and $2$ for high-dosage. The primary
outcome $Y\in\\{0,\dots,3\\}$ is the health of the patient $6$ months after
the treatment, where $0$ stands for death, $1$ for being dependent on the
family, $2$ for the partial recovery, and $3$ for the full recovery.

To emulate the presence of unobserved confounding, we filter the experimental
data with selection rules $f_{X}^{(Z)}$, $Z\in\\{0,\dots,9\\}$, following a
procedure in (Zhang and Bareinboim 2021). More specifically, we are provided
with a collection of IST samples $\\{X^{(n)},Y^{(n)},U_{2}^{(n)}\\}_{n=1}^{N}$
where $U_{2}^{(n)}$ is the age of the $n$-th patient. For each data point
$\left(X^{(n)},Y^{(n)},U_{2}^{(n)}\right)$, we introduce an instrumental
variable $Z^{(n)}\in\\{0,\dots,9\\}$. Values of the instrumental variable
$Z^{(n)}$ for the $n$-th patient are decided by

$\displaystyle Z^{(n)}=\lfloor 10\times U_{1}\rfloor,\text{ where
}U^{(n)}_{1}\sim\texttt{Unif}(0,1).$ (97)

We then check if $X^{(n)}$ satisfies the following condition

$\displaystyle X^{(n)}=\lfloor 6\times\rho_{X}\rfloor,$ (98)

where parameter $\rho_{X}$ is given by

$\displaystyle\rho_{X}=\frac{1}{1+\exp\left(-U^{(n)}_{2}/100-Z^{(n)}/10\right)}$

If the above condition is satisfied, we keep the data point
$\left(X^{(n)},Y^{(n)},Z^{(n)},U_{1}^{(n)},U_{2}^{(n)}\right)$ in the dataset;
otherwise, the data point is dropped. After this data selection process is
complete, we hide columns of variables $U_{1}^{(n)},U_{2}^{(n)}$. Doing so
allows us to obtain $N=1\times 10^{3}$ synthetic observational samples
$\bar{\bm{V}}=\left\\{X^{(n)},Y^{(n)},Z^{(n)}\right\\}_{n=1}^{N}$ that are
compatible with the “IV”’ diagram of Fig. 1(a).

In this experiment, we set hyperparameters $\alpha_{U_{1}}=10$ and
$\alpha_{U_{2}}=1$. As a baseline, we estimate the treatment effect
$E[Y_{x=(1,0)}]=1.3418$ for only assigning aspirin $X=(1,0)$ from randomized
trial data containing $1.9285\times 10^{4}$ subjects.

ZXWYU1U2U3 (a) Napkin

ZXYU1U2U1U2 (b) Double Bow

XZYU1U2 (c) M+BD Graph

ZWXYU1U2U3U1U2U3 (d) Triple Bow

Figure 8: Causal diagrams for Experiment 5 (8(a)), Experiment 6 (8(b)),
Experiment 7 (8(c)), and Experiment 8 (8(d)). Each diagram contains (not
exclusively) a treatment $X$, an outcome $Y$, ancestors $Z,W$, and exogenous
variables $U_{i}$, $i=1,2,3$.

#### Experiment 4: Obs. + Exp.

We study the problem of evaluating counterfactual probabilities
$P(z,x_{z^{\prime}},y_{x^{\prime}})$ from the combination of the observational
distribution $P(X,Y,Z)$ and interventional distributions $P(X_{z},Y_{z})$,
$\forall z\in\Omega_{Z}$, in the causal diagram of Fig. 1(b). We collect
$N=10^{3}$ samples $\bar{\bm{v}}=\\{x^{(n)},y^{(n)},z^{(n)}\\}_{n=1}^{N}$ from
an SCM compatible with Fig. 1(b), which we define as follows:

$\begin{split}&U_{1}\sim\texttt{Unif}(0,1),\\\
&U_{2}\sim\texttt{Unif}(0,1),\\\ &Z\leftarrow\min\left\\{\lfloor 15\cdot
U_{1}\rfloor,9\right\\},\\\ &X\sim\texttt{Binomial}(9,\rho_{X}),\\\
&Y\sim\texttt{Binomial}(9,\rho_{Y}),\end{split}$ (99)

where for any real $\alpha\in\mathbb{R}$, the operator $\lfloor\alpha\rfloor$
denotes the largest integer $n\in\mathbb{Z}$ smaller than $\alpha$, i.e.,
$\lfloor\alpha\rfloor=\min\\{n\in\mathbb{Z}\mid n\geq\alpha\\}$; probabilities
$\rho_{X},\rho_{Y}$ are given by

$\displaystyle\rho_{X}=\frac{1}{1+\exp(-Z-U_{2})},$
$\displaystyle\rho_{Y}=\frac{1}{1+\exp(X/10-U_{1}\cdot U_{2})}.$

Each sample $\left(x^{(n)},y^{(n)},z^{(n)}\right)$ is an independent draw from
the observational distribution $P(X,Y,Z)$ or an interventional distribution
$P(X_{z},Y_{z})$. To obtain a sample from $P(X_{z},Y_{z})$, we pick a constant
$z\in\Omega_{Z}$ uniformly at random, perform intervention $\text{do}(Z=z)$ in
the SCM described in Eq. 99 and observed subsequent outcomes. In this
experiment, we set hyperparameters $\alpha_{U_{1}}=10$ and
$\alpha_{U_{2}}=10$.

### C.1 Additional Simulation Results

We also evaluate our algorithms on various simulated SCM instances in other
more involved causal diagrams. Overall, we found that simulation results match
our findings in the main manuscript. For identifiable settings (Experiment 5),
our algorithms are able to recover the actual, unknown counterfactual
probabilities. For non-identifiable settings, our algorithm consistently
dominates existing bounding strategies: it achieves sharp bounds if closed-
formed solutions exist (Experiments 6); otherwise, it improves over state-of-
art bounds (Experiment 7). Finally, for other more challenging non-
identifiable settings where existing strategies do not apply (Experiments 8),
our algorithm is able to achieve effective bounds over unknown counterfactual
probabilities.

In all experiments, we evaluate our proposed strategy using credible intervals
(ci). In particular, we draw at least $4\times 10^{3}$ samples from the
posterior distribution $P\left(\theta_{\text{ctf}}\mid\bar{\bm{v}}\right)$
over the target counterfactual. This allows us to compute $100\%$ credible
interval over $\theta_{\text{ctf}}$ within error $\epsilon=0.05$, with
probability at least $1-\delta=0.95$. As the baseline, we also include the
actual counterfactual probability, labeled as $\theta^{*}$.

#### Experiment 5: Napkin Graph

Consider the “Napkin” graph in Fig. 8(a) where $X,Y,Z,W$ are binary variables
in $\\{0,1\\}$; $U_{1},U_{2},U_{3}$ take values in real $\mathbb{R}$. The
identifiability of interventional probabilities $P(y_{x})$ from the
observational distribution $P(X,Y,Z,W)$ could be derived by iteratively
applying inference rules of “do-calculus” (Pearl 2000, Thm. 4.3.1). We collect
$N=10^{4}$ observational samples
$\bar{\bm{v}}=\\{x^{(n)},y^{(n)},z^{(n)},w^{(n)}\\}_{n=1}^{N}$ from an SCM
compatible with Fig. 8(a), defined as follows:

$\begin{split}&U_{i}\sim\texttt{Normal}(0,1),\;\;i=1,2,3,\\\
&W\sim\texttt{Binomial}(1,\rho_{W}),\\\
&Z\sim\texttt{Binomial}(1,\rho_{Z}),\\\
&X\sim\texttt{Binomial}(1,\rho_{X}),\\\
&Y\sim\texttt{Binomial}(1,\rho_{Y}),\end{split}$ (100)

where probabilities $\rho_{W},\rho_{Z},\rho_{X},\rho_{Y}$ are given by:

$\displaystyle\rho_{W}=\frac{1}{1+\exp(U_{1}-U_{2})},$
$\displaystyle\rho_{Z}=\frac{1}{1+\exp(W-U_{3})},$
$\displaystyle\rho_{X}=\frac{1}{1+\exp(-Z-U_{1})},$
$\displaystyle\rho_{Y}=\frac{1}{1+\exp(X-U_{2}-0.5)}.$

Each observation $\left(x^{(n)},y^{(n)},z^{(n)},w^{(n)}\right)$ is an
independent draw from the observational distribution $P(X,Y,Z,W)$. In this
experiment, we set hyperparameters $\alpha_{U_{1}}=d_{U_{1}}=32$,
$\alpha_{U_{2}}=d_{U_{1}}=32$, and $\alpha_{U_{3}}=d_{U_{3}}=4$. Fig. 9(a)
shows a histogram containing samples drawn from the posterior distribution of
$\left(P(Y_{x=0}=1)\mid\bar{\bm{v}}\right)$. Our analysis reveals that these
samples converges to the actual interventional probability
$P(Y_{x=0}=1)=0.6098$, which confirms the identifiability of $P(y_{x})$ in the
napkin graph.

(a) Napkin

(b) Double bow

(c) M+BD Graph

(d) Triple bow

Figure 9: Histogram plots for samples drawn from the posterior distribution
over target counterfactual probabilities. For all plots (9(a) \- 9(d)), ci
represents our proposed algorithms; bp stands for Gibbs samplers using the
representation of canonical partitions (Balke and Pearl 1994); $\theta^{*}$ is
the actual counterfactual probability; opt is the optimal asymptotic bounds
(if exists); nb stands for the natural bounds (Manski 1990).

#### Experiment 6: Double Bow

Consider the “Double Bow” diagram in Fig. 8(b) where $X,Y,Z\in\\{0,1\\}$ and
$U_{1},U_{2}\in\mathbb{R}$. We study the problem of evaluating interventional
probabilities $P(y_{x})$ from the observational distribution $P(X,Y,Z)$. We
collect $N=10^{3}$ observational samples
$\bar{\bm{v}}=\\{x^{(n)},y^{(n)},z^{(n)}\\}_{n=1}^{N}$ from an SCM compatible
with Fig. 1(b). The detailed parametrization of the SCM is defined as follows:

$\begin{split}&U_{i}\sim\texttt{Normal}(0,1),\;\;i=1,2,\\\
&Z\sim\texttt{Binomial}(1,\rho_{Z}),\\\
&X\sim\texttt{Binomial}(1,\rho_{X}),\\\
&Y\sim\texttt{Binomial}(1,\rho_{Y}),\end{split}$ (101)

where probabilities $\rho_{Z},\rho_{X},\rho_{Y}$ are given by:

$\displaystyle\rho_{Z}=\frac{1}{1+\exp(-U_{1})},$
$\displaystyle\rho_{X}=\frac{1}{1+\exp(-Z-U_{1}-U_{2})},$
$\displaystyle\rho_{Y}=\frac{1}{1+\exp(X-U_{2}+0.5)}.$

Each observation $\left(x^{(n)},y^{(n)},z^{(n)}\right)$ is an independent draw
from the observational distribution $P(X,Y,Z)$.

(Balke and Pearl 1997) introduced a closed-form bound over $P(y_{x})$ from the
observational distribution $P(X,Y,Z)$ for the “IV” diagram in Fig. 1(a) with
binary $X,Y,Z\in\\{0,1\\}$. It is verifiable that such a bound is also
applicable in Fig. 9(b) with binary endogenous domains, and is provably
optimal (labeled as opt). To obtain a $100\%$ credible intervals, we apply the
collapsed Gibbs sampler with hyperparameters $\alpha_{U_{1}}=d_{U_{1}}=32$ and
$\alpha_{U_{2}}=d_{U_{1}}=32$. Fig. 9(b) shows samples drawn from the
posterior distribution of $\left(P(Y_{x=0}=1)\mid\bar{\bm{v}}\right)$. The
analysis reveals that our algorithm derives a valid bound over the actual
probability $P(Y_{x=0}=1)=0.3954$; the $100\%$ credible interval converges to
the optimal IV bound $l=0.1980,r=0.6258$.

#### Experiment 7: M+BD Graph

Consider the “M+BD” graph in Fig. 8(c) where $X,Y,Z\in\\{0,1\\}$ and
$U_{1},U_{2}\in\mathbb{R}$. In this case, interventional probabilities
$P(y_{x})$ are non-identifiable from the observational distribution $P(X,Y,Z)$
due to the presence of the collider path $X\leftarrow U_{1}\rightarrow
Z\leftarrow U_{2}\rightarrow Y$. We collect $N=10^{3}$ observational samples
$\bar{\bm{v}}=\\{x^{(n)},y^{(n)},z^{(n)}\\}_{n=1}^{N}$ from an SCM compatible
with Fig. 8(c). The detailed parametrization of the SCM is provided as
follows:

$\begin{split}&U_{i}\sim\texttt{Normal}(0,1),\;\;i=1,2,\\\
&Z\sim\texttt{Binomial}(1,\rho_{Z}),\\\
&X\sim\texttt{Binomial}(1,\rho_{X}),\\\
&Y\sim\texttt{Binomial}(1,\rho_{Y}),\end{split}$ (102)

where probabilities $\rho_{Z},\rho_{X},\rho_{Y}$ are given by:

$\displaystyle\rho_{Z}=\frac{1}{1+\exp(-U_{1})},$
$\displaystyle\rho_{X}=\frac{1}{1+\exp(-Z-U_{1}-U_{2})},$
$\displaystyle\rho_{Y}=\frac{1}{1+\exp(X-Z-U_{2})}.$

Each observation $\left(x^{(n)},y^{(n)},z^{(n)}\right)$ is an independent draw
from the observational distribution $P(X,Y,Z)$.

In this experiment, we set hyperparameters $\alpha_{U_{1}}=d_{U_{1}}=32$ and
$\alpha_{U_{2}}=d_{U_{1}}=32$. Fig. 9(c) shows samples drawn from the
posterior distribution of $\left(P(Y_{x=0}=1)\mid\bar{\bm{v}}\right)$. As a
baseline, we also include the natural bounds introduced in (Robins 1989;
Manski 1990) (nb). The analysis reveals that all algorithms achieve bounds
that contain the actual, target causal effect $P(Y_{x=0}=1)=0.5910$. Our
algorithm obtains a $100\%$ credible interval
$l_{\textit{ci}}=0.4884,r_{\textit{ci}}=0.6519$, which improves over the
existing bounding strategy ($l_{\textit{nb}}=0.2230,r_{\textit{nb}}=0.8296$).

(a) Flat

(b) Skewed

(c) Flat

(d) Skewed

Figure 10: Prior distributions for (10(a), 10(b)) Experiment 9 and (10(c),
10(d)) Experiment 10.

(a) $N=10$

(b) $N=10^{2}$

(c) $N=10^{3}$

(d) $N=10^{4}$

(e) $N=10$

(f) $N=10^{2}$

(g) $N=10^{3}$

(h) $N=10^{4}$

Figure 11: Histogram plots for samples drawn from the posterior distribution
over probability $P(Y_{x=0}=0)$ in “Frontdoor” graph of Fig. 1(c) using two
priors. (11(a) \- 11(d)) shows the posteriors using the flat prior and
observational data of size $N=10,10^{2},10^{3}$ and $10^{4}$ respectively;
(11(e) \- 11(h)) shows the posetriors using the skewed prior and the same
respective observational datasets.

(a) $N=10$

(b) $N=10^{2}$

(c) $N=10^{3}$

(d) $N=10^{4}$

(e) $N=10$

(f) $N=10^{2}$

(g) $N=10^{3}$

(h) $N=10^{4}$

Figure 12: Histogram plots for samples drawn from the posterior distribution
over probability $P(Y_{x=0}=0)$ in “IV” graph of Fig. 1(a) using two priors.
(12(a) \- 12(d)) shows the posteriors using the flat prior and observational
data of size $N=10,10^{2},10^{3}$ and $10^{4}$ respectively; (12(e) \- 12(h))
shows the posetriors using the skewed prior and the same respective
observational datasets.

#### Experiment 8: Triple Bow

Consider the “Triple Bow” diagram in Fig. 8(d) where $X,Y,Z\in\\{0,1\\}$ and
$U_{1},U_{2},U_{3}\in\mathbb{R}$. We are interested in evaluating the
counterfactual probability $P(Y_{x=1}=1,Y_{x=0}=0)$ from the combination of
the observational distribution $P(X,Y,Z,W)$ and interventional distributions
$P(X_{z},Y_{z},W_{z})$. To our best knowledge, existing bounding strategies
are not applicable to this setting. We collect $N=10^{3}$ samples
$\bar{\bm{v}}=\\{x^{(n)},y^{(n)},z^{(n)},w^{(n)}\\}_{n=1}^{N}$ from an SCM
compatible Fig. 8(d). The detailed parametrization of the SCM is provided in
the following:

$\begin{split}&U_{1}\sim\texttt{Unif}(0,1),\\\
&U_{i}\sim\texttt{Normal}(0,1),\;\;i=2,3,\\\ &Z\sim\lfloor 1.5\cdot
U_{1}\rfloor,\\\ &W\sim\texttt{Binomial}(1,\rho_{W}),\\\
&X\sim\texttt{Binomial}(1,\rho_{X}),\\\ &E\sim\texttt{Logistic}(0,1),\\\
&Y\leftarrow\mathds{1}_{X-U_{3}+E+0.1>0},\end{split}$ (103)

where probabilities $\rho_{Z},\rho_{W},\rho_{X}$ are given by:

$\displaystyle\rho_{Z}=\frac{1}{1+\exp(-U_{1})},$
$\displaystyle\rho_{W}=\frac{1}{1+\exp(-Z-U_{1}-U_{2})},$
$\displaystyle\rho_{X}=\frac{1}{1+\exp(-W-U_{2}-U_{3})}.$

Each sample $\left(x^{(n)},y^{(n)},z^{(n)},w^{(n)}\right)$ is an independent
draw from the observational distribution $P(X,Y,Z,W)$ or an interventional
distribution $P(X_{z},Y_{z},W_{z})$. To obtain a sample from
$P(x_{z},y_{z},w_{z})$, we pick a constant $z\in\Omega_{Z}$ uniformly at
random, perform intervention $\text{do}(Z=z)$ in the SCM described in Eq. 103
and observed subsequent outcomes.

In this experiment, we set hyperparameters $\alpha_{U_{1}}=d_{U_{1}}=32$ and
$\alpha_{U_{2}}=d_{U_{1}}=32$. Fig. 9(d) shows samples drawn from the
posterior distribution of $\left(P(Y_{x=0}=1)\mid\bar{\bm{v}}\right)$. The
analysis reveals that our proposed approach is able to achived an effective
bound that contain the actual counterfactual probability
$P(Y_{x=1}=1,Y_{x=0}=0)=0.1867$. The $100\%$ credible interval (ci) is equal
to $l=0.1150,r=0.3686$.

### C.2 The Effect of Sample Size and Prior Distributions

We will evaluate our algorithms using skewed prior distributions. We found
that increasing the size of observational samples was able to wash away the
bias introduced by prior distributions. That is, despite the influence of
prior distributions, our algorithms eventually converge to sharp bounds over
unknown counterfactual probabilities as the number of observational sample
grows (to infinite).

#### Experiment 9: Frontdoor

Consider first the “Frontdoor” graph in Fig. 1(d) where interventional
probabilities $P(y_{x})$ is identifiable from the observational distribution
$P(X,Y,W)$. The detailed parametrization of the underlying SCM is described in
Eq. 95. We present our results using two different priors. The first is a flat
(uniform) distribution over probabilities of $U_{1}$ and $U_{2}$ respectively,
i.e., $\alpha_{U_{1}}=d_{U_{1}}=8$ and $\alpha_{U_{1}}=d_{U_{2}}=4$. The
second is skewed to present a strong preference on the deterministic
relationships between $X$ and $Y$; in this case, $\alpha_{1}=300\times
d_{U_{i}}$, $i=1,2$, for prior distributions associated with both $U_{1}$ and
$U_{2}$. Figs. 10(a) and 10(b) shows the distribution of $P(Y_{x=0})$ induced
by these two priors (in the absence of any observational data). We see that
the skewed prior of Fig. 10(b) assigns almost all weights to deterministic
events $P(Y_{x=0}=1)=1$ or $P(Y_{x=0}=0)=1$.

Fig. 8 shows posterior samples obtained by our Gibbs sampler when applied to
observational data of various sizes, using both the flat prior (Figs. 11(a) to
11(d)) and the skewed prior (Figs. 11(e) to 11(h)). Both priors eventually
collapse to the actual, unknown probability $P(Y_{x=0}=1)=0.5085$. As
expected, more observational data are needed for the skewed prior before the
posterior distribution converges, since the skewed prior is concentrated
further away from the value $0.5085$ than the uniform prior.

#### Experiment 10: IV

Consider the “IV” diagram in Fig. 1(a) where $X,Y,Z$ are binary variables
taking values in $\\{0,1\\}$. Detailed parametrization of the SCM is provided
as follows:

$\begin{split}&U_{1}\sim\texttt{Normal}(0,1),\\\
&U_{2}\sim\texttt{Normal}(0,1),\\\ &Z\sim\texttt{Binomial}(1,\rho_{Z}),\\\
&X\sim\texttt{Binomial}(1,\rho_{X}),\\\
&Y\sim\texttt{Binomial}(1,\rho_{Y}),\end{split}$ (104)

where probabilities $\rho_{Z},\rho_{X},\rho_{Y}$ are given by

$\displaystyle\rho_{Z}=\frac{1}{1+\exp(-U_{1})},$
$\displaystyle\rho_{X}=\frac{1}{1+\exp(-Z-U_{2})},$
$\displaystyle\rho_{Y}=\frac{1}{1+\exp(X-U_{2}+0.5)}.$

In this case, the counterfactual distribution $P(y_{x})$ is not identifiable
from the observational distribution $P(X,Y,Z)$ (Bareinboim and Pearl 2012).
Sharp bounds over $P(y_{x})$ from $P(x,y,z)$ were derived in (Balke and Pearl
1994) (labelled as opt). We present our results using two different priors.
The first is a flat (uniform) distribution over probabilities of $U_{1}$ and
$U_{2}$ respectively, i.e., $\alpha_{U_{1}}=d_{U_{1}}=2$ and
$\alpha_{U_{1}}=d_{U_{2}}=16$. The second is skewed to present a strong
preference on the deterministic relationships between $X$ and $Y$; in this
case, $\alpha_{1}=300\times d_{U_{i}}$, $i=1,2$, for prior distributions
associated with both $U_{1}$ and $U_{2}$. Figs. 10(c) and 10(d) shows
distributions of $P(Y_{x=0})$ induced by these two prior distributions (in the
absence of any observational data). We see that the skewed prior of Fig. 10(d)
assigns almost all weights to deterministic events $P(Y_{x=0}=1)=1$ or
$P(Y_{x=0}=0)=1$.

Fig. 12 shows posterior samples obtained by our Gibbs sampler when applied to
observational data of various sizes, using both the flat prior (Figs. 12(a) to
12(d)) and the skewed prior (Figs. 12(e) to 12(h)). Our analysis reveals that
$100\%$ credible intervals of both priors eventually converge to the sharp IV
bound $l=0.1468,r=0.6617$ over the unknown interventional probability
$P(Y_{x=0}=1)=0.3954$. It is interesting to note that, in this experiment,
while the choice of prior distribution does not influence the final bound, it
still has an effect on the shape of posterior distributions given finite
samples of the observational data.

##  Appendix D D. Polynomial Optimization for Bounding Counterfactual
Probabilities

In this section, we will demonstrate how one could solve the optimization
problem in Eq. 2 assuming access to a polynomial optimization oracle.

Recall that Thm. 1 implies that counterfactual distributions
$P\left(\bm{Y}_{\bm{x}},\dots,\bm{Z}_{\bm{w}}\right)$ in any causal diagram
$\mathcal{G}$ could be generated by a discrete SCM in the canonical family
$\mathscr{N}(\mathcal{G})$ and be written as follows:

$\displaystyle
P\left(\bm{y}_{\bm{x}},\dots,\bm{z}_{\bm{w}}\right)=\sum_{\bm{u}}\mathds{1}_{\bm{Y}_{\bm{x}}(\bm{u})=\bm{y}}\cdots\mathds{1}_{\bm{Z}_{\bm{w}}(\bm{u})=\bm{z}}\prod_{U\in\bm{U}}\theta_{u}.$

Among above quantities, for every exogenous $U\in\bm{U}$, parameters
$\theta_{u}$ are discrete probabilities $P(U=u)$ over a finite domain
$\\{1,\dots,d_{U}\\}$ where the cardinality
$d_{U}=\prod_{V\in\bm{C}(U)}\left|\Omega_{\mathit{Pa}_{V}}\mapsto\Omega_{V}\right|$.
That is, parameters $\left\\{\theta_{u}\mid\forall u\in\Omega_{U}\right\\}$
satisfy the following:

$\displaystyle\theta_{u}\in[0,1],$
$\displaystyle\sum_{u\in\Omega_{U}}\theta_{u}=1.$

For every $V\in\bm{V}$, we represent the output of function
$f_{V}(\mathit{pa}_{V},u_{V})$ given input $\mathit{pa}_{V},u_{V}$ using an
indicator vector
$\mu_{V}^{(\mathit{pa}_{V},u_{V})}=\left(\mu_{v}^{(\mathit{pa}_{V},u_{V})}\mid\forall
v\in\Omega_{V}\right)$ such that

$\displaystyle\mu_{v}^{(\mathit{pa}_{V},u_{V})}\in\\{0,1\\},$
$\displaystyle\sum_{v\in\Omega_{V}}\mu_{v}^{(\mathit{pa}_{V},u_{V})}=1.$

For subsets $\bm{X},\bm{Y}\subseteq\bm{V}$, fix constants
$\bm{x},\bm{y},\bm{u}$. The indicator function
$\mathds{1}_{\bm{Y}_{\bm{x}}(\bm{u})=\bm{y}}$ could be written as a product

$\displaystyle\mathds{1}_{\bm{Y}_{\bm{x}}(\bm{u})=\bm{y}}=\prod_{Y\in\bm{Y}}\mathds{1}_{Y_{\bm{x}}(\bm{u})=y}.$

For every $Y\in\bm{Y}$, $\mathds{1}_{Y_{\bm{x}}(\bm{u})=y}$ is recursively
given by:

$\displaystyle\mathds{1}_{Y_{\bm{x}}(\bm{u})=y}=\begin{dcases}\mathds{1}_{y=\bm{x}_{Y}}&\mbox{if
}Y\in\bm{X}\\\
\sum_{\mathit{pa}_{Y}}\mu_{y}^{\left(\mathit{pa}_{Y},u_{Y}\right)}\mathds{1}_{\mathit{PA}_{Y\bm{x}}=\mathit{pa}_{Y}}&\mbox{otherwise}\end{dcases}$

The above equations allow us to write any counterfactual probability
$P\left(\bm{y}_{\bm{x}},\dots,\bm{z}_{\bm{w}}\right)$ as a polynomial function
of parameters $\mu_{v}^{(\mathit{pa}_{V},u_{V})}$ and $\theta_{u}$. This means
that the polynomial optimization in Eq. 2 could be reducible to an equivalent
polynomial optimization program. For the remainder of this section, we will
illustrate this reduction using various examples in different causal diagrams.

#### Example 1: IV

Consider the “IV” diagram $\mathcal{G}$ in Fig. 1(a). We study the problem of
bounding counterfactual probabilities $P(y^{\prime}_{x^{\prime}},x,y)\equiv
P(Y_{x^{\prime}}=y^{\prime},X=x,Y=y)$ from the observational distribution
$P(X,Y,Z)$. Formally, let $\mathscr{M}(\mathcal{G})$ denote the set of all
SCMs compatible with the diagram $\mathcal{G}$. One could obtain the tight
bound over $P(y^{\prime}_{x^{\prime}},x,y)$ from $P(X,Y,Z)$ by solving the
optimization problem as follows:

$\displaystyle\underset{M\in\mathscr{M}(\mathcal{G})}{\min/\max}$
$\displaystyle P_{M}\left(y^{\prime}_{x^{\prime}},x,y\right)$ (105) s.t.
$\displaystyle P_{M}(x,y,z)=P(x,y,z),\;\;\forall x,y,z.$

In the above optimization problem, it follows from Thm. 1 that the objective
function could be written as

$\displaystyle P_{M}(y^{\prime}_{x^{\prime}},x,y)$
$\displaystyle=\sum_{u_{1}=1}^{d_{1}}\sum_{u_{2}=1}^{d_{2}}\mu_{y^{\prime}}^{(x^{\prime},u_{2})}\mu_{y}^{(x,u_{2})}\sum_{z}\mu_{x}^{(z,u_{2})}\mu_{z}^{(u_{1})}\theta_{u_{1}}\theta_{u_{2}}.$

Similarly, the observational constraints could be written as:

$\displaystyle
P_{M}(x,y,z)=\sum_{u_{1}=1}^{d_{1}}\sum_{u_{2}=1}^{d_{2}}\mu_{z}^{(u_{1})}\mu_{x}^{(z,u_{2})}\mu_{y}^{(x,u_{2})}\theta_{u_{1}}\theta_{u_{2}}.$

The above equations imply that Eq. 105 could be reducible to an equivalent
polynomial program as follows:

$\displaystyle\min/\max\;\;$
$\displaystyle\sum_{u_{1}=1}^{d_{1}}\sum_{u_{2}=1}^{d_{2}}\mu_{y^{\prime}}^{(x^{\prime},u_{2})}\mu_{y}^{(x,u_{2})}\sum_{z}\mu_{x}^{(z,u_{2})}\mu_{z}^{(u_{1})}\theta_{u_{1}}\theta_{u_{2}}$
subject to
$\displaystyle\;\;\sum_{u_{1}=1}^{d_{1}}\sum_{u_{2}=1}^{d_{2}}\mu_{z}^{(u_{1})}\mu_{x}^{(z,u_{2})}\mu_{y}^{(x,u_{2})}\theta_{u_{1}}\theta_{u_{2}}$
$\displaystyle=P(x,y,z),\;\;\forall x,y,z$ $\displaystyle\forall
z,u_{1},\;\;\mu_{z}^{(u_{1})}\left(1-\mu_{z}^{(u_{1})}\right)=0,$
$\displaystyle\forall z,u_{1},\;\;\sum_{z}\mu_{z}^{(u_{1})}=1$
$\displaystyle\forall
x,z,u_{2},\;\;\mu_{x}^{(z,u_{2})}\left(1-\mu_{x}^{(z,u_{2})}\right)=0$
$\displaystyle\forall x,z,u_{2},\;\;\sum_{x}\mu_{x}^{(z,u_{2})}=1$
$\displaystyle\forall
y,x,u_{2},\;\;\mu_{y}^{(x,u_{2})}\left(1-\mu_{y}^{(x,u_{2})}\right)=0$
$\displaystyle\forall y,x,u_{2}\;\;\sum_{y}\mu_{y}^{(x,u_{2})}=1$
$\displaystyle\forall u_{1},\;\;0\leq\theta_{u_{1}}\leq
1,\;\;\sum_{u_{1}}\theta_{u_{1}}=1$ $\displaystyle\forall
u_{2},\;\;0\leq\theta_{u_{2}}\leq 1,\;\;\sum_{u_{2}}\theta_{u_{2}}=1$

where cardinalities $d_{1},d_{2}$ are equal to

$\displaystyle d_{1}=\left|\Omega_{Z}\right|,$ $\displaystyle
d_{2}=\left|\Omega_{Z}\mapsto\Omega_{X}\right|\times\left|\Omega_{X}\mapsto\Omega_{Y}\right|.$

#### Example 2

Consider the causal diagram in Fig. 1(b). We study the problem of bounding
counterfactual probabilities $P(z,x_{z^{\prime}},y_{x^{\prime}})$ from a
combination of the observational distribution $P(X,Y,Z)$ and the
interventional distribution $\left\\{P(X_{z},Y_{z})\mid\forall
z\in\Omega_{Z}\right\\}$. That is,

$\displaystyle\underset{M\in\mathscr{M}(\mathcal{G})}{\min/\max}$
$\displaystyle P_{M}\left(z,x_{z^{\prime}},y_{x^{\prime}}\right)$ (106) s.t.
$\displaystyle P_{M}(x,y,z)=P(x,y,z),\;\;\forall x,y,z$ $\displaystyle
P_{M}(x_{z},y_{z})=P(x_{z},y_{z}),\;\;\forall x,y,z$

Among quantities in the above equation, it follows from Thm. 1 that the
objective function could be written as

$\displaystyle P_{M}(z,x_{z^{\prime}},y_{x^{\prime}})$
$\displaystyle=\sum_{u_{1},u_{2}=1}^{d}\mu_{z}^{(u_{1})}\mu_{x}^{(z^{\prime},u_{2})}\mu_{y}^{(x^{\prime},u_{1},u_{2})}\theta_{u_{1}}\theta_{u_{2}}.$

Similarly, the observational constraints could be written as:

$\displaystyle
P_{M}(x,y,z)=\sum_{u_{1},u_{2}=1}^{d}\mu_{z}^{(u_{1})}\mu_{x}^{(z,u_{2})}\mu_{y}^{(x,u_{1},u_{2})}\theta_{u_{1}}\theta_{u_{2}},$

and the interventional constraints imply:

$\displaystyle
P_{M}(x_{z},y_{z})=\sum_{u_{1},u_{2}=1}^{d}\mu_{x}^{(z,u_{2})}\mu_{y}^{(x,u_{1},u_{2})}\theta_{u_{1}}\theta_{u_{2}}.$

The above equations imply that one could obtain an optimal bound over
$P(z,x_{z^{\prime}},y_{x^{\prime}})$ given by Eq. 106 by solving an equivalent
polynomial program as follows:

$\displaystyle\min/\max\;\;$
$\displaystyle\sum_{u_{1},u_{2}=1}^{d}\mu_{z}^{(u_{1})}\mu_{x}^{(z^{\prime},u_{2})}\mu_{y}^{(x^{\prime},u_{1},u_{2})}\theta_{u_{1}}\theta_{u_{2}}$
s.t.
$\displaystyle\sum_{u_{1},u_{2}=1}^{d}\mu_{z}^{(u_{1})}\mu_{x}^{(z,u_{2})}\mu_{y}^{(x,u_{1},u_{2})}\theta_{u_{1}}\theta_{u_{2}}$
$\displaystyle=P(x,y,z),\;\;\forall x,y,z$
$\displaystyle\sum_{u_{1},u_{2}=1}^{d}\mu_{x}^{(z,u_{2})}\mu_{y}^{(x,u_{1},u_{2})}\theta_{u_{1}}\theta_{u_{2}}$
$\displaystyle=P(x_{z},y_{z}),\;\;\forall x,y,z$ $\displaystyle\forall
z,u_{1},\;\;\mu_{z}^{(u_{1})}\left(1-\mu_{z}^{(u_{1})}\right)=0$
$\displaystyle\forall z,u_{1},\;\;\sum_{z}\mu_{z}^{(u_{1})}=1$
$\displaystyle\forall
x,z,u_{1},u_{2},\;\;\mu_{x}^{(z,u_{1},u_{2})}\left(1-\mu_{x}^{(z,u_{1},u_{2})}\right)=0$
$\displaystyle\forall x,z,u_{1},u_{2},\;\;\sum_{x}\mu_{x}^{(z,u_{1},u_{2})}=1$
$\displaystyle\forall
y,x,u_{2},\;\;\mu_{y}^{(x,u_{2})}\left(1-\mu_{y}^{(x,u_{2})}\right)=0$
$\displaystyle\forall y,x,u_{2},\;\;\sum_{y}\mu_{y}^{(x,u_{2})}=1$
$\displaystyle\forall u_{1},\;\;0\leq\theta_{u_{1}}\leq
1,\;\;\sum_{u_{1}}\theta_{u_{1}}=1$ $\displaystyle\forall
u_{2},\;\;0\leq\theta_{u_{2}}\leq 1,\;\;\sum_{u_{2}}\theta_{u_{2}}=1$

where the cardinality $d$ equates to

$\displaystyle
d=\left|\Omega_{Z}\right|\times\left|\Omega_{Z}\mapsto\Omega_{X}\right|\times\left|\Omega_{X}\mapsto\Omega_{Y}\right|.$

#### Example 3: Frontdoor

Consider the “Frontdoor” diagram in Fig. 1(c). We are interested in evaluating
interventional probabilities $P(y_{x})$ from the observational distribution
$P(X,Y,W)$. That is,

$\displaystyle\underset{M\in\mathscr{M}(\mathcal{G})}{\min/\max}$
$\displaystyle P_{M}\left(y_{x}\right)$ (107) s.t. $\displaystyle
P_{M}(x,y,w)=P(x,y,w),\;\;\forall x,y,w$

It follows from Thm. 1 that the objective function in the above optimization
problem could be further written as

$\displaystyle
P_{M}(y_{x})=\sum_{u_{1}=1}^{d_{1}}\sum_{u_{1}=1}^{d_{2}}\sum_{w}\mu_{y}^{(w,u_{1})}\mu_{w}^{(x,u_{2})}\theta_{u_{1}}\theta_{u_{2}}.$

Similarly, the observational constraints could be written as:

$\displaystyle
P_{M}(x,y,w)=\sum_{u_{1}=1}^{d_{1}}\sum_{u_{1}=1}^{d_{2}}\mu_{x}^{(u)}\mu_{y}^{(w,u_{1})}\mu_{w}^{(x,u_{2})}\theta_{u_{1}}\theta_{u_{2}}.$

The above equations imply that one could obtain the optimal solution in Eq.
107 by solving an equivalent polynomial optimization problem defined as
follows:

$\displaystyle\min/\max\;\;$
$\displaystyle\sum_{u_{1}=1}^{d_{1}}\sum_{u_{1}=1}^{d_{2}}\sum_{w}\mu_{y}^{(w,u_{1})}\mu_{w}^{(x,u_{2})}\theta_{u_{1}}\theta_{u_{2}}$
subject to
$\displaystyle\sum_{u_{1}=1}^{d_{1}}\sum_{u_{1}=1}^{d_{2}}\mu_{x}^{(u)}\mu_{y}^{(w,u_{1})}\mu_{w}^{(x,u_{2})}\theta_{u_{1}}\theta_{u_{2}}$
$\displaystyle=P(x,y,w),\forall x,y,w$ $\displaystyle\forall
x,u_{1},\;\;\mu_{x}^{(u)}\left(1-\mu_{x}^{(u)}\right)=0,$
$\displaystyle\forall x,u_{1},\;\;\sum_{x}\mu_{x}^{(u)}=1,$
$\displaystyle\forall
y,w,u_{1},\;\;\mu_{y}^{(w,u_{1})}\left(1-\mu_{y}^{(w,u_{1})}\right)=0,$
$\displaystyle\forall y,w,u_{1},\;\;\sum_{y}\mu_{y}^{(w,u_{1})}=1,$
$\displaystyle\forall
w,x,u_{2},\;\;\mu_{w}^{(x,u_{2})}\left(1-\mu_{w}^{(x,u_{w})}\right)=0,$
$\displaystyle\forall w,x,u_{2},\;\;\sum_{w}\mu_{w}^{(x,u_{w})}=1,$
$\displaystyle\forall u_{1},\;\;0\leq\theta_{u_{1}}\leq
1,\;\;\sum_{u_{1}}\theta_{u_{1}}=1,$ $\displaystyle\forall
u_{2},\;\;0\leq\theta_{u_{2}}\leq 1,\;\;\sum_{u_{2}}\theta_{u_{2}}=1,$

where cardinalities $d_{1},d_{2}$ equate to

$\displaystyle
d_{1}=\left|\Omega_{X}\right|\times\left|\Omega_{W}\mapsto\Omega_{Y}\right|,$
$\displaystyle d_{2}=\left|\Omega_{X}\mapsto\Omega_{W}\right|.$

#### Example 4: Bow

Consider the “Bow” diagram in Fig. 1(d). We study the problem of bounding
counterfactual probabilities $P(y_{x},y^{\prime}_{x^{\prime}})\equiv
P\left(Y_{x}=y,Y_{x=x^{\prime}}=y^{\prime}\right)$ from a combination of the
observational distribution $P(X,Y,Z)$ and the interventional distribution
$\left\\{P(Y_{x})\mid\forall x\in\Omega_{X}\right\\}$, i.e.,

$\displaystyle\underset{M\in\mathscr{M}(\mathcal{G})}{\min/\max}$
$\displaystyle P_{M}\left(y_{x},y^{\prime}_{x^{\prime}}\right)$ (108) s.t.
$\displaystyle P_{M}(x,y)=P(x,y),\;\;\forall x,y$ $\displaystyle
P_{M}(y_{x})=P(y_{x}),\;\;\forall x,y$

Among quantities in the above equation, it follows from Thm. 1 that the
objective function could be written as

$\displaystyle
P_{M}(y_{x},y^{\prime}_{x^{\prime}})=\sum_{u=1}^{d}\mu_{y}^{(x,u)}\mu_{y^{\prime}}^{(x^{\prime},u)}\theta_{u}.$

Similarly, the observational constraints could be written as:

$\displaystyle
P_{M}(x,y)=\sum_{u=1}^{d}\mu_{x}^{(u)}\mu_{y}^{(x,u)}\theta_{u},$

and the interventional constraints are given by:

$\displaystyle P_{M}(y_{x})=\sum_{u=1}^{d}\mu_{y}^{(x,u)}\theta_{u}.$

The optimization problem defined in Eq. 108 is thus reducible to an equivalent
polynomial program as follows:

$\displaystyle\min/\max\;\;$
$\displaystyle\sum_{u=1}^{d}\mu_{y}^{(x,u)}\mu_{y^{\prime}}^{(x^{\prime},u)}\theta_{u}$
subject to
$\displaystyle\sum_{u=1}^{d}\mu_{x}^{(u)}\mu_{y}^{(x,u)}\theta_{u}=P(x,y),\;\;\forall
x,y$
$\displaystyle\sum_{u=1}^{d}\mu_{y}^{(x,u)}\theta_{u}=P(y_{x}),\;\;\forall
x,y$ $\displaystyle\forall
x,u,\;\;\mu_{x}^{(u)}\left(1-\mu_{x}^{(u)}\right)=0$ $\displaystyle\forall
x,u,\;\;\sum_{x}\mu_{x}^{(u)}=1$ $\displaystyle\forall
y,x,u,\;\;\mu_{y}^{(x,u)}\left(1-\mu_{y}^{(x,u)}\right)=0$
$\displaystyle\forall y,x,u,\;\;\sum_{y}\mu_{y}^{(x,u)}=1$
$\displaystyle\forall u,\;\;0\leq\theta_{u}\leq 1,\;\;\sum_{u}\theta_{u}=1$

where the cardinality $d$ is equal to
$\left|\Omega_{Z}\mapsto\Omega_{X}\right|$.

##  Appendix E E. A Naïve Generalization of (Balke and Pearl 1994)

In this section, we will describe a naïve generalization of the discretization
procedure introduced in (Balke and Pearl 1994) to the causal diagram of Fig.
13(a). In particular, given any SCM $M$ compatible with Fig. 13(a), we will
construct a discrete SCM $N$ compatible with a different causal diagram
described in Fig. 13(b) such that $M$ and $N$ coincide in all counterfactual
distributions $\bm{P}^{*}$.

We first introduce some useful notations. Let $f_{Z},f_{X},f_{Y}$ denote
functions associated with $Z,X,Y$ in SCM $M$. Let constants $h_{Z}^{(1)}=0$
and $h_{Z}^{(2)}=1$. Note that given any $U_{1}=u_{1}$, $f_{Z}(u_{1})$ must
equate to a binary value in $\\{0,1\\}$. Therefore, we could define a
partition $\mathcal{U}_{Z}^{(i)}$, $i=1,2$, over domains of $U_{1}$ such that
$u_{1}\in\mathcal{U}_{Z}^{(i)}$ if and only if

$\displaystyle f_{Z}(u_{1})=h_{Z}^{(i)}.$ (109)

Given any $u_{2}$, $f_{X}(\cdot,u_{2})$ defines a function mapping from
domains of $Z$ to $X$. Let functions in the hypothesis class
$\Omega_{Z}\mapsto\Omega_{X}$ be ordered by

$\displaystyle h_{X}^{(1)}(z)=0,$ $\displaystyle h_{X}^{(2)}(z)=z,$ (110)
$\displaystyle h_{X}^{(3)}(z)=\neg z,$ $\displaystyle h_{X}^{(4)}(z)=1.$

Similarly, we could define a partition $\mathcal{U}_{X}^{(i)},i=1,2,3,4$ over
the domain $\Omega_{U_{2}}$ such that $u_{2}\in\mathcal{U}_{X}^{(i)}$ if and
only if the induced function $f_{X}(\cdot,u_{2})=h_{X}^{(i)}$. Finally, let
functions in $\Omega_{X}\mapsto\Omega_{Y}$ mapping from domains of $X$ to $Y$
be ordered by

$\displaystyle h_{Y}^{(1)}(x)=0,$ $\displaystyle h_{Y}^{(2)}(x)=x,$ (111)
$\displaystyle h_{Y}^{(3)}(x)=\neg x,$ $\displaystyle h_{Y}^{(4)}(x)=1.$

For any $u_{1},u_{2}$, the induced function $f_{Y}(\cdot,u_{1},u_{2})$ must
coincide with only of the above elements in the hypothesis class
$\Omega_{X}\mapsto\Omega_{Y}$. Let $\mathcal{U}_{Y}^{(i)},i=1,2,3,4$ be a
subset of the product domain $\Omega_{U_{1}}\times\Omega_{U_{2}}$ such that
$(u_{1},u_{2})\in\mathcal{U}_{Y}^{(i)}$ if any only if
$f_{Y}(\cdot,u_{1},u_{2})=h_{Y}^{(i)}$. It is verifiable that
$\mathcal{U}_{Y}^{(i)},i=1,2,3,4$ must form a partition over
$\Omega_{U_{1}}\times\Omega_{U_{2}}$.

We now construct a discrete SCM $N$ compatible with the causal diagram of Fig.
13(b). Let the exogenous variable $U$ in $N$ be a tuple $(U_{Z},U_{X},U_{Y})$,
where $U_{Z}\in\\{1,2\\}$, $U_{X}\in\\{1,2,3,4\\}$ and
$U_{Y}\in\\{1,2,3,4\\}$. For any $u_{Z}$, values of $Z$ are decided by a
function as follows:

$\displaystyle z\leftarrow f_{Z}(u_{z})=h_{Z}^{(u_{Z})},$ (112)

where $h_{Z}^{(1)}=0$ and $h_{Z}^{(2)}=1$. Given any input $z,u_{X}$, values
of $X$ are given by

$\displaystyle x\leftarrow f_{X}(z,u_{X})=h_{X}^{(u_{X})}(z),$ (113)

where $h_{X}^{(i)}(z)$, $i=1,2,3,4$, are defined in Eq. 110. Similarly, given
any $x,u_{Y}$, values of $Y$ are given by

$\displaystyle y\leftarrow f_{Y}(x,u_{Y})=h_{Y}^{(u_{Y})}(x),$ (114)

where $h_{Y}^{(i)}(x)$, $i=1,2,3,4$, are functions defined in Eq. 111.
Finally, we define the exogenous distribution $P(u_{Z},u_{X},u_{Y})$ in the
discrete SCM $N$ as the joint probability over partitions
$\mathcal{U}_{Z}^{(i)},\mathcal{U}_{X}^{(j)},\mathcal{U}_{Y}^{(k)}$, $i=1,2$,
$j=1,2,3,4$, $k=1,2,3,4$. That is,

$\displaystyle P_{N}\left(U_{Z}=i,U_{X}=j,U_{Y}=k\right)$ (115)
$\displaystyle=P_{M}\left((U_{1},U_{2})\in\mathcal{U}_{Z}^{(i)}\wedge\mathcal{U}_{X}^{(j)}\wedge\mathcal{U}_{Y}^{(k)}\right).$

It follows from the decomposition in Lem. 3 that $N$ and $M$ must coincide in
all counterfactual distributions over binary $X,Y,Z$. The total cardinality of
the exogenous domains in $N$ is
$|\Omega_{U_{Z}}|\times|\Omega_{U_{X}}|\times|\Omega_{U_{Y}}|=2\times 4\times
4=32$.

However, the construction for the reverse direction does not hold true. That
is, given an arbitrary discrete $N$ compatible with the causal diagram in Fig.
13(b), one may not be able to construct an SCM $M$ compatible with the causal
diagram in Fig. 13(a) such that $M$ and $N$ coincide in all counterfactual
distributions. To witness, consider a discrete SCM $N$ where
$P(U_{Z}=U_{X})=1$, i.e., variables $U_{Z}$ and $U_{X}$ are always the same,
taking values in $\\{1,2\\}$. Since in SCM $N$, values of $Z(u_{Z})$ and
$X_{z=1}(u_{X})$ are given by

$\displaystyle
Z(u_{Z})=h_{Z}^{(u_{Z})}=0\times\mathds{1}_{u_{Z}=1}+1\times\mathds{1}_{u_{Z}=2},$
$\displaystyle
X_{z=1}(u_{X})=h_{X}^{(u_{X})}(1)=0\times\mathds{1}_{u_{X}=1}+1\times\mathds{1}_{u_{X}=2}.$

This means that values of counterfactual variables $Z$ and $X_{z=0}$ must
always coincide, i.e., $P(Z=X_{x=1})=1$. However, for any SCM $M$ compatible
with Fig. 13(a), counterfactual variables $Z$ and $X_{z}$ must be independent
due to the independence restriction (Pearl 2000, Ch. 7.3.2), i.e.,
$Z\perp\\!\\!\\!\perp X_{z}$, which is a contradiction.

ZXYU1U2 (a)

ZXYU (b)

Figure 13: Causal diagrams (13(a)-13(b)) containing a treatment $X$, an
outcome $Y$, an ancestor $Z$, and unobserved $U$s.