I want to try a probabilistic proof for this problem. Please give some comments on this attempt at a proof.
Let $G$ be our complete graph $K_{2^{3d}}$, with the edges colored red/blue randomly and independently. My observation is that, any $d$-dimensional cube $Q_d$ can be constructed from $2$ copies of $Q_{d-1}$, with the missing edges added appropriately. Since $2^{3d} = 2^{3(d-1)}\cdot 8$, by induction $G$ contains $8$ copies of monochromatic $Q_{d-1}$, at least $4$ of which must be of the same color (wlog let the color be red).
Now consider the event $X$ that none of the pair of $Q_{d-1}$ among those $4$ copies form a monochromatic red $Q_d$. This is the union of the events that all pairs of $Q_{d-1}$ are invalid. By the union bound, we have: $$\mathbb{P}(X) \leq \sum \mathbb{P} \text{(the pair of $Q_{d-1}$ forms invalid $Q_d$)} = {4 \choose 2} \cdot \left( \frac{1}{2} \right)^{2^{d-1}} = \frac{6}{2^{2^{d-1}}} < 1, \text{ for $d>1$.}$$
Hence the probability that one of the pair of $Q_{d-1}$ forms a valid, monochromatic red $Q_d$ is strictly positive.
—————————————
Edit: I’m putting up a bounty for this question. Hints or answers would be appreciated.
This proof does not work. The probability that any edge causes the pair of $Q_{d-1}$ to be invalid is $1/2$, so the probability that there is an edge that causes it to be invalid is one minus the probability that all edges are valid, that is $$1-\left(\frac12\right)^{2^{d-1}}.$$ This number is unfortunately way too large for the probabilistic proof to carry through.