# Grover's algorithm and Battleship solution

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?

• Can you include the reference where you read that? – cnada Mar 9 '19 at 9:04
• You might want to double check the difference between the game played between 2 people and the decision problem (pdf link)/puzzle - in both, you want to find all the ships but while the former involves large amounts of guesswork, the latter is a very different problem where the solution can be found without guesswork – Mithrandir24601 Mar 9 '19 at 9:07
• cs.virginia.edu/~robins/The_Limits_of_Quantum_Computers.pdf – QCQCQC Mar 9 '19 at 9:12
• @QCQCQC How's that PDF relevant? – Sanchayan Dutta Mar 9 '19 at 9:40
• I was asked to provide reference to where I read that QCs are not known to be able to solve np-complete problems in polynomial time. Guess I replied to the wrong post. @Mithrandir24601 I will look into that article, thanks – QCQCQC Mar 9 '19 at 10:29

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 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.