July 07, 2026
A combinatorial game is a deterministic game with no hidden information played between two opponents such as tic-tac-toe, checkers or chess. In this paper we extend combinatorial games to the quantum setting, by first revisiting and reformulating existing theory of classical combinatorial games.
We investigate in which case a quantum opponent has an advantage over a classical one. Surprisingly, our instantiation of Zermelo’s classical theorem in the quantum setting shows that the effects of quantum mechanics do not convey an advantage against a classical player that plays a perfect classical strategy. In a more realistic scenario, when the classical player makes mistakes, we show how the quantum opponent can amplify the mistake to increase their chance of winning. Our theory has application beyond the mere playing of board games and can be used as a tool in finite deterministic adversarial models with perfect information.
A common characteristic of a game of tic-tac-toe, checkers, chess, abalone or go is that they are played between two opponents, they are deterministic and don’t involve any hidden information. In the literature, they are known as combinatorial games. In this paper we ask ourselves what a match of a combinatorial game might look like on a quantum computer, and whether one can have strategies that guarantee a certain outcome like winning, or not losing (e.g. tic-tac-toe). While the rules for any of the above mentioned classical, well-known combinatorial games are set in stone, different generalizations are possible for a quantum variant. Indeed, several quantum variants of tic-tac-toe have already been proposed for different purposes [1]–[5], and also for chess [6] and go [7]–[9]. None of them, however, quite fit the following reasonable requirements:
The quantum variant should be actually practically playable on a quantum computer; e.g. measurement at the end.
The quantum variant should be an extension of the regular, classical game in the sense that a strategy for the regular game (a set of instructions on how to react to each move of the opponent) should be playable in the quantum variant.
The player in the quantum variant should not be arbitrarily restricted to, say, make superpositions of only two moves.
We propose a general framework for quantization of combinatorial games that meets all these realistic requirements and applies to a broad class of combinatorial games with ties, including tic-tac-toe, chess and hex. After having defined the exact rules of our quantum variant of a combinatorial game, we turn to the question of winning strategies. For example, it is well known that there is no winning strategy for tic-tac-toe, but there is a non-losing one. Our main result implies that, surprisingly, in our variant of quantum tic-tac-toe a ‘quantum player’, a player that takes full advantage of the moves permitted under this quantum variant, can still not win against a regular ‘classical player’ playing the classical non-losing strategy. A similar result holds for quantum combinatorial games in general, see Section 3. One might conclude from this that playing on a quantum computer (under our rules) is not really interesting as the classical best strategies still apply. This might well be the case for a game like tic-tac-toe, where the classical best strategy is memorizable by a child, but does not apply to games like chess, where, while at least one of the two players (black or white) must have a non-losing strategy (by Zermelo’s theorem [10]), the details of such a strategy are not known to mortals. It might thus not be unreasonable to think that a chess player making proper quantum moves might gain an edge over a non-perfect, human opponent playing just classical moves. (We’ll actually see an example of this, Lemma 2).
Finally, taking into account the criteria above, we argue that the framework we propose can be used as a tool for many finite deterministic adversarial models with perfect information. One only has to find a suitable translation of their problem to a classical game. An example is the Byzantine Generals problem, which we detail in Section 4.
Several publications on quantized combinatorial games have been published in recent years. Especially quantum tic-tac-toe has attracted considerable attention. The first definition was proposed by Goff et al. [1] who introduced quantum tic-tac-toe for teaching the concepts of quantum mechanics and computing. Subsequent definitions [2]–[5] shared similar motivations. This justifies the use of a restricted set of quantum moves and sometimes involves intermediate measurement. Building on top of Goff et al., Leaw & Cheong [11] propose an alternative definition of quantum tic-tac-toe that generalizes classical tic-tac-toe (contrary to Goff et al). However, the implementability of this construction as a quantum circuit remains unclear.
Besides quantum tic-tac-toe, other combinatorial games have also been quantized. Cantwell’s [6] variant of quantum chess uses “split” and “merge” moves, which are a good way to convey intuition about quantumness but very restricting for the quantum player. Both Ranchin et al. and Sahu et al. [7], [8] construct a quantum-like version of go for pedagogical purposes. Qiao et al.’s [9] variant of quantum go expands classical go by adding specific quantized moves. Finally, a variant of quantum checkers has been proposed by Raat et al.[12], implementing the proposal for general combinatorial games by Dorbec and Mhalla [13].
Dorbec and Mhalla [13] propose a general framework for quantum combinatorial games. They propose a definition with five levels of quantumness. The level with the most “quantumness”, allows both classical moves and moves in a superposition all with equal amplitude. The moves must be applied to all positions in the superposition, illegal moves are dropped. A player loses a position once measuring a loss has probability one. This was done to ensure the combinatorial nature of the quantum variant of the games.
Kyle Burke et al. [14] study several properties of the various quantumness levels in the framework of Dorbec and Mhalla, most notably (for our research) showing that quantum moves have impact on the game’s outcome, in their highest quantumness level. This is contrary to our results and the consequence of Dorbec and Mhalla not adhering to our third requirement: the players’ moves in the quantum game should not be arbitrarily restricted. Specifically, in the game defined by Dorbec and Mhalla a player cannot make the move dependent on the specific position in the superposition it is applied to — something which should be achievable using controlled gates — possibly forcing players to make mistakes.
We propose a general framework for quantizing combinatorial games. First, we show that any combinatorial game can be reformulated into an equivalent quantizable form — one with a fixed number of rounds and injective valid moves — which we establish via bisimulation.
Our main result is that quantumness does not improve a player’s achievable outcome against a perfect opponent. Formally, we show that for any position the set of guaranteeable outcomes is identical (up to superpositions) in the classical and quantum variants of the game. The key insight is that quantum moves must respect classical rules, so if an outcome can be guaranteed classically the quantum moves cannot escape this as their effects can be reduced to a set of classical moves.
As a corollary, we prove a quantum Zermelo theorem [10]. Applying the classical theorem directly to the quantum game — which is itself a combinatorial game — yields guarantees only over distributions of outcomes. In particular, when neither player can force an outright win, it leaves open the possibility of losing with some probability. Our stronger version eliminates this: if neither player can force a win, both can still prevent any chance of losing, just as in the classical game. Against an imperfect opponent, we show that quantum players can gain advantage. To do so, we introduce a flaw-amplifying strategy that “cherry-picks” the opponent’s mistakes, yielding a strictly better outcome than classical strategies could achieve. To demonstrate the applicability of our framework beyond merely playing games, we formulate the Byzantine Generals problem as a combinatorial game. This yields a clean proof that any instance of the Byzantine Generals problem solvable under classical failures is also solvable under quantum failures — for classical well-behaving nodes.
The paper is organized as follows. In Section 2 we define combinatorial games and develop the basic combinatorial theory. We extend our theory to quantum combinatorial games in Section 3, where we analyse the cases of a perfect and an imperfect classical players. In Section 4, we present a non-trivial application of our theory. We conclude with Section 5 where we discuss possible generalizations and open problems.
We will be interested in two-player games like tic-tac-toe, where no chance or secrets are involved, and that are guaranteed to end after a set number of turns with a win for one of the two players, or a tie. We will denote the two players with \(X\) and \(O\). More formally we define such games as follows. Note that this is not the standard definition of combinatorial game[15], but a version modified for our purposes.
One change worth mentioning up front is that we include whose turn it is into the positions of our combinatorial games. So while normally a (combinatorial game) position of chess would only comprise the location of the pieces on the chess board1, our chess positions include whether black or white is to move too.
Definition 1. A combinatorial game \(\mathcal{G}\) consists of a set of positions (also denoted by) \(\mathcal{G}\), a set of moves \(\Sigma\), a starting position \(0\), a player-to-move map \(\mathrm{turn}\colon \mathcal{G}\to \{X,O\}\), a transition map, \[\Gamma\colon \mathcal{G} \times \Sigma \longrightarrow \mathcal{G} \cup \{ \perp \},\] a set of finished positions \(\mathcal{F}\subseteq \mathcal{G}\), an outcome set \(\Omega\) (usually \(\{X,O,T\}\)), and an outcome function \(\mathcal{O}\colon \mathcal{F}\rightarrow \Omega\), such that (we write \(g\xrightarrow{\sigma} g'\) when \(\Gamma(g,\sigma)=g'\)):
(\(X\) starts) \(\mathrm{turn}(0)=X\);
(Taking turns) \(\mathrm{turn}(\Gamma(g,\sigma)) \neq \mathrm{turn}(g)\) for all \(g\in \mathcal{G}\) and \(\sigma\in \Sigma\) with \(\Gamma(g,\sigma)\neq\perp\);
(No moves implies finished) If in a position \(g\) there is no more (valid) move, then \(g\in \mathcal{F}\);
(Outcomes do not change) If in a finished position \(g\in \mathcal{F}\) it is still possible to make a move, \(g\xrightarrow{\sigma} g'\), then this does not change the outcome: \(g'\in\mathcal{F}\) and \(\mathcal{O}(g')=\mathcal{O}(g)\).
(Each position is reachable) For every \(g\in \mathcal{G}\) there are \(\sigma_1,\dotsc,\sigma_n\in \Sigma\) such that \[0\xrightarrow{\sigma_1} g_1 \xrightarrow{\sigma_2} g_2 \xrightarrow{\sigma_3} \dotsb \xrightarrow{\sigma_n} g_n=g.\]
(Games end) There is a natural number \(N\) such that for any sequence \(g_0\xrightarrow{\sigma_1}g_1 \xrightarrow{\sigma_2} \dotsb \xrightarrow{\sigma_N}g_N\) of \(N\) moves we have \(g_N\in\mathcal{F}\).
We call a combinatorial game finite if the following three sets are finite: the set of positions, \(\mathcal{G}\), the set of moves, \(\Sigma\), and the outcome set, \(\Omega\).
Some remarks about the definition above are in order.
Only for the finite combinatorial games will we define a quantum variant, which will itself be a (non-finite) combinatorial game. The restriction to a finite set of positions and moves is necessary, because (quantum) computers only have finite memory. The resulting quantum variant, however, will not have only a finite set of positions, so finiteness is not part of the definition of combinatorial game above. Similarly, since the execution time on a quantum computer is limited, we only consider games that end after finitely many moves. (These are known as ‘short’ games in the literature [15].) Interestingly, the quantum variant will be short as well, so we included this restriction in the definition of our ‘combinatorial game’, via condition [games-end]. While the outcome set for tic-tac-toe (and many other combinatorial games) is simply \(\{X,O,T\}\), representing a win for \(X\), a win for \(O\), and a tie, respectively, you will see below that the outcome set for a game of quantum tic-tac-toe will be the set \(\mathcal{D}(\{X,O,T\})\) of probability distributions over \(\{X,O,T\}\).
Condition [outcomes-do-not-change] might seem odd: why not simply prohibit moves in a finished position? The reason is that a quantum position will be a superposition of classical positions, some of which may already be finished while others are not. If we want a move on a quantum position to simply be a classical move on each component of the superposition, we must permit moves on finished positions. In many games, such as tic-tac-toe, this is not part of the original rules, so for quantization we consider a slightly modified version with a ‘skip’ move on any finished position (see Definition 11), which raises the question whether anything essential has changed. We address this by showing the modified game is bisimilar to the original (Definition 6).
A second hurdle one encounters when defining a quantum variant of a combinatorial game is making sure that a classical strategy can be followed on a quantum computer as well. It may happen that two different positions lead to the same position in one step, for example, for tic-tac-toe it is standard for \(X\) to move to ii) both from i) and iii) in the figure below. This presents a problem on
a quantum computer: any operation must be a unitary, which is injective, which the move iii) to ii) is not. The solution is to let the unitary act not on the current position alone, but on the full play history (Definition 10), making \(\Gamma\colon \mathcal{G}\times \Sigma\to \mathcal{G}\cup\{\perp\}\) an injective partial map. Again, bisimulation shows this modified game is equivalent, at least classically.
Definition 2. Given a position \(g\) in a combinatorial game \(\mathcal{G}\), let \(N(g)\) be the maximum number of moves that can be made from \(g\) before ending up in a finished position.
Note that \(N(g)<\infty\) by condition [games-end]. The number \(N(g)\) is very convenient for induction over the set of positions in a game, because:
\(N(g)=0\) if and only if \(g\) is finished; and
if \(g\xrightarrow{\sigma} g'\) for some \(\sigma\), and \(g\) is not finished, then \(N(g') < N(g)\).
(The number \(N(g)\) plays a role similar to the birthday of a position in traditional combinatorial game theory.)
With the help of \(N(g)\) we can introduce the two most important characters of this paper, the sets \(\Sigma_{\mathcal{T}}\) and \(\Pi_{\mathcal{T}}\) (where \(\mathcal{T}\subseteq \Omega\) is some ‘target outcome’), with the following interpretation:
\(g\in \Sigma_{\mathcal{T}}\) iff the current player can achieve an outcome from \(\mathcal{T}\), whatever the opponent does.
\(g\in \Pi_{\mathcal{T}}\) iff no matter what the current player does, the opponent can achieve an outcome from \(\mathcal{T}\).
Definition 3. For a combinatorial game \(\mathcal{G}\) and ‘target outcome’ \(\mathcal{T} \subseteq \Omega\) we define \(\Sigma_{\mathcal{T}}, \Pi_{\mathcal{T}}\subseteq \mathcal{G}\) by:
\(g\in \Sigma_{\mathcal{T}}\) iff either \(g\) is finished and \(\mathcal{O}(g)\in\mathcal{T}\), or \(g\) is not finished and there is some move \(g\xrightarrow{\sigma} g'\) with \(g'\in \Pi_{\mathcal{T}}\).
\(g\in \Pi_{\mathcal{T}}\) iff either \(g\) is finished and \(\mathcal{O}(g)\in\mathcal{T}\), or \(g\) is not finished and \(g'\in \Sigma_{\mathcal{T}}\) for any move \(g\xrightarrow{\sigma} g'\).
It is not a priori clear that this definition is well-founded; if we completely unfold the recursive definition of \(g\in \Sigma_{\mathcal{T}}\), why might we not end up with an infinite recursion tree leaving us unable to decide whether \(g\in \Sigma_{\mathcal{T}}\) or not? This problem, however, does not occur, since games do not loop nor go on forever. The recursion tree will have depth at most \(N(g)\), and so we end up always being able to decide whether \(g\in \Sigma_{\mathcal{T}}\) and whether \(g\in \Pi_{\mathcal{T}}\).
Note that the interpretation for \(g \notin \Sigma_{\mathcal{T}}\) is that the current player cannot make sure that the game ends in \(\mathcal{T}\) if their opponent makes the right moves. Logically, this should be equivalent to their opponent having a way to make sure the game ends in an outcome from \(\Omega\backslash \mathcal{T}\), whatever the current player does, that is, \(g\in \Pi_{\Omega\backslash \mathcal{T}}\). This is indeed the case.
Theorem 1. Given a combinatorial game \(\mathcal{G}\), and \(\mathcal{T} \subseteq \Omega\), we have \(\mathcal{G}\backslash \Sigma_{\mathcal{T}} = \Pi_{\Omega\backslash\mathcal{T}}\).
Proof. Let us write \(\overline{\mathcal{T}} := \Omega\backslash \mathcal{T}\) for brevity. Let \(g\in \mathcal{G}\). We’ll prove the following equation holds for all \(\mathcal{T}\) by strong induction over \(N(g)\).
\[\label{pisigma} g\notin\Sigma_{\mathcal{T}} \;\iff \;\;g\in\Pi_{\Omega\backslash \mathcal{T}}.\tag{1}\] When \(N(g)=0\), then \(g\in \mathcal{F}\), and so \(g\notin \Sigma_{\mathcal{T}}\) iff not \(\mathcal{O}(g) \in \mathcal{T}\) iff \(\mathcal{O}(g) \in \overline{\mathcal{T}}\) iff \(g\in \Pi_{\overline{\mathcal{T}}}\), for any \(\mathcal{T}\).
Suppose now that \(N(g)>0\), and that 1 holds for all \(g'\) with \(N(g')<N(g)\) and all \(\mathcal{T}\); we’ll show that 1 holds for \(g\) and all \(\mathcal{T}\) as well. Note that \(g\) is not finished, since \(N(g)>0\).
Given \(\mathcal{T}\), the following are equivalent to \(g\notin \Sigma_{\mathcal{T}}\):
there are no \(g'\) and \(\sigma\) with \(g\xrightarrow{\sigma}g'\) and \(g'\in \Pi_{\mathcal{T}}\);
for any \(g'\) and \(\sigma\) with \(g\xrightarrow{\sigma}g'\) we have \(g'\notin \Pi_{\mathcal{T}}\); and (using the induction hypothesis here, and the fact that \(N(g')<N(g)\))
for any \(g'\) and \(\sigma\) with \(g\xrightarrow{\sigma}g'\) we have \(g'\in \Sigma_{\overline{\mathcal{T}}}\).
Since the latter item is equivalent to \(g\in \Pi_{\overline{\mathcal{T}}}\), we have proven 1 by induction. ◻
Corollary 1 (Zermelo). Given a combinatorial game \(\mathcal{G}\) and a partition of the outcome set \(\Omega = \Omega_X \sqcup \Omega_O \sqcup \Omega_T\), where an outcome in \(\Omega_X\) is interpreted as a win for \(X\), \(\Omega_O\) as a win for \(O\), and \(\Omega_T\) a tie. Then for a position \(g\) of \(\mathcal{G}\) where the current player is \(X\) exactly one of the following three mutually exclusive cases holds:
\(g \in \Sigma_{\Omega_X}\) — the current player \(X\) can force a win;
\(g \in \Pi_{\Omega_O}\) — their opponent \(O\) can force a win;
\(g \in \Sigma_{\Omega_T \sqcup \Omega_{X}}\) and \(g \in \Pi_{\Omega_T \sqcup \Omega_{O}}\) — both players can prevent a loss.
(The same result holds for when \(O\) is the current player, mutatis mutandis.)
See Appendix 7. ◻
Note that if there are no ties, that is \(\Omega_T=\varnothing\), only cases 1 and 2 can hold.
A special case of this corollary is where \(g = 0\). We can therefore classify games on the case in which their starting position falls into. For example, tic-tac-toe falls in case 3: neither the starting player \(X\) nor its opponent \(O\) can always guarantee a win, which means that they can both prevent a loss.
Before we can move to quantization of a combinatorial game we require two properties of a combinatorial game. First, we need some notion of injectivity, as described above. We now define injective combinatorial games and later in Lemma 1 we will show that this requirement is sufficient to ensure any classical move has some equivalent unitary quantum move.
Definition 4. We call a combinatorial game \(\mathcal{G}\) injective when the transition map \(\Gamma\colon \mathcal{G}\times \Sigma\rightarrow \mathcal{G}\cup\{\perp\}\) is injective on valid moves, that is, \(\Gamma(g,\sigma)=\Gamma(h,\pi)\neq \perp\) implies \(g=h\) and \(\sigma=\pi\).
To define a quantum variant, we need not only injectivity of the game, and the fact that the game ends after a set number of moves (condition [games-end] of Def. 1), but also that that number of moves can always be played:
Definition 5. We call a combinatorial game \(\mathcal{G}\) fixed-length when there is a natural number \(N\) such that not only for any sequence \(g_0 \xrightarrow{\sigma_1} \cdots \xrightarrow{\sigma_N} g_N\) of \(N\) moves we have \(g_N \in \mathcal{F}\), but also that for any sequence \(0 =: g_0 \xrightarrow{\sigma_1} \cdots \xrightarrow{\sigma_{M}} g_{M}\) of \(M<N\) moves there is still some move \(\smash{g_{M}\xrightarrow{\sigma_{M+1}} g_{M+1}}\) that can be played (even when \(g_M\) is already finished).
Any combinatorial game can be modified to become injective and of fixed-length, without fundamentally changing the gameplay. This follows from the fact that the modified game is bisimilar (see Definition 6) to the original one (see Corollary 3 and Proposition [prop:guaranteeable32sets32are32equivalent32for32bisimilar32games]). Details of this construction can be found in Appendix 8, but we will introduce the notion of bisimilarity here.
The idea of a bisimulation between two games \(\mathcal{G}_1\) and \(\mathcal{G}_2\) is that it allows one to translate a strategy for one game into another. Every move in \(\mathcal{G}_1\) (either from the starting player or their opponent) can be translated into an equivalent move in \(\mathcal{G}_2\), and vice versa.
Definition 6. A bisimulation \(\sim\) between combinatorial games \(\mathcal{G}_1\) and \(\mathcal{G}_2\) with the same outcome set \(\Omega\) is a relation \(\sim \subseteq \mathcal{G}_1\times\mathcal{G}_2\) such that \(0_{\mathcal{G}_1} \sim 0_{\mathcal{G}_2}\), and:
Given \(g_1 \sim g_2\) we have \(g_1\in \mathcal{F}\) iff \(g_2\in \mathcal{F}\), and then \(\mathcal{O}(g_1)=\mathcal{O}(g_2)\);
Given \(g_1 \sim g_2\) with \(g_1 \notin \mathcal{F}_1\) (iff \(g_2 \notin \mathcal{F}\)), we have:
If \(g_1\xrightarrow{\sigma_1} g_1'\), then \(g_2\xrightarrow{\sigma_2} g_2'\) for some \(\sigma_2\) and \(g_2'\) with \(g_1'\sim g_2'\).
If \(g_2\xrightarrow{\sigma_2} g_2'\), then \(g_1\xrightarrow{\sigma_1} g_1'\) for some \(\sigma_1\) and \(g_1'\) with \(g_1'\sim g_2'\).
When such a bisimulation exists, we call the games \(\mathcal{G}_1\) and \(\mathcal{G}_2\) bisimilar, and we write \(\mathcal{G}_1 \sim \mathcal{G}_2\).
Bisimilar games have the same gameplay (for proof see Appendix 7):
Let \(\sim\) be a bisimulation between games \(\mathcal{G}_1\) and \(\mathcal{G}_2\) with the same outcome set \(\Omega\), and let \(\mathcal{T}\subseteq \Omega\) be some target outcome. Then: \[\label{bisimilarity-implies-equistrategy} g_1 \sim g_2 \quad \implies \begin{cases} \quad g_1 \in \Sigma_{\mathcal{T}} & \iff \quad g_2 \in \Sigma_{\mathcal{T}}\\ \quad g_1 \in \Pi_{\mathcal{T}} & \iff \quad g_2 \in \Pi_{\mathcal{T}} \end{cases}.\tag{2}\]
Below we’ll define a quantum variant \(\mathcal{G}^Q\) of a combinatorial game \(\mathcal{G}\). In this definition we’ve very explicitly distinguished the components of the quantum and classical games using the \(Q\) and \(C\) superscripts (e.g. \(\Sigma^Q\) and \(\Sigma^C\)). In the rest of the text, we’ll often drop the \(C\) superscript (just writing \(\Sigma\) for \(\Sigma^C\)).
Definition 7. Let \(\mathcal{G}\) be a fixed-length and injective combinatorial game such that the positions can be encoded using length \(L\) bitstrings, so \(\mathcal{G}\subseteq \{0,1\}^L\). We call such combinatorial games quantizable. The quantum variant \(\mathcal{G}^Q\) of \(\mathcal{G}=:\mathcal{G}^C\) is the combinatorial game with:
Set \(\Sigma^Q\) of possible moves, defined as the set of all \(2^L\times 2^L\) unitaries \(U\);
Set \(\mathcal{G}^Q\) of possible positions defined as the superpositions \[\textstyle \ket\varphi\,= \,\sum_{g\in \mathcal{G}^C} \alpha_g \ket{g} \qquad\text{so}\qquad \sum_{g\in \mathcal{G}^C} \left|\alpha_g\right|^2=1\] that are reachable from the starting position \(\ket{0}\) using the moves from \(\Sigma^Q\).
Given such a position \(\ket\varphi\), we denote by \(\text{Supp}_{}{\ket\varphi}\) the support of \(\ket\varphi\), the set of all classical positions \(g\in\mathcal{G}^C\) with \(\alpha_g \neq 0\);
Set \(\mathcal{F}^Q\) of finished positions defined as the positions \(\ket\varphi\) with \(\text{Supp}_{}(\ket{\varphi})\subseteq \mathcal{F}^C\);
Transition map \(\Gamma: \mathcal{G}^Q \times \Sigma^Q \rightarrow \mathcal{G}^Q\) defined by
\[\Gamma(\ket{\varphi}, U) = \begin{cases} {U \ket{\varphi}}, \text{whenever U is a valid move on position}~ \ket\varphi \\ =\perp, \text{otherwise}. \end{cases}\] We say that a move \(U\) is valid2 on a position \(\ket\varphi\) if \(\ket\varphi\) is not finished and \(U\ket{\varphi}\) is a superposition of positions in \(\mathcal{G}^C\) and for all \(g'\in \text{Supp}_{}(U\ket{\varphi})\) we have \(g\xrightarrow{\sigma} g'\) for some \(\sigma\in \Sigma^C\) and \(g \in \text{Supp}_{}(\ket\varphi)\);
Outcome set \(\Omega^Q\) defined as the set of probability distributions on classical outcomes \(\Omega^C\), i.e., \[\Omega^Q\; :=\;\mathcal{D}(\Omega^C)\;=\;\textstyle \{\; \mu \colon \Omega^C\to [0,1]\;\text{such that} \;\sum_{\omega\in \Omega^C} \mu(\omega)=1\; \};\]
Outcome function \(\mathcal{O}:\mathcal{F}^Q\rightarrow \Omega^Q\) given by \(\mathcal{O}\bigl(\,\sum_{g\in \mathcal{G}^C} \alpha_g \ket{g}\;\bigr)(\omega) \;= \; \sum_{\substack{g\in \mathcal{G}^C \\ \mathcal{O}(g)=\omega}} \left|\alpha_g\right|^2;\)
Player-to-move map given by \(\mathrm{turn}(\ket{\varphi}) = \mathrm{turn}(g)\) for any (and all) \(g\in \text{Supp}_{}(\ket{\varphi})\). (See Remark [cg-turn-wd] below for why this is well-defined.)
That \(\mathrm{turn}\) is well-defined in the sense that \(\mathrm{turn}(g_1)=\mathrm{turn}(g_2)\) for any \(g_1,g_2\in \text{Supp}_{}{\ket{\varphi}}\) follows from the fact that \(\ket\varphi\) is reachable by a sequence of, say, \(M\) valid (quantum) moves starting at \(\ket0\). This implies that \(g_1\) (and also \(g_2\)) can be obtained using a sequence of \(M\) classical moves starting at \(0\). If \(M\) is even, \(\mathrm{turn}(g_1)=X=\mathrm{turn}(g_2)\), and if \(M\) is odd, \(\mathrm{turn}(g_1)=O=\mathrm{turn}(g_2)\).
The fact that \(\mathcal{G}^Q\) obeys the six conditions laid out for combinatorial games in Definition 1 is pretty straightforward, except for condition [no-moves-implies-finished], which demands that if a (super)position \(\ket\varphi\) of \(\mathcal{G}^Q\) is not finished, then there must still be some valid move \(U\) on it. To see why this is the case, first note that there must be a component \(g\in \text{Supp}_{}(\ket\varphi)\) of \(\ket\varphi\) that is not finished, \(g\notin \mathcal{F}\). Since the original game \(\mathcal{G}\) obeys condition [no-moves-implies-finished], there must be a valid move on \(g\) in \(\mathcal{G}\). Since \(\mathcal{G}\) is of fixed-length, there is, in fact, still a valid move \(\smash{g'\xrightarrow{\omega(g')}\dotsc}\) on every \(g'\in \text{Supp}_{}(\ket\varphi)\) and not just on \(g\). Now we will see in Lemma 1 below that this map \(\omega\colon \text{Supp}_{}(\ket\varphi)\rightarrow \Sigma\) can be turned into a unitary \(U\) that is a valid move on \(\ket\varphi\). Hence \(\mathcal{G}^Q\) obeys condition [no-moves-implies-finished].
If \(\mathcal{G}\) is not injective, then we might still try to define \(\mathcal{G}^Q\), but the resulting game \(\mathcal{G}^Q\) might not obey condition [no-moves-implies-finished]. Indeed, consider the game \(\mathcal{G}\) with four states \(0:=00\), \(1:=01\), \(2:=10\) and \(F:=11\) from \(\{0,1\}^2\), where \(0\) is the starting state, and three moves \(\{1,2,\bullet\}\), with the following transitions (and no other valid moves), as depicted below, on the right. Here, \(\mathrm{turn}(0)=\mathrm{turn}(F)=X\), and \(\mathrm{turn}(1)=\mathrm{turn}(2)=O\). The only finished state in this game is \(F\). For this example, the outcome set and function do not really matter, so let’s say that \(\Omega=\{42\}\) and \(\mathcal{O}(F)=42\). This is clearly a non-injective combinatorial game of fixed-length, \(N=2\).
In the quantum variant of this game we can reach the state \(\ket{\varphi} = \frac{1}{\sqrt{2}}(\ket{1} + \ket{2})\) from the starting position \(\ket{0}\) with the unitary \(U\) given by the circuit on the right. This \(U\) is a valid move in \(\mathcal{G}^Q\) on \(\ket{0}\), because \(\ket\varphi\) is a superposition of states \(1\) and \(2\), which can both be reached from \(0\) in \(\mathcal{G}\) in one step.
& & & &
& & & &
Note that this state \(\ket\varphi\) is not finished in \(\mathcal{G}^Q\), because \(1\) and \(2\) are not finished in \(\mathcal{G}\). However, there is no valid move \(U\) on \(\ket\varphi\). Indeed, what can \(U\ket{1}\) be? For \(U\) to be a valid move on \(\ket\varphi\), \(U\ket{1}\) must be a superposition of \(\ket{F}\), since \(1\xrightarrow{\bullet}F\) is the only valid move in \(\mathcal{G}\). So \(U\ket{1}=\alpha_1\ket{F}\) for some \(\alpha_1\in\mathbb{C}\) with \(\left|\alpha_1\right|=1\). Similarly, \(U\ket{2} = \alpha_2\ket{F}\) for some \(\alpha_2\in\mathbb{C}\) with \(\left|\alpha_2\right|=1\). But then \(U(\alpha_1^{-1}\ket{1})=\ket{F}=U(\alpha_2^{-1}\ket{2})\), which contradicts the injectivity of the unitary \(U\). Hence no such valid move \(U\) exists. Thus \(\mathcal{G}^Q\) is not a combinatorial game, for this non-injective \(\mathcal{G}\).
To show that \(\mathcal{G}^Q\) is an extension of \(\mathcal{G}^C\), we need the following.
Definition 8. A move \(U\in \Sigma^Q\) on a position \(\ket{\varphi}\) in the quantum variant \(\mathcal{G}^Q\) of a combinatorial game is called classical if for every \(g\in \text{Supp}_{}(\ket{\varphi})\) there exists \(g' \in \mathcal{G}\) with \(U\ket{g}=\ket{g'}\).
Lemma 1. Let \(\mathcal{G}\) be a quantizable combinatorial game. Let \(S\subseteq \mathcal{G}\) be a subset of positions, and let \(\omega\colon S\to \Sigma\) be a map such that \(\omega(g)\) is a valid move on \(g\) for each \(g\in S\). One may think of \(\omega\colon S\to\Sigma\) as a (partial) strategy for a classical player: when faced with \(g\in S\), the move \(\omega(g)\) is to be made. There is a unitary \(U_\omega\) that implements this strategy, that is, \[\label{eq:cqm} U_\omega\ket{g} \;=\; \ket{\Gamma(g,\omega(g))}\qquad\text{for all }g\in S.\qquad{(1)}\] Moreover, \(U_\omega\) is a valid and classical move on every non-finished \(\ket\varphi\in \mathcal{G}^Q\) with \(\text{Supp}_{}\ket\varphi \subseteq S\).
See Appendix 9. ◻
Definition 9. Let \(\mathcal{G}\) be a quantizable combinatorial game. We denote by \(\mathcal{G}^{C\text{--}Q}\) the classical against quantum variant of \(\mathcal{G}^Q\) in which the starting player, \(X\), is restricted to classical moves while its opponent, \(O\), is not. Note that this restriction in moves of \(X\) makes some positions of the general quantum variant \(\mathcal{G}^{Q}\) unreachable in \(\mathcal{G}^{C\text{--}Q}\). (For example, under \(\mathcal{G}^{C\text{--}Q}\) the starting player \(X\) can not move from \(0\) to a proper superposition, while under \(\mathcal{G}^{Q}\) they can.)
The quantum against classical, \(\mathcal{G}^{Q\text{--}C}\) variant (where instead \(O\) is restricted to classical moves), and the classical against classical, \(\mathcal{G}^{C\text{--}C}\) variant (where both \(X\) and \(O\) are restricted to classical moves) are defined similarly. All three variants are a special case of the partially quantum variant, \(\mathcal{G}^{Q|P}\), of \(\mathcal{G}^{Q}\) in which both players may make quantum moves on the (super)positions from some set \(P\subseteq \mathcal{G}^{Q}\), but are restricted to classical moves on \(\mathcal{G}^Q\backslash P\).
With this conversion from classical to classical quantum moves we show that classical games are equivalent to their quantum variant restricted to classical moves (for proof see Appendix 7).
A quantizable combinatorial game \(\mathcal{G}\) is bisimilar to its classical versus classical quantum variant, \(\mathcal{G}\sim \mathcal{G}^{C\text{--}C} := \mathcal{G}^{Q|\emptyset}\).
Besides a definition of a quantum variant as a generalization of the classical game, we are interested in studying the advantage of a quantum player over a classical player. Surprisingly, it turns out that if one is able to play perfectly, there is no additional benefit to having access to quantum moves, see Theorem 2 below.
Theorem 2. Given a quantizable combinatorial game \(\mathcal{G}\), and a position \(\ket{\varphi}\) in any partially quantum variant \(\mathcal{G}^{Q|P}\) (think \(\mathcal{G}^{Q\text{--}C}\), \(\mathcal{G}^{C\text{--}Q}\), \(\mathcal{G}^{C\text{--}C}\) or \(\mathcal{G}^Q\) itself). Then for any ‘target outcome’ \(\mathcal{T}\subseteq\Omega\),
\[\begin{align} {3} \label{nqa-1} \text{Supp}_{}{\ket \varphi}\,\subseteq\,\Sigma_{\mathcal{T}}^C \qquad&\implies\qquad \ket{\varphi}\,\in\, \Sigma_{\mathcal{D}(\mathcal{T})}^{Q|P} \\ \label{nqa-2} \text{Supp}_{}{\ket \varphi}\,\subseteq\,\Pi_{\mathcal{T}}^C \qquad&\implies\qquad \ket{\varphi}\,\in\, \Pi_{\mathcal{D}(\mathcal{T})}^{Q|P} \end{align}\] {#eq: sublabel=eq:nqa-1,eq:nqa-2}
Proof. We prove by induction on the moves left in position \(\ket\varphi\) that statements ?? and ?? hold for all \(\mathcal{T}\).
Suppose that \(\ket\varphi\) has \(0\) moves left. Then \(\ket\varphi\) is definitely finished, hence all \(g\in \text{Supp}_{}{\ket\varphi}\) are finished. Let \(\mathcal{T}\) be given, and suppose that \(\text{Supp}_{}{\ket\varphi} \subseteq \Sigma_{\mathcal{T}}^C\). Then \(\mathcal{O}(g)\in\mathcal{T}\) for all \(g\in \text{Supp}_{}{\ket\varphi}\), and thus the distribution \(\mathcal{O}(\ket\varphi)\) is only non-zero on \(\mathcal{T}\), so \(\mathcal{O}(\ket\varphi)\in\mathcal{D}(\mathcal{T})\). Thus \(\ket\varphi \in \smash{\Sigma_{\mathcal{D}(\mathcal{T})}^{Q|P}}\). Hence ?? holds for \(\ket\varphi\). The proof that ?? holds for \(\ket\varphi\) is almost identical.
Now let \(\ket\varphi\) be again arbitrary, and suppose that \(\ket\varphi\) has \(N+1\) moves left. Further suppose that ?? and ?? hold for any \(\mathcal{T}\), and any \(\ket{\varphi'}\) with \(N\) moves left. We’ll show that ?? and ?? hold for \(\ket\varphi\) as well. First note that if \(\ket\varphi\) is finished, then ?? and ?? hold for the reasons mentioned above, so we may assume without loss of generality that \(\ket\varphi\) is not finished.
Statement ?? . Let \(\text{Supp}_{}{\ket\varphi}\subseteq \Sigma^C_{\mathcal{T}}\). This means that for each \(g\in \text{Supp}_{}{\ket\varphi}\) there is \(\hat{g}\in \Pi^C_{\mathcal{T}}\) such that \(g\xrightarrow{\sigma} \hat{g}\) for some \(\sigma\). Note that this is true also when \(g\) is already finished, because the classical game is fixed-length, so there is still a classical move from \(g\), and such a move on a finished position does not change the outcome, which thus remains in \(\mathcal{T}\).
Note that there is a unitary \(U\) with \(U\ket g = \ket{\hat{g}}\) for all \(g \in \text{Supp}_{}\ket\varphi\). Indeed, for each \(g\in\text{Supp}_{}\ket\varphi\) pick \(\sigma_g\) with \(g\smash{\xrightarrow{\sigma_g}}\hat{g}\), and apply Lemma 1 to the map \(\omega\colon g\mapsto \sigma_g\) on \(S:=\text{Supp}_{}\ket\varphi\). Note that this unitary \(U\) is a valid move on \(\ket\varphi\) because for each \(g\in \text{Supp}_{}\ket\varphi\) there is a \(\sigma\) with \(g\smash{\xrightarrow{\sigma}}\hat{g}\), by definition of \(\hat{g}\). Moreover, \(U\) is a classical move by Lemma 1, which makes \(U\) a valid move in \(\mathcal{G}^{Q|P}\), whether or not \(\ket\varphi \in P\). We claim that \(U\ket\varphi \in \smash{\Pi^{Q|P}_{\mathcal{D}(\mathcal{T})}}\) which implies that \(\ket\varphi \in \smash{\Sigma^{Q|P}_{\mathcal{D}(\mathcal{T})}}\). By the induction hypothesis, and specifically ?? , it suffices to show that \(\text{Supp}_{}(U\ket\varphi) \subseteq \Pi_{\mathcal{T}}^C\). Moreover, by Lemma 9 it suffices to show that \(\text{Supp}_{}(U\ket g) \subseteq \Pi_{\mathcal{T}}^C\) given \(g\in \text{Supp}_{}\ket{\varphi}\). But \(U\ket{g}=\ket{\hat{g}}\), so we just have to show that \(\hat{g} \in \Pi_{\mathcal{T}}^C\), but this we already know. Whence ?? holds for \(\ket\varphi\).
Statement ?? . Suppose that \(\text{Supp}_{}{\ket\varphi}\subseteq \Pi_{\mathcal{T}}^C\). We must show that \(\ket\varphi \in \smash{ \Pi_{\mathcal{D}(\mathcal{T})}^{Q|P}}\). That is, given a valid move \(U\) on \(\ket\varphi\) we must show that \(U\ket{\varphi}\in \smash{ \Sigma^{Q|P}_{\mathcal{D}(\mathcal{T})}}\). By the induction hypothesis, and specifically ?? , it suffices to show that \(\text{Supp}_{}(U\ket\varphi)\subseteq \Sigma^C_{\mathcal{T}}\). So let \(g'\in \text{Supp}_{}(U\ket\varphi)\) be given. Since \(U\) is a valid move on \(\ket\varphi\), there is some \(g\in \text{Supp}_{}\ket\varphi\) and \(\sigma\) with \(g\smash{\xrightarrow{\sigma}} g'\). Since \(g\in \text{Supp}_{}\ket\varphi\) and we assumed \(\text{Supp}_{}\ket\varphi \subseteq \Pi_{\mathcal{T}}^C\), this implies that \(g'\in\Sigma_{\mathcal{T}}^C\). Hence \(\text{Supp}_{}(U\ket\varphi)\subseteq \Sigma^C_{\mathcal{T}}\), and so ?? holds for \(\ket\varphi\). ◻
Since the quantum variant of a combinatorial game is also a combinatorial game, Zermelo’s theorem (Corollary 1) also holds for this quantum variant. However, we remark that this is not a very strong theorem in the quantum case. Since the outcome space of the quantum variant is the set of distributions on the classical outcome set, the partitions as in Zermelo’s theory contain uncertainty about the outcomes. A priori it is not clear whether we can partition the outcome set such that the guaranteed outcome does not contain distributions with uncertainty on the outcome. In the following corollary, we prove a stronger version of Zermelo’s theorem which states that we can ensure a deterministic outcome and moreover that this outcome coincides with the classical variant of the game. So, for example, if a win can be guaranteed for player X in the classical game, then it can also be guaranteed in the quantum variant.
We have Corollary 2 whose proof follows immediately from Corollary 1 and Theorem 2.
Corollary 2. Given a position \(g\) with \(\mathrm{turn}(g)=X\) in a quantizable combinatorial game \(\mathcal{G}\), and a partially quantum variant \(\mathcal{G}^{Q|P}\) of \(\mathcal{G}\), and a partition \(\Omega = \Omega_X\sqcup \Omega_O\sqcup \Omega_T\) of the outcome set of the classical game. Then exactly one of the following three mutually exclusive cases holds.
\(g\in\Sigma_{\Omega_X}\), and in that case \(\ket g \in \Sigma^{Q|P}_{\mathcal{D}(\Omega_X)}\).
\(g\in \Pi_{\Omega_O}\), and in that case \(\ket g \in \Pi^{Q|P}_{\mathcal{D}(\Omega_O)}\).
\(g\in \Sigma_{\Omega_X\sqcup \Omega_T}\) and \(g\in \Pi_{\Omega_O\sqcup \Omega_T}\), and in that case \(\ket g \in \Sigma^{Q|P}_{\mathcal{D}(\Omega_X \cup \Omega_T)}\) and \(\ket g \in \Pi^{Q|P}_{\mathcal{D}(\Omega_O \cup \Omega_T)}\).
We remark that just like with Zermelo’s theorem this statement holds in the particular case where \(\ket g= \ket 0\) and that in this case — since \(0 \in \mathcal{G}\) — we get that a classical game has some guaranteed outcome if and only if its quantum variant has the same outcome. This means that the outcomes a player can achieve (using perfect play) do not change when quantum moves are added to the mix, in any way. That is, a classical player (making all the right moves) is just as strong as their quantum counterpart.
The take-away from Corollary 2 is that quantum moves give no benefit against a classical player playing perfectly. Perfect play can be expected for a simple game like tic-tac-toe, but who knows which opening moves of chess are winning, and which ones are not? Interestingly, if a classical player is not able to play perfectly, a quantum player can fish for a mistake from its classical opponent by making superpositions of moves that it considers strong. When at some point it becomes clear that one of the components of the superposition is winning for the quantum player, they can ‘amplify’ this particular classical position (see Lemma 2) using what is technically a valid move in the quantum variant. This means that when playing against a quantum opponent, the classical player can’t afford to make any mistakes.
Lemma 2 (Flaw amplification). Given a position \(\ket\varphi\) in the quantum variant \(\mathcal{G}^Q\) of a combinatorial game \(\mathcal{G}^C\) and a target outcome \(\mathcal{T}\subseteq\Omega\). If \(g\in \Sigma_{\mathcal{T}}^C\) and \(g\) is not finished for some \(g\in \text{Supp}_{}{\ket\varphi}\), then \(\ket\varphi \in \Sigma_{\mathcal{D}(\mathcal{T})}^Q\).
Proof. Since \(g\in \Sigma_{\mathcal{T}}^C\) and \(g\) is not finished, there is some move \(g \smash{\xrightarrow{\sigma}} h\) with \(h\in \Pi_{\mathcal{T}}^C\). By Theorem 2 we have \(\ket{h}\in\Pi_{\mathcal{D}(\mathcal{T})}^Q\). So let \(U\) be a unitary with \(U\ket\varphi = \ket{h}\). To create such a unitary, extend \(\ket\varphi\) and \(\ket{h}\) to orthonormal bases \(\ket{e_1}:=\ket\varphi,\,\ket{e_2},\,\dotsc,\,\ket{e_{N}}\) and \(\ket{f_1}:=\ket{h},\,\ket{f_2},\,\dotsc,\,\ket{f_{N}}\), respectively, where \(N=2^L\) (see Definition 7 for “\(2^L\)”), and let \(U\) be defined by \(U\ket{e_n} = \ket{f_n}\) for all \(n\). This unitary \(U\) is a valid move on \(\ket\varphi\), for the simple reason that \(\text{Supp}_{}{(U\ket\varphi)}\equiv\{h\}\) and \(g\smash{\xrightarrow{\sigma}} h\). Whence \(\ket\varphi \in \Sigma_{\mathcal{D}(\mathcal{T})}^Q\). ◻
One could argue that this reveals not a cunning strategy for the quantum player, but perhaps that too many unitaries are considered valid quantum moves according to our Definition 7. The following notion would arguably have been more natural given the linearity of quantum mechanics. Let us call a unitary \(U\) completely valid on \(\ket\varphi\) if \(\ket\varphi\) is not finished and for each \(g\in \text{Supp}_{}{\ket\varphi}\), \(U\ket{g}\) is a superposition of positions in \(\{g'\in\mathcal{G}^C\colon g\xrightarrow{\sigma} g' \text{ for some } \sigma\in\Sigma^C\}\). Any such completely valid quantum move is also valid in the regular sense (by Lemma 9). Moreover, the classical moves constructed via Lemma 1 are completely valid. This means that our main Theorem 2 also holds if we opt for completely valid moves in the definition of the quantum variant \(\mathcal{G}^Q\). However, this restricts the power of the quantum player, and thus makes Theorem 2 weaker. Hence we did not opt for this more restricted notion of quantum move. However, if one ever gets the chance to play a game of chess on a quantum computer as a classical player, one should definitely demand that all moves be completely valid, precisely because the trick above cannot be played against you.
A fundamental problem in distributed networks is that of guaranteeing reliability of the whole system even in the case of failure or adversarial behaviour of some of its nodes. Often, this reliability needs to be preserved even if the adversarial nodes communicate false or contradictory information to the rest of the nodes. This is often modelled as achieving Byzantine consensus – a reference to the Byzantine generals problem [16]. Here, consensus means that:
All non-Byzantine (= well-behaving) nodes agree on the same decision value (Agreement).
If all non-Byzantine nodes had the same initial decision value, then the final decision value must be the same as the initial decision value (Validity).
Interestingly, this problem can be modelled as a classical combinatorial game. Here we give a sketch of the idea, and the more detailed modelling can be found in Appendix 10.
Our model uses the standard approach of modelling distributed networks as graphs, with each node having “internal” state, “incoming” and “outgoing” messages and “decision” value. Rounds are synchronous, and in each, all nodes do a state transition, with input the “internal” state and “incoming” message which changes the “internal” state and the “outgoing” messages (which become incoming in the next round). In our model, player X represents the well-behaving nodes and player O represents the Byzantine nodes. Player X has a strategy to play, which can be chosen at the beginning of the game, or hardcoded in the starting position. During each round, player X first delivers all messages and applies its chosen algorithm to all well-behaving nodes, after which player O applies some move to each of the Byzantine nodes. The winner of the game is determined by looking at all decision values of the well-behaving nodes after the last round and seeing whether they reach consensus. Note that there is no tying in this game.
For the quantum variant, the only meaningful version is where player X plays classically and player O plays quantumly. It tells us that given a topology and a number of Byzantine failure nodes if there exists a classical algorithm to guarantee consensus against classical failure nodes, then there also exists a classical algorithm to ensure consensus against quantum failure nodes. Furthermore, if we specify the classical algorithm used in the initial position we get that the algorithm that ensures consensus against the classical Byzantine nodes is precisely the algorithm that guarantees consensus against the quantum Byzantine nodes.
Our model of a combinatorial game of the Byzantine consensus might not be the most efficient. Indeed, Lamport’s solution [16] that can be seen as a combinatorial game requires a significant number of message passes. Nevertheless, if one plays it as a combinatorial game, our results are meaningful, and guarantee that there is no quantum advantage against honest parties that have a strategy that can classically always lead to consensus. This reduced efficiency is an acceptable trade-off for the strong guarantee it offers.
Note that the quantum variant of the Byzantine agreement problem has already been treated in the literature: Ben-Or et al. [17] provide a more efficient solution for honest parties, while Fitzi et al. [18] show an advantage for quantum well-behaving nodes in certain settings. In contrast, we provide a model that guarantees that a classical solution can be transferred to the quantum setting.
We have defined a quantum variant for a broad class of combinatorial games, including tic-tac-toe, chess, and checkers, and shown that perfect classical play remains invincible against a quantum opponent (Corollary 2). As an application, we saw classical Byzantine consensus algorithms that tolerate classical adversaries equally tolerate quantum ones. In practice, flawless play is not realistic, and the quantum player can exploit any mistake via flaw amplification (Lemma 2). This, however, relies on our permissive definition of valid quantum move; under the stricter notion of completely valid moves, this specific amplification technique does not apply.
Although formulated for two-player combinatorial games without chance, we expect the proof of Corollary 2 to generalize to any number of players. Moreover, by modelling chance and probabilistic strategies as moves by an additional player (e.g. ‘chance’, see [19]), we believe the result extends to these settings as well: any outcome that a classical player can guarantee would be preserved against a quantum opponent. Conversely, Meyer’s PQ Penny Flip game [20] demonstrates that imperfect information can enable a quantum player to guarantee outcomes that a classical player cannot. In summary, quantum advantage is real, but elusive.
We’d like to thank the anonymous reviewers for their valuable feedback. One reviewer in particular gave very detailed and helpful suggestions.
The maps \(\mathcal{T}\mapsto \Sigma_{\mathcal{T}}\) and \(\mathcal{T}\mapsto \Pi_{\mathcal{T}}\) are order preserving:
Lemma 3. Given some combinatorial game \(\mathcal{G}\), and \(\mathcal{S} \subseteq \mathcal{T} \subseteq \Omega\), we have: \[\Sigma_{\mathcal{S}} \,\subseteq\, \Sigma_{\mathcal{T}}\qquad\text{and}\qquad \Pi_{\mathcal{S}}\,\subseteq\,\Pi_{\mathcal{T}}\]
Proof. Let \(\mathcal{S},\mathcal{T}\subseteq \Omega\) be given. We prove by induction on \(N(g)\) that for any \(g\in \mathcal{G}\), \[\label{sigpiop} g\in \Sigma_\mathcal{S} \implies g\in \Sigma_\mathcal{T} \qquad\text{and}\qquad g\in \Pi_\mathcal{S} \implies g\in \Pi_\mathcal{T}.\tag{3}\] Suppose that \(N(g)=0\). Then \(g\) is finished. So if \(g\in \Sigma_{\mathcal{S}}\) we must have \(g\in \mathcal{S}\subseteq \mathcal{T}\), and thus \(g\in \Sigma_{\mathcal{T}}\). Similarly, \(g\in \Pi_{\mathcal{S}}\) implies \(g\in \Pi_{\mathcal{T}}\).
Next suppose that \(g\in \mathcal{G}\) with \(N(g)>0\) is given such that 3 holds for all \(g'\) with \(N(g')<N(g)\). Suppose further that \(g\in \Sigma_{\mathcal{S}}\). Then \(\smash{g\xrightarrow{\sigma} g'}\) for some \(\sigma\in\Sigma\) and \(g'\in \Pi_{\mathcal{S}}\). Then \(g'\in \Pi_{\mathcal{T}}\) by the induction hypothesis, and so \(g\in\Sigma_{\mathcal{T}}\). With a similar reasoning we get that \(g\in \Pi_{\mathcal{S}}\) implies \(g\in \Pi_{\mathcal{T}}\). Hence 3 holds for \(g\). ◻
of Corollary 1. Note that either \(g \in \Sigma_{\Omega_X}\) (case 1) holds or not, \(g \not\in \Sigma_{\Omega_X}\), which (by Theorem 1) is equivalent to \(g \in \Pi_{\Omega \backslash \Omega_X} = \Pi_{\Omega_T \sqcup \Omega_O}\). Similarly, either \(g\in \Pi_{\Omega_O}\) (case 2) holds, or otherwise \(g \in \Sigma_{\Omega_T \sqcup \Omega_X}\) (but not both). Note that if neither case 1 nor case 2 holds, we are in case 3. A priori there is the option that both case 1 and case 2 hold, but this does not actually happen. If \(g\in \Sigma_{\Omega_X}\) (case 1), then also \(g\in \Sigma_{\Omega_T \sqcup \Omega_X}\) (by Lemma 3), which means that case 2 does not hold by the argumentation above. ◻
of Proposition [prop:guaranteeable32sets32are32equivalent32for32bisimilar32games]. We only have to prove the equivalence involving \(\Sigma_{\mathcal{T}}\); the equivalence involving \(\Pi_{\mathcal{T}}\) follows from it by Theorem 1. We use induction over \(N(g_1)\). Let \(g_1\) be given.
Suppose that \(N(g_1)=0\), and let \(g_2\) with \(g_1 \sim g_2\) be given. Then \(g_1 \in \mathcal{F}\), and thus \(g_2 \in \mathcal{F}\) and \(\mathcal{O}(g_1)=\mathcal{O}(g_2)\) (since \(g_1\sim g_2\)). Now, we have \(g_1 \in \Sigma_{\mathcal{T}}\) iff \(\mathcal{O}(g_1)\equiv \mathcal{O}(g_2) \in \mathcal{T}\) iff \(g_2 \in \Sigma_{\mathcal{T}}\).
Suppose now that \(N(g_1) > 0\), and that 2 already holds for all \(\tilde{g}_1\) with \(N(\tilde{g}_1) < N(g_1)\) (and any \(g_2\)). We’ll show that 2 holds for \(g_1\) as well.
Let \(g_2\) with \(g_1\sim g_2\) be given. Note that since \(N(g_1)>0\), we know that \(g_1\) is not finished, and since \(g_1 \sim g_2\), we know \(g_2\) is not finished either.
Suppose that \(g_1 \in \Sigma_{\mathcal{T}}\). We must show that \(g_2\in\Sigma_{\mathcal{T}}\) as well. Since \(g_1\) is not finished and \(g_1\in \Sigma_{\mathcal{T}}\) there is a move \(g_1 \xrightarrow{\sigma_1} g_1'\) such that \(g_1' \in \Pi_{\mathcal{T}}\). Since \(g_1\sim g_2\) there is a move \(g_2 \xrightarrow{\sigma_2} g_2'\) such that \(g_1'\sim g_2'\). Since \(N(g_1')<N(g_1)\), we know that equation 2 already holds for \(N(g_1')\). In particular, \(g_2' \in \Pi_{\mathcal{T}}\). This means that from \(g_2\) we can move into \(\Pi_{\mathcal{T}}\), so \(g_2\in\Sigma_{\mathcal{T}}\).
Suppose instead that \(g_2 \in \Sigma_{\mathcal{T}}\); we must show that \(g_1 \in \Sigma_{\mathcal{T}}\). Since \(g_2\) is not finished, we know there is some move \(g_2 \xrightarrow{\sigma_2} g_2'\in \Pi_{\mathcal{T}}\). Since \(g_1\sim g_2\), and \(g_2\) is not finished, there is some move \(g_1 \xrightarrow{\sigma_1} g_1'\) with \(g_1'\sim g_2'\). Thus \(g_1'\in \Pi_{\mathcal{T}}\) since 2 already holds for \(g_1'\). Thus \(g_1\in \Sigma_{\mathcal{T}}\). ◻
To make a game injective, we employ the following construction.
Definition 10. The transcribed variant \(\mathcal{G}_{tr}\) of a combinatorial game \(\mathcal{G}\) is defined as follows.
As positions, \(\mathcal{G}_{tr}\) has transcripts, pairs \((g,R)\in \mathcal{G}\times \Sigma^*\), where \(g\in\mathcal{G}\) and \(R\equiv (R_1,\dotsc,R_n)\) is a sequence of moves in \(\mathcal{G}\) from \(0\) to \(g\), so \(0 \smash{\xrightarrow{R_1} g_1 \xrightarrow{R_2} \dots \xrightarrow{R_n}} g\).
\(\mathcal{G}_{tr}\) has the same set of moves, \(\Sigma\), as \(\mathcal{G}\), and its transition map* is given by \[{\Gamma_{tr}}(\,(g, (R_1,\dotsc,R_n)), \,\sigma\,)\; =\; \begin{cases} (\,\Gamma(g, \sigma), \,(R_1,\dotsc,R_n,\sigma)\,) &\text{if } \Gamma(g, \sigma )\neq \perp,\\ \perp &\text{otherwise.} \end{cases}\] The starting position of \(\mathcal{G}_{tr}\) is simply \((0,())\).*
\(\mathcal{G}_{tr}\) has the same outcome set, \(\Omega\), as \(\mathcal{G}\). A position \((g,R)\) in \(\mathcal{G}_{tr}\) is finished when \(g\) is finished in \(\mathcal{G}\), and in that case the outcome is given by \(\mathcal{O}((g,R))=\mathcal{O}(g)\).
Finally, \(\mathrm{turn}((g,R))=\mathrm{turn}(g)\).
The proof that \(\mathcal{G}_{tr}\) obeys the six conditions we put on a combinatorial game (see Definition 1) is easy, and omitted. What’s more important is that \(\mathcal{G}_{tr}\) is injective:
Lemma 4. The transcribed variant \(\mathcal{G}_{tr}\) of a combinatorial game \(\mathcal{G}\) is injective.
Proof. Let \((g, R), (h, S) \in \mathcal{G}_{tr}\) and \(\sigma, \pi \in \Sigma\) such that \({\Gamma_{tr}}((g, R), \sigma) = {\Gamma_{tr}}((h, S), \pi) \neq \perp\) be given. We must show that \((g,R)=(h,S)\) and \(\sigma=\pi\).
Write \(R\equiv(R_1,\dotsc,R_n)\) and \(S\equiv (S_1,\dotsc,S_m)\). Then by definition of \({\Gamma_{tr}}\) we get \[(\Gamma(g, \sigma), (R_1,\dotsc,R_n,\sigma))\;=\;(\Gamma(h, \pi), (S_1,\dotsc,S_m,\pi)),\] which implies that \(\sigma=\pi\) and \(R = S\). Since therefore \(g\) and \(h\) are reached starting at \(0\) by the same sequence of moves \(R=S\), we have \(g=h\). Hence \(\mathcal{G}_{tr}\) is injective. ◻
A combinatorial game can be made fixed length as follows.
Definition 11. The extended variant \(\mathcal{G}_{ext}\) of a comb. game \(\mathcal{G}\) is defined as follows.
The game \(\mathcal{G}_{ext}\) basically has the same positions as \(\mathcal{G}\), except that finished positions are duplicated so that either \(X\) or \(O\) can be the player-to-move on them: \[\mathcal{G}_{ext} \;= \; \{ \,(g,\mathrm{turn}(g))\,\colon\,g\in \mathcal{G}\backslash\mathcal{F}\,\}\; \cup\;\{\,(g,P)\,\colon\, g\in\mathcal{F},\, P\in \{X,O\}\,\} \;\subseteq\;\mathcal{G}\times \{X,O\}.\] The starting position is \((0,X)\), and on a position \((g,P)\), the player-to-move is just \(\mathrm{turn}((g,P))=P\).
\(\mathcal{G}_{ext}\) adds one additional move, \(\bullet\), (the ‘extension move’) to \(\mathcal{G}\), so \(\Sigma_{ext}=\Sigma\cup\{\bullet\}\). This extension move can be made on any finished position \(g\in\mathcal{F}\), and will only switch the player, so \[\Gamma((g,P),\bullet)\;=\; (g,\overline{P}),\] where \(\overline{X}=O\) and \(\overline{O}=X\). For a move \(\sigma \in \Sigma\) from the original game \(\mathcal{G}\), the transition map* is given by \(\Gamma((g,P),\sigma)\;=\; (\,\Gamma(g,\sigma),\,\overline{P}\,).\)*
\(\mathcal{G}_{ext}\) has the same outcome set \(\Omega\) as \(\mathcal{G}\). A position \((g,P)\) is finished* when \(g\) is finished, and in that case \(\mathcal{O}((g,P)) = \mathcal{O}(g)\).*
That the extended variant of a combinatorial game itself obeys the six conditions of Definition 1 is straightforward to check. Recall that the “games end” condition [games-end] only requires that any sequence of \(N\) moves results in a finished position. Nothing in our definition of combinatorial game prohibits moves on finished positions, like the extension move \(\bullet\) (as long as the outcome stays the same.)
What’s special is that \(\mathcal{G}_{ext}\) is also fixed length:
Lemma 5. The extended variant \(\mathcal{G}_{ext}\) of a combinatorial game \(\mathcal{G}\) is fixed length.
Proof. There is a number \(N\) for the game \(\mathcal{G}\) such that any sequence of \(N\) moves in \(\mathcal{G}\) from \(0\) results in a finished position. Clearly, the same will be true for this \(N\) in \(\mathcal{G}_{ext}\). But in \(\mathcal{G}_{ext}\) we also have that in any position \((g,P)\) there is still a move that can be made. Indeed, either \((g,P)\) (and thus \(g\)) is not finished, and therefore there must already have been a move from \(g\) in \(\mathcal{G}\) (which can be made on \((g,P)\) in \(\mathcal{G}_{ext}\) too), or \((g,P)\) (and thus \(g\)) is finished, and we can thus make the extension move \((g,P)\xrightarrow\bullet(g,\overline{P})\). ◻
To make combinatorial game both injective and of fixed-length, one first adds the extension move, and then adds the transcripts, see the proposition below. The other way around does not work: the extended variant of a combinatorial game is generally not injective.
The transcribed variant \(\mathcal{G}_{tr}\) of a fixed-length combinatorial game \(\mathcal{G}\) is of fixed-length too. In particular, \((\mathcal{G}_{ext})_{tr}\) is both injective and fixed length.
Proof. Since \(\mathcal{G}\) is fixed length, there is some number \(N\) such that any sequence of \(N\) moves from \(0\) results in a finished position in \(\mathcal{G}\), and after any \(M<N\) moves from \(0\) a move can still be made. It’s clear that a sequence of \(N\) moves in \(\mathcal{G}_{tr}\) results in a finished position too. Suppose \((g,R)\) is reachable from \((0,())\) in \(M<N\) moves. Then the exact same moves can be made in \(\mathcal{G}\) too to reach \(g\) from \(0\). In \(g\), there is a still a move that can be made and that move can be made on \((g,R)\) too, by definition of the transition map on \(\mathcal{G}_{tr}\). Hence \(\mathcal{G}_{tr}\) is fixed length. ◻
We now know how to make a combinatorial game both injective and fixed length, which are required for our definition of quantum variant (see Definition 7). When we speak, for example, of quantum tic-tac-toe, we do not actually mean the quantum variant of tic-tac-toe itself (which is not defined), but of the transcribed variant of the extended variant of tic-tac-toe. This extended and then transcribed variant is in gameplay, however, indistinguishable from the original variant, which we formalize below using the notion of bisimulation[21].
With this notion of bisimilarity between games we can show that transcribing or extending a game has no effect on gameplay.
Lemma 6. A combinatorial game \(\mathcal{G}\) and its transcribed variant \(\mathcal{G}_{tr}\) are bisimilar.
Proof. Define \(\sim \subseteq \mathcal{G}\times \mathcal{G}_{tr}\) by \(g \sim (h, R)\) iff \(g=h\). Then first of all, clearly \(0 \sim (0, ()) = 0_{tr}\). Now let \(g\sim (g,(\sigma_1,\dotsc,\sigma_n))\). Then \(\sim\) is a bisimulation, because, using the same numbering of conditions as in Definition 6:
We have \(g \in \mathcal{F}\) iff \((g, R) \in\mathcal{F}_{tr}\), and in that case \(\mathcal{O}(g) = \mathcal{O}((g,R))\), by definition.
Suppose \(g \not\in \mathcal{F}\).
If \(g \xrightarrow{\sigma} g'\), then we have the corresponding move \((g, (\sigma_1,\dotsc,\sigma_n)) \xrightarrow{\sigma} (g', (\sigma_1,\dotsc,\sigma_n,\sigma))\) with \(g'\sim (g',(\sigma_1,\dotsc,\sigma_n,\sigma))\).
If \((g, (\sigma_1,\dotsc,\sigma_n)) \xrightarrow{\sigma} (g', (\sigma_1,\dotsc,\sigma_n,\sigma))\) then we have the corresponding move \(g \xrightarrow{\sigma} g' \sim (g', (\sigma_1,\dotsc,\sigma_n,\sigma))\).
◻
Lemma 7. A combinatorial game \(\mathcal{G}\) and its extended variant \(\mathcal{G}_{ext}\) are bisimilar.
Proof. Define \(\sim\subseteq \mathcal{G}\times\mathcal{G}_{ext}\) by \(g\sim(h,P)\) iff \(g=h\). Then first of all, clearly \(0\sim(0,X)\equiv 0_{ext}\). Now, let \(g\sim(g,P)\) be given. The relation \(\sim\) is a bisimulation, because, using the same numbering of conditions as in Definition 6:
We have \(g \in \mathcal{F}\) iff \((g, P) \in \mathcal{F}_{ext}\), and in that case, \(\mathcal{O}((g,P))\equiv \mathcal{O}(g)\), by definition.
Suppose \(g \not\in \mathcal{F}\)
When \(g \xrightarrow{\sigma} g'\) for some \(\sigma \in \Sigma\), we have a corresponding move \((g,P)\xrightarrow\sigma (g',\overline{P})\), with \(g'\sim (g',\overline{P})\).
When \((g,P)\xrightarrow\sigma (g',P')\), we know \(\sigma\neq \bullet\) (since \(g\notin \mathcal{F}\)), so we have a corresponding move \(g\xrightarrow\sigma g'\) in \(\mathcal{G}\), with \(g'\sim(g',P')\).
◻
Whence \(\mathcal{G}\sim \mathcal{G}_{ext}\sim (\mathcal{G}_{ext})_{tr}\). To conclude that \(\mathcal{G}\sim (\mathcal{G}_{ext})_{tr}\), we need the fact that bisimilarity is a transitive relation on games.
Lemma 8. The bisimulation relation \(\sim\) is transitive, i.e. if \(\mathcal{G}_1 \sim \mathcal{G}_2\) and \(\mathcal{G}_2 \sim \mathcal{G}_3\) then \(\mathcal{G}_1 \sim \mathcal{G}_3\), for combinatorial games \(\mathcal{G}_1, \mathcal{G}_2\) and \(\mathcal{G}_3\).
Proof. Let the bisimulations between \(\mathcal{G}_1\) and \(\mathcal{G}_2\) and between \(\mathcal{G}_2\) and \(\mathcal{G}_3\) both be denoted by \(\sim\). We define the bisimilarity relation between \(\mathcal{G}_1\) and \(\mathcal{G}_3\) by \(g_1 \sim g_3\) iff \(g_1 \sim g_2\) and \(g_2 \sim g_3\).
We must now show that this relation is indeed a bisimulation. First, \(0_1 \sim 0_2\) and \(0_2 \sim 0_3\) so \(0_1 \sim 0_3\). Then, we go over the conditions as in Definition 6.
Let \(g_1 \in \mathcal{G}_1\) and \(g_3 \in \mathcal{G}_3\) such that \(g_1 \sim g_3\), then by definition there exists a \(g_2 \in \mathcal{G}_2\) such that \(g_1 \sim g_2 \sim g_3\).
\(g_1 \in \mathcal{F}_1\) iff \(g_2 \in \mathcal{F}_2\) iff \(g_3 \in \mathcal{F}_3\), and then \(\mathcal{O}(g_1) = \mathcal{O}(g_2) = \mathcal{O}(g_3)\).
Assume \(g_1 \not \in \mathcal{F}_1\), then:
If \(g_1 \xrightarrow{\sigma_1} g_1'\), then \(g_2 \xrightarrow{\sigma_2} g_2'\) for some \(\sigma_2\) and \(g_2'\), with \(g_1' \sim g_2'\). Since \(\mathcal{G}_2 \sim \mathcal{G}_3\) we also have that \(g_3 \xrightarrow{\sigma_3} g_3'\) for some \(\sigma_3\) and \(g_3'\) with \(g_2' \sim g_3'\). This gives that \(g_1' \sim g_3'\).
This case is analogous to (a).
So, \(\mathcal{G}_1 \sim \mathcal{G}_3\). ◻
Corollary 3. Any combinatorial game \(\mathcal{G}\) is bisimilar to its extended and then transcribed variant, \(\mathcal{G}\sim (\mathcal{G}_{ext})_{tr}\).
Lemma 9. Given a move \(U\) on a position \(\ket{\varphi}\) in the quantum variant of a quantizable combinatorial game \(\mathcal{G}\), we have \(\text{Supp}_{}(U\ket\varphi) \;\subseteq \;\bigcup_{g \in \text{Supp}_{}\ket \varphi}\text{Supp}_{}(U\ket g)\).
Proof. Let \(s\in \text{Supp}_{}(U\ket\varphi)\) be given. This means that \(\left<s \right| U \ket\varphi \neq 0\). Since \(\ket\varphi = \sum_{g\in\text{Supp}_{}\ket\varphi} \left<g\middle|\varphi\right>\ket{g}\), we get \(0\neq \left<s \right | U \ket\varphi \;= \;\sum_{g\in \text{Supp}_{}\ket\varphi} \left<g \middle| \varphi \right> \left<s\right| U \ket{g}\), and so there must be at least one \(g\) for which \(\left<s\right| U \ket{g}\neq 0\), that is, \(s\in \text{Supp}_{}(U\ket{g})\). ◻
of Lemma 1. Given \(g\in S\), write \(\hat{g} := \Gamma(g,\omega(g))\) and define \(\smash{\hat{S}}:=\{\Gamma(g,\omega(g))\colon g\in S\}\). Then \(\hat{\cdot}\) gives a bijection \(S\longrightarrow \smash{\hat{S}}\), using here that the game \(\mathcal{G}\) is injective. Recall that the positions of \(\mathcal{G}\) are encoded using length-\(L\) bitstrings, that is, \(\mathcal{G}\subseteq \{0,1\}^L\). Since there is a bijection from \(S\) to \(\smash{\hat{S}}\), the sets \(S\) and \(\smash{\hat{S}}\) have the same size. As a consequence, \(\{0,1\}^L\backslash S\) and \(\{0,1\}^L\backslash \smash{\hat{S}}\) have the same number of elements too. This means that \(\hat{\cdot}\colon S\to\smash{\hat{S}}\) can be extended to a permutation of \(\{0,1\}^L\). Pick such a permutation \(\hat{\cdot}\colon \{0,1\}^L\to\{0,1\}^L\) — it does not matter which one. Let \(U_\omega\) denote the unitary associated with this permutation, given by \(U_\omega\ket{w} = \ket{\hat{w}}\). Then, by definition, equation ?? holds.
Let non-finished \(\ket \varphi\in\mathcal{G}^Q\) with \(\text{Supp}_{}\ket\varphi\subseteq S\) be given. We claim that \(U_\omega\) is a valid move on \(\ket\varphi\). First, \(U_\omega\ket\varphi\) is a superposition of positions in \(\mathcal{G}^C\), since \(U_\omega\) maps each \(g\in\text{Supp}_{}\ket\varphi\subseteq S\subseteq \mathcal{G}\) to \(\hat{g}\in\mathcal{G}\). Second, let \(g'\in \text{Supp}_{}(U_\omega\ket\varphi)\) be given; we must find \(g\in \mathcal{G}\) and \(\sigma\in\Sigma\) with \(g\xrightarrow\sigma g'\). By Lemma 9, there is \(g\in\text{Supp}_{}\ket\varphi\) with \(g'\in \text{Supp}_{}(U_\omega\ket{g})\). Since \(g\in\text{Supp}_{}\ket\varphi\subseteq S\), we have \(U_\omega\ket{g}=\ket{\hat{g}}\), so \(g'=\hat{g}\). Since \(\smash{g\xrightarrow{\omega(g)}\hat{g}}\equiv g'\), \(U_\omega\) is a valid move on \(\ket\varphi\). That \(U_\omega\) is a classical move on \(\ket\varphi\) follows directly from ?? . ◻
of Proposition [classical-bisimilar]. We claim that the relation \(\sim \subseteq \mathcal{G}\times \mathcal{G}^{C\text{--}C}\) given by \(g \sim \ket{\varphi}\) iff \(\ket{\varphi}=\ket{g}\) is a bisimulation. Indeed, first of all, \(0 \sim 0\), because \(0\equiv \ket{0}\) is by definition the starting position of \(\mathcal{G}^{C\text{--}C}\). Second, we check the two numbered conditions of Definition 6:
Let \(g_1 \sim \ket{\varphi_2}\) be given. Then \(\ket{\varphi_2} = \ket{g_1}\) by definition of \(\sim\). Now, \(g_1\in\mathcal{F}\) iff \(\ket{g_1}\in\mathcal{F}^Q\), by definition of the quantum variant. If \(g_1\in \mathcal{F}\), then \(\mathcal{O}(\ket{g_1})=\mathcal{O}(g_1)\), again by definition of the quantum variant.
If \(g \xrightarrow{\sigma} g'\), then by Lemma 1 we get that \(\ket g \xrightarrow{U_\sigma} U_\sigma \ket g = \ket {g'}\), and \(g'\sim \ket{g'}\).
If \(\ket g \xrightarrow{U} \ket {\varphi'}\), then since \(U\) must be classical, \(U\ket{g}=\ket{\varphi'}\equiv \ket {g'}\) for some \(g'\in \mathcal{G}\). By definition of a valid quantum move, there is a \(\sigma\in \Sigma^C\) with \(g \xrightarrow{\sigma}g'(\sim \ket{\varphi'})\).
Hence we have a bisimulation, \(\mathcal{G}\sim \mathcal{G}^{C\text{--}C}\). ◻
We model the network as a graph \(G=(V,E)\), where nodes represent computing units and edges represent communication channels. We assume synchronous rounds and perfect communication channels.
Each node has a state, an element from the set \(\mathcal{S}\), that includes not only its internal state, but also the registers for incoming and outgoing messages, and its decision value from a set \(\mathcal{D}\). Every round, every node applies a local state-transition \(\mathcal{S}\rightarrow \mathcal{S}\), after which the system routes outgoing messages according to the network topology, \(G\). We denote the action of routing messages by \(\mathrm{sys}\colon \mathcal{S}^n \rightarrow \mathcal{S}^n\), where \(n = |V|\).
The Byzantine failure problem asks whether, in a network with up to \(f\) adversarial nodes, the remaining well-behaving nodes can reach consensus. Formally we require:
Agreement: all well-behaving nodes must end with the same decision value; and
Validity: if all honest nodes start with the same decision value, they must decide that value.
A commonly considered third requirement is “Termination”. By the finiteness requirement of quantizable games we only consider the Byzantine problem for a fixed finite number of rounds \(N\). This implicitly gives us the termination requirement.
We now show how this can be cast as a combinatorial game. Let player \(X\) represent the well-behaving nodes and player \(O\) represent the Byzantine nodes. The game \(\mathcal{G}_{BF}(f, G, N)\) is defined like so.
Definition 12. Let \(\mathcal{G}_{BF}(f, G, N)\) be the classical combinatorial game representing the Byzantine problem on network topology \(G\) with at most \(f\) failure nodes played for \(N\) turns.
A position is defined as a triple, \((\vec{s}, \mathcal{A}, B)\), the vector \(\vec{s} \in \mathcal{S}^n\) of states of all nodes, the algorithm \(\mathcal{A}\) the well-behaving nodes will follow, and the set \(B \subseteq V\) of Byzantine nodes. The game starts in state \((\vec{0}, NULL, \emptyset)\), where the algorithm and Byzantine have not yet been chosen. The initial state vector \(\vec{0}\) starts each node with empty message registers, no decision value, and empty internal state, except for a unique identifier for this node. The set of positions is formed by all positions which are reachable by the set of moves.
The set of moves is defined as \(\Sigma := \Sigma_{init} \cup \Sigma_{move}\). Where \(\Sigma_{move} := \{\sigma: \mathcal{S} \rightarrow \mathcal{S}\}\) (the set of local state transitions) and \(\Sigma_{init} := \{(\vec{d}, B)\;|\;\vec{d} \in \mathcal{D}^n, B \subseteq V, |B| \leq f\}\) (the set of initial problem configurations).
The game proceeds in two phases:
**Initialization:* Player \(X\) chooses an algorithm \(\mathcal{A} \in \Sigma_{move}\), yielding position \((\vec{0}, \mathcal{A}, \emptyset)\). Then player \(O\) chooses an initial set-up \((\vec{d}, B) \in \Sigma_{init}\), yielding position \((\vec{s}_0, \mathcal{A}, B)\), where \(\vec{s}_0\) is the result of setting the decision values in \(\vec{0}\) according to \(\vec{d}\).*
**Simulation:* At each subsequent round, player \(X\)’s move is fixed: first the application of the \(\mathrm{sys}\) function, then the pre-chosen move \(\mathcal{A}\). Where \(\mathcal{A}\) is only applied to the well-behaving nodes, \(V\setminus B\). Player \(O\) chooses any \(\sigma \in \Sigma_{move}\), which is only applied to the Byzantine nodes, \(B\).*
After \(N\) turns, player \(X\) wins iff consensus is reached i.e. agreement and validity; otherwise player \(O\) wins.
The important choice here is that player \(X\) commits to a strategy \(\mathcal{A}\) before it is known what nodes will fail or what the initial values are, effectively hiding this information from player \(X\).
Corollary 4. Let \(G\) be a network topology and \(f\) the maximum number of Byzantine nodes. If there exists a classical algorithm guaranteeing consensus against classical Byzantine nodes within \(N\) rounds, then there exists a classical algorithm guaranteeing consensus against quantum Byzantine nodes within \(N\) rounds.
Proof. A direct application of Corollary 2. ◻
One can adapt the definition to include player \(X\)’s choice for the algorithm used in the game definition. This would give that the algorithm that guarantees classical consensus is precisely the classical algorithm that guarantees consensus against the quantum failures.
The only meaningful quantum variant is \(\mathcal{G}^{C-Q}\) for this application, for two reasons. First, if player \(X\) plays as a quantum player it is restricted in its choice of algorithm. It may choose any unitary in the initialization phase, however this will still be encoded as a superposition of classical moves. Player \(O\) can then fix different initial values for each classical component, effectively forcing player \(X\) to play classically. Second, by the definition of valid quantum moves, player \(X\) still retains some freedom in its choice of move after the initial values have been specified. This is against the spirit of the Byzantine Generals problem.
These reasons might seem contradictory; arguing too much and too little freedom. The resolution is that the set of valid quantum moves is constrained by the allowed classical moves, but the set of valid classical moves is restricted too much. Simultaneously, within this restricted set of valid quantum moves, there is still freedom of choice, which violates the spirit of the problem.
And, of course, whether black has castled, etc.↩︎
This definition of ‘valid’ quantum move is very permissive to the quantum player. This is on purpose: the weaker the condition on the quantum player, the stronger the main result (Theorem 2) becomes. A more restrictive, and perhaps more natural notion of validity is discussed in Remark [completely-valid].↩︎