The Connection between the PQ Penny Flip Game and the Dihedral Groups

Abstract

This paper is inspired by the PQ penny flip game. It employs group-theoretic concepts to study the original game and its possible extensions. In this paper, it is shown that the PQ penny flip game can be associated, in a precise way, with the dihedral group $D_8$ and that within $D_8$ there exist precisely two classes of equivalent winning strategies for Q. This is achieved by proving that there are exactly two different sequences of states that can guarantee Q’s win with probability $1.0$. It is demonstrated that the game can be played in every dihedral group $D_{8n}$, where $n\ge 1$, without any significant change. A formal examination of what happens when Q can draw their moves from the entire $U\left(2\right)$, leads to the conclusion that, again, there are exactly two classes of winning strategies for Q, each class containing an infinite number of equivalent strategies, but all of them sending the coin through the same sequence of states as before. Finally, when general extensions of the game, with the quantum player having $U\left(2\right)$ at their disposal, are considered, a necessary and sufficient condition for Q to surely win against Picard is established: Q must make both the first and the last move in the game.

1. Introduction

It is rather unnecessary to stress the importance of game theory. It has been extensively used for decades now to help researchers and practitioners make sense of situations involving conflict, competition, and cooperation. The abstraction of players who antagonize each other in a specified framework by devising elaborate strategies has been employed in the fields of economics, political and social sciences, biology, and, naturally, computer science. Game theorists have developed an enormous technical machinery for the quantitative assessment of the players’ strategies and their pay-offs. Of particular significance is the assumption that the players are rational, which means that they seek to maximize their pay-offs. In this paper, only very basic and easy to grasp notions from game theory are used. These can be found in all standard textbooks, such as [1,2,3]. The emergence of the quantum era in information and computation also brought about the creation of the field of quantum game theory. This recent field is devoted to the study of classical games in the quantum setting, giving an exciting new perspective and results that are beyond the grasp of the classical realm.

1.1. Related Work

The year 1999 was an important milestone for the creation of the field of quantum games. In that year, two influential works were published. In a seminal paper Meyer [4] introduced the PQ penny flip game, which can be considered the quantum analogue of the classical penny flip game. The other influential work from 1999 was by Eisert et al. in [5]. There the authors presented a novel technique, known now as the Eisert–Wilkens–Lewenstein protocol, that has gained wide acceptance in the field.

In Meyer’s PQ penny flip game, the two players are the famous tv characters Picard and Q from the TV series Star Trek. They consecutively “toss” a quantum coin and if at the end of the game the coin is found heads up Q wins, otherwise Picard wins. There is a metaphor behind the two players: Picard represents the classical player and Q the quantum player. For Picard the game is perceived as the classical penny flip game, but for Q the quantumness of the coin is evident and can be exploited to their advantage. Meyer demonstrated that Q can always win with probability $1.0$ by employing the Hadamard operator. Afterwards, many researchers generalized this game to n-dimensional quantum systems. Important results in this direction were obtained by [6,7,8]. These results indicated that under a specific set of rules, the quantum player does have an advantage over the classical player. Nonetheless, this need not always hold as the authors in [9] pointed out. There, it was shown that if the the rules of the PQ penny flip game are appropriately modified, it is even possible that Picard may win the game. Another related problem, namely that of quantum gambling based on the Nash-equilibrium was examined in [10]. The association of every finite variant of the PQ penny flip game with finite automata, so that strategies are words accepted by the corresponding automaton, was established in [11]. In that work, the underlying assumption was that Q will always use the Hadamard operator. The present paper is also focused on the PQ penny flip game and its possible extensions, but this time without any limitations, as Q is free to choose their moves from the entire $U\left(2\right)$.

With respect to the Eisert–Wilkens–Lewenstein scheme, many important results have been obtained. Several quantum adaptations of the famous prisoners’ dilemma have been defined and studied, giving quantum strategies that are better than any classical strategy ([5]). Some recent results were presented in [12], where the correspondence of typical conditional strategies, used in the classical repeated prisoners’ dilemma game, to languages accepted by quantum automata was established, and in [13], where the Eisert–Wilkens–Lewenstein scheme was extended. Quantum games, especially coin tossing, have also been fruitfully utilized in many quantum cryptographic protocols. In such a setting, Alice and Bob assume the role of remote parties that, despite not trusting each other, have to agree on a random bit (see [14] and references therein). This has been extended in [15] to quantum dice rolling when multiple outcomes and parties are involved. In a different but quite similar line of thought, Parrondo games were studied via quantum lattice gas automata in [16] and in [17] it was shown that quantum automata accepting infinite words can capture winning strategies for abstract quantum games. Recently, abstract sequential quantum games were investigated in [18]. Games have been cast not only in a quantum setting, but also in a biological setting. Some well-known classical games, such as the prisoners’ dilemma, can be expressed via biological and bio-inspired concepts (see [19,20,21] for more references).

1.2. Contribution

This paper is inspired by previous research on the PQ penny flip game. Its novelty lies in the use of group-theoretic concepts to study the original game and its possible extensions. It is shown for the first time that the original PQ penny flip game can be associated in a precise way with the dihedral group $D_8$. Interpreting the game in terms of stabilizers and fixed sets, which are basic and helpful group notions, facilitates the explanation and replication of Q’s strategy. Within $D_8$ there exist precisely two classes of winning strategies for Q. Each class contains many different strategies, but all these strategies are equivalent in the sense that they drive the coin through the same sequence of states. It is proven for the first time in the literature that there are precisely two different sequences of states that can guarantee Q’s win with probability $1.0$. Subsequently, it is demonstrated that the same game can be played in the all dihedral groups $D_{8n}$, $n\ge 1$, without any significant change in the winning strategies of Q. Thus, the smallest group that captures the essence of the game is $D_8$. The most general setting, where Q can draw their moves from the entire $U\left(2\right)$, is examined next. The definitive answer is that, perhaps surprisingly, the situation remains the same. Again, there are exactly two classes of winning strategies for Q, each class containing now an infinite number of equivalent strategies, but all of them send the coin through the same sequence of states as before. Ultimately, the original PQ penny flip game can be succinctly summarized by saying that there are precisely two paths of states that lead to Q’s win and, of course, no path that leads to Picard’s win. Finally, general extensions of the game in which Q has $U\left(2\right)$ at their disposal, are studied. Their examination uncovers a very important fact: for Q to surely win against the classical player the tremendous advantage of available quantum actions is not enough; he must also make both the first and last move, or else he is not certain to win.

1.3. Organization

The paper is structured as follows. Section 1 sets the stage and gives the most relevant references. Section 2 introduces the notation and terminology used in this article. Section 3 proves the connection of the game with the dihedral group $D_8$ and Section 4 analyzes Q’s strategy in terms of group concepts. Section 5 and Section 5 analyze the characteristics and the possible extensions of the game in larger groups. A thorough discussion and evaluation of the results can be found in Section 7 and, finally, Section 8 provides a summary of the current work and sketches some ideas for future work.

2. Background

2.1. The $PQ$ Penny Flip Game

In what is now regarded as a landmark paper [4], Meyer defined the penny flip game between the famous television personas Picard and Q from the TV series Star Trek. From now on, for brevity, the Picard–Q game is referred to as the $PQG$. This game is much more than a coin flipping game; its importance lies in the fact that it demonstrates the advantage of quantum strategies over classical strategies. The human player, Picard, can only employ classical strategies, while the quantum player, Q, is capable of using quantum strategies. This asymmetry is the reason why, no matter what Picard does, Q always wins with probability $1.0$. Picard is confined to just the two classical moves available in a 2-dimensional system: he can either do nothing, or he can flip the coin. Doing nothing means that the coin remains in its current state, while flipping the coin changes its state from heads to tails or vice versa. Q’s advantage stems from the fact that he can potentially choose from an infinite pool of allowable moves; the only obvious restriction being that their move must be represented by a unitary operator. The game begins with the coin heads up and the two players act on the coin following a predetermined order. Q acts first, then Picard and last Q again. If, after Q’s last action, the coin is found heads up, then Q wins. If the coin is found tails up, then Picard wins.

In the context of the $PQG$ and its extensions, it is convenient to employ the terminology outlined in Definition 1, adapted from [1,3]. Informally, the word strategy implies a rational plan on behalf of each player. This plan ultimately consists of actions, or moves that the player makes as the game evolves.

