Questions about Farhi's pre-Adiabatic paper

Question

I have been going through Eddie Farhi's 6-pages long pre-Adiabatic paper, An Analog Analogue of a Digital Quantum Computation.

I guess I understand most of the math and physics but I am struggling with the intuitions used throughout the paper. Here are my questions.

Introduction of $|r\rangle$ on page 3: I understand that $|r\rangle$ and $|w\rangle$ are orthonormal. But I don't see why the authors introduced this state.

Use of Norm in equation 17 on page 4: The equation is as follows. $$\sum_w |||\Psi_w, t\rangle - |\Psi, t\rangle||^2 \ge N \varepsilon$$ There are more than one kind of norms. What kind of norm are we talking about here? Why? What is the physical significance of this quantity in this context?

Answer 1

Everything interesting happens in this paper happens within the 2D subspace generated by the two vectors $|s\rangle$ and $|w\rangle$. The vector $|r\rangle$ is a vector from this subspace orthogonal to $|w\rangle$, giving us the basis $|w\rangle, |r\rangle$, where the analysis will be very simple (using 2x2 matrices).

The norm in the second question is simply $|||a\rangle||^2 = \langle a | a \rangle $. The meaning of individual terms in the sum is: "Does the result of our (Hamiltonian) algorithm actually get away from the (useless) state we would get without applying the oracle at all?" If this term is small for many different instances (different $w$'s), the algorithm doesn't work, as it would likely give the same (wrong) answer for these instances. Thus, if the sum over all of the $w$'s were small, it would tell us that the algorithm fails. If it is large, it doesn't immediately mean it works, however, having the sum large is a necessary condition for a successful algorithm.