Let $N=2^n$. In Aaronson's Quantum Computing and Hidden Variables (1) and the recent follow up by Aaronson, Bouland, Fitzsimons, and Lee The space "just above" BQP (2), we consider models of computation involving hidden variables or non-collapsing measurements, and prove that this model of computation is able to simulate Grover's algorithm in time $O(N^{1/3})$.
The proof — Theorem 10 of (1) or Theorem 4.1 of (2); both go the same way for my question — starts with applying $N^{1/3}$ Grover iterations. After this we should have the state:
$$\alpha \lvert x\rangle+\beta \!\!\!\sum_{y \in \{0,1\}^n} \!\!\lvert y\rangle$$
where $\alpha = \dfrac{1}{\sqrt{2^{n/3} + 2^{-n/3 + 1} + 1}}$ and $\beta = 2^{-n/3}\alpha$.
My questions:
- From where do we follow this? The original paper from Grover is referenced, but he provides only the recurrence (in later versions he added a reference to the explicit sin/cos solution).
- In my opinion, the state should be something like $\alpha \lvert x\rangle+\beta \sum_{y \in \{0,1\}^n \:\! \setminus\{x\}} \lvert y\rangle$, otherwise we would have for $n=3$ a superposition of $1 + 2^3 = 9$ states. I guess this is only a lazy notation for convenience?
- Is this state normalized? If I try e.g. $n=3$, then I will have: $$\begin{aligned}[b] \alpha &= \frac{1}{\sqrt{2^{1} + 2^{-1 + 1} + 1}} = \frac{1}{2} \\[1ex] \beta &= 2^{-n/3}\alpha = 2^{-1} \cdot \frac{1}{2} = \frac{1}{4} \end{aligned}$$ If we assume a factor $k$ from the sum, we can try to check the normalization with: $$\begin{aligned}[b] 1 = \alpha^2 + (k\beta)^2 = \bigl(\frac{1}{2}\bigr)^2 + \bigl(\frac{k}{4}\bigr)^2 ={}& \frac{4 + k^2}{16} \\[1ex]\implies{}& k^2 = 12 \end{aligned}$$ which is not solvable in integer. (If I take the $n$ general, substitute by $2^{n/3} = s$, and solve for $\alpha^2 + (k\beta)^2 = 1$, I get a polynomial in 3. degree. The general case does not give any insight for me)
The statement from (1) that "one can check that this state is normalized" does not provide a good feeling for my question. Scott Aaronson published a "list" of some errata on his blog for this paper, but the list did not include this. What am I missing?