 3

Throughout this question let $|A_0⟩={\sum }_{f(x)=0}|x⟩$, $|A_1⟩={\sum }_{f(x)=1}|x⟩$, and $|J⟩={\sum }_{x=0}^{N-1}|x⟩=\sqrt{N}|e_0⟩$. These subset sums are unnormalized: $⟨A_j|A_j⟩=S_j$ and $⟨A_0|A_1⟩=0$. The promise implies that $N>0$ is divisible by four. No power-of-two assumption is needed for the abstract $N$-dimensional calculation.