## Appendix B – The Physics of TiqTaqToe **NB: WORK IN PROGRESS** TiqTaqToe is based directly on quantum theory, and all moves are informed by quantum mechanical calculations. Those calculations are reproduced below for the benefit of the interested reader. The following sections assume familiarity with basic quantum mechanics and the Dirac notation. For a gentle introduction, see Nielsen and Chuang's celebrated introduction to [Quantum Computation and Quantum Information](https://www.cambridge.org/highereducation/books/quantum-computation-and-quantum-information/01E10196D0A682A6AEFFEA52D53BE9AE#overview). ### The Formalism We will interpret the pieces as spin-half particles, such as electrons existing in a discretized space, namely the nine squares of the board. We will identify $\triangle$ as spin-up and $\square$ as spin-down, and use subscripts to denote their location, with the squares numbered $1$ to $9$ from the top left to the bottom right. For example, if there is a classical $\triangle$ state in the first square (top left), this is denoted $\ket{\uparrow_1}$. We do not make a distinction based on who placed the piece on the board. Hence, there are eighteen possible basis states for each piece on the board: $ \ket{\uparrow_1},\, \ldots,\, \ket{\uparrow_9},\, \ket{\downarrow_1},\, \ldots,\, \ket{\downarrow_9}\, . $ The quantum state $\ket{\psi}$ describes the full state of all the pieces on the board. This state will in general be a tensor product of independent sub-states; if for instance all pieces are in a classical state, then $\ket{\psi}$ is just a tensor product of the respective basis states describing each piece. We will write the product ordered so that the state of the first piece placed is to the left and the state of the last piece placed is to the right. For example, the quantum state describing the following board[^2] ``` +--------------+--------------+--------------+ | | | | | /\ | | R---R | | / 4\ | | | 4 | | | g----g | | R---R | | | | | +--------------+--------------+--------------+ | | | | | | /\ | | | | / 4\ | | | | r----r | | | | | | +--------------+--------------+--------------+ | | | | | | | | | | | | | | | | | | | | +--------------+--------------+--------------+ ``` is given by $ \ket{\psi} = \ket{\uparrow_5}\ket{\downarrow_3}\ket{\uparrow_1}\, . $ Some pieces will be entangled, however, in which case their state is *non-separable*, meaning it can no longer be written as a tensor product of two independent states. For example, the quantum state describing the following board ``` +--------------+--------------+--------------+ | R---R | | R---R | | /\ | 2 | | | /\ | 2 | | | / 2\ R---R | | / 2\ R---R | | r----r | | r----r | | | | | +--------------+--------------+--------------+ | | | | | | /\ | | | | / 4\ | | | | r----r | | | | | | +--------------+--------------+--------------+ | | | | | | | | | | | | | | | | | | | | +--------------+--------------+--------------+ ``` is given by $ \ket{\psi} = \ket{\uparrow_5}\left( \frac{\ket{\uparrow_1}\ket{\downarrow_3} + \ket{\downarrow_1}\ket{\uparrow_3}}{\sqrt{2}} \right)\, . $ Still, since at most three pieces can be entangled a time (in the case of a twice half-entangled superposition state), it thankfully suffices to argue about one to three pieces at a time, rather than the full board. The *plus* and *minus* states are defined as follows: $ \ket{+_a} \coloneqq \frac{\ket{\uparrow_a} + \ket{\downarrow_a}}{\sqrt{2}}\, ,\quad \ket{-_a} \coloneqq \frac{\ket{\uparrow_a} - \ket{\downarrow_a}}{\sqrt{2}}\, . $ When using the rotated view/mode of observation, we use the following identities to rewrite the states in the $+/-$ basis: $ \ket{\uparrow_a} = \frac{\ket{+_a} + \ket{-_a}}{\sqrt{2}}\, ,\quad \ket{\downarrow_a} = \frac{\ket{+_a} - \ket{-_a}}{\sqrt{2}}\, . $ Note the symmetry. ### The Classical Move ``` Square a Square a +--------------+ +--------------+ | | | | | | | /\ | | | -> | / 4\ | | | | r----r | | | | | +--------------+ +--------------+ ``` Whenever Player 1 makes a classical move in square $a \in \{1, \ldots, 9\}$, they are adding a piece to the board in the state $\ket{\uparrow_a}$. Whenever Player 2 makes the move, they are adding a piece to the board in the state $\ket{\downarrow_b}$.[^4] A classical states only has one possible outcome under a standard observation, with amplitude $1$, so the probability of that outcome is $|1|^2 = 1$. Under the rotated mode of observation, we are making an observation in the $+/-$ basis, so we rewrite the state according to the rule above, such that the state becomes $ \frac{\ket{+_a} \pm \ket{-_a}}{\sqrt{2}}\, . $ There are two possible outcomes, each with probability $|\pm 1 / \sqrt{2}|^2 = 1/2$. ### The Superposition Move ``` Square a Square b Square a Square b +--------------+--------------+ +--------------+--------------+ | | | | | | | | | | /\ | /\ | | | | -> | / 2\ | / 2\ | | | | | r----r | r----r | | | | | | | +--------------+--------------+ +--------------+--------------+ ``` Whenever Player 1 makes a superposition move in two squares $a$ and $b$, they are adding a piece to the board in the state $ \frac{\ket{\uparrow_a} + \ket{\uparrow_b}}{\sqrt{2}}\, , $ and likewise for Player 2: $ \frac{\ket{\downarrow_a} + \ket{\downarrow_b}}{\sqrt{2}}\, . $ There are two possible outcomes, each with probability $|1 / \sqrt{2}|^2 = 1/2$. ### The Entangling Move ``` Square a Square b Square a Square b +--------------+--------------+ +--------------+--------------+ | | | | R---R | R---R | | /\ | | | /\ | 2 | | /\ | 2 | | | / 2\ | | -> | / 2\ R---R | / 2\ R---R | | r----r | | | r----r | r----r | | | | | | | +--------------+--------------+ +--------------+--------------+ ``` When e.g. Player 2 makes an entangling move on a piece in square $a$, they take a single-piece classical state $ \ket{\uparrow_a} $ and turn it into the entangled two-piece state $ \frac{\ket{\uparrow_a}\ket{\downarrow_b} + \ket{\uparrow_b}\ket{\downarrow_a}}{\sqrt{2}} $ for some open square $b$ of their choice. There are two possible outcomes: $\ket{\uparrow_a}\ket{\downarrow_b}$ and $\ket{\uparrow_b}\ket{\downarrow_a}$, each with probability $|1 / \sqrt{2}|^2 = 1/2$. The rules mention that the entangled states are unaffected by the change of basis (view/mode). It is a useful exercise to check this by rewriting the above state in the $+/-$ basis and verifying that the state you get is $ \frac{\ket{+_a}\ket{-_b} + \ket{+_b}\ket{-_a}}{\sqrt{2}}\, . $ ### The Half-Entangling Move ``` Square a Square b Square c +--------------+--------------+--------------+ | | | | | /\ | /\ | | | / 2\ | / 2\ | | | r----r | r----r | | | | | | +--------------+--------------+--------------+ Square a Square b Square c +--------------+--------------+--------------+ | R---R | | R---R | | /\ | 2 | | /\ | /\ | 2 | | -> | / 1\ R---R | / 2\ | / 1\ R---R | | r----r | r----r | r----r | | | | | +--------------+--------------+--------------+ ``` When e.g. Player 2 makes a half-entangling move on one half of a superposition state in square $a$, spread over squares $a$ and $b$, they take a single-piece superposition state $ \frac{\ket{\uparrow_a} + \ket{\uparrow_b}}{\sqrt{2}}\, , $ and turn it into the half-entangled two-piece state $ \frac{\ket{\uparrow_a}\ket{\downarrow_c} + \ket{\uparrow_c}\ket{\downarrow_a}}{2} + \ket{\uparrow_b}\frac{\ket{\downarrow_a} + \ket{\downarrow_c}}{2} $ for some open square $c$ of their choice. There are four possible outcomes: 1. $\ket{\uparrow_a}\ket{\downarrow_c}$ 2. $\ket{\uparrow_c}\ket{\downarrow_a}$ 3. $\ket{\uparrow_b}\ket{\downarrow_a}$ 4. $\ket{\uparrow_b}\ket{\downarrow_c}$ each with probability $|1 / 2|^2 = 1/4$. ### The Cancelling Move ``` Square a Square b Square a Square b +--------------+--------------+ +--------------+--------------+ | | | | /\ | R---R | | /\ | | | /\ /-2\ | /\ |-2 | | | / 2\ | | -> | / 2\ R----R| / 2\ R---R | | r----r | | | r----r | r----r | | | | | | | +--------------+--------------+ +--------------+--------------+ ``` When e.g. Player 2 makes an entangling move on a piece in square $a$, they take a single-piece classical state $ \ket{\uparrow_a} $ and turn it into the single-piece state $ \frac{\ket{\uparrow_a} - \ket{\uparrow_a}}{\sqrt{2}} + \frac{\ket{\uparrow_b} - \ket{\downarrow_b}}{\sqrt{2}} = \frac{\ket{\uparrow_b} - \ket{\downarrow_b}}{\sqrt{2}} = \ket{-_b} $ for some open square $b$ of their choice. In the standard basis, there are two possible outcomes, $\ket{\uparrow_b}$ and $\ket{\downarrow_b}$, each with probability $|\pm 1 / \sqrt{2}|^2 = 1/2$. In the $+/-$ basis there is a single outcome, namely $\ket{-_b}$, with probability $1$. If Player 1 performs the move on one of Player 2's pieces, the result will be $ \ket{\downarrow_a} \longrightarrow \frac{\ket{\downarrow_a} - \ket{\downarrow_a}}{\sqrt{2}} + \frac{\ket{\uparrow_b} + \ket{\downarrow_b}}{\sqrt{2}} = \frac{\ket{\uparrow_b} + \ket{\downarrow_b}}{\sqrt{2}} = \ket{+_b}\, . $ Like above, there are two possible outcomes in the standard basis, $\ket{\uparrow_b}$ and $\ket{\downarrow_b}$, each with probability $1/2$, whereas in the $+/-$ basis there is the single outcome $\ket{+_b}$ with probability $1$. ### The Half-Cancelling Move ``` Square a Square b Square c +--------------+--------------+--------------+ | | | | | /\ | /\ | | | / 2\ | / 2\ | | | r----r | r----r | | | | | | +--------------+--------------+--------------+ Square a Square b Square c +--------------+--------------+--------------+ | /\ | | R---R | | /\ /-2\ | /\ | /\ |-2 | | -> | / 1\ R----R| / 2\ | / 1\ R---R | | r----r | r----r | r----r | | | | | +--------------+--------------+--------------+ ``` When e.g. Player 2 makes a half-entangling move on one half of a superposition state in square $a$, spread over squares $a$ and $b$, they take a single-piece superposition state $ \frac{\ket{\uparrow_a} + \ket{\uparrow_b}}{\sqrt{2}}\, , $ and for some open square $c$ of their choice, turn it into the half-cancelled single-piece state $ r \cdot \left( \frac{\ket{\uparrow_a}}{2} - \frac{\ket{\uparrow_a}}{\sqrt{2}} + \frac{\ket{\uparrow_c}}{2} - \frac{\ket{\downarrow_c}}{\sqrt{2}} + \frac{\ket{\uparrow_b}}{\sqrt{2}} \right) $ $ = r \cdot \left( \frac{1 - \sqrt{2}}{2}\ket{\uparrow_a} + \frac{1}{2} \ket{\uparrow_c} - \frac{1}{\sqrt{2}} \ket{\downarrow_c} + \frac{1}{\sqrt{2}} \ket{\uparrow_b} \right)\, , $ where $r$ is a normalization constant ensuring that probabilities sum to one. The sum of probabilities inside the paranthesis evaluates to $ \left( \frac{1 - \sqrt{2}}{2} \right)^2 + \left( \frac{1}{2} \right)^2 + \left( \frac{-1}{\sqrt{2}} \right)^2 + \left( \frac{1}{\sqrt{2}} \right)^2 \approx 1.29\, , $ so for the probabilities to sum to $100\%$, we must set $r$ such that $ r^2 \approx \frac{1}{1.29} \approx 0.77\, . $ More exactly, a little algebraic manipulation gives that $ r = \sqrt{\frac{2}{4-\sqrt{2}}}\, . $ (Exercise: Check this.) Under a standard basis observation, there are four possible outcomes, each with the following probability: |Outcome|Amplitude|Probability| |:-----:|:-------:|:---------:| |$\ket{\uparrow_a}$|$\sqrt{\frac{2}{4-\sqrt{2}}} \cdot \frac{1 - \sqrt{2}}{2} = \frac{1 - \sqrt{2}}{\sqrt{2(4-\sqrt{2})}}$|$\Big( \frac{1 - \sqrt{2}}{\sqrt{2(4-\sqrt{2})}} \Big)^2 \approx 0.03$| |$\ket{\uparrow_c}$|$\sqrt{\frac{2}{4-\sqrt{2}}} \cdot \frac{1}{2} = \frac{1}{\sqrt{2(4 - \sqrt{2})}}$|$\Big( \frac{1}{\sqrt{2(4 - \sqrt{2})}} \Big)^2 \approx 0.19$| |$\ket{\downarrow_c}$|$\sqrt{\frac{2}{4-\sqrt{2}}} \cdot \frac{-1}{\sqrt{2}} = \frac{-1}{\sqrt{4-\sqrt{2}}}$|$\Big( \frac{-1}{\sqrt{4-\sqrt{2}}} \Big)^2 \approx 0.39$| |$\ket{\uparrow_b}$|$\sqrt{\frac{2}{4-\sqrt{2}}} \cdot \frac{1}{\sqrt{2}} = \frac{1}{\sqrt{4-\sqrt{2}}}$|$\Big( \frac{1}{\sqrt{4-\sqrt{2}}} \Big)^2 \approx 0.39$| Note the closeness of the latter three probabilities to one-fifth ($0.2$) and two-fifths ($0.4$), respectively. You may want to verify that, conditioned on the cancellation succeeding (first outcome excluded), renormalizing the state again makes the probabilities exactly into fifths, matching the procedure explained in [[TiqTaqToe with Interference]]. Finally, we check for successful half-cancellation by rolling two d6 and checking for snake-eyes, and indeed the probability of this outcome is $1/6 \cdot 1/6 = 1/36 \approx 0.03$. ##### Half-Cancelling and the Rotated Mode of Observation Recall that on Level 4 and 5, we begin the observation phase by identifying the location of the empty squares. If, from the possible outcomes in the table above, the piece was found to be in either square $a$ or $b$, then the piece will be moved to a classical state in the relevant square, and may be treated as such. But what if it is found to be in square $c$? ``` Square a Square b Square c +--------------+--------------+--------------+ | | | R---R | | | | /\ |-2 | | | | | / 1\ R---R | | | | r----r | | | | | +--------------+--------------+--------------+ ``` Reading off the square, we get the state $ r \cdot \left( \frac{\ket{\uparrow_c}}{2} - \frac{\ket{\downarrow_c}}{\sqrt{2}} \right)\, . $ If we observe this state in the standard $\triangle/\square$ basis, then, conditioned on the probabilities summing to $1$, it is easy to see that $r$ must be such that the probability of observing $\triangle$ is one-third, and the probability of observing $\square$ is two-thirds. Since the probabilities within the paranthesis are currently $(1/2)^2 = 1/4$ and $(1/\sqrt{2})^2 = 1/2$, respectively, this is achieved by setting $r^2 = 4/3 \to r = 2/\sqrt{3}$. But what if we observe the square under the *rotated* mode of observation, i.e. the $+/-$ basis? Let us rewrite the state using the identities from the start of the section: $ r \cdot \left( \frac{\ket{\uparrow_c}}{2} - \frac{\ket{\downarrow_c}}{\sqrt{2}} \right) = \frac{2}{\sqrt{3}} \cdot \left( \frac{\ket{+_c} + \ket{-_c}}{2 \sqrt{2}} - \frac{\ket{+_c} - \ket{-_c}}{2} \right) $ $ = \frac{2}{\sqrt 3} \cdot \left( \frac{1-\sqrt{2}}{2\sqrt{2}}\ket{+_c} + \frac{1+\sqrt{2}}{2\sqrt{2}} \ket{-_c} \right) $ $ = \frac{1-\sqrt{2}}{\sqrt{6}}\ket{+_c} + \frac{1+\sqrt{2}}{\sqrt{6}} \ket{-_c}\, . $ There are two possible outcomes, and they have the following probabilities: |Outcome|Amplitude|Probability| |:-----:|:-------:|:---------:| |$\ket{+_c}$|$\frac{1 - \sqrt{2}}{\sqrt{6}}$|$\left( \frac{1 - \sqrt{2}}{\sqrt{6}} \right)^2 \approx 0.03$| |$\ket{-_c}$|$\frac{1 + \sqrt{2}}{\sqrt{6}}$|$\left( \frac{1 + \sqrt{2}}{\sqrt{6}} \right)^2 \approx 0.97$| The $3\%$ vs. $97\%$ probabilities match those of the half-cancelled case, and may thus be rolled for in the same way: Simply roll two d6, and check for snake-eyes![^3] As an exercise, you may want to repeat the above calculations for the case that Player 1 half-cancels Player 2, and check that you get the same probabilities only reversed. After that, check the case of a twice half-cancelled state, and verify that both cancellation probabilities still round to $3\%$, and that the remaining outcomes, conditioned on none of the cancellations failing, get probabilities that are exactly sixths. [^2]: Here, as elsewhere, each player uses their colours in the order red, green, blue, yellow, purple, (with lowercase letters denoting Player 1 and uppercase letters denoting Player 2). [^3]: In case you're wondering: No, the probabilities do not end up *exactly* the same as in the case of the half-cancelled square, but both cases do round to $0.03$. [^4]: These moves are obviously not *unitary*, since they do not even preserve the total number of pieces on the board. One way to *make* them unitary (for example in order to implement the game on a quantum computer) would be to add "ancilla" off-board squares, and posit that any time a move adds a piece to the board, the piece is actually just moved from an off-board square to an on-board square.