Clarification for argument in proof of search in N^1/3 queries with hidden variables/non-collapsing measurements

Question

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:

1. 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).
2. 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?
3. 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?

Answer 1

The short answer is that the state we wrote down is only an approximation in the large $n$ limit (which is all that is required to prove the upper bound). The state isn't normalized for finite $n$, but becomes normalized as $n \rightarrow \infty$. It looks like we either used a different approximation than what I will describe below, or made a typo - thanks for pointing this out! - but these details don't affect our proof.

The details:

After $t$ Grover iterations, the exact state of the system is $\sin((2t+1)\theta) | x \rangle + \cos((2t+1)\theta) \Sigma_{y\neq x} \frac{1}{\sqrt{2^n-1}} | y\rangle$ Where $\theta$ is such that $\sin(\theta) = 2^{-n/2}$ (this exact solution is given in Nielsen & Chuang Section 6.1.3).

Working with the exact expression isn't very informative about how this state behaves asymptotically. So most of the time, to analyze asymptotics, people use the approximation that for small $\theta$, we have that $\sin\theta \approx \theta$ and $\cos\theta\approx 1-\theta^2/2$. Using this approximation, you can show that if you set $t=2^{n/3 -1}$, then your resulting state is $\approx \frac{2^{n/3}+1}{2^{n/2}} |x\rangle +\left(1-\frac{1}{2}\left(\frac{2^{n/3}+1}{2^{n/2}}\right)^2\right) \Sigma_{y\neq x} \frac{1}{\sqrt{2^n-1}} | y\rangle$. Note we've lost the normalization because of our approximation - so if you plug in any $n\in\mathbb{N}$ as you did, you'll get a non-normalized state. However as $n\rightarrow\infty$ the state becomes normalized, because the approximation $\sin\theta\approx \theta$ becomes increasingly accurate.

From this, you can easily see that if you measure this state, you see $x$ with probability $\Theta(2^{-n/3})$. Hence if you could perform $\tilde{O}(2^{n/3})$ non-collapsing measurements, you'd see the marked item once with constant probability. This is all we're using about the state to prove our upper bound.