Cycling through $\{0,1\}^{(2^n)}$ such that all Hamming distance appear equally frequently Let $n\in\mathbb{N}$ be a positive integer. Let $\{0,1\}^{(2^n)}$ be the set of $0,1$-sequences of length $2^n$. For $a,b\in \{0,1\}^{(2^n)}$ let $d_h(a,b)$ be the Hamming distance between $a$ and $b$.
Question. Is there a bijection $\varphi:\{0,\ldots,2^{(2^n)}-1\} \to \{0,1\}^{(2^n)}$ such that the multiset
$$\Big\{d_h\Big(\varphi(k), \varphi(k+1)\Big): k< 2^{(2^n)}-1\Big\}\cup\Big\{d_h\Big(\varphi(2^{(2^n)}-1), \varphi(0)\Big)\Big\}$$
is composed of elements $1, 2, \dots, 2^n$ with the same multiplicity $2^{(2^n)} / 2^n = 2^{2^n - n}$?
Example. For $n = 1$, the answer is yes; consider the "run" $00, 11, 10, 01$, that is, the possible Hamming distances $1$ and $2$ each appear $2$ times when going through all strings of length $2^n = 2^1$.
 A: The answer is yes.
The proof is as follows: If there is a Hamiltonian cycle $f: \{0,...,2^{2^n}-1\} \rightarrow \{0,1\}^{2^n}$ of the hypercube where the number of edges of a given direction in the Hamiltonian cycle are the same, then there is such a bijection $\varphi$, by setting $\varphi_m(x)=\sum_{k=1}^m f_k(x)$, $m=1,2, ... 2^n$ (i.e. taking the cumulative sum of $f(x)$). Such a Hamiltonian cycle will be called a balanced Hamiltonian cycle.
My construction of balanced Hamiltonian cycles is inspired by this paper, which provides balanced Hamiltonian cycles for $n=1,2,3$. The construction for $n=2$ will serve as the base case of mathematical induction.
Assume the existence of a balanced Hamiltonian cycle for $n$, and make it a directed cycle. Let $g$ be a function on $\{0,1\}^{2^n}$ where $g(x)$ is the next vertex of $x$.
Let $h(x)$ be an involution on $\{0,1\}^{2^n}$ such that there are exactly $2^{2^n}/2^n$ values where $x$ and $h(x)$ differs at the $k$th bit, $k \in \{1 ... 2^n \}$. (The existence of $h$ will be proven later.)
Then there is a balanced Hamiltonian cycle on the hypercube of dimension $2^{n+1}$.
Let's identify the $2^{n+1}$-dimensional hypercube by the Cartesian product of the $2^n$-dimensional hypercube with itself. Let $(a_0, b_0)$ be a vertex of the $2^{n+1}$-dimensional hypercube. The sequence $(a_k, b_k)$ is defined as follows: if $k$ is odd, then $(a_{k+1}, b_{k+1})=(a_k, g(b_k))$; if $k=0 \text{ or } 2 
 (\text{mod } 2^{2^n+1})$, then $(a_{k+1}, b_{k+1})=(g(a_k), b_k)$; otherwise $(a_{k+1}, b_{k+1})=(h(a_k), b_k)$
One can see the function $k\rightarrow (a_k, b_k)$ plays the role of $f$ for $n+1$. The point is to analyze a cycle of length $2^{2^n+1}$, conclude that $(a_{2^{2^n+1}m}, b_{2^{2^n+1}m})=(g(g(a_{2^{2^n+1}(m-1)})),b_{2^{2^n+1}(m-1)})$ and it follows that $(a_k, b_k)$ traces out a Hamiltonian cycle (i.e. you need $m=2^{2^n-1}$ for the point to return to $(a_0,b_0)$). It's easy to check the Hamiltonian cycle is balanced.
Now we only to prove the existence of $h$.
If $n=2$, then such $h$ exists:
0000 - 0001
1110 - 1111
0010 - 0110
0011 - 0111
0100 - 1100
0101 - 1101
1000 - 1010
1001 - 1101

Assume the existence of $h$ for $n$. Choose a subset $K$ of $\{0,1\}^{2^n}$ with size $2^{2^n-1}$ that is closed under $h$ and there are exactly $2^{2^n-1}/2^n$ elements $x$ in $K$ where $x$ and $h(x)$ differs at the $k$th bit ($k \in \{1 ... 2^n \}$).
Define a function $p$ on $\{0,1\}^{2^n} \times \{0,1\}^{2^n}$: $p(a,b)=(a,h(b))$ if $b \in K$, otherwise $p(a,b)=(h(a),b)$. Then $p$ plays the role of $h$ for $n+1$.
