$\def\ket#1{|{#1}\rangle}$
Question
What is the minimum number of gates required to create the $N$-qubit state $\ket{\psi} = \frac{\ket{a} + \ket{b}}{\sqrt2}$ from the all-zeroes state, where one term in the superposition, $\ket{a}$, can be created through a depth $D$ random circuit with $ND$ gates, and separately the other term, $\ket{b}$, can be created through a separate depth $D$ random circuit with $ND$ gates.
What is the complexity of this final state $\ket{\psi}$? That is, what is the minimum number of gates would it usually take to generate the superposed state $\ket{\psi}$ (or get $\epsilon$-close to it) from an all zeroes state?
I expect the answer to be between $ND$ and $2ND$ - probably it's the latter, or something like $2N(D+1)$?
Background
Suppose you have a very long chain of $N$ qubits. If I start in $\ket{000\cdots}$ and apply a depth-$D$ circuit of local Haar-random 2-qubit gates, ending up in state $\ket{\phi}$ it is known that with high probability there will be no other way to get to the same final state which uses significantly fewer than $N\times D$ quantum gates: there are unlikely to be shortcuts to random circuits (as long as the depth $D$ is less than exponential in $N$).
Similarly, if you prepare two such states $\ket{a}$ and $\ket{b}$ and want to map between them, then it's (conjectured?) that the complexity of mapping from $\ket{a}$ and $\ket{b}$ (or vice-versa) will be around $2ND$. This is another consequence of these ``second law'' no-shortcuts for random circuits conjectures. To get from $\ket{a}$ to $\ket{b}$, you've basically just got to undo nearly all of the gates that built $\ket{a}$, until you're basically back at a product state, and then apply the gates that build $\ket{b}$, without shortcuts.
Finally, I'm aware of work relevant to the complexity of detecting superpositions of random states, or flipping the phase in the superposition, or swapping $\ket{a}$ and $\ket{b}$, and so on. But my knowledge of the complexity of superpositions is lacking.
For my question of the complexity of a superposition of two such states, is the answer also $2ND$?
