Showing ${\rm Aut}(D_{2^n})\cong{\rm Aut}(Q_{2^n})$ for $n\ge 4$.

Here is one general way of computing automorphism groups.

Consider for example $G = \langle r,s \mid r^{2^{n-1}} = s^2 = 1, srs^{-1} = r^{-1} \rangle$.

Any automorphism $\phi: G \rightarrow G$ is determined by $\phi(r)$ and $\phi(s)$. Furthermore $\phi(r)$ and $\phi(s)$ must satisfy the same relations, i.e. $$\phi(r)^{2^{n-1}} = \phi(s)^2 = 1,\ \phi(s)\phi(r)\phi(s)^{-1} = \phi(r)^{-1}.$$

Conversely, suppose that you can find generators $x,y \in G$ of $G$ such that they satisfy the same relations: $$x^{2^{n-1}} = y^2 = 1,\ yxy^{-1} = x^{-1}.$$

Then by the universal property of free groups, there exists a surjective homomorphism $\phi_{x,y}: G \rightarrow G$ with $r \mapsto x$ and $s \mapsto y$. Since $G$ is finite, the map $\phi_{x,y}$ must also be an automorphism.

So to determine $\operatorname{Aut}(G)$, it will suffice to find pairs $(x,y)$ which generate $G$ and have the same relations as $(r,s)$. Check that they are $x = r^d$ with $d$ odd and $y = r^e s$ with $e$ integer. This tells you precisely what the automorphisms of $G$ are.

Then you want to do the same thing with $H = \langle r,s\mid r^{2^{n-1}} = 1, s^2=r^{2^{n-2}}, s^{-1}rs=r^{-1} \rangle$. Assuming $n > 3$, the automorphisms of $H$ correspond to the same pairs $(x,y) = (r^d, r^e s)$ as for $G$. From this it should be clear that $\operatorname{Aut}(G) \cong \operatorname{Aut}(H)$.

Both groups have a unique cyclic subgroup of index $2$ ($\langle r \rangle$ and $\langle x \rangle$), so this is fixed by all automorphisms, which must map $r \mapsto r^a$ or $x \mapsto x^a$ for some odd $a$ with $1 \le a < 2^{n-1}$.

Similarly, an automorphism must map $s \mapsto sr^b$ or $y \mapsto yx^b$ for some $b$ with $0 \le b < 2^{n-1}$.

You can check from the relations of the presentations that, for both of the groups, each of these maps does indeed define an automorphism of $D_{2^n}$ or $Q_{2^n}$. For example we have $(sr^b)^2 = ssr^{-b}r^b = s^2$ and similarly $(yx^b)^2 = y^2$ for all $b$, so the second defining relation is preserved.

Let's denote this automorphism by $\alpha(a,b)$, so for both groups the set of automorphisms is $$\{\alpha(a,b): 0 < a < 2^{n-1}, a\ {\rm odd}, 0 \le b < 2^{n-1}\},$$ which has size $2^{2n-3}$.

To show that the two automorphism groups are isomorphic, let $$\Lambda = \{ 1,\rho,\rho^2,\ldots,\rho^{2^{n-1}-1},\sigma,\sigma\rho,\sigma\rho^2,\ldots\sigma\rho^{2^{n-1}-1}\}$$ regarded as a set of abstract symbols, and notice that mapping $\rho$ and $\sigma$ to $r$ and $s$ defines a bijection between $\Lambda$ and the elements of $D_{2^n}$, whereas mapping $\rho$ and $\sigma$ to $x$ and $y$ defines a bijection between $\Lambda$ and the elements of $Q_{2^n}$.

Using these bijections, the automorphisms $\alpha(a,b)$ of $D_{2^n}$ or $Q_{2^n}$ induce permutations of the set $\Lambda$, which in both cases is $$\rho^i \mapsto \rho^{ia},\ \sigma\rho^i \mapsto \sigma \rho^{b + ia},$$ where of course the exponents are reduced mod $2^{n-1}$.

So the automorphism groups of $D_{2^n}$ and $Q_{2^n}$ induce exactly the same (faithful) actions on the set $\Lambda$ and hence they must be isomorphic groups.