# Implementation of hitting times of discrete time quantum random walks on
Cubelike graphs.

Jaideep Mulherkar<EMAIL_ADDRESS>,  Rishikant Rajdeepak
<EMAIL_ADDRESS>and  V Sunitha<EMAIL_ADDRESS>Dhirubhai
Ambani Institute of Information and Communication Technology , Gandhinagar,
India.

###### Abstract.

We demonstrate an implementation of the hitting time of a discrete time
quantum random walk on cubelike graphs using IBM’s Qiskit platform. Our
implementation is based on efficient circuits for the Grover and Shift
operators. We verify the results about the one-shot hitting time of quantum
walks on a hypercube as proved in [17]. We extend the study to another family
of cubelike graphs called the augmented cubes [11]. Based on our numerical
study, we conjecture that for all families of cubelike graphs there is a
linear relationship between the degree of a cubelike graph and its hitting
time which holds asymptotically. That is, for any cubelike graph of degree
$\Delta$, the probability of finding the quantum random walk at the target
node at time $\frac{\pi\Delta}{2}$ approaches 1 as the degree $\Delta$ of the
cubelike graph approaches infinity.

Keywords. Quantum Random Walks, Cubelike graphs, Hitting times

##  1\. Introduction

Classical random walks have found applications in many areas such as computer
science, physics, finance and engineering. In particular, classical random
walks have been used in the development of faster algorithms for estimating
the volume of a convex body, finding a satisfying assignment to a Boolean
formula (2-SAT problem) and finding if two vertices of an undirected graph are
connected [21]. Quantum random walks [16, 23, 25] are quantum mechanical
analogues of classical random walks. The first quantum random walk models were
proposed in [5, 12]. It has since been observed that there are some startling
differences between classical and quantum walks. For instance, it has been
shown that the hitting time from one vertex to the antipodal vertex is linear
in the dimension of the hypercube, which is exponentially fast in quantum
walks compared to classical walks [17]. Moreover, there is also a speed up
obtained in the mixing time of quantum versus the classical walks [22]. These
differences between classical and quantum walks led to search for quantum walk
based algorithms that can outperform classical counterparts. Some of the
quantum algorithms that have been developed based on quantum walks are
searching a marked element on a grid, the element distinctness problem and the
triangle finding problem in a graph [6]. Quantum walks have also been shown to
be universal for quantum computation [10, 20].

In quantum random walks there is a quantum system such as a spin system on a
graph and the evolution is given by a unitary operator acting on a Hilbert
space of the graph. Generally speaking quantum walks are of two types :
Discrete and Continuous. In the discrete time quantum walk the associated
Hilbert space is a joint system of a coin space and position space. For a
regular graph the coin space has dimension equal to the number of edges per
node and the dimension of the position space is equal to the number of
vertices in the graph. The discrete time quantum walk starts with an initial
state of the coin and position. Each time step in the evolution of the
discrete random walk consists of the following: 1. A coin operator acts on the
coin space changing the original coin state to a new state 2. A Shift operator
shifts the current position of the random walker conditioned on the coin
state. This step is then repeated many times thus evolving the random walker
over the state space of the graph. After a certain number of time steps a
measurement is done of the position space. The continuous random walks are the
evolution of a quantum system on a graph according to the unitary $e^{iAt}$
where $A$ is the adjacency matrix of the graph. A quantity of interest in
quantum walks is the hitting time for a pair of vertices. For a pair of
vertices $(u,v)$, if starting from vertex $u$, after a certain number of time
steps $T$ of the walker is observed to be in vertex $v$ with probability $p$
then $(T,p)$ is called the hitting time for vertex $v$ starting from vertex
$u$. The hitting times are based on the graph topology and faster hitting
times could mean speed up algorithms. Quantum walks have been studied on a
variety of graphs such as cycles, trees, and cubelike graphs and general
Cayley graphs [4, 3]. A related question is of perfect state transfer between
two vertices, which has been studied in [14]. Apart from the results in [17]
in hypercubes, cubelike graphs have been studied in the context of continuous
time random walks. Criterion for the perfect state transfer on cubelike graphs
have been given in [8, 9]. In this paper we restrict our study to the hitting
times of discrete time quantum walks on cubelike graphs.

Because of their universality and potential use in developing algorithms there
is a need for good physical implementations of quantum random walks. Physical
implementations based on ion-traps, optical cavities and optical lattices has
been suggested in [18, 24, 27]. Circuit implementations of various standard
quantum algorithms using IBM’s Qiskit platform was done in [15]. Recently in
[2] implementation of staggered quantum walks on cycles, two-dimensional
lattices and complete graph was studied on IBM quantum computers. A comparison
on two different implementation approaches of quantum walks is given in [13].
An implementation of the discrete time quantum walk on hypercubes, complete
graphs, complete bipartite graphs and 2-d lattice is recently given in [26].
Our work is in the spirit of implementation of QRW’s for NISQ (Nosiy
Intermediate Scale Quantum computing) era computers. Our main contributions in
this paper are 1) An implementation of efficient circuits for the QRW on a
cubelike graph based on decompositions of the Grover and Shift operator. 2) An
application of these circuits to find the hitting times in cubelike graphs.
Here we implement our circuits on the IBM’s Qiskit platform and verify the
one-shot hitting times in families of cubelike graphs such as hypercubes and
augmented cubes.

This paper is organized as follows: In section 2 we describe the construction
of the discrete time quantum random walk based on the Grover coin operator and
the Shift operator on a cubelike graph. In section 3 we define the one-shot
hitting time of quantum random walks and review the past results. In section 4
we describe our implementation of the efficient circuits for the QRW and
finally in section 5 we apply our efficient circuits to the problem of hitting
times for various cubeike graphs.

##  2\. Discrete-time Quantum Walk on Cubelike graphs

###  2.1. The quantum walk

A discrete-time quantum walk (DTQW) on a graph $\Gamma$ is described by the
evolution of an associated quantum system in a Hilbert space. If $\Gamma$ is
$\Delta$-regular with $N$ vertices, then the associated Hilbert space is the
joint Hilbert space $\mathcal{H}=\mathcal{H}_{C}\otimes\mathcal{H}_{P}$, where
$\mathcal{H}_{C}\cong\mathbb{C}^{\Delta}$ is known as the coin space, and
$\mathcal{H}_{P}\cong\mathbb{C}^{N}$ is known as the position space. Suppose
vertices and edges in $\Gamma$ are labeled by
$\\{v_{0},v_{1},\dots,v_{N-1}\\}$ and
$\\{\alpha_{0},\alpha_{1},\dots,\alpha_{\Delta-1}\\}$, respectively, then the
computational basis of $\mathcal{H}$ is given by

(1) $\\{\ket{\alpha_{k}}\ket{v_{a}}:0\leq k\leq\Delta-1,\;0\leq a\leq N-1\\}.$

This association between $\Gamma$ and $\mathcal{H}$ is such that vertex
$v_{a}$ represents the position state $\ket{v_{a}}$ in $\mathcal{H}_{P}$, and
edge $\alpha_{k}$ represents the coin state $\ket{\alpha_{k}}$ in
$\mathcal{H}_{C}$. The evolution of the system is described by a unitary
operator $U$, called the evolution operator, defined by

(2) $U=S(C\otimes I),$

where, $C$ is the coin operator analogous to $\Delta$-dimensional classical
coin and $S$ is the shift operator that shifts the quantum state
$\ket{\alpha_{k}}\ket{v_{a}}$ to the quantum state
$\ket{\alpha_{k}}\ket{v_{b}}$ such that $\alpha_{k}$ is the label of the edge
$(v_{a},v_{b})$.

$v_{0}$$000$$v_{1}$$001$$v_{3}$$011$$v_{2}$$010$$v_{4}$$100$$v_{5}$$101$$v_{7}$$111$$v_{6}$$110$$\alpha_{0}$$00$$\alpha_{1}$$01$$\alpha_{2}$$10$$\alpha_{1}$$01$$\alpha_{2}$$10$$\alpha_{0}$$00$$\alpha_{2}$$10$$\alpha_{2}$$10$$\alpha_{0}$$00$$\alpha_{1}$$01$$\alpha_{1}$$01$$\alpha_{0}$$00$
(a) $\mathcal{Q}_{3}$

$v_{0}$$v_{1}$$v_{3}$$v_{2}$$v_{4}$$v_{5}$$v_{7}$$v_{6}$$\alpha_{0}$$\alpha_{1}$$\alpha_{3}$$\alpha_{2}$$\alpha_{4}$$\alpha_{1}$$\alpha_{3}$$\alpha_{2}$$\alpha_{4}$$\alpha_{0}$$\alpha_{3}$$\alpha_{4}$$\alpha_{4}$$\alpha_{3}$$\alpha_{0}$$\alpha_{1}$$\alpha_{2}$$\alpha_{1}$$\alpha_{2}$$\alpha_{0}$
(b) $\mathcal{AQ}_{3}$

Figure 1. Pictorial representation of (1(a))
$\mathcal{Q}_{3}=Cay(\mathbb{Z}_{2}^{3},\\{001,010,100\\})$ and (1(b))
$\mathcal{AQ}_{3}=Cay(\mathbb{Z}_{2}^{3},\\{001,010,011,100,111\\})$. In both
the cases, a vertex $x_{2}x_{1}x_{0}$ is represented by $v_{a}$, where
$a=x_{2}2^{2}+x_{1}2^{1}+x_{0}2^{0}$, and an edge $(v_{a},v_{b})$ is
represented by $\alpha_{k-1}$, if $v_{a}\oplus v_{b}$ is the $k$-element of
the corresponding lexicographically ordered generating set. The edge
$\alpha_{k-1}$ is also represented by the binary string (of length 2) of the
integer $k-1$.

###  2.2. Cubelike graphs

A Cayley graph is a graph defined over a pair $(G,\Omega)$, where $G$ is a
finite group and $\Omega$ is a generating set of $G$, with the properties; (1)
$\Omega$ does not contain the identity element, and (2) $\Omega$ is closed
under the group inverse, i.e., $x^{-1}\in\Omega$ for all $x\in\Omega$. The
Cayley graph, denoted by $Cay(G,\Omega)$, is a graph whose vertices are
identified with the elements of $G$ and the edge set is
$\\{(x,y):xy^{-1}\in\Omega\\}$. Clearly, $Cay(G,\Omega)$ is a regular graph on
$N=|G|$ vertices with regularity $\Delta=|\Omega|$. The Cayley graph
$Cay(\mathbb{Z}_{2}^{n},\Omega)$ defined over the Boolean group
$\mathbb{Z}_{2}^{n}$ is called cubelike graph of dimension $n$. For a cubelike
graph $Cay(\mathbb{Z}_{2}^{n},\Omega)$ when the ordering on $\Omega$ is not
specified then we assume the lexicographical ordering, i.e., we assume that
the cubelike graph is given in its canonical form. A vertex
$(x_{n-1},\dots,x_{1},x_{0})\in\mathbb{Z}_{2}^{n}$ is denoted by the binary
string $x_{n-1}\cdots x_{1}x_{0}$, and is given the label $v_{a}$, where
$a=x_{n-1}2^{n-1}+\cdots+x_{1}2^{1}+x_{0}2^{0}$. An edge $(v_{a},v_{b})$ is
labeled by $\alpha_{k-1}$, $1\leq k\leq\Delta$, if the XOR operation of
$v_{a}$ and $v_{b}$, i.e. $v_{a}\oplus v_{b}$, is the $k$-th element
$\Omega(k)$ of $\Omega$. Suppose $2^{m-1}<\Delta\leq 2^{m}$, for some integer
$m$, then the edge labeled by $\alpha_{k-1}$ can be denoted by the $k$-th
binary string $y_{m-1}\cdots y_{1}y_{0}$ in $\mathbb{Z}_{2}^{m}$, i.e.,
$k-1=y_{m-1}2^{m-1}+\cdots+y_{1}2^{1}+y_{0}2^{0}$.

Some special subfamily of cubelike graphs of interest are (a) Hypercubes
$\mathcal{Q}_{n}$ with $\Omega=\\{0^{i}10^{j}:i+j=n-1\\}$, and (b) Augmented
cubes [11] $\mathcal{AQ}_{n}$ with
$\Omega=\\{0^{i}10^{j}:i+j=n-1\\}\cup\\{0^{n-i}1^{i}:1\leq i\leq n\\}$. In
Figure 1(a), edge $(v_{0},v_{4})$ is labeled by $\alpha_{2}$ because
$v_{0}\oplus v_{4}=100$ is the third element of its generating set
$\\{001,010,100\\}$, while in Figure 1(b) it is labeled by $\alpha_{3}$ as
$100$ is the fourth element of its generating set $\\{001,010,011,100,111\\}$.
The binary representations of $\alpha_{0}$, $\alpha_{1}$, $\alpha_{2}$ in
$\mathcal{Q}_{3}$ (Figure 1(a)) are $00$, $01$, $10$, respectively, while in
$\mathcal{AQ}_{3}$ (Figure 1(b)), the binary representations of $\alpha_{0}$,
$\alpha_{1}$, $\alpha_{2}$, $\alpha_{3}$, $\alpha_{4}$ are $000$, $001$,
$010$, $011$, $100$, respectively.

Let $U=S(C\otimes I)$ be the evolution operator for DTWQ on
$Cay(\mathbb{Z}_{2}^{n},\Omega)$, with $\Delta=|\Omega|$. Then, the shift
operator $S$ is defined by

(3)
$S=\sum_{k=1}^{\Delta}\sum_{a=0}^{2^{n}-1}\ket{\alpha_{k-1},v_{a}\oplus\Omega(k)}\bra{\alpha_{k-1},v_{a}},$

Any unitary operator on $\mathbb{C}^{\Delta}$ can be chosen as the coin
operator. A popular coin operator is the Grover coin $C$ which is defined by
$2\ket{D}\bra{D}-I$, where,

(4)
$\ket{D}=\frac{1}{\sqrt{\Delta}}\sum_{k=1}^{\Delta}\ket{\alpha_{k-1}}\implies
C=\begin{bmatrix}\frac{2}{\Delta}-1&\frac{2}{\Delta}&\frac{2}{\Delta}&\cdots&\frac{2}{\Delta}\\\\[14.22636pt]
\frac{2}{\Delta}&\frac{2}{\Delta}-1&\frac{2}{\Delta}&\cdots&\frac{2}{\Delta}\\\\[14.22636pt]
\vdots&\vdots&\vdots&\ddots&\vdots\\\\[14.22636pt]
\frac{2}{\Delta}&\frac{2}{\Delta}&\frac{2}{\Delta}&\cdots&\frac{2}{\Delta}-1\end{bmatrix}.$

In the following example DTQW is illustrated on $C_{4}$, a cycle on four
vertices.

######  Example 1 (Discrete-time quantum walk on
$Cay(\mathbb{Z}_{2}^{2},\\{01,10\\})$).

The Hilbert space associated with the graph is
$\mathbb{C}^{2}\otimes\mathbb{C}^{4}$, and the computational basis is

$\\{\ket{0}\ket{00},\ket{1}\ket{00},\ket{0}\ket{01},\ket{1}\ket{01},\ket{0}\ket{10},\ket{1}\ket{10},\ket{0}\ket{11},\ket{1}\ket{11}\\}.$

The evolution operator $U$ is $S(C\otimes I)$, where,

$C=\begin{bmatrix}0&1\\\ 1&0\end{bmatrix},$

and,

$\begin{split}S&=\sum_{k=1}^{2}\sum_{a=0}^{3}\ket{\alpha_{k-1}}\ket{v_{a}\oplus\Omega(k)}\bra{\alpha_{k-1}}\bra{v_{a}}.\end{split}$

The evolution, with the initial state
$\ket{D}\ket{00}=\frac{\ket{0}+\ket{1}}{\sqrt{2}}\ket{00}$, occurs as:

  1. (1)

The first time step;

$\begin{split}U\ket{D}\ket{00}&=S(C\otimes
I)\left(\frac{1}{\sqrt{2}}(\ket{0}\ket{00}+\ket{1}\ket{00})\right)\\\
&=\frac{1}{\sqrt{2}}\left(\ket{1}\ket{10}+\ket{0}\ket{01}\right).\end{split}$

  2. (2)

The second time step;

