# Advances in Quantum Deep Learning: An Overview

Siddhant Garg Goutham Ramakrishnan11footnotemark: 1
Department of Computer Sciences
University of Wisconsin–Madison
<EMAIL_ADDRESS>Equal contribution by authors

###### Abstract

The last few decades have seen significant breakthroughs in the fields of deep
learning and quantum computing. Research at the junction of the two fields has
garnered an increasing amount of interest, which has led to the development of
quantum deep learning and quantum-inspired deep learning techniques in recent
times. In this work, we present an overview of advances in the intersection of
quantum computing and deep learning by discussing the technical contributions,
strengths and similarities of various research works in this domain. To this
end, we review and summarise the different schemes proposed to model quantum
neural networks (QNNs) and other variants like quantum convolutional networks
(QCNNs). We also briefly describe the recent progress in quantum inspired
classic deep learning algorithms and their applications to natural language
processing.

##  1 Introduction

In recent years, deep neural networks have led to breakthroughs in several
domains of machine learning, such as computer vision [58, 31, 89], natural
language processing [97, 23], reinforcement learning [85], speech recognition
[22], etc. Deep Learning [51] forms the backbone of a majority of modern
machine learning techniques and has become one of the most active research
areas in computer science, spurred on by increased availability of data and
computational resources.

Parallelly, there has been remarkable progress in the domain of quantum
computing focused towards solving classically intractable problems through
computationally cheaper techniques. A major leap forward in quantum computing
came when Shor [84, 83] proposed his famous algorithm for prime factoring
numbers in polynomial time, which exposed the vulnerabilities of security
protocols such as RSA. Consequent research has been aimed at developing poly-
time alternatives of classical algorithms utilising the core idea of quantum
superposition and entanglement. We briefly describe these ideas when reviewing
basic principles of quantum computing.

Quantum computing naturally lends its ideas to the domain of machine learning
and consequently there been active research on trying to use principles of
quantum computing to improve the representation power and computational
efficiency of classical ML approaches. Quantum extensions to classical ML
problems have gained prominence in recent times, such as clustering [56, 41,
67], support vector machines [69], gradient descent for linear systems [40],
principal component analysis [57], Boltzmann machines [6], feature extraction
[102], recommendation systems [39], EM algorithm for Gaussian Mixture Models
[42], variational generations for adversarial learning [72], etc.

The perceptron [74] represents a single neuron and forms the basic unit of the
deep learning architectures. The idea of a quantum perceptron was first
proposed by Kak [38] in 1995 and has since been formalized in multiple works
[29, 71, 79, 99, 13, 21, 24, 81, 8]. Recently, Wiebe et al. [101] showed that
quantum computing can provide a more comprehensive framework for deep learning
than classical computing and can help optimization of the underlying objective
function.

In this work, we summarise the different ideas presented in the domain of
quantum deep learning which include quantum analogues to classic deep learning
networks and quantum inspired classic deep learning algorithms. We present the
different schemes proposed to model quantum neural networks (QNNs) and their
corresponding variants like quantum convolutional networks (QCNNs).

This work is structured as follows: we first review the basics of classical
deep learning and quantum computing in Sections 2 and 3, for the benefit of an
uninitiated reader. In Section 4, we provide a detailed overview of Quantum
Neural Networks as formulated in several works, by examining its individual
components analogous to a classical NN. We also briefly summarize several
variants of QNNs and their proposed practical implementations. In Section 5,
we review works that develop quantum analogues to classical convolutional and
recurrent neural networks (CNNs and RNNs). In Section 6, we mention several
classical deep learning algorithms which have been inspired by quantum
methods, including applications to natural language processing.

##  2 Basic Principles of Classical Deep Learning

Neural networks represent a subset of machine learning methods, which try to
mimic the structure of the human brain in order to learn. Neurons are the
fundamental computational units in neural networks. Each neuron performs a
sequence of computations on the inputs it receives to give an output. Most
commonly, this computation is a linear combination of the inputs followed by a
non-linear operation, i.e. the output is $F(\sum_{i=1}^{N}w_{i}x_{i})$ where
$x_{i}$ are the inputs to the neuron. The $w_{i}$ are the parameters of the
neuron, and $F(.)$ is the non-linear function. Commonly used non-linear
functions are the Rectified Linear Unit (ReLU) and the sigmoid function
$\sigma$:

$ReLU(x)=max(0,x)\quad,\quad\sigma(x)=\frac{1}{1+e^{-x}}$

Neural network architectures are constructed by stacking neurons. In fully-
connected feedforward neural networks, the output of each neuron in the
previous layer is fed to each neuron in the next layer. The simplest neural
network is the fully-connected network with one hidden layer (Figure 1). Let
the input $x$ be $d_{1}$-dimensional and output be $d_{2}$-dimensional. Then,
a NN a single hidden layer of $h$ units performs the following computation:

$N(x)=W_{2}\cdot F(W_{1}\cdot x)$

$W_{1}$ and $W_{2}$ are weight matrices of dimensions $h\crossproduct d_{1}$
and $d_{2}\crossproduct h$ respectively. The non-linear function $F$ is
applied element-wise to the vector input. This can be generalized to a NN with
$M$ hidden layers as:

