2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Can you include the reference where you read that? $\endgroup$ – cnada Mar 9 at 9:04
  • 3
    $\begingroup$ 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 $\endgroup$ – Mithrandir24601 Mar 9 at 9:07
  • $\begingroup$ cs.virginia.edu/~robins/The_Limits_of_Quantum_Computers.pdf $\endgroup$ – QCQCQC Mar 9 at 9:12
  • $\begingroup$ @QCQCQC How's that PDF relevant? $\endgroup$ – Sanchayan Dutta Mar 9 at 9:40
  • $\begingroup$ 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 $\endgroup$ – QCQCQC Mar 9 at 10:29
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.