$\begin{split}U^{2}\ket{D}\ket{00}&=S\frac{1}{\sqrt{2}}\left[\left(2\frac{\ket{0}+\ket{1}}{\sqrt{2}}\frac{1}{\sqrt{2}}-\ket{1}\right)\ket{10}\right.\\\
&+\left.\left(2\frac{\ket{0}+\ket{1}}{\sqrt{2}}\frac{1}{\sqrt{2}}-\ket{0}\right)\ket{01}\right]\\\
&=S\frac{1}{\sqrt{2}}\left(\ket{0}\ket{10}+\ket{1}\ket{01}\right)=\frac{\ket{0}\ket{11}+\ket{1}\ket{11}}{\sqrt{2}}\\\
&=\ket{D}\ket{11}.\end{split}$

Consequently, we get the probability distribution of the quantum states. After
the first step, the quantum system is at state $\ket{01}$ or $\ket{10}$ with
probability $\frac{1}{2}$, and after two steps the probability of the quantum
system to be at $\ket{11}$ is $1$.

##  3\. Hitting times of quantum walks

The DTQW starts from a particular starting vertex $v_{0}$ and evolves under
the dynamics of the evolution operator given in equations (3) and (4). Letting
the system evolve for a finite number of steps $T$ is equivalent to applying
$U^{T}$ to an initial state $\ket{v_{0}}$ of the system. A measurement is then
performed in the position space basis to see if the walker is found in a
specific target vertex. At time T, if we find the walker in the state
$\ket{v}$ corresponding to the target vertex $v$ with probability at least
$p$, then we say $(T,p)$ is the quantum hitting time for $v$, starting from
vertex $v_{0}$. This hitting time was called the one-shot hitting time defined
by Kempe in [17]. More formally,

######  Definition 1 ([17]).

The discrete-time quantum walk is said to admit $(T,p)$ one-shot
$(\ket{v_{0}},\ket{v})$ hitting time if $|\bra{v}U^{T}\ket{v_{0}}|^{2}\geq p$.

It was shown in [17] that the one-shot hitting time a of quantum random walk
on a hypercube is exponentially faster than its classical analogue. We state
the following result from [17].

######  Theorem 1 ([17]).

The discrete-time quantum walk with Grover coin on the hypercube of dimension
$n$ has a $(T,p)$ one-shot $(\ket{x},\ket{\bar{x}})$ hitting time, i.e.
$\Big{|}\bra{\bar{x}}U^{T}\ket{x}\Big{|}^{2}\geq p$, where $T$ is either
$\lfloor{\frac{\pi}{2}n}\rfloor$ or $\lceil{\frac{\pi}{2}n}\rceil$ and
$p=1-\mathcal{O}(\frac{\log^{3}n}{n})$.

For example, $\mathcal{Q}_{2}$ has $(2,1)$ one-shot $(\ket{00},\ket{11})$
hitting time. The quantum circuit for the DTWQ on $\mathcal{Q}_{2}$ is shown
in Figure 2 [15]. The first two qubits represent the position state which is
initially at zero state $\ket{00}$. The third qubit represents the coin state,
and is initialized to the diagonal state by applying the Hadamard gate $H$.
The composition of the next three operators, namely, two $CNOT$-gates and one
$NOT$-gate, forms the evolution operator $U$. The evolution operator $U$ is
applied twice, which are separated by a dotted vertical line called the
barrier. The following calculations show that the circuit (Figure 2) is indeed
a DTQW on $\mathcal{Q}_{2}$. We use $X(a)$ to denote the X-gate that flips the
value of the qubit $a$, and $C_{X}(a,b)$ to denote the CNOT-gate with control
qubit $a$ and target qubit $b$.

  1. (1)

The system is initialized to $(H\otimes I\otimes I)\ket{000}$, where $I$ is
the identity operator. Since,

$(H\otimes I\otimes
I)\ket{000}=\frac{\ket{000}+\ket{100}}{\sqrt{2}}=\ket{D}\ket{00},$

the system is thus initialized to $\ket{D}\ket{00}$.

  2. (2)

The application of $U$ to this initial state evolves the system to the quantum
state $\frac{\ket{110}+\ket{001}}{\sqrt{2}}$ as shown below.

$\begin{split}\frac{\ket{000}+\ket{100}}{\sqrt{2}}&\xrightarrow{C_{X}(2,0)}\frac{\ket{000}+\ket{101}}{\sqrt{2}}\\\
&\xrightarrow{X(2)}\frac{\ket{100}+\ket{001}}{\sqrt{2}}\\\
&\xrightarrow{C_{X}(2,1)}\frac{\ket{110}+\ket{001}}{\sqrt{2}},\end{split}$

  3. (3)

By applying $U$ to the current state, we see that the system evolves to the
state $\ket{D}\ket{11}$, as shown below.

$\begin{split}\frac{\ket{110}+\ket{001}}{\sqrt{2}}&\xrightarrow{C_{X}(2,0)}\frac{\ket{111}+\ket{001}}{\sqrt{2}}\\\
&\xrightarrow{X(2)}\frac{\ket{011}+\ket{101}}{\sqrt{2}}\\\
&\xrightarrow{C_{X}(2,1)}\frac{\ket{011}+\ket{111}}{\sqrt{2}}=\ket{D}\ket{11}.\end{split}$

Now, the measurement operator outputs $\ket{11}$ with probability $1$. If the
measurement was done after the first application of $U$ and then after the
second application, then, we would have obtained either $\ket{00}$ or
$\ket{11}$ with probability $\frac{1}{2}$.

$\Qcircuit@C=0.5em@R=0.2em@!R{\lstick{{q}_{0}:}&\qw\barrier[0em]{2}\qw\targ\qw\qw\barrier[0em]{2}\qw\targ\qw\qw\barrier[0em]{2}\qw\meter\qw\qw\qw\\\
\lstick{{q}_{1}:}\qw\qw\qw\qw\targ\qw\qw\qw\targ\qw\qw\meter\qw\qw\\\
\lstick{{q}_{2}:}\gate{\mathrm{H}}\qw\ctrl{-2}\gate{\mathrm{X}}\ctrl{-1}\qw\ctrl{-2}\gate{\mathrm{X}}\ctrl{-1}\qw\qw\qw\qw\qw\\\
\lstick{c:}\lstick{/_{{}_{2}}}\cw\cw\cw\cw\cw\cw\cw\cw\cw\cw\dstick{{}_{{}_{0}}}\cw\cwx[-3]\dstick{{}_{{}_{1}}}\cw\cwx[-2]\cw\cw\\\
}$ Figure 2. The quantum circuit for DTWQ on $\mathcal{Q}_{2}$.

##  4\. The Quantum circuit for DTQW on cubelike graphs

A general quantum circuit representing the DTQW on
$Cay(\mathbb{Z}_{2}^{n},\Omega)$, with $\Delta=|\Omega|$, is depicted in
Figure 3. A unitary operator that can be appended to a quantum circuit has
dimension $2^{t}$, for some positive integer $t$. Since the coin operator
acting on the coin space is of dimension $\Delta$, we study the case where
$\Delta=2^{m}$, for some positive integer $m$. All the qubits are initialized
to state $\ket{0}$. The position state is represented by the first $n$ qubits,
which is initially $\ket{v_{0}}=\ket{0}^{\otimes n}$. The coin state,
represented by the last $m$ qubits, is initialized to diagonal state
$\ket{D}=\frac{1}{\sqrt{\Delta}}\sum_{k=1}^{\Delta}\ket{\alpha_{k-1}}$ by
applying the Hadamard gate H to each coin qubit. After the initialization, the
evolution operator $U$, which is the composition of the Grover operator $C$
and the shift operator $S$, is applied to the circuit for a specific number of
times before the measurement is taken. It is important to decompose the
evolution operator to run the circuit more efficiently.

$\Qcircuit@C=1.0em@R=2em{\lstick{\ket{0}}&\qw\barrier[0em]{6}\qw\qw\multigate{6}{\mathrm{Shift}}\qw\cdots\barrier[0em]{6}\qw\qw\multigate{6}{\mathrm{Shift}}\qw\barrier[0em]{6}\qw\meter\qw\qw\qw\qw\\\
\lstick{\ket{1}}\qw\qw\qw\ghost{\mathrm{Shift}}\qw\cdots\qw\qw\ghost{\mathrm{Shift}}\qw\qw\qw\meter\qw\qw\qw\\\
\lstick{\vdots}\vdots\vdots\cdots\vdots\vdots\\\
\lstick{\ket{n-1}}\qw\qw\qw\ghost{\mathrm{Shift}}\qw\cdots\qw\qw\ghost{\mathrm{Shift}}\qw\qw\qw\qw\meter\qw\qw\\\
\lstick{\ket{n}}\gate{\mathrm{H}}\qw\multigate{2}{\mathrm{Grover}}\ghost{\mathrm{Shift}}\qw\cdots\qw\multigate{2}{\mathrm{Grover}}\ghost{\mathrm{Shift}}\qw\qw\qw\\\
\lstick{\vdots}\vdots\ghost{\mathrm{Grover}}\ghost{\mathrm{Shift}}\qw\cdots\qw\ghost{\mathrm{Grover}}\ghost{\mathrm{Shift}}\qw\qw\qw\\\
\lstick{\ket{n+m-1}}\gate{\mathrm{H}}\qw\ghost{\mathrm{Grover}}\ghost{\mathrm{Shift}}\qw\cdots\qw\ghost{\mathrm{Grover}}\ghost{\mathrm{Shift}}\qw\qw\qw\\\
\lstick{c:}\lstick{/_{{}_{n}}}\cw\cw\cw\cw\cw\cw\cw\cw\cw\cw\cw\cw\dstick{/_{{}_{0}}}\cw\cwx[-7]\dstick{1}\cw\cwx[-6]\dstick{n-1}\cw\cwx[-4]\cw\cw\\\
}$ Figure 3. Quantum circuit for DTQW on cubelike graph. H is applied to each
coin qubit to initialize the coin state to $\ket{D}$. The evolution operator
$U=S(C\otimes I)$ is applied for a finite number of times. Each application of
U is separated by a barrier. Finally, measurement operators are applied to the
position qubits.

###  4.1. Decomposition of the evolution operator $U$

####  4.1.1. Decomposition of the Grover operator

The decomposition of the Grover operator $C$ has been discussed in [7, 19]
(see Figure 4), which is;

$C=H^{\otimes m}X^{\otimes m}H\otimes I^{\otimes
m-1}C^{(m-1)}_{X}([0,1,\dots,m-2],m-1)H\otimes I^{\otimes m-1}X^{\otimes
m}H^{\otimes m},$

where, $C^{(m-1)}_{X}(c,t)$ is the generalized Toffoli gate with a set of
$m-1$ control qubits, denoted by $c$, and a target qubit $t$, i.e., it flips
the value of the target only if each qubit in $c$ is at state $\ket{1}$.

$\Qcircuit@C=1em@R=1em{\lstick{\ket{0}}&\gate{\mathrm{H}}\gate{\mathrm{X}}\gate{\iota\mathrm{I}}\ctrl{4}\gate{\iota\mathrm{I}}\gate{\mathrm{X}}\gate{\mathrm{H}}\qw\\\
\lstick{\ket{1}}\gate{\mathrm{H}}\gate{\mathrm{X}}\qw\ctrl{3}\qw\gate{\mathrm{X}}\gate{\mathrm{H}}\qw\\\
\lstick{\vdots}\vdots\vdots\vdots\vdots\\\
\lstick{\ket{m-2}}\gate{\mathrm{H}}\gate{\mathrm{X}}\qw\ctrl{1}\qw\gate{\mathrm{X}}\gate{\mathrm{H}}\qw\\\
\lstick{\ket{m-1}}\gate{\mathrm{H}}\gate{\mathrm{X}}\gate{\mathrm{H}}\targ\gate{\mathrm{H}}\gate{\mathrm{X}}\gate{\mathrm{H}}\qw}$
Figure 4. Decomposition of the Grover operator.

####  4.1.2. Decomposition of the Shift operator

The shift operator $S$ can be expressed as

(5) $S=\sum_{k=1}^{d}S_{k-1},\mbox{ where
}S_{k-1}=\sum_{i=0}^{2^{n}-1}\ket{\alpha_{k-1}}\ket{v_{i}\oplus\Omega(k)}\bra{\alpha_{k-1}}\bra{v_{i}}.$

The operator $S_{k-1}$ shifts the walker only along the edge $\alpha_{k-1}$.
Suppose $\Omega(k)$ has non-zero entries at positions
$p_{1},p_{2},\dots,p_{l}$, then we append the extended Toffoli gates
$C^{(m)}_{X}(c,p_{j}-1)$, $1\leq j\leq l$, to the quantum circuit
corresponding to $S_{k-1}$, where, $c$ is the control consisting of all coin
qubits and $p_{j}$-th position qubit is the target. These gates do not flip
the values of the target qubits unless the coin state $\ket{\alpha_{k-1}}$ is
$\ket{1^{m}}$. Therefore, we need to first apply X gate to each coin qubit
with value zero in $\ket{\alpha_{k-1}}$ and then apply the extended Toffoli
gates. Thus, the sequence of gates appended to the quantum circuit
corresponding to $S_{k-1}$ is given by

(6) $\tilde{S}_{k-1}=(f(k))(C^{(m)}_{X}(c,p_{l}-1)\dots
C^{(m)}_{X}(c,p_{2}-1)C^{(m)}_{X}(c,p_{1}-1)),$

where, $f(k)$ is an operator equivalent to appended X gates that transforms
$\ket{\alpha_{k-1}}$ to $\ket{1^{m}}$. Thus, the sequence of operators
appended to the quantum circuit corresponding to $S$ is

(7) $S\equiv\tilde{S}_{0}\tilde{S}_{1}\cdots\tilde{S}_{d-1}.$

where, $S_{k-1}$, $1\leq k\leq d$, is expressed by equation 6.

######  Example 2.

We can understand the decomposition of the shift operator through an example
of DTQW on $Cay(\mathbb{Z}_{2}^{4},\Omega)$, with
$\Omega=\\{0101,0111,1001,1010\\}$. Suppose the walker is at vertex $v=1101$,
then the shift operation at position state $\ket{v}=\ket{1101}$ is described
as;

(8) $\begin{split}S\ket{\alpha_{0}}\ket{1101}&=\ket{\alpha_{0}}\ket{1101\oplus
0101}=\ket{\alpha_{0}}\ket{1000}\\\
S\ket{\alpha_{1}}\ket{1101}&=\ket{\alpha_{1}}\ket{1101\oplus
0111}=\ket{\alpha_{1}}\ket{1010}\\\
S\ket{\alpha_{2}}\ket{1101}&=\ket{\alpha_{2}}\ket{1101\oplus
1001}=\ket{\alpha_{2}}\ket{0100}\\\
S\ket{\alpha_{3}}\ket{1101}&=\ket{\alpha_{2}}\ket{1101\oplus
1010}=\ket{\alpha_{3}}\ket{0110}.\end{split}$

$\Qcircuit@C=1em@R=1em{\lstick{0}&\qw\targ\qw\barrier[-1em]{5}\qw\targ\qw\qw\barrier[-1em]{5}\qw\targ\barrier[1em]{5}\qw\qw\qw\qw\qw\\\
\lstick{1}\qw\qw\qw\qw\qw\targ\qw\qw\qw\qw\qw\targ\qw\qw\\\
\lstick{2}\qw\qw\targ\qw\qw\qw\targ\qw\qw\qw\qw\qw\qw\qw\\\
\lstick{3}\qw\qw\qw\qw\qw\qw\qw\qw\qw\targ\qw\qw\targ\qw\\\
\lstick{4}\gate{\mathrm{X}}\ctrl{-4}\ctrl{-2}\gate{\mathrm{X}}\ctrl{-4}\ctrl{-3}\ctrl{-2}\gate{\mathrm{X}}\ctrl{-4}\ctrl{-1}\gate{\mathrm{X}}\ctrl{-3}\ctrl{-1}\qw\\\
\lstick{5}\gate{\mathrm{X}}\ctrl{-1}\ctrl{-1}\qw\ctrl{-1}\ctrl{-1}\ctrl{-1}\gate{\mathrm{X}}\ctrl{-1}\ctrl{-1}\qw\ctrl{-1}\ctrl{-1}\qw\\\
}$ Figure 5. The quantum circuit for the shift operator used in DTQW on
$Cay(\mathbb{Z}_{2}^{4},\\{0101,0111,1001,1010\\})$.

