I saw it as a sort of science-fiction - imagine living in a world where the smartest intellectuals all struggled to solve basic exercises about graph theory. Really imagine living in such a world - would you not feel frustrated when you tried to explain this basic concept to these supposed experts and they just didn't get it? The main character must have felt like he was going crazy!
For learning the theory behind quantum computing, I usually recommend Watrous's lecture notes [1] - they start out by immediately giving a helpful analogy to ordinary probabilistic computation.
The online tutorial [2] is a good followup, especially if you want to understand Clifford gates / stabilizer states, which are important for quantum error correction.
If you have a more theoretical bent, you may enjoy learning about the ZX-calculus [3] - I found this useful for understanding how measurement-based quantum computing is supposed to work.
There is no general procedure for computing upper bounds on busy beaver numbers (this can be proven). We haven't even come close to enumerating all of the interesting six-state Turing machines, so right now we don't even have a wild guess for an upper bound on BB(6).
I've only skimmed the paper, but this looks very nice: the construction is very simple (aside from the precise choices of the parameters), just the analysis to show that it works is difficult.
(I bet the construction can be refined - it feels like there is a semidefinite programming problem lurking in the background, so there is probably a way to mindlessly optimize things with an SDP solver once the proof technique is rephrased a bit.)