Definition 1

(Winning and dominant strategies).

• A strategy is a function that associates an admissible action to every round that the player makes a move. It is convenient to represent strategies as finite sequences of moves from the player’s repertoire;
• A strategy ${\sigma }_P$ for Picard is a winning strategy if for every strategy ${\sigma }_Q$ of Q, Picard wins the game with probability $1.0$;
• Symmetrically, a strategy ${\sigma }_Q$ for Q is a winning strategy if for every strategy ${\sigma }_P$ of Picard, Q wins the game with probability $1.0$;
• A strategy for Picard or Q is dominated if there exists another strategy that has greater probability to win for every strategy of the other player. A strategy that dominates all other strategies is called dominant.

Of course, in the original $PQG$, Picard’s strategy is just one move, e.g., $\left(F\right)$. Q’s strategy on the other hand is a sequence of two moves: $(H,H)$. Moreover, a winning strategy for Q is also a dominant strategy. Meyer proved that the use of the Hadamard operator constitutes a winning strategy for Q. If Q uses the Hadamard operator, he will win with probability $1.0$, irrespective of Picard’s moves. In technical terms, the game takes place in the 2-dimensional complex Hilbert space ${\mathcal{H}}_2$. The computational basis of ${\mathcal{H}}_2$ is denoted by B and consists of the kets $|0\rangle =\left[\begin{array}{c}1\\ 0\end{array}\right]$ and $|1\rangle =\left[\begin{array}{c}0\\ 1\end{array}\right]$:

$$\begin{array}{c}\hfill B=\{|0\rangle ,|1\rangle \}.\end{array}$$

(1)

Typically, $|0\rangle$ and $|1\rangle$ capture the state of the coin being heads up or tails up, respectively. Picard’s moves do nothing and flip the coin correspond to the identity I and the flip operator F, respectively. As already mentioned, Q’s winning strategy is the Hadamard operator H. In ${\mathcal{H}}_2$ the players’ moves are represented by the following $2\times 2$ matrices:

$$I=\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right],F=\left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right],\mathrm{and}H=\left[\begin{array}{cc}\frac{\sqrt{2}}{2}\hfill & \hfill \frac{\sqrt{2}}{2}\\ \frac{\sqrt{2}}{2}\hfill & \hfill -\frac{\sqrt{2}}{2}\end{array}\right].$$

(2)

F is, of course, one of the famous Pauli matrices, frequently denoted by ${\sigma }_x$ or ${\sigma }_1$. In this work the dynamics of the $PQG$ and its extensions are studied through the actions available to the players.

Definition 2

($PQG$ moves and their composition). Let $M_P=\{I,F\}$ and $M_Q=\left\{H\right\}$ be the sets of permissible moves for Picard and Q, respectively, and let $M=M_P\cup M_Q=\{I,F,H\}$. The set of all finite compositions of moves from M, denoted by $M^{☆}$, is called the operational space of the $PQG$.

Consider for instance the composition $FH$, that can arise in the $PQG$ when Picard replies with F to Q’s H. A simple matrix multiplication shows that

$$\begin{array}{c}\hfill FH=\left[\begin{array}{c}\begin{array}{cc}\frac{\sqrt{2}}{2}\hfill & \hfill -\frac{\sqrt{2}}{2}\\ \frac{\sqrt{2}}{2}\hfill & \hfill \frac{\sqrt{2}}{2}\end{array}\end{array}\right].\end{array}$$

(3)

The operational space $M^{☆}$ contains not only the above operator (3), but also every operator that results from a finite composition of the moves in M. Most of them are not realized in the actual $PQG$ because its duration is just 3 rounds. Definition 2 can be generalized as follows:

Definition 3.

Given any game V (e.g., an extension of the original $PQG$ game), for which the set of moves is $M_V$, its operational space is $M_V^{☆}$.

2.2. Dihedral Groups

The notation and definitions from group theory are based on standard textbooks such as [22,23]. The number of elements of the group G is called the order of G and is denoted by $\left|G\right|$. It is customary to employ the following notation regarding powers of an arbitrary element g of a group G.

• $g^0=\mathbb{1}$,
• $g^n=\begin{array}{c}\underbrace{g\circ g\circ \dots \circ g}\\ n\mathrm{factors}\end{array}$, when $n>0$, and
• $g^n={\left(g^{-1}\right)}^{\left|n\right|}$, when $n<0$.

The symbol ∘ of the binary operation is omitted, particularly in view of the fact that in many occasions the group elements will be represented by $2\times 2$ matrices and the operation ∘ will be matrix multiplication. Hence, instead of writing $f\circ g$, the juxtaposition of the two elements $fg$ is used.

The groups that capture the symmetries of regular polygons are called dihedral groups. By regular polygon it is understood that all the sides of the polygon have the same length and all the interior angles are equal. Furthermore, it is assumed that the center of the regular polygon is located at the origin of the plane.

Definition 4

(Dihedral groups). The group of symmetries of the regular n-gon, where $n\ge 3$, is called the dihedral group of order $2n$ and is denoted by $D_n$.

Many authors denote the dihedral group of order $2n$ by $D_{2n}$ to explicitly indicate its order. However, in this paper the notation $D_n$ is preferred to emphasize the geometric intuition. From now on, when referring to the arbitrary dihedral group $D_n$, it will be assumed that $n\ge 3$. The group operation is composition of symmetries, i.e., composition of rotations and reflections. The $2n$ symmetries of a regular n-gon, where $n\ge 3$, can be categorized as follows.

• There are n rotational symmetries. These are the rotations about the center of the n-gon by $\frac{2\pi k}{n}$, with k taking the values $0,1,\cdots ,n-1$. Figure 1 and Figure 2 show the 7 and 8 rotational symmetries of the regular heptagon and octagon, respectively.
• There are also n reflection symmetries.

  –

  If n is odd these are the reflections in the lines defined by a vertex and the center of the regular n-gon. As an example, see Figure 3 depicting the reflection symmetries of the regular heptagon.

  –

  If n is even, these are $\frac{n}{2}$ reflections in the lines through opposite vertices and $\frac{n}{2}$ reflections in the lines passing through midpoints of opposite faces. An example that will play an important role in this study is given in Figure 4, showing the reflection symmetries of the regular octagon.

  By fixing a vertex of the regular n-gon to lie on the x-axis (such a vertex 1 in Figure 3 and Figure 4) and the center of the n-gon at the origin of the plane, the n reflection symmetries correspond to lines through the origin making an angle $\frac{\pi k}{n}$ with the positive x-axis, with k taking the values $0,1,\cdots ,n-1$.

The general dihedral group contains the following $2n$ elements (for details the interested reader may consult [22,23] or [24])

$$\begin{array}{c}\hfill D_n=\{\mathbb{1},r,r^2,\cdots ,r^{n-1},s,rs,r^{2}s,\cdots ,r^{n-1}s\},\end{array}$$

(4)

where r is the rotation by $\frac{2\pi }{n}$ and s is any reflection. It is evident that each element of $D_n$ can be uniquely written as $r^k{s}^l$ for some $k,0\le k\le n-1,$ and l, where $l=0$ or 1. Elements $\mathbb{1},r,r^2,\cdots ,r^{n-1}$ are rotations, i.e., $r^k$ is the rotation by $\frac{2\pi k}{n}$, and elements $s,rs,r^{2}s,\cdots ,r^{n-1}s$ are reflections.

In particular, the dihedral group $D_8$ contains the 16 elements

$$\begin{array}{c}\hfill D_8=\{\mathbb{1},r,r^2,\cdots ,r^7,s,rs,r^{2}s,\cdots ,r^{7}s\},\end{array}$$

(5)

where r is the rotation by $\frac{2\pi }{8}$ and s is any reflection. Referring to Figure 4, s can be taken to be the reflection in the line passing through the vertices 1 and 5, or the reflection in the line passing through the midpoints A and $A^{\prime }$, or the reflection in the line passing through the vertices 2 and 6, or any of the remaining reflections.

Definition 5

(Generators). Given a subset X of a group G, the smallest subgroup of G that contains X is denoted by X. The elements of X are called generators for X.

When X is finite, i.e., $X=\{x_1,\cdots ,x_n\}$, as will be the case in this work, it is customary to simply write $x_1,\cdots ,x_n$.

