\section{Introduction} \label{sec:Introduction}

Game theory is a powerful tool that can be especially helpful whenever one wants to study complex situations, concerning conflict, competition, cooperation, and, even, survival between rational entities, typically refereed to as players. Despite its rather playful terminology and setting, game theory has been used to address serious problems from a multitude of fields, ranging from economics, political and social sciences, to computer science, evolutionary biology and psychology. It is not at all surprising that for such a popular subjects there are many superb textbooks. Such a modern and pedagogical introduction is the book \cite{Dixit2015}. For the reader striving for more rigor, the book \cite{Myerson1997} by Myerson and the book by Maschler et al. \cite{Maschler2020} fit the bill. These books are the main references for the game-theoretic concepts used in this paper. Game theory provides an elaborate framework that facilitates the analysis of conflict, competition, and cooperation. This analysis is primarily based on the concept of players or agents. Every agent has her own agenda and her actions interfere with the plans of the other agents. When the game ends, every player evaluates her gains or losses using a payoff function. The assumption of rationality is essential in order to ensure that every agent strives to maximize her payoff.

The field of quantum computation promises to bring a new era in our computational abilities. Although its origins can be traced back to the early '80s, it took a while for the field to mature and reach its current state. Today there exist commercial quantum computers utilizing a rather modest number number of qubits. This is expected to change in the coming years; if the predictions come true, the number of available qubits will increase substantially. This, in turn, will offer a spectacular increase in our computational capabilities and enable us to tackle useful and practical instances of difficult decision and optimization problems. In this larger perspective it would seem that the emergence of quantum games was unavoidable. The recent field of quantum game theory studies the use of quantum ideas and concepts in classical games, such as the coin flipping, the prisoners' dilemma and many others.

\subsection{Related work}

The field of quantum games was initiated in 1999 when Meyer in his influential paper \cite{Meyer1999} presented the PQ penny flip game, which is the quantum version of the classical penny flip game. One of the major attractions of his formulation was the inclusion of two well-known fictional characters, Picard and Q, from the famous tv series Star Trek, that compete by acting upon a quantum coin. Picard represents the classical player and Q the quantum player. This means that Picard behaves as a player in the classical penny flip game, but Q can use arbitrary unitary operator, a hallmark of the quantum domain. Mayer proved that in this game Q can always win using the venerable Hadamard transform. Later, many researchers motivated by Meyer's ideas, generalized the same game pattern to $n$-dimensional quantum systems. This line of research was pursued in \cite{Wang2000}, \cite{Ren2007}, and \cite{Salimi2009}. Later, a complete correspondence of every finite variant of the PQ penny flip game with easily constructed finite automata was given in \cite{Andronikos2018}. Recently, the same game was extensively analyzed from the viewpoint of groups and its relation to the dihedral groups was established in \cite{Andronikos2021}. In many works the quantum player seems to have a clear advantage over the classical player. However, things are not that black and white, as was shown in \cite{Anand2015}. The authors there cleverly changed the rules of the PQ penny flip game and this allowed the classical player to win. Another general and interesting problem, that of quantum gambling based on Nash equilibrium, was also recently studied in \cite{Zhang2017}. In a similar vein, quantum coin flipping has ben used as a crucial ingredient of many quantum cryptographic protocols, where the usual suspects Alice and Bob assume the role of remote parties that have to agree on a random bit (see \cite{Bennett2014} for more details). This idea has been extended in \cite{Aharon2010} to quantum dice rolling in settings of multiple outcomes and more than two parties.

A particularly influential work, also from 1999, was the one by Eisert et al. in \cite{Eisert1999}. They introduced a novel technique, the Eisert-Wilkens-Lewenstein protocol, which is now extensively used in the literature. Using their technique, they defined a variant of the famous prisoners' dilemma and demonstrated that there exists a quantum strategy that is better than any classical strategy. Subsequently, many researchers followed that line of research, obtaining interesting results. For some recent developments one may consult \cite{Giannakis2019}, where the correspondence of typical conditional strategies used in the classical repeated prisoners' dilemma game to languages accepted by quantum automata was established, and \cite{Rycerz2020}, where the Eisert–Wilkens–Lewenstein protocol was generalized.

The connection between game theory, and in particular infinitely repeated games, and finite automata was initially investigated in the works of \cite{Neyman1985}, \cite{Rubinstein1986}, \cite{Abreu1988}, and \cite{Marks1990}. Subsequently, Meyer used quantum lattice gas automata to study Parrondo games in \cite{Meyer2002}. The application of probabilistic automata in the prisoners' dilemma game was undertaken in \cite{Bertelle2002}, while \cite{Suwais2014} considered the use of different automata variants in game theory. In \cite{Giannakis2015a} it was pointed out that quantum automata operating on infinite words can encode winning strategies for abstract quantum games.

It is worth noting that the idea to resort to unconventional means to achieve better results in classical games is not limited to the quantum domain. The most famous classical games, such as the prisoners' dilemma, have been cast in terms of biological notions (see \cite{Kastampolidou2020} for a survey). Actually, a lot of classical games can be expressed in the context of biological and bio-inspired processes (see \cite{Kastampolidou2020,Theocharopoulou2019,Kastampolidou2020a} for more references).

\subsection{Contribution}

This paper studies sequential quantum games, under the premise that the sets of moves available to the players are groups of unitary operators and not just plain vanilla sets. The additional structure present in the groups facilitates the derivation of quite general results that completely clarify the existence or not of winning strategies. Emphasis is placed not only in the case where both players are on an equal footing in terms of available actions and number of moves, but also to the case where one player has a strong advantage over the one. This advantage may concern either the number of moves, or the set of available actions, or both. It is established that who wins depends on the combination of two factors: (i) the sets of admissible moves for each player, and (ii) the order of moves, i.e., whether the same player makes the first and the last move. An important conclusion is that quantum strategies do not necessarily prevail over classical ones. The game designer has the ability to either guarantee the fairness of the game, or to give a decisive advantage to one of the players. The results obtained in this paper are, to the best of our knowledge, stated and proved in this generality for the first time in the literature.

\subsection{Organization}

This paper is organized as follows: Section \ref{sec:Introduction} provides the most relevant references, while Section \ref{sec:Background} explains the concepts and notation used in this paper. Sections \ref{sec:Results for Canonical Games} and \ref{sec:Results for Asymmetric Games} state and prove the main results of this work. Section \ref{sec:Discussion and Examples} presents two illustrative examples and discusses the most important findings. Finally, Section \ref{sec:Conclusions} contains the main conclusions, along with some pointers for future work.

\section{Background} \label{sec:Background}

This paper studies \emph{sequential} \emph{zero-sum} quantum games that are played between two rational players, namely player 1 and player 2. The term sequential means that there is a specific predefined order of play. The two players do not act simultaneously, but take turns making their moves, always adhering to the predefined order. A single move by any player will be referred to as a \emph{round}.
Of course, zero-sum implies that the amount of loss of player 1 is equal to the amount of gain of player 2 and vice versa. Before we proceed any further, let us formally state the assumptions on which our analysis is based.

\begin{enumerate}
	\item[\textbf{A1:}]	The object of the game is a fixed $n$-dimensional quantum system. This can be any finite dimensional quantum system, but if a more concrete visualization can enhance our perception, we may think of a quantum coin, or a quantum dice, or a quantum roulette.
	\item[\textbf{A2:}]	The game takes place in the $n$-dimensional complex Hilbert space $\mathcal{H}_{n}$. The computational basis, $H_{n}$, consists of the $n$ basis states: $\ket{0},$ $\ket{1},$ $\dots,$ $\ket{n - 1}$.
	\item[\textbf{A3:}]	The system is initially in one of its basis states. This is predefined and agreed upon by both players. Henceforth, we shall refer to this basis state as the \emph{initial} state and designate it by $\ket{q_{0}} \in H_{n}$.
	\item[\textbf{A4:}]	The two players take turns acting upon the system according to some predefined order.

	$A$ and $B$ denote the sets of admissible moves of players 1 and 2, respectively. The two players draw their moves from their respective set when acting upon the system. In this paper, we shall assume that $A$ and $B$ are nontrivial \emph{subgroups} of $U(n)$, the unitary group of degree $n$. We use the standard notation $A, B \leq U(n)$ to denote this fact, and we refer to them as \emph{action groups}.
	\item[\textbf{A5:}]	Both players know the initial state of the system, but after the game begins and while it unfolds the state of the system is unknown to both of them. After the game ends, the state of the system is measured in the computational basis. If it is found to be $\ket{q_{A}} \in H_{n}$ then player 1 wins, whereas if it is found to be $\ket{q_{B}} \in H_{n}$ then player 2 wins. We shall assume that $\ket{q_{A}}$ and $\ket{q_{B}}$ are \emph{different}, and refer to $\ket{q_{A}}$ and $\ket{q_{B}}$ as the \emph{target} state of player 1 and the \emph{target} state of player 2, respectively.
	\item[\textbf{A6:}]	Therefore, each player knows:
	\begin{enumerate}
		\item	the set of moves of the other player,
		\item	the initial state $\ket{q_{0}}$, and
		\item	the target state of the other player.
	\end{enumerate}
	The players do not know the state of system after the game begins, and until they make the final measurement.

\end{enumerate}

So, the situation in a quantum game is in stark contrast to the typical situation of classical games, where both players are aware of the state of the system as the game progresses, and are thus able, at least in principle, to adapt their strategies. The fact that none of the players knows the state of the system deprives them of critical information that might have helped them to win the game. In effect it places an additional difficulty upon the decision-making process of the players.

At this point, we make the following helpful remarks:
\begin{enumerate}
	\item	More general situations can be easily envisioned. For example, the initial state may be a (maximally) entangled state or the target state (for either player) might also be entangled (see also the important reference \cite{Anand2015}). Nevertheless, we shall not concern ourselves with such cases here.
	\item	It is certainly possible to think of games where the sets of moves $A$ and $B$ are just (finite) subsets of $U(n)$, i.e., without the additional structure of a group. However, by assuming that $A$ and $B$ are groups, we can easily arrive at interesting conclusions. The concepts and the notation from group theory will be kept to a minimum and, in any case, can be found in standard textbooks such as \cite{Artin2011} and \cite{Dummit2004}. For unitary groups in particular more specialized text such as \cite{Stillwell2008} and \cite{Hall2013} can be consulted.
\end{enumerate}

In the context of sequential quantum games, it is convenient to employ the terminology outlined in Definition \ref{def:Strong and Weak Winning Strategies}, adapted from \cite{Maschler2020} and \cite{Myerson1997} to fit our analysis. Informally, the word \emph{strategy} implies the existence of a plan on behalf of each player. This plan is composed of actions, or moves that the player makes as the game evolves.

\begin{definition} [Strong and weak winning strategies] \label{def:Strong and Weak Winning Strategies} \
	\begin{itemize}
		\item	A \emph{strategy} $\sigma_{1} = (A_1, \dots, A_{m_1})$ $( \sigma_{2} = (B_1, \dots, B_{m_2}) )$ for player 1 $($player 2$)$ is a sequence of admissible moves, where $m_1$ $(m_2)$ is the number of rounds that player 1 $($player 2$)$ acts on the system, and $A_1, \dots, A_{m_1} \in A$ $( B_1, \dots, B_{m_2} \in B )$.
		\item	A strategy $\sigma_{1}$ $( \sigma_{2} )$ is a \emph{strong winning} strategy for player 1 $($player 2$)$ if for \emph{every} strategy $\sigma_{2}$ $( \sigma_{1} )$ of player 2 $($player 1$)$, player 1 $($player 2$)$ wins the game with probability $1.0$.
		\item	A strategy $\sigma_{1}$ $( \sigma_{2} )$ is a \emph{weak winning} strategy for player 1 $($player 2$)$ if for \emph{there exists} a strategy $\sigma_{2}$ $( \sigma_{1} )$ of player 2 $($player 1$)$, such that player 1 $($player 2$)$ wins the game with probability $1.0$.
	\end{itemize}
\end{definition}

Since the main concern of this work is to examine when a player can win with probability $1.0$ no matter what the other player does, it focuses on strong winning strategies. This situation is more succinctly described by saying that the player \emph{surely wins} the game. The notion of weak winning strategy can serve simply as an indicator of a possible win, in contrast to a certain win.

It is conceivable that a game may be devised so that one of the players or even both players act on the system for a number of consecutive rounds. For instance, perhaps in a game one player makes the moves $A_{i}, A_{i + 1}, \dots, A_{j}$ back-to-back, without the other player being allowed to make an intermediate move. Such a situation can be greatly simplified due to the fact that the moves available to each player are elements of a group. This means that their composition is also an element of the same group and as such it is available to the player. In the preceding example, the action $C = A_{j} \dots A_{i + 1} A_{j}$, is also an admissible move for the player. Hence, for the rest of this paper, the following useful simplification is adopted: \emph{no player plays two or more successive rounds and the two players alternate each round}. This motivates the next Definition \ref{def:Canonical and Noncanonical Games}.

\begin{definition} [Canonical and noncanonical games] \label{def:Canonical and Noncanonical Games} \
	\begin{itemize}
		\item	A game is called \emph{canonical} if its duration is $2 m$ rounds, player 1 plays at odd rounds $1, 3, \dots, 2 m - 1$, and player 2 at even rounds $2, 4, \dots, 2 m$. In a canonical game both players play the same number of rounds taking turns making their moves, player 1 plays first, and player 2 plays last.
		\item	A game is called \emph{noncanonical} if it has $2 m + 1$ rounds, player 1 plays at odd rounds $1, 3, \dots, 2 m - 1, 2 m + 1$, and player 2 at even rounds $2, 4, \dots, 2 m$. In a noncanonical game both players take turns making their moves, but player 1  plays one more round than player 2 and makes the \emph{first} and the \emph{last} move.
	\end{itemize}
\end{definition}

Let us remark that it is the assumption that the repertoire of actions for each player constitutes a group that makes this simplification possible. If the player's set of moves is just a set and not a group, then it is quite possible that the composition of moves is not an element of this set.

It would not make any difference if in the definition of canonical games it was player 2 that made the first move. The important point is that canonical games capture the notions of symmetry and fairness, with respect to sequential quantum games, in the sense that both players have the exact same number of moves, one gets to act first and the other last. Similarly, in noncanonical games it is not substantial that player 1 makes the first and the last move. It would be equally viable to be player 2. What matters is that noncanonical games model asymmetric situations when one of the players seems to have the advantage of both starting and finishing the game. An abstract visual representation of the form of canonical and noncanonical games is given in Figures \ref{fig:Canonical Game} and \ref{fig:Noncanonical Game}, respectively.

\vspace{0.5 cm}

\begin{figure}[H]
	\centering
	\begin{tikzpicture} [scale = 1.0]
		\begin{yquant}
			qubits {$\ket{q_0}$} GAME;
			%
			hspace {0.2 cm} GAME;

			box {$A_1$} GAME;
			%
			hspace {0.2 cm} GAME;

			box {$B_1$} GAME;
			%
			hspace {0.2 cm} GAME;

			box {$A_2$} GAME;
			%
			hspace {0.2 cm} GAME;

			box {$B_2$} GAME;
			%
			hspace {0.2 cm} GAME;
			[draw = none]
			box {$\dots$} GAME;
			%
			hspace {0.2 cm} GAME;

			box {$A_{m}$} GAME;
			%
			hspace {0.2 cm} GAME;

			box {$B_{m}$} GAME;
			%
			hspace {0.2 cm} GAME;

			measure GAME;
			%
			hspace {0.2 cm} GAME;
			output {$\ket{q?}$} GAME;
		\end{yquant}
	\end{tikzpicture}
	\caption{This figures gives a schematic representation of a $2 m$ round canonical game in which the two players take turns playing $m$ round each. Player 1 makes the first move and player 2 the last. The question mark ``?'' is used to convey the fact that the outcome of the measurement cannot be determined with probability 1.0 beforehand.}
	\label{fig:Canonical Game}
\end{figure}

\vspace{0.3 cm}

\begin{figure}[H]
	\centering
	\begin{tikzpicture} [scale = 1.0]
		\begin{yquant}
			qubits {$\ket{q_0}$} GAME;
			%
			hspace {0.2 cm} GAME;

			box {$A_1$} GAME;
			%
			hspace {0.2 cm} GAME;

			box {$B_1$} GAME;
			%
			hspace {0.2 cm} GAME;

			box {$A_2$} GAME;
			%
			hspace {0.2 cm} GAME;

			box {$B_2$} GAME;
			%
			hspace {0.2 cm} GAME;
			[draw = none]
			box {$\dots$} GAME;
			%
			hspace {0.2 cm} GAME;

			box {$A_{m}$} GAME;
			%
			hspace {0.2 cm} GAME;

			box {$B_{m}$} GAME;
			%
			hspace {0.2 cm} GAME;

			box {$A_{m + 1}$} GAME;
			%
			hspace {0.2 cm} GAME;

			measure GAME;
			%
			hspace {0.2 cm} GAME;
			output {$\ket{q?}$} GAME;
		\end{yquant}
	\end{tikzpicture}
	\caption{This figures shows a $2 m + 1$ round noncanonical game in which the player 1 plays $m + 1$ rounds but player 2 only $m$ rounds. Player 1 makes the first and the last move. In this case too the question mark ``?'' is used to convey the fact that the outcome of the measurement cannot be determined with probability 1.0 beforehand.}
	\label{fig:Noncanonical Game}
\end{figure}

\section{Results for canonical games} \label{sec:Results for Canonical Games}

In the subsequent study one well-known classical group will feature prominently. This is the group of all permutations of the indices $\{1, 2, \dots, n\}$, which is called the \emph{symmetric group}, and is denoted by $S_n$. If one distinguishes between the quantum and the classical player, as is often done in this area, the symmetric group in a sense encodes the maximal capabilities of the classical player. Thus it makes sense to consider it as a point of reference when analyzing how the classical player can act on the system. The elements of the symmetric group have a standard matrix representation (see also \cite{Artin2011} and \cite{Meyer2000}) in the form of permutation matrices. A \emph{permutation matrix} has a single 1 in each row and in each column and all its other entries are 0.

The identity operator, which is the identity element of the groups $S_{n}$ and $U(n)$, is denoted by $I$ and is succinctly written as $I = \begin{bmatrix} \ket{0} | \dots | \ket{i} | \dots | \ket{j} | \dots | \ket{n - 1} \end{bmatrix}$. Among permutation matrices, especially useful are the \emph{transposition} matrices. Transposition matrices are designated by $T_{i, j}$, where $0 \leq i \neq j \leq n - 1$.

\begin{align} \label{eq:Transposition Matrix Definition}
	T_{i, j}
	=
	\NiceMatrixOptions
	{
		code-for-first-row = \color{WordRed},
	}
	\begin{bNiceMatrix}[first-row]
		0^{th}	&	\dots	&	i^{th}	&	\dots	&	j^{th}	&	\dots	&	(n - 1)^{th}	\\
		\ket{0}	&	\dots	&	\ket{j}	&	\dots	&	\ket{i}	&	\dots	&	\ket{n - 1}
	\end{bNiceMatrix}
	\ .
\end{align}

Transposition matrices can interchange basis kets as follows:

\begin{align} \label{eq:Transposition Matrix Properties}
	T_{i, j} \ket{i} = \ket{j}
	\qquad \text{and} \qquad
	T_{i, j} \ket{j} = \ket{i}
	\ .
\end{align}

\begin{example}
For instance, when $n = 7$, the computational basis $H_{7}$ consists of the $7$ basis states: $\ket{0}, \ket{1}, \dots, \ket{6}$ shown below, and the corresponding symmetric group is $S_7$.

\begin{align} \label{eq:The Computational Basis $H_{7}$}
	\ket{0} =
	\begin{bNiceMatrix}
		1 \\
		0 \\
		0 \\
		0 \\
		0 \\
		0 \\
		0
	\end{bNiceMatrix}, \
	\ket{1} =
	\begin{bNiceMatrix}
		0 \\
		1 \\
		0 \\
		0 \\
		0 \\
		0 \\
		0
	\end{bNiceMatrix}, \
	\ket{2} =
	\begin{bNiceMatrix}
		0 \\
		0 \\
		1 \\
		0 \\
		0 \\
		0 \\
		0
	\end{bNiceMatrix}, \
	\ket{3} =
	\begin{bNiceMatrix}
		0 \\
		0 \\
		0 \\
		1 \\
		0 \\
		0 \\
		0
	\end{bNiceMatrix}, \
	\ket{4} =
	\begin{bNiceMatrix}
		0 \\
		0 \\
		0 \\
		0 \\
		1 \\
		0 \\
		0
	\end{bNiceMatrix}, \
	\ket{5} =
	\begin{bNiceMatrix}
		0 \\
		0 \\
		0 \\
		0 \\
		0 \\
		1 \\
		0
	\end{bNiceMatrix}, \
	\ket{6} =
	\begin{bNiceMatrix}
		0 \\
		0 \\
		0 \\
		0 \\
		0 \\
		0 \\
		1
	\end{bNiceMatrix} \ .
\end{align}

As a typical example of a transposition matrix we may consider $T_{3, 5}$.

\begin{align} \label{eq:Transposition Matrix $T_{3, 5}$}
	T_{3, 5}
	\overset{ (\ref{eq:Transposition Matrix Definition}) }{=}
	\begin{bNiceMatrix}
		\ket{0} & \ket{1} & \ket{2} & \ket{5} & \ket{4} & \ket{3} & \ket{6}
	\end{bNiceMatrix}
	=
	\begin{bNiceMatrix}
		1 & 0 & 0 & 0 & 0 & 0 & 0 \\
		0 & 1 & 0 & 0 & 0 & 0 & 0 \\
		0 & 0 & 1 & 0 & 0 & 0 & 0 \\
		0 & 0 & 0 & 0 & 0 & 1 & 0 \\
		0 & 0 & 0 & 0 & 1 & 0 & 0 \\
		0 & 0 & 0 & 1 & 0 & 0 & 0 \\
		0 & 0 & 0 & 0 & 0 & 0 & 1
	\end{bNiceMatrix} \ .
\end{align}

It is easy to verify that the properties outlined in (\ref{eq:Transposition Matrix Properties}) are satisfied:

\begin{align} \label{eq:Transposition Matrix $T_{3, 5}$ Properties}
	T_{3, 5} \ket{3} = \ket{5}
	\qquad \text{and} \qquad
	T_{3, 5} \ket{5} = \ket{3}
	\ .
\end{align}

\end{example}

The following fact, which is self-evident, is recorded as Proposition \ref{prp:Condition for Strong Winning Strategy} for future reference.

\begin{proposition} \label{prp:Condition for Strong Winning Strategy}
	In any type of game, canonical or noncanonical, player 1 $($player 2$)$ has a strong winning strategy, if and only if the state of the quantum system $\ket{\psi}$ prior to measurement is the target state $\ket{q_{A}}$ $(\ket{q_{B}})$ of player 1 $($player 2$)$.
\end{proposition}

\begin{theorem}[The same action group for both players] \label{thr:CSG Same action group for Both Players}
	Consider a canonical game where both players use the same action group. If the action group contains $S_{n}$ as a subgroup, i.e., $S_{n} \leq A = B \leq U(n)$, no player has a strong winning strategy, but both players have a weak winning strategy.
