3
$\begingroup$

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?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.