Tic-Tac-Toe: a quantum probabilistic approach
by Akhilesh Dubey
Kirori Mal College, University of Delhi
by Akhilesh Dubey
Kirori Mal College, University of Delhi
Abstract: The project propose quantum version of Tic-Tac-Toe which accurately resemble the inherent probabilistic nature of the Measurement Principle in Quantum Mechanics. It is aimed at showing the formulation of quantum rules, by using quantum superposition of different states and entanglement from the aid of qutrits and quantum gates representing the whole Game Tree.
1. Introduction
1. Introduction
The quantum information field has wide variety of range embodying information in physical systems whose algorithm can be understood by laws of quantum mechanics and probing the consequences of physical support that how quantum information is processed and manipulated .
We are implementing the quantum approach on classical version of game theory with better and more successful quantum strategies . The main inspiration behind applying quantum information into game theory is the ability to formulate many problems.
The quantum Tic-Tac-Toe game discussed below applies the properties of quantum systems in an abstract manner with the purpose that how using probabilities and statistical approach, a player can win. The measurement done on states is considered as a game played. Further, each and every turn/step in the game is depicted on a multiway graph system.
Here in this project, we take a different approach of rules in locus of quantum algorithm . Rather than seeking a unified theory of games and quantum mechanics, we wish to explore the effects of “superposition and entanglement” on well known games . This upgrading refers to the physical support of the game (For example the board). The board is embodied as a quantum system and each move in the game is viewed as a quantum operation or transformation acting upon and changing the current quantum state of the system .
We are implementing the quantum approach on classical version of game theory with better and more successful quantum strategies . The main inspiration behind applying quantum information into game theory is the ability to formulate many problems.
The quantum Tic-Tac-Toe game discussed below applies the properties of quantum systems in an abstract manner with the purpose that how using probabilities and statistical approach, a player can win. The measurement done on states is considered as a game played. Further, each and every turn/step in the game is depicted on a multiway graph system.
Here in this project, we take a different approach of rules in locus of quantum algorithm . Rather than seeking a unified theory of games and quantum mechanics, we wish to explore the effects of “superposition and entanglement” on well known games . This upgrading refers to the physical support of the game (For example the board). The board is embodied as a quantum system and each move in the game is viewed as a quantum operation or transformation acting upon and changing the current quantum state of the system .
2. Rule of the Game
2. Rule of the Game
This section deals with quantum version rules of the Tic-Tac-Toe game. Our aim is to explore the consequences introduced in gaming by the same principles that govern the behavior of quantum systems, without ‘adjusting’ or ‘customizing’ them in any way.
2.1 Legalised Moves
2.1 Legalised Moves
Player can choose from a set of quantum states (provided) and can implement onto a maximum of two qubits out of the four from the game.
2.2 Winning Criteria
2.2 Winning Criteria
(a)Thefirstprobabilitybaralwayscorrespondstotheplayerone
andthesecondbar
totheplayertwo.(b)Thewinnerisdeterminedbymeasuringtheprobabilitiesforeachqubits.Thebarcorrespondingtothegreaterprobabilitywouldbeentitledasthewinnerplayer.
3. The Game
3. The Game
3.1 Initialization
3.1 Initialization
A 22 Tic-Tac-Toe has total of 4 different choices expressed as four qubits. We set the initial board to in state.
|0000〉
3.1 Initialization
3.1 Initialization
A 22 Tic-Tac-Toe has total of 4 different choices expressed as four qubits. We set the initial board to in state.
|0000〉
In[]:=
g0=QuantumState["0000"]
Out[]=
QuantumState
Show states in terms of matrix representation.
In[]:=
g0["Formula"]["Name"]//ArrayReshape[#,{2,2}]&//MatrixForm
Out[]//MatrixForm=
0 | 0 |
0 | 0 |
3.1.1 Available choices of Quantum gates
3.1.1 Available choices of Quantum gates
There are a total of 5 Quantum gates(out of 5 famous universal gates) provided in the game out of which a player is free to choose one in his/her turn.
In[]:=
ManipulateQuantumCircuitOperator[If[gate=="CNOT",QuantumOperator[gate,{i,j}],QuantumOperator[{gate,angle},{order}]]]["Diagram"],{{gate,"XRotation","Gate"},{"XRotation","YRotation","ZRotation","Phase","CNOT"}},{angle,0,"Rotation Angle (0 to 2π)"},0,2π,,Appearance->"Labeled",{{order,1,"Order (what cell operator acts)"},Range@4},{{i,1,"CNOT control"},Range@4,RadioButton},{{j,2,"CNOT target"},Range@4,RadioButtonBar},SaveDefinitions->True
π
12
Out[]=
3.2 Start the game
3.2 Start the game
We make sure that the game can be physically implemented using a quantum system whose behavior must obey the rules of quantum mechanics throughout the entire game play.
Provision is made to choose quantum gates randomly to show an equally probabilistic or non-deterministic move made by the players.
Provision is made to choose quantum gates randomly to show an equally probabilistic or non-deterministic move made by the players.
Define the random move made by the player with the available choices of gates, any angle and order to the qubits.
In[]:=
randomGate:=With[{gate=RandomChoice[{"XRotation","YRotation","ZRotation","Phase","CNOT"}]},If[gate=="CNOT",Module[{ctrl,trg},ctrl=RandomChoice[Range[4]];trg=RandomChoice@Complement[Range[4],{ctrl}];QuantumOperator["CNOT",{ctrl,trg}]],QuantumOperator[{gate,RandomReal[{0,2π}]},{RandomChoice[Range[4]]}]]]
Show the circuit diagram of random gates chosen by players to be applied on different four qubits.
In[]:=
qcc=QuantumCircuitOperator[Table[randomGate,{i,4}]];qcc["Diagram",FontSize->6,ImageSize->Medium]
Out[]=
Total number of gates used by the player is four .
In[]:=
qcc["Gates"]
Out[]=
4
Apply the resulting quantum gates on initial state .
|0000〉
In[]:=
qcs=qcc[g0]
Out[]=
QuantumState
Note that resulting output is Quantum State.
Check its dimensions.
In[]:=
qcs["Dimensions"]
Out[]=
{2,2,2,2}
Check its VonNeumann Entropy
In[]:=
qcs["VonNeumannEntropy"]
Out[]=
Check the decomposition of resulting state.
In[]:=
qcs["Decompose"]
Out[]=
QuantumState,QuantumState,QuantumState,QuantumState
Show the formula
Show the state in matrix form.
3.3 Final Measurement
3.3 Final Measurement
We had chosen to implement a non-deterministic measurement process identical in every respect to a probabilistic quantum game. This is different from the classical version of Tic-TacToe where the player has direct control over how a superposition collapses and to the outcome of the measurement.
Check the probability for the final verdict
Player 1 wins.
This is pretty much straight forward result for any player to win. It is mainly due to small number of sample space. To see best statistical result, we can have more variation in our selection of gates or in number of turns which we had executed above.
3.4 MultiWay graph
3.4 MultiWay graph
One might not imagine that something as everyday as well-known games and puzzles would have any connection to the formalism for something like quantum mechanics. But the idea of multicomputation provides a link. And indeed one can view the very possibility of being able to have “interesting” games and puzzles as being related to a core phenomenon of multicomputation.
In a multicomputational system the key idea is that states can have multiple successors—and tracing their behavior defines a whole multiway graph of branching and merging threads of time . And the point is that this is directly related to how one can think about typical games and puzzles .
My particular goal here is to investigate—fairly systematically—a sequence of Tic-Tac-Toe game using the general methods discussed in [1].
Classical picture of Tic-Tac-Toe using Multiway graph
Classical picture of Tic-Tac-Toe using Multiway graph
Visualise the number of possible choices in Classical Tic-Tac-Toe game.
Likewise, Multiway graph of the quantum game shows how choices made by players in game leads to the final output.
Multiway graph in Bloch Cartesian Coordinates works as following:
(a) VertexReplace effectively uses Replace for each vertex in the VertexList.
(b) VertexReplace works with undirected graphs, directed graphs, multigraphs, and mixed graphs.
(b) VertexReplace works with undirected graphs, directed graphs, multigraphs, and mixed graphs.
General Approach
General Approach
Game with 3 choices of gates
Game with 3 choices of gates
Generate a random gate(out of 3 choices), with random angles (if any) and random order.
Generate 20 random moves (equivalent playing tic-tac-toe, 5 times) and create its circuit
Measure the aggregate probabilities of each qubits.
Player 1 wins.
This truly depicts the statistical behaviour of the game with quite fair result.
Implementation of Circuit multiway graph showing each choices made by player.
Multiway graph with Bloch Cartesian Coordinates
Define the random move made by the player with the available choices of gates, any angle and order to the qubits.
Generate 48 random moves (equivalent of playing tic-tac-toe, 12 times) and show the circuit diagram.
Matrix representation of operated state
Check the StateVector of quantum state.
Check the probability plot.
Player 2 wins.
Show the multiway graph of the game.
Apply some operation on Multiway graph.
Definition
Definition
Concluding remarks
Concluding remarks
In this project, we have formulated and analyzed a quantum version of Tic-Tac-Toe based on the actual physical laws describing the behavior of quantum systems. This property makes our quantum game completely implementable using an actual quantum system.
Our investigation also clearly shows that the intrinsic complexity and non-determinism characterizing quantum systems can easily diffuse in the game play.
The major points around which project revolves are as follows:
1. RandomChoices are made to exhibit true probabilistic nature of the game.
2. Measure the aggregate result of probabilities on each condition to decide the winner.
3. Visualise each quantum steps through a multiway graph.
4. Check different properties of Quantum State and Quantum Operators in between to understand each step used to deploy game.
Our investigation also clearly shows that the intrinsic complexity and non-determinism characterizing quantum systems can easily diffuse in the game play.
The major points around which project revolves are as follows:
1. RandomChoices are made to exhibit true probabilistic nature of the game.
2. Measure the aggregate result of probabilities on each condition to decide the winner.
3. Visualise each quantum steps through a multiway graph.
4. Check different properties of Quantum State and Quantum Operators in between to understand each step used to deploy game.
Future Plans and Ideas
Future Plans and Ideas
My future plans involves further development of this idea of 22 Tic-Tac-Toe to 33 and nn dimension. It can also be extended to make a full fledged game app and make final measurement on real-quantum computers.
Keywords
Keywords
◼
Quantum Games
◼
Tic-Tac-Toe
◼
Multiway graph
◼
Qubits
◼
Gates
◼
Superposition
◼
Quantum Circuit
◼
Probability
◼
Random
Acknowledgment
Acknowledgment
Mentor: Christopher Wolfram
Thanks to my mentor Christopher Wolfram for his help and guides throughout in my project. Special thanks to Mads Bahrami and Nik for brainstorming and sorting out the codes along with valuable ideas in designing the game.
A big thanks to Shivam Sawarn and others’ who helped and answered my lame questions and codes .
Last but not the least the fellow student from whom I learned a lot and the friendly supporting staff of summer school.
Thanks to my mentor Christopher Wolfram for his help and guides throughout in my project. Special thanks to Mads Bahrami and Nik for brainstorming and sorting out the codes along with valuable ideas in designing the game.
A big thanks to Shivam Sawarn and others’ who helped and answered my lame questions and codes .
Last but not the least the fellow student from whom I learned a lot and the friendly supporting staff of summer school.
References
References
◼
M. Nagy and N. Nagy, “Quantum Tic-Tac-Toe: A Genuine Probabilistic Approach,” Applied Mathematics, Vol. 3 No. 11A, 2012, pp. 1779-1786. doi: 10.4236/am.2012.331243.
◼
Wolfram Research (2010), VertexReplace, Wolfram Language function, https://reference.wolfram.com/language/ref/VertexReplace.html (updated 2015).