A typical way to specify groups is via presentations. This amounts to using generators and relations, with the understanding that all group elements can be constructed as products of powers of the generators, and the relations are equations involving the generators and the group identity. The following presentation of $D_n$ is especially convenient:

$$\begin{array}{c}\hfill D_n=\langle s,t|s^2=t^2={\left(st\right)}^n=\mathbb{1}\rangle .\end{array}$$

(6)

This presentation demonstrates that $D_n$ is generated by two reflections s and t. It appears in [22,25], where it is clarified that $D_n$ can be generated by two reflections $s,t$ in adjacent axes of symmetry passing though the origin and intersecting in an angle $\frac{\pi }{n}$. In this case, the product $st$ is a rotation through an angle of $\pm \frac{2\pi }{n}$.

3. The Connection between PQG and D₈

3.1. Matrix Representations of Rotations and Reflections

A useful and quite common way to represent rotations and reflections in the plane is to use $2\times 2$ matrices. Such matrices, which are often called rotators and reflectors, can be conveniently written in a form that is easy to recognize and manipulate (see [24,26,27] for more details). A rotator representing a counter-clockwise rotation through an angle $\phi$ about the origin is denoted by $R_{\phi }$ and, similarly, a reflector about a line through the origin that makes an angle $\phi$ with the positive x-axis is denoted by $S_{\phi }$. $R_{\phi }$ and $S_{\phi }$ are given by the formulas shown below. Note that capital R and capital S are used to designate these $2\times 2$ matrices, in order to avoid any confusion with the elements of the dihedral group that are denoted by small r and s.

$$\begin{array}{c}\hfill R_{\phi }=\left[\begin{array}{c}\begin{array}{cc}cos\phi \hfill & \hfill -sin\phi \\ sin\phi \hfill & \hfill cos\phi \end{array}\end{array}\right]\end{array}$$

(7)

$$\begin{array}{c}\hfill S_{\phi }=\left[\begin{array}{c}\begin{array}{cc}cos2\phi \hfill & \hfill sin2\phi \\ sin2\phi \hfill & \hfill -cos2\phi \end{array}\end{array}\right]\end{array}$$

(8)

It is now quite straightforward to see that the F and H operators can be written as follows.

$$\begin{array}{c}\hfill F=\left[\begin{array}{c}\begin{array}{cc}cos2\frac{2\pi }{8}\hfill & \hfill sin2\frac{2\pi }{8}\\ sin2\frac{2\pi }{8}\hfill & \hfill -cos2\frac{2\pi }{8}\end{array}\end{array}\right]\end{array}$$

(9)

$$\begin{array}{c}\hfill H=\left[\begin{array}{c}\begin{array}{cc}cos2\frac{\pi }{8}\hfill & \hfill sin2\frac{\pi }{8}\\ sin2\frac{\pi }{8}\hfill & \hfill -cos2\frac{\pi }{8}\end{array}\end{array}\right]\end{array}$$

(10)

This form reveals that both are reflectors: F reflects about a line that makes an angle $\frac{\pi }{4}$ with the positive x-axis. To be exact, this is the line passing through the vertices 2 and 6 in Figure 4. Likewise, H reflects about a line that makes an angle $\frac{\pi }{8}$ with the positive x-axis, which is the line passing through the midpoints A and $A^{\prime }$ in Figure 4. Hence, their axes of symmetry intersect in an angle $\frac{\pi }{8}$, as shown in Figure 4. Moreover, their product $FH$, which is given in (3), is just the rotator $R_{\frac{2\pi }{8}}$, as can be verified by employing Formula (7). Therefore, by invoking the presentation (6), associating s to F, and t to H, or vice versa, it becomes evident that F and H generate the dihedral group $D_8$. This conclusion is stated as Theorem 1.

In an effort to enhance the readability of this paper, all the proofs have been relocated to the Appendix A.

Definition 6

(The ambient group). Let V be a game with operational space $M_V^{☆}$. If $M_V^{☆}$ is isomorphic to the group G, then G is called the ambient group of the game V.

Theorem 1

(The ambient group of the $PQG$). The ambient group of the $PQG$ is $D_8$.

The above result tells us that Picard and Q’s moves generate the group $D_8$. This has important ramifications. As long as the two players are allowed to use only the aforementioned actions, no matter what specific game they play, the game will take place in the $D_8$ group. Every conceivable composition of moves by the players is just an element of $D_8$. Therefore, although the rules of the game can change dramatically, e.g., the players’ turn, the number of rounds, etc., the available moves will always be elements of $D_8$.

Every element of the dihedral group $D_n$ can be represented by $2\times 2$ matrices of the form shown in (7) and (8) (see [23,28] or [29] for more details). One such representation is given below. In the literature it is usually referred to as the standard representation of $D_n$. In more technical terms, this is a faithful irreducible representation of dimension 2. To clear any potential misunderstanding, let us emphasize that in the standard representation s corresponds to the reflection in the line passing through the vertices 1 and 5, i.e., the x-axis of Figure 4.

$$\begin{array}{c}\hfill r\mapsto R_{\frac{2\pi }{n}}=\left[\begin{array}{c}\begin{array}{cc}cos\frac{2\pi }{n}\hfill & \hfill -sin\frac{2\pi }{n}\\ sin\frac{2\pi }{n}\hfill & \hfill cos\frac{2\pi }{n}\end{array}\end{array}\right]\end{array}$$

(11)

$$\begin{array}{c}\hfill s\mapsto S_0=\left[\begin{array}{c}\begin{array}{cc}1\hfill & \hfill 0\\ 0\hfill & \hfill -1\end{array}\end{array}\right]\end{array}$$

(12)

The above mapping of r and s uniquely determines the standard representation of the remaining reflections and rotations of $D_n$.

$$\begin{array}{c}\hfill r^k\mapsto R_{\frac{2\pi k}{n}}=\left[\begin{array}{c}\begin{array}{cc}cos\frac{2\pi k}{n}\hfill & \hfill -sin\frac{2\pi k}{n}\\ sin\frac{2\pi k}{n}\hfill & \hfill cos\frac{2\pi k}{n}\end{array}\end{array}\right]\end{array}$$

(13)

$$\begin{array}{c}\hfill r^{k}s\mapsto S_{\frac{\pi k}{n}}=\left[\begin{array}{c}\begin{array}{cc}cos\frac{2\pi k}{n}\hfill & \hfill sin\frac{2\pi k}{n}\\ sin\frac{2\pi k}{n}\hfill & \hfill -cos\frac{2\pi k}{n}\end{array}\end{array}\right],\end{array}$$

(14)

where $0\le k\le n-1$.

3.2. Orbits and Stabilizers

Definition 7

(Group action). Let G be a group and let X be a non-empty set. A group action ☆ of G on X is a function $☆:G\times X\to X$ that satisfies the following properties.

(A1) 

$\mathbb{1}☆x=x$ for every $x\in X$.

(A2) 

$g_1☆\left(g_2☆x\right)=\left(g_1{g}_2\right)☆x$, for all $g_1,g_2\in G$ and all $x\in X$.

Under the standard representation of $D_n$, its action on a state of the quantum coin is computed by simply multiplying every matrix corresponding to an element of $D_n$ with the ket describing the state of the coin. In what follows, in addition to speaking about an action, the expression that Gacts on X will occasionally be employed. It is convenient to just write $gx$ instead of $g☆x$, since the action in this paper is that of operators on kets, i.e., of matrix-vector multiplication.

Definition 8

(Orbits and stabilizers). Suppose that a group G of linear operators, or their corresponding matrix representations, acts on a non-empty set of kets X. The next definitions, always taking into account that all kets of the form $e^{i\theta }|\psi \rangle$, with $\theta \in \mathbb{R}$, represent ket $|\psi \rangle$, will be useful.

1. 

Given $x\in X$, the G-orbit of x, denoted by $G☆x$, is the set $\{g☆x\in X:g\in G\}$.

2. 

Given $S\subset X$, the G-orbit of S, denoted by $G☆S$, is the union of the orbits $G☆x$, for each $x\in S$

3. 

Given $x\in X$, the stabilizer of x, denoted by $G\left(x\right)$, is the set $\{g\in G:g☆x=x\}$.

4. 