The shift operator, mentioned in Equation 8, can be decomposed as shown in
Figure 5. For each edge $\alpha_{k-1}$, $1\leq k\leq 4$, we transform
$\ket{\alpha_{k-1}}$ to $\ket{\alpha_{3}}\equiv\ket{11}$ by applying NOT
gates, and then apply Toffoli gates to flip the value of position qubits
corresponding to non-zero entries in $\Omega(k)$. See Table 1, where we have
illustrated the transformation of coin qubits. The shift along each direction
is given by;

(9) $\begin{split}S_{0}&=(X\otimes
X)(C^{(2)}_{X}([4,5],0)C_{X}^{(2)}([4,5],2))\\\ S_{1}&=(I\otimes
X)(C_{X}^{(2)}([4,5],0)C_{X}^{(2)}([4,5],1)C_{X}^{(2)}([4,5],2))\\\
S_{2}&=(X\otimes X)(C_{X}^{(2)}([4,5],0)C_{X}^{(2)}([4,5],3))\\\
S_{3}&=(I\otimes X)(C_{X}^{(2)}([4,5],1)C_{X}^{(2)}([4,5],3))\end{split}$

| $X\otimes X$ | $I\otimes X$ | $X\otimes X$ | $I\otimes X$
---|---|---|---|---
00 | 11 | 10 | 01 | 00
01 | 10 | 11 | 00 | 01
10 | 01 | 00 | 11 | 10
11 | 00 | 01 | 10 | 11
Table 1. Transforming each coin state $\ket{\alpha_{k-1}}$, $1\leq k\leq 4$,
to $\ket{11}$ by applying NOT gates.

We now discuss how we keep track of changes made to each coin state while
implementing the shift operation. For $y\in\mathbb{Z}_{2}^{m}$, define
permutations $P_{y}$ by

$P_{y}(x)=y\oplus x,\;\forall x\in\mathbb{Z}_{2}^{m}.$

We construct a sequence of binary strings
$B(\alpha_{k-1})=0^{m-r_{k}}1^{r_{k}}$, $1\leq k\leq 2^{m}$, where $m-r_{k}$
is the position of the last non-zero bit of the $k$-th binary string
$\alpha_{k-1}$ in $\mathbb{Z}_{2}^{m}$. Note that $B(0^{m})=1^{m}$.

Claim:

(10)
$P_{B(\alpha_{k-1})}(P_{B(\alpha_{k-2})}(\cdots(P_{B(\alpha_{0})}(\alpha_{k-1}))\cdots))=1^{m}.$

If the claim is true, then $f(k)=I^{m-r_{k}}X^{r_{k}}$, $1\leq k\leq 2^{m}$,
transforms each coin state $\ket{\alpha_{k-1}}$ to $\ket{1^{m}}$, one at a
time and therefore the operator given by Equation 6 is correct.

We now prove the claim by induction on $k$. For $k=1$, we have
$\alpha_{0}=0^{m}$ and $B(\alpha_{0})=1^{m}$. Thus,

$P_{B(\alpha_{0})}(\alpha_{0})=1^{m}\oplus 0^{m}=1^{m}.$

Assume that at $k$-th iteration, $\alpha_{k-1}$ gets transformed to $1^{m}$.
Since $\alpha_{k-1}$ and $\alpha_{k}$ differ at the last $r$ positions, for
some $1\leq r\leq m$, $\alpha_{k}$ gets transformed to $1^{m-r}0^{r}$ at
$k$-th iteration. Therefore, $B(\alpha_{k})=0^{m-r}1^{r}$ and at $(k+1)$-th
iteration we get $B(\alpha_{k})\oplus\alpha_{k}=1^{m}$. Hence, the claim is
True.

Notice that, the transformation of a coin state corresponding to an edge
alters other coin states corresponding to other edges. At the end of the shift
operation in Example 2 we retrieve the original generic coin state as shown in
the last column of Table 1. Indeed, after the $2^{m}$-th iterations, notice
that the $i$-bit of $\alpha_{k-1}$, $1\leq i\leq m$ and $1\leq k\leq 2^{m}$,
flips only if $B(\alpha_{j-1})$, $1\leq j\leq 2^{m}$, is of the form
$0^{m-s}1^{s}$, with $s\geq i$, which corresponds to a binary string $e_{j-1}$
of the form $x_{m-1}\cdots x_{i}0^{i}$. Since the number of such binary
strings are $2^{m-i}$, the $i$-th bit of $\alpha_{k-1}$ flips even number of
times. Therefore, each coin state $\ket{\alpha_{k-1}}$, $1\leq k\leq 2^{m}$,
remains unchanged after the $2^{m}$-th iterations. Therefore, the shift
operation is performed successfully without altering the coin state.

####  4.1.3. Analysis of the quantum circuit for the shift operator

The number of $X$ gates $Num(X)$ used in the decomposition of the shift
operator is equal to

(11) $Num(X)=\sum_{x\in\mathbb{Z}_{2}^{m}}wt(B(x))=2^{m+1}-2,$

where $wt(B(x))$ is the Hamming weight of $B(x)$. This can be proved by
induction on $m$. For $m=1$, $Num(X)=2$ because $B(0)=1$ and $B(1)=1$. Assume
by way of induction that, for $m=k$, $Num(X)=2^{k+1}-1$. Then, for $m=k+1$,
notice that if $x\in\mathbb{Z}_{2}^{m}$ then $0x,1x\in\mathbb{Z}_{2}^{m+1}$
and,

(12) $B(bx)=\begin{cases}B(x),&\mbox{if }x\neq 0^{m}\\\ B(x)+1,&\mbox{if
}x=0^{m}.\end{cases}$

where $b=0$ or $1$. Therefore, $Num(X)$ for $m=k+1$ is equal to

$2\times(2^{k+1}-2)+2=2^{k+2}-2.$

$Num(X)$ is of order $\mathcal{O}(|\Omega|)$. The number of generalized
Toffoli gates used is equal to the sum of Hamming weights of all elements of
the generating set $\Omega$, which is

(13) $Num(C^{(m)}_{X})=\sum_{x\in\Omega}wt(x),\qquad wt(x)=\mbox{number of 1's
in }x.$

###  4.2. Quantum circuit for cubelike graph of arbitrary degree

If the degree of the cubelike graph is not a power of $2$ (for example
$Q_{3}$) then we have to make certain modifications to implement our circuit.
Consider a cubelike graph $Cay(\mathbb{Z}_{2}^{n},\Omega)$, with
$\Delta=|\Omega|$. Let $m$ be a positive integer satisfying
$2^{m-1}<\Delta\leq 2^{m}$. The Grover coin $C=2\ket{D}\bra{D}-I$ is a
$\Delta\times\Delta$ matrix, where $\Delta$ may not be equal to $2^{m}$. We,
therefore, define a new $2^{m}\times 2^{m}$ operator $C^{\prime}$ by

(14) $C^{\prime}=\begin{bmatrix}2\ket{D}\bra{D}&\textbf{0}\\\
\textbf{0}&\textbf{0}\end{bmatrix}-I=2\ket{D^{\prime}}\bra{D^{\prime}}-I,$

where,
$\ket{D^{\prime}}=\frac{1}{\sqrt{\Delta}}\sum_{k=1}^{\Delta}\ket{\alpha_{k-1}}\in\mathbb{C}^{2^{m}}$
is a projection of the diagonal state $\ket{D}$ in the higher dimensional
Hilbert space $\mathcal{H}_{C^{\prime}}=\mathbb{C}^{2^{m}}$ that contains the
coin space $\mathcal{H}_{C}=\mathbb{C}^{\Delta}$ as a subspace. In other
words, $\mathcal{H}_{C^{\prime}}$ is a new coin space with the computational
basis $\\{\ket{\alpha_{k-1}}:1\leq k\leq 2^{m}\\}$, and the quantum walk
occurs in $Cay(\mathbb{Z}_{2}^{n},\Omega^{\prime})$, where $\Omega^{\prime}$
has $2^{m}$ elements containing $\Omega$, i.e.,
$Cay(\mathbb{Z}_{2}^{n},\Omega)$ is a subgraph of
$Cay(\mathbb{Z}_{2}^{n},\Omega^{\prime})$. The new coin operator $C^{\prime}$
changes the coefficients of the initialized vector, which is
$\ket{D^{\prime}}$, and therefore, the coefficents of coin states
$\ket{\alpha_{k-1}}$, with $k\geq d+1$, remain $0$ throughout the evolution,
i.e. the generic coin state $\ket{c}$, in our case, is

(15)
$\ket{c}=\sum_{k=1}^{\Delta}\lambda_{k}\ket{\alpha_{k-1}}+\sum_{k=\Delta+1}^{2^{m}}\ket{\alpha_{k-1}}.$

We define a new shift operator $S^{\prime}$ by

(16)
$S^{\prime}=\sum_{k=1}^{\Delta}\sum_{a=0}^{2^{n}-1}\ket{\alpha_{k-1}}\ket{v_{a}\oplus\Omega(k)}\bra{\alpha_{k-1}}\bra{v_{a}}+\sum_{k=\Delta+1}^{2^{m}}\sum_{a=0}^{2^{n}-1}\ket{\alpha_{k-1}}\ket{v_{a}}\bra{\alpha_{k-1}}\bra{v_{a}}.$

$\Qcircuit@C=1em@R=1em{\lstick{0}&\qw\targ\qw\qw\qw\qw\qw\qw\\\
\lstick{1}\qw\qw\qw\targ\qw\qw\qw\qw\\\
\lstick{2}\qw\qw\qw\qw\qw\targ\qw\qw\\\
\lstick{3}\gate{\mathrm{X}}\ctrl{-3}\gate{\mathrm{X}}\ctrl{-2}\gate{\mathrm{X}}\ctrl{-1}\gate{\mathrm{X}}\qw\\\
\lstick{4}\gate{\mathrm{X}}\ctrl{-1}\qw\ctrl{-1}\gate{\mathrm{X}}\ctrl{-1}\qw\qw}$
Figure 6. Quantum circuit for $Q_{3}$

The new shift operator $S^{\prime}$ fixes $\ket{\alpha_{k-1}}\ket{v_{a}}$,
$0\leq a\leq 2^{n}-1$, if $k\geq\Delta+1$, i.e.,
$S^{\prime}\ket{\alpha_{k-1}}\ket{v_{a}}=\ket{\alpha_{k-1}}\ket{v_{a}}$. The
Figure 6 represents the quantum circuit for $\mathcal{Q}_{3}$. Notice that the
circuit does not shift a position state along the direction
$\ket{\alpha_{3}}\equiv\ket{11}$. Finally, the original coin state is
retrieved at the end of the shift operation because each quantum wire contains
even number of X gates.

##  5\. Application to hitting times on cubelike graphs

We use Qiskit [1] to implement DTQW on IBM’s Quantum simulators and quantum
computers. The Qiskit simulator qasm_simulator runs locally and other IBM’s
simulators such as simulator_mps, simulator_extended_stabilizer, etc, are
accessed via IBM provider ibm-q.

###  5.1. DTQW on Quantum computers

The quantum circuit for DTWQ on $\mathcal{Q}_{2}$, see Figure 2, was run on
IBM’s quantum computer ibmq_manila v1.0.3, the result of which is compared
with the result on qasm_simulator, as shown in Figure 7. The quantum circuits
corresponding to higher dimensional cubelike graphs could not be run
successfully on real quantum computers due to unavoidable gate errors and
noise from the environment around the quantum computer. In case of
$\mathcal{Q}_{3}$, the errors and noise were low and therefore could be run
successfully.

###  5.2. Hitting times of Hypercubes and Augmented cubes

Upon implementing quantum circuits for DTQW on cubelike graphs, we have
observed that the specific vertex, called the target vertex, to which the
walker reach with highest probability, is unique and equal to the binary XOR
operations of elements of the generating set $\Omega$, i.e.,

(17) $\mbox{target vertex }=\bigoplus_{x\in\Omega}x.$

(a)

(b)

Figure 7. Probability distribution of DTQW on $\mathcal{Q}_{2}$ after two
steps when run on Qiskit simulator (7(a)) qasm_simulator and on IBM’s quantum
computer (7(b)) ibmq_manila.

(a) DTQW on $\mathcal{Q}_{3}$ with steps $T=3$, target vertex $7\equiv 111$,
and target probability $0.804$.

(b) DTQW on $\mathcal{AQ}_{3}$ with steps $T=9$, target vertex $3\equiv 011$,
and target probability $0.812$.

Figure 8. Probability distribution of Hypercubes and Augmented cubes of
dimension $3$. Target vertices correspond to the tallest bar in each bar
graph.

(a) DTQW on $\mathcal{Q}_{4}$ with steps $T=6$, target vertex $15\equiv 1111$,
and target probability $0.562$.

(b) DTQW on $\mathcal{AQ}_{4}$ with steps $T=11$, target vertex $4\equiv
0100$, and target probability $0.993$.

(c) DTQW on $\mathcal{Q}_{5}$ with steps $T=7$, target vertex $31\equiv
11111$, and target probability $0.722$.

(d) DTQW on $\mathcal{AQ}_{5}$ with steps $T=13$, target vertex $11\equiv
01011$, and target probability $0.953$.

Figure 9. Probability distribution of Hypercubes and Augmented cubes of
dimension $4$ and $5$.

$n=\Delta$ | T | Target | $p$
---|---|---|---
3 | 3 | $111$ | 0.804
4 | 6 | $1111$ | 0.562
5 | 7 | $11111$ | 0.722
6 | 10 | $1^{6}$ | 0.816
7 | 11 | $1^{7}$ | 0.912
8 | 12 | $1^{8}$ | 0.954
9 | 13 | $1^{9}$ | 0.950
10 | 14 | $1^{10}$ | 0.901
11 | 17 | $1^{11}$ | 0.927
12 | 18 | $1^{12}$ | 0.956
13 | 19 | $1^{13}$ | 0.947
14 | 22 | $1^{14}$ | 0.929
15 | 23 | $1^{15}$ | 0.961
16 | 24 | $1^{16}$ | 0.960
Table A.  $\mathcal{Q}_{n}$.

n | $\Delta$ | T | Target | $p$
---|---|---|---|---
3 | 5 | 9 | $011$ | 0.812
4 | 7 | 11 | $0100$ | 0.993
5 | 9 | 13 | $01011$ | 0.953
6 | 11 | 17 | $(01)^{2}00$ | 0.928
7 | 13 | 19 | $(01)^{3}1$ | 0.919
8 | 15 | 23 | $(01)^{3}00$ | 0.969
9 | 17 | 25 | $(01)^{4}1$ | 0.926
10 | 19 | 29 | $(01)^{4}00$ | 0.955
11 | 21 | 31 | $(01)^{5}1$ | 0.919
12 | 23 | 35 | $(01)^{5}00$ | 0.954
13 | 25 | 39 | $(01)^{6}1$ | 0.958
14 | 27 | 41 | $(01)^{6}00$ | 0.962
15 | 29 | 45 | $(01)^{7}1$ | 0.977
16 | 31 | 47 | $(01)^{7}00$ | 0.961
Table B.  $\mathcal{AQ}_{n}$.

In Table B and Table B, $n$ denotes dimension of $\mathcal{Q}_{n}$ and
$\mathcal{AQ}_{n}$. $T$ is the hitting time with probability $p$, and $\Delta$
is the degree.

(a)

(b)

Figure 10. Plot of the hitting time $T$ vs the degree (10(a)) $|\Omega|=n$ of
the Hypercube and (10(b)) $|\Omega|=2n-1$ of the Augmented cube.

In Figure 8 and 9 the target probabilities for Augmented cubes are higher than
that of Hypercubes of same dimensions. In either case, the target probability
gets closer to $1$ as the dimension increases. In Table B and B, we have
displayed the hitting time $T$ along with target and target probability
corresponding to dimensions of $\mathcal{Q}_{n}$ and $\mathcal{AQ}_{n}$. In
case of Hypercubes, $T$ is linear with $n$ that tallies with the theoretical
result stated by Kempe in [17], while in Augmented cubes it is linear with the
degree of the graph. See Figure 10(b), where we have shown that $T$ is linear
with the degree $2n-1$ of $\mathcal{AQ}_{n}$.

(a)

(b)

(c)

(d)

(e)

(f)

