Assuming that the probability distribution is smooth, differentiable and has an upper bound on its derivative, $$D_p = \max_x |p'(x)|,
  \label{eq:max-derivative}$$ we obtain upper bounds for the entropy of the extra qubit. For one added qubit, $k=1$ our bound reads $$S[\rho^{(m,1)}] \leq \sqrt{2(1-P)} \leq 2\sqrt{D_p}|b-a|2^{-m/2}.
  \label{eq:one-qubit-bound}$$ If $k$ is larger, we have roughly $$S[\rho^{(m,k)}] \leq \mathcal{O}\left( 2\sqrt{D_p}|b-a|2^{-(m-k)/2} \right).
  \label{eq:k-qubit-bound}$$ Note that this argument easily extends to the Riemann-type  or Simpson sampling , because the differences between them decays exponentially with the number of qubits.

The fact that adding every new bit requires a small amount of entanglement implies that the probability state $\ket{p^{(m)}}$ has an efficient matrix-product state (MPS) representation. A matrix product state is a decomposition of a wavefunction as a contraction of matrices that are labeled by the physical indices of a composite quantum system $$\ket{p^{(m)}} = \sum_s \sqrt{p^{(m)}(s)}\ket{s} \simeq \sum A_{\alpha_1}^{s_1}A_{\alpha_1,\alpha_2}^{s_2}\cdots
  A^{s_m}_{\alpha_{m}}\ket{s_1,s_2,\ldots,s_m}.
  \label{eq:MPS}$$ Each of the tensors is in general different, and has three indices $A_{\alpha_i,\alpha_{i+1}}^{s_i}\in \mathbb{C}^{2\times \chi_i\times \chi_{i+1}}.$ There is one physical index $s$ of dimension 2, and two *bond dimensions* of sizes $\chi_i$ and $\chi_{i+1}.$ In our particular case, the fact that $S[\rho^{(i,m-i)}]$ decays exponentially with $i$ means that the bond dimensions also decrease extremely 