$N(x)=W_{M+1}\cdot F(W_{M}\cdot F(W_{M-1}\cdot...\ F(W_{1}\cdot x)...)$

The universal approximation theorem [19, 52] states that, a neural network
with a single hidden layer can approximate any function, under assumptions on
its continuity. However, it is known that deeper networks (with greater number
of hidden layers) learn more efficiently and generalize better than shallow
networks [63, 61]. Increased availability of data, greater complexity of tasks
and the development of hardware resources such as GPUs have led to the use of
deeper and deeper neural networks, thus the term ‘deep learning’.

Figure 1: A simple feedforward NN with one hidden layer (Figure from [2])
Figure 2: The structure of a simple convolutional neural network (Figure from
[109])

#### Parameter Learning

Like most machine learning algorithms, tasks in deep learning are posed as
Empirical Risk Minimization (ERM) problems. Fundamentally, the parameter
learning is done through gradient based optimization methods to minimize a
loss function. The loss function is computed over the training data, and
depends on the task at hand. Common loss functions include the 0/1 and cross-
entropy loss for classification tasks, $l_{2}$-loss for regression tasks and
reconstruction loss for autoencoder tasks (a form of unsupervised learning).
The backpropagation algorithm [78, 49] uses the chain-rule to offer a
computationally efficient way of obtaining gradients in neural networks.
Learning is known to be highly sensitive to the optimization algorithm [45,
48] as well as the initialization of the parameters [28].

#### Complex Neural Architectures

The past decades of deep learning research have led to several breakthroughs
such as convolutional neural networks [26, 50, 47] (designed for learning
hierarchical and translation-invariant features in images), recurrent neural
networks [77, 34] (for sequential data such as time series and natural
language), ResNets [30] (designed to combat the vanishing gradient problem in
deep learning) and Transformers [98] (the current state of the art method in
natural language processing).

#### CNNs

Convolutional neural networks (CNNs) have revolutionized the field of computer
vision, since LeCun et al. [49] demonstrated how to use back propagation to
efficiently learn feature maps. They form the basis of most state-of-the-art
tasks in modern computer vision, and are widely deployed in applications
including image processing, facial recognition, self-driving cars, etc.

Classical CNNs are designed to capture hierarchical learning of translation-
invariant features in structured image data, through the use of convolutional
and pooling layers. Convolutional layers consist of multiple convolutional
filters, each of which computes an output feature map by convolving local
subsections of the input iteratively. Pooling layers perform subsampling to
reduce the dimensionality of the feature maps obtained from convolutional
layers, most commonly by taking the maximum or mean of several nearby input
values. A non-linear activation is usually applied to the output of the
pooling layer.

A typical CNN architecture for image classification consists of several
successive blocks of convolutional$\rightarrow$pooling$\rightarrow$non-linear
layers, followed by a fully connected layer (Figure 2). Convolutional filters
learn different input patterns, at different levels of abstraction depending
upon the depth of the layer. For image inputs, the initial layers of the CNN
learn to recognize simple features such as edges. The features learnt by
successive layers become increasingly complex and domain specific, through a
combination of features learnt in previous layers. CNNs are a powerful
technique, and several papers have adapted its ideas to the quantum setting,
and we discuss these in Section 5.

Figure 3: The structure and temporal unfolding of a simple RNN (Figure from
[25])

#### RNNs

Feedforward neural networks are constrained as they perform predefined
computations on fixed-size inputs. Recurrent Neural Networks (RNNs) are
designed to handle sequences of inputs, operating on one input at a time while
retaining information about preceding inputs through a hidden state. For a
sequential input $x=(x^{(1)},\dots,x^{(L)})$, the simplest RNN performs the
following computation:

$h_{t}=F(x_{t},h_{t-1}),\ \ o_{t}=G(h_{t}),\ \ t=1,\dots,L$

$h_{t}$ and $o_{t}$ refer to the hidden state and output of the RNN at step
$t$ of the sequence, $h_{0}$ is the initial hidden state, $F$ and $G$ are
functions to be learnt. RNNs can also be used to learn representations of
sequence inputs for different down stream tasks with the final hidden state
$h_{L}$ as the embedding of the input $x$. Figure 3 shows the the temporal
unfolding of a simple RNN.

RNNs are trained using Backpropagation-through-time (BPPT) [100], a temporal
extension of the backpropagation algorithm. The versatility of RNNs is such
that they are used for a wide variety of applications: sequential-input
single-output (e.g. text classification), single-input sequential-output (e.g.
image captioning) and sequential-input sequential-output (e.g. part-of-speech
tagging, machine translation) tasks. Several innovations have improved the
performance of the vanilla RNN described above, such as LSTM [34] and GRU
[15], bidirectional RNNs [80], attention mechanism [7], encoder-decoder
architecture [14] and more.

##  3 Principles of Quantum Computing

The qubit is the basic unit of information in quantum computing. The power of
quantum computing over classical computing derives from the phenomena of
superposition and entanglement exhibited by qubits. Unlike a classical bit
which has a value of either 0 or 1, superposition allows for a qubit to exist
in a combination of the two states. In general, a qubit is represented as:

$\ket{\psi}=\alpha\ket{0}+\beta\ket{1}$

$\ket{0}$ and $\ket{1}$ represent the two computational basis states, $\alpha$
and $\beta$ are complex amplitudes corresponding to each, satisfying
$|\alpha|^{2}+|\beta|^{2}=1$. Observing a qubit causes a collapse into one of
the basis states. The probability of each state being observed is proportional
to the square of the amplitude of its coefficient, i.e. the probabilities of
observing $\ket{0}$ and $\ket{1}$ are $|\alpha|^{2}$ and $|\beta|^{2}$
respectively. A qubit is physically realizable as a simple quantum system, for
example the two basis states may correspond to the horizontal and vertical
polarization of a photon. Superposition allows quantum computing systems to
potentially achieve exponential speedups over their classical counterparts,
due to the parallel computations on the probabilistic combinations of states.

Entanglement refers to the phenomenon by which qubits exhibit correlation with
one another. In general, a set of $n$ entangled qubits exist as a
superposition of $2^{n}$ basis states. Observing one or more qubits among them
causes a collapse of their states, and alters the original superposition to
account for the observed values of the qubits. For example, consider the
2-qubit system in the following initial state:

$\ket{\psi}=\frac{1}{\sqrt{3}}\ket{00}+\frac{1}{\sqrt{3}}\ket{01}+\frac{1}{\sqrt{6}}\ket{10}+\frac{1}{\sqrt{6}}\ket{11}$

Suppose a measurement of the first qubit yields a value of 0 (which can occur
with probability $\frac{2}{3}$). Then, $\psi$ collapses into:

$\ket{\psi^{\prime}}=\frac{1}{\sqrt{2}}\ket{00}+\frac{1}{\sqrt{2}}\ket{01}$

Note that the relative probabilities of the possible states are conserved,
after accounting for the state collapse of the observed qubits.

#### Quantum operators

In classical computing, two fundamental logic gates (AND and OR) perform
irreversible computations, i.e. the original inputs cannot be recovered from
the output. Quantum gates (which operate on qubits) are constrained to be
reversible, and operate on the input state to yield an output of the same
dimension. In general, quantum gates are represented by unitary matrices,
which are square matrices whose inverse is their complex conjugate.

An $n$-qubit system exists as a superposition of $2^{n}$ basis states. Its
state can be described by a $2^{n}$ dimensional vector containing the
coefficients corresponding to each basis state. For example, the $\ket{\psi}$
vector above may be described by the vector
$[\frac{1}{\sqrt{3}},\frac{1}{\sqrt{3}},\frac{1}{\sqrt{6}},\frac{1}{\sqrt{6}}]^{T}$
using the basis vectors.

Thus, a $n$-qubit quantum gate $H$ represents a $2^{n}\times 2^{n}$ unitary
matrix that acts on the state vector. Two common quantum gates are the
Hadamard and CNOT gates. The Hadamard gate acts on 1-qubit and maps the basis
states $\ket{0}$ and $\ket{1}$ to $\frac{\ket{0}+\ket{1}}{\sqrt{2}}$ and
$\frac{\ket{0}-\ket{1}}{\sqrt{2}}$ respectively. The CNOT gate acts on
2-qubits and maps $\ket{a,b}$ to $\ket{a,a\oplus b}$. In other words, the
first bit is copied, and the second bit is flipped if the first bit is 1. The
unitary matrices corresponding to the Hadamard and CNOT gates are:

$H=\frac{1}{\sqrt{2}}\begin{bmatrix}1&1\\\ 1&-1\end{bmatrix},\text{on the
basis }[\ \ket{0},\ket{1}\ ]$ $CNOT=\begin{bmatrix}1&0&0&0\\\ 0&1&0&0\\\
0&0&0&1\\\ 0&0&1&0\\\ \end{bmatrix},\text{on the basis }[\
\ket{00},\ket{01},\ket{10},\ket{11}\ ]$

The Pauli matrices ($\\{\sigma_{x},\sigma_{y},\sigma_{z}\\}$) are a set of
three $2\times 2$ complex matrices which form a basis for the real vector
space of 2 × 2 Hermitian matrices along with the $2\times 2$ identity matrix.

$\sigma_{x}=\begin{bmatrix}0&1\\\ 1&0\\\
\end{bmatrix},\sigma_{y}=\begin{bmatrix}0&-i\\\ i&0\\\
\end{bmatrix},\sigma_{z}=\begin{bmatrix}1&0\\\ 0&-1\\\ \end{bmatrix}$

For a $d$ dimensional function space, the density operator $\rho$ represents a
mixed state and is defined as:

$\rho=\sum_{i=0}^{2^{d}}p_{i}\ket{\psi_{i}}\bra{\psi_{i}}$

where $\\{\psi_{i}\\}$ represent the computational bases of the
$\mathcal{H}^{2^{n}}$ Hilbert space, the coefficients $p_{i}$ are non-negative
probabilities and add up to $1$, and $\ket{\psi}\bra{\psi}$ is an outer
product written in bra-ket notation. The expected value of a measurement $X$
can be obtained using the density operator using the following formula:

$\langle X\rangle=\sum_{i}p_{i}\bra{\psi_{i}}X\ket{\psi_{i}}=\sum_{i}p_{i}\
tr(\ket{\psi_{i}}\bra{\psi_{i}}X)=tr(\rho X)$

where $tr$ denotes the trace of the matrix.

##  4 Quantum Neural Network

Multiple research works [29, 71, 79, 99, 13, 21, 24, 81, 8] have proposed
formulations for a quantum neural network(QNN) as a quantum analogue to a
perceptron. Ricks and Ventura [71] were one of the earliest to propose a QNN
which was modelled using a quantum circuit gate whose weights were learned
using quantum search and piecewise weight learning. Several of these papers
share a high level idea with respect to formulating the QNN through reversible
unitary transforms on the data and then learning them through an approach
analogous to the backpropagation algorithm. In this section, we present an
overview of a QNN by breaking its components for learning a
regression/classification problem in the quantum setting.

###  4.1 Representing the input

Inherently, the classical neural network computations are irreversible,
implying a unidirectional computation of the output given the input. When
mathematically posed, a classical NN computes the output $y$ from the input:
$(x_{1},x_{2},\dots,x_{d})\rightarrow y$. In contrast, quantum mechanics
inherently depends on reversible transforms and a quantum counterpart for
transforming the inputs to outputs for a NN can be posed by adding an
ancillary bit to the input to obtain the output:
$(x_{1},x_{2},\dots,x_{d},0)\rightarrow(x_{1}^{\prime},x_{2}^{\prime},\dots,x_{d}^{\prime},y)$.
Muthukrishnan [64] show that such an operation can be always represented
through a permutation matrix. To make the input representation unitary, we
represent the input component of the vector $(x_{1},\dots,x_{d})$ through a
quantum state $\ket{\psi}_{1,\dots,d}$. An ancillary dummy qubit can be added
to $\ket{\psi}_{1,\dots,d}$ corresponding to the output $y$. The reversible
transformation is thus rendered unitary in the quantum setting as:
$\ket{\psi}_{1,\dots,d}\ket{0}\rightarrow\ket{\psi^{\prime}}_{1,\dots,d}\ket{y}$
where $\ket{\psi^{\prime}}_{1,\dots,d}$ represents the transformed input
qubits. For multi-class classification problems, when the output labels cannot
be captured by a single qubit, one can allocate $\mathcal{O}(logK)$ output
qubits to represent the label where $K$ is the number of label classes.

QNNs can take as input purely quantum data or transformation of classical data
into quantum states. When representing quantum data, $\ket{\psi}_{1,\dots,d}$
can be a superposition of the $2^{d}$ computational basis in the
$d$-dimensional Hilbert space
$\mathcal{H}^{2^{d}}=\mathcal{H}^{2}\otimes\dots\otimes\mathcal{H}^{2}$ where
$\mathcal{H}^{2}$ represents the 2-dimensional Hilbert space with basis
$\\{\ket{0},\ket{1}\\}$ and the basis for $\mathcal{H}^{2^{d}}$ are
$\\{\ket{0,0,\dots,0},\dots,\ket{1,1,\dots,1}\\}$. Thus
$\ket{\psi}_{1,\dots,d}$ can be denoted as
$\ket{\psi}_{1,\dots,d}=\sum_{i=1}^{2^{d}}a_{i}\ket{z_{i}}$ where
$a_{i},i\in\\{1,\dots,2^{d}\\}$ represents the complex amplitudes assigned to
computational basis states $\ket{z_{i}}\in\mathcal{H}^{2^{d}}$.

While exploiting truly quantum data is the eventual goal of developing QNN
models, the majority of related works shift their focus to the immediate
benefits derived from QNNs over classical data. To transform classical data to
a quantum state represented through qubits, several popular strategies have
been put to use. An easy strategy, popularly used by several QNN proposals
[24], is to binarize each individual component $x_{i},i\in\\{1,\dots,d\\}$ of
the input $x=(x_{1},x_{2},\dots,x_{d})$ through a threshold, and then
represent each binarized dimension $x_{i}$ as a corresponding
$\ket{0}/\ket{1}$ qubit resulting in $x$ being represented as a computational
basis in the $\mathcal{H}^{2^{d}}$ Hilbert space. This approach leads to a
high loss of information contained in the data. To counter this, Allcock et
al. [3] suggest capturing a more fine-grained representation of $x$ as a
superposition of computational basis in the $\mathcal{H}^{2^{d}}$ Hilbert
space. For example, let $\ket{i}$ denote the computational basis corresponding
to the quantum state $\ket{0,\dots,1,\dots,0}$ with the qubit 1 in the
$i^{th}$ position for each dimension $i\in\\{1,\dots,d\\}$. Then $x$ can be
represented as a quantum state
$\ket{\psi}_{1,\dots,d}=\sum_{i=1}^{d}b_{i}\ket{i}$ where
$b_{i}=\frac{x_{i}}{||x||}$.

In parallel work, some strategies have been proposed in the continuous-
variable architecture [44], which encodes the input to quantum states through
continuous degrees of freedom such as the amplitudes of the electromagnetic
fields. This approach avoids the information loss due to the discretization of
continuous inputs, however at the cost of complexity of practical realization.

Figure 4: Illustration of a $L$ layered quantum circuit QNN where the input is
$\ket{\psi}\ket{0}$ and the final output is measured through a Pauli-y
operator on the ancillary bit (Figure from [24])

###  4.2 Modeling the Quantum Network

The quantum network has been most popularly modelled through learnable
variational quantum circuits [94] . A permutation matrix can be used to
transform
$\ket{\psi}_{1,\dots,d}\ket{0}\rightarrow\ket{\psi^{\prime}}_{1,\dots,d}\ket{y}$
and therefore is the simplest technique for the QNN model. Mathematically, a
square matrix $P$ is a permutation matrix if $PP^{T}=I$ and all entries of $P$
are either 0 or 1. However, the total number of distinct permutation matrices
is a discrete set of size $n!$ and therefore restricts the richness of
representations that they can capture. This transformation can be modelled
more richly using unitary matrices, which are characterized by learnable free
parameters. Any unitary matrix $U$ can be expressed as $U=e^{iH}$, where $H$
is a Hermitian matrix. Since every Hermitian matrix can be written as linear
combinations of tensor products of the Pauli matrices
($\\{\sigma_{x},\sigma_{y},\sigma_{z}\\}$) and the identity matrix($I$), the
unitary matrix $U$ over $K$ bits can be written as

$U=exp\bigg{[}i\big{(}\sum_{j_{1}=0,\dots,j_{K}=0}^{3,\dots,3}\alpha_{j_{1},j_{2},\dots,j_{K}}\times(\sigma_{j_{1}}\otimes\dots\otimes\sigma_{j_{K}})\big{)}\bigg{]}$

where $\sigma_{i}$ denotes $\\{I_{2\times
2},\sigma_{x},\sigma_{y},\sigma_{z}\\}$ respectively for $\\{i=0,1,2,3\\}$ and
$\alpha_{j_{1},j_{2},\dots,j_{K}}$ is the trainable free parameter. For
notational brevity, we will denote a K bit unitary $U$ as $U^{K}(\Theta)$
where $\Theta$ is the set of all free parameters
$\\{\alpha_{j_{1},j_{2},\dots,j_{K}}\\}_{j_{1}=0,\dots,j_{K}=0}^{j_{1}=3,\dots,j_{K}=3}$.
For our input representation $\ket{\psi}_{1,\dots,d}\ket{0}$ we need a $d+1$
bit unitary matrix to transform this to the output
$\ket{\psi^{\prime}}_{1,\dots,d}\ket{y}$. Thus the simple variant of a quantum
neural network, analogous to a single perceptron in the classical setting,
uses a single unitary matrix of dimension $d+1$ and can be denoted by

$U^{d+1}(\Theta)\ket{\psi}_{1,\dots,d}\ket{0}$

To capture detailed patterns in the input, a quantum neural network may be a
cascade of several variational circuits, similar to a classical deep neural
network. A sequential cascade of $L$ unitary matrices may be denoted as the
following (we skip writing the $U^{d+1}_{i}$ for notational brevity):

$\mathcal{U}(\Theta)=U_{L}(\Theta_{L})U_{L-1}(\Theta_{L-1})\cdots
U_{1}(\Theta_{1})$

where $U_{i}(\Theta_{i})$ denotes the unitary matrix corresponding to the
$i^{th}$ layer and $\Theta=\\{\Theta_{1},\dots,\Theta_{L}\\}$ is the set of
all parameters.

Some recent works [8] have further increased the modeling complexity of
$\mathcal{U}$ through a more direct inspiration from classical NNs: having
multiple hidden units for every layer in the model. We introduce an additional
notation for the mixed state density corresponding to the input state
$\ket{\psi}_{1,\dots,d}$ as
$\rho^{in}=\sum_{i=0}^{2^{d}}p_{i}\ket{\psi_{i}}\bra{\psi_{i}}$, where
$\psi_{i}$ denote the computational basis of the $\mathcal{H}^{2^{d}}$ Hilbert
space. In [8], the first layer $U_{1}$ initializes a state of
$\ket{0,\dots,0}$ of dimension $h$ (hidden state dimension) in addition to the
input state $\ket{\psi}_{1\dots d}\ket{0}$. $U_{1}$ is applied to
$\ket{\psi}_{1,\dots,d}\otimes\ket{0,\dots,0}_{h}\bra{0}$, where $\bra{0}$
corresponds to the ancillary output qubit. Here $U_{1}$ can be denoted as a
sequential product of multiple unitary matrices $U_{1}=U_{1}^{m_{1}}\dots
U_{1}^{2}U_{1}^{1}$ corresponding to $m_{1}$ number of perceptrons in layer
$1$. This transformation is denoted as
$X^{1}=U^{1}(\rho_{in}\otimes\ket{0,\dots,0}_{h}\bra{0}){U^{1}}^{\dagger}$.
From $X^{1}$, the density operator corresponding to the $h$ hidden state
qubits and the output ancillary qubit are extracted using a partial trace
operator, and fed to the next layer where the transforms are applied in the
same way. Having $m_{l}$ number of perceptrons in layer $l$ allows a greater
degree of freedom to the QNN to capture patterns in the data.

In the continuous variable architecture, Killoran et al. [44] model a QNN as a
variational quantum circuit, with gaussian and non-gaussian gates used to
implement linear and non-linear transformations.

###  4.3 Observing the Output

Schuld et al. [79] describe several works [60, 103] where measuring the output
from the network corresponds to the collapse of the superposition of quantum
states to a single value, forming a close analogue to the non-linearity
imposed in classical NNs through activation functions.

When the data is truly quantum in nature, the output state $\ket{y}$
corresponding to the input state $\ket{\psi}_{1,\dots,d}$ can be a pure
computational basis or a mixed quantum state. Let the the mixed state density
for the output state obtained from the QNN be denoted by $\rho^{out}$,
corresponding to the last qubit in the final quantum state obtained after the
unitary matrix operations. A popular measure of closeness between the observed
and actual output quantum state is their fidelity, which when averaged over
the training data can be mathematically represented as:

$C=\frac{1}{N}\sum_{x=1}^{N}\bra{y_{x}}\rho^{out}_{x}\ket{y_{x}}$

Beer et al. [8] show that the fidelity is a direct generalization of the
classical empirical risk. When the the output state $\ket{y}$ for the input is
mixed quantum state and not a computational basis, the fidelity expression can
simply be modified to account for the case when $\ket{y}$ is mixed.

When the input data was originally in a classical form and the output is a
classical scalar/vector value, measurement of the output state from the QNN
has been the popular approach [24, 99] to compute the cost function ($C$).
Farhi and Neven [24] measure a Pauli operator, say $\sigma_{y}$ on the readout
bit and denote this measurement by $Y$. Measuring $Y$ is probabilistic in the
different possible outcomes, and hence an average of $Y$ is measured for
multiple copies of the input $\ket{\psi}_{1,\dots,d}\ket{0}$. Averaging $Y$
computes the following:

$y^{out}=\bra{\psi_{1,\dots,d}\
0}\mathcal{U}(\Theta)^{\dagger}Y\mathcal{U}(\Theta)\ket{\psi_{1,\dots,d}\ 0}$

The loss $C$ can now be defined as a mean squared error or $0/1$ loss with
respect to this averaged value of $Y$ as:

$C_{MSE}=\frac{1}{N}\sum_{x=1}^{N}|y_{x}-y^{out}_{x}|^{2}\ \ \text{or}\ \
C_{0/1}=\frac{1}{N}\sum_{x=1}^{N}\mathds{1}[y_{x}=y^{out}_{x}]$

where $y_{x},y^{out}_{x}$ corresponds to the original output and averaged QNN
output for input $x$.

###  4.4 Learning network parameters

Similar to classical deep learning, the QNN parameters, $\Theta$ for
$\mathcal{U}$, are learnt by using first-order optimization techniques to
minimize a loss function over the dataset. The simplest gradient based update
rule is the following:

$\Theta\ \leftarrow\Theta-\eta\frac{\partial C(\Theta)}{\partial\Theta}$

where $\Theta$ are the parameters being learnt, $C$ is the loss computed over
the data and $\eta$ is the step-size. A second order estimate of the
derivative of a function can be found using the finite difference method as:

$\frac{dC(\Theta_{i})}{d\Theta_{i}}=\frac{C(\Theta_{i}+\epsilon)-C(\Theta_{i}-\epsilon)}{2\epsilon}+\mathcal{O}(\epsilon^{2})$

For this, the loss function $C$ for a particular value of the parameter set
$\Theta_{i}$ for the unitary matrix $\mathcal{U}$ of layer $i$, needs to be
estimated to within $\mathcal{O}(\epsilon^{3})$ and Farhi and Neven [24] show
that this requires $\mathcal{O}(\frac{1}{\epsilon^{6}})$ measurements. This
needs to be done for every layer parameter $\Theta_{i}$ independently
resulting in $L$ such repetitions for a $L$-layer QNN.

Under a special condition on the unitary matrices $U(\Theta)$ for the QNN
where they can be represented as $e^{i\Theta\Sigma}$ ($\Sigma$ being a tensor
product of Pauli operators $\\{\sigma_{x},\sigma_{y},\sigma_{z}\\}$ acting on
a few qubits), an explicit gradient descent update rule can be obtained. The
gradient of the cost function $C(\Theta)$ with respect to the $\Theta_{i}$ for
the $i^{th}$ layer parameters is given by:

$\frac{dC(\Theta)}{d\Theta_{i}}=2Im\big{(}\bra{\psi_{1,\dots,d}\
0}U_{1}^{\dagger}\dots U_{L}^{\dagger}YU_{L}\dots U_{i+1}\Sigma_{i}U_{i}\dots
U_{1}\ket{\psi_{1,\dots,d}\ 0}\big{)}$

where $\Sigma_{i}$ is the tensor product of Pauli operators corresponding to
layer $i$ defined above and $Im()$ refers to the imaginary part. Farhi and
Neven [24] make the interesting observation that $U_{1}^{\dagger}\dots
U_{L}^{\dagger}YU_{L}\dots U_{i+1}\Sigma_{i}U_{i}\dots U_{1}$ is a unitary
operation and can therefore be viewed as a quantum circuit of $2L+2$ unitaries
each acting on a few qubits, therefore enabling efficient gradient
computations.

###  4.5 QNN Variants

There have been multiple ideas proposed similar to a learnable QNN as
described above. Mitarai et al. [62] pose a problem through the lens of
learning a quantum circuit, very similar to the QNN, and use a gradient-based
optimization to learn the parameters. Romero et al. [73] introduce a quantum
auto-encoder for the task of compressing quantum states which is optimized
through classical algorithms. Ngoc and Wiklicky [65] propose an alternate QNN
architecture only using multi-controlled NOT gates and avoiding using
measurements to capture the non-linear activation functions of classical NNs.
Zhao and Gao [108] suggest interleaved quantum structured layers with
classical non-linear activations to model a variant of the QNN. Multiple ideas
[62, 108, 3] utilise a hybrid quantum-classical approach where the computation
is split so as to be easily computable on classical computers and quantum
devices.

###  4.6 Practical implementations of QNNs

While modelling a QNN has been a hot topic in the field of quantum deep
learning, several of the algorithms cannot be practically implemented due to
the poor representation capability of current quantum computing devices. There
has been considerable research in the field of practically implementing QNNs
[11] and developing hybrid quantum-classical algorithms which can successfully
perform computations using a small QRAM.

Early works in practically implementing QNNs used the idea of representing the
qubits through polarized optical modes and weights by optical beam splitters
and phase shifters [5]. Parallely, Behrman et al. [12] proposed implementing
the QNN through a quantum dot molecule interacting with phonons of a
surrounding lattice and an external field. Such a model using quantum dotshas
been extensively studied since [95, 10, 4].

Korkmaz et al. [46] used a central spin model as a practical implementation of
a QNN using a system of 2 coupled nodes with independent spin baths. A similar
idea was earlier proposed by Türkpençe et al. [96] using a collisional spin
model for representing the QNN thereby enabling them to analyse the Markovian
and non-Markovian dynamics of the system.

The majority of the recent research in the area of practical implementations
of QNNs has been centered on simulating quantum circuits on Noisy
Intermediate-Scale Quantum Computing (NISQ) devices. Shen et al. [82]
presented a neuromorphic hardware co-processor called Darwin Neural Processing
Unit (NPU) which is a practical implementation of the Spiking Neural Network
(SNN) [93, 36], a type of biologically-inspired NN which has been popularly
studied recently.

Potok et al. [68] conduct a study of performance of deep learning
architectures on 3 different computing platforms: quantum (a D-Wave processor
[37]), high performance, and neuromorphic and show the individual benefits of
each. Tacchino et al. [91] experimentally use a NISQ quantum processor and
test a QNN with a small number of qubits. They propose a hybrid quantum
classical update algorithm for the network parameters which is also parallely
suggested by [90].

##  5 Complex Quantum Neural Network Architectures

###  5.1 Quantum CNNs

Cong et al. [18] propose a quantum CNN through a quantum circuit model
adapting the ideas of convolutional and pooling layers from classical CNNs.
The proposed architecture (shown in Figure 5) is similarly layered, however it
differs in the fact that it applies 1D convolutions to the input quantum state
(contrary to 2D/3D convolutions on images). The convolutional layer is modeled
as a quasi-local unitary operation on the input state density $\rho_{in}$.
This unitary operator is denoted by $U_{i}$ and is applied on several
successive sets of input qubits, up to a predefined depth. The pooling layer
is implemented by performing measurements on some of the qubits and applying
unitary rotations $V_{i}$ to the nearby qubits. The rotation operation is
determined by the observations on the qubits. This combines the functionality
of dimensionality reduction (the output of $V_{i}$ is of lower dimension) as
well as non-linearity (due to the partial measurement of qubits). After the
required number of blocks of convolutional and pooling unitaries, the unitary
$F$ implements the fully connected layer. A final measurement on the output of
$F$ yields the network output.

Similar to classical CNNs, the overall architecture of the quantum CNN is
user-defined, whereas the parameters of the unitaries are learned. The
parameters are optimized by minimizing a loss function, for example by using
gradient descent using the finite difference method described in Section 4.4.
Cong et al. [18] demonstrate the effectiveness of the proposed architecture on
two classes of problems, quantum phase recognition (QPR) and quantum error
correction (QEC).

More recently, Kerenidis et al. [43] identify the relation between
convolutions and matrix multiplications, and propose the first quantum
algorithm to compute the forward pass of a CNN as a convolutional product.
They also provide a quantum back propagation algorithm to learn network
parameters through gradient descent. In an application of CNNs, Zhang et al.
[107] and Melnikov et al. [59] propose special convolutional neural networks
for extracting features from graphs, to identify graphs that exhibit quantum
advantage.

Figure 5: The Quantum CNN architecture proposed by Cong et al. [18]

###  5.2 Hybrid CNNs

Henderson et al. [32] introduce the quanvolutional layer, a transformation
based on random quantum circuits, as an additional component in a classical
CNN, thus forming a hybrid model architecture. Quanvolutional layers consist
of multiple quantum filters, each of which takes a matrix of 2D values as
input, and outputs a single scalar value. Similar to convolutional filters,
the operations are iteratively applied to subsections of the input. Each
quantum filter is characterized by an encoder, random circuit, and decoder,
where the encoder converts the raw input data into an initialization state to
be fed into the random circuit and the output from the circuit is fed to the
decoder which yielding a scalar value. [32] do not present a learning
methodology to optimize the random circuits since the quanvolutional layer has
no learnable parameters. However, the experimental results suggest that the
quanvolutional layer performed identically to a classical random feature
extractor, thus questioning its utility.

###  5.3 Quantum RNNs

There has also been several interesting suggestions to the front of developing
quantum variants of recurrent neural networks. Hibat-Allah et al. [33] propose
a quantum variant of recurrent neural networks(RNNs) using variational wave-
functions to learn the approximate ground state of a quantum Hamiltonian. Roth
[75] propose an iterative retraining approach using RNNs for simulating bulk
quantum systems via mapping translations of lattice vectors to the RNN time
index. Hopfield Networks [35] were a popular early form of a recurrent NN for
which several works [70, 92, 76] have proposed quantum variants.

##  6 Quantum inspired Classical Deep Learning

Quantum computing methods have been applied to classical deep learning
techniques by several researchers. Adachi and Henderson [1] suggest a quantum
sampling-based approach for generative training of Restricted Boltzmann
Machines, which is shown to be much faster than Gibbs sampling. Smith et al.
[86] use quantum mechanical (QM) DFT methods to train deep neural networks to
build an molecular energy estimating engine. Li et al. [55] propose to use
quantum based particle swarm optimization to find optimal CNN model
architectures. da Silva and de Oliveira [20] propose a quantum algorithm to
evaluate the performance of neural network architectures. Behera et al. [9]
use a quantum RNN variant to simulate a brain model, and use it to explain eye
tracking movements.

#### Natual Language Processing

Clark et al. [16], Coecke et al. [17] introduce a tensor product composition
model(CSC) to incorporate grammatical structure into algorithms that compute
meaning. Zeng and Coecke [104] show the shortcomings of the CSC model with
respect to computational overhead and resolve it using QRAM based quantum
algorithm for the closest vector problem.

Sordoni et al. [88], Zhang et al. [105] suggest a language modelling approach
inspired from the quantum probability theory which generalizes [87]. Zhang et
al. [106] present an improved variant of the quantum language model which has
higher representation capacity and can be easily integrated with neural
networks.

Galofaro et al. [27] tackle the problem of typification of semantic relations
between keyword couples in hate and non-hate speech using quantum geometry and
correlation. Li et al. [54] utilise the Hilbert space quantum representation
by assigning a complex number relative phase to every word and use this to
learn embeddings for text classification tasks. O’Riordan et al. [66] recently
present a hybrid workflow toolkit for NLP tasks where the classical corpus is
encoded, processed, and decoded using a quantum circuit model.

##  7 Conclusion

Quantum computing and deep learning are two of the most popular fields of
research today. In this work, we have presented a comprehensive and easy to
follow survey of the field of quantum deep learning. We have summarized
different schemes proposed to model quantum neural networks (QNNs), variants
like quantum convolutional networks (QCNNs) and the recent progress in quantum
inspired classic deep learning algorithms. There is a tremendous potential for
collaborative research at the intersection of the two fields, by applying
concepts from one to solve problems in the other. For example, Levine et al.
[53] demonstrate the entanglement capacity of deep networks, and therefore
suggest their utility for studying quantum many-body physics.

## References

  * Adachi and Henderson [2015] Steven H. Adachi and Maxwell P. Henderson.  Application of quantum annealing to training of deep neural networks.  _CoRR_ , abs/1510.06356, 2015.  URL http://dblp.uni-trier.de/db/journals/corr/corr1510.html#AdachiH15.
  * Ahmadian and Khanteymoori [2015] Sajad Ahmadian and Alireza Khanteymoori.  Training back propagation neural networks using asexual reproduction optimization.  05 2015.  doi: 10.1109/IKT.2015.7288738.
  * Allcock et al. [2018] Jonathan Allcock, Chang-Yu Hsieh, Iordanis Kerenidis, and Shengyu Zhang.  Quantum algorithms for feedforward neural networks.  _CoRR_ , abs/1812.03089, 2018.  URL http://dblp.uni-trier.de/db/journals/corr/corr1812.html#abs-1812-03089.
  * Altaisky et al. [2014] M. Altaisky, Natalia Kaputkina, and V. Krylov.  Quantum neural networks: Current status and prospects for development.  _Physics of Particles and Nuclei_ , 45:1013–1032, 11 2014\.  doi: 10.1134/S1063779614060033.
  * Altaisky [2001] M. V. Altaisky.  Quantum neural network, 2001.
  * Amin et al. [2018] Mohammad H. Amin, Evgeny Andriyash, Jason Rolfe, Bohdan Kulchytskyy, and Roger Melko.  Quantum boltzmann machine.  _Physical Review X_ , 8(2), May 2018.  ISSN 2160-3308.  doi: 10.1103/physrevx.8.021050.  URL http://dx.doi.org/10.1103/PhysRevX.8.021050.
  * Bahdanau et al. [2014] Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio.  Neural machine translation by jointly learning to align and translate, 2014.  URL http://arxiv.org/abs/1409.0473.
  * Beer et al. [2020] Kerstin Beer, Dmytro Bondarenko, Terry Farrelly, Tobias Osborne, Robert Salzmann, Daniel Scheiermann, and Ramona Wolf.  Training deep quantum neural networks.  _Nature Communications_ , 11:808, 02 2020.  doi: 10.1038/s41467-020-14454-2.
  * Behera et al. [2004] Laxmidhar Behera, Indrani Kar, and Avshalom Elitzur.  Quantum brain: A recurrent quantum neural network model to describe eye tracking of moving targets.  _Foundations of Physics Letters_ , 18, 07 2004.  doi: 10.1007/s10702-005-7125-6.
  * Behrman et al. [1999] E. C. Behrman, J. E. Steck, and S. R. Skinner.  A spatial quantum neural computer.  In _IJCNN’99. International Joint Conference on Neural Networks. Proceedings (Cat. No.99CH36339)_ , volume 2, pages 874–877 vol.2, 1999.
  * Behrman et al. [2002] E. C. Behrman, V. Chandrashekar, Z. Wang, C. K. Belur, J. E. Steck, and S. R. Skinner.  A quantum neural network computes entanglement, 2002.
  * Behrman et al. [2000] Elizabeth Behrman, L.R. Nash, James Steck, V.G. Chandrashekar, and S.R. Skinner.  Simulations of quantum neural networks.  _Information Sciences_ , 128:257–269, 10 2000.  doi: 10.1016/S0020-0255(00)00056-6.
  * Cao et al. [2017] Yudong Cao, Gian Giacomo Guerreschi, and Alán Aspuru-Guzik.  Quantum neuron: an elementary building block for machine learning on quantum computers, 2017.
  * Cho et al. [2014] Kyunghyun Cho, Bart van Merriënboer, Caglar Gulcehre, Fethi Bougares, Holger Schwenk, and Y. Bengio.  Learning phrase representations using rnn encoder-decoder for statistical machine translation.  06 2014.  doi: 10.3115/v1/D14-1179.
  * Chung et al. [2014] Junyoung Chung, Caglar Gulcehre, KyungHyun Cho, and Y. Bengio.  Empirical evaluation of gated recurrent neural networks on sequence modeling.  12 2014.
  * Clark et al. [2008] Stephen Clark, Bob Coecke, and Mehrnoosh.  A compositional distributional model of meaning.  2008\.
  * Coecke et al. [2010] Bob Coecke, Mehrnoosh Sadrzadeh, and Stephen Clark.  Mathematical foundations for a compositional distributional model of meaning, 2010.
  * Cong et al. [2019] Iris Cong, Soonwon Choi, and Mikhail D. Lukin.  Quantum convolutional neural networks.  _Nature Physics_ , 15(12):1273–1278, Aug 2019\.  ISSN 1745-2481.  doi: 10.1038/s41567-019-0648-8.  URL http://dx.doi.org/10.1038/s41567-019-0648-8.
  * Cybenko [1989] G. Cybenko.  Approximation by superpositions of a sigmoidal function.  _Mathematics of Control, Signals, and Systems (MCSS)_ , 2(4):303–314, December 1989.  ISSN 0932-4194.  doi: 10.1007/BF02551274.  URL http://dx.doi.org/10.1007/BF02551274.
  * da Silva and de Oliveira [2017] Adenilton Jose da Silva and Rodolfo Luan Franco de Oliveira.  Neural networks architecture evaluation in a quantum computer.  _2017 Brazilian Conference on Intelligent Systems (BRACIS)_ , Oct 2017\.  doi: 10.1109/bracis.2017.33.  URL http://dx.doi.org/10.1109/BRACIS.2017.33.
  * Daskin [2018] Ammar Daskin.  A simple quantum neural net with a periodic activation function.  _2018 IEEE International Conference on Systems, Man, and Cybernetics (SMC)_ , Oct 2018.  doi: 10.1109/smc.2018.00491.  URL http://dx.doi.org/10.1109/SMC.2018.00491.
  * Deng et al. [2013] li Deng, Geoffrey Hinton, and Brian Kingsbury.  New types of deep neural network learning for speech recognition and related applications: An overview.  pages 8599–8603, 10 2013.  doi: 10.1109/ICASSP.2013.6639344.
  * Devlin et al. [2019] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4171–4186, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics.  doi: 10.18653/v1/N19-1423.  URL https://www.aclweb.org/anthology/N19-1423.
  * Farhi and Neven [2018] Edward Farhi and Hartmut Neven.  Classification with quantum neural networks on near term processors.  2018\.
  * Feng et al. [2017] Weijiang Feng, Naiyang Guan, Yuan Li, Xiang Zhang, and Zhigang Luo.  Audio visual speech recognition with multimodal recurrent neural networks.  pages 681–688, 05 2017.  doi: 10.1109/IJCNN.2017.7965918.
  * Fukushima [1980] Kunihiko Fukushima.  Neocognitron: A self-organizing neural network model for a mechanism of pattern recognition unaffected by shift in position.  _Biological Cybernetics_ , 36:193–202, 1980.
  * Galofaro et al. [2018] Francesco Galofaro, Zeno Toffano, and Bich-Liên Doan.  Quantum semantic correlations in hate and non-hate speeches.  _Electronic Proceedings in Theoretical Computer Science_ , 283:62–74, Nov 2018.  ISSN 2075-2180.  doi: 10.4204/eptcs.283.5.  URL http://dx.doi.org/10.4204/EPTCS.283.5.
  * Glorot and Bengio [2010] Xavier Glorot and Y. Bengio.  Understanding the difficulty of training deep feedforward neural networks.  _Journal of Machine Learning Research - Proceedings Track_ , 9:249–256, 01 2010.
  * Gupta and Zia [2001] Sanjay Gupta and R.K.P. Zia.  Quantum neural networks.  _Journal of Computer and System Sciences_ , 63(3):355 – 383, 2001.  ISSN 0022-0000.  doi: https://doi.org/10.1006/jcss.2001.1769.  URL http://www.sciencedirect.com/science/article/pii/S0022000001917696.
  * He et al. [2015] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition, 2015.
  * He et al. [2016] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _The IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , June 2016.
  * Henderson et al. [2019] Maxwell Henderson, Samriddhi Shakya, Shashindra Pradhan, and Tristan Cook.  Quanvolutional neural networks: Powering image recognition with quantum circuits, 2019.
  * Hibat-Allah et al. [2020] Mohamed Hibat-Allah, Martin Ganahl, Lauren E. Hayward, Roger G. Melko, and Juan Carrasquilla.  Recurrent neural network wavefunctions, 2020.
  * Hochreiter and Schmidhuber [1997] Sepp Hochreiter and Jürgen Schmidhuber.  Long short-term memory.  _Neural computation_ , 9(8):1735–1780, 1997.
  * Hopfield [1982] J. J. Hopfield.  Neural networks and physical systems with emergent collective computational abilities.  _Proceedings of the National Academy of Sciences of the United States of America_ , 79(8):2554–2558, April 1982.  ISSN 0027-8424.  URL http://view.ncbi.nlm.nih.gov/pubmed/6953413].
  * Huh and Sejnowski [2018] Dongsung Huh and Terrence J Sejnowski.  Gradient descent for spiking neural networks.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, _Advances in Neural Information Processing Systems 31_ , pages 1433–1443. Curran Associates, Inc., 2018.
  * Johnson et al. [2011] M. W. Johnson, M. H. S. Amin, S. Gildert, T. Lanting, F. Hamze, N. Dickson, R. Harris, A. J. Berkley, J. Johansson, P. Bunyk, E. M. Chapple, C. Enderud, J. P. Hilton, K. Karimi, E. Ladizinsky, N. Ladizinsky, T. Oh, I. Perminov, C. Rich, M. C. Thom, E. Tolkacheva, C. J. S. Truncik, S. Uchaikin, J. Wang, B. Wilson, and G. Rose.  Quantum annealing with manufactured spins.  _Nature_ , 473(7346):194–198, May 2011.  ISSN 0028-0836.  doi: 10.1038/nature10012.
  * Kak [1995] Subhash Kak.  On quantum neural computing.  _Inf. Sci._ , 83(3–4):143–160, March 1995\.  ISSN 0020-0255.  doi: 10.1016/0020-0255(94)00095-S.  URL https://doi.org/10.1016/0020-0255(94)00095-S.
  * Kerenidis and Prakash [2016] Iordanis Kerenidis and Anupam Prakash.  Quantum recommendation systems, 2016.
  * Kerenidis and Prakash [2020] Iordanis Kerenidis and Anupam Prakash.  Quantum gradient descent for linear systems and least squares.  _Physical Review A_ , 101(2), Feb 2020.  ISSN 2469-9934.  doi: 10.1103/physreva.101.022316.  URL http://dx.doi.org/10.1103/PhysRevA.101.022316.
  * Kerenidis et al. [2019a] Iordanis Kerenidis, Jonas Landman, Alessandro Luongo, and Anupam Prakash.  q-means: A quantum algorithm for unsupervised machine learning.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d’Alché Buc, E. Fox, and R. Garnett, editors, _Advances in Neural Information Processing Systems 32_ , pages 4134–4144. Curran Associates, Inc., 2019a.
  * Kerenidis et al. [2019b] Iordanis Kerenidis, Alessandro Luongo, and Anupam Prakash.  Quantum expectation-maximization for gaussian mixture models, 2019b.
  * Kerenidis et al. [2020] Iordanis Kerenidis, Jonas Landman, and Anupam Prakash.  Quantum algorithms for deep convolutional neural networks.  In _International Conference on Learning Representations_ , 2020.  URL https://openreview.net/forum?id=Hygab1rKDS.
  * Killoran et al. [2018] Nathan Killoran, Thomas R. Bromley, Juan Miguel Arrazola, Maria Schuld, Nicolás Quesada, and Seth Lloyd.  Continuous-variable quantum neural networks.  _CoRR_ , abs/1806.06871, 2018.  URL http://dblp.uni-trier.de/db/journals/corr/corr1806.html#abs-1806-06871.
  * Kingma and Ba [2014] Diederik P. Kingma and Jimmy Ba.  Adam: A method for stochastic optimization, 2014.  URL http://arxiv.org/abs/1412.6980.  cite arxiv:1412.6980Comment: Published as a conference paper at the 3rd International Conference for Learning Representations, San Diego, 2015.
  * Korkmaz et al. [2019] Ufuk Korkmaz, Deniz TÃŒrkpençe, Tahir Çetin Akinci, and Serhat Şeker.  Evolution of entanglement in quantum neural network.  _IOP Conference Series: Materials Science and Engineering_ , 618:012006, oct 2019.  doi: 10.1088/1757-899x/618/1/012006.
  * Krizhevsky et al. [2012] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  In _Advances in neural information processing systems_ , pages 1097–1105, 2012.  URL http://papers.nips.cc/paper/4824-imagenet-classification-with-deep-convolutional-neural-networks.
  * Le et al. [2011] Quoc Le, Jiquan Ngiam, Adam Coates, Ahbik Lahiri, Bobby Prochnow, and Andrew Ng.  On optimization methods for deep learning.  volume 2011, pages 265–272, 01 2011.
  * LeCun et al. [1989] Y. LeCun, B. Boser, J. S. Denker, D. Henderson, R. E. Howard, W. Hubbard, and L. D. Jackel.  Backpropagation applied to handwritten zip code recognition.  _Neural Computation_ , 1(4):541–551, 1989.  doi: 10.1162/neco.1989.1.4.541.  URL https://doi.org/10.1162/neco.1989.1.4.541.
  * Lecun et al. [2000] Yann Lecun, Patrick Haffner, and Y. Bengio.  Object recognition with gradient-based learning.  08 2000.
  * LeCun et al. [2015] Yann LeCun, Yoshua Bengio, and Geoffrey Hinton.  Deep learning.  _Nature_ , 521(7553):436–444, 2015.  doi: 10.1038/nature14539.  URL https://doi.org/10.1038/nature14539.
  * Leshno et al. [1993] Moshe Leshno, Vladimir Ya. Lin, Allan Pinkus, and Shimon Schocken.  Multilayer feedforward networks with a nonpolynomial activation function can approximate any function.  _Neural Networks_ , 6(6):861–867, 1993.  URL http://dblp.uni-trier.de/db/journals/nn/nn6.html#LeshnoLPS93.
  * Levine et al. [2019] Yoav Levine, Or Sharir, Nadav Cohen, and Amnon Shashua.  Quantum entanglement in deep learning architectures.  _Physical Review Letters_ , 122(6), Feb 2019.  ISSN 1079-7114.  doi: 10.1103/physrevlett.122.065301.  URL http://dx.doi.org/10.1103/PhysRevLett.122.065301.
  * Li et al. [2018] Qiuchi Li, Sagar Uprety, Benyou Wang, and Dawei Song.  Quantum-inspired complex word embedding.  _Proceedings of The Third Workshop on Representation Learning for NLP_ , 2018.  doi: 10.18653/v1/w18-3006.  URL http://dx.doi.org/10.18653/v1/w18-3006.
  * Li et al. [2019] Yangyang Li, Junjie Xiao, Yanqiao Chen, and Licheng Jiao.  Evolving deep convolutional neural networks by quantum behaved particle swarm optimization with binary encoding for image classification.  _Neurocomputing_ , 362:156–165, 2019.  URL http://dblp.uni-trier.de/db/journals/ijon/ijon362.html#LiXCJ19.
  * Lloyd et al. [2013] Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost.  Quantum algorithms for supervised and unsupervised machine learning, 2013\.
  * Lloyd et al. [2014] Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost.  Quantum principal component analysis.  _Nature Physics_ , 10(9):631–633, Jul 2014.  ISSN 1745-2481.  doi: 10.1038/nphys3029.  URL http://dx.doi.org/10.1038/nphys3029.
  * Long et al. [2015] J. Long, E. Shelhamer, and T. Darrell.  Fully convolutional networks for semantic segmentation.  In _2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 3431–3440, 2015.
  * Melnikov et al. [2019] Alexey A. Melnikov, Leonid Fedichkin, and Alexander Alodjants.  Detecting quantum speedup by quantum walk with convolutional neural networks.  _CoRR_ , abs/1901.10632, 2019.  URL http://dblp.uni-trier.de/db/journals/corr/corr1901.html#abs-1901-10632.
  * Menneer and Narayanan [1995] Tamaryn Menneer and Ajit Narayanan.  Quantum-inspired neural networks.  06 1995.
  * Mhaskar et al. [2017] Hrushikesh Mhaskar, Qianli Liao, and Tomaso Poggio.  When and why are deep networks better than shallow ones?, 2017.  URL https://aaai.org/ocs/index.php/AAAI/AAAI17/paper/view/14849.
  * Mitarai et al. [2018] Kosuke Mitarai, Makoto Negoro, Masahiro Kitagawa, and Keisuke Fujii.  Quantum circuit learning, 2018.  URL http://arxiv.org/abs/1803.00745.  cite arxiv:1803.00745.
  * Montufar et al. [2014] Guido F Montufar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio.  On the number of linear regions of deep neural networks.  In Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger, editors, _Advances in Neural Information Processing Systems 27_ , pages 2924–2932. Curran Associates, Inc., 2014.
  * Muthukrishnan [1999] Ashok Muthukrishnan.  Classical and quantum logic gates: An introduction to quantum computing quantum information seminar, 1999.
  * Ngoc and Wiklicky [2020] Viet Pham Ngoc and Herbert Wiklicky.  Tunable quantum neural networks for boolean functions, 2020.
  * O’Riordan et al. [2020] Lee J. O’Riordan, Myles Doyle, Fabio Baruffa, and Venkatesh Kannan.  A hybrid classical-quantum workflow for natural language processing, 2020\.
  * Otterbach et al. [2017] J. S. Otterbach, R. Manenti, N. Alidoust, A. Bestwick, M. Block, B. Bloom, S. Caldwell, N. Didier, E. Schuyler Fried, S. Hong, P. Karalekas, C. B. Osborn, A. Papageorge, E. C. Peterson, G. Prawiroatmodjo, N. Rubin, Colm A. Ryan, D. Scarabelli, M. Scheer, E. A. Sete, P. Sivarajah, Robert S. Smith, A. Staley, N. Tezak, W. J. Zeng, A. Hudson, Blake R. Johnson, M. Reagor, M. P. da Silva, and C. Rigetti.  Unsupervised machine learning on a hybrid quantum computer, 2017.
  * Potok et al. [2017] Thomas E. Potok, Catherine Schuman, Steven R. Young, Robert M. Patton, Federico Spedalieri, Jeremy Liu, Ke-Thia Yao, Garrett Rose, and Gangotree Chakma.  A study of complex deep learning networks on high performance, neuromorphic, and quantum computers, 2017.  URL http://arxiv.org/abs/1703.05364.  cite arxiv:1703.05364.
  * Rebentrost et al. [2014] Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd.  Quantum support vector machine for big data classification.  _Physical Review Letters_ , 113(13), Sep 2014.  ISSN 1079-7114.  doi: 10.1103/physrevlett.113.130503.  URL http://dx.doi.org/10.1103/PhysRevLett.113.130503.
  * Rebentrost et al. [2018] Patrick Rebentrost, Thomas R. Bromley, Christian Weedbrook, and Seth Lloyd.  Quantum hopfield neural network.  _Physical Review A_ , 98(4), Oct 2018.  ISSN 2469-9934.  doi: 10.1103/physreva.98.042308.  URL http://dx.doi.org/10.1103/PhysRevA.98.042308.
  * Ricks and Ventura [2004] Bob Ricks and Dan Ventura.  Training a quantum neural network.  In S. Thrun, L. K. Saul, and B. Schölkopf, editors, _Advances in Neural Information Processing Systems 16_ , pages 1019–1026. MIT Press, 2004.  URL http://papers.nips.cc/paper/2363-training-a-quantum-neural-network.pdf.
  * Romero and Aspuru-Guzik [2019] Jonathan Romero and Alan Aspuru-Guzik.  Variational quantum generators: Generative adversarial quantum machine learning for continuous distributions, 2019.
  * Romero et al. [2017] Jonathan Romero, Jonathan P Olson, and Alan Aspuru-Guzik.  Quantum autoencoders for efficient compression of quantum data.  _Quantum Science and Technology_ , 2(4):045001, Aug 2017.
  * Rosenblatt [1958] F. Rosenblatt.  The perceptron: A probabilistic model for information storage and organization in the brain.  _Psychological Review_ , 65(6):386–408, 1958\.  ISSN 0033-295X.  doi: 10.1037/h0042519.  URL http://dx.doi.org/10.1037/h0042519.
  * Roth [2020] Christopher Roth.  Iterative retraining of quantum spin models using recurrent neural networks, 2020.
  * Rotondo et al. [2018] P Rotondo, M Marcuzzi, J P Garrahan, I Lesanovsky, and M Müller.  Open quantum generalisation of hopfield neural networks.  _Journal of Physics A: Mathematical and Theoretical_ , 51(11):115301, Feb 2018.
  * Rumelhart et al. [1986a] D. E. Rumelhart, G. E. Hinton, and R. J. Williams.  _Learning Internal Representations by Error Propagation_ , page 318–362.  MIT Press, Cambridge, MA, USA, 1986a.  ISBN 026268053X.
  * Rumelhart et al. [1986b] David E. Rumelhart, Geoffrey E. Hinton, and Ronald J. Williams.  Learning Representations by Back-propagating Errors.  _Nature_ , 323(6088):533–536, 1986b.  doi: 10.1038/323533a0.  URL http://www.nature.com/articles/323533a0.
  * Schuld et al. [2014] Maria Schuld, Ilya Sinayskiy, and Francesco Petruccione.  The quest for a quantum neural network.  _Quantum Inf. Process._ , 13(11):2567–2586, 2014\.  URL http://dblp.uni-trier.de/db/journals/qip/qip13.html#SchuldSP14.
  * Schuster and Paliwal [1997] M. Schuster and K. K. Paliwal.  Bidirectional recurrent neural networks.  _IEEE Transactions on Signal Processing_ , 45(11):2673–2681, 1997.
  * Shao [2018] Changpeng Shao.  A quantum model for multilayer perceptron, 2018.
  * Shen et al. [2015] Juncheng Shen, De Ma, Zonghua Gu, Ming Zhang, Xiaolei Zhu, Xiaoqiang Xu, Qi Xu, Yangjing Shen, and Gang Pan.  Darwin: a neuromorphic hardware co-processor based on spiking neural networks.  _Science China Information Sciences_ , 59:1–5, 12 2015\.  doi: 10.1007/s11432-015-5511-7.
  * Shor [1994] P. W. Shor.  Algorithms for quantum computation: Discrete logarithms and factoring.  In _Proceedings of the 35th Annual Symposium on Foundations of Computer Science_ , SFCS ’94, page 124–134, USA, 1994. IEEE Computer Society.
  * Shor [1997] Peter W. Shor.  Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer.  _SIAM J. Comput._ , 26(5):1484–1509, October 1997.  ISSN 0097-5397.  doi: 10.1137/S0097539795293172.  URL https://doi.org/10.1137/S0097539795293172.
  * Silver et al. [2016] David Silver, Aja Huang, Christopher Maddison, Arthur Guez, Laurent Sifre, George Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis.  Mastering the game of go with deep neural networks and tree search.  _Nature_ , 529:484–489, 01 2016.  doi: 10.1038/nature16961.
  * Smith et al. [2017] J. S. Smith, O. Isayev, and A. E. Roitberg.  Ani-1: an extensible neural network potential with dft accuracy at force field computational cost.  _Chem. Sci._ , 8(4):3192–3203, 2017.  doi: 10.1039/C6SC05720A.  URL http://dx.doi.org/10.1039/C6SC05720A.
  * Sordoni and Nie [2014] Alessandro Sordoni and Jian-Yun Nie.  Looking at vector space and language models for ir using density matrices.  _Lecture Notes in Computer Science_ , page 147–159, 2014.
  * Sordoni et al. [2013] Alessandro Sordoni, Jian-Yun Nie, and Yoshua Bengio.  Modeling term dependencies with quantum language models for ir.  In _Proceedings of the 36th International ACM SIGIR Conference on Research and Development in Information Retrieval_ , SIGIR ’13, page 653–662, New York, NY, USA, 2013. Association for Computing Machinery.
  * Szegedy et al. [2015] C. Szegedy, Wei Liu, Yangqing Jia, P. Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, and A. Rabinovich.  Going deeper with convolutions.  In _2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 1–9, 2015.
  * Tacchino et al. [2019a] Francesco Tacchino, Panagiotis Barkoutsos, Chiara Macchiavello, Ivano Tavernelli, Dario Gerace, and Daniele Bajoni.  Quantum implementation of an artificial feed-forward neural network, 2019a.
  * Tacchino et al. [2019b] Francesco Tacchino, Chiara Macchiavello, Dario Gerace, and Daniele Bajoni.  An artificial neuron implemented on an actual quantum processor.  _npj Quantum Information_ , 5, 12 2019b.
  * Tang et al. [2019] Hao Tang, Zhen Feng, Ying-Han Wang, Peng-Cheng Lai, Chao-Yue Wang, Zhuo-Yang Ye, Cheng-Kai Wang, Zi-Yu Shi, Tian-Yu Wang, Yuan Chen, and et al.  Experimental quantum stochastic walks simulating associative memory of hopfield neural networks.  _Physical Review Applied_ , 11(2), Feb 2019.
  * Tavanaei et al. [2019] Amirhossein Tavanaei, Masoud Ghodrati, Saeed Reza Kheradpisheh, Timothée Masquelier, and Anthony Maida.  Deep learning in spiking neural networks.  _Neural Networks_ , 111:47–63, Mar 2019.
  * Torrontegui and Garcia-Ripoll [2018] E. Torrontegui and J. Garcia-Ripoll.  Universal quantum perceptron as efficient unitary approximators.  _EPL (Europhysics Letters)_ , 125, 01 2018.  doi: 10.1209/0295-5075/125/30004.
  * Toth et al. [1996] Geza Toth, Craig S. Lent, P.Douglas Tougaw, Yuriy Brazhnik, Weiwen Weng, Wolfgang Porod, Ruey-Wen Liu, and Yih-Fang Huang.  Quantum cellular neural networks.  _Superlattices and Microstructures_ , 20(4):473–478, Dec 1996.
  * Türkpençe et al. [2017] Deniz Türkpençe, T. Cetin AKINCI, and Serhat Seker.  Quantum neural networks driven by information reservoir.  09 2017.
  * Vaswani et al. [2017a] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Ł ukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, _Advances in Neural Information Processing Systems 30_ , pages 5998–6008. Curran Associates, Inc., 2017a.
  * Vaswani et al. [2017b] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In _Advances in Neural Information Processing Systems_ , pages 5998–6008, 2017b.
  * Wan et al. [2017] Kwok Ho Wan, Oscar Dahlsten, Hlér Kristjánsson, Robert Gardner, and M. S. Kim.  Quantum generalisation of feedforward neural networks.  _npj Quantum Information_ , 3(1), Sep 2017.
  * Werbos [1990] P. J. Werbos.  Backpropagation through time: what it does and how to do it.  _Proceedings of the IEEE_ , 78(10):1550–1560, 1990.
  * Wiebe et al. [2014] Nathan Wiebe, Ashish Kapoor, and Krysta M. Svore.  Quantum deep learning, 2014.
  * Wilson et al. [2018] C. M. Wilson, J. S. Otterbach, N. Tezak, R. S. Smith, A. M. Polloreno, Peter J. Karalekas, S. Heidel, M. Sohaib Alam, G. E. Crooks, and M. P. da Silva.  Quantum kitchen sinks: An algorithm for machine learning on near-term quantum computers, 2018.
  * Zak and Williams [1998] Michail Zak and Colin Williams.  Quantum neural nets.  _International Journal of Theoretical Physics - INT J THEOR PHYS_ , 37:651–684, 02 1998.  doi: 10.1023/A:1026656110699.
  * Zeng and Coecke [2016] William Zeng and Bob Coecke.  Quantum algorithms for compositional natural language processing.  _Electronic Proceedings in Theoretical Computer Science_ , 221:67–75, Aug 2016.  ISSN 2075-2180.
  * Zhang et al. [2018a] Peng Zhang, Jiabin Niu, Zhan Su, Benyou Wang, Liqun Ma, and Dawei Song.  End-to-end quantum-like language models with application to question answering.  In _AAAI_ , 2018a.
  * Zhang et al. [2018b] Peng Zhang, Zhan Su, Lipeng Zhang, Benyou Wang, and Dawei Song.  A quantum many-body wave function inspired language modeling approach.  _Proceedings of the 27th ACM International Conference on Information and Knowledge Management_ , Oct 2018b.
  * Zhang et al. [2019] Zhihong Zhang, Dongdong Chen, Jianjia Wang, Lu Bai, and Edwin R. Hancock.  Quantum-based subgraph convolutional neural networks.  _Pattern Recognit._ , 88:38–49, 2019.  URL http://dblp.uni-trier.de/db/journals/pr/pr88.html#ZhangCWBH19.
  * Zhao and Gao [2019] Chen Zhao and Xiao-Shan Gao.  Qdnn: Dnn with quantum neural network layers, 2019.
  * Zhu et al. [2018] Qiaomu Zhu, Jinfu Chen, Lin Zhu, Xianzhong Duan, and Yilu Liu.  Wind speed prediction with spatio–temporal correlation: A deep learning approach.  _Energies_ , 11:705, 03 2018.  doi: 10.3390/en11040705.


# The automorphisms group and the classification of gradings of finite
dimensional associative algebras

G. Militaru  Faculty of Mathematics and Computer Science, University of
Bucharest, Str. Academiei 14, RO-010014 Bucharest 1, Romania  Simion Stoilow
Institute of Mathematics of the Romanian Academy, P.O. Box 1-764, 014700
Bucharest, Romania<EMAIL_ADDRESS>and<EMAIL_ADDRESS>
###### Abstract.

Let $A$ be an $n$-dimensional algebra over a field $k$ and $a(A)$ its quantum
symmetry semigroup. We prove that the automorphisms group ${\rm Aut}_{\rm
Alg}(A)$ of $A$ is isomorphic to the group $U\bigl{(}G(a(A)^{\rm o})\bigl{)}$
of all invertible group-like elements of the finite dual $a(A)^{\rm o}$. For a
group $G$, all $G$-gradings on $A$ are explicitly described and classified:
the set of isomorphisms classes of all $G$-gradings on $A$ is in bijection
with the quotient set ${\rm Hom}_{\rm
BiAlg}\,\bigl{(}a(A),\,k[G]\bigl{)}/\approx$ of all bialgebra maps $a(A)\,\to
k[G]$, via the equivalence relation implemented by the conjugation with an
invertible group-like element of $a(A)^{\rm o}$.

###### Key words and phrases:

automorphisms group of associative algebras, classifications of gradings.

###### 2010 Mathematics Subject Classification:

16W20, 16W50, 16T10

This work was supported by a grant of the Ministry of Research, Innovation and
Digitization, CNCS/CCCDI–UEFISCDI, project number PN-III-P4-ID-PCE-2020-0458,
within PNCDI III

## Introduction

The quantum symmetry semigroup $a(A)$ of a finite dimensional associative
algebra $A$ over a field $k$, introduced by Manin [15] and Tambara [18], is
used to approach two classical open problems: the description of the
automorphisms group ${\rm Aut}_{\rm Alg}(A)$ of $A$ and the classification of
all $G$-gradings on $A$, for an arbitrary group $G$. The description of the
automorphisms group of an algebra is an old problem arising from Hilbert’s
invariant theory: the first notable result obtained was the Skolem-Noether
theorem [22]. Since then a lot a literature was devoted to this problem: see
for instance [6, 8, 21] and their list of references. The classification of
all $G$-gradings on an algebra $A$ is a problem formulated by Zelmanov [24] in
the case that $A={\rm M}_{n}(k)$, the usual matrix algebra. The problem is
interesting but very diffficult and has generated a lot of interest. It is
also far from being solved: see [5, 7, 10, 13] and their references. The
similar question for the classification of all $G$-gradings on Lie algebras
was also studied a lot [11].

In this paper a new approach to the two above mentioned problems is proposed
using the power of a key object in quantum groups and noncommutative geometry,
namely the quantum symmetry semigroup $a(A)$ [15, 18] of an $n$-dimensional
algebra $A$. Let $\\{e_{1}:=1_{A},\cdots,e_{n}\\}$ be a $k$-basis of $A$ and
$\\{\tau_{i,j}^{s}\,|\,i,j,s=1,\cdots,n\\}$ the structure constants of $A$.
Then, $a(A)$ is the free algebra generated by
$\\{x_{si}\,|\,s,i=1,\cdots,n,\\}$ and the relations:

$\sum_{u=1}^{n}\,\tau_{i,j}^{u}\,x_{au}=\sum_{s,t=1}^{n}\,\tau_{s,t}^{a}\,x_{si}x_{tj},\qquad
x_{a1}=\delta_{a,1}$ (1)

for all $a$, $i$, $j=1,\cdots,n$, where $\delta_{a,1}$ is the Kroneker symbol.
Furthermore, $a(A)$ has a canonical bialgebra structure such that the
canonical map $\eta_{A}:A\to A\otimes a(A)$,
$\eta_{A}(e_{i}):=\sum_{s=1}^{n}\,e_{s}\otimes x_{si}$, for all $i=1,\cdots,n$
is a right $a(A)$-comodule algebra structure on $A$ and the pair
$(a(A),\,\eta_{A})$ is the initial object of the category of all bialgebras
coacting on $A$ (Theorem 1.6). The bialgebra $a(A)$ captures most of the
essential information of the algebra $A$ and this idea is exploited in this
paper. Theorem 2.1 provides an explicit description of a group isomorphism
between the group of automorphisms of $A$ and the group of all invertible
group-like elements of the finite dual $a(A)^{\rm o}$:

${\rm Aut}_{\rm Alg}(A)\cong U\bigl{(}G\bigl{(}a(A)^{\rm o}\bigl{)}\bigl{)}.$

Proposition 2.2 proves that for an arbitrary group $G$ there exists an
explicitly described bijection between the set of all $G$-gradings on $A$ and
the set of all bialgebra homomorphisms $a(A)\to k[G]$. Furthermore, all
$G$-gradings on $A$ are explicitly classified and parameterized in Theorem
2.4: the set $G-{\rm\textbf{gradings}}(A)$ of isomorphisms classes of all
$G$-gradings on $A$ is in bijection with the quotient set ${\rm Hom}_{\rm
BiAlg}\,\bigl{(}a(A),\,k[G]\bigl{)}/\approx$ of all bialgebra maps $a(A)\,\to
k[G]$ via the equivalence relation implemented by the usual conjugation with
an invertible group-like element of $a(A)^{\rm o}$. Similar results where
recently obtained for Leibniz/Lie algebras [2].

##  1\. Preliminaries

All vector spaces, (bi)linear maps, associative algebras or bialgebras are
over an arbitrary field $k$ and $\otimes=\otimes_{k}$. We shall denote by
${\rm Alg}_{k}$ the category of all unital associative algebras and unital
persevering morphisms. For $A\in{\rm Alg}_{k}$ we denote by ${\rm Aut}_{\rm
Alg}(A)$ the automorphisms group of $A$ and $k[G]$ denotes the usual group
algebra of a group $G$. Let $G$ be a group and $A$ an algebra. We recall that
a _$G$ -grading_ on $A$ is a vector space decomposition $A=\oplus_{\sigma\in
G}A_{\sigma}$ such that $A_{\sigma}A_{\tau}\subseteq A_{\sigma\tau}$, for all
$\sigma$, $\tau\in G$. Two $G$-gradings $A=\oplus_{\sigma\in
G}\,A_{\sigma}=\oplus_{\sigma\in G}\,A_{\sigma}^{{}^{\prime}}$ on $A$ are
called _isomorphic_ if there exists $w\in{\rm Aut}_{{\rm Alg}}(A)$ an algebra
automorphism of $A$ such that $w(A_{\sigma})\subseteq
A_{\sigma}^{{}^{\prime}}$, for all $\sigma\in G$. Since $w$ is bijective and
$A$ is $G$-graded we can prove easily that the last condition is equivalent to
$w(A_{\sigma})=A_{\sigma}^{{}^{\prime}}$, for all $\sigma\in G$, which is the
condition that usually appears in the literature in the classification of
$G$-gradings ([11]). For more details on the theory of $G$-graded rings we
refer to [17].

For any bialgebra $H$ the set of group-like elements, denoted by
$G(H):=\\{g\in H\,|\,\Delta(g)=g\otimes g\,\,{\rm
and}\,\,\varepsilon(g)=1\\}$, is a monoid with respect to the multiplication
of $H$. We denote by $H^{\rm o}$, the finite dual bialgebra of $H$, i.e.

$H^{\rm o}:=\\{f\in H^{*}\,|\,f(I)=0,\,{\rm for\,some\,ideal}\,\,I\lhd
H\,\,{\rm with}\,\,{\rm dim}_{k}(H/I)<\infty\\}$

It is well known (see for instance [19, pag. 62]) that $G(H^{\rm o})={\rm
Hom}_{\rm Alg_{k}}(H,\,k)$, the set of all algebra homomorphisms $H\to k$. For
a later use we also recall the following well know result ([16, Example
4.1.7]): let $A$ be an algebra and $G$ a group. Then there exists a bijection
between the set of all $G$-gradings on $A$ and the set of all right
$k[G]$-comodule algebra structures on $A$ given such that the $G$-grading on
$A$ associated to a right $k[G]$-comodule algebra structures $\varrho:A\to
A\otimes k[G]$ is given for any $\sigma\in G$ by:

$A_{\sigma}=\\{a\in A\,|\,\varrho(a)=a\otimes\sigma\\}$ (2)

For unexplained notions pertaining Hopf algebras we refer the reader to [16,
19, 23].

Tambara’s construction revised. We shall recall the construction and the main
properties of the quantum symmetry semigroup of a finite dimensional algebra
$A$. The results below in this sections are well-known or have been recently
proven in much more general cases [3, 4]. The following is [18, Theorem 1.1]:
we shall present a short proof since we prefer to give an explicit
construction of the algebra $a(A)$, using generators and relations implemented
by the structure constants of $A$ in the spirit of [1, Theorem 3.2].

######  Theorem 1.1.

Let $A$ be a finite dimensional algebra over a field $k$. Then the functor
$A\otimes-\,:{\rm Alg}_{k}\to{\rm Alg}_{k}$ has a left adjoint $a(A,\,-)$.

###### Proof.

Assume that ${\rm dim}_{k}(A)=n$ and fix $\\{e_{1},\cdots,e_{n}\\}$ a basis in
$A$ over $k$ such that $e_{1}=1_{A}$, the unit of $A$. Let
$\\{\tau_{i,j}^{s}\,|\,i,j,s=1,\cdots,n\\}$ be the structure constants of $A$,
i.e. for any $i$, $j=1,\cdots,n$ we have:

$e_{i}\,e_{j}=\sum_{s=1}^{n}\,\tau_{i,j}^{s}\,e_{s}.$ (3)

Let $B$ be an arbitrary algebra and let $\\{f_{i}\,|\,i\in I\\}$ be a basis of
$B$ containing $1_{B}$, i.e. $1_{B}=f_{i_{0}}$, for some $i_{0}\in I$. For any
$i$, $j\in I$, let $B_{i,j}\subseteq I$ be a finite subset of $I$ such that
for any $i$, $j\in I$ we have:

$f_{i}\,f_{j}=\sum_{u\in B_{i,j}}\,\beta_{i,j}^{u}\,f_{u}.$ (4)

Let $a(A,\,B)$ be the free algebra generated by
$\\{x_{si}\,|s=1,\cdots,n,\,i\in I\\}$ and the relations:

$\sum_{u\in
B_{i,j}}\,\beta_{i,j}^{u}\,x_{au}=\sum_{s,t=1}^{n}\,\tau_{s,t}^{a}\,x_{si}x_{tj},\qquad
x_{ai_{0}}=\delta_{a,1}$ (5)

for all $a=1,\cdots,n$ and $i,\,j\in I$, where $\delta_{a,1}$ is the Kroneker
symbol. Using the relations (5) we can easily see that the map defined by

$\eta_{B}:B\to A\otimes
a(A,\,B),\quad\eta_{B}(f_{i}):=\sum_{s=1}^{n}\,e_{s}\otimes x_{si},\quad{\rm
for\,\,all}\,\,i\in I.$ (6)

is an algebra homomorphism preserving the unit. Furthermore, for any
$k$-algebra $C$ the canonical map:

$\gamma_{B,\,C}\,:{\rm Hom}_{\rm Alg_{k}}\,(a(A,\,B),\,C)\to{\rm Hom}_{\rm
Alg_{k}}\,(B,\,A\otimes C),\quad\gamma_{B,\,C}(\theta):=\bigl{(}{\rm
Id}_{A}\otimes\theta\bigl{)}\circ\eta_{B}$ (7)

is bijective, that is for any algebra map $f:B\to A\otimes C$ there exists a
unique algebra homomorphism $\theta:A(A,\,B)\to C$ such that the following
diagram is commutative:

(12)

i.e. $f=\bigl{(}{\rm Id}_{A}\otimes\theta\bigl{)}\circ\,\eta_{B}$. The natural
isomorphism (7) proves that the functor $a(A,\,-)$ is a left adjoint of
$A\otimes-$. ∎

By taking $C:=k$ in the bijection described in (7) we obtain:

######  Corollary 1.2.

Let $A$ and $B$ be two algebras such that $A$ is finite dimensional. Then the
following map is bijective:

$\gamma\,:{\rm Hom}_{\rm Alg_{k}}\,(a(A,\,B),\,k)\to{\rm Hom}_{\rm
Alg_{k}}\,(B,\,A),\quad\gamma(\theta):=\bigl{(}{\rm
Id}_{A}\otimes\theta\bigl{)}\circ\eta_{B}.$ (13)

######  Definition 1.3.

Let $A$ be a finite dimensional algebra over a field $k$. The algebra
$a(A):=a(A,\,A)$ is called the _quantum symmetry semigroup_ of $A$.

The explicit description, using generators and relations, of algebra $a(A)$ is
the following: let $\\{e_{1},\cdots,e_{n}\\}$ be a $k$-basis of $A$ such that
$e_{1}=1_{A}$ and let $\\{\tau_{i,j}^{s}\,|\,i,j,s=1,\cdots,n\\}$ be the
structure constants of $A$. Then, $a(A)$ is the free algebra generated by
$\\{x_{si}\,|s,i=1,\cdots,n,\\}$ and the relations:

$\sum_{u=1}^{n}\,\tau_{i,j}^{u}\,x_{au}=\sum_{s,t=1}^{n}\,\tau_{s,t}^{a}\,x_{si}x_{tj},\qquad
x_{a1}=\delta_{a,1}$ (14)

for all $a$, $i$, $j=1,\cdots,n$, where $\delta_{a,1}$ is the Kroneker symbol.
Furthermore, the canonical map

$\eta_{A}:A\to A\otimes
a(A),\quad\eta_{A}(e_{i}):=\sum_{s=1}^{n}\,e_{s}\otimes x_{si},\quad{\rm
for\,\,all}\,\,i=1,\cdots,n$ (15)

is an algebra homomorphism. The bijection given by (7) applied for $B:=A$
shows that the algebra $a(A)$ satisfies the following first universal
property:

######  Corollary 1.4.

Let $A$ be a finite dimensional algebra. Then for any algebra $C$ and any
algebra homomorphism $f:A\to A\otimes C$, there exists a unique algebra
homomorphism $\theta:a(A)\to C$ such that $f=({\rm
Id}_{A}\otimes\theta)\circ\eta_{A}$, i.e. the following diagram is
commutative:

(20)

The algebra $a(A)$ is also a bialgebra such that $(A,\eta_{A})$ is a right
$a(A)$-comodule algebra ([18]). Moreover, we can explicitly describe the
coalgebra structure on $a(A)$ as follows:

######  Proposition 1.5.

Let $A$ be a $k$-algebra of dimension $n$. Then there exists a unique
bialgebra structure on $a(A)$ such that the algebra homomorphism
$\eta_{A}:A\to A\otimes a(A)$ becomes a right $a(A)$-comodule structure on
$A$. More precisely, the comultiplication and the counit on $a(A)$ are given
for any $i$, $j=1,\cdots,n$ by

$\Delta(x_{ij})=\sum_{s=1}^{n}\,x_{is}\otimes x_{sj}\quad{\rm
and}\quad\varepsilon(x_{ij})=\delta_{i,j}$ (21)

###### Proof.

Consider the algebra homomorphism $f:A\to A\otimes a(A)\otimes a(A)$ defined
by $f:=(\eta_{A}\otimes{\rm Id}_{a(A)})\,\circ\,\eta_{A}$. It follows from
Corollary 1.4 that there exists a unique algebra homomorphism $\Delta:a(A)\to
a(A)\otimes a(A)$ such that $({\rm Id}_{A}\otimes\Delta)\circ\eta_{A}=f$; that
is, the following diagram is commutative:

(26)

Now, if we evaluate the diagram (26) at each $e_{i}$, for $i=1,\cdots,n$ we
obtain, taking into account (15), the following:

$\displaystyle\sum_{t=1}^{n}\,e_{t}\otimes\Delta(x_{ti})=(\eta_{A}\otimes{\rm
Id})(\sum_{s=1}^{n}\,e_{s}\otimes
x_{si})=\sum_{s=1}^{n}(\sum_{t=1}^{n}\,e_{t}\otimes x_{ts})\otimes x_{si}$
$\displaystyle=\sum_{t=1}^{n}\,e_{t}\otimes(\sum_{s=1}^{n}x_{ts}\otimes
x_{si})$

and hence $\Delta(x_{ti})=\sum_{s=1}^{n}\,x_{ts}\otimes x_{si}$, for all $t$,
$i=1,\cdots,n$. Obviously, $\Delta$ given by this formula on generators is
coassociative. In a similar fashion, applying once again Corollary 1.4, we
obtain that there exists a unique algebra homomorphism $\varepsilon:a(A)\to k$
such that the following diagram is commutative:

(31)

where ${\rm can}:A\to A\otimes k$ is the canonical isomorphism, ${\rm
can}(x)=x\otimes 1$, for all $x\in A$. If we evaluate this diagram at each
$e_{t}$, for $t=1,\cdots,n$, we obtain $\varepsilon(x_{ij})=\delta_{i,j}$, for
all $i$, $j=1,\cdots,n$. It can be easily checked that $\varepsilon$ is a
counit for $\Delta$, thus $a(A)$ is a bialgebra. Furthermore, the
commutativity of the above two diagrams implies that the canonical map
$\eta_{A}:A\to A\otimes a(A)$ defines a right $a(A)$-comodule structure on
$A$, i.e. $A$ is a right $a(A)$-comodule algebra. ∎

The pair $(a(A),\,\eta_{A})$, with the coalgebra structure defined in
Proposition 1.5, is called the universal coacting bialgebra of $A$. The reason
is that it fullfils the following universal property which extends Corollary
1.4 and shows that $(a(A),\,\eta_{A})$ is the initial object of the category
of all bialgebras coacting on $A$:

######  Theorem 1.6.

Let $A$ be a finite dimensional algebra. Then, for any bialgebra $H$ and any
algebra homomorphism $f\colon A\to A\otimes H$ which makes $A$ into a right
$H$-comodule there exists a unique bialgebra homomorphism $\theta\colon
a(A)\to H$ such that the following diagram is commutative:

(36)

###### Proof.

It follows from Corollary 1.4 there exists a unique algebra map $\theta\colon
a(A)\to H$ such that diagram (36) commutes. The proof will be finished once we
show that $\theta$ is a coalgebra homomorphism as well. This follows by using
again the universal property of $a(A)$. Indeed, we obtain a unique algebra
homomorphism $\psi\colon a(A)\to H\otimes H$ such that the following diagram
is commutative:

$\textstyle{A\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\eta_{A}}$$\scriptstyle{\bigl{(}{\rm
Id}_{A}\otimes\,\Delta_{H}\circ\theta\bigl{)}\circ\eta_{A}}$$\textstyle{{A\otimes
a(A)}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{{\rm
Id}_{A}\otimes\psi}$$\textstyle{{A\otimes H\otimes H}}$ (37)

The proof will be finished once we show that
$(\theta\otimes\theta)\circ\Delta$ makes diagram (37) commutative. Indeed, as
$f\colon A\to A\otimes H$ is a right $H$-comodule structure, we have:

$\displaystyle\bigl{(}{\rm
Id}_{A}\otimes\,(\theta\otimes\theta)\circ\Delta\bigl{)}\circ\,\eta_{A}$
$\displaystyle=$ $\displaystyle\bigl{(}{\rm
Id}_{A}\otimes\theta\otimes\theta\bigl{)}\circ\underline{\bigl{(}{\rm
Id}_{A}\otimes\Delta\bigl{)}\circ\,\eta_{A}}$
$\displaystyle\stackrel{{\scriptstyle(\ref{eq:delta})}}{{=}}$
$\displaystyle\bigl{(}{\rm
Id}_{A}\otimes\theta\otimes\theta\bigl{)}\circ(\eta_{A}\otimes{\rm
Id}_{a(A)})\circ\eta_{A}$ $\displaystyle=$
$\displaystyle\bigl{(}\underline{({\rm Id}_{A}\otimes\theta)\circ\eta_{A}}\
\otimes\theta\bigl{)}\circ\,\eta_{A}$
$\displaystyle\stackrel{{\scriptstyle(\ref{eq:univbialg})}}{{=}}$
$\displaystyle\bigl{(}f\otimes\theta\bigl{)}\circ\,\eta_{A}$ $\displaystyle=$
$\displaystyle(f\otimes{\rm Id}_{H})\circ\underline{({\rm
Id}_{A}\otimes\theta)\circ\,\eta_{A}}$
$\displaystyle\stackrel{{\scriptstyle(\ref{eq:univbialg})}}{{=}}$
$\displaystyle\underline{(f\otimes{\rm Id}_{H})\circ f}$ $\displaystyle=$
$\displaystyle({\rm Id}_{A}\otimes\Delta_{H})\circ\underline{f}$
$\displaystyle\stackrel{{\scriptstyle(\ref{eq:univbialg})}}{{=}}$
$\displaystyle({\rm Id}_{A}\otimes\Delta_{H})\circ({\rm
Id}_{A}\otimes\theta)\circ\eta_{A}$ $\displaystyle=$ $\displaystyle({\rm
Id}_{A}\otimes\Delta_{H}\circ\theta)\circ\eta_{A}$

as desired. Similarly, one can show that
$\varepsilon_{H}\,\circ\,\theta=\varepsilon$ and the proof is now finished. ∎

We end this section with the following two questions:

_1\. Are there two finite dimensional non-isomorphic algebras $A$ and $B$ such
that $a(A)\cong a(B)$? (isomorphism of bialgebras)?_

_2\. If $A$ and $B$ are two finite dimensional algebras, is it true that
$a(A\otimes B)\cong a(A)\otimes a(B)$ (isomorphism of bialgebras)?_

##  2\. The automorphisms group and the classification of gradings on algebras

The power of the quantum symmetry semigroup of an algebra $A$ is evidenced by
its applications to the two open problems mentioned in the introduction. The
first application is related to the description of the automorphisms group
${\rm Aut}_{{\rm Alg}}(A)$ of $A$.

######  Theorem 2.1.

Let $A$ be a finite dimensional algebra with basis $\\{e_{1},\cdots,e_{n}\\}$
and let $U\bigl{(}G\bigl{(}a(A)^{\rm o}\bigl{)}\bigl{)}$ be the group of all
invertible group-like elements of the finite dual $a(A)^{\rm o}$. Then the map
defined for any $\theta\in U\bigl{(}G\bigl{(}a(A)^{\rm o}\bigl{)}\bigl{)}$ and
$i=1,\cdots,n$ by:

$\overline{\gamma}:U\bigl{(}G\bigl{(}a(A)^{\rm o}\bigl{)}\bigl{)}\to{\rm
Aut}_{{\rm
Alg}}(A),\qquad\overline{\gamma}(\theta)(e_{i}):=\sum_{s=1}^{n}\,\theta(x_{si})\,e_{s}$
(38)

is an isomorphism of groups.

###### Proof.

By applying Corollary 1.2 for $B:=A$ it follows that the map

$\gamma:{\rm Hom}_{\rm Alg_{k}}(a(A),\,k)\to{\rm End}_{{\rm
Alg}}(A),\quad\gamma(\theta)=\bigl{(}{\rm
Id}_{A}\otimes\theta\bigl{)}\circ\eta_{A}$

is bijective. Based on formula (15), it can be easily seen that $\gamma$ takes
the form given by (38). As we mentioned in the preliminaries we have ${\rm
Hom}_{\rm Alg_{k}}(a(A),k)=G\bigl{(}a(A)^{\rm o}\bigl{)}$. Therefore, since
$\overline{\gamma}$ is the restriction of $\gamma$ to the invertible elements
of the two monoids, the proof will be finished once we show that $\gamma$ is
an isomorphism of monoids. We mention that the monoid structure on ${\rm
End}_{{\rm Alg}}(A)$ is given by the usual composition of endomorphisms of the
algebra $A$, while $G\bigl{(}a(A)^{\rm o}\bigl{)}$ is a monoid with respect to
the multiplication of the bialgebra $a(A)^{\rm o}$, that is the convolution
product:

$(\theta_{1}\star\theta_{2})(x_{sj})=\sum_{t=1}^{n}\,\theta_{1}(x_{st})\theta_{2}(x_{tj})$
(39)

for all $\theta_{1}$, $\theta_{2}\in G\bigl{(}a(A)^{\rm o}\bigl{)}$ and $j$,
$s=1,\cdots,n$. Now, for any $\theta_{1}$, $\theta_{2}\in G\bigl{(}a(A)^{\rm
o}\bigl{)}$ and $j=1,\cdots,n$ we have:

$\displaystyle\bigl{(}\gamma(\theta_{1})\circ\gamma(\theta_{2})\bigl{)}(e_{j})=\gamma(\theta_{1})\bigl{(}\sum_{t=1}^{n}\,\theta_{2}(x_{tj})e_{t}\bigl{)}=\sum_{s,t=1}^{n}\,\theta_{1}(x_{st})\theta_{2}(x_{tj})\,e_{s}$
$\displaystyle=\sum_{s=1}^{n}\,\bigl{(}\sum_{t=1}^{n}\,\theta_{1}(x_{st})\theta_{2}(x_{tj})\bigl{)}\,e_{s}=\sum_{s=1}^{n}\,(\theta_{1}\star\theta_{2})(x_{sj})\,e_{s}=\gamma(\theta_{1}\star\theta_{2})(e_{j})$

thus,
$\gamma(\theta_{1}\star\theta_{2})=\gamma(\theta_{1})\circ\gamma(\theta_{2})$,
and therefore $\gamma$ respects the multiplication. We are left to show that
$\gamma$ also preserves the unit. Note that the unit $1$ of the monoid
$G\bigl{(}a(A)^{\rm o}\bigl{)}$ is the counit $\varepsilon_{a(A)}$ of the
bialgebra $a(A)$ and we obtain:

$\gamma(1)(e_{i})=\gamma(\varepsilon_{a(A)})(e_{i})=\sum_{s=1}^{n}\,\varepsilon_{a(A)}(x_{si})\,e_{s}=\sum_{s=1}^{n}\,\delta_{si}\,e_{s}=e_{i}={\rm
Id}_{A}(e_{i})$

Thus we have proved that $\gamma$ is an isomorphism of monoids and the proof
is finished. ∎

The second application of the bialgebra $a(A)$ is related to the problem of
classification of all $G$-gradings on the algebra $A$.

######  Proposition 2.2.

Let $G$ be a group and $A$ a finite dimensional algebra. Then there exists a
bijection between the set of all $G$-gradings on $A$ and the set of all
bialgebra homomorphisms $a(A)\to k[G]$. The bijection is given such that the
$G$-grading on $A=\oplus_{\sigma\in G}\,A_{\sigma}^{(\theta)}$ associated to a
bialgebra map $\theta:a(A)\to k[G]$ is given by:

$A_{\sigma}^{(\theta)}:=\\{x\in A\,|\,\bigl{(}{\rm
Id}_{A}\otimes\theta\bigl{)}\,\circ\,\eta_{A}(x)=x\otimes\sigma\\}$ (40)

for all $\sigma\in G$.

###### Proof.

Applying Theorem 1.6 for the bialgebra $H:=k[G]$ yields a bijection between
the set of all bialgebra homomorphisms $a(A)\to k[G]$ and the set of all
algebra homomorphisms $f\colon A\to A\otimes k[G]$ which makes $A$ into a
right $k[G]$-comodule. The proof is now finished since the latter set is in
bijective correspondence with the set of all $G$-gradings on $A$ (see (2) and
[16, Example 4.1.7]). ∎

It is easy to see that, under the bijection given by Proposition 2.2, the
$G$-grading on $A$ associated to the trivial bialgebra map $a(A)\to
k[G],\,x\mapsto\varepsilon(x)$, is just the trivial grading on $A$, that is
$A_{1}:=A$ and $A_{\sigma}:=0$, for any $1\neq\sigma\in G$. In the next step
we shall classify all $G$-gradings on a given algebra $A$. We need to recall
one more elementary fact from Hopf algebras: if $H$ and $L$ are two bialgebras
over a field $k$ then the abelian group ${\rm Hom}(H,\,L)$ of all $k$-linear
maps is an unital associative algebra under the convolution product ([23]):
$(\theta_{1}\star\theta_{2})(h):=\sum\,\theta_{1}(h_{(1)})\theta_{2}(h_{(2)})$,
for all $\theta_{1}$, $\theta_{2}\in{\rm Hom}(H,\,L)$ and $h\in H$.

######  Definition 2.3.

Let $G$ be a group and $A$ a finite dimensional algebra. Two morphism of
bialgebras $\theta_{1},\theta_{2}:a(A)\to k[G]$ are called _conjugate_ and
denote $\theta_{1}\approx\theta_{2}$, if there exists $g\in
U\bigl{(}G\bigl{(}a(A)^{\rm o}\bigl{)}\bigl{)}$ an invertible group-like
element of the finite dual $a(A)^{\rm o}$ such that
$\theta_{2}=g\star\theta_{1}\star g^{-1}$, in the convolution algebra ${\rm
Hom}\bigl{(}a(A),\,k[G]\bigl{)}$.

We denote by ${\rm Hom}_{\rm BiAlg}\,\bigl{(}a(A),\,k[G]\bigl{)}/\approx$ the
quotient set of the set of all bialgebra maps $a(A)\to k[G]$ through the above
equivalence relation and by $\hat{\theta}$ the equivalence class of
$\theta\in{\rm Hom}_{\rm BiAlg}\,\bigl{(}a(A),\,k[G]\bigl{)}$.

######  Theorem 2.4.

Let $G$ be a group, $A$ a finite dimensional algebra and
$G-{\rm\textbf{gradings}}(A)$ the set of isomorphisms classes of all
$G$-gradings on $A$. Then the map

${\rm Hom}_{\rm
BiAlg}\,\bigl{(}a(A),\,k[G]\bigl{)}/\approx\,\,\,\mapsto\,\,G-{\rm\textbf{gradings}}(A),\qquad\hat{\theta}\mapsto
A^{(\theta)}:=\oplus_{\sigma\in G}\,A_{\sigma}^{(\theta)}$

where $A_{\sigma}^{(\theta)}=\\{x\in A\,|\,\bigl{(}{\rm
Id}_{A}\otimes\theta\bigl{)}\,\circ\,\eta_{A}(x)=x\otimes\sigma\\}$, for all
$\sigma\in G$, is bijective.

###### Proof.

Let $\\{e_{1},\cdots,e_{n}\\}$ be a basis in $A$. Using Proposition 2.2 we
obtain that for any $G$-grading $A=\oplus_{\sigma\in G}\,A_{\sigma}$ on $A$
there exists a unique bialgebra map $\theta:a(A)\to k[G]$ such that
$A_{\sigma}=A_{\sigma}^{(\theta)}$, for all $\sigma\in G$. It remains to prove
when two such $G$-gradings are isomorphic. Let $\theta_{1}$,
$\theta_{2}:a(A)\to k[G]$ be two bialgebra maps and let
$A=A^{(\theta_{1})}:=\oplus_{\sigma\in
G}\,A_{\sigma}^{(\theta_{1})}=\oplus_{\sigma\in
G}\,A_{\sigma}^{(\theta_{2})}=:A^{(\theta_{2})}$ be the associated
$G$-gradings. It follows from the proof of Proposition 2.2 that given a
$G$-grading on $A$ is equivalent (and the correspondence is bijective) to a
right $k[G]$-comodule structure $\rho:A\to A\otimes k[G]$ on $A$ such that the
right coaction $\rho$ is a morphism of algebras. Moreover, the right coactions
$\rho^{(\theta_{1})}$ and $\rho^{(\theta_{2})}:A\to A\otimes k[G]$ are
implemented form $\theta_{1}$ and $\theta_{2}$ using Theorem 1.6, that is they
are given for any $j=1,2$ by

$\rho^{(\theta_{j})}:A\to A\otimes
k[G],\qquad\rho^{(\theta_{j})}(e_{i})=\sum_{s=1}^{n}\,e_{s}\otimes\theta_{j}(x_{si})$
(41)

for all $i=1,\cdots,n$. It is well known in Hopf algebras that the two
$G$-gradings $A^{(\theta_{1})}$ and $A^{(\theta_{2})}$ are isomorphic if and
only if $(A,\,\rho^{(\theta_{1})})$ and $(A,\,\rho^{(\theta_{2})})$ are
isomorphic as algebras and right $k[G]$-comodules, that is there exists
$w:A\to A$ an algebra automorphism of $A$ such that
$\rho^{(\theta_{2})}\,\circ w=(w\otimes{\rm
Id}_{k[G]})\,\circ\rho^{(\theta_{1})}$. We apply now Theorem 2.1: for any
algebra automorphism $w:A\to A$ there exists a unique $g\in
U\bigl{(}G\bigl{(}a(A)^{\rm o}\bigl{)}\bigl{)}$ an invertible group-like
element of the finite dual $a(A)^{\rm o}$ such that $w=w_{g}$ is given for any
$i=1,\cdots,n$ by

$w_{g}(e_{i})=\sum_{s=1}^{n}\,g(x_{si})\,e_{s}$ (42)

Using (41) and (42) we can easily compute that:

$\bigl{(}\rho^{(\theta_{2})}\,\circ
w_{g}\bigl{)}(e_{i})=\sum_{a=1}^{n}\,e_{a}\otimes\bigl{(}\sum_{s=1}^{n}\,\theta_{2}(x_{as})g(x_{si})\bigl{)}$

and

$\bigl{(}(w_{g}\otimes{\rm
Id}_{k[G]})\,\circ\rho^{(\theta_{1})}\bigl{)}(e_{i})=\sum_{a=1}^{n}\,e_{a}\otimes\bigl{(}\sum_{s=1}^{n}\,g(x_{as})\theta_{1}(x_{si})\bigl{)}$

for all $i=1,\cdots,n$. Thus, the algebra automorphism $w_{g}:A\to A$ is also
a right $k[G]$-comodule map if and only if

$\sum_{s=1}^{n}\,g(x_{as})\theta_{1}(x_{si})=\sum_{s=1}^{n}\,\theta_{2}(x_{as})g(x_{si})$
(43)

for all $a$, $i=1,\cdots,n$. Taking into account the formula of the
comultiplication on the bialgebra $a(A)$, the equation (43) can be rewritten
in a compact form as $(g\star\theta_{1})(x_{ai})=(\theta_{2}\star g)(x_{ai})$,
for all $a$, $i=1,\cdots,n$ in the convolution algebra ${\rm
Hom}\bigl{(}a(A),\,k[G]\bigl{)}$, or (since $\\{x_{ai}\\}_{a,i=1,\cdots,n}$ is
a system of generators of $a(A)$) just as $g\star\theta_{1}=\theta_{2}\star
g$. We also note that $g:a(A)\to k$ is an invertible group-like element, that
is it is an invertible element in the above convolution algebra.

To conclude, we have proved that two $G$-gradings $A^{(\theta_{1})}$ and
$A^{(\theta_{2})}$ on $A$ associated to two bialgebra maps $\theta_{1}$,
$\theta_{2}:a(A)\to k[G]$ are isomorphic if and only if there exists $g\in
U\bigl{(}G\bigl{(}a(A)^{\rm o}\bigl{)}\bigl{)}$ such that
$\theta_{2}=g\star\theta_{1}\star g^{-1}$, in the convolution algebra ${\rm
Hom}\bigl{(}a(A),\,k[G]\bigl{)}$, that is $\theta_{1}$ and $\theta_{2}$ are
conjugated and this finished the proof. ∎

Theorem 2.1 and Theorem 2.4 offer a theoretical answer to the two classic
problems, reducing them to typical problems for Hopf algebras. While the
explicit description of the bialgebra $a(A)$ is relatively easy (albeit using
a laborious computation, eliminating the redundant relations among the $n^{3}$
relations (1) that define it), the really difficult part is the description of
the finite dual $a(A)^{\rm o}$ using generators and relations. Unfortunately,
the explicit description of the finite dual of a finite generated bialgebra is
a problem that has not been studied until now. It does however merit attention
in the future; the first steps in this direction have been taken very recently
in [9, 12, 14].

######  Example 2.5.

Let $A:=k[X]/(X^{2})$. Then $a\bigl{(}k[X]/(X^{2})\bigl{)}$ is the algebra
$k\langle x,y\,|\,x^{2}=0,\,xy+yx=0\rangle$ with the coalgebra structure given
by:

$\Delta(x)=x\otimes y+1\otimes x,\,\,\Delta(y)=y\otimes
y,\quad\varepsilon(x)=0,\,\,\varepsilon(y)=1$

Indeed, let $\\{e_{1}:=1,\,e_{2}:=x\\}$ be a basis of $A$, where $x$ is the
class of $X$ in $A$. Then the only non-zero structure constants of the algebra
$A$ are $\tau_{1,j}^{j}=\tau_{j,1}^{j}=1$, for $j=1,2$. Now, it is just a
routine computation, to reduce the eight relations (14) defining the algebra
$a\bigl{(}k[X]/(X^{2})\bigl{)}$ to:

$x_{12}^{2}=0,\qquad x_{12}x_{22}+x_{22}x_{12}=0$

Denoting $x_{12}=x$ si $x_{22}=y$ the conclusion follows (the coalgebra
structure arises from Proposition 1.5). Applying Theorem 2.1 we obtain that
${\rm Aut}_{{\rm Alg}}\bigl{(}k[X]/(X^{2})\bigl{)}$ is in bijection with the
set of all morphisms of algebras $\vartheta:a\bigl{(}k[X]/(X^{2})\bigl{)}\to
k$ such that the matrix $(\vartheta(x_{ij}))\in{\rm M}_{2}(k)$ is invertible.
Such a morphism is defined by: $\vartheta(x_{11})=\vartheta(1):=1$,
$\vartheta(x_{21})=\vartheta(0):=0$, $\vartheta(x_{12}):=\alpha$ and
$\vartheta(x_{22}):=\beta$, for some $\alpha,\beta\in k$. Since,
$x_{12}^{2}=0$ we obtain that $\alpha=0$ and $\beta\neq 0$ since the matrix
$(\vartheta(x_{ij}))$ is invertible. Thus, ${\rm Aut}_{{\rm
Alg}}\bigl{(}k[X]/(X^{2})\bigl{)}\,\cong\,k^{*}$.

######  Example 2.6.

Let $A:=\begin{pmatrix}k&k\\\ 0&k\end{pmatrix}\subseteq{\rm M}_{2}(k)$ be the
algebra of upper-triangular matrices with the basis
$\\{e_{1}:=I_{2},\,e_{2}:=e_{21},\,e_{3}:=e_{22}\\}$. Then $a(A)$ is the
algebra generated by $\\{x_{ij}\,|\,i,j=1,2,3\\}$ and the relations:

$\displaystyle
x_{11}=1,\,\,x_{21}=x_{31}=0,\,\,x_{12}^{2}=0,\,\,x_{12}x_{13}=x_{12},\,\,x_{13}x_{12}=0$
$\displaystyle
x_{13}^{2}=x_{13},\,\,x_{12}x_{22}+x_{22}x_{12}=-x_{22}x_{32},\,\,x_{12}x_{23}+x_{23}x_{13}+x_{22}x_{33}=x_{22}$
$\displaystyle
x_{13}x_{22}+x_{23}(x_{12}+x_{32})=0,\,\,x_{13}x_{23}+x_{23}(x_{13}+x_{33})=x_{23}$
$\displaystyle
x_{32}x_{33}+x_{32}x_{13}+x_{12}x_{33}=x_{32},\,\,x_{32}^{2}+x_{32}x_{12}+x_{12}x_{32}=0$

Indeed, the only non-zero structure constants of the algebra $A$ are:

$\tau_{1,j}^{j}=\tau_{j,1}^{j}=\tau_{2,3}^{2}=\tau_{3,3}^{3}:=1$

for all $j=1,2,3$. A routine computation shows that out of the 27 relations
(14) defining algebra $a(A)$ only the above remain.

## References

  * [1] Agore, A.L. - Universal coacting Poisson Hopf algebras, Manuscripta Math., 165 (2021), 255–268.
  * [2] Agore, A.L., Militaru, G. - A new invariant for finite dimensional Leibniz/Lie algebras, J. Algebra, 562(2020), 390–409.
  * [3] Agore, A.L., Gordienko, A.S., Vercruysse, J. - Equivalences of (co)module algebra structures over Hopf algebras, to appear in J. Noncommut. Geom., arXiv:1812.04563.
  * [4] Agore, A.L., Gordienko, A.S., Vercruysse, J. - $V$-universal Hopf algebras (co)acting on $\Omega$-algebras, arXiv:2005.12954.
  * [5] Bahturin, Y., S. K. Sehgal, S.K., M. V. Zaicev, M.V. - Group gradings on associative algebras, J. Algebra, 241 (2001), 677–698.
  * [6] Bavula, V.V. and Jordan, D.A. - Isomorphism problems and groups of automorphisms for generalized Weyl algebras, Trans. Amer. Math. Soc., 353 (2001), 769–794.
  * [7] Besleaga, F., Dascalescu, S. - Structural matrix algebras, generalized flags and gradings, Trans. Amer. Math. Soc., 373(2020), 6863–6885.
  * [8] Ceken, S., Palmieri, J., Wang Y.- H. and Zhang, J.J. - The discriminant controls automorphism groups of noncommutative algebras, Adv. Math., 269 (2015), 551–584.
  * [9] Couto, M. - Commutative-by-finite Hopf algebras and their finite dual, thesis, University of Glasgow (2019), http://theses.gla.ac.uk/74418/.
  * [10] Dascalescu, S., Ion, B., Nastasescu, C., and J. Rios Montes - Group gradings on full matrix rings, J. Algebra, 220(1999), 709–728.
  * [11] Elduque, A., Kochetov, M. - Gradings on Simple Lie Algebras, Mathematical Surveys and Monographs, Vol. 189, 2013, Amer. Math. Soc.
  * [12] Ge, F., G. Liu, G. - A combinatorial identity and the finite dual of infinite dihedral group algebra, Mathematika 67 (2021), 498–513.
  * [13] Gordienko, A., Schnabel, O. - On weak equivalences of gradings, J. Algebra, 501 (2018), 435–457.
  * [14] Li, K., Liu, G. - The finite duals of affine prime regular Hopf algebras of GK-dimension one, arXiv:2103.00495.
  * [15] Manin, Yu. I. - Quantum groups and noncommutative geometry, Universite de Montreal, Centre de Recherches Mathematiques, Montreal, QC, 1988.
  * [16] Montgomery, S. - Hopf algebras and their actions on rings, 82 (1992), AMS.
  * [17] Nastasescu, C. and Oystaeyen F. van - Methods of graded rings, Lecture Notes in Math., vol. 1836(2004), Springer Verlag.
  * [18] Tambara, D. - The coendomorphism bialgebra of an algebra. J. Fac. Sci. Univ. Tokyo Math. 37 (1990), 425–456.
  * [19] Radford, D.E. - Hopf algebras, World Scientific, 2012.
  * [20] Radford, D.E. - The structure of Hopf algebras with a projection, J. Algebra 92(1985), 322–347.
  * [21] Shestakov, I. and Umirbaev, U. - The tame and the wild automorphisms of polynomial rings in three variables, J. Amer. Math. Soc., 17(2004), 197–227.
  * [22] Skolem, T. - Zur Theorie der assoziativen Zahlensysteme, Skrifter Oslo, 12 (1927), 50.
  * [23] Sweedler, M.E. - Hopf Algebras, Benjamin New York, 1969.
  * [24] Zel’manov, E. I. - Semigroup algebras with identities, Siberian Mathematical Journal, 18 (1977), 557–565.