What is the initial state in the second register in Shor's algorithm?

Question

Following up on this question, can someone help me clear up the notation we're using for states in Shor's algorithm? It's very unclear what the sentence "where the second register is $|1\rangle$ made from $n$ qubits" in the Wikipedia article means. The input state is supposedly $|0\rangle^{\otimes 2n+1} \otimes |1\rangle$. The first register makes sense, and one could write $|0\rangle^{\otimes 2n+1}=|\underbrace{0 \ldots 0}_{2n+1}\rangle$. Would one say that's $|0\rangle$ made from $2n+1$ qubits?

It appears we have states for all integers $0 \le k < 2^n$, which makes sense because if our fundamental qubit states are $|0\rangle$ and $|1\rangle$ then we can write $k$ in binary and we have $2^n$ tensor product states. Isn't the state $|0\rangle = |\underbrace{0 \ldots 0}_{n}\rangle$ and $|1\rangle = |1\underbrace{0 \ldots 0}_{n-1}\rangle$?

Clearly there must be $n$ qubits in the second register as input since $U$ (multiplication by $a$ modulo $N$) is a $2^n \times 2^n$ matrix. Yes, $U$ has eigenvectors, and $|1\rangle$ is an equal sum of those eigenvectors, but that doesn't help me understand the fixed input state.

Answer 1

They mean that the second register uses $n$ qubits, and it's in the state $|1\rangle$.

This is using the standard way of enumerating the $2^n$ possible (computational basis) $n$-qubit states, so $|k\rangle$ denotes the $n$-qubit state corresponding to the binary string which in base-10 corresponds to $k\in\mathbb{N}$.

Consider for example $n=2$. Then $$|0\rangle \simeq|0,0\rangle, \quad |1\rangle \simeq|0,1\rangle, \quad |2\rangle \simeq|1,0\rangle, \quad |3\rangle \simeq|1,1\rangle.$$ So more generally, you could say that $|1\rangle$ denotes the $n$-qubit state with binary representation $|0\rangle^{\otimes(n-1)}\otimes|1\rangle$. Although this expression is generally not very insightful in this context.

Note also that conventions may vary, and so you might have the equivalence $|1\rangle\simeq|1\rangle\otimes|0\rangle^{\otimes(n-1)}$ rather than the one above. This doesn't affect any result of course, it's only a notational detail.

The reason you use this particular state for the second register is that, as you might observe directly, the modular multiplication operator $U_a$ has eigenvectors $|u_s\rangle$, corresponding to eigenvalues $e^{2\pi i s/p}$ with $p$ period, which sum to precisely $|1\rangle$. Therefore using $|1\rangle$ as second register is a convenient way to perform a quantum phase estimation with a set of possible eigenstates of $U_a$ in superposition.