An Exact Quantum Algorithm for a Restricted Subtraction Game

An algorithm is exact if it always produces the correct answer on any input. Coming up with exact quantum algorithms that substantially outperform the best classical algorithm has been a quite challenging task. Nim game is a well-known combinatorial game which has a complete mathematical theory, and many kinds of Nim games have been studied in the literature. One famous kind of Nim games are subtraction games played with one heap of tokens, with players taking turns removing from the heap a number of tokens belonging to a specified subtraction set. The last player to move wins. In this paper, we propose a restricted subtraction game with the subtraction set determined by a specified matrix, and present an exact quantum algorithm to solve it. We show that the query complexity of our quantum algorithm is O(n32)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O(n^{\frac {3}{2}})$\end{document}, while the classical exact query complexity is Θ(n2).