1
$\begingroup$

The Amplitude Amplification paper states in Theorem 13:

For any positive integers $M$ and $k$, and any Boolean function $f: \{0,1,\ldots,N-1\}\rightarrow\{0,1\}$, the algorithm Count $\left(f,M\right)$ outputs an estimate $t^{\prime}$ to $t=|f^{-1}(1)|$ such that $$|t^{\prime}-t|\le2\pi k \frac{\sqrt{t\left(N-t\right)}}{M}+\pi^2k^2\frac{N}{M^2}$$ with probability at least $8/k^2$ when $k=1$, and with probability greater then $1-\frac{1}{2\left(k-1\right)}$ for $k\ge 2$. If $t=0$ then $t^{\prime}=0$ with certainty, and if $t=N$ and $M$ is even, then $t^{\prime}=N$ with certainty.

The Count algorithm uses the QPE-based amplitude estimation algorithm.

I would appreciate clarification regarding the assertion that the algorithm can tell with certainty when there are no solutions ($t=0$).

The algorithm seems to provide "immediate" unsatisfiability certificates to any co-NP problem.

What is the "fine print"? what is the size of the QPE register, hence the number of controlled Grover operators, that are required?

Update

Despite comments that the algorithm does not violate any complexity issues, this algorithm could solve SAT (and all NP-complete problems) in linear time:

  1. first check if the SAT function has a solution with a single invocation of Count$\left(f,M\right)$. If no solutions exist - exit
  2. fix $x_1=1$, and check whether $g\left(x_2,\ldots,x_n\right)=f\left(1,x_2,\ldots,x_n\right)$ has a solution. the result tells us whether $x_1=1$ or $x_1=0$
  3. using the known variables, repeat step 2 with functions of decreasing number of variables
  4. after $n$ iterations, we learn the values of all variables which satisfy the SAT

So, either the Count$\left(f,M\right)$ algorithm is exponential in $n$, or we can solve NP-complete problems in polynomial time (which, naturally, can't be true).

$\endgroup$
4
  • $\begingroup$ If I don't even run any algorithm but just always return $t'=0$, then I'm guaranteed to get the $t=0$ case correct every time. In that sense, there's nothing too suspicious. $\endgroup$
    – DaftWullie
    Jun 29, 2023 at 7:31
  • $\begingroup$ thanks @DaftWullie, however the algorithm does not return $t^{\prime}=0$, rather a close value to $t$ $\endgroup$
    – inq
    Jun 29, 2023 at 11:57
  • $\begingroup$ I'm not saying that it always gives $t'=0$. The point I'm making is simply that there's nothing special about an algorithm that always gets the answer $t'=0$ if $t=0$ (because that's what my "algorithm" achieves). The challenge, of course, is to get $t'$ a better approximation if $t\neq 0$. But, even then you are basically trying to detect the existence of solutions. If you never see any solutions (which you can't if there aren't any), you return the answer $t'=0$. $\endgroup$
    – DaftWullie
    Jun 29, 2023 at 12:51
  • $\begingroup$ I agree with your theoretical complexity analysis that it is possible to return the value $0$ with certainty. But my question is about the specifics: What is the cost of the algorithm (number of Grover operator calls) to return a good approximation of the number of solutions and "no solutions" with certainty? $\endgroup$
    – inq
    Jun 29, 2023 at 21:19

1 Answer 1

1
$\begingroup$

I think I finally got it...

The key is that while we can't have "false positives" (returning a non-zero number of solutions when no solutions exist), there can certainly be "false negatives" (returning a zero as the number of solutions when in fact, there are solutions).

If we use QPE to estimate the number of solutions, we reduce the "false negative" probability by adding qubits to the "estimation register". But this requires adding more controlled $Q^{2^k}$ operations, which results in exponential time... which is to be expected for NP-complete problems.

In summary, the certainty of getting $t=0$ when there are no solutions is not very impressive when the same result ($t=0$) will be returned with high probability even when there is a single solution, unless we call the oracle "a very large" number of times.

$\endgroup$
1
  • $\begingroup$ Yes, it's exactly this! $\endgroup$
    – DaftWullie
    Jul 11, 2023 at 8:08

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.