# SAT and #SAT in Quantum

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?

## 1 Answer

It depends on how many satisfying assignments there are. If there are $$t$$ satisfying assignments, then it takes approximately $$O(\sqrt{Nt})$$ time for a quantum algorithm to identify all of them, if we are given an oracle to recognize which assignments are satisfying. This can be compared to $$O(N)$$ time for a classical algorithm to do the same task. So if $$t$$ is small, a quantum algorithm is significantly better.

See Quantum Counting, Gilles Brassard, Peter Hoyer, Alain Tapp, ICALP 1998.

• Is there any specific name to this algorithm?
– hola
Mar 3, 2022 at 13:14
• If I understand correctly, the answer depends on the specific problem. If the problem has many solutions, then the quantum advantage diminishes.
– hola
Mar 3, 2022 at 15:49