Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
I have read that quantum computers are not known to be able to solve NP-complete problems in polynomial time. However, if you consider a game of Battleship with grid size $X, Y$ and represent this by a binary string $01100\cdots$ of size $X \times Y$ where the $1$s represents ship locations, wouldn't Grover's algorithm be able to solve this in $\mathcal{O}(\sqrt{XY})$?
Battleship is considered NP-complete. Why isn't this considered polynomial time?
I think you've simplified the problem too much. The way your question is framed it sounds like you expect a square-root speedup of a small problem, which doesn't seem that impressive. In actuality there may be a Grover-style speedup not of $O(\sqrt{X Y})$ but of $O(\sqrt{2^X 2^Y})$.
Let's set up the problem, and see what is to be solved.
Let's let your opponent's battleship grid be of size $X\times Y$. It is populated with $s\in\{0,1\}$ binary numbers, where $1$ is "ship" and $0$ is "sea". Thus you can think of your opponent's grid as an element $S$ of $\{0,1\}^{XY}$.
The size of and placement of ships further constrains what $S$ can be; for example, there must be two consecutive $1$'s for a destroyer, four consecutive $1$'s for a battleship, etc.
Nonetheless your goal is to guess the location of all of your opponent's $1$'s with fewest number of guesses.
Thus, you are trying to determine $S\in \{0,1\}^{XY}$. When properly framed this can be a $\mathsf{3SAT}$ instance and Grover's algorithm can get the polynomial speedup of an exponential problem.
