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?

  • 1
    $\begingroup$ Can you include the reference where you read that? $\endgroup$ – cnada Mar 9 at 9:04
  • 2
    $\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

Your Answer

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

Browse other questions tagged or ask your own question.