Given $g\in G$, the fixed set of g, denoted by $Fix\left(g\right)$, is the set $\{x\in X:g☆x=x\}$.

5. 

Given $X\subset G$, the fixed set of X, denoted by $Fix\left(X\right)$, is the intersection of the fixed sets $Fix\left(g\right)$, for each $g\in X$.

In the next section these tools will be employed in the analysis of Q’s strategy to gain insight from a group theoretic perspective.

4. Analyzing Q’s Strategy in Terms of Groups

In this section, the $PQG$ is interpreted using the aforementioned groups concepts. It is helpful to use the following abbreviations, which are very common in the literature.

$$\begin{array}{c}\hfill |+\rangle =\frac{1}{\sqrt{2}}\left(|0\rangle +|1\rangle \right)\end{array}$$

(15)

$$\begin{array}{c}\hfill |-\rangle =\frac{1}{\sqrt{2}}\left(|0\rangle -|1\rangle \right)\end{array}$$

(16)

It is instructive to see the effect of the action of $D_8$ on the computational basis B. One easy way to do this is geometrically, by consulting Figure 2 and Figure 4, to see where vertices 1 and 3 are sent when being acted upon by the elements of $D_8$. Alternatively, one can arrive at the same result algebraically simply by multiplying the matrix representation of every member of $D_8$ with $|0\rangle$ and $|1\rangle$. The representations of the elements of $D_8$ can be readily found by setting $n=8$ in the more general Formulas (13) and (14). In any event, for future reference the action of $D_8$ on the computational basis B is summarized in Proposition 1 (recall that $e^{i\theta }|\psi \rangle$, with $\theta \in \mathbb{R}$, and $|\psi \rangle$ represent the same state).

Proposition 1

(The action of $D_8$ on B).

1. 

$|0\rangle$ and $|1\rangle$ have the same orbit:

$$\begin{array}{c}\hfill D_8☆|0\rangle =D_8☆|1\rangle =\{|0\rangle ,|+\rangle ,|1\rangle ,|-\rangle \}.\end{array}$$

(17)

2. 

The orbit of B is:

$$\begin{array}{c}\hfill D_8☆B=\{|0\rangle ,|+\rangle ,|1\rangle ,|-\rangle \}.\end{array}$$

(18)

Q’s first move aims to drive the coin into the state

$$\begin{array}{c}\hfill H|0\rangle =|+\rangle .\end{array}$$

(19)

Definition 8 is helpful in understanding the advantage of Q’s move in terms of group notions. In particular, there are certain elements of $D_8$ whose action on $|+\rangle$ has no effect whatsoever and which constitute the stabilizer of $|+\rangle$. These can be easily found either geometrically or algebraically, and are listed in Proposition 2.

Proposition 2

(The stabilizers of $|0\rangle ,|+\rangle ,|1\rangle$ and $|-\rangle$ in $D_8$).

• The stabilizers of $|0\rangle$ and $|1\rangle$ in $D_8$ are

  $$\begin{array}{c}\hfill D_8\left(|0\rangle \right)=\{I,R_{\pi },S_0,S_{\frac{4\pi }{8}}\}and{D}_8\left(|1\rangle \right)=\{I,R_{\pi },S_0,S_{\frac{4\pi }{8}}\}.\end{array}$$

  (20)
• The stabilizers of $|+\rangle$ and $|-\rangle$ are

  $$\begin{array}{c}\hfill D_8\left(|+\rangle \right)=\{I,R_{\pi },F,S_{\frac{6\pi }{8}}\}and{D}_8\left(|-\rangle \right)=\{I,R_{\pi },F,S_{\frac{6\pi }{8}}\}.\end{array}$$

  (21)

In a complementary manner, it can be surmised that Picard’s set of moves fixes specific states in ${\mathcal{H}}_2$, as demonstrated in Proposition 3.

Proposition 3

(The fixed set of $\{I,F\}$ in $D_8$).

1. 

The fixed set of F in $D_8$ is the set

$$\begin{array}{c}\hfill Fix\left(F\right)=\{|+\rangle ,|-\rangle \}.\end{array}$$

(22)

2. 

The fixed set of $M_P=\{I,F\}$ in $D_8$ is the set

$$\begin{array}{c}\hfill Fix\left(\right\{I,F\left\}\right)=\{|+\rangle ,|-\rangle \}.\end{array}$$

(23)

Proposition 2 tells us that Picard’s set of moves is a subset of $D_8\left(|+\rangle \right)$ and Proposition 3 completes the picture by revealing that ket $|+\rangle$ is among those that are fixed by Picard’s moves. Thus, he is completely powerless to change the state $|+\rangle$ of the coin. From this perspective the progression of the $PQG$ can be abstractly described as by the following “algorithm”.

Picard symbolizes the classical player and as such it is quite appropriate to assume that their repertoire is the set $M_P=\{I,F\}$. This set is also a group, in particular the ${\mathbb{Z}}_2$ group of two elements (In the literature ${\mathbb{Z}}_2$ is more often denoted as $\{0,1\}$ under addition modulo 2). In the rest of this paper it will be assumed that the classical player can only make use of these two actions. In the coming sections Algorithm 1 will be employed to discover winning strategies for Q in more general situations.

Algorithm 1: Q’s Winning Strategy.

1 Q’s first move sends the coin to an intermediate target state (in the actual game it happens to be $|+\rangle$) that satisfies the following property: this state is fixed by Picard’s moves or, equivalently, all of Picard’s moves belong to the stabilizer of this state (in the actual game $I,F\in D_8\left(|+\rangle \right)$). 2 Picard acts on the coin, but no matter which move he makes, the quantum coin remains in the same state. 3 Q’s final move sends the coin to the desired state.

5. Enlarging the Operational Space of the Game

The operational space of the original $PQG$ is indeed a group, and, in particular, the dihedral group $D_8$, as established by Theorem 1. In this section, the ambient group of the $PQG$ will be progressively enlarged and Q’s winning strategies will be analyzed. The analysis is guided by the belief that the essence of the original $PQG$ is the sharp distinction between the classical and the quantum player. From this perspective, the subsequent investigation relies on the following two assumptions.

• Picard, who embodies the classical player, can flip the coin. If he is deprived of this ability, then the resulting game becomes trivial and meaningless. He should not be able to do more than that, as this would endow them with quantum capabilities. Formally, this is expressed by specifying:

  $$\begin{array}{c}\hfill M_P=\{I,F\}.\end{array}$$

  (24)
• Q, who stands for the quantum player, must exhibit quantumness. Thus, at least one of their actions must lie outside the classical realm. In more technical terms, their repertoire $M_Q$ must contain at least one operator from $U\left(2\right)$ other than I and F.

Under the above assumptions, the following properties are observed. These properties are quite general, as they are satisfied by every winning strategy of Q, no matter what the ambient group is. Therefore, they will be invoked when much larger dihedral groups and the unitary group $U\left(2\right)$ are considered.

Theorem 2

(Characteristic properties of winning strategies). If $(A_1,A_2)$ is a winning strategy for Q, then:

$$\begin{array}{cc}\hfill A_{2}I{A}_1|0\rangle & =A_{2}F{A}_1|0\rangle =|0\rangle ,and\hfill \end{array}$$

(25)

$$\begin{array}{cc}\hfill A_1|0\rangle & \in Fix\left(\right\{F\left\}\right).\hfill \end{array}$$

(26)

The notion of equivalent strategies greatly simplifies the classification of winning strategies. Two strategies are considered to be equivalent if, when acting on the same initial state of the coin, they produce the same sequence of states. In view of the extension of the original game that will be undertaken in Section 6, the next definition is general enough to deal with strategies for games with more than three number of rounds.

Definition 9

(Equivalent strategies). Let $\sigma =(A_1,\cdots ,A_r)$ and ${\sigma }^{\prime }=(A_1^{\prime },\cdots ,A_r^{\prime })$ be two strategies of the same player, and let $|q_0\rangle$ be the initial state of the coin. σ and ${\sigma }^{\prime }$ are equivalent with respect to $|q_0\rangle$, denoted by $\sigma \sim {\sigma }^{\prime }$, if

$$\begin{array}{c}\hfill A_j\cdots A_1|q_0\rangle =A_j^{\prime }\cdots A_1^{\prime }|q_0\rangle ,\mathrm{for}\mathrm{every}j,1\le j\le r.\end{array}$$

