Let us look at the two questions that are NP-complete for a classical computer:

1. Given an arbitrary Boolean expression, find an assignment of variables that evaluates the expression to $0$ (SAT).
2. Given an arbitrary Boolean expression, count the number of assignments that evaluates the expression to $0$ (Max-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?

Let us look at the two questions that are NP-complete for a classical computer:

1. Given an arbitrary Boolean expression, find an assignment of variables that evaluates the expression to $0$ (SAT).
2. 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?

I would like to know if the concept of the complexity classes are the same for a quantum computer and a classical computer.

For a concrete question, let us look at the two questions that are NP-complete for a classical computer:

1. Given an arbitrary Boolean expression, find an assignment of variables that evaluates the expression to $0$. (SAT)
2. Given an arbitrary Boolean expression, count the number of assignments that evaluates the expression to $0$ (Max-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?

Let us look at the two questions that are NP-complete for a classical computer:

1. Given an arbitrary Boolean expression, find an assignment of variables that evaluates the expression to $0$ (SAT).
2. Given an arbitrary Boolean expression, count the number of assignments that evaluates the expression to $0$ (Max-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?