Trying to understand how the first Hadamard gate in Deutsch–Jozsa algorithm works

Question

I'm still a beginner in the quantum aspect of computer science (self-studying). So please bear with me if this may sound like a stupid question.

I know Hadamard gate transforms qubit into a superposition state with $\frac{1}{2}$ chance that the outcome would be 0 or 1 when the wave function collapses:

$$\frac{\left|0\right\rangle + \left|1\right\rangle}{\sqrt2} \text{ for }\left|0\right\rangle \\ \frac{\left|0\right\rangle - \left|1\right\rangle}{\sqrt2} \text{ for }\left|1\right\rangle$$

For already-in-a-superposition qubit, it would be just some linear transformation.

$$\alpha\left|0\right\rangle + \beta\left|1\right\rangle \rightarrow \alpha \frac{\left|0\right\rangle + \left|1\right\rangle}{\sqrt2} + \beta \frac{\left|0\right\rangle - \left|1\right\rangle}{\sqrt2} = \frac{\alpha+\beta}{\sqrt2}\left|0\right\rangle + \frac{\alpha-\beta}{\sqrt2}\left|1\right\rangle $$

But I got really confused when I see the $\Sigma \left|x\right\rangle$ in the equation on the Wikipedia article about Deutsch–Jozsa algorithm.

A Hadamard transformation is applied to each bit to obtain the state

Why is it doing a summation with a ever-increasing value of $x$? My understanding of a qubit is that it can only be in either $\left|0\right\rangle$, $\left|1\right\rangle$ or a superposition state.

What the equation is doing above appears to indicate that if $n$ is 2, we would get

$$\frac{1}{\sqrt{2^{3}}} \left|0\right\rangle (\left|0\right\rangle - \left|1\right\rangle) + \frac{1}{\sqrt{2^{3}}}\left|1\right\rangle (\left|0\right\rangle - \left|1\right\rangle) + \\\frac{1}{\sqrt{2^{3}}} \left|2\right\rangle (\left|0\right\rangle - \left|1\right\rangle) + \frac{1}{\sqrt{2^{3}}} \left|3\right\rangle (\left|0\right\rangle - \left|1\right\rangle)$$

How do I make sense of the $\left|2\right\rangle$ and $\left|3\right\rangle$?

[Update]

As I was writing the question, I remembered that qubits in the state of $\left|1\right\rangle$$\left|0\right\rangle$ are often expressed as $\left|10\right\rangle$. Since we are working with two-state system here I figured out that the 2 and 3 should be converted into binary in this context. And therefore the expression should be interpreted as

$$\frac{1}{\sqrt{2^{3}}} (\left|0\right\rangle (\left|0\right\rangle - \left|1\right\rangle) + \frac{1}{\sqrt{2^{3}}}(\left|1\right\rangle (\left|0\right\rangle - \left|1\right\rangle) + \\\frac{1}{\sqrt{2^{3}}} (\left|10\right\rangle (\left|0\right\rangle - \left|1\right\rangle) + \frac{1}{\sqrt{2^{3}}} (\left|11\right\rangle (\left|0\right\rangle - \left|1\right\rangle)$$

It appears that things are making a lot more sense now. But as I take a deeper look into the expression above, two questions come to me:

1. Why do I see so many $\left|0\right\rangle - \left|1\right\rangle$ but not a single $\left|0\right\rangle + \left|1\right\rangle$ ? (Intuitively I expect to see just one $\left|0\right\rangle - \left|1\right\rangle$ since we can only get $\frac{\left|0\right\rangle - \left|1\right\rangle}{\sqrt2}$ when it is in the state of $ \left|1\right\rangle$ and there is only one qubit in $ \left|1\right\rangle$).

2. Why are there only $2^{n}$ possible states with each having the chance of $(\sqrt{2^{3}})^2$ when the input is $2^n+1$ qubits? Adding four $(\sqrt{2^{3}})^2$ together doesn't give us 1.

Answer 1

After studying the maths behind it, I realized that a linear algebraic expression for a quantum state may not appear to be intuitive at first sight (or prehaps it is only to the not mathematically gifted ones like myself).

Apparently, this is how the expression in the Wikipedia page is derived:

$$\begin{align} &\frac{\left|0...0\right\rangle + \left|0...1\right\rangle + \left|1...1\right\rangle}{\sqrt2 ... \sqrt2} \cdot \frac{1}{\sqrt{2}} (\left|0\right\rangle - \left|1\right\rangle)\\ =&\sum^{n}_{x=0}\frac{1}{\sqrt{2^n}} \left|x\right\rangle \cdot \frac{1}{\sqrt{2}} (\left|0\right\rangle - \left|1\right\rangle) \\=&\sum^{n}_{x=0}\frac{1}{\sqrt{2^{n+1}}} \left|x\right\rangle \cdot (\left|0\right\rangle - \left|1\right\rangle) \\ =&\frac{1}{\sqrt{2^{n+1}}} \sum^{n}_{x=0} \left|x\right\rangle (\left|0\right\rangle - \left|1\right\rangle) \end{align}$$

Now this explains why it is alright to have the four $\frac{1}{\sqrt{2^{3}}}$ probability amplitudes above, which is indeed just the product of $\frac{1}{\sqrt{2^{2}}}$ and $\frac{1}{\sqrt{2}}$.

$\frac{\left|0...0\right\rangle + \left|0...1\right\rangle + \left|1...1\right\rangle}{\sqrt2 ... \sqrt2} \cdot \frac{1}{\sqrt{2}} (\left|0\right\rangle - \left|1\right\rangle)$ sure feels like we are having a superposition state within a superposition state (I'm not sure if that is the correct way to interpret it). And this is probably what makes an entangled system so magical when it comes to computation.