(27)

Q’s strategies $(H,H)$ and $(R_{\frac{2\pi }{8}},R_{\frac{14\pi }{8}})$ are equivalent because they send the coin from state $|0\rangle$ first to $|+\rangle$ and then back to $|0\rangle$. It is obvious that ∼ is an equivalence relation that partitions the set of strategies into equivalence classes of strategies.

Definition 10

(Strategy classes).

1. 

Given a strategy σ,$\left[\sigma \right]$ designates the equivalence class that contains σ. Any member of $\left[\sigma \right]$ is a representative of $\left[\sigma \right]$.

2. 

To every class $\left[\sigma \right]$ the state path ${\tau }_{\left[\sigma \right]}$ is associated as follows: if $(A_1,\cdots ,A_r)$ is any representative of $\left[\sigma \right]$, ${\tau }_{\left[\sigma \right]}$ is defined to be $(|q_0\rangle ,|q_1\rangle ,\cdots ,|q_r\rangle )$, where

$$\begin{array}{c}\hfill |q_j\rangle =A_j\cdots A_1|q_0\rangle ,\mathrm{for}\mathrm{every}j,1\le j\le r.\end{array}$$

(28)

Clearly, the state path ${\tau }_{\left[\sigma \right]}$ is well-defined and unique for each class $\left[\sigma \right]$. The equivalence class $\left[\right(H,H\left)\right]$ contains 16 strategies, as will be explained in Example 1, and the corresponding state path is $(|0\rangle ,|+\rangle ,|0\rangle )$.

5.1. Inside $D_8$

Before delving into larger groups, the case where Q can chose their moves from the entire $D_8$ group is examined, i.e.,

$$\begin{array}{c}\hfill M_Q=D_8.\end{array}$$

(29)

The following Example 1 will be instructive.

Example 1.

In this example, Algorithm 1 facilitates the study all winning strategies of Q in the original $PQG$. Let $(A_1,A_2)$ be Q’s first and second move in a winning strategy. After Q’s first move the quantum coin will in one of the states in the orbit $D_8☆B$, where B is the computational basis. From (18) it follows that $D_8☆B=\{|0\rangle ,|+\rangle ,|1\rangle ,|-\rangle \}$.

• Let us first establish that if Q leaves the coin at state $|0\rangle$, or sends it to state $|1\rangle$, then he will not be able to win with probability $1.0$. To see this more clearly, let us recall that, by Theorem 2, $A_{2}I{A}_1|0\rangle =A_{2}F{A}_1|0\rangle =|0\rangle$. If $(A_1,A_2)$ leaves the coin at state $|0\rangle$, i.e., $A_1|0\rangle =|0\rangle$, then $A_{2}I|0\rangle =A_{2}F|0\rangle =|0\rangle \Rightarrow A_2|0\rangle =A_2|1\rangle =|0\rangle$, which is impossible because $A_2$ represents an element of $D_8$. The same reasoning shows that if Q’s first move sends the coin to state $|1\rangle$, then he will not be able to win with probability $1.0$.
• In the original $PQG$, Q won by sending the coin to state $|+\rangle$. In $D_8$, this can be achieved with 4 different ways: $H,R_{\frac{2\pi }{8}},S_{\frac{5\pi }{8}}$, and $R_{\frac{10\pi }{8}}$. State $|+\rangle$ is fixed by I and F according to (23), which means that no matter what Picard plays, the coin will remain in this state. Finally, Q can send the coin back to the $|0\rangle$ state with 4 different ways: $H,R_{\frac{14\pi }{8}},S_{\frac{5\pi }{8}}$, and $R_{\frac{6\pi }{8}}$. This means that Q has 16 different winning strategies, which, in view of Definition 9, are equivalent. Thus, they constitute one equivalence class of winning strategies. Strategy $(H,H)$ is a representative of this class, but any other strategy would also do. For this class the corresponding state path is $(|0\rangle ,|+\rangle ,|0\rangle )$.
• Algorithm 1 enables us to discover one more winning strategy for Q. Q has another option, which is to drive the coin to state $|-\rangle$. This can also be achieved with 4 different ways: $S_{\frac{7\pi }{8}},R_{\frac{14\pi }{8}},S_{\frac{3\pi }{8}}$, or $R_{\frac{6\pi }{8}}$. Picard cannot change this state either because $|-\rangle$ is fixed by I and F, according to (23). During the final round Q has the opportunity to send the coin back to the $|0\rangle$ state with 4 different ways: $S_{\frac{7\pi }{8}},R_{\frac{2\pi }{8}},S_{\frac{3\pi }{8}}$, or $R_{\frac{10\pi }{8}}$. Hence, Q has 16 more winning strategies, which are equivalent. They make the second equivalence class of winning strategies and any one of them, e.g., $(S_{\frac{7\pi }{8}},S_{\frac{7\pi }{8}})$ can be its representative. For this class, the corresponding state path is $(|0\rangle ,|-\rangle ,|0\rangle )$.
• Picard, unfortunately for him, has no winning strategy.

According to Definition 1, for Q a winning strategy is also a dominant strategy. Hence, Q has precisely two classes of winning and dominant strategies, each containing 16 individual strategies. These two classes correspond to exactly the 2 path states $(|0\rangle ,|+\rangle ,|0\rangle )$, and $(|0\rangle ,|-\rangle ,|0\rangle )$. ◃

Table 1. The two classes of winning and dominant strategies for Q in the original $PQG$.

The Evolution of the $\mathit{PQG}$
	Initial State	Round 1	Round 2	Round 3
$(H,H),(R_{\frac{2\pi }{8}},R_{\frac{14\pi }{8}}),(S_{\frac{5\pi }{8}},S_{\frac{5\pi }{8}}),\cdots$	$|0\rangle$	$|+\rangle$	$|+\rangle$	$|0\rangle$
$(S_{\frac{7\pi }{8}},S_{\frac{7\pi }{8}}),(R_{\frac{14\pi }{8}},R_{\frac{2\pi }{8}}),(S_{\frac{3\pi }{8}},S_{\frac{3\pi }{8}}),\cdots$	$|0\rangle$	$|-\rangle$	$|-\rangle$	$|0\rangle$

and Figure 5 summarize these results.

Theorem 3.

(The ambient group of the $PQG$ is $D_8$). If $M_P=\{I,F\}$ and $M_Q=D_8$, i.e., the ambient group of the $PQG$ is $D_8$, then the following hold.

1. 

Q has exactly two classes of winning and dominant strategies, each containing 16 equivalent strategies:

$$\begin{array}{c}\hfill {\mathcal{C}}_{+}=\left[(A_1,A_2)\right]and{\mathcal{C}}_{-}=\left[(B_1,B_2)\right],\end{array}$$

(30)

where

• $A_1$ is one of $H,R_{\frac{2\pi }{8}},S_{\frac{5\pi }{8}}$ or $R_{\frac{10\pi }{8}}$,
• $A_2$ is one of $H,R_{\frac{14\pi }{8}},S_{\frac{5\pi }{8}}$ or $R_{\frac{6\pi }{8}}$,
• $B_1$ is one of $S_{\frac{7\pi }{8}},R_{\frac{14\pi }{8}},S_{\frac{3\pi }{8}}$ or $R_{\frac{6\pi }{8}}$, and
• $B_2$ is one of $S_{\frac{7\pi }{8}},R_{\frac{2\pi }{8}},S_{\frac{3\pi }{8}}$ or $R_{\frac{10\pi }{8}}$.

2. 

The winning state paths corresponding to ${\mathcal{C}}_{+}$ and ${\mathcal{C}}_{-}$ are

$$\begin{array}{c}\hfill {\tau }_{{\mathcal{C}}_{+}}=(|0\rangle ,|+\rangle ,|0\rangle )and{\tau }_{{\mathcal{C}}_{-}}=(|0\rangle ,|-\rangle ,|0\rangle ).\end{array}$$

(31)

3. 

Picard has no winning strategy.

5.2. The Smaller Dihedral Groups $D_3,D_4,D_5,D_6$ and $D_7$

It is natural to ask whether any of the smaller dihedral groups $D_3,D_4,D_5,D_6$, and $D_7$ can be an appropriate operational space for the $PQG$. The answer is no for the reasons outlined below.