Figure 11. Plots of steps T required to attain the target probability verses
the degree $|\Omega|$ of cubelike graphs of degree $n+k$, where $k$ is fixed
and $n$ is the dimension.

###  5.3. A conjecture on hitting times of general cubelike graphs

The result mentioned by J. Kempe in [17] can be generalized to other cubelike
graphs. In Figure 11 and 12 we have shown plots of steps T verses degrees
$n+k$ of some cubelike graphs, where $T$ is the number of iterations required
to hit the target vertex, and $n$ is the dimension of cubelike graph of degree
$n+k$. In the first figure, we fix the value of $k$ and increase $n$, and in
the second figure, we fix the dimension $n$ and increase the value of $k$. In
either case, we find that $T$ verses $n+k$ plot is linear and follows the
relation;

(18) $T\approx(n+k)\times\pi/2.$

It is to be noted that it is just a coincidence that $T$ vs dimension plot is
same as $T$ vs degree plot for DTQW on Hypercubes.

(a)

(b)

(c)

(d)

Figure 12. Plots of steps T requried to attain the target probability verses
the degree $|\Omega|=n+k$ of cubelike graphs of fixed dimension n.

The observations and remarks made above lead to the following conjecture.

######  Conjecture 1.

Let $\Gamma=Cay(\mathbb{Z}_{2}^{n},\Omega)$ be an $n$-dimensional Cubelike
graph with degree $\Delta=|\Omega|$. Define the target vertex by;

(19) $v_{targ}=\bigoplus_{x\in\Omega}x.$

Then, there exists a hitting time $T\approx\frac{\pi\Delta}{2}$ such that the
target probability $p_{targ}$, the probability by which DTWQ reaches
$v_{targ}$, is asymptotically equal to 1. Moreover, the parity of $T$ is same
as that of $\Delta$, i.e., $T$ is even only if $\Delta$ is even.

##  6\. Conclusion

Quantum random walks and their hitting times are an important area of study in
quantum computation due to their applications in development of faster quantum
algorithms. In this paper we have implemented efficient quantum circuits for
discrete quantum random walks on families of cubelike graphs such as
hypercubes and augmented cubes. Our implementations show that the hitting-
times of all cubelike graphs is asymptotically linear in the degree $\Delta$
of the graphs. That is, for the hitting time $\frac{\pi\Delta}{2}$,
probability that the walker is found at the target vertex approaches $1$ as
$\Delta$ approaches infinity. Our circuits run on IBM’s quantum computing
platform Qiskit, both on real quantum computers as well as simulators.

We note that $T\approx\frac{\Delta\pi}{2}$ is not necessarily the minimum
hitting time or its multiple for a $\Delta$-regular cubelike graph. For
example, in DTQW on $\mathcal{Q}_{3}$, see Figure 13, the walker hits the
target vertex $\ket{111}$ after steps $T=23$ with probability 1. Another
example is that of a complete graph. The cubelike graphs
$Cay(\mathbb{Z}_{2}^{n},\Omega)$, with
$\Omega=\mathbb{Z}_{2}^{n}\backslash\\{0^{n}\\}$, are complete graphs. In
Figure 14, the hitting time for the complete graphs on $2^{n}$ vertices has
been shown constant with the value $T=4$, with target probability equal to 1,
irrespective of dimensions and degrees of the graphs. We have theoretically
verified that $T=4$ is the minimum hitting time with the target probability
equal to 1 for the complete graphs on $2^{n}$ vertices. It will of interest to
find other hitting times for a cubelike graph, specially the minimum one for
which the walker hit the target with high probability or with probability
equal to $1$.

Figure 13. Probability distribution of $\mathcal{Q}_{3}$ after step $T=23$.
Figure 14. Plot for hitting time $T$ verses degree $2^{n}-1$ of complete graph
on $2^{n}$ vertices.

Further, it would be interesting to study the same problem on other types of
regular graphs particularly cayley graphs that are not cubelike graphs.
Another implementation problem to study along the same lines is of perfect
state transfer on regular graphs in the continuous time random walks. It would
be interesting to build efficient quantum circuits for the perfect state
transfer problem.

## References

  * [1] Abraham, H., and et. al. Qiskit: An open-source framework for quantum computing, 2019.
  * [2] Acasiete, F., Agostini, F., Khatibi Moqadam, J., and Portugal, R. Implementation of quantum walks on ibm quantum computers.  Quntum Information Processing 19, 426 (2020).
  * [3] Acevedo, O. L., and Gobron, T. Quantum walks on cayley graphs.  Journal of Physics A: Mathematical and General 39, 3 (Dec 2005), 585–599.
  * [4] Aharonov, D., Ambainis, A., J., K., and Vazirani, U. Quantum walks on graphs.  Proceedings of ACM Symposium on Theory of Computation (STOC’01) (2001), 50–59.
  * [5] Aharonov, Y., Davidovich, L., and N., Z. Quantum random walks.  Phys. Rev. A 48(2), 6 (1993), 1687–1690.
  * [6] Ambanis, A. Quantum walks and their algorithmic applications.  International Journal of Quantum Information 1 (2003), 507–518.
  * [7] Batty, M., Braunstein, S., Duncan, A., and Rees, S. Quantum algorithms in group theory.
  * [8] Bernasconi, A., Godsil, C., and Severini, P. Quantum networks on cubelike graphs.  Phys. Rev. A 78, 052320 (2008).
  * [9] Cheung, W., and Godsil, C. Perfect state transfer in cubelike graphs.  Linear Algebra and its Applications 435 (2011), 2468–2474.
  * [10] Childs, A. Universal computation by quantum walk.  Phys. Rev. Lett. 102:180501 (2009).
  * [11] Choudum, S., A., and Sunitha, V. Augmented cubes.  Networks 40(2) (2002), 71–84.
  * [12] Farhi, E., and Gutmann, S. Quantum computation and decision trees.  Phys. Rev. A 58, 2 (1998), 915–928.
  * [13] Georgopoulos, K., Emary, C., , and Zuliani, P. Comparison of quantum-walk implementations on noisy intermediate-scale quantum computers.  Phys. Rev. A 103, 022408 (2021).
  * [14] Godsil, C. State transfer on graphs.  Discrete Mathematics 312(1) (2012), 129–147.
  * [15] J., A., and et. al. Quantum algorithm implementations for beginners, 2020.
  * [16] Kempe, J. Quantum random walks: An introductory overview.  Contemporary Physics 44, 4 (2003), 307–327.
  * [17] Kempe, J. Quantum random walks hit exponentially faster.  Probability Theory and Related Fields 133(2) (2005), 215–235.
  * [18] Knight, P., Roldán, E., and Sipe, J. Optical cavity implementations of the quantum walk.  Optics Communications 227 (2003), 147–157.
  * [19] Lavor, C., Manssur, L., and Portugal, R. Grover’s algorithm: Quantum database search.  arXiv: Quantum Physics (02 2003).
  * [20] Lovett, N., Cooper, S., Everitt, M., Trevers, M., and Kendon, V. Universal quantum computation using the discrete-time quantum walk.  Phys. Rev. A 81(4):042330 (2010).
  * [21] Lovász, L. Random walks on graphs: A survey, 1993.
  * [22] Moore, C., and Russell, A. Quantum walks on the hypercube.  In Randomization and Approximation Techniques in Computer Science (Berlin, Heidelberg, 2002), J. D. P. Rolim and S. Vadhan, Eds., Springer Berlin Heidelberg, pp. 164–178.
  * [23] Portugal, R. Quantum Walks and Search Algorithms.  Springer Publishing Company, Incorporated, 2013.
  * [24] Roldán, E., and Soriano, J. Optical implementability of the two-dimensional quantum walk.  Journal of Modern Optics 52 (2005), 2649–2657.
  * [25] Venegas-Andraca, S. E. Quantum walks: a comprehensive review.  Quantum Information Processing 11, 5 (2012), 1015–1016.
  * [26] Wanzambi, E., and Anderson, S. Quantum computing: Implementing hitting time for coined quantum walks on regular graphs.  https://arxiv.org/pdf/2108.02723.pdf (2021).
  * [27] Xue, P., Sanders, C., and Leibfried, D. Quantum walk on a line for a trapped ion.  Phys. Rev. Lett. 103(18):183602 (2009).


# Free Products of Trialgebras

Juwei Huang  J.H., School of Mathematical Sciences, South China Normal
University, Guangzhou 510631, P. R. China<EMAIL_ADDRESS>,  Yuqun Chen†
Y.C., School of Mathematical Sciences, South China Normal University,
Guangzhou 510631, P. R. China<EMAIL_ADDRESS>and  Zerui Zhang∗ Z.Z.,
School of Mathematical Sciences, South China Normal University, Guangzhou
510631, P. R. China<EMAIL_ADDRESS>
###### Abstract.

We apply the method of Gröbner-Shirshov bases for replicated algebras
developed by Kolesnikov to offer a general approach for constructing free
products of trialgebrs (resp. trioids). In particular, the open problem of
Zhuchok on constructing free products of trioids is solved.

###### Key words and phrases:

Gröbner-Shirshov basis, trialgebra, trioid, dimonoid, free product

AMS 2020 Subject Classification. 17A61, 16S15, 20M10

† Supported by the NNSF of China (11571121, 12071156)

∗ Supported by the fellowship of China Postdoctoral Science Foundation
2021M691099 and the Young Teacher Research and Cultivation Foundation of South
China Normal University 20KJ02

∗ Corresponding author

##  1\. Introduction

Gröbner and Gröbner–Shirshov bases theory was first introduced by Buchberger
[6] for commutative algebras and independently by Shirshov [15] for Lie
algebras. Then it was developed for various kind of algebras in the last tens
of years under the name of Gröbner bases theory or Gröbner–Shirshov bases
theory. We refer to the survey [2] for more interesting history. This theory
has become an effective computational tool in algebras, especially for those
defined by generators and relations. In particular, if we use generators and
relations to construct free products of certain algebras, trialgebras for
instance, this theory turns out to be useful.

Associative dialgebras (dialgebras, for short) and associative trialgebras
(trialgebras, for short) are generalizations of associative algebras by
applying certain “replication procedure” [10]. Kolesnikov [10] established the
Gröbner-Shirshov bases method for various replicated algebras such as
dialgebras, trialgebras and Leibniz algebras. In particular, he showed that
every dialgebra or trialgebra can be embedded into its universal enveloping
associative algebra. This fact on embedding turns out to be very useful in
constructing free products of dialgebras or trialgebras.

Dimonoids [12] and trioids [13] are generalizations of semigroups. Trioids
have close relationships with Hopf algebras [14], Leibniz 3-algebras [7] and
Rota-Baxter operators [9]. Dimonoids and trioids are interesting subjects, for
instance, see [3, 8, 12, 13, 19, 20, 21, 11]. Loday and Ronco [13] constructed
a free trioid of rank 1, which can be easily generalized to the case of
arbitrary rank, see also [20]. Trioids satisfying some identities are also
studied, Zhuchok [16] constructed free commutative trioids. Free products of
two dialgebras were constructed in [3], free products of arbitrary dimonoids
were constructed in [17] and free products of arbitrary doppelsemigroups were
constructed in [18]. One of the open problems raised by Zhuchok in [16] is how
to construct free products of arbitrary trioids. The aim of this article is to
solve this problem.

The paper is organized as follows: We first recall the Gröbner-Shirshov bases
theory for associative algebras. Then we recall the embeddings of dialgebras
or trialgebras into their universal enveloping associative algebras. Finally,
based on this embedding, we construct a linear basis for a free products of
arbitrary trialgebras. As a special case, if all the trialgebras are trioid
algebras, then the linear basis we obtained will be a set of normal forms of
elements for a free product of trioids.

##  2\. Gröbner-Shirshov bases theory for trialgebras and dialgebras

The main aim of this article is to offer a general approach for constructing
free products of dialgebras or trialgebras or trioids. The method we applied
here is the Gröbner-Shirshov bases theory for dialgebras or trialgebras which
is established by Kolesnikov [10]. Kolesnikov showed that every dialgebra or
trialgebra can be embedded into its universal enveloping associative algebra
[10], in particular, this holds for free products of arbitrary dialgebras or
trialgebras. In light of this, we shall first construct the universal
enveloping associative algebra of the desired free products of certain
algebras, which in turn indicates a linear basis of a free product of
dialgebras or trialgebras.

The aim of this section is to recall the Gröbner-Shirshov bases theories for
associative algebras and trialgebras, respectively.

###  2.1. Gröbner-Shirshov bases theory for associative algebras

Roughly speaking, the method of Gröbner-Shirshov bases for various algebras is
a special kind of rewriting rule. In general, one first construct a linear
basis for the free algebra under consideration, then for the linear basis, one
introduce some well-order which is more or less compatible with the operations
of the algebra. Finally, one study the leading monomial of elements of an
ideal generated by a set. And the key lies in the conditions under which one
can “reduce” every element into a linear combination of the linear basis of
the quotient algebra. Now we recall the Gröbner-Shirshov bases for associative
algebras.

Let $X$ be a well-ordered set and let $k\langle X\rangle$ be the free
associative algebra generated by $X$ over a field $k$. Denote by $X^{*}$ the
free monoid generated by $X$, which consists of all words (i.e., sequences) on
$X$ including the empty word (denoted by $\varepsilon$). Clearly, $X^{*}$
forms a linear basis for $k\langle X\rangle$.

For every word $u=x_{i_{1}}x_{i_{2}}...x_{i_{n}}\in X^{*}$, where the letters
$x_{i_{1}},...,x_{i_{n}}$ lie in $X$, we define the _length_ $\ell(u)$ of $u$
to be $n$, in particular, we have $\ell(\varepsilon)=0$. We recall that the
deg-lex order (degree-lexicographic order) on $X^{*}$ is defined as follows:
for all words $u=x_{i_{1}}x_{i_{2}}...x_{i_{m}}$, and
$v=x_{j_{1}}x_{j_{2}}...x_{j_{n}}\in X^{*}$, where $x_{i_{l}},~{}x_{j_{t}}\in
X$, we define

$u>v\ \ \ \ \mbox{if}\
(\ell(u),x_{i_{1}},x_{i_{2}},...,x_{i_{m}})>(\ell(v),x_{j_{1}},x_{j_{2}},...,x_{j_{n}})\
\mbox{lexicographically}.$

In particular, if $u$ is not the empty word, then we have $u>\varepsilon$. A
well order $>$ on $X^{*}$ is called monomial if for all words
$u,v,w_{1},w_{2}\in X^{*}$, we have

$u>v\Rightarrow w_{1}uw_{2}>w_{1}vw_{2}.$

Clearly, the above deg-lex order on $X^{*}$ is a monomial order.

For every nonzero polynomial $f=\sum_{i=1}^{n}\alpha_{i}u_{i}\in k\langle
X\rangle$, where $0\neq\alpha_{i}\in k$, $1\leq i\leq n$,
$u_{1},\dots,u_{n}\in X^{*}$ and $u_{1}>u_{2}>...>u_{n}$, we call $u_{1}$ the
leading monomial of $f$, denoted by $\overline{f}$; and call $\alpha_{1}$ the
_leading coefficient_ of $f$, denoted by $\mathsf{lc}(f)$. A polynomial $f$ is
called _monic_ if $\mathsf{lc}(f)=1$, and a nonempty subset $S$ of $k\langle
X\rangle$ is called _monic_ if every element in $S$ is monic. For every
$S\subseteq k\langle X\rangle$, define

$\overline{S}=\\{\bar{s}\mid s\in S\\}.$

And for every set $U,V\subseteq X^{*}$, define

$UV=\\{uv\mid u\in U,v\in V\\}.$

Denote by $\mathsf{Id}(S)$ the ideal of $k\langle X\rangle$ generated by $S$.
For convenience, we define $\bar{0}=0$ and define $0<u$ for every $u\in
X^{*}$.

A monic set $S$ is called a _Gröbner-Shirshov basis_ in $k\langle X\rangle$
for the quotient algebra $k\langle X|S\rangle:=k\langle
X\rangle/\mathsf{Id}(S)$, if for every nonzero polynomial $f\in\mathsf{Id}(S)$
, there exists some words $u,v\in X^{*}$ and some element $s\in S$ satisfying
$\bar{f}=u\bar{s}v$. By this definition, it is in general not easy to see
whether a set $S$ is a Gröbner-Shirshov basis for $k\langle X|S\rangle$, so in
practice, we usually consider the following special elements in the ideal
generated by $S$: For all $f,g\in S$, (i) If there exist words $u,v\in X^{*}$
such that $\bar{f}=u\bar{g}v$, then $(f,g)_{\bar{f}}=f-ugv$ is called an
inclusion composition of $f$ and $g$ with respect to $\bar{f}$; (ii) If there
exist words $u,v\in X^{*}$ such that $\bar{f}u=v\bar{g}$ and
$1\leq\ell(u)<\ell(\bar{g})$, then $(f,g)_{\bar{f}u}=fu-vg$ is called an
intersection composition of $f$ and $g$ with respect to $\bar{f}u$. If all the
compositions of the form $(f,g)_{w}$ can be written as linear combinations of
elements of the form $u_{i}s_{i}v_{i}$ satisfying
$u_{i}\overline{s_{i}}v_{i}<w$, where all $u_{i},v_{i}$ lie in $X^{*}$ and
each $s_{i}$ lies in $S$, then the composition $(f,g)_{w}$ is called trivial.

The following result was implicitly proved in [15], and independently proved
in [1], see also [5, 4]. By this lemma, in order to see whether a set $S$
forms a Gröbner-Shirshov basis for $k\langle X|S\rangle$, it suffices to
calculate all the possible compositions.

######  Lemma 2.1.

[15, 1, 5, 4] Let $S$ be a monic subset of $k\langle X\rangle$ and let
$\mathsf{Id}(S)$ the ideal of $k\langle X\rangle$ generated by $S$. Then the
following statements are equivalent.

(i) All the compositions of elements in $S$ are trivial.

(ii) The set $S$ is a Gröbner-Shirshov basis for $k\langle X|S\rangle$, that
is, for every nonzero polynomial $f\in\mathsf{Id}(S)$, we have
$\bar{f}=u\bar{s}v$ for some element $s\in S$ and for some words $u,v\in
X^{*}$.

(iii) $\mathsf{Irr}(S):=\\{u+\mathsf{Id}(S)\mid u\in X^{*}\setminus
X^{*}\overline{S}X^{*}\\}$ forms a $k$-basis of the quotient associative
algebra $k\langle X|S\rangle$.

Now we recall a known fact on Gröbner-Shirshov bases for associative algebras,
and we omit the proof since it is quite similar to those for Lemmas 3.5 and
3.2.

######  Lemma 2.2.

Let $\\{k\langle Y_{i}|U_{i}\rangle\mid i\in I\\}$ be a family of associative
algebras such that $Y_{i}\cap Y_{j}=\emptyset$ for all distinct $i,j\in I$. If
for every $i\in I$, $U_{i}$ is a Gröbner-Shirshov basis for $k\langle
Y_{i}|U_{i}\rangle$, then $\cup_{i\in I}U_{i}$ forms a Gröbner-Shirshov basis
for $k\langle\cup_{i\in I}Y_{i}|\cup_{i\in I}U_{i}\rangle$. In particular, for
every index $j\in I$, $k\langle Y_{j}|U_{j}\rangle$ is isomorphic to the
subalgebra of $k\langle\cup_{i\in I}Y_{i}|\cup_{i\in I}U_{i}\rangle$ generated
by $\\{y_{j}+\mathsf{Id}(\cup_{i\in I}U_{i})\mid y_{j}\in Y_{j}\\}$ under the
isomorphism which maps $y_{j}+\mathsf{Id}(U_{j})$ to
$y_{j}+\mathsf{Id}(\cup_{i\in I}U_{i})$ for every $y_{j}$ in $Y_{j}$.

######  Remark 2.3.

By Lemma 2.2, one can easily construct a linear basis of a free product of an
arbitrary family of associative algebras. Unfortunately, a similar result of
Lemma 2.2 does not hold for dialgebras or trialgebras, see [3, Theorem 4.8]
for instance.

###  2.2. Embeddings of dialgebras and trialgebras into associative algebras

In this section, we shall shortly recall the definition of dialgebras,
trialgebras, and the embeddings of dialgebras and trialgebras into their
corresponding universal enveloping associative algebras. All of the results in
this section can be found in [10]. For the convenience of the readers, we
shortly recall what are needed here.

######  Definition 2.4.

[13] A _dialgebra_ (resp. _dimonoid_) is a vector space (resp. set)
$(D,\vdash,\dashv)$ equipped with two binary associative operations $\vdash$
and $\dashv$ such that the following identities hold:

(2.1) $\begin{cases}a\dashv(b\vdash c)=a\dashv(b\dashv c),\\\ (a\dashv
b)\vdash c=(a\vdash b)\vdash c,\\\ a\vdash(b\dashv c)=(a\vdash b)\dashv
c,\end{cases}$

for all $a,b$ and $c$ in $D$. We denote by $\mathsf{V}^{(2)}(X)$ (resp.
$\mathsf{Vid}^{(2)}(X)$) the free dialgebra (resp. dimonoid) generated by $X$.

######  Definition 2.5.

[13] A _trialgebra_ (resp. _trioid_) is a vector space (resp. set)
$(T,\vdash,\dashv,\perp)$ equipped with 3 binary associative operations:
$\vdash$, $\dashv$ and $\perp$, satisfying the following identities:

(2.2) $\begin{cases}a\dashv(b\vdash c)=a\dashv(b\dashv c),\\\ (a\dashv
b)\vdash c=(a\vdash b)\vdash c,\\\ a\vdash(b\dashv c)=(a\vdash b)\dashv c,\\\
a\dashv(b\perp c)=a\dashv(b\dashv c),\\\ (a\perp b)\vdash c=(a\vdash b)\vdash
c,\\\ a\vdash(b\perp c)=(a\vdash b)\perp c,\\\ a\perp(b\dashv c)=(a\perp
b)\dashv c,\\\ a\perp(b\vdash c)=(a\dashv b)\perp c\end{cases}$

for all $a,\ b,\ c\in T$. We denote by $\mathsf{V}^{(3)}(X)$ (resp.
$\mathsf{Vid}^{(3)}(X)$) the free trialgebra (resp. trioid) generated by $X$.

Obviously, every trialgebra can be represented by generators and relations:
For a trialgebra $T$, if $X=\\{a_{i}\mid i\in I\\}$ is a $k$-basis of $T$ and

$S=\\{a_{i}\delta a_{j}=\\{a_{i}\delta a_{j}\\}\mid i,j\in
I,\delta\in\\{\vdash,\dashv,\perp\\}\\}$

is the multiplication table, where $\\{a_{i}\delta a_{j}\\}$ is of the form
$\Sigma\alpha_{{}_{\delta,ijt}}a_{t}$, $\alpha_{{}_{\delta,ijt}}\in k$ and
$a_{t}\in X$, then we have

$T\cong\mathsf{V}^{(3)}(X|S):=\mathsf{V}^{(3)}(X)/\mathsf{Id}^{(3)}(S),$

where $\mathsf{Id}^{(3)}(S)$ is the ideal of $\mathsf{V}^{(3)}(X)$ generated
by $S$ .

Similarly, let $T$ be a trioid. For $\delta\in\\{\vdash,\dashv,\perp\\}$,
denote by $\\{x\delta y\\}$ the letter in $T$ that is equal to $x\delta y$.
Let $\mathsf{Vid}^{(3)}(T)$ be the free trioid generated by $T$ and denote by
$\rho_{{}_{S}}$ the congruence of $\mathsf{Vid}^{(3)}(T)$ generated by

$S=\\{(x\delta y,\\{x\delta y\\})\mid x,y\in
T,\delta\in\\{\vdash,\dashv,\perp\\}\\}.$

Then it is clear that we have

$T\cong\mathsf{Vid}^{(3)}(T|S):=\mathsf{Vid}^{(3)}(T)/\rho_{{}_{S}}.$

Similar results hold for dialgebras and dimonoids. In particular, we can
denote by $\mathsf{V}^{(t)}(X|S)$ (resp. $\mathsf{Vid}^{(t)}(X|S)$) an
arbitrary trialgebra (resp. trioid) when $t=3$ and an arbitrary dialgebra
(resp. dimonoid) when $t=2$.

Note that if $(T,\vdash,\dashv,\perp)$ is a trioid (resp. trialgebra), then
$(T,\vdash,\dashv)$ is a dimonoid (resp. dialgebra). Obviously, dialgebras and
trialgebras are generalizations of associative algebras. Recall that for every
dialgebra (dimonoid) $D$, for all $y_{1},...\leavevmode\hbox{}\hskip
0.56905pt,y_{m}$ in $D$, by [12] every parenthesizing of

$y_{1}\vdash\cdots\vdash y_{t}\dashv\cdots\dashv y_{m}$

gives the same element in $D$, which we denote by
$y_{1}...\dot{y}_{t}...y_{m}$. For instance, we have
$y_{3}y_{2}\dot{y}_{1}=y_{3}\vdash y_{2}\vdash y_{1}$ and
$\dot{y}_{7}y_{8}=y_{7}\dashv y_{8}$.

Similarly, let $T$ be a trialgebra (trioid). Then for all $y_{1},...,y_{m}\in
T$, by [13] every parenthesizing of

$(y_{1}\vdash\cdots\vdash y_{m_{1}-1})\vdash(y_{m_{1}}\dashv\cdots\dashv
y_{m_{2}-1})\perp(y_{m_{2}}\dashv\cdots\dashv
y_{m_{3}-1})\perp\cdots\perp(y_{m_{r}}\dashv\cdots\dashv y_{m})$

gives the same element in $T$, which we denote by

$y_{1}\dots y_{m_{1}-1}\dot{y}_{m_{1}}y_{m_{1}+1}\dots
y_{m_{2}-1}\dot{y}_{m_{2}}y_{m_{2}+1}\dots
y_{m_{r}-1}\dot{y}_{m_{r}}y_{m_{r}+1}\dots y_{m}.$

These notations indicate some connections between dialgebras (or trialgebras)
with associative algebras. More precisely, Kolesnikov [10] proved a surprising
result that every trialgebra (resp. dialgebra) generated by $X$ can be
embedded into an associative algebra generated by $X\cup\dot{X}$, where
$\dot{X}=\\{\dot{x}\mid x\in X\\}$ is a copy of $X$, namely for every $x$ in
$X$, the notation $\dot{x}$ means a letter corresponding to $x$. Now we shall
explain the embedding in more details.

As in Section 2.1, denote by $k\langle X\cup\dot{X}\rangle$ and $k\langle
X\rangle$ the free associative algebras generated by $X\cup\dot{X}$ and $X$
respectively. Obviously, there exists a unique homomorphism

(2.3) $\varphi:k\langle X\cup\dot{X}\rangle\rightarrow k\langle X\rangle$

induced by $x\mapsto x$ and $\dot{x}\mapsto x$ for all $x\in X$. A more
precise notation for $\varphi$ might be $\varphi_{{}_{X}}$, but to simplify
the formulas we do not add the subscript because each time the underlying
generating set is clear. In particualr, sometimes we do not denote the
generating set by $X$, but $\varphi$ always means the homomorphism by removing
the dot.

If we define three binary operations $\vdash$, $\dashv$ and $\perp$ in
$k\langle X\cup\dot{X}\rangle$ as follows:

(2.4) $a\vdash b=\varphi(a)b,\ a\dashv b=a\varphi(b),\ a\perp b=ab,$

for all $a,b\in k\langle X\cup\dot{X}\rangle$, then by [10], we obtain that

$k\langle X\cup\dot{X}\rangle^{(3)}:=(k\langle
X\cup\dot{X}\rangle,\vdash,\dashv,\perp)$

becomes a trialgebra and

$k\langle X\cup\dot{X}\rangle^{(2)}:=(k\langle
X\cup\dot{X}\rangle,\vdash,\dashv)$

becomes a dialgebra. Moreover, we can also introduce trialgebras or dialgebras
structure on certain associative algebras defined by generators and relations.
More precisely, let $R$ be a $\varphi$-invariant subset of $k\langle
X\cup\dot{X}\rangle$, namely, $\varphi(R)\subseteq R$. Then we define the
three binary operations $\vdash$, $\dashv$ and $\perp$ in $k\langle
X\cup\dot{X}|R\rangle$ as follows:

(2.5)
$\begin{cases}(a+\mathsf{Id}(R))\vdash(b+\mathsf{Id}(R))=\varphi(a)b+\mathsf{Id}(R),\\\
(a+\mathsf{Id}(R))\dashv(b+\mathsf{Id}(R))=a\varphi(b)+\mathsf{Id}(R),\\\
(a+\mathsf{Id}(R))\perp(b+\mathsf{Id}(R))=ab+\mathsf{Id}(R),\end{cases}$

for all $a,b\in k\langle X\cup\dot{X}\rangle$. It is straightforward to show
that

(2.6) $k\langle X\cup\dot{X}|R\rangle^{(3)}:=(k\langle
X\cup\dot{X}|R\rangle,\vdash,\dashv,\perp)$

is a trialgebra, and

(2.7) $k\langle X\cup\dot{X}|R\rangle^{(2)}:=(k\langle
X\cup\dot{X}|R\rangle,\vdash,\dashv)$

is a dialgebra. Moreover, for $t=2,3$, we have $k\langle
X\cup\dot{X}|R\rangle^{(t)}=k\langle X\cup\dot{X}|R\rangle$ as a vector space,
so they have the same linear basis.

######  Remark 2.6.

Since $\mathsf{V}^{(3)}(X)$ (resp. $\mathsf{V}^{(2)}(X)$) is the free
trialgebra (resp. dialgebra) generated by $X$, there are algebra homomorphisms
$\Psi_{3}$ and $\Psi_{2}$ as follows:

$\Psi_{3}:\mathsf{V}^{(3)}(X)\longrightarrow k\langle
X\cup\dot{X}\rangle^{(3)},\ x\mapsto\dot{x},\ x\in X$

and

$\Psi_{2}:\mathsf{V}^{(2)}(X)\longrightarrow k\langle
X\cup\dot{X}\rangle^{(2)},\ x\mapsto\dot{x},\ x\in X.$

To simplify the formulas, we denote them by

$\Psi_{t}:\mathsf{V}^{(t)}(X)\longrightarrow k\langle
X\cup\dot{X}\rangle^{(t)},\ x\mapsto\dot{x},\ x\in X$

for $t=2,3$. By [10], we know that $\Psi_{t}$ is an embedding of algebras.
Moreover, for every element $f\in\Psi_{t}(\mathsf{V}^{(t)}(X))$, we denote by
$\Psi_{t}^{-1}(f)$ the pre-image of $f$. Again, a more precise notation for
$\Psi_{t}$ could be $\Psi_{(t,X)}$, but to simplify the formulas, we do not
add the subscript $X$. When the generating set is not denoted by $X$, the maps
$\Psi_{2}$ and $\Psi_{3}$ are defined in the same way.

######  Example 2.7.

Let $X=\\{x,y\\}$ and let $f=x\vdash(x\dashv y)\perp(y\dashv x)-x\vdash
x\in\mathsf{V}^{(3)}(X)$. Then we have $\dot{X}=\\{\dot{x},\dot{y}\\}$,

$\Psi_{3}(f)=x\dot{x}y\dot{y}x-x\dot{x}\in k\langle X\cup\dot{X}\rangle$

and

$\varphi(\Psi_{3}(f))=xxyyx-xx\in k\langle X\rangle.$

On the other hand, for the element $\dot{y}xy\dot{x}x$ in
$\Psi_{3}(\mathsf{V}^{(3)}(X))$, we have

$\Psi_{3}^{-1}(\dot{y}xy\dot{x}x)=(y\dashv x\dashv y)\perp(x\dashv x).$

Let $S$ be a subset of $V^{(t)}(X)$ (resp. $k\langle X\rangle$) and denote by
$\mathsf{Id}^{(t)}(S)$ (resp. $\mathsf{Id}(S)$) the ideal of
$\mathsf{V}^{(t)}(X)$ (resp. $k\langle X\rangle$) generated by $S$. Now we
recall one of the main theorems in [10], which establishes the Gröbner-
Shirshov bases theory for trialgebras and dialgebras, respectively.

######  Lemma 2.8.

_[10, Corollary 4.3]_ For $t=2$ or $3$, the algebra $V^{(t)}(X|S)$ is
isomorphic to the subalgebra of $k\langle
X\cup\dot{X}|\Psi_{t}(S)\cup\varphi(\Psi_{t}(S))\rangle^{(t)}$ generated by
$\\{\dot{x}+\mathsf{Id}(\Psi_{t}(S)\cup\varphi(\Psi_{t}(S)))\mid\dot{x}\in\dot{X}\\}$
under the embedding

