Optimal quantization of histogram
This can be reduced to the following problem.

APPROXIMATE ROUNDING:
Input: real numbers $c_1,\dots,c_m \in \mathbb{R}$, an integer $d \in \mathbb{N}$
Goal: find non-negative integers $x_1,\dots,x_m \in \mathbb{N}$ that minimize
$\sum_i (x_i - c_i)^2$, subject to the requirement $\sum_i x_i = d$.

The reduction: define $S = \{i : H_i &gt; 0\}$, $x_i = Q_i - 1$ for $i \in S$, $d=2^n-1-|S|$, and

$$c_i = -1 + (2^n-1) H_i / \sum_j H_j.$$

Now the optimal solution to APPROXIMATE ROUNDING immediately yields the optimal solution to your problem, by setting $Q_i = x_i + 1$ for each $i \in S$ and $Q_i=0$ for each $i \notin S$.



Can we solve APPROXIMATE ROUNDING efficiently?  I don't know.  I conjecture there exists $t \in \mathbb{R}$ such that the optimal solution is $x_i = \lfloor t c_i \rceil$ for all $i$ (i.e., $x_i$ is $tc_i$ rounded to the nearest integer).  If this is true, we can use binary search to find $t$ such that $\sum_{i \in S} \lfloor t c_i \rceil = d$, and thereby solve APPROXIMATE ROUNDING efficiently.  However, I have no proof that this works.

Erwin Kalvelagen over on Math.SE has suggested that APPROXIMATE ROUNDING can be solved using a MIQP solver.