In this short computational essay, we explored a quantum version of the tic-tac-toe in a 2x2 board. Each player’s turn can be described quantum mechanically as a quantum channel, with four Kraus operators acting on the quantum state of the board, with each cell/square is described as a 3D quantum system (0 unclaimed, 1 claimed by the first player, and 2 claimed by the 2nd player). At each turn, a player can simultaneously change the state of all cells. Note the quantum channel we used is non-trace preserving. To our surprise, the graph generated quantum mechanically is isomorphic to the tic-tac-toe multiway graph obtained from the abstract idea of multicomputation.
Quick history
Quick history
The idea of a quantum version of tic-tac-toe game was suggested by Stephen Wolfram during one of many long project selection meetings that we had this year during the Wolfram Summer School 2022. In fact, our student did a decent job in implementing a quantum version of that game, using logic gates, and determining the winner in a probabilistic way. Note that neither what we are going to represent here, nor our student’s project, is the same as what is usually called as quantum tic-tac-toe in the literature [at least, up to now]. Our approach, and the way that we included quantum-ness into this game is different. We will explain the detail soon.
An interesting fact, worth mentioning, is that since Oct 2021 that I and Nik had taken over the Wolfram quantum project and turned into a paclet, Stephen had been reminding us on several occasions that there should be an interesting explicit analogy/correspondence between some quantum features and multicomputation (eg, read the starting paragraph of this post). We should say Mads had been skeptical of this idea. But to our surprise, this simple quantum game not only show an analogy, but also a serious relation between the core idea of multicomputation and the quantum theory (in particular, Schmidt decomposition and terms with no entanglement). Of course, we are just about to understand this relationship better, and we are sure there are a lot to learn and discover. We highly motivate young scholars, esp theoretical scientists, to explore the multicomputation and its connection with quantum theory, more. There are still a lot more to learn.
Wolfram Quantum Framework
Wolfram Quantum Framework
Our quantum framework is a paclet, that one can install using the following code:
In[]:=
PacletInstall[CloudObject["https://wolfr.am/DevWQCF"],ForceVersionInstall->True]<<Wolfram`QuantumFramework`
Out[]=
PacletObject
After running above code, a collection of functions will be added to your system, where by using them you can do any quantum computation in a finite dimensional Hilbert space. In the documentation page of our quantum framework, one can find enough info on each quantum functionalities and how to set them up. Any question, please contact: quantum AT wolfram.com
Quantum version of tic-tac-toe
Quantum version of tic-tac-toe
Define , and (3D qudit)
|0〉
|1〉
|2〉
In[]:=
qudits=Table[QuantumState[{"Register",{3},i}],{i,0,2}];
non-unitary to transform
|0〉->|1〉
In[]:=
u1=QuantumOperator[qudits[[2]][qudits[[1]]["Dagger"]]]
Out[]=
QuantumOperator
channel corresponding to player 1. It looks into all cells, and marks all 0 by 1
player1=QuantumChannel[Table[QuantumOperator[u1,{i}],{i,4}]]
Out[]=
QuantumChannel
non-unitary to transform
|0〉->|2〉
In[]:=
u2=QuantumOperator[qudits[[3]][qudits[[1]]["Dagger"]]]
Out[]=
QuantumOperator
channel corresponding to player 1 (look into all cells, and mark all 0 by 2)
player2=QuantumChannel[Table[QuantumOperator[u2,{i}],{i,4}]]
Out[]=
QuantumChannel
The sequence of turns, and its representation as a quantum circuit:
In[]:=
qc=QuantumCircuitOperator[player1]/*QuantumCircuitOperator[player2]/*QuantumCircuitOperator[player1]/*QuantumCircuitOperator[player2];
Now we define two functions that we will use to create a multigraph of a quantum circuit.
In[]:=
operatorApply[op_,states_]:=With[{order=op["InputOrder"]}, Map[With[{n=Length[#]-Length[order]},Join[ReplacePart[states,Thread[order->Drop[#,n]]],Take[#,n]]]&,op["State"][QuantumTensorProduct@@states[[order]]]["Decompose"]]]
In[]:=
CircuitMultiwayGraph[circuit_,initStates_:Automatic]:=ResourceFunction["FoldGraph"][ {s,op}|->Map[{s[[1]]+1,#}&]@operatorApply[op,s[[2]]], {{0,Replace[initStates,Automatic->Table[QuantumState["0"],circuit["Arity"]]]}}, circuit["Operators"], GraphLayout->"LayeredDigraphEmbedding"]
The function CircuitMultiwayGraph creates a graph where each vertex is list of quantum states, the first four corresponds to the board state (four squares/cells) and the rest the corresponding environments (that appear in the quantum channels). Note that each player’s turn is described quantum mechanically by a quantum channel (which is non-trace preserving map, in our case), thus the overall quantum state of the board is a mixed state. To create the corresponding graph using CircuitMultiwayGraph, we first decompose the states using “Decompose” property of QuantumState. In this process, we repeated apply the Schmidt decomposition, until we get a linear combination of states where each state (ie term in the superposition) is fully separable. In other words, each branching the following graph represents a space/world in which all particles (here four squares/cells of the board and the environment) are fully separable, meaning no entanglement between them.
In[]:=
cmwg=CircuitMultiwayGraph[qc,Table[N@QuantumState[{1},3],4]]
Out[]=
Note that the above graph is in fact the output of the resource function FoldGraph. This function takes three arguments as input: FoldGraph[f,{x1,x2,…},{y1,y2,…}] and the final output is a graph with edges for each output of a multi-output function f applied to inputs and iteratively to each . In the function CircuitMultiwayGraph, {y1,y2,..} are collection of gates for corresponding circuit, and the list {x1,x2,..} is {0,{state1,state2,...}} where states correspond to an initial separable state of the composite system (here, four squares/cells of the board). The first element, that is initially set as 0 will be used to track the players turns.
x
i
y
i
For the sake of explanation, let us consider some special cases. For all of them, we will consider the state to be the same as the initial state of squares/cell of a 2x2 board (four 3D quantum systems, all prepared in the state ). First, let’s consider the case that each square/cell evolves independents, thus no possible evolution.
|0〉
In[]:=
ρ0=Table[N@QuantumState[{1},3],4];qcU=QuantumCircuitOperator[QuantumTensorProduct@Table[QuantumOperator[{"RandomUnitary",3}],4]];CircuitMultiwayGraph[qcU,ρ0]
Out[]=
As expected, no branching happens, since there is not entanglement.
However, if one considers the case where there is a possibility of entanglement formation between different sub-systems, one observes the branching in the multiway graph. We consider the case that a unitary evolution can form entanglement between qudits 1 and 2 only (ie one two cells/square of the board)
In[]:=
qcU=QuantumCircuitOperator[QuantumOperator[{"RandomUnitary",{3,3}}]@QuantumOperator[{"RandomUnitary",{3}}]@QuantumOperator[{"RandomUnitary",{3}}]];CircuitMultiwayGraph[qcU,ρ0]
Out[]=
As expected, one observes branching in the multiway graph due the entanglement formation (reminder: each branch represents a Schmidt decomposition term such that within each term, the state is fully separable).
Let’s take a look at the vertices of the multiway graph we obtained for our game. Each vertex contains a list of quantum states for four squares/cells of the board, and also environment (corresponding to players). The first element of each vertex is an integer number, tracking how many times the game is played (ie number of turns). Let’s look at all vertices after two turns (player 1, and player 2). There are, overall, 12 possible combination, and each one different state of the board, and different state of the environment (reminder: a quantum channel can be described as adding an environment). The first four terms of each state correspond to the board, and the rest, to the environment.
In[]:=
Map[QuantumTensorProduct[#]["Normalized"]["Computational"]["Formula"]&,GroupBy[VertexList[cmwg],First->Last][2]]
Out[]=
{1.|12000001〉,1.|10200010〉,1.|10020011〉,1.|01020111〉,1.|01200110〉,1.|21000100〉,1.|02101001〉,1.|00121011〉,1.|20101000〉,1.|02011101〉,1.|00211110〉,1.|20011100〉}
Now, we will define a function to generate primitives for rendering each vertex. For this aim, we will consider only the first four terms of each vertex, which correspond to the state of squares/cells in the board. If the state is , we represent it by an empty cell, by X , and by O. Using that function, we replace vertices in the multiway graph.
|0〉
|1〉
|2〉
In[]:=
SimpleGraph@VertexReplace[cmwg,v_:>Normal@MapAt[#["Computational"]["CanonicalStateVector"]&,v,{2,All}][[2,;;4]],VertexShapeFunction->Function[Inset[ResourceFunction["CharacterArrayPlot"][ArrayReshape[Position[#,1.]&/@#2,{2,2}],"CharacterStyleRules"->{x_:>{8,Black,Bold}},"CharacterRules"->{1->"",2->"X",3->"O"},ColorRules->{1->White,2->Lighter[Orange,.5],3->Lighter[Purple,.7]},MeshStyle->Directive[Thick,LightGray],Frame->False,FrameTicks->False,FrameStyle->Directive[Blend[{Orange,Red},.3],Thickness[.05]],ImageSize->20],#1,#3]],PerformanceGoal->"Quality"]
Out[]=
To our surprise, the above graph is isomorphic to the tic-tac-toe graph obtained from multicomputation approach:
Acknowledgment
Acknowledgment
This work has been a byproduct of the Wolfram Summer School 2022. Although both authors (Nik and Mads) were busy with student mentoring and other affairs of the school, we were very happy that Stephen Wolfram motivated us to work on this idea. In fact, the original idea was suggested (and also expected!) by Stephen Wolfram.We also thank Akhilesh Dubey and Christopher Wolfram, for their questions that motivated us more to work on this idea. Nik developed a big portion of codes, esp the graph-related part. Mads wrote the narrative text and other explanations.