Let us look at the two questions that are NP-complete for a classical computer:
- Given an arbitrary Boolean expression, find an assignment of variables that evaluates the expression to $0$ (SAT).
- Given an arbitrary Boolean expression, count the number of assignments that evaluates the expression to $0$ (#SAT).
We know that the Simon's algorithm or the Grover's search can effectively solve the first problem with square-root complexity with high probability. Is it the case for the second problem too, or a quantum computer still needs to perform the same number of queries as a classical computer does?