\end{theorem}
\begin{proof}[Proof of Theorem \ref{thr:CSG Same action group for Both Players}]
	Suppose to the contrary that player 1 has a strong winning strategy $\sigma_{1}$ $=$ $(A_1,$ $A_2,$ $\dots,$ $A_m)$, where $A_1, A_2, \dots, A_m \in A$. This means that for every strategy $\sigma_{2}$ of player 2, player 1 will surely win.

	Consider the following two strategies for player 2: $\sigma_{2} = (B_1, B_2, \dots, B_{m - 1}, I)$ and $\sigma'_{2}$ $=$ $(B_1,$ $B_2,$ $\dots,$ $B_{m - 1},$ $T_{q_A, q_B})$, where $B_1, B_2, \dots, B_{m - 1}, I, T_{q_A, q_B} \in B$ because $B$ contains $S_{n}$. In view of Proposition \ref{prp:Condition for Strong Winning Strategy}, it must hold that
	\begin{align}
		I A_m \dots B_1 A_1 \ket{q_{0}} &= \ket{q_{A}} \label{eq:CSG Strong Winning Strategy Condition for Player 1 - I} \qquad \text{and}
		\\
		T_{q_A, q_B} A_m \dots B_1 A_1 \ket{q_{0}} &= \ket{q_{A}} \label{eq:CSG Strong Winning Strategy Condition for Player 1 - II} \ .
	\end{align}
	Equation (\ref{eq:CSG Strong Winning Strategy Condition for Player 1 - I}) implies that
	\begin{align}
		A_m \dots B_1 A_1 \ket{q_{0}} = \ket{q_{A}} \label{eq:CSG Strong Winning Strategy Condition for Player 1 - III} \ .
	\end{align}
	But then
	\begin{align} \label{eq:CSG Strong Winning Strategy Contradiction for Player 1}
		T_{q_A, q_B} A_m \dots B_1 A_1 \ket{q_{0}}
		\overset
		{ ( \ref{eq:CSG Strong Winning Strategy Condition for Player 1 - III} ) }
		{ = }
		T_{q_A, q_B} \ket{q_{A}} = \ket{q_{B}} \ ,
	\end{align}
	which contradicts (\ref{eq:CSG Strong Winning Strategy Condition for Player 1 - II}). Thus, player 1 does not have a strong winning strategy.

	Symmetrically, assume again to the contrary that player 2 has a strong winning strategy $\sigma_{2} = (B_1, B_2, \dots, B_{m - 1}, B_{m})$, where $B_1, B_2, \dots, B_m \in B$. Consider then the following two strategies for player 1: $\sigma_{1} = (A_1, A_2, \dots, A_{m - 1}, B_{m}^{-1})$ and $\sigma'_{1} = (A_1, A_2, \dots, A_{m - 1},$ $B_{m}^{-1} T_{q_A, q_B})$, where $A_1,$ $A_2,$ $\dots,$ $A_{m - 1},$ $B_{m}^{-1},$ $B_{m}^{-1} T_{q_A, q_B}$ $\in$ $A$ because $A = B$ and contains $S_{n}$. From Proposition \ref{prp:Condition for Strong Winning Strategy} we know that
	\begin{align}
		B_{m} B_{m}^{-1} B_{m - 1} A_{m - 1} \dots B_1 A_1 \ket{q_{0}} &= \ket{q_{B}} \label{eq:CSG Strong Winning Strategy Condition for Player 2 - I} \qquad \text{and}
		\\
		B_{m} B_{m}^{-1} T_{q_A, q_B} B_{m - 1} A_{m - 1} \dots B_1 A_1 \ket{q_{0}} &= \ket{q_{B}} \label{eq:CSG Strong Winning Strategy Condition for Player 2 - II} \ .
	\end{align}
	Equation (\ref{eq:CSG Strong Winning Strategy Condition for Player 2 - I}) implies that
	\begin{align}
		B_{m - 1} A_{m - 1} \dots B_1 A_1 \ket{q_{0}} &= \ket{q_{B}} \ , \label{eq:CSG Strong Winning Strategy Condition for Player 2 - III}
	\end{align}
	which together with (\ref{eq:CSG Strong Winning Strategy Condition for Player 2 - II}) gives
	\begin{align} \label{eq:CSG Strong Winning Strategy Contradiction for Player 2}
		B_{m} B_{m}^{-1} T_{q_A, q_B} B_{m - 1} A_{m - 1} \dots B_1 A_1 \ket{q_{0}}
		\overset
		{ ( \ref{eq:CSG Strong Winning Strategy Condition for Player 2 - III} ) }
		{ = }
		T_{q_A, q_B} \ket{q_{B}} = \ket{q_{A}} \ .
	\end{align}
	This last result contradicts (\ref{eq:CSG Strong Winning Strategy Condition for Player 2 - II}) and, therefore, player 2 does not have a strong winning strategy either.

	The existence of weak winning strategies for player 1 is easy to establish; the obvious choice $\sigma_{1} = (I, I, \dots, T_{q_A, q_B})$ is indeed such a strategy for player's 2 strategy $\sigma_{2} = (T_{q_0, q_B}, I, \dots, I)$. In an analogous manner we can show that player 2 has weak winning strategies too.
\end{proof}

This result is quite general and highlights the critical role of $S_{n}$ in quantum games. Furthermore, it allows us to immediately state two useful corollaries.

\begin{corollary}[Two classical players with the same action group] \label{crl:CSG Same Action Group for Classical Players}
	When two classical players use the same action group $S_{n}$ in a canonical game, neither of them has an advantage over the other, in the sense that neither possesses a strong winning strategy.
\end{corollary}

\begin{corollary}[Two quantum players with the same action group] \label{crl:CSG Same Action Group for Quantum Players}
	In a canonical game between two quantum players, if both players use the same action group that contains $S_{n}$, no player possesses a strong winning strategy.
\end{corollary}

These two corollaries prove that when both players have the same repertoire, which can be either classical, e.g., $S_{n}$, or quantum, e.g., a subgroup of $U(n)$, they are on an equal footing. This is a natural outcome of the overall symmetry in this case. The symmetry inherent in a canonical game is combined with the symmetry in the moves available to the players. If there is a moral in this, it would be that the pursuit of fairness, in the sense that both players have a chance to win, without any of them being certain to win, must involve symmetry.

\section{Results for asymmetric games} \label{sec:Results for Asymmetric Games}

The results of the previous section indicate that if we seek games where one players can surely win, we must turn to asymmetric settings. For this reason, in this section we shall consider three asymmetric scenarios:

\begin{enumerate}
	\item	The game is noncanonical, that is player 1, who makes the first move, also makes the last move, while both players have the same action group.
	\item	The game is canonical, but the action group $B$ of player 2 is a proper subgroup of the action group $A$ of player 1: $B < A$.
	\item	The game is noncanonical and, at the same time, the action group $B$ of player 2 is a proper subgroup of the action group $A$ of player 1.
\end{enumerate}

In the first of the above cases, the perceived advantage of player 1 is still not enough to guarantee a strong winning strategy. Hence, in this case too neither player is certain to win. This is proved in the next Theorem \ref{thr:NSG Noncanonical Game Same Action Group for Both Players}.

\begin{theorem}[Noncanonical game, same action group] \label{thr:NSG Noncanonical Game Same Action Group for Both Players}
	Consider a noncanonical game where player 1 makes the first and the last move and both players use the same action group. If the action group contains $S_{n}$, i.e., $S_{n} \leq A = B \leq U(n)$, no player has a strong winning strategy, but both players have a weak winning strategy.
\end{theorem}
\begin{proof}[Proof of Theorem \ref{thr:NSG Noncanonical Game Same Action Group for Both Players}]
	Suppose to the contrary that player 1 has a strong winning strategy $\sigma_{1}$ $=$ $(A_1,$ $A_2,$ $\dots,$ $A_{m},$ $A_{m + 1})$, where $A_1,$ $A_2,$ $\dots,$ $A_{m},$ $A_{m + 1}$ $\in$ $A$. This means that for every strategy $\sigma_{2}$ of player 2, player 1 will surely win.

	Consider the following two strategies of player 2: $\sigma_{2} = (B_1, B_2, \dots, B_{m - 1}, A_{m + 1}^{-1})$ and $\sigma'_{2}$ $=$ $(B_1,$ $B_2,$ $\dots,$ $B_{m - 1},$ $A_{m + 1}^{-1} T_{q_A, q_B})$, where $B_1, B_2, \dots, B_{m - 1}, A_{m + 1}^{-1}, A_{m + 1}^{-1} T_{q_A, q_B} \in B$ because $S_{n} \leq A = B \leq U(n)$. In view of Proposition \ref{prp:Condition for Strong Winning Strategy}, it must hold that
	\begin{align}
		A_{m + 1} A_{m + 1}^{-1} A_{m} \dots B_1 A_1 \ket{q_{0}} &= \ket{q_{A}} \label{eq:NSG Strong Winning Strategy Condition for Player 1 - I} \qquad \text{and}
		\\
		A_{m + 1} A_{m + 1}^{-1} T_{q_A, q_B} A_{m} \dots B_1 A_1 \ket{q_{0}} &= \ket{q_{A}} \label{eq:NSG Strong Winning Strategy Condition for Player 1 - II} \ .
	\end{align}
	Equation (\ref{eq:NSG Strong Winning Strategy Condition for Player 1 - I}) implies that
	\begin{align}
		A_m \dots B_1 A_1 \ket{q_{0}} = \ket{q_{A}} \label{eq:NSG Strong Winning Strategy Condition for Player 1 - III} \ .
	\end{align}
	Consequently,
	\begin{align} \label{eq:NSG Strong Winning Strategy Contradiction for Player 1}
		A_{m + 1} A_{m + 1}^{-1} T_{q_A, q_B} A_{m} \dots B_1 A_1 \ket{q_{0}}
		\overset
		{ ( \ref{eq:NSG Strong Winning Strategy Condition for Player 1 - III} ) }
		{ = }
		T_{q_A, q_B} \ket{q_{A}} = \ket{q_{B}} \ ,
	\end{align}
	which contradicts (\ref{eq:NSG Strong Winning Strategy Condition for Player 1 - II}). Thus, player 1 does not have a strong winning strategy.

	Similarly, in order to arrive at a contradiction, let us assume that player 2 has a strong winning strategy $\sigma_{2} = (B_1, B_2, \dots, B_{m - 1}, B_{m})$, where $B_1, B_2, \dots, B_m \in B$. Consider then the following two strategies of player 1: $\sigma_{1} = (A_1, A_2, \dots, A_{m}, I)$ and $\sigma'_{1} = (A_1, A_2, \dots, A_{m},$ $T_{q_A, q_B})$, where $A_1, A_2, \dots, A_{m}, I, T_{q_A, q_B} \in A$ because $A$ contains $S_{n}$. From Proposition \ref{prp:Condition for Strong Winning Strategy} we know that
	\begin{align}
		I B_{m} A_{m} \dots B_1 A_1 \ket{q_{0}} &= \ket{q_{B}} \label{eq:NSG Strong Winning Strategy Condition for Player 2 - I} \qquad \text{and}
		\\
		T_{q_A, q_B} B_{m} A_{m} \dots B_1 A_1 \ket{q_{0}} &= \ket{q_{B}} \label{eq:NSG Strong Winning Strategy Condition for Player 2 - II} \ .
	\end{align}
	Equation (\ref{eq:NSG Strong Winning Strategy Condition for Player 2 - I}) implies that
	\begin{align}
		B_{m} A_{m} \dots B_1 A_1 \ket{q_{0}} &= \ket{q_{B}} \ , \label{eq:NSG Strong Winning Strategy Condition for Player 2 - III}
	\end{align}
	which together with (\ref{eq:NSG Strong Winning Strategy Condition for Player 2 - II}) gives
	\begin{align} \label{eq:NSG Strong Winning Strategy Contradiction for Player 2}
		T_{q_A, q_B} B_{m} A_{m} \dots B_1 A_1 \ket{q_{0}}
		\overset
		{ ( \ref{eq:NSG Strong Winning Strategy Condition for Player 2 - III} ) }
		{ = }
		T_{q_A, q_B} \ket{q_{B}} = \ket{q_{A}} \ .
	\end{align}
	This last result contradicts (\ref{eq:NSG Strong Winning Strategy Condition for Player 2 - II}) and, therefore, player 2 does not have a strong winning strategy either.

	We can easily demonstrate the existence of weak winning strategies for both players using the same arguments as in Theorem \ref{thr:CSG Same action group for Both Players}.
\end{proof}

Let us emphasize that the above theorem holds when both players are classical and when both players are quantum.

Things are pretty much the same when the game is canonical, but the action group of one player is a proper subgroup of the action group of the other player, provided the smaller group contains $S_{n}$, as Theorem \ref{thr:CDG Canonical Game Different Action Group for Each Player} reveals.

\begin{theorem}[Canonical game, different action groups] \label{thr:CDG Canonical Game Different Action Group for Each Player}
	The following hold:
	\begin{itemize}
		\item	In a canonical game where the action group $A$ of player 1 contains $S_{n}$ and is a proper subgroup of the action group $B$ of player 2, i.e., $S_{n} \leq A < B \leq U(n)$, no player has a strong winning strategy.
		\item	Likewise, in a canonical game where the action group $B$ of player 2 contains $S_{n}$ and is a proper subgroup of the action group $A$ of player 1, i.e., $S_{n} \leq B < A \leq U(n)$, no player has a strong winning strategy.
	\end{itemize}