• $D_3,D_5,D_6$, and $D_7$ do not contain the reflection F. This can be verified by comparing Formula (9) with formula (14) for $n=3,5,6$, and 7 and $k=1,\cdots ,n-1$. This is based on the assumption that Picard, the classical player, must be able to flip the coin, as emphasized in (24).
• $D_4$ does contain the reflection F. However, the orbit $D_4☆B$ is $\{|0\rangle ,|1\rangle \}$. This means that Q can only flip the coin from heads to tails or vice versa. If $M_Q=D_4$, then the $PQG$ degenerates to the classical coin tossing game. Q is no longer a quantum entity and, as explained in Example 1, no longer possesses a winning strategy. From this perspective, it becomes meaningless to play the $PQG$ in $D_4$.

These conclusions are contained in

Table 2. In smaller dihedral groups, it is either impossible to play the $PQG$, or, in the event that it is possible (such as in $D_4$), Q lacks a winning strategy. The abbreviation WS stands for winning strategy.

Ambient Group	Is PQG Playable	WS for Picard	WS for Q
$D_3$	No ($F\notin M_P$)	—	—
$D_4$	Yes (classical coin tossing)	No	No
$D_5$	No ($F\notin M_P$)	—	—
$D_6$	No ($F\notin M_P$)	—	—
$D_7$	No ($F\notin M_P$)	—	—

for easy reference.

Thus, assuming that the classical player should be able to flip the coin in order to have a non-trivial game, and that the quantum player must exhibit quantumness, then the smallest dihedral group for the $PQG$ is $D_8$. This is stated as Theorem 4.

Theorem 4

(The smallest dihedral group for the $PQG$ is $D_8$). $D_8$ is the smallest dihedral group in which $PQG$ can be meaningfully played and Q has a quantum winning strategy.

5.3. The Dihedral Groups $D_{8n}$, $n\ge 1$

The previous subsection demonstrated that the smallest meaningful group for the $PQG$ is $D_8$. This subsection examines what happens if Q can choose from a larger repertoire, and, more specifically, if

$$\begin{array}{c}\hfill M_Q=D_n,n\ge 8.\end{array}$$

(32)

A helpful observation is that when n is odd, then $D_n$ does not contain F, which is proved as Proposition A4 in the Appendix A. Thus, these groups can be excluded when considering larger groups where the $PQG$ can be successfully played. Another useful result about the orbit of B in general dihedral groups is contained in Theorem 5.

Theorem 5

(The action of $D_n$ on B). The action of the general dihedral group $D_n,n\ge 3,$ on the computational basis B depends on whether n is a multiple of 4 or even but not a multiple of 4.

1. 

if n is a multiple of 4, then the action of $D_n$ on the computational basis B is

$$\begin{array}{c}\hfill D_n☆|0\rangle =D_n☆|1\rangle =D_n☆B=\{cos\frac{2\pi k}{n}|0\rangle +sin\frac{2\pi k}{n}|1\rangle :0\le k<\frac{n}{2}\},\end{array}$$

(33)

2. 

if n is even but not a multiple of 4, then the action of $D_n$ on the computational basis B is

$$\begin{array}{cc}\hfill D_n☆|0\rangle & =\{cos\frac{2\pi k}{n}|0\rangle +sin\frac{2\pi k}{n}|1\rangle :0\le k<\frac{n}{2}\},\hfill \end{array}$$

(34)

$$\begin{array}{cc}\hfill D_n☆|1\rangle & =\{-sin\frac{2\pi k}{n}|0\rangle +cos\frac{2\pi k}{n}|1\rangle :0\le k<\frac{n}{2}\},\hfill \end{array}$$

(35)

$$\begin{array}{cc}\hfill D_n☆B& =\{cos\frac{2\pi k}{n}|0\rangle +sin\frac{2\pi k}{n}|1\rangle :0\le k<\frac{n}{2}\}\cup \{-sin\frac{2\pi k}{n}|0\rangle +cos\frac{2\pi k}{n}|1\rangle :0\le k<\frac{n}{2}\}.\hfill \end{array}$$

(36)

Figure 6, Figure 7 and Figure 8 provide intuitive visualizations of Theorem 5.

In this setting, Algorithm 1 can be used to establish under what conditions Q still possesses winning strategies and, if so, which these are. This is facilitated by the next Theorem 6, which explains what happens to the fixed set of $\{I,F\}$ in $D_n$.

Theorem 6

(The fixed set of $\{I,F\}$ in $D_n$). When the general dihedral group $D_n,n\ge 3,$ acts on the computational basis B, the fixed set of $M_P=\{I,F\}$ depends on whether n is a multiple of 8 or not.

1. 

If n is a multiple of 8, then:

$$\begin{array}{c}\hfill Fix\left(\right\{I,F\left\}\right)=Fix\left(F\right)=\{|+\rangle ,|-\rangle \}.\end{array}$$

(37)

1. 

In every other case:

$$\begin{array}{c}\hfill Fix\left(\right\{I,F\left\}\right)=Fix\left(F\right)=\varnothing .\end{array}$$

(38)

The significance of Theorem 6 is twofold. First, from a negative perspective, disqualifies most of the dihedral groups as potential ambient groups for the $PQG$. Simultaneously, in a positive note, it ascertains that the $PQG$ can be meaningfully played in every dihedral group $D_n$ such that n is a multiple of 8. Theorem 7 explains what exactly happens in terms of winning strategies when the $PQG$ is played in these groups.

Theorem 7

(The ambient group of the $PQG$ is $D_{8n}$). If $M_P=\{I,F\}$ and $M_Q=D_{8n}$, i.e., the ambient group of the $PQG$ is $D_{8n}$, where $n\ge 1$, then the following hold.

1. 

Q has exactly two classes of winning and dominant strategies, each containing 16 equivalent strategies:

$$\begin{array}{c}\hfill {\mathcal{C}}_{+}=\left[(A_1,A_2)\right]and{\mathcal{C}}_{-}=\left[(B_1,B_2)\right],\end{array}$$

(39)

where

• $A_1$ is one of $H,R_{\frac{2\pi }{8}},S_{\frac{5\pi }{8}}$ or $R_{\frac{10\pi }{8}}$,
• $A_2$ is one of $H,R_{\frac{14\pi }{8}},S_{\frac{5\pi }{8}}$ or $R_{\frac{6\pi }{8}}$,
• $B_1$ is one of $S_{\frac{7\pi }{8}},R_{\frac{14\pi }{8}},S_{\frac{3\pi }{8}}$ or $R_{\frac{6\pi }{8}}$, and
• $B_2$ is one of $S_{\frac{7\pi }{8}},R_{\frac{2\pi }{8}},S_{\frac{3\pi }{8}}$ or $R_{\frac{10\pi }{8}}$.

2. 

The winning state paths corresponding to ${\mathcal{C}}_{+}$ and ${\mathcal{C}}_{-}$ are

$$\begin{array}{c}\hfill {\tau }_{{\mathcal{C}}_{+}}=(|0\rangle ,|+\rangle ,|0\rangle )and{\tau }_{{\mathcal{C}}_{-}}=(|0\rangle ,|-\rangle ,|0\rangle ).\end{array}$$

(40)

3. 

Picard has no winning strategy.

This leads to a very important conclusion: nothing substantial will change if the game takes place in much larger groups than $D_8$; the winning strategies remain precisely the same. This realization begs the question whether things will turn out to be different when Q has at their disposal the largest group possible, $U\left(2\right)$, which is examined in the next subsection.

5.4. The Entire $U\left(2\right)$

This section examines the situation when Q is free to choose from all of $U\left(2\right)$, which is the largest possible group that Q can draw their moves from. Therefore, the final assumption regarding Q’s set of actions is that

$$\begin{array}{c}\hfill M_Q=U\left(2\right).\end{array}$$

(41)

The major difference compared to the previous cases is that $U\left(2\right)$ contains infinitely many elements, whereas the previous groups were finite. Although, superficially, this might be expected to drastically enhance Q’s capabilities, it turns out that in a certain sense everything remains the same. This can be attributed to the following very simple fact. Kets $|\psi \rangle$ and $e^{i\theta }|\psi \rangle$, where $\theta \in \mathbb{R}$, physically represent the same state. In turn, this implies that the action of the operator $A\in U\left(2\right)$ on a ket $|\psi \rangle$ is the same as the action of $e^{i\theta }A\in U\left(2\right)$ on $|\psi \rangle$ (see [30] for details). If $e^{i\theta }A$ is viewed as denoting a parametric family of operators, it is clear that all these operators can be considered equivalent and any of them, e.g., A, can be taken as the representative of the corresponding equivalence class. In order to simplify the notation, the following Definition 11 is useful.

