Does quantum computers give any advantage over classical computers in Sudoku?

Question

To my basic knowledge I know that solving a generalized Sudoku problems is an NP-complete problem so, is there any possible way quantum computers give an advantage over classical computers in this type of problem?

Answer 1

You are correct that solving Sudoku for $n^2 \times n^2$ grids with $n\times n$ blocks is an NP complete problem.

The quantum complexity class BQP is the class of decision problems solvable by a quantum computer in polynomial time (with an error probability of at most 1/3 in all cases). The relationship between BQP and the classical complexity classes P and NP-Complete is currently an open problem, but most experts think that quantum computers cannot solve NP-Complete problems in polynomial time:

This is an excerpt from this Wikipedia article:

It is suspected that NP $ \nsubseteq $ BQP; that is, it is believed that there are efficiently checkable problems that are not efficiently solvable by a quantum computer. As a direct consequence of this belief, it is also suspected that BQP is disjoint from the class of NP-complete problems (if an NP-complete problem were in BQP, then it would follow from NP-hardness that all problems in NP are in BQP).

Therefore quantum comptuers are unlikely to be able to solve an $n^2 \times n^2$ Sudoku puzzle in polynomial time. It is quite possible that quantum computers will have to pay $\mathcal{O}(2^n)$ to solve the puzzle, as would be the case for classical computers, however this doesn't rule out the possibility that the quantum computer could beat the classical computer by having a smaller constant hidden under the big O, or by having a smaller pre-factor in the exponent.

The original question:

"is there any possible way quantum computers give an advantage over classical computers in this type of problem?"

is a bit vague, because what is meant by "advantage" ? Many people would only consider it to be an "advantage" if there is there is an improvement in the scaling of the cost with respect to $n$, which is why at first I mentioned computational complexity considerations. However if you just want to know whether or not a quantum computer can finish the puzzle with fewer logic gates than a classical computer, of course the quantum computer will have an advantage because all classical computers are quantum computers, so by definition there is absolutely no way a classical computer can finish the puzzle with fewer gates. Whether or not quantum gates can be performed as efficiently (energy-wise) compared to classical gates though, is an open problem. So the answer depends on what you consider to be an "advantage" and how you define things, but you can certainly define things in a way in which a quantum computer would have an advantage.