For those who are curious, here's the specific thing that Appendix C misses. Suppose you have gates (quantum or CMOS -- doesn't matter), and they are imperfect

For those who are curious, here's the specific thing that Appendix C misses. Suppose you have gates (quantum or CMOS -- doesn't matter), and they are imperfect. And you want to implement some algorithm that won't work without error correction. So you use an error-correcting code of complexity c. (Classically, this could be as simple as copying every memory cell c times and taking a majority vote of c attempts of each gate. Some extra complication is needed to put the pieces together while still getting exponentially close to 100% accuracy.) So you start by setting c=3 (majority vote of three tries), and you get really really far. But you need a longer calculation, so you go up to c=5. Then c=7. Then c=9. And so on. And you discover that this actually scales pretty poorly. This is because the little gizmo that takes a majority vote is itself error-prone, and just making it wider doesn't improve fast enough with increasing width. But you can instead use recursive error correction. Take c=3, look at the result as its own imperfect computer, and error-correct that with a second code with c=3. It's kind of like c=9, except all the little majority-of-three voting gizmos become majority-of-majorities-of-3 instead of majority-of-9 gizmos, and you get a natural way to make them arbitrarily wide. And (IIRC -- it's been quite a while since I've gone through the whole derivation), this works! You can recurse this construction (or at least something quite similar) a number of times that grows sufficiently slowly in the size of the circuit that you get the overall O(t * polylog(t)) scaling that you want. To make this work on a quantum computer is much harder (majority-of-3 doesn't work at all -- you need a bare minimum of 5 physical qubits per logical qubit for anything resembling this to work, and it's not a majority vote per se), but the overall conclusion is the same. The paper looks at what coding width is needed without recursion to make Grover's algorithm work for large problems, concludes that you at least square the complexity, and decides that Grover's algorithm is useless. But anyone actually trying to do a huge Grover search would use a proper recursive code, and they wouldn't have this problem. And this has known since 1996.