Definition 11

(Families of unitary operators).

If $A\in U\left(2\right)$, then

$$\begin{array}{c}\hfill A\left(\theta \right)=e^{i\theta }A,\theta \in \mathbb{R}.\end{array}$$

(42)

denotes a one-parameter family of unitary operators.

Similarly, if $R_{\phi }$ and $S_{\phi }$ are rotators and reflectors, as given by (7) and (8), respectively, the following one-parameter families of operators are defined:

$$\begin{array}{c}\hfill R_{\phi }\left(\theta \right)=e^{i\theta }{R}_{\phi }\end{array}$$

(43)

$$\begin{array}{c}\hfill S_{\phi }\left(\theta \right)=e^{i\theta }{S}_{\phi },\end{array}$$

(44)

where $\theta \in \mathbb{R}$. Analogously, if H is the Hadamard transform and $R_{\frac{2\pi k}{n}}$ and $S_{\frac{\pi k}{n}}$ are the matrix representations given by (13) and (14), the corresponding collections of operators are:

$$\begin{array}{c}\hfill H\left(\theta \right)=e^{i\theta }H,\end{array}$$

(45)

$$\begin{array}{c}\hfill R_{\frac{2\pi k}{n}}\left(\theta \right)=e^{i\theta }{R}_{\frac{2\pi k}{n}},\end{array}$$

(46)

$$\begin{array}{c}\hfill S_{\frac{\pi k}{n}}\left(\theta \right)=e^{i\theta }{S}_{\frac{\pi k}{n}}.\end{array}$$

(47)

Again it is fruitful to turn to Algorithm 1 to establish under what conditions Q possesses winning strategies and which are these. This approach is guided by the next Theorem 8, which establishes the fixed set of $\{I,F\}$ in $U\left(2\right)$.

Theorem 8

(The fixed set of $\{I,F\}$ in $U\left(2\right)$). Under the action of $U\left(2\right)$ on the computational basis B, the fixed set of $M_P=\{I,F\}$ is

$$\begin{array}{c}\hfill Fix\left(\right\{I,F\left\}\right)=Fix\left(F\right)=\{|+\rangle ,|-\rangle \}.\end{array}$$

(48)

This result is crucial in discovering and enumerating the winning strategies of Q in $U\left(2\right)$. Although, one might have hoped for more variety in discovering winning strategies, the result is not unexpected because the flip operator F cannot fix more that two states. The next Theorem 9 explains what exactly happens in terms of winning strategies when the $PQG$ takes place in $U\left(2\right)$.

Theorem 9

(The ambient group of the $PQG$ is $U\left(2\right)$). If $M_P=\{I,F\}$ and $M_Q=U\left(2\right)$, i.e., the ambient group of the $PQG$ is $U\left(2\right)$, then the following hold.

1. 

Q has exactly two classes of winning and dominant strategies, each containing infinite equivalent strategies:

$$\begin{array}{c}\hfill {\mathcal{C}}_{+}=\left[(A_1\left({\theta }_1\right),A_2\left({\theta }_2\right))\right]and{\mathcal{C}}_{-}=\left[(B_1\left({\theta }_3\right),B_2\left({\theta }_4\right))\right],\end{array}$$

(49)

where

• $A_1\left({\theta }_1\right)$ is one of $H\left({\theta }_1\right),R_{\frac{2\pi }{8}}\left({\theta }_1\right),S_{\frac{5\pi }{8}}\left({\theta }_1\right)$ or $R_{\frac{10\pi }{8}}\left({\theta }_1\right)$,
• $A_2\left({\theta }_2\right)$ is one of $H\left({\theta }_2\right),R_{\frac{14\pi }{8}}\left({\theta }_2\right),S_{\frac{5\pi }{8}}\left({\theta }_2\right)$ or $R_{\frac{6\pi }{8}}\left({\theta }_2\right)$,
• $B_1\left({\theta }_3\right)$ is one of $S_{\frac{7\pi }{8}}\left({\theta }_3\right),R_{\frac{14\pi }{8}}\left({\theta }_3\right),S_{\frac{3\pi }{8}}\left({\theta }_3\right)$ or $R_{\frac{6\pi }{8}}\left({\theta }_3\right)$,
• $B_2\left({\theta }_4\right)$ is one of $S_{\frac{7\pi }{8}}\left({\theta }_4\right),R_{\frac{2\pi }{8}}\left({\theta }_4\right),S_{\frac{3\pi }{8}}\left({\theta }_4\right)$ or $R_{\frac{10\pi }{8}}\left({\theta }_4\right)$, and
• ${\theta }_1,{\theta }_2,{\theta }_3,{\theta }_4$ are possibly different real parameters.

2. 

The winning state paths corresponding to ${\mathcal{C}}_{+}$ and ${\mathcal{C}}_{-}$ are

$$\begin{array}{c}\hfill {\tau }_{{\mathcal{C}}_{+}}=(|0\rangle ,|+\rangle ,|0\rangle )and{\tau }_{{\mathcal{C}}_{-}}=(|0\rangle ,|-\rangle ,|0\rangle ).\end{array}$$

(50)

3. 

Picard has no winning strategy.

This final conclusion is illuminating. Although there are infinitely many winning strategies, they are equivalent to the strategies found in $D_8$. In this perspective nothing is really gained by enabling Q to pick moves from $U\left(2\right)$. In a certain sense the spirit of the game is completely captured when it is realized in $D_8$. The next

Table 3. The two classes of winning strategies for Q when the $PQG$ is played in a dihedral group $D_{8n},n\ge 1$ and when the game is played in the largest possible group $U\left(2\right)$.

The Ambient Group is${\mathit{D}}_{8\mathit{n}},\mathit{n}\ge 1$
	Initial State	Round 1	Round 2	Round 3
$(H,H),(R_{\frac{2\pi }{8}},R_{\frac{14\pi }{8}}),(S_{\frac{5\pi }{8}},S_{\frac{5\pi }{8}}),\cdots$	$|0\rangle$	$|+\rangle$	$|+\rangle$	$|0\rangle$
$(S_{\frac{7\pi }{8}},S_{\frac{7\pi }{8}}),(R_{\frac{14\pi }{8}},R_{\frac{2\pi }{8}}),(S_{\frac{3\pi }{8}},S_{\frac{3\pi }{8}}),\cdots$	$|0\rangle$	$|-\rangle$	$|-\rangle$	$|0\rangle$
The Ambient Group is$\mathit{U}\left(\mathbf{2}\right)$($\mathbf{\theta }\in \mathbb{R}$)
	Initial State	Round 1	Round 2	Round 3
$(H\left({\theta }_1\right),H\left({\theta }_2\right)),(R_{\frac{2\pi }{8}}\left({\theta }_1\right),R_{\frac{14\pi }{8}}\left({\theta }_2\right)),\cdots$	$|0\rangle$	$|+\rangle$	$|+\rangle$	$|0\rangle$
$(S_{\frac{7\pi }{8}}\left({\theta }_3\right),S_{\frac{7\pi }{8}}\left({\theta }_4\right)),(R_{\frac{14\pi }{8}}\left({\theta }_3\right),R_{\frac{2\pi }{8}}\left({\theta }_4\right)),\cdots$	$|0\rangle$	$|-\rangle$	$|-\rangle$	$|0\rangle$

contains the complete results about Q’s classes of winning strategies whether the ambient group belongs to the family of dihedral groups $D_{8n}$ or is the entire $U\left(2\right)$.

In $U\left(2\right)$ the strategy classes contain infinite many strategies, but all these strategies are equivalent to the strategies encountered before.

6. Extending the Game