\end{theorem}
\begin{proof}[Proof of Theorem \ref{thr:CDG Canonical Game Different Action Group for Each Player}] \
	\begin{itemize}
		\item	Showing that player 1 does not have a strong winning strategy can be achieved by adapting the analogous arguments in Theorem \ref{thr:CSG Same action group for Both Players}.

		Therefore, we focus on showing that player 2 does not have a strong winning strategy either. To this end, let us suppose to the contrary that player 2 has a strong winning strategy $\sigma_{2} = (B_1, B_2, \dots, B_{m})$, where $B_1, B_2, \dots, B_{m} \in B$. This means that for every strategy $\sigma_{1}$ of player 1, player 2 will surely win. Consider the following two strategies of player 1: $\sigma_{1} = (T_{q_0, q_A}, A_2, \dots, A_{m})$ and $\sigma'_{2} = (T_{q_0, q_B}, A_2, \dots, A_{m})$, where $T_{q_0, q_A}, T_{q_0, q_B}, A_2, \dots, A_{m} \in A$ because $A$ contains $S_{n}$. Proposition \ref{prp:Condition for Strong Winning Strategy} entails that
		\begin{align}
			B_{m} A_{m} \dots B_1 T_{q_0, q_A} \ket{q_{0}} &= \ket{q_{B}} \label{eq:CDG Strong Winning Strategy Condition for Player 2 - I} \qquad \text{and}
			\\
			B_{m} A_{m} \dots B_1 T_{q_0, q_B} \ket{q_{0}} &= \ket{q_{B}} \label{eq:CDG Strong Winning Strategy Condition for Player 2 - II} \ .
		\end{align}
		If $C = B_{m} A_{m} \dots B_1$, then $C$ is a unitary operator, being the composition of unitary operators. Using $C$, equations (\ref{eq:CDG Strong Winning Strategy Condition for Player 2 - I}) and (\ref{eq:CDG Strong Winning Strategy Condition for Player 2 - II}) imply that
		\begin{align}
			C \ket{q_{A}} &= \ket{q_{B}} \label{eq:CDG Strong Winning Strategy Condition for Player 2 - III} \qquad \text{and}
			\\
			C \ket{q_{B}} &= \ket{q_{B}} \label{eq:CDG Strong Winning Strategy Condition for Player 2 - IV} \ .
		\end{align}
		This is impossible because $C$ is a unitary operator and, as such, sends different orthonormal vectors to different orthonormal vectors. Thus, player 2 does not have a strong winning strategy.

		\item	In this case it is straightforward to prove that player 2 does not have a strong winning strategy by suitably modifying analogous arguments in Theorem \ref{thr:CSG Same action group for Both Players}.

		Thus, we concentrate on showing that player 1 does not have a strong winning strategy either. To arrive at a contradiction, we suppose that player 1 has a strong winning strategy $\sigma_{1} = (A_1, A_2, \dots, A_{m})$, where $A_1, A_2, \dots, A_{m} \in A$. This means that for every strategy $\sigma_{2}$ of player 2, player 1 will surely win. Let us consider the following two strategies of player 2: $\sigma_{2} = (B_1, B_2, \dots, B_{m - 1}, I)$ and $\sigma'_{2} = (B_1, B_2, \dots, B_{m - 1},$ $T_{q_A, q_B})$, where $B_1, B_2, \dots, B_{m - 1}, I, T_{q_A, q_B} \in B$ because $B$ contains $S_{n}$. In view of Proposition \ref{prp:Condition for Strong Winning Strategy}, it must hold that
		\begin{align}
			I A_{m} \dots B_1 A_1 \ket{q_{0}} &= \ket{q_{A}} \label{eq:CDG Strong Winning Strategy Condition for Player 1 - I} \qquad \text{and}
			\\
			T_{q_A, q_B} A_{m} \dots B_1 A_1 \ket{q_{0}} &= \ket{q_{A}} \label{eq:CDG Strong Winning Strategy Condition for Player 1 - II} \ .
		\end{align}
		Equation (\ref{eq:CDG Strong Winning Strategy Condition for Player 1 - I}) implies that
		\begin{align}
			A_m \dots B_1 A_1 \ket{q_{0}} = \ket{q_{A}} \label{eq:CDG Strong Winning Strategy Condition for Player 1 - III} \ .
		\end{align}
		Consequently,
		\begin{align} \label{eq:CDG Strong Winning Strategy Contradiction for Player 1}
			T_{q_A, q_B} A_{m} \dots B_1 A_1 \ket{q_{0}}
			\overset
			{ ( \ref{eq:CDG Strong Winning Strategy Condition for Player 1 - III} ) }
			{ = }
			T_{q_A, q_B} \ket{q_{A}} = \ket{q_{B}} \ ,
		\end{align}
		which contradicts (\ref{eq:CDG Strong Winning Strategy Condition for Player 1 - II}). This concludes the proof that player 1 does not have a strong winning strategy.
	\end{itemize}
\end{proof}

We have thus arrived at an important realization. To ensure that one player has a strong winning strategy is not enough for her to play first and last if the other player has the same set of moves. Perhaps even more importantly, we have discovered that in a canonical game even if one player has access to a much larger action group, let's say the entire $U(n)$, she may still not win with probability $1.0$, provided the other player's action group contains $S_{n}$. Again, the hypothesis that the smaller group contains $S_{n}$ is absolutely critical. Unavoidably, to ensure the existence of a strong winning strategy for player 1 we must set the rules of the game so that she makes the first and the last move and, at the same time, her action group $A$ is sufficiently larger than the action group $B$ of player 2. This is what the following Theorem \ref{thr:NDG Noncanonical Game Different Action Group for Each Player} asserts. The proof is simple and is based on the concept of a state being unaffected by the action of all the elements of a group. In particular, we shall call a state $\ket{\psi}$ \emph{invariant} under the action of the group $B$, if for \emph{every} $B_i \in B$ it holds that $B_i \ket{\psi} = \ket{\psi}$. Of course, the identity operator $I$ fixes every state, but in this case the requirement is that all operators in $B$ fix the state $\ket{\psi}$.

\begin{theorem}[Noncanonical game and different action group] \label{thr:NDG Noncanonical Game Different Action Group for Each Player}
	Consider a noncanonical game where player 1 makes the first and the last move.
	\begin{itemize}
		\item	If the action group $A$ of player 1 contains $S_{n}$ as well as some action $U \in A$, which can drive the system from its initial state to a state $\ket{\psi}$ invariant under the action of $B$, then player 1 has a strong winning strategy.
		\item	If the action group $A$ of player 1 does not contain $S_{n}$, but contains some action $U \in A$ that can drive the system from its initial state to a state $\ket{\psi}$ invariant under the action of $B$, and her target state is the initial state, then player 1 has a strong winning strategy.
	\end{itemize}
\end{theorem}
\begin{proof}[Proof of Theorem \ref{thr:NDG Noncanonical Game Different Action Group for Each Player}] \
	\begin{itemize}
		\item	The fact that there exists $U \in A$ such that $U \ket{q_{0}} = \ket{\psi}$, implies that the strategy $\sigma_{1}$ $=$ $(U,$ $I,$ $\dots,$ $I,$ $T_{q_0, q_A} U^{- 1})$ is a strong winning strategy for player 1. Note that the composition $T_{q_0, q_A} U^{- 1}$ constitutes a move available to player 1 because $A$ contains $S_{n}$. It is easy to see that when player 2 makes her first move, the system is already at state $\ket{\psi}$, which, according to the hypothesis is invariant under the action of all operators in $B$. Thus, no matter what strategy player 2 employs the system will remain at state $\ket{\psi}$ until the last round of the game. Then during the last round of the game player 1 will drive the system to her target state $\ket{q_{A}}$ via the action $T_{q_0, q_A} U^{- 1}$.
		\item	In this case, although there exists $U \in A$ such that $U \ket{q_{0}} = \ket{\psi}$, the action group $A$ does not contain $S_{n}$ and, hence, transpositions cannot be used. The extra hypothesis in this case, which is that the target state of player 1 is $\ket{q_{0}}$, is critical. The strategy $\sigma_{1} = (U, I, \dots, I, U^{- 1})$ is a strong winning strategy for player 1. Again, it is easy to verify that when player 2 makes her first move, the system is already at state $\ket{\psi}$, which, according to the hypothesis is invariant under the action of all operators in $B$. Thus, no matter what strategy player 2 employs the system will remain at state $\ket{\psi}$ until the last round of the game. Then during the last round of the game player 1 will drive the system to back to its initial state $\ket{q_{0}}$, which is also her target state, via the action $U^{- 1}$.
	\end{itemize}
\end{proof}

At this point it may be expedient to clarify that the situation described in Theorem \ref{thr:NDG Noncanonical Game Different Action Group for Each Player} can only be realized when the action groups of the two players are different. It is straightforward to see that if $A = B$, whatever player 1 does to the system via a transformation $U$, can be undone by player 2 via $U^{- 1}$, which is available to her. In such a case, evidently, there exists no invariant state.

Theorem \ref{thr:NDG Noncanonical Game Different Action Group for Each Player} can help us to complete the picture formed by the previous three theorems. Theorems \ref{thr:CSG Same action group for Both Players} -- \ref{thr:CDG Canonical Game Different Action Group for Each Player} are somewhat negative by asserting the absence of a strong winning strategy. Theorem \ref{thr:NDG Noncanonical Game Different Action Group for Each Player} is more positive by giving conditions, or, a ``recipe'' for the design of games that ensure that one player will surely win. For example, this strategy is implicitly followed in the original PQ penny flip game of \cite{Meyer1999} and its clever generalizations to higher dimensions, like roulette, accomplished in \cite{Wang2000}, \cite{Ren2007}, and \cite{Salimi2009}. The following Table \ref{tbl:Conditions for the Existence of Strong Winning Strategy} summarizes the results we have obtained.

\hspace{0.5 cm}

\begin{table}[H]
	{\small
		\caption{This table presents the previous results in a compact form so that one can check the conditions under which a player will surely win. The abbreviation ``sws'' stands for strong winning strategy.}
		\label{tbl:Conditions for the Existence of Strong Winning Strategy}
		\renewcommand{\arraystretch}{1.5}
		\begin{center}
		\begin{tabular}{c !{\vrule width 1.25 pt} c|c}
			\Xhline{4 \arrayrulewidth}
			Type of game & sws for player 1 & sws for player 2
			\\
			\Xhline{3 \arrayrulewidth}
			Canonical \& same group (classical vs. classical) & No & No
			\\
			\hline
			Canonical \& same group (quantum vs. quantum) & No & No
			\\
			\hline
			Noncanonical \& same group (classical vs. classical) & No & No
			\\
			\hline
			Noncanonical \& same group (quantum vs. quantum) & No & No
			\\
			\hline
			Canonical \& $S_{n} \leq A < B \leq U(n)$ & No & No
			\\
			\hline
			Canonical \& $S_{n} \leq B < A \leq U(n)$ & No & No
			\\
			\hline
			Noncanonical \& $B < A$ \& $S_{n} \leq A$ \& $\ket{\psi}$ invariant & Yes & No
			\\
			\hline
			Noncanonical \& $B < A$ \& $\ket{\psi}$ invariant \& $\ket{q_0} = \ket{q_A}$ & Yes & No
			\\
			\Xhline{4 \arrayrulewidth}
		\end{tabular}
		\end{center}
		\renewcommand{\arraystretch}{1.0}
	}
\end{table}

\section{Discussion and examples} \label{sec:Discussion and Examples}

In this section we discuss the implications of the previous results and devise some toy games in the form of examples to see how the method outlined in Theorem \ref{thr:NDG Noncanonical Game Different Action Group for Each Player} can be used to guarantee that player 1 surely wins. The examples will employ finite automata, which, as mentioned in
the Introduction, can be used as a powerful visual aid to enhance our understanding of the evolution of the state of the system and the progression of the game.

