This tutorial will explain the concepts behind a quantum version of Tic-Tac-Toe and how you would build it using the Unitary library.
The following code block installs the unitary library from github.
!pip install --quiet git+https://github.com/quantumlib/Unitary@main
import unitary.alpha as alpha
Classical Tic-Tac-Toe
Tic-Tac-Toe is a common game played on a 3x3 grid for two players. The two players take alternating turns placing X's and O's onto the grid until there are either three X's or O's in a row or the grid has been filled.
Creating Classical Tic-Tac-Toe
We could create a classical version of Tic-Tac-Toe by using a 3x3 array (or list of lists). Each entry would be 0 (empty), 1 (X), or 2 (O) depending on the state of that square. We can define an enumeration (Enum) to conveniently denote that.
For instance,
import enum
class TicTacSquare(enum.Enum):
EMPTY = 0
X = 1
O = 2
tic_tac_toe_board = [
[TicTacSquare.EMPTY, TicTacSquare.EMPTY, TicTacSquare.EMPTY],
[TicTacSquare.EMPTY, TicTacSquare.EMPTY, TicTacSquare.EMPTY],
[TicTacSquare.EMPTY, TicTacSquare.EMPTY, TicTacSquare.EMPTY],
]
This is all that is needed to store a Tic-Tac-Toe game board classically. To finish developing the game, one would need to write a simple user interface (UI) that allows the players to set the grid values to X or O. It would also need to check whether either player has achieved three in a row or if all grid positions are filled up. This will be left up as an exercise to the reader. Instead, we will continue with the quantum version.
Quantum Tic-Tac-Toe
We will use the same ideas to create the quantum representation of a Tic-Tac-Toe board.
Rather than a classical array value (integer) representing whether a square has an X or an O, we will use a qubit (quantum bit) to represent it. While a classical bit can be in one of two states (0 or 1), a qubit can be in one of two states (denoted |0〉 or |1〉) or in a superposition (i.e. combination) of both states.
For some games, this may be sufficient, as we may only need to denote whether a square is empty or occupied. (For example, this is how the game quantum chess works. Each square is a qubit representing whether a piece is occupying the square. Which kind of piece (knight, rook, etc) is kept track of classically).
However, for Tic-Tac-Toe, we will need three different possibilities (empty, X, or O). Thus, a qubit is insufficient, and we will need to use a Qutrit. A qutrit is similar to a qubit but can be in a combination of |0〉, |1〉, or |2〉. Luckily, this is easily done using the unitary repository.
First we will need a name for each square on the board, so we can name the qutrits. We will use a single letter, such as the following:
a | b | c
-----------
d | e | f
-----------
g | h | i
Then, we can create a QuantumWorld object that has nine QuantumObjects, one for each square:
_SQUARE_NAMES = "abcdefghi"
quantum_board = alpha.QuantumWorld(
[alpha.QuantumObject(name, TicTacSquare.EMPTY) for name in _SQUARE_NAMES])
The above will create a QuantumWorld object that contains the representation of our tic-tac-toe board. The QuantumWorld will automatically know to use qutrits since we are initializing it with enums that have three possible values.
Since it is a quantum state, we will need to "measure" it in order to get our tic-tac-toe board. Quantum states have two important properties:
- Measuring them affects the state. All superpositions will disappear and we will be left in the state that we
- Results are not deterministic. When we measure, we could get one of several possible results.
Because of that, there are two different ways to get the results from the quantum state. They are named similar to "stack" operations.
pop(): Measure the state. This will change the result of theQuantumWorldto the state you measured.peek(): Retrieve a "sample" measurement from theQuantumWorldwithout destructively measuring or changing the state.
Let's try this with our initial state:
print(quantum_board.peek())
[[<TicTacSquare.EMPTY: 0>, <TicTacSquare.EMPTY: 0>, <TicTacSquare.EMPTY: 0>, <TicTacSquare.EMPTY: 0>, <TicTacSquare.EMPTY: 0>, <TicTacSquare.EMPTY: 0>, <TicTacSquare.EMPTY: 0>, <TicTacSquare.EMPTY: 0>, <TicTacSquare.EMPTY: 0>]]
We can see that the state is all empty, but it is a little difficult to read. Let's make a function to print it out in a more readable format:
_MARK_SYMBOLS = {TicTacSquare.EMPTY: ".", TicTacSquare.X: "X", TicTacSquare.O: "O"}
def _histogram(results: list[list[TicTacSquare]]) -> list[dict[TicTacSquare, int]]:
"""Turns a list of whole board measurements into a histogram.
Returns:
A 9 element list (one for each square) that contains a dictionary with
counts for EMPTY, X, and O.
"""
hist = []
for idx in range(9):
hist.append({TicTacSquare.EMPTY: 0, TicTacSquare.X: 0, TicTacSquare.O: 0})
for r in results:
for idx in range(9):
hist[idx][r[idx]] += 1
return hist
def print_board(board) -> str:
"""Returns the TicTacToe board in ASCII form."""
# Get 100 representative samples
results = board.peek(count=100)
# Collect them into a histogram
hist = _histogram(results)
# Print it out all nice
output = "\n"
for row in range(3):
for mark in TicTacSquare:
output += " "
for col in range(3):
idx = row * 3 + col
output += f" {_MARK_SYMBOLS[mark]} {hist[idx][mark]:3}"
if col != 2:
output += " |"
output += "\n"
if idx in [2, 5, 8] and row != 2:
output += "--------------------------\n"
return output
Now let's print it out again, this time in a more readable format:
print(print_board(quantum_board))
. 100 | . 100 | . 100 X 0 | X 0 | X 0 O 0 | O 0 | O 0 -------------------------- . 100 | . 100 | . 100 X 0 | X 0 | X 0 O 0 | O 0 | O 0 -------------------------- . 100 | . 100 | . 100 X 0 | X 0 | X 0 O 0 | O 0 | O 0
We can see that, out of 100 trials, each of the squares in the grid was empty. This is expected for the initial state of the board.
Now, let's try to change a square to an X. For this, we will use an effect called QuditFlip which will take one state and change it to another. This effect takes three arguments:
- The dimension, which is 3, since we are using qutrits to represent three states.
- The initial state, which is 0 (Empty)
- The final state, which is 1 (X).
alpha.QuditFlip(3, 0, 1)(quantum_board.objects[0])
print(print_board(quantum_board))
. 0 | . 100 | . 100 X 100 | X 0 | X 0 O 0 | O 0 | O 0 -------------------------- . 100 | . 100 | . 100 X 0 | X 0 | X 0 O 0 | O 0 | O 0 -------------------------- . 100 | . 100 | . 100 X 0 | X 0 | X 0 O 0 | O 0 | O 0
Now, the upper left corner is 'X' in 100 our of 100 samples.
So far, this game is very similar to classical tic-tac-toe. Let's introduce some quantum-ness into our game with a new move particular to quantum states.
This move will be a 'split'. A split move will be defined as marking two grid squares simultaneously. For instance, we will try to mark both 'b' and 'c' with 'O'. This will work by utilizing superposition. The 'O' will be in one of the two squares ('b' or 'c') but we will not know which one until we measure.
from unitary.alpha.qudit_gates import QuditXGate, QuditISwapPowGate
class TicTacSplit(alpha.QuantumEffect):
"""
Flips a qubit from |0> to |1> then splits to another square.
Depending on the ruleset, the split is done either using a standard
sqrt-ISWAP gate, or using the custom QuditSplitGate.
Args:
tic_tac_type: whether to mark X or O
"""
def __init__(self, tic_tac_type: TicTacSquare):
self.tic_tac_type = tic_tac_type
def num_dimension(self) -> int | None:
return 3
def num_objects(self) -> int | None:
return 2
def effect(self, *objects):
square1 = objects[0]
square2 = objects[1]
yield QuditXGate(3, 0, self.tic_tac_type.value)(square1.qubit)
yield QuditISwapPowGate(3, 0.5)(square1.qubit, square2.qubit)
TicTacSplit(TicTacSquare.O)(quantum_board.objects[1],quantum_board.objects[2])
print(print_board(quantum_board))
. 0 | . 53 | . 47 X 100 | X 0 | X 0 O 0 | O 47 | O 53 -------------------------- . 100 | . 100 | . 100 X 0 | X 0 | X 0 O 0 | O 0 | O 0 -------------------------- . 100 | . 100 | . 100 X 0 | X 0 | X 0 O 0 | O 0 | O 0
Now we can see some variation in the results. If we take 100 sample boards, the O will be in the 'b' square about 50 of them and in 'c' the rest of the time.
Lastly, we can see what happens when we measure with a pop() call.
print(quantum_board.pop())
print(print_board(quantum_board))
[<TicTacSquare.X: 1>, <TicTacSquare.EMPTY: 0>, <TicTacSquare.O: 2>, <TicTacSquare.EMPTY: 0>, <TicTacSquare.EMPTY: 0>, <TicTacSquare.EMPTY: 0>, <TicTacSquare.EMPTY: 0>, <TicTacSquare.EMPTY: 0>, <TicTacSquare.EMPTY: 0>] . 0 | . 100 | . 0 X 100 | X 0 | X 0 O 0 | O 0 | O 100 -------------------------- . 100 | . 100 | . 100 X 0 | X 0 | X 0 O 0 | O 0 | O 0 -------------------------- . 100 | . 100 | . 100 X 0 | X 0 | X 0 O 0 | O 0 | O 0
Now, the board has resolved to the O being in one spot or the other, but not both. This will be in the 'b' square about half the time and 'c' in the other half. However, after the measurement occurs, it will always be in the same place.
The full example for Tic-Tac-Toe can be found here: https://github.com/quantumlib/unitary/tree/main/unitary/examples/tictactoe