The original $PQG$ can be extended in numerous ways. In each conceivable extension, the precise formulation of the rules of the game is of paramount importance. By drastically changing the rules it is even possible for Picard to win the game. This was accomplished in [9] where the authors exploited entanglement in a clever way, so that whether the system ends up in a maximally entangled or separable state determines the outcome. In [11], it was shown that all possible finite extensions of the $PQG$ can be expressed in terms of simple finite automata, provided that the allowable moves of Picard are either I or F and Q always uses the Hadamard transform H. The focus of the present investigation is enlarging the operational space of the game. Therefore, when considering extensions of the original $PQG$, not only the assumptions (24) and (41), i.e., $M_P=\{I,F\}$ and $M_Q=U\left(2\right)$ are valid, but, additionally, it is supposed that:

• at the start of the game the coin is in a predefined basis state, which is called the initial state and designate by $|q_0\rangle$,
• Picard and Q alternate turns acting on the coin following a specified order, and
• when the game ends, the coin is measured in the computational basis; if it is found in state $|q_P\rangle$ Picard wins, whereas if it is found in $|q_Q\rangle$ then Q wins.

It is convenient to refer to $|q_P\rangle$ as Picard’s target state and to $|q_Q\rangle$ as Q’s target state. In a zero-sum game the target states $|q_P\rangle$ and $|q_Q\rangle$ are different. Furthermore, since both Picard and Q draw their moves from groups, nothing is lost in terms of generality if neither of them is allowed to make consecutive moves. Two or more successive moves by Q can be composed to give just one equivalent move, and the same holds for Picard.

Definition 12

(Extended games between Picard & Q). An n-round game, $n\ge 2$, is a function that associates one of the players, i.e., Picard or Q, to every round of the game. An n-round game is conveniently represented as a sequence of length n from the alphabet $\{P,Q\}$, where the letters P and Q stand for Picard and Q, respectively. In accordance with the previous remarks it is assume that if $(K_1,K_2,\cdots ,K_n)$ is an n-round game, then $K_i\ne K_{i+1}$, $1\le i<n$.

Definition 1 is general enough to also hold for extended games. The next important Theorem 10 confirms that Picard cannot win any such game with probability $1.0$. This negative result implies that for these extended games, Picard is at a permanent disadvantage.

Theorem 10

(Picard lacks a winning strategy). Picard does not have a winning strategy in any n-round game, $n\ge 2$, as long as Q makes at least one move.

The next couple of theorems explain in which games Q is unable to formulate a winning strategy. First, rather predictably, if Picard is given the opportunity to act last on the coin, then Q cannot surely win.

Theorem 11

(Q lacks a winning strategy when Picard plays last). Q does not have a winning strategy in any n-round game, $n\ge 2$, in which Picard makes the last move.

Symmetrically, it is also true that Q is unable to devise a winning strategy when Picard plays first, as the next Theorem 12 asserts.

Theorem 12

(Q lacks a winning strategy when Picard plays first). Q does not have a winning strategy in any n-round game, $n\ge 2$, in which Picard makes the first move.

Theorems 11 and 12 establish that Q cannot surely win in any game where Picard makes the first or the last move. Figure 9 and Figure 10 provide a visual explanation of the validity of these two theorems.

The picture is completed by the next Theorem 13 which asserts that Q has a winning strategy if and only if Q makes the first and the last move. This result clarifies that the overwhelmingly larger repertoire of moves of the quantum player by itself is not enough. It has to be combined with the advantage of making both the first and the last move in order to guarantee that the quantum player will surely win. Figure 11 presents two typical situations where Q can surely win. In the first n-round game Q makes the first and the last move and the initial state of the coin and the target state for Q are both the same. In the second n-round game Q makes the first and the last move, but the initial state of the coin is $|1\rangle$, whereas the target state for Q is $|0\rangle$.

Theorem 13

(When Q possesses a winning strategy). In any n-round game, $n\ge 2$, Q has a winning strategy iff Q makes the first and the last move.

One last conclusion that may drawn from the above theorems is about the initial state of the coin and the target states of the players. In the original $PQG$, both the initial state and Q’s target state were the same, namely $|0\rangle$. Clearly, the particular choice of the initial state and the target states is of no importance. If there exists a winning strategy for Q with respect to specific initial and target states, then there exists a winning strategy for every combination of initial and target states.

Corollary 1

(The impact of initial and target states). In any n-round game, $n\ge 2$, if Q has a winning strategy, he has a winning strategy for any combination of initial and target states.

7. Discussion

The important philosophical question behind the original $PQG$ game is whether and under what precise conditions the quantum paradigm exhibits a definitive advantage against the classical paradigm. From this perspective, this section analyzes the results obtained here.

Theorem 1 sets the group theoretic background of the $PQG$ by showing that Picard and Q’s moves generate the group $D_8$. The significance of groups is paramount because it implies that no matter what strategies are used the game will take place in the group. Even if the rules of the game change, the available actions will be elements of the group.

Theorem 3 builds on this result by enumerating and classifying the winning strategies of Q in $D_8$. The notion of equivalent strategies simplifies this classification by identifying two strategies as equivalent if their action on the coin produces the same sequence of states. Hence, the winning strategies can be grouped into equivalent classes that are distinguished by their corresponding state path. Theorem 3 proves that Q has two classes of winning strategies, each containing 16 equivalent strategies, and the corresponding state paths are $(|0\rangle ,|+\rangle ,|0\rangle )$, and $(|0\rangle ,|-\rangle ,|0\rangle )$. In effect, these are the only paths that Q can take to surely win the game and each of them can be realized by 16 different ways.

Furthermore, assuming that Picard should, at the very least, be able to flip the coin and that Q must exhibit quantumness, then Theorem 4 establishes the smallest group in which the $PQG$ can be meaningfully played is $D_8$. When considering larger dihedral groups, Theorem 6 furnishes important information. From a prohibitive aspect, it disqualifies most of the dihedral groups as eligible groups for the $PQG$. In a more positive note, it ensures that the $PQG$ can be played in every dihedral group $D_{8n}$. Theorem 7 analyzes this situation and concludes that the winning strategies remain precisely the same, despite the much larger repertoire of moves from which Q can choose their actions.

Theorem 9 completes the picture by examining $U\left(2\right)$, the largest group possible. $U\left(2\right)$ contains infinitely many elements, whereas the dihedral groups were finite. Superficially, this would seem to drastically enhance Q’s capabilities. Nonetheless, everything remains practically the same. Although in $U\left(2\right)$ there are infinitely many winning strategies, they are all equivalent to the strategies found in $D_8$. It seems that the essence of the $PQG$ is captured by $D_8$.

The original $PQG$ can be extended in a plethora of ways. In each extension, the precise formulation of the rules of the game is crucial. In the study of finite extensions of the original game Theorem 13 provides an important clarification. It asserts that the overwhelmingly larger repertoire of moves of Q is not enough by itself, but it has to be combined with the advantage of making both the first and the last move in order to guarantee that Q will surely win. One last minor conclusion drawn from 1 is that whenever Q has a winning strategy for specific initial and target states, he has a winning strategy for every combination of initial and target states.

8. Conclusions

Quantum games not only pose many interesting questions, but also motivate research that can have important applications in other related fields such quantum algorithms and quantum key distribution. This work was inspired by the iconic PQ penny flip game that, undoubtedly, helped create the field. The approach advocated here is based on the use of concepts from group theory. This allowed us to uncover the interesting connection of the original game with the dihedral group $D_8$. Interpreting the game in terms of stabilizers and fixed sets enabled us to easily explain and replicate Q’s strategy. This in turn allowed to prove that there exist precisely two classes of winning strategies for Q. Each class contains many different strategies, but all these strategies are equivalent in the sense that they drive the coin through the same sequence of states. It was established that there are exactly two different sequences of states that can guarantee Q’s win with probability $1.0$. What is noteworthy is the realization that even when the game takes place in larger dihedral groups, or even in the entire $U\left(2\right)$, this fact remains true. The essence of the game can be succinctly summarized by saying that there are precisely two paths that lead to Q’s win and, of course, no path that leads to Picard’s win. Finally, when extensions of the game without any restriction were examined, it was discovered that for the quantum player to surely win against the classical player the tremendous advantage of quantum actions is not enough. Q must also make the first and the last move, or else he is not certain to win.

There still many questions to be answered and a lot of important issues have to be addressed. These results were based on the assumption that the initial state of the coin and the target states of the players were one the the basis states. If this is not the case, and entanglement comes into play, how does that affect the progression of the game? This is a particularly interesting topic, worthy to be the subject of a future work.