AM  Vol.3 No.11 A , November 2012
Quantum Tic-Tac-Toe: A Genuine Probabilistic Approach
ABSTRACT
We propose a quantum version of Tic-Tac-Toe which accurately reflects the inherent probabilistic nature of the measurement principle in quantum mechanics. We then formulate a quantum strategy which allows a quantum player to consistently win over a classical player, with a certain probability. This result can be seen as another proof of the superior computational power of a quantum system with respect to a classical one. Our investigation also reveals that the non-determinism and complexity introduced by the principles of quantum mechanics into even the most simple games make brute-force strategies considerably more difficult to implement. Consequently, games in which machines have gained the upper hand over humans may be made fair again by upgrading them to a quantum level.

Cite this paper
M. Nagy and N. Nagy, "Quantum Tic-Tac-Toe: A Genuine Probabilistic Approach," Applied Mathematics, Vol. 3 No. 11, 2012, pp. 1779-1786. doi: 10.4236/am.2012.331243.
References
[1]   D. R. Simon, “On the Power of Quantum Computation,” Special Issue on Quantum Computation of the SIAM Journal on Computing, Vol. 26, No. 5, 1997, pp. 14741483.

[2]   P. W. Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer,” Special Issue on Quantum Computation of the SIAM Journal on Computing, Vol. 26, No. 5, 1997, pp. 1484-1509.

[3]   S. Wiesner, “Conjugate Coding,” SIGACT News, Vol. 15, No. 1, 1983, pp. 78-88. doi:10.1145/1008908.1008920

[4]   C. H. Bennett and G. Brassard, “Quantum Cryptography: Public Key Distribution and Coin Tossing,” Proceedings of IEEE International Conference on Computers, Systems and Signal Processing, Bangalore, 10-19 December 1984, pp. 175-179.

[5]   A. Ekert, “Quantum Cryptography Based on Bell’s Theorem,” Physical Review Letters, Vol. 67, No. 6, 1991, pp. 661-663. doi:10.1103/PhysRevLett.67.661

[6]   M. Nagy, S. G. Akl and S. Kershaw, “Key Distribution Based on the Quantum Fourier Transform,” International Journal of Security and Its Applications, Vol. 3, No. 4, 2009, pp. 45-67.

[7]   M. Nagy and S. G. Akl, “Entanglement Verification with an Application to Quantum Key Distribution Protocols,” Parallel Processing Letters, Vol. 20, No. 3, 2010, pp. 227-237. doi:10.1142/S0129626410000181

[8]   R. Cleve and H. Buhrman, “Substituting Quantum Entanglement for Communication,” Physical Review A, Vol. 56, No. 2, 1997, pp. 1201-1204. doi:10.1103/PhysRevA.56.1201

[9]   J. Eisert and M. Wilkens, “Quantum Games,” Journal of Modern Optics, Vol. 47, No. 14-15, 2000, pp. 2543-2556.

[10]   S. C. Benjamin and P. M. Hayden, “Multiplayer Quantum Games,” Physical Review A, Vol. 64, 2001, Article ID: 030301. http://xxx.lanl.gov/abs/quant-ph/0003036.

[11]   I. Fialik, “Separation between Classical and Quantum Winning Strategies for the Matching Game,” International Journal of Foundations of Computer Science, Vol. 19, No. 6, 2008, pp. 1449-1459. doi:10.1142/S0129054108006388

[12]   D. A. Meyer, “Quantum Strategies” Physical Review Letters, Vol. 82, 1999, pp. 1052-1055. http://arxiv.org/abs/quant-ph/9804010

[13]   R. F. Werner, “Optimal Cloning of Pure States,” Physical Review A, Vol. 58, No. 3, 1998, pp. 1827-1832. doi:10.1103/PhysRevA.58.1827

[14]   D. Deutsch, “Quantum Theory of Probability and Decisions,” Proceedings of the Royal Society of London A, Vol. 455, 1999, pp. 3129-3137. doi:10.1098/rspa.1999.0443

[15]   S. G. Akl, “On the Importance of Being Quantum,” Parallel Processing Letters, Special Issue on Advances in Quantum Computation, Vol. 20, No. 3, 2010, pp. 275-286.

[16]   A. Goff, “Quantum Tic Tac Toe: A Teaching Metaphor for Superposition in Quantum Mechanics,” American Journal of Physics, Vol. 74, No. 11, 2006, pp. 962-973. doi:10.1119/1.2213635

[17]   M. Nagy and S. G. Akl, “Quantum Computing: Beyond the Limits of Conventional Computation,” International Journal of Parallel, Emergent and Distributed Systems, Special Issue: Emergent Computation, Vol. 22, No. 2, 2007, pp. 123-135. doi:10.1080/13547500600899209

 
 
Top