\begin{example} \label{xmp:A 4-Round Canonical Game with Different Groups}
	Let us consider a canonical $4$-round game on a $7$-dimensional quantum system. Let us further assume that $A = U(7)$, $B = S_{7}$, $\ket{q_0} = \ket{0}$, $\ket{q_A} = \ket{6}$, and $\ket{q_B} = \ket{0}$. Player 1 has the advantage of having a much larger group to choose from. $U(n)$ contains the $7$-dimensional quantum Fourier transform, which we denote by $F_{7}$. This is an extremely useful unitary transform with an elegant matrix representation (see \cite{Nielsen2010} for details). Its matrix representation is shown below, along with the result of its application to $\ket{0}$.
	\begin{align} \label{eq:The Quantum Fourier Transform $F_{7}$}
		F_{7}
		=
		\frac{1}{\sqrt{7}}
		\begin{bNiceMatrix}
			1 & 1 & 1 & 1 & 1 & 1 & 1 \\
			1 & \omega^{} & \omega^{2} & \omega^{3} & \omega^{4} & \omega^{5} & \omega^{6} \\
			1 & \omega^{2} & \omega^{4} & \omega^{6} & \omega^{} & \omega^{3} & \omega^{5} \\
			1 & \omega^{3} & \omega^{6} & \omega^{2} & \omega^{5} & \omega^{} & \omega^{4} \\
			1 & \omega^{4} & \omega^{} & \omega^{5} & \omega^{2} & \omega^{6} & \omega^{3} \\
			1 & \omega^{5} & \omega^{3} & \omega^{} & \omega^{6} & \omega^{4} & \omega^{2} \\
			1 & \omega^{6} & \omega^{5} & \omega^{4} & \omega^{3} & \omega^{2} & \omega^{}
		\end{bNiceMatrix}
		\quad \text{and} \quad
		\ket{\psi}
		=
		F_{7} \ket{0}
		=
		\frac{1}{\sqrt{7}}
		\begin{bNiceMatrix}
			1 \\
			1 \\
			1 \\
			1 \\
			1 \\
			1 \\
			1
		\end{bNiceMatrix} \ ,
	\end{align}
	where $\omega = e^{\frac{2 \pi i}{7}}$. Hence, player 1 can drive the system to the state $\ket{\psi} = \frac{1}{\sqrt{7}} \sum_{i = 0}^{6} \ket{i}$ during her first move by immediately applying $F_{7}$ to the initial state of the system. This particular state is invariant under $S_{n}$, so the system will remain at this state, irrespective of the second player's move.

	In the third round, player 1  makes her second and last move. If she decides to apply the composition of $T_{0, 6}$ and inverse action $F_{7}^{-1} = F_{7}^{\dagger}$, i.e., the action $T_{0, 6} F_{7}^{\dagger}$, then she will drive the system to her target state $\ket{6}$.

	However, it is quite possible that during her last move player 2 will use $T_{0, 6}$ to send the system back to the initial state $\ket{0}$, which happens to be her target state, and thus win the game.

	If, on the other hand, player 1 decides to use the identity operator $I$ as her last move, then player 2 will be unable to change the state of the system and, consequently, the system will be at state $\ket{\psi}$ prior to measurement. In this scenario player 1 fails again to win the game with probability $1.0$, having just $\frac{1}{7}$ probability to win.

	Naturally, all these are to be expected since Theorem \ref{thr:CDG Canonical Game Different Action Group for Each Player} asserts the nonexistence of a strong winning strategy. These two scenarios are graphically depicted in the automaton of Figure \ref{fig:Example 1 Automaton}.

	\begin{figure}[H]
		\centering
		\begin{tikzpicture}
			[
			scale = 1.3,
			state/.style =
			{
				circle,
				draw,
				minimum size = 1.0 cm,
				semithick,

			},
			every loop/.style = {min distance = 12 mm}
			]
			\def 360/7 {360/7}
			\node [ state, fill = GreenLighter2!20, initial, initial text = { initial state }, initial where = right, initial distance = 0.5 cm, accepting ] (q0)
			at ( {3 * cos(0 * 360/7)}, {3 * sin(0 * 360/7)} ) { $ \ket{0} $ };
			\node (t2) at ( 4.75, -0.5 ) { \& Player's 2 target };
			\node [ state ] (q1) at ( {3 * cos(1 * 360/7)}, {3 * sin(1 * 360/7)} ) { $ \ket{1} $ };
			\node [ state ] (q2) at ( {3 * cos(2 * 360/7)}, {3 * sin(2 * 360/7)} ) { $ \ket{2} $ };
			\node [ state ] (q3) at ( {3 * cos(3 * 360/7)}, {3 * sin(3 * 360/7)} ) { $ \ket{3} $ };
			\node [ state ] (q4) at ( {3 * cos(4 * 360/7)}, {3 * sin(4 * 360/7)} ) { $ \ket{4} $ };
			\node [ state ] (q5) at ( {3 * cos(5 * 360/7)}, {3 * sin(5 * 360/7)} ) { $ \ket{5} $ };
			\node [ state, fill = RedPurple!15 ] (q6) at ( {3 * cos(6 * 360/7)}, {3 * sin(6 * 360/7)} ) { $ \ket{6} $ };
			\node (t1) at ( 3.5, -2.375 ) { Player's 1 target };
			\node [ state, fill = WordBlueDark!50 ] (psi) at ( 0.0, 0.0 ) { $ \ket{\psi} $ };
			\path[->]
			(q0) edge [bend right = 25] node [ above ] { $F_{7}$ } (psi)
			(q0) edge [bend right = 25] node [ left ] { $T_{0, 6}$ } (q6)
			(q6) edge [bend right = 25] node [ right ] { $T_{0, 6}$ } (q0)
			(psi) edge [bend right = 25] node [ above ] { $F_{7}^{\dagger}$ } (q0)
			(psi) edge [out = 150, in = -150, loop] node [left] { $I, T_{i, j}$ } ();
		\end{tikzpicture}
		\caption{This automaton captures the evolution of the game studied in this example according to the two possible strategies of player 1 outlined above.}
		\label{fig:Example 1 Automaton}
	\end{figure}

\end{example}

\begin{example} \label{xmp:A 5-Round Noncanonical Game with Different Groups}
	In the previous game player 1 cannot surely win. Therefore, in order to guarantee that player 1 wins with probability $1.0$, the rules of the game must change. In particular, the asymmetry and the disadvantage for player 2 must increase. To this end, let us consider a noncanonical $5$-round game on the same $7$-dimensional quantum system, in which, again, we assume that $A = U(7)$, $B = S_{7}$, $\ket{q_0} = \ket{0}$, $\ket{q_A} = \ket{6}$, and $\ket{q_B} = \ket{0}$.

	The obvious difference in the current game is that now player 1 has a double advantage:

	\begin{enumerate}
		\item	she makes both the first and the last move, and
		\item	she has a much larger group to choose from.
	\end{enumerate}

	The same quantum Fourier transform $F_{7}$ shown in equation (\ref{eq:The Quantum Fourier Transform $F_{7}$}) of the previous example, can now pave the way to much better results.

	Specifically, the strategy $\sigma_{1} = ( F_{7}, I, \dots, I, T_{0, 6} F_{7}^{\dagger} )$ is a strong winning strategy for player 1. This strategy of player 1 drives the system to the state $\ket{\psi} = \frac{1}{\sqrt{7}} \sum_{i = 0}^{6} \ket{i}$, which is invariant under $S_{n}$. Hence, the system will remain at this state, irrespective of the second player's move.

	The critical realization here is that the system, in contrast to the previous example, is still at state $\ket{\psi}$ after player 2 has completed her moves.

	The last move is now by player 1, who can act using the operator $T_{0, 6} F_{7}^{\dagger}$ to drive the system to her target state $\ket{6}$. In this game player 1 will surely win. This winning scenario is captured by the automaton of Figure \ref{fig:Example 2 Automaton}.

	\begin{figure}[H]
		\centering
		\begin{tikzpicture}
			[
			scale = 1.3,
			state/.style =
			{
				circle,
				draw,
				minimum size = 1.0 cm,
				semithick,

			},
			every loop/.style = {min distance = 12 mm}
			]
			\def 360/7 {360/7}
			\node [ state, fill = GreenLighter2!20, initial, initial text = { initial state }, initial where = right, initial distance = 0.5 cm, accepting ] (q0)
			at ( {3 * cos(0 * 360/7)}, {3 * sin(0 * 360/7)} ) { $ \ket{0} $ };
			\node (t2) at ( 4.75, -0.5 ) { \& Player's 2 target };
			\node [ state ] (q1) at ( {3 * cos(1 * 360/7)}, {3 * sin(1 * 360/7)} ) { $ \ket{1} $ };
			\node [ state ] (q2) at ( {3 * cos(2 * 360/7)}, {3 * sin(2 * 360/7)} ) { $ \ket{2} $ };
			\node [ state ] (q3) at ( {3 * cos(3 * 360/7)}, {3 * sin(3 * 360/7)} ) { $ \ket{3} $ };
			\node [ state ] (q4) at ( {3 * cos(4 * 360/7)}, {3 * sin(4 * 360/7)} ) { $ \ket{4} $ };
			\node [ state ] (q5) at ( {3 * cos(5 * 360/7)}, {3 * sin(5 * 360/7)} ) { $ \ket{5} $ };
			\node [ state, fill = RedPurple!15 ] (q6) at ( {3 * cos(6 * 360/7)}, {3 * sin(6 * 360/7)} ) { $ \ket{6} $ };
			\node (t1) at ( 3.5, -2.375 ) { Player's 1 target };
			\node [ state, fill = WordBlueDark!50 ] (psi) at ( 0.0, 0.0 ) { $ \ket{\psi} $ };
			\path[->]
			(q0) edge [bend right = 25] node [ above ] { $F_{7}$ } (psi)
			(q0) edge [bend right = 25] node [ left ] { $T_{0, 6}$ } (q6)
			(q6) edge [bend right = 25] node [ right ] { $T_{0, 6}$ } (q0)
			(psi) edge [bend right = 25] node [ below left ] { $T_{0, 6} F_{7}^{\dagger}$ } (q6)
			(psi) edge [out = 150, in = -150, loop] node [left] { $I, T_{i, j}$ } ();
		\end{tikzpicture}
		\caption{This automaton displays the strong strong winning strategy of player 1 for the game studied in this example.}
		\label{fig:Example 2 Automaton}
	\end{figure}

\end{example}

The results and the examples above should help drive through the main point of this study, which is that the \emph{specific rules of a game are extremely important}! A slight variation can have profound consequences. It is the combination of two factors:

\begin{enumerate}
	\item	the precise sequence of moves as dictated by the rules of the game, and
	\item	the sets of admissible actions the players draw their moves from,
\end{enumerate}

that determines who wins. Quantum strategies do not a priori prevail over classical strategies. With some ingenuity one may design a game where the quantum player does not have a winning strategy against the classical player. See such an illuminating example and further comments in \cite{Anand2015}. The determining factor are the rules of the game. By carefully designing the rules of the game, the advantage of either player can be established. Alternatively, the fairness of the game can also be guaranteed. Another immediate conclusion that can be drawn is that although it is indeed possible to have quantum versions of classical games that exhibit different behavior or even entirely new traits, caution must exercised in designing the rules that will make this possible.

\section{Conclusions} \label{sec:Conclusions}

Quantum games can be used in a plethora of ``serious'' situations. For instance rolling quantum dice can be used to implement secure cryptographic protocols. In this paper we studied sequential quantum games under the assumption that the moves of the players are drawn from groups and not plain unstructured sets. The extra group structure makes possible to easily derive very general results as the those in Sections \ref{sec:Results for Canonical Games} and \ref{sec:Results for Asymmetric Games}, which, to the best of our knowledge, are stated in this generality for the first time. Although it seems a bit restrictive to focus on groups, it is consistent with the quantumness of these games. After all, quantum actions come from unitary groups.

Of course, the possibilities for quantum games are virtually endless. Many important and critical issues have to be addressed, such as to what extent the players communicate, what type of information is known to the players, if and how precisely entanglement comes into play. Indeed, the degree of knowledge of the players about the system is critical in the formation of strategies as we know from classical game theory. One of course will ask how can this be, without measuring the system? It is of course virtually impossible, but perhaps we can imagine a third party spying on the players and acquiring partial information about their strategies. This is, we believe, a very intriguing topic which we intend to pursuit in a future work.

\bibliographystyle{ieeetr}


\section{Introduction}
Scene Text Recognition(STR) refers to the text recognition of natural scene images captured by camera. Compared with traditional Optical Character Recognition(OCR) systems dedicated to high-quality document images, STR techniques are developed for the outdoor images and applied in a wider range of fields, such as street view positioning, image advertisement filtering, bill recognition, et al. Due to the randomness in the process of capturing text images in natural scenes, STR has many challenges in practical applications, including uneven lighting and focusing caused image quality degradation, complex image background, occluded and incomplete characters. Moreover, the characters themselves also have diverse font types, font sizes and colors; the text distribution is irregular, many of which are perspective, distorted or oriented. Therefore, as a complex problem, STR has been extensively studied in industry and academia.

STR is divided into regular and irregular text recognition tasks according to the text distribution. Modern technical solutions mainly include Connectionist Temporal Classification(CTC) based methods\cite{shi2016end}, attention-based encoder-decoder framework\cite{shi2018aster,yang2020holistic} and the combination of both\cite{litman2020scatter,zuo2019natural}. These methods only need word-level annotations and robust to complicated scene text images. CTC-based methods solve the problem of misalignment between the input image and the target outputs but can not leverage the contextual dependency between characters, thus it is mainly used for horizontal text recognition. Comparatively, attention mechanism is a good way to strengthen the relevance between visual and semantic features and improve the interpretability of the model, making it a suitable choice for irregular STR scenarios. The major architectures of the attention-based encoder-decoder framework include the sequence-to-sequence models which adopt 1D attention mechanism\cite{shi2018aster} or 2D attention mechanism\cite{li2019show} in the decoder, and the transformer-based models\cite{yang2020holistic,lu2019master,sheng2019nrtr}.

However, there are still shortcomings for the existing attention-based encoder-decoder framework. 1D attention methods generally use RNN layer(s) to model contextual dependencies but lose apparent information of the text\cite{shi2018aster}. Although 2D attention is able to handle the irregular spatial distribution of the text, its performance is greatly restricted by the size of the encoded feature map\cite{li2019show}. Since the inter-character dependence in STR is weaker than the inter-word dependence in machine translation, the self-attention design in transformer-based models which targets at building long-range dependencies may not achieve the expected performance\cite{yang2020holistic}, but increases the parameters due to its multiple fully-connected layers and the multi-layer stacking structure of decoder. The common reasons for these problems lie in the information loss of the global and local feature, as well as the weak relevance between the encoder working on the visual space and the decoder working on the language space.

Therefore, we propose the $\mathbf{R}$epresentation and $\mathbf{C}$orrelation $\mathbf{E}$nhanced $\mathbf{E}$ncoder-$\mathbf{D}$ecoder Framework(RCEED). The encoder generates a comprehensive representation of local visual feature and global context feature. The decoder utilizes the Multi-Head General Attention mechanism to capture an enriched glimpse of the encoded feature. The initialization manner and the efficient workflow of the decoder increase the correlation between the visual feature and the decoded characters.
Our main contributions are summarized as follows:
\\ 1. \ In the encoder module, a representation enhanced feature map is obtained by combining the visual, context and position information. The encoded feature map has a small size corresponding to the spatial distribution of characters.
\\ 2. \ In the decoder module, a holistic feature and the a global glimpse vector are introduced from the encoder to guide the initialization of the decoder. The intuitive workflow enables the glimpse vector to participate in the update of the decoded hidden state and the character prediction at the same time. These integrated designs make the model achieve SOTA performance in public benchmarks, especially the irregular ones.
\\ 3. \ We devise a Mulit-Head General Attention mechanism to capture the main information and the supplementary information of the encoded feature with fewer operations and parameters.
\\ 4. \  We specially design the LD-LSTM cell as basic block to form the RNN layers of the encoder and the decoder. The LD-LSTM can balance independence and relevance between characters and improve model's generalization for irregular texts, which is very important for the STR applications.

\section{Related Work}
Early text image recognition is oriented to the document recognition scenario which has a clear picture and a fixed pattern. People use binarization method\cite{casey1996survey} and sliding window method\cite{wang2011end} for individual character detection, and then integrate the characters into words by dynamic programming. These methods are vulnerable to the background noise, and unable to use the global context information. Later works tend to treat the text image recognition as a sequence recognition problem. These methods are more capable of the complex STR tasks and mainly divided into two categories, the CTC-based methods and the attention based methods. CRNN\cite{shi2016end} utilizes the CNN and RNN to generate feature sequence from the visual information, and CTC to align the characters predicted by the RNN decoder. Attention based encoder-decoder models like RARE\cite{shi2016robust} and $R^2AM$\cite{lee2016recursive} are developed to introduce the attention-mechanism from machine translation\cite{bahdanau2014neural} to solve the image-based sequence recognition problem. Focusing attention network\cite{cheng2017focusing} is raised to fix the attention drifting caused by complex scenes or low image quality. With similar targets, Bai et al. introduce the edit probability\cite{bai2018edit} method to alleviate character missing or superfluous in text recognition. In addition, model as a combination of CTC and attention based methods\cite{zuo2019natural} also performs well on regular scene text datasets.

In recent years, many approaches have been proposed regarding the more challenging irregular scene text recognition task. The first type is the rectification based methods. ASTER\cite{shi2018aster} combines the Thin-Plate Spline (TPS) method\cite{bookstein1993thin} and the Spatial Transformer Network(STN)\cite{jaderberg2015spatial} to form the rectification network. The line-fitting transformation method is proposed in ESIR\cite{zhan2019esir} which employs iterative rectification to improve the performance. MORAN\cite{luo2019moran} proposes a pixel transform method to make a smooth conversion to the text images. The other type is the character level methods. Models like Char-Net\cite{liu2018char} and Mask TextSpotter\cite{liao2019mask} detect and rectify the individual characters, which requires additional character-level supervision. The last type is the attention based encoder-decoder frameworks. 2D feature map is used for both the sequence-to-sequence models\cite{li2019show,yue2020robustscanner} and the transformer-based models\cite{yang2020holistic,lu2019master}. The expanded focus range contributes to the recognition of characters with arbitrary shape and position. RobustScanner\cite{yue2020robustscanner} introduces a positional enhancement branch to the 2D attentional encoder-decoder structure proposed in SAR\cite{li2019show}, leveraging the positional information to make prediction during decoding process. MASTER\cite{lu2019master} employs the non-local network as the encoder of the transformer-based structure to capture longer contextual dependencies.

\section{Model Architecture}
As presented in Figure \ref{Fig.1}, there are three important components of RCEED: the Rectification Network which redistributes the characters, the Representation Enhanced Encoder which combines the local visual feature and global context feature, the Multi-Head General Attention Decoder which increases the correlation between the visual space and the language space. Two basic composition methods are utilized in the encoder and decoder, including the LD-LSTM cell which improves model's generalization and the Multi-Head General Attention mechanism which makes effective use of main and supplementary information.
\begin{figure}
\vspace{-0.3cm}
\setlength{\belowcaptionskip}{-0.5cm}
\includegraphics[width=\textwidth]{./1_4.png}
\caption{Architecture of the RCEED. The input image is transformed by the Rectification Network before fed into the encoder. The encoder combines the visual feature from CNN, the context feature from the LD-BiLSTM layer and the position information to generate the comprehensive feature map($\mathbf{v}$). The holistic feature($h_{f}$) and the global glimpse vector($g_{f}$) from encoder are used to guide decoder initialization. At each decoding step t, the glimpse vector $g_{t}( \in \mathbf{g})$ is calculated by MHGAT based on the current hidden state $h_{t}( \in \mathbf{h})$, and exported to the next LD-LSTM iteration to generate $h_{t+1}$. Both $g_{t}$ and $h_{t}$ are used to make the current prediction.}
\label{Fig.1}
\end{figure}
\subsection{Rectification Network}
Thin-Plat Spline\cite{bookstein1993thin} is a 2D interpolation method which makes conversion with minimal bending energy based on a set of corresponding control points of two pictures. Similar to the STN in \cite{shi2018aster}, our rectification network utilizes a lightweight CNN to generate the control points of the source image, associating them with the pre-defined control points of the target image through TPS to accomplish the rectification process. We also find that the rectification network is able to adjust the width and spacing of characters adaptively, which reduces the divergence of input text images and improves the alignment between receptive fields and characters.

\subsection{Basic Composition Methods for Encoder-Decoder Framework}
In order to facilitate understanding, before the illustration of the Encoder and Decoder, we introduce two methods which are important components of them.
\subsubsection{Layernorm-Dropout LSTM Cell(LD-LSTM)}
The Long Short-Term Memory(LSTM) \cite{hochreiter1997long} is widely used in the machine translation models\cite{bahdanau2014neural}. Considering the difference between the text recognition task and the language processing task which has strong semantic dependencies between tokens, we specially design the Layernorm-Dropout LSTM Cell.

Firstly, we add layernorm\cite{ba2016layer} to the current input and the previous hidden state of the LSTM cell to speed up the convergence of training process and regularize the network. Secondly, on account of the relatively weak dependencies between characters in the text image, we introduce the dropout function\cite{hinton2012improving} to reduce feature co-adaptation and improve the presentation of important information. Different from the conventional way of applying dropout in the feed-forward connections between RNN layers\cite{zaremba2014recurrent}, we design a per-step dropout method in the recurrent connections of RNN cells. Both the hidden state and the cell state are sampled by the dropout masks with probability p to balance the relevance and independence between characters, and improve the generalization at the same time.

The layernorm operation is given by:
\begin{equation}
    LN(\mathbf{x}; \alpha ,\beta )=\frac{(\mathbf{x}-\mu )}{\sigma }\odot \alpha +\beta
\end{equation}
\begin{equation}
    \mu =\frac{1}{D}\sum_{i=1}^{D}x_{i}, \quad\sigma =\sqrt{\frac{1}{D}\sum_{i=1}^{D}(x_{i}-\mu )^{2}}
\end{equation}

Where $x_{i}$ is the $i_{th}$ element of $\mathbf{x}$ with length D. $\alpha$ and $\beta$ are defined as gain and bias parameters. In this paper, we set $\beta$ as zero. Then the LD-LSTM cell is defined as:
\begin{equation}
\label{eq_3}
\begin{pmatrix}
f_{t}\\
i_{t}\\
o_{t}\\
\hat{c}_{t}
\end{pmatrix}= LN(W_{x}x_{t}; \alpha _{1}, \beta _{1}) + LN(W_{h}h_{t-1}; \alpha _{2}, \beta _{2})
\end{equation}
\begin{equation}
c_{t} = Dropout\left (sigm(f_{t})\odot c_{t-1}+sigm(i_{t})\odot tanh(\hat{c}_{t}), \ p \right)
\end{equation}
\begin{equation}
h_{t} = Dropout\left (sigm(o_{t})\odot tanh(c_{t}), \ p \right )
\end{equation}

Where $W_x$ and $W_h$ are weight matrixes of the input $x_t$ and the hidden state $h_{t-1}$. $\odot$ denotes the element-wise product operation. $p$ is the probability of each element of the vector being zero.

\subsubsection{Multi-Head General Attention(MHGAT)}
The commonly used attention functions include general attention, additive attention, dot product attention et al. Unlike most sequence-to-sequence text recognition models which utilize additive attention mechanism to build connection between encoder and decoder\cite{shi2018aster,litman2020scatter,li2019show}, we use general function\cite{luong2015effective} to reduce the computational complexity. Compared with additive attention\cite{bahdanau2014neural} which needs two-step operations to obtain the attention weights(add first and then multiply by the transform matrix), general attention only needs one-step matrix multiplication operation(Equation (\ref{eq_6})). Given $\mathbf{v^{'}}$=[$v_{1}^{'}, v_{2}^{'},...,v_{N}^{'}$] as a splitted part of the flattened comprehensive feature map $\mathbf{v}$ with length N, the formulation of the general attention mechanism for $\mathbf{v^{'}}$ can be expressed as follows:
\begin{equation}
\label{eq_6}
   score(h_{t}^{'}, \mathbf{v^{'}}) = \frac{\mathbf{v}W_{a}^{'}h_{t}^{'}}{d_{v^{'}}^{2}}
\end{equation}
\begin{equation}
\mathbf{a_{t}^{'}}=softmax(score(h_{t}^{'}, \mathbf{v^{'}})) \in \mathbb{R}^{N}
\end{equation}
\begin{equation}
GeneralAttention(h_{t}^{'}, \mathbf{v^{'}}) = \sum_{i=1}^{N}a_{t,i}^{'}v_{i}^{'}
\end{equation}

Where $a_{t,i}^{'}$ is the $i_{th}$ element of the attention weights $\mathbf{a_{t}^{'}}$. $W_{a}^{'}\in \mathbb{R}^{d_{v}\times d_{v^{'}}}$ is a parameter matrix with $d_{v}$ and $d_{v^{'}}$ representing the dimensions of $\mathbf{v}$ and $\mathbf{v^{'}}$. In order to build a harder attention module to suppress the background noise, we set the a relatively large scale factor, which is  $d_{v^{'}}^{2}$ under 8 parallel heads.

Due to the diversity of character size and distribution, there is misalignment between the feature map obtained after CNN downsampling and the character visual information. Therefore, we adopt the multi-head attention(shown in Figure \ref{Fig.4}(a)) to increase the attention flexibility and reduce information loss. Given the hidden state $h_{t}$ at time step t as a query, the Multi-Head General Attention for $\mathbf{v}$ is generated by:
\begin{equation}
    g_{t}=MultiHead(h_{t}, \mathbf{v}) = Concat(head_{1},...,head_{m})
\end{equation}
\begin{equation}
where \ head_{j} = GeneralAttention(h_{t}W_{h,j}, \mathbf{v_{j}}), \ \mathbf{v_{j}} \in Split(\mathbf{v}, m) \notag
\end{equation}

The parameters are $W_{h,j} \in  \mathbb{R}^{d\times \frac{d_{v}}{m}}$, where $d$ denotes the dimension of $h_{t}$, m is the number of parallel heads. $\mathbf{v_{j}}$ is obtained by splitting m times along $d_{v}$. $g_{t}$ as a concatenation of the attention heads refers to the "glimpse" of the encoded feature where the current step attends to. Figure \ref{Fig.2} visualizes the 8-heads attention maps at each decoding step. Head 8 and head 4 are respectively in charge of the main and the supplementary attention tasks, and accurately aligned with the target characters.
\begin{figure}
\centering
\includegraphics[width=\textwidth]{./4_1.png}
\caption{Visualization of the 8-heads attention map at each decoding step. Head 8 is in charge of the main information and completely aligned with the decoded characters. Head 4 pays attention to the supplementary information around the target area.}
\label{Fig.2}
\end{figure}

\subsection{Representation Enhanced Encoder}
The encoder of RCEED consists of two parts: the Resnet[18] based CNN backbone(presented in Table \ref{tab1}) which extracts local visual feature, and the single-layer LD-BiLSTM which outputs global context feature. Limited by the receptive field, the CNN encoder can not well represent the contextual information. Therefore, BiLSTM\cite{hochreiter1997long} layer with the LD-LSTM Cell as block(abbreviated as LD-BiLSTM) is utilized to generate the context feature sequence, which is based on the intermediate feature sequence produced by average pooling on the visual feature column vectors. The final hidden state is taken as the holistic feature.

However, due to the abstractness of the LD-BiLSTM operation, the complex shape and spatial information of the text is lost. Thus, as shown in Figure \ref{Fig.3}, we add the context feature sequence and the corresponding visual feature column vectors along the row axis, getting the comprehensive feature representation.
\begin{table}[]
\caption{The configuration of the ResNet based CNN feature extractor. The stride and padding for the convolutional layers are all set to 1. The 'k' and 's' in the max-pooling layers refer to kernel size and stride. Height and width of the output of each layer are presented in the last column.}
\label{tab1}
\centering
\begin{tabular}{c|c|c}
\hline
\textbf{Layer} & \textbf{\quad Configuration \quad} & \textbf{\quad Output \quad} \\ \hline
Conv           & $3\times 3, \ 64$                      & $48\times 160$               \\
Conv           & $3\times 3, \ 128$                      & $48\times 160$               \\
Max-pooling    & $k:2\times 2, \ s:2\times 2$                      & $24\times 80$               \\
Residual block \quad \quad & $\begin{bmatrix}
\ 3\times 3, \ 256 \ \\
\ 3\times 3, \ 256 \
\end{bmatrix} \ \times  \ 1$                      & $24\times 80$               \\
Conv           & $3\times 3, \ 256$                       & $24\times 80$               \\
Max-pooling    & $k:2\times 2, \ s:2\times 2$                      & $12\times 40$               \\
Residual block & $\begin{bmatrix}
\ 3\times 3, \ 256 \ \\
\ 3\times 3, \ 256 \
\end{bmatrix} \ \times  \ 2$                      &  $12\times 40$              \\
Conv           & $3\times 3, \ 256$                      & $12\times 40$               \\
Max-pooling    & $k:2\times 2, \ s:2\times 2$                      & $6\times 20$               \\
Residual block & $\begin{bmatrix}
\ 3\times 3, \ 512 \ \\
\ 3\times 3, \ 512 \
\end{bmatrix} \ \times  \ 5$                      & $6\times 20$               \\
Conv           & $3\times 3, \ 512$                      & $6\times 20$               \\
Max-pooling    & $k:2\times 2, \ s:[2,1]\times [2,1]$                      & $3\times 20$               \\
Residual block & $\begin{bmatrix}
\ 3\times 3, \ 512 \ \\
\ 3\times 3, \ 512 \
\end{bmatrix} \ \times  \ 3$                      & $3\times 20$               \\
Conv           & $3\times 3, \ 512$                      & $3\times 20$               \\ \hline
\end{tabular}
\end{table}

\begin{figure}
\centering
\includegraphics[width=0.6\textwidth]{./2.png}
\caption{Structure of the Representation Enhanced Encoder. The intermediate feature sequence is obtained by applying average pooling on the visual feature column vectors. After the column-aligned addition between the visual feature and the context feature, as well as the positional encoding operation, a comprehensive feature map is generated.}
\label{Fig.3}
\end{figure}

Since the character position distribution along the vertical direction is mainly divided into three parts: upper, middle, and lower. Meanwhile, for the sake of reducing computational consumption, we set the feature map size as 3$\times$20, where 3 corresponds to the 3 types vertical position. Compared with \cite{li2019show,lu2019master,yue2020robustscanner}, our feature map size is only a quarter of theirs. Similar to \cite{vaswani2017attention}, we consider the influence of position information and use sinusoid function to encode absolute as well as relative position information to the comprehensive feature map.

\subsection{Recurrent Multi-Head General Attention Decoder}
As shown in Figure \ref{Fig.4}(b), the decoder is built on a sequence-to-sequence architecture with the LD-LSTM cell and the Multi-Head General Attention as basic blocks. Before the decoding starts, given the flattened comprehensive feature map $\mathbf{v}$ and the holistic feature $h_{f}$ from the encoder as inputs, a global glimpse vector $g_{f}$ related to $h_{f}$ is derived from MHGAT. $h_{f}$ and $g_{f}$ represent the global information of the encoded feature map and serve as the guidance for the initialization of decoder, which helps to focus on the explicit part at the first decoding step and improve the accuracy. Then, the LD-LSTM operation is performed fed with $g_{f}$, $h_{f}$, and a start token $y_{s}$. Note that the LD-LSTM is slightly changed in the decoder, the word embedding of the start token and sequential outputs $\mathbf{y}=[y_{s}, y_{1},...,y_{T-1}]$ is added to Equation (\ref{eq_3}).
\begin{equation}
(h_{t}, c_{t})=\left\{\begin{array}{l}
LD-LSTM(g_{f}, h_{f}, y_{s}) \qquad \quad \ \  t=1\\
LD-LSTM(g_{t-1}, h_{t-1}, y_{t-1}) \quad t>1
\end{array}\right.
\end{equation}

Next, the Multi-Head General Attention mechanism is performed to generate the glimpse vector related to the current hidden state $h_{t}$.
\begin{equation}
g_{t} = MultiHead(h_{t}, \mathbf{v})
\end{equation}

Finally, the predicted character is calculated by:
\begin{equation}
y_{t} = \phi(h_{t},g_{t}) = argmax(softmax(W_{o}[h_{t};g_{t}] + b_{o}))
\end{equation}

The hidden state $h_{t}$ and current glimpse vector $g_{t}$ are concatenated and passed through the linear transformation to make the final prediction to 63 classes, including 10 digits, 52 case sensitive letters and the 'EOS' token. Then the hidden state, cell state and glimpse vector are recovered and passed to the next step. The decoder works iteratively until the 'EOS' token is predicted or the maximum time step T is arrived.

Attention based sequence-to-sequence models\cite{shi2018aster,litman2020scatter,liao2019mask} generally use the decoding workflow based on \cite{bahdanau2014neural}, which is $h_{t-1}\rightarrow \mathbf{a_{t}} \rightarrow g_{t}\rightarrow h_{t}$, where the glimpse vector $g_{t}$ is related to the last time step and cannot be directly used for the current prediction. On the other hand, the workflow of RCEED is more intuitive, which is $(h_{t-1},g_{t-1})\rightarrow h_{t}\rightarrow \mathbf{a_{t}} \rightarrow g_{t}$. The decoding workflow of SAR\cite{li2019show} is comparable to us. Nevertheless, the first round RNN iteration of SAR does not make predictions, and its glimpse vector is not utilized in the RNN calculation. In our design, $\mathbf{g}$ as representation of a certain part of the encoded feature directly participates in the recurrent iteration of $\mathbf{h}$ and the character prediction. Therefore, a content enriched expression is obtained and the correlation between the visual feature and the character sequence is enhanced.
\begin{figure}
\vspace{-0.2cm}
\setlength{\belowcaptionskip}{-0.6cm}
\centering
\includegraphics[width=\textwidth]{./3.png}
\caption{(a) Structure of the Multi-Head General Attention.  (b) Structure of the  Recurrent Multi-Head General Attention Decoder. When decoding starts, the holistic feature $h_{f}$ and global glimpse vector $g_{f}$ from encoder are input to the LD-LSTM cell together with the start token $y_{s}$ to get the hidden state $h_{1}$. $h_{1}$ and its related glimpse vector $g_{1}$ are both used to make the first prediction. Then decoding iteration continues based on the previous outputs until the 'EOS' token is predicted.}
\label{Fig.4}
\end{figure}
\section{Experiments}
\subsection{Datasets}
We train our RCEED on part of the two synthetic datasets: MJSynth and SynthText, and the training sets of the four scene text datasets, i.e., IIIT5K, ICDAR2013, SVT, ICDAR2015. Evaluation results are based on the six standard benchmarks, including three regular datasets and three irregular datasets.

\textbf{MJSynth}(MJ)\cite{jaderberg2014synthetic} is also named Synth90k. MJ has 9 million synthetic images of english words, each of them is annotated with a word-level ground truth. We use 4.8 million images from MJ for training.

\textbf{SynthText}(ST)\cite{gupta2016synthetic} is another synthetic dataset which is widely used in text detection and recognition. We crop the word patches from the background images and random select 4.8 million out of 7 million word images for training.

\textbf{IIIT5K}\cite{mishra2012scene} is a natural scene text dataset cropped from the Google search images. It is divided into 2000 training and 3000 testing images.

\textbf{SVT}\cite{wang2011end} consists of 257 training and 647 testing data cropped from the Google Street View images. SVT is challenging for the blur or noise interference.

\textbf{ICDAR2013}\cite{karatzas2013icdar} contains 848 images for training and 1095 images for evaluation. We filter out the images that only contain the non-alphanumeric characters, resulting in a test set with 1078 images.

\textbf{ICDAR2015}\cite{karatzas2015icdar} has 4468 word patches for training and 2077 for testing. IC15 is a benchmark dataset for irregular scene text recognition. The images are captured from the Google Glasses under arbitrary angles. Therefore, most words are irregular and have a changeable perspective.

\textbf{SVT-Perspective}(SVTP)\cite{phan2013recognizing} has 645 cropped scent text images for testing. It is also from the Google Street View but has more perspective words than SVT.

\textbf{CUTE80} (CUTE)\cite{risnumawan2014robust} consists of 288 word patches. CUTE is widely used for STR model evaluation for various curved text images.

\subsection{Implementation Details}
We build our model on the Tensorflow framework. All experiments are conducted on 2 NVIIDA Titan X GPUs with 12GB memory. The training dataset consists of 4.8 million from MJ, 4.8 million from ST, and 50k from the mixed training sets of IIIT5K, IC13, IC15 and SVT. Data augmentation methods such as perspective distortion and color transformation are applied to the mixed real datasets. The batch size is set to 42, including 20 from the MJ, 20 from the ST and 2 from the mixed dataset. The training process only needs 2.2 epochs in total with word-level annotation. Adam is utilized for optimization, with the addition of cross-entropy loss and l2 regularization loss(with the coefficient of 1e-4) as the objective function. Learning rate is set to 1e-4 per GPU, and reduced to 1e-5 in the last 0.2 epoch.

The input size of our model is $48\times160$. Height is fixed, if the image width is shorter than target width after resize with the original scale, we apply the padding operation, else we change the scale and simply reshape the image to the target size. The LD-BiLSTM in the encoder and LD-LSTM in the decoder are both single-layer, with the dropout rate of 0.1 and 0.5 respectively. The dimensions of the visual feature/context feature/decoded hidden state/word embedding matrix are set to 512/512/512/256. The maximum time step T is 27.

At the inference stage, no lexicon is used. For the sake of efficiency, we simply rotate 90 degree clockwise for the images of which the height is larger than 2 times of the width, instead of applying two directions rotation as previous studies\cite{shi2018aster,litman2020scatter,li2019show,lu2019master,yue2020robustscanner}. Besides, unlike\cite{shi2018aster,li2019show}, we do not use the beam search method to improve the performance. The decoder works in the forward direction, rather than the bidirectional strategy which is adopted in\cite{shi2018aster,yang2020holistic}.

\begin{table}[]
\vspace{-0.3cm}
\caption{Recognition accuracy of our method and other sate-of-the-art methods on the six public datasets. All the results listed are lexicon free. The approaches which need character-level annotations are marked *. In each column, the best performance is shown in $\mathbf{bold}$ font, and the second best result is  \underline{underlined}. Our model achieves the best accuracy in regular dataset SVT and the most challenging irregular dataset IC15, the second highest accuracy in regular dataset IC13 and curve dataset CUTE.}
\label{tab2}
\centering
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
\multirow{2}{*}{\textbf{Method}} & \multicolumn{3}{c|}{\textbf{Regular Text}}     & \multicolumn{3}{c|}{\textbf{Irregular Text}}  \\ \cline{2-7}
                                 & \textbf{IIIT5K} & \ \textbf{SVT} \  & \ \textbf{IC13} \  & \ \textbf{IC15} \ &  \ \textbf{SVTP} \ &  \ \textbf{CUTE} \ \\ \hline
CRNN(2015)\cite{shi2016end}                     &   81.2           &  82.7          &  89.6         & -             & -             & -             \\
$R^2AM$(2016)\cite{lee2016recursive}         & 78.4            & 80.7         & 90.0          &  -          & -         &  -          \\
RARE(2016)\cite{shi2016robust}         & 81.9            & 81.9         & 88.6          &  -          & -         &  -          \\
FAN(2017)\cite{cheng2017focusing}*                    & 87.4            & 85.9         & 93.3          &  70.6          & -         &  -          \\
NRTR(2017)\cite{sheng2019nrtr}                     & 86.5            & 88.3         &  \underline{94.7}          & -             & -             & -             \\
EP(2018)\cite{bai2018edit}*         & 88.3            & 87.5         & 94.4          &  73.9          & -         &  -          \\
ESIR(2018)\cite{zhan2019esir}                    & 93.3            & 90.2         & 91.3          & 76.9          & 79.6          & 83.3          \\
Char-Net(2018)\cite{liu2018char}*                 & 92.0            & 85.5         & 91.1          & 74.2          & 78.9          & -             \\
Mask TextSpotter(2018)\cite{liao2019mask}*         & \underline{95.3}           & $\mathbf{91.8}$         & $\mathbf{95.3}$          & 78.2          & 83.6          & 88.5          \\
ASTER(2018)\cite{shi2018aster}                     & 93.4            & 89.5         & 91.8          & 76.1          & 78.5          & 79.5          \\
ZOU, L et al.(2019)\cite{zuo2019natural}        & 85.4            & 84.5         & 91.0          &  -          & -         &  -          \\
MORAN(2019)\cite{luo2019moran}                   & 91.2            & 88.3         & 92.4          &  68.8          & 76.1         &  77.4          \\
MASTER(2019)\cite{lu2019master}                   & 95.0            & 90.6         & $\mathbf{95.3}$         & 79.4          & \underline{84.5}          & 87.5          \\
SCATTER(2020)\cite{litman2020scatter}                & 92.9            & 89.2         & 93.8          & \underline{81.8}          & \underline{84.5}          & 85.1          \\
Yang, L et al.(2020)\cite{yang2020holistic}            & 94.7            & 88.9         & 93.2          & 74.0          & 80.9          & 85.4          \\ \hline
$\mathbf{SAR(2019)}$\cite{li2019show}      & 95.0            & \underline{91.2}         & 94.0          & 78.8          & $\mathbf{86.4}$          & 89.6          \\
$\mathbf{SAR \ 3\times20}$    &94.0      &90.6      &93.1      &76.2     &83.7      &87.5     \\
$\mathbf{RobustScanner(2020)}$\cite{yue2020robustscanner}         & $\mathbf{95.4}$            & 89.3         & 94.1          & 79.2          & 82.9          & $\mathbf{92.4}$          \\ \hline
$\mathbf{RCEED(Ours)}$                       & 94.9                & $\mathbf{91.8}$             & \underline{94.7}              &  $\mathbf{82.2}$             &  83.6             &  \underline{91.7}             \\ \hline
\end{tabular}
\end{table}
\vspace{-0.5cm}

\subsection{Experimental Results}
In this section, we test the model performance on regular and irregular STR public datasets, and make comparison with the SOTA methods. As shown in Table \ref{tab2}, RCEED achieves the best performance in regular dataset SVT and irregular dataset IC15, and the second highest accuracy in regular dataset IC13 and curve dataset CUTE. Compared with competitors SAR\cite{li2019show} and RobustScanner\cite{yue2020robustscanner} which are baseline and up-to-date methods targeting at irregular scene text recognition and trained with synth\&real datasets, RCEED performs accuracy increases of 3pp to 3.4pp in the most challenging irregular dataset IC15 and outperforms them by 4 out of 6 benchmarks, while the size of the encoded feature map is only 1/4 of theirs. Compared with SAR modeled with the same-size encoded feature map(SAR 3$\times$20), our model outperforms it in 5 benchmarks with 6pp ahead in maximum. Experimental results demonstrate that RCEED has got rid of the performance bottleneck caused by small-size feature map, and is competitive in both the regular and the irregular datasets.

Figure \ref{Fig.5} shows the success and failure cases of RCEED. Success cases in the first row demonstrate that the proposed model has a robust ability to deal with blur, variation, occlusion, distortion, uneven light and other difficult situations. However, when the problems become serious, failure cases such as over-prediction and less-prediction appear. It can be seen that image quality still has a significant impact on the recognition results.

\begin{figure}
\vspace{-0.3cm}
\setlength{\belowcaptionskip}{-0.5cm}
\centering
\includegraphics[width=\textwidth]{./5.png}
\caption{Success and failure cases of RCEED. GT refers to the ground truth, Pred refers to the predicted results. }
\label{Fig.5}
\end{figure}

\subsection{Ablation Studies}
In this section, we conduct a series of comparison experiments to analyse the effectiveness of the key contributions in RCEED. Evaluation results of 8 conditions are listed in Table \ref{tab3}.

\noindent\textbf{Impact of comprehensive feature} \quad
We evaluate the performance when visual feature and context feature are used alone as the input of the decoder. As shown in Row 2 and 3, single visual and single context features both have lower accuracy of up to -1.6pp on the regular dataset and -2.8pp on the irregular dataset compared with the comprehensive feature, indicating that the feature fusion operation plays an important role in improving model performance.

\noindent \textbf{Impact of Layernorm-Dropout LSTM Cell} \quad
Row 1 reveals the model performance when the LD-LSTM design in the encoder and decoder are both replaced with normal LSTM cells. Compared with Row 8, the model implemented with normal LSTM cells shows an accuracy drop of -1.3pp on the largest irregular dataset IC15. While in the largest regular dataset IIIT5K, the accuracy is 0.6pp higher and equals to the best performance\cite{yue2020robustscanner}. The dropout design in the LD-LSTM improves model's ability in dealing with changeable characters, but is not compatible with regular texts with stable features. Overall, LD-LSTM cell still outperforms the normal one in most benchmarks.

\noindent \textbf{Impact of guided initialization of decoder} \quad
Row 4 lists the results when the decoder is initialized with zero vectors instead of the holistic feature and global glimpse vector from the encoder. Accuracy shows a drop up to -1.6pp in the five out of six public datasets, which demonstrates that the global information from the encoder is helpful for improving the decoding accuracy.

\noindent \textbf{Impact of glimpse vector for prediction} \quad
We build a comparison model which does not use glimpse vector for prediction. As shown in Row 5, the performance degradation is more serious in irregular datasets(up to -1.8pp), proving that visual information has a greater impact on recognizing complex texts.

\noindent\textbf{Impact of heads number} \quad
We compare the evaluation results when attention heads number m is set to 1, 4 and 8 in Row 6, 7, 8. The 1 head condition is equivalent to not using the multi-head design. We set m=8 in our model for the superior performance on irregular datasets.

\begin{table}[]
\vspace{-0.3cm}
\caption{Ablation studies by changing model structures and hyper-parameters.  LD refers to models w/o the Layernorm-Dropout method in the RNN layers. VF/CF denote whether the Visual Feature and Context Feature are involved in the encoded feature map. GI/GP analyze the impact of the Guided Initialization of decoder and the Glimpse vector for Prediction. Heads column presents the conditions with different number of heads. All the comparison models are trained from scratch with word-level annotations.}
\label{tab3}
\centering
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
\textbf{Cond} & \textbf{LD} & \textbf{VF} & \textbf{CF} & \textbf{GI} & \textbf{GP} & \textbf{Heads} & \textbf{IIIT5K} & \textbf{SVT} & \textbf{IC13} & \textbf{IC15} & \textbf{SVTP} & \textbf{CUTE} \\ \hline
1             & $\times$                & $\checkmark$    & $\checkmark$       & $\checkmark$           & $\checkmark$          & 8              & 95.4            & 91.5         & 94.7          & 80.9          & 84.9          & 89.9          \\
2             & $\checkmark$        & $\times$      & $\checkmark$   & $\checkmark$        & $\checkmark$          & 8              & 94.7            & 90.9         & 93.1        & 80.0            & 82.6          & 88.9          \\
3             & $\checkmark$        & $\checkmark$       & $\times$    & $\checkmark$       & $\checkmark$          & 8              & 94.9            & 91.6         & 93.7          & 80.4          & 82.8          & 90.3          \\
4       & $\checkmark$        & $\checkmark$        & $\checkmark$     & $\times$      &$\checkmark$           & 8              & 95.3            & 90.9         & 94.6          & 80.6          & 83.3          & 90.6          \\
5             & $\checkmark$        & $\checkmark$        & $\checkmark$     & $\checkmark$      & $\times$          & 8              & 94.9            & 92.6         & 94.3          & 80.9          & 82.9          & 89.9          \\
6             & $\checkmark$      & $\checkmark$       & $\checkmark$    & $\checkmark$       & $\checkmark$          & 1              &94.3                 &91.6              & 94.3              &  80.8             & 83.6              & 91.7              \\
7     & $\checkmark$      & $\checkmark$   & $\checkmark$     & $\checkmark$      & $\checkmark$          & 4              & 95.0              & 92.4         & 94.1          & 81.1          & 83.7          & 89.5          \\  \hline
8    & $\checkmark$      & $\checkmark$      & $\checkmark$  & $\checkmark$   & $\checkmark$          & 8             & 94.9            & 91.8       & 94.7          & 82.2         & 83.6         & 91.7        \\ \hline
\end{tabular}
\end{table}
\vspace{-0.5cm}

\section{Conclusion}
In this work, we propose a representation and correlation enhanced encoder-decoder framework for scene text recognition. The encoder enhances model's representation ability through the aligning and fusing operation between the local visual feature and the global context feature. The decoder strengthens the correlation between the encoded comprehensive feature and the decoded character sequence through the guided initialization and the efficient workflow. Essential components including the Multi-Head General Attention mechanism and the LD-LSTM cell are designed to reduce feature deficiency and improve the generalization towards changeable texts. The model breaks the constraint of feature map size and has a superior performance on public benchmarks. In future research, we will develop an end-to-end integrated detection and recognition model for the text spotting task and develop advanced applications of the visual-semantic interaction.

\section{Acknowledgments}
This work is supported by National Natural Science Foundation of China (61976214, 61721004, 61633021), and Science and Technology Project of SGCC Research on feature recognition and prediction of typical ice and wind disaster for transmission lines based on small sample machine learning method.
\vspace{1cm}

\bibliographystyle{unsrt}