The LGZ algorithm for Topological Data Analysis via computing Betti Numbers is a quantum algorithm that relies on sampling random eigenvalues of an appropriate linear operator. The expected fraction of these eigenvalues that are 0 is equal to the normalised Betti Number.

My question concerns how many samples of random eigenvalues one would need to be confident that the estimator (i.e. the ratio of eigenvalues that are 0 in the sample) is close to its true value (the normalised Betti Number.

Abstracting away all details of quantum algorithms, the problem is effectively the following: Suppose we have a coin with some unknown probability of heads (p).

We make N flips of the coin with the aim of knowing p to within error ±ϵ, and with probability of failure <δ. For a given target of (ϵ,δ), how many flips N do we need to make?


1 Answer 1


The answer is $$ \Theta\left( \frac{\log(1/\delta)}{\varepsilon^2} \right) $$ for a uniform minimax bound. The upper bound follows from a Hoeffding bound; for the lower bound, you can derive it from the "simpler" testing question, as, e.g., outlined in this Wikipedia article. You can have a local minimax version as well, if that's what you want, with a dependence on the (unknown) parameter $p$ in the bound; see, e.g., this question.

  • $\begingroup$ Hi thank you for your answer! The wikipedia link you mention isn't correctly linked - could you please fix that? $\endgroup$
    – shashvat
    Sep 19, 2022 at 15:31
  • $\begingroup$ @shashvat My bad: it should be fixed now. $\endgroup$
    – Clement C.
    Sep 19, 2022 at 19:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .