Solution
= Solution
For perfect balance, $k=2^{n-1}$ and the all-zero probability is zero. For other balances the one-shot outcomes overlap the constant case. Repeat <Deutsch-Jozsa algorithm> and declare nonconstant upon any nonzero result. Constants are never misclassified; a $k$-balanced <function> fails after $R$ trials with probability $q^R$, $q=(1-2k/2^n)^2$. It suffices that $R\ge\log\epsilon/\log q$, using that many oracle calls.