 Solution

A vertex is a bit string of length $k$, and adjacent vertices differ in one coordinate. Therefore the parity of the number of one-bits changes along every edge. The even-parity and odd-parity strings are a bipartition, proving $Q_k$ is bipartite for every $k\ge 1$, in particular for the requested range.