$\displaystyle\widetilde{\Psi}_{t}:\ $
$\displaystyle\mathsf{V}^{(t)}(X|S)\mapsto k\langle
X\cup\dot{X}|\Psi_{t}(S)\cup\varphi(\Psi_{t}(S))\rangle^{(t)},$ $\displaystyle
x+\mathsf{Id}^{(t)}(S)\mapsto\dot{x}+\mathsf{Id}(\Psi_{t}(S)\cup\varphi(\Psi_{t}(S)))$

for every $x\in X$. Moreover, if some set $Y^{(t)}\subseteq(X\cup\dot{X})^{*}$
consisting of monomials satisfies that

$\\{y+\mathsf{Id}(\Psi_{t}(S)\cup\varphi(\Psi_{t}(S)))\mid y\in Y^{(t)}\\}$

forms a linear basis for $k\langle
X\cup\dot{X}|\Psi_{t}(S)\cup\varphi(\Psi_{t}(S))\rangle^{(t)}$, then

$\\{\Psi_{t}^{-1}(u)+\mathsf{Id}^{(t)}(S)\mid u\in
Y^{(t)}\cap\Psi_{t}(\mathsf{V}^{(t)}(X))\\}$

forms a linear basis for $\mathsf{V}^{(t)}(X|S)$.

##  3\. Free products of trialgebras and trioids

This section contains the main result of this article. We shall first
construct free products of arbitrary trialgebras or dialgebras. And if all the
trialgebras (resp. dialgebras) are trioid algebras (resp. dimonoid algebras),
then a linear basis of the corresponding free product consisting of monomials
forms a set of normal forms for the corresponding free products of the trioids
(resp. dimonoids).

We first recall the definition of free products of trialgebras (resp.
dialgebras, trioids, dimonoids).

######  Definition 3.1.

Let $\\{T_{i}\mid i\in I\\}$ be a family of indexed trialgebras (resp.
dialgebras, trioids, dimonoids), and let $T$ be a trialgebra (resp. dialgebra,
trioid, dimonoid) such that
(i) there exists an injective trialgebra (resp. dialgebra, trioid, dimonoid)
homomorphism $\tau_{i}:T_{i}\longrightarrow T$ for every $i\in I$;
(ii) if $T^{\prime}$ is a trialgebra (resp. dialgebra, trioid, dimonoid), and
if there exists a trialgebra (resp. dialgebra, trioid, dimonoid) homomorphism
$\phi_{i}:T_{i}\rightarrow T^{\prime}$ for every $i\in I$, then there exists a
unique trialgebra (resp. dialgebra, trioid, dimonoid) homomorphism
$\eta:T\rightarrow T^{\prime}$ such that the diagram

---
$\textstyle{T_{i}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\tau_{i}}$$\scriptstyle{\phi_{i}}$$\textstyle{T\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\eta}$$\textstyle{T^{\prime}}$

commutes for every $i\in I$.

Then $T$ is called a free product of $\\{T_{i}\mid i\in I\\}$.

Obviously, the free product of the family $\\{T_{i}\mid i\in I\\}$ of
trialgebras (resp. dialgebras, trioids, dimonoids) is unique up to
isomorphism.

Let $\\{T_{i}\mid i\in I\\}$ be a family of trialgebras (resp. dialgebras,
trioids, dimonoids). If for every $i\in I$, $T_{i}$ is isomorphic to
$T_{i}^{\prime}$, then the free product of $\\{T_{i}^{\prime}\mid i\in I\\}$
is isomorphic to that of $\\{T_{i}\mid i\in I\\}$. Therefore, when one
constructs the free product of arbitrary trialgebras (resp. dialgebras)
$\\{T_{i}\mid i\in I\\}$, one may always assume that $T_{i}\cap T_{j}=\\{0\\}$
for all $i\neq j\in I$. Similarly, when one constructs the free product of
trioids (resp. dimonids) $\\{T_{i}\mid i\in I\\}$, one can always assume
$T_{i}\cap T_{j}=\emptyset$ for all $i\neq j\in I$.

Let $T=(T,\vdash,\dashv,\perp)$ be an arbitrary trioid and let $0$ be a new
letter that does not lie in $T$. We define a trioid
$T^{0}=(T\cup\\{0\\},\vdash,\dashv,\perp)$ as follows: for all $x,y\in T$ and
$\delta\in\\{\vdash,\dashv,\perp\\}$, define

$x\delta y=\begin{cases}\\{x\delta y\\},\ \ \text{ if }x,y\text{ lie in }T,\\\
0\ \ \ \ \ \ \ \ \text{otherwise.}\end{cases}$

Then it is clear that $T^{0}$ is a trioid and $T$ is a subtrioid of $T^{0}$.

Now we show that one can easily construct free products of arbitrary trioids
by generators and relations.

######  Lemma 3.2.

Let $\\{X_{i}\mid i\in I\\}$ be a pairwise disjoint set and let
$\\{\mathsf{Vid}^{(3)}(X_{i}|S_{i})\mid i\in I\\}$ be a family of trioids,
where $I$ is an index set. Then $\mathsf{Vid}^{(3)}(\cup_{i\in
I}X_{i}|\cup_{i\in I}S_{i})$ is the free product of trioids
$\\{\mathsf{Vid}^{(3)}(X_{i}|S_{i})\mid i\in I\\}$.

###### Proof.

For every letter $x\in\cup_{i\in I}X_{i}$, define $\mathsf{ind}(x)=i$ if $x$
lies in $X_{i}$. Let $T$ be an arbitrary trioid such that there exists a
family of homomorphisms $\phi_{i}$ from $\mathsf{Vid}^{(3)}(X_{i}|S_{i})$ to
$T$, $i\in I$. Denote by $\rho$ the congruence of
$\mathsf{Vid}^{(3)}(\cup_{i\in I}X_{i})$ generated by $\cup_{i\in I}S_{i}$,
and denote by $\rho_{i}$ the congruence of $\mathsf{Vid}^{(3)}(X_{i})$
generated by $S_{i}$. Define a map

$\theta:\cup_{i\in I}X_{i}\longrightarrow T,\
x\mapsto\phi_{\mathsf{ind}(x)}(x\rho_{\mathsf{ind}(x)})$

for every $x\in\cup_{i\in I}X_{i}$. Since $\mathsf{Vid}^{(3)}(\cup_{i\in
I}X_{i})$ is the free trioid generated by $\cup_{i\in I}X_{i}$, there exists a
homomorphism

$\widetilde{\theta}:\mathsf{Vid}^{(3)}(\cup_{i\in I}X_{i})\longrightarrow T,\
x\mapsto\phi_{\mathsf{ind}(x)}(x\rho_{\mathsf{ind}(x)})$

for every $x\in\cup_{i\in I}X_{i}$. Clearly, for every $(a,b)\in\cup_{i\in
I}S_{i}$, there exists some index $i\in I$ such that $(a,b)\in S_{i}$. So we
have $\phi_{i}(a\rho_{i})=\phi_{i}(b\rho_{i})$, which means that
$\widetilde{\theta}(a)=\widetilde{\theta}(b)$. Thus, there exists a
homomorphism

$\eta:\mathsf{Vid}^{(3)}(\cup_{i\in I}X_{i}|\cup_{i\in I}S_{i})\longrightarrow
T,\ x\rho\mapsto\phi_{\mathsf{ind}(x)}(x\rho_{\mathsf{ind}(x)})$

for every $x\in\cup_{i\in I}X_{i}$.

Define $\tau_{i}$ to be the homomorphism induced by

$\tau_{i}:\mathsf{Vid}^{(3)}(X_{i}|S_{i})\longrightarrow\mathsf{Vid}^{(3)}(\cup_{i\in
I}X_{i}|\cup_{i\in I}S_{i}),\ x\rho_{i}\mapsto x\rho,\ \ \ x\in X_{i}.$

Note that for every $i\in I$, we have $\rho_{i}\subseteq\rho$. So $\tau_{i}$
is well-defined and we have $\eta\tau_{i}=\phi_{i}$ for every $i\in I$. Such a
homomorphism $\eta$ is clearly unique.

It remains to show that $\tau_{i}$ is injective for every $i\in I$. For every
$j\in I$, we define a homomorphism $\phi_{j}^{\prime}$ as follows:

$\phi_{j}^{\prime}:\mathsf{Vid}^{(3)}(X_{j}|S_{j})\rightarrow T^{0}_{i},\
x\rho_{j}\mapsto x\rho_{i}\mbox{ if }j=i;\mbox{ and }x\rho_{j}\mapsto 0\mbox{
if }j\neq i$

for every $x\in X_{j}$. Clearly, $\phi_{i}^{\prime}$ is injective. Then by the
above reasoning, there exists a homomorphism $\eta^{\prime}$ such that
$\eta^{\prime}\tau_{j}=\phi_{j}^{\prime}$ for all $j\in I$. In particular, we
have $\eta^{\prime}\tau_{i}=\phi_{i}^{\prime}$ and thus $\tau_{i}$ is
injective. ∎

A similar result holds for dimonoids, dialgebras and trialgebras. We formulate
it for trialgebras and dialgebras without proof.

######  Lemma 3.3.

Let $\\{X_{i}\mid i\in I\\}$ be a pairwise disjoint set and let
$\\{\mathsf{V}^{(3)}(X_{i}|S_{i})\mid i\in I\\}$ $($resp.
$\\{\mathsf{V}^{(2)}(X_{i}|S_{i})\mid i\in I\\})$ be a family of trialgebras
$($resp. dialgebras$)$, where $I$ is an index set. Then
$\mathsf{V}^{(t)}(\cup_{i\in I}X_{i}|\cup_{i\in I}S_{i})$ is the free product
of $\\{\mathsf{V}^{(t)}(X_{i}|S_{i})\mid i\in I\\}$, $t\in\\{2,3\\}$. In
particular, for every $i\in I$, the algebra $\mathsf{V}^{(t)}(X_{i}|S_{i})$
embeds into $\mathsf{V}^{(t)}(\cup_{i\in I}X_{i}|\cup_{i\in I}S_{i})$.

By Lemmas 3.2, 3.3 and 2.8, in order to construct a set of normal forms of
elements for a free product of trialgebras (resp. dialgebras, dimonoids,
trioids), we can apply the method of Gröbner-Shirshov bases theory for
trialgebras (resp. dialgebras, dimonoids, trioids).

Now we recall a well order on the free monoid $(\cup_{i\in
I}(X_{i}\cup\dot{X_{i}}))^{*}$ generated by $(\cup_{i\in
I}(X_{i}\cup\dot{X_{i}}))$. Assume that each $X_{i}$ is a well-ordered set for
every $i\in I$ and assume that $I$ is well-ordered. Now we extend the well
orders on the sets $X_{i}$ to $(\cup_{i\in I}(X_{i}\cup\dot{X_{i}}))^{+}$ as
follows: for all $x,y\in\cup_{i\in I}X_{i}$, define

(i) $x>y$ if $x\in X_{i}$, $y\in X_{j}$, $i,j\in I$ with $i>j$;

(ii) $\dot{x}>\dot{y}$ if $x>y$;

(iii) $\dot{x}>y$.
Then we obtain a well order on $\cup_{i\in I}(X_{i}\cup\dot{X_{i}})$. Finally,
let $>$ be the degree-lexicographic order recalled in Section 2.1 on
$(\cup_{i\in I}(X_{i}\cup\dot{X_{i}}))^{\ast}$.

To avoid too many repetitions on the notations, we shall fix some notations as
follows.

######  Remark 3.4.

Let $\\{X_{i}\mid i\in I\\}$ be a pairwise disjoint set, and let
$\\{\mathsf{V}^{(t)}(X_{i}|S_{i})\mid i\in I\\}$ be a family of dialgebras
when $t=2$ (resp. trialgebras when $t=3$) such that
$\\{x+\mathsf{Id}^{(t)}(S_{i})\mid x\in X_{i}\\}$ is a linear basis for
$\mathsf{V}^{(t)}(X_{i}|S_{i})$ and $S_{i}$ is the multiplication table for
$\mathsf{V}^{(t)}(X_{i}|S_{i})$. For every letter $x\in\cup_{i\in
I}(X_{i}\cup\dot{X}_{i})$, define $\mathsf{ind}(x)=i$ if $x$ lies in
$X_{i}\cup\dot{X}_{i}$. Recall that $\varphi$ is defined by the rule in (2.3)
and $\Psi_{t}$, $t\in\\{2,3\\}$ is defined by the rule in Remark 2.6. (Note
that in this situation the generating sets are not denoted by $X$, but
hopefully no confusions will arise.) Define

$\mathcal{B}_{i,t}=k\langle X_{i}|\varphi(\Psi_{t}(S_{i}))\rangle,$
$\mathcal{A}_{i,t}=k\langle
X_{i}\cup\dot{X_{i}}|\Psi_{t}(S_{i})\cup\varphi(\Psi_{t}(S_{i}))\rangle\rangle,$

and

$\mathcal{A}_{t}=k\langle\cup_{i\in I}(X_{i}\cup\dot{X_{i}})|\cup_{i\in
I}(\Psi_{t}(S_{i})\cup\varphi(\Psi_{t}(S_{i})))\rangle.$

Finally, suppose that $R_{i,t}$ is a Gröbner-Shirshov basis for
$\mathcal{B}_{i,t}$ with respect to the degree-lexicographic order $>$ on
$X_{i}^{*}$. Without loss of generality, we may assume
$\varphi(\Psi_{t}(S_{i}))\subseteq R_{i,t}$. Define
$X_{i}^{\prime}=X_{i}^{*}\setminus X_{i}^{*}\overline{R_{i,t}}X_{i}^{*}$. Then
we have $X_{i}^{\prime}=X_{i}\setminus\\{\bar{f}\mid f\in R_{i,t}\\}$. By
Lemma 2.1, the set $\mathsf{Irr}(R_{i,t})=\\{x+\mathsf{Id}(R_{i,t})\mid x\in
X_{i}^{\prime}\\}$ forms a linear basis for $\mathcal{B}_{i,t}$.

######  Lemma 3.5.

With the notations in Remark 3.4, the set $\Psi_{t}(S_{i})\cup R_{i,t}$ forms
a Gröbner-Shirshov basis for $\mathcal{A}_{i,t}$.

###### Proof.

Since $R_{i,t}$ is a Gröbner-Shirshov basis for $\mathcal{B}_{i,t}=k\langle
X_{i}|\varphi(\Psi_{t}(S_{i}))\rangle$, the sets $R_{i,t}$ and
$\varphi(\Psi_{t}(S_{i}))$ generate the same ideal of $k\langle X_{i}\rangle$.
It follows immediately that we have

$\varphi(\Psi_{t}(S_{i}))\subseteq k\langle X_{i}\rangle R_{i,t}k\langle
X_{i}\rangle\subseteq k\langle X_{i}\cup\dot{X_{i}}\rangle R_{i,t}k\langle
X_{i}\cup\dot{X_{i}}\rangle$

and

$R_{i,t}\subseteq k\langle
X_{i}\cup\dot{X_{i}}\rangle\varphi(\Psi_{t}(S_{i}))k\langle
X_{i}\cup\dot{X_{i}}\rangle.$

So we obtain

$\mathcal{A}_{i,t}=k\langle
X_{i}\cup\dot{X_{i}}|\Psi_{t}(S_{i})\cup\varphi(\Psi_{t}(S_{i}))\rangle\rangle=k\langle
X_{i}\cup\dot{X_{i}}|\Psi_{t}(S_{i})\cup R_{i,t}\rangle.$

For all $f,g\in\Psi_{t}(S_{i})\cup R_{i,t}$, we shall show that all the
possible compositions of the form $(f,g)_{w}$ for some $w\in(\dot{X_{i}}\cup
X_{i})^{\ast}$ (if any) are trivial, and then the lemma follows.

First of all, if no letters in $\dot{X_{i}}$ are involved in the composition
$(f,g)_{w}$, then it follows that $f,g$ lie in $R_{i,t}$. Since $R_{i,t}$ is a
Gröbner-Shirshov basis for $\mathcal{B}_{i,t}$, it follows that the
composition $(f,g)_{w}$ can be written as a linear combination of elements of
the form $uhv$ satisfying $u\overline{h}v<w$, where all $u,v$ lie in
$(X_{i})^{*}\subseteq(X_{i}\cup\dot{X_{i}})^{*}$ and each $h$ lies in
$R_{i,t}\subseteq\Psi_{t}(S_{i})\cup R_{i,t}$. Therefore, the composition
$(f,g)_{w}$ is trivial.

On the other hand, if some letter in $\dot{X_{i}}$ is involved in the
compostion $(f,g)_{w}$, then $f$ or $g$ lies in $\Psi_{t}(S_{i})$. And by the
definition of the composition $(f,g)_{w}$, every monomial that appears in
$(f,g)_{w}$ (with nonzero coefficient) must involves some letter in
$\dot{X_{i}}$. Suppose that $(f,g)_{w}=\sum_{n}\alpha_{n}w_{n}$ with
$w>\overline{(f,g)_{w}}=w_{1}>w_{2}>\cdots$. Since $S_{i}$ is the
multiplication table for $\mathsf{V}^{(t)}(X_{i}|S_{i})$, we know that every
element in $\Psi_{t}(S_{i})$ is of the form
$y_{p}y_{q}=\sum_{m}\beta_{m}z_{m}$, where $y_{p},y_{q}$ lie in
$X_{i}\cup\dot{X_{i}}$ and at least one of $y_{p},y_{q}$ lies in
$\dot{X_{i}}$, moreover, every $z_{m}$ lies in $\dot{X_{i}}$. It follows that
we can rewrite $(f,g)_{w}$ into the form

$\sum_{l}\gamma_{l}u_{l}f_{l}v_{l}+\sum_{n}\delta_{n}z_{n}^{\prime},$

where each $z_{n}^{\prime}$ lies in $\dot{X_{i}}$, each $f_{l}$ lies in
$\Psi_{t}(S_{i})$, all $u_{l},v_{l}$ lie in $(X_{i}\cup\dot{X_{i}})^{\ast}$,
and we have $u_{l}\overline{f_{l}}v_{l}\leq w_{1}<w$. (For instance, say
$(f,g)_{w}=x_{1}\dot{x_{2}}x_{3}-\dot{x_{3}}$,
$f_{1}=\dot{x_{2}}x_{3}-\dot{x_{1}}\in\Psi_{t}(S_{i})$ and
$f_{2}=x_{1}\dot{x_{1}}-\dot{x_{3}}\in\Psi_{t}(S_{i})$, then we have
$(f,g)_{w}=x_{1}f_{1}+f_{2}.$)

By Lemma 2.8, it follows that $\mathsf{V}^{(t)}(X_{i}|S_{i})$ embeds into
$\mathcal{A}_{i,t}^{(t)}=k\langle X_{i}\cup\dot{X_{i}}|\Psi_{t}(S_{i})\cup
R_{i,t}\rangle^{(t)}$. Since $\\{x+\mathsf{Id}^{(t)}(S_{i})\mid x\in X_{i}\\}$
forms a linear basis for $\mathsf{V}^{(t)}(X_{i}|S_{i})$, we obtain that its
image $\\{\dot{x}+\mathsf{Id}(\Psi_{t}(S_{i})\cup
R_{i,t})\mid\dot{x}\in\dot{X}_{i}\\}$ is linear independent, and thus every
coefficient $\delta_{n}$ is zero. Therefore, the set $\Psi_{t}(S_{i})\cup
R_{i,t}$ forms a Gröbner-Shirshov basis for $\mathcal{A}_{i,t}$. ∎

######  Corollary 3.6.

With the notations in Remark 3.4, the set $\cup_{i\in I}(\Psi_{t}(S_{i})\cup
R_{i,t})$ forms a Gröbner-Shirshov basis for $\mathcal{A}_{t}$.

###### Proof.

By Lemmas 3.5 and 2.2, the result follows immediately. ∎

Now we can establish the first main result of the article, in which we
construct a linear basis for a free product of arbitrary trialgebras (resp.
dialgebras).

######  Theorem 3.7.

Let the notations be as in Remark 3.4. Let

$Y^{(t)}=\\{y_{1}...y_{n}\mid y_{1},...\leavevmode\hbox{}\hskip
0.56905pt,y_{n}\in\cup_{i\in
I}(X_{i}^{\prime}\cup\dot{X_{i}}),\mathsf{ind}(y_{p})\neq\mathsf{ind}(y_{p+1}),n\in\mathbb{N}^{+},1\leq
p\leq n-1\\}.$

Then the set

$\\{\Psi_{t}^{-1}(u)+\mathsf{Id}^{(t)}(\cup_{i\in I}S_{i})\mid u\in
Y^{(t)}\cap\Psi_{t}(\mathsf{V}^{(t)}(\cup_{i\in I}X_{i}))\\}$

forms a linear basis for the free product $\mathsf{V}^{(t)}(\cup_{i\in
I}X_{i}|\cup_{i\in I}S_{i})$ of $\\{\mathsf{V}^{(t)}(X_{i}|S_{i})\mid i\in
I\\}$, $t\in\\{2,3\\}$.

###### Proof.

Denote $\cup_{i\in I}(\Psi_{t}(S_{i})\cup R_{i,t})$ by $S$, and denote
$\cup_{i\in I}(\dot{X_{i}}\cup X_{i})$ by $X$. Then by Lemma 2.1 and Corollary
3.6, the set

$\mathsf{Irr}(S)=\\{u+\mathsf{Id}(S)\mid u\in X^{*}\setminus
X^{*}\overline{S}X^{*}\\}$

forms a set of linear basis for the quotient associative algebra
$\mathcal{A}_{t}$. By Lemma 2.8, $\mathsf{V}^{(t)}(\cup_{i\in
I}(\dot{X_{i}}\cup X_{i})|\cup_{i\in I}(\Psi_{t}(S_{i})\cup R_{i,t}))$ has a
$k$-basis:

$\\{\Psi_{t}^{-1}(u)+\mathsf{Id}^{(t)}(S)\mid u\in(X^{*}\setminus
X^{*}\overline{S}X^{*})\cap\Psi_{t}(\mathsf{V}^{(t)}(\cup_{i\in I}X_{i}))\\}.$

So it suffices to show

$Y^{(t)}\cap\Psi_{t}(\mathsf{V}^{(t)}(\cup_{i\in I}X_{i}))=(X^{*}\setminus
X^{*}\overline{S}X^{*})\cap\Psi_{t}(\mathsf{V}^{(t)}(\cup_{i\in I}X_{i})).$

For each $i\in I$, since $\\{x+\mathsf{Id}^{(t)}(S_{i})\mid x\in X_{i}\\}$ is
a linear basis for $\mathsf{V}^{(t)}(X_{i}|S_{i})$ and $S_{i}$ is the
multiplication table for $\mathsf{V}^{(t)}(X_{i}|S_{i})$, we have

(3.1) $\overline{\Psi_{t}(S_{i})}=\begin{cases}\\{yz\mid y,z\in
X_{i}\cup\dot{X_{i}},\text{ and at least one of }y,z\text{ lies in
}\dot{X_{i}}\\}\text{ if }t=3,\\\ \\{yz\mid y,z\in X_{i}\cup\dot{X_{i}},\text{
and exactly one of }y,z\text{ lies in }\dot{X_{i}}\\}\text{ if
}t=2,\end{cases}$

and

$\overline{\varphi(\Psi_{t}(S_{i}))}=\\{yz\mid y,z\in
X_{i}\\}\subseteq\overline{R_{i,t}}.$

Moreover, for every $i\in I$ and for all $y,y^{\prime}\in\dot{X_{i}}$, we have

(3.2) $yy^{\prime}\in\overline{\Psi_{3}(S_{i})}\mbox{ if }t=3,\mbox{ and
}yy^{\prime}\notin\Psi_{2}(\mathsf{V}^{(2)}(\cup_{i\in I}X_{i}))\mbox{ if
}t=2.$

Therefore, if $u=y_{1}...y_{n}\in(X^{*}\setminus
X^{*}\overline{S}X^{*})\cap\Psi_{t}(\mathsf{V}^{(t)}(\cup_{i\in I}X_{i}))$,
where $y_{1},...\leavevmode\hbox{}\hskip 0.56905pt,y_{n}$ lies in $X$, then we
have

$\mathsf{ind}(y_{p})\neq\mathsf{ind}(y_{p+1})$

for every integer $p$ such that $1\leq p\leq n-1$. Since
$X_{i}^{\prime}=X_{i}^{*}\setminus
X_{i}^{*}\overline{R_{i,t}}X_{i}^{*}=X_{i}\setminus\\{\bar{f}\mid f\in
R_{i,t}\\}$, we deduce that

$y_{1},...\leavevmode\hbox{}\hskip 0.56905pt,y_{n}\in\cup_{i\in
I}(X_{i}^{\prime}\cup\dot{X_{i}}).$

It follows immediately that

$(X^{*}\setminus
X^{*}\overline{S}X^{*})\cap\Psi_{t}(\mathsf{V}^{(t)}(\cup_{i\in
I}X_{i}))\subseteq Y^{(t)},$

and thus we obtain

$(X^{*}\setminus
X^{*}\overline{S}X^{*})\cap\Psi_{t}(\mathsf{V}^{(t)}(\cup_{i\in
I}X_{i}))\subseteq Y^{(t)}\cap\Psi_{t}(\mathsf{V}^{(t)}(\cup_{i\in I}X_{i})).$

On the other hand, since $\overline{R_{i,t}}$ is a subset of $X_{i}^{*}$, it
is clear that every $\dot{x}\in X$ is not a leading monomial of any element in
$\cup_{i\in I}(\Psi_{t}(S_{i})\cup R_{i,t})$. Moreover, since
$X_{i}^{\prime}=X_{i}\setminus\\{\bar{f}\mid f\in R_{i,t}\\}$ and since the
leading monomial of every element in $\Psi_{t}(S_{i})$ for every $i\in I$ has
length at least two, we deduce that every $x\in X_{i}^{\prime}$ is not a
leading monomial of any element in $\cup_{i\in I}(\Psi_{t}(S_{i})\cup
R_{i,t})$. Combining the above reasoning with (3.1) and (3.2), we deduce that

$Y^{(t)}\cap\Psi_{t}(\mathsf{V}^{(t)}(\cup_{i\in
I}X_{i}))\subseteq(X^{*}\setminus
X^{*}\overline{S}X^{*})\cap\Psi_{t}(\mathsf{V}^{(t)}(\cup_{i\in I}X_{i})).$

The result follows immediately. ∎

By Lemma 2.8 and by Theorem 3.7, we immediately obtain the following
alternative description of a free product of arbitrary trialgebras (resp.
dialgebras).

######  Corollary 3.8.

Let the notations be as in Remark 3.4. Then the subalgebra $\mathcal{P}_{t}$
of

$\mathcal{A}_{t}^{(t)}=k\langle\cup_{i\in I}(X_{i}\cup\dot{X_{i}})|\cup_{i\in
I}(\Psi_{t}(S_{i})\cup\varphi(\Psi_{t}(S_{i})))\rangle^{(t)}$

generated by $\\{\dot{x}+\mathsf{Id}(\cup_{i\in I}(\Psi_{t}(S_{i})\cup
R_{i,t}))\mid\dot{x}\in\cup_{i\in I}\dot{X_{i}}\\}$ is the free product of
algebras $\\{\mathsf{V}^{(t)}(X_{i}|S_{i})\mid i\in I\\}$. Moreover, with the
notations of Theorem 3.7, the set

$\\{u+\mathsf{Id}(\cup_{i\in I}(\Psi_{t}(S_{i})\cup R_{i,t}))\mid u\in
Y^{(t)}\cap\Psi_{t}(\mathsf{V}^{(t)}(\cup_{i\in I}X_{i}))\\}$

forms a linear basis for $\mathcal{P}_{t}$, $t\in\\{2,3\\}$.

Let $(T,\vdash,\dashv,\perp)$ (resp. $(D,\vdash,\dashv)$) be an arbitrary
trialgebra (resp. dialgebra) and let $U^{(3)}$ (resp. $U^{(2)}$) be the ideal
of $T$ (resp. $D$) generated by

$\\{f\vdash g-f\dashv g,f\vdash g-f\perp g\mid f,g\in T\\}\ \ \ (resp.\
\\{f\vdash g-f\dashv g\mid f,g\in D\\}).$

Then $T/U^{(3)}$ (resp. $D/U^{(2)}$) is called the _associated associative
algebra_ of the trialgebra $T$ (resp. dialgebra $D$).

For an arbitrary associative algebra $\mathcal{B}$, if we define $f\vdash
g=f\dashv g=f\perp g=fg$ for all $f,g\in\mathcal{B}$, then
$(\mathcal{B},\vdash,\dashv,\perp)$ is a trialgebra which is denoted by
$\mathcal{B}^{[3]}$, and $(\mathcal{B},\vdash,\dashv)$ is a dialgebra which is
denoted by $\mathcal{B}^{[2]}$ (cf. Equations (2.6) and (2.7)). Now we show
that we can identify $k\langle X_{i}|\varphi(\Psi_{t}(S_{i}))\rangle$ with the
associated associative algebra of the trialgebra
$\mathsf{V}^{(t)}(X_{i}|S_{i})$ when $t=3$ (resp. dialgebra when $t=2$).

######  Lemma 3.9.

With the notations in Remark 3.4, let $U^{(3)}$ _(resp. $U^{(2)}$)_ be the
ideal of $\mathsf{V}^{(3)}(X_{i})$ _(resp. $\mathsf{V}^{(2)}(X_{i})$)_
generated by $\\{f\vdash g-f\dashv g,f\vdash g-f\perp g\mid
f,g\in\mathsf{V}^{(3)}(X_{i})\\}$ _(resp. $\\{f\vdash g-f\dashv g\mid
f,g\in\mathsf{V}^{(2)}(X_{i})\\}$)_. Then $\mathsf{V}^{(t)}(X_{i}|U^{(t)}\cup
S_{i})$ is isomorphic to $k\langle
X_{i}|\varphi(\Psi_{t}(S_{i}))\rangle^{[t]}$, for $t\in\\{2,3\\}$. Moreover,
the set $\\{x+\mathsf{Id}^{(t)}(U^{(t)}\cup S_{i})\mid x\in X_{i}^{\prime}\\}$
forms a linear basis for $\mathsf{V}^{(t)}(X_{i}|U^{(t)}\cup S_{i})$.

###### Proof.

First of all, it is easy to see that all the operations in
$\mathsf{V}^{(t)}(X_{i}|U^{(t)}\cup S_{i})$ coincide and then
$\mathsf{V}^{(t)}(X_{i}|U^{(t)}\cup S_{i})$ is also an associative algebra.
Since $k\langle X_{i}\rangle$ is the free associative algebra generated by
$X_{i}$, we can define an (associative) algebra homomorphism $\psi$ from
$k\langle X_{i}\rangle$ to $\mathsf{V}^{(t)}(X_{i}|U^{(t)}\cup S_{i})$ by the
rule $\psi(x)=x+\mathsf{Id}^{(t)}(U^{(t)}\cup S_{i})$ for every $x\in X_{i}$.
Moreover, since the operations $\vdash$ and $\dashv$ in
$\mathsf{V}^{(t)}(X_{i}|U^{(t)}\cup S_{i})$ coincide, for every element $f\in
S_{i}$, we have

$\psi(\varphi(\Psi_{t}(f)))+\mathsf{Id}^{(t)}(U^{(t)}\cup
S_{i})=f+\mathsf{Id}^{(t)}(U^{(t)}\cup S_{i})=\mathsf{Id}^{(t)}(U^{(t)}\cup
S_{i}),$

in other words, $\psi$ induces an (associative) algebra homomorphism, denoted
by $\widetilde{\psi}$, from the algebra $k\langle
X_{i}|\varphi(\Psi_{t}(S_{i}))\rangle$ to $\mathsf{V}^{(t)}(X_{i}|U^{(t)}\cup
S_{i})$ by the rule:

$\widetilde{\psi}(x+\mathsf{Id}(\varphi(\Psi_{t}(S_{i}))))=x+\mathsf{Id}^{(t)}(U^{(t)}\cup
S_{i})$

for every $x\in X_{i}$. Clearly, $\widetilde{\psi}$ is also a dialgebra (resp.
trialgebra) homomorphism when $t=2$ (resp. $t=3$) from $k\langle
X_{i}|\varphi(\Psi_{t}(S_{i}))\rangle^{[t]}$ to
$\mathsf{V}^{(t)}(X_{i}|U^{(t)}\cup S_{i})$.

On the other hand, we have an algebra homomorphism

$\widetilde{\varphi}:\ \mathsf{V}^{(t)}(X_{i}|U^{(t)}\cup
S_{i})\longrightarrow k\langle X_{i}|\varphi(\Psi_{t}(S_{i}))\rangle^{[t]},\
x+\mathsf{Id}^{(t)}(U^{(t)}\cup S_{i})\mapsto
x+\mathsf{Id}(\varphi(\Psi_{t}(S_{i})))$

for every $x\in X_{i}$ (as a dialgebra homomorphism when $t=2$ and as a
trialgebra homomorphism when $t=3$). Moreover, $\widetilde{\varphi}$ is
clearly an associative algebra homomorphism.

Obviously, $\widetilde{\varphi}$ is the inverse of $\widetilde{\psi}$. The
first claim follows immediately.

As for the last assertion, by Remark 3.4, the set
$\\{x+\mathsf{Id}(\varphi(\Psi_{t}(S_{i})))\mid x\in X_{i}^{\prime}\\}$ forms
a linear basis for $k\langle X_{i}|\varphi(\Psi_{t}(S_{i}))\rangle$, so the
set $\\{x+\mathsf{Id}^{(t)}(U^{(t)}\cup S_{i})\mid x\in X_{i}^{\prime}\\}$
forms a linear basis for $\mathsf{V}^{(t)}(X_{i}|U^{(t)}\cup S_{i})$. ∎

We conclude the article with an observation on a free product of arbitrary
trioids. Assume that $\\{(X_{i},\vdash,\dashv,\perp)\mid i\in I\\}$ is a
family of disjoint trioids. (Sometimes we use the notation $X_{i}$ both for
the trioid $(X_{i},\vdash,\dashv,\perp)$ and for its underlying set to
simplify the notations if no confusions arise.) Let
$\mathsf{Vid}^{(3)}(X_{i})$ be the free trioid generated by the set $X_{i}$
and let $\rho_{i}$ be the congruence of $\mathsf{Vid}^{(3)}(X_{i})$ generated
by

(3.3) $S_{i}=\\{(x\delta y,\\{x\delta y\\})\mid x,y\in
X_{i},\delta\in\\{\vdash,\dashv,\perp\\}\\},$

where $\\{x\delta y\\}$ is the letter in the set $X_{i}$ such that we have
$x\delta y=\\{x\delta y\\}$ in $(X_{i},\vdash,\dashv,\perp)$. It is clear that
we have

$(X_{i},\vdash,\dashv,\perp)\cong\mathsf{Vid}^{(3)}(X_{i})/\rho_{i}.$

Denote by $kX_{i}$ the linear space with a linear basis $X_{i}$, and extend
the operations $\vdash,\dashv,\perp$ on $kX_{i}$ in a natural way. Then we
have the trialgebra $(kX_{i},\vdash,\dashv,\perp)$ and an isomorphism of
trialgebras

$(kX_{i},\vdash,\dashv,\perp)\cong\mathsf{V}^{(3)}(X_{i}|S_{i}),$

where we identify the set $S_{i}$ with the set $\\{x\delta y-\\{x\delta
y\\}\mid x,y\in X_{i},\delta\in\\{\vdash,\dashv,\perp\\}\\}.$

Clearly, $(X_{i},\vdash,\dashv,\perp)$ is isomorphic to the subtrioid of
$\mathsf{V}^{(3)}(X_{i}|S_{i})$ generated by the set
$\\{x+\mathsf{Id}^{(3)}(S_{i})\mid x\in X_{i}\\}$. Therefore, by Lemma 2.8,
$(X_{i},\vdash,\dashv,\perp)$ is isomorphic to the subtrioid of $k\langle
X_{i}\cup\dot{X_{i}}|\Psi_{3}(S_{i})\cup\varphi(\Psi_{3}(S_{i}))\rangle^{(3)}$
generated by the set

$\dot{X_{i}}+\mathsf{Id}(\Psi_{3}(S_{i})\cup\varphi(\Psi_{3}(S_{i}))):=\\{\dot{x}+\mathsf{Id}(\Psi_{3}(S_{i})\cup\varphi(\Psi_{3}(S_{i})))\mid\dot{x}\in\dot{X}_{i}\\}.$

Finally, by Lemmas 3.2 and 2.8, the subtrioid of $k\langle\cup_{i\in
I}(X_{i}\cup\dot{X_{i}})|\cup_{i\in
I}(\Psi_{3}(S_{i})\cup\varphi(\Psi_{3}(S_{i})))\rangle^{(3)}$ generated
$\cup_{i\in
I}(\dot{X_{i}}+\mathsf{Id}(\Psi_{3}(S_{i})\cup\varphi(\Psi_{3}(S_{i})))$ is
the free product $\mathsf{Vid}^{(3)}(\cup_{i\in I}X_{i}|\cup_{i\in I}S_{i})$
of the family of trioids $\\{(X_{i},\vdash,\dashv,\perp)\mid i\in
I\\}=\\{\mathsf{Vid}^{(3)}(X_{i}|S_{i})\mid i\in I\\}$.

Denote by $\rho_{i}^{\prime}$ the congruence of $(X_{i},\vdash,\dashv,\perp)$
generated by

$\\{(x\delta y,x\delta^{\prime}y)\mid x,y\in
X_{i},\delta,\delta^{\prime}\in\\{\vdash,\dashv,\perp\\}\\}$

and define

$(B_{i},\vdash,\dashv,\perp):=(X_{i},\vdash,\dashv,\perp)/\rho_{i}^{\prime}.$

Suppose that $R_{i}$ is a Gröbner-Shirshov basis of $k\langle
X_{i}|\varphi(\Psi_{3}(S_{i}))\rangle$ containing $\varphi(\Psi_{3}(S_{i}))$,
and define

$X_{i}^{\prime}=X_{i}\setminus\\{\bar{f}\mid f\in R_{i}\\}.$

Then by Lemma 3.9, we deduce that

$X_{i}^{\prime}\rho_{i}^{\prime}:=\\{x\rho_{i}^{\prime}\mid x\in
X_{i}^{\prime}\\}$

forms a set of normal forms of elements in $(B_{i},\vdash,\dashv,\perp)$.
Therefore, we have

$(B_{i},\vdash,\dashv,\perp)=(X_{i},\vdash,\dashv,\perp)/\rho_{i}^{\prime}=(\\{x\rho_{i}^{\prime}\mid
x\in X_{i}\\},\vdash,\dashv,\perp)=(\\{x\rho_{i}^{\prime}\mid x\in
X_{i}^{\prime}\\},\vdash,\dashv,\perp).$

Define

$V_{3}=\mathsf{V}^{(3)}(\cup_{i\in I}X_{i}),\ Y_{3}=\cup_{i\in
I}(\dot{X_{i}}\cup X_{i}^{\prime}),$

and define

$\mathsf{FP}(X_{i})_{i\in I}=\\{y_{1}...y_{n}\in\Psi_{3}(V_{3})\mid
y_{1},...\leavevmode\hbox{}\hskip 0.56905pt,y_{n}\in
Y_{3},n\in\mathbb{N}^{+},\mathsf{ind}(y_{p})\neq\mathsf{ind}(y_{p+1}),p\leq
n-1\\}.$

Now we define operations $\vdash^{\prime},\dashv^{\prime},\perp^{\prime}$ on
$\mathsf{FP}(X_{i})_{i\in I}$ such that $(\mathsf{FP}(X_{i})_{i\in
I},\vdash^{\prime},\dashv^{\prime},\perp^{\prime})$ becomes the free product
of $\\{(X_{i},,\vdash,\dashv,\perp)\mid i\in I\\}$.

For all letters $y,z\in Y_{3}$, define $\mathsf{Red}(yz)$ to be the word $u$
in the free semigroup $Y_{3}^{+}$ such that $u+\mathsf{Id}(\cup_{i\in
I}(\Psi_{3}(S_{i})\cup\varphi(\Psi_{3}(S_{i})))$ is the normal form of
$yz+\mathsf{Id}(\cup_{i\in I}(\Psi_{3}(S_{i})\cup\varphi(\Psi_{3}(S_{i})))$
obtained in the associative algebra $k\langle\cup_{i\in
I}(X_{i}\cup\dot{X_{i}})|\cup_{i\in
I}(\Psi_{3}(S_{i})\cup\varphi(\Psi_{3}(S_{i}))\rangle$ by applying the
Grönber-Shirshov basis $\cup_{i\in I}(\Psi_{3}(S_{i})\cup R_{i})$. There exist
several cases:

(i) If $\mathsf{ind}(y)\neq\mathsf{ind}(z)$, then we have
$\mathsf{Red}(yz)=yz$;

(ii) If $y,z\in X_{i}^{\prime}$ for some index $i\in I$, then we can rewrite
$yz$ into a letter in $X_{i}^{\prime}$ by relations in $R_{i}$, namely, we
have $(y\vdash z)\rho_{i}^{\prime}=\mathsf{Red}(yz)\rho_{i}^{\prime}$ in
$(B_{i},\vdash,\dashv,\perp)$. (Note that in the trioid
$(B_{i},\vdash,\dashv,\perp)$, the operations $\vdash,\dashv,\perp$ coincide.)

(iii) If $y,z\in\dot{X_{i}}\cup X_{i}^{\prime}$ for some index $i\in I$ and
$\\{y,z\\}\cap\dot{X_{i}}\neq\emptyset$, then we can rewrite $yz$ into a
letter in $\dot{X_{i}}$ by relations in $\Psi_{3}(S_{i})$. More precisely, if
$y=\dot{a}\in\dot{X_{i}}$ and $z\in X_{i}^{\prime}$, then
$\mathsf{Red}(yz)=\dot{b}$, where $b$ is the letter in $X_{i}$ such that we
have $b=a\dashv z$ in $(X_{i},\vdash,\dashv,\perp)$; if $y\in X_{i}^{\prime}$
and $z=\dot{a}\in\dot{X_{i}}$, then $\mathsf{Red}(yz)=\dot{c}$, where $c$ is
the letter in $X_{i}$ such that we have $c=y\vdash a$ in
$(X_{i},\vdash,\dashv,\perp)$; if $y=\dot{a}$ and $z=\dot{b}$, then
$\mathsf{Red}(yz)=\dot{d}$, where $d$ is the letter in $X_{i}$ such that we
have $d=a\perp b$ in $(X_{i},\vdash,\dashv,\perp)$.

By Corollary 3.8, we obtain the main result of this article, in which we
construct free products of arbitrary (disjoint) trioids.

######  Theorem 3.10.

Let $\\{(X_{i},\vdash,\dashv,\perp)\mid i\in I\\}$ be a family of disjoint
trioids. Then $(\mathsf{FP}(X_{i})_{i\in
I},\vdash^{\prime},\dashv^{\prime},\perp^{\prime})$ is the free product of
$\\{X_{i}\mid i\in I\\}$ with the following products:

$\displaystyle
y_{1}...y_{n}\vdash^{\prime}z_{1}...z_{m}=\varphi(y_{1})...\varphi(y_{n-1})\mathsf{Red}(\varphi(y_{n})z_{1})z_{2}...z_{m},$
$\displaystyle
y_{1}...y_{n}\dashv^{\prime}z_{1}...z_{m}=y_{1}...y_{n-1}\mathsf{Red}(y_{n}\varphi(z_{1}))\varphi(z_{2})...\varphi(z_{m}),$
$\displaystyle
y_{1}...y_{n}\perp^{\prime}z_{1}...z_{m}=y_{1}...y_{n-1}\mathsf{Red}(y_{n}z_{1})z_{2}...z_{m},$

for all $y_{1}...y_{n},z_{1}...z_{m}\in\mathsf{FP}(X_{i})_{i\in I}$.

###### Proof.

Denote $\cup_{i\in I}(\Psi_{t}(S_{i})\cup\varphi(\Psi_{t}(S_{i})))$ by $S$,
and denote $\cup_{i\in I}\dot{X_{i}}$ by $\dot{X}$. Obviously,
$(\mathsf{FP}(X_{i})_{i\in I},\vdash^{\prime},\dashv^{\prime},\perp^{\prime})$
is isomorphic to the sub-trioid of $\mathcal{A}_{3}:=k\langle\cup_{i\in
I}(X_{i}\cup\dot{X_{i}})|S\rangle$ generated by
$\dot{X}+\mathsf{Id}(S):=\\{\dot{x}+\mathsf{Id}(S)\mid\dot{x}\in\dot{X}\\}$,
which is isomorphic to $\mathsf{Vid}^{(3)}(\cup_{i\in I}X_{i}|\cup_{i\in
I}S_{i})$. The result follows immediately. ∎

######  Remark 3.11.

Similar to Theorem 3.10, one can obtain a set of normal forms for free product
of arbitrary dimonoids and one can deduce the multiplication table for the
free product, which turns out to be essentially the same as that constructed
in [17].

## References

  * [1] G.M. Bergman, The diamond lemma for ring theory, Adv. Math. 19  (1978) 178–218.
  * [2] L.A. Bokut and Y.Q. Chen, Gröbner–Shirshov bases and their calculation, Bull. Math. Sci. 4(3) (2014) 325–395.
  * [3] L.A. Bokut, Y.Q. Chen and C.H. Liu, Gröbner-Shirshov bases for dialgebras,  Internat. J. Algebra Comput. 20(3) (2010) 391–415.
  * [4] L.A. Bokut, Y. Fong and W.F. Ke, Gröbner-Shirshov bases and composition lemma for associative conformal algebras: an example, Fundanmental and applied mathematics 6 (2006) 669–706.
  * [5] L.A. Bokut and K.P. Shum, Gröbner-Shirshov bases in algebra: an elmentary approach, Southeast Asian Bulletin of Mathematics 29(6) (2005) 20–25.
  * [6] B. Buchberger, An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal, Translated from the 1965 German original by Michael P. Abramson, J. Symbolic Comput. 41 (2006) 475–511.
  * [7] J.M. Casas, Trialgebras and Leibniz 3-algebras, Bol. Soc. Mat. Mex. 12(2) (2006) 165–178.
  * [8] Y.Q. Chen and G.L. Zhang, A new Composition-Diamond lemma for dialgebras, Algebra Colloquium 24(1) (2017) 323–350.
  * [9] K.J. Ebrahimi-Fard, Loday-type algebras and the Rota-Baxter relation. Lett. Math. Phys. 61(2) (2002) 139–147.
  * [10] P.S. Kolesnikov, Gröbner-Shirshov bases for replicated algebras, Algebra Colloquium 24(4) (2017) 563–576.
  * [11] P.S. Kolesnikov, Varieties of dialgebras and conformal algebras, Siberian Mathematical Journal 49(2) (2008) 257–272.
  * [12] J.-L. Loday, A.Frabetti, F. Chapoton and F. Goichot, Dialgebras and related operads, Lecture Notes in Mathematics, vol. 1763, Springer-Verlag, Berlin, 2001.
  * [13] J.-L. Loday and M.O. Ronco, Trialgebras and families of polytopes, Comtemp. Math. 346 (2004) 369–398.
  * [14] J.C. Novelli and J.Y. Thibon, Polynomial realizations of some trialgebras. In: 18th Conference on Formal Power Series and Algebraic Combinatoricas. San Diego, USA, (2006) 243–254.
  * [15] A.I. Shirshov, Some algorithmic problems for Lie algebras, Siberian Math. 3 (1962) 292–296.
  * [16] A.V. Zhuchok, Free commutative trioids, Semigroup Forum 98 (2019) 355–368.
  * [17] A.V. Zhuchok, Free products of dimonoids, Quasigroups Relat. Syst. 21(2) (2013) 273–278
  * [18] A. V. Zhuchok, Free products of doppelsemigroups, Algebra Universalis 77 (2017) 361–374.
  * [19] A.V. Zhuchok, Structure of relatively free dimonoids, Comm. Algebra. 45(4) (2017) 1639–1656.
  * [20] A.V. Zhuchok, Trioids, Asian Eur. J. Math. 8(4) (2015) 1550089 (23 pages).
  * [21] Y.V. Zhuchok, Free abelian dimonoids, Algebra and Discrete Mathematics 20(2) (2015) 330–342.