Amplitude Estimation/Counting - unsatisfiability

Question

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).

Answer 1

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.