Quantum Tic-Tac-Toe: A Genuine Probabilistic Approach

Affiliation(s)

College of Computer Engineering and Science, Prince Mohammad Bin Fahd University, Al Azeziya, KSA.

College of Computer Engineering and Science, Prince Mohammad Bin Fahd University, Al Azeziya, KSA.

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.

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.

KEYWORDS

Quantum Games; Tic-Tac-Toe; Quantum Measurement; Superposition; Entanglement; Computational Power

Quantum Games; Tic-Tac-Toe; Quantum Measurement; Superposition; Entanglement; Computational Power

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.

M. Nagy and N. Nagy, "Quantum Tic-Tac-Toe: A Genuine Probabilistic Approach,"

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

[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