We generalize. Claim. If we split $Q$ into the parts $A$ and $B$, then there are at least $\min(|A|,|B|)$ pairs $(a,b)\in A\times B$ such that $a$ and $b$ differ in only one term. Proof. Our claim is clear for $n=1$; we will now induct from $n$ to $n+1$. WLOG $|A|\le |B|$. If $A$ has $x$ elements ending in $0$ and $y$ elements ending in $1$, then $B$ has $2^n-x$ elements ending in $0$ and $2^n-y$ ending in $1$; WLOG $x\ge y$. Applying the induction hypothesis, the number of pairs $(a,b)$ generated by $a,b$ ending in the same number is $\ge \min(x,2^n-x)+\min(y,2^n-y)$, and the number of pairs $(a,b)$ differing exactly in the last component is $\ge |x-y|$, so in total, we get at least \[ \min(x,2^n-x)+\min(y,2^n-y)+|x-y|\ge y+y+(x-y)=x+y=|A| \]pairs $(a,b)\in A\times B$ differing in just one component. $\blacksquare$