Aaaaah nice. It makes me happy that the first question posted is the hardest. Or rather, one can hope that's the case. :]
(These comments are mine; I'll be taking point this week, relaying these questions to the other two authors, who are traveling.)
This is a giant topic of ongoing research (of course). While I can't provide a direct and simple answer to Bruce's original question, the following notes may help you to think about the issue and explore it a bit. I'll start by hitting some of the top-line issues you've raised, and see where we go from there.
FT vs. Raw Qubits: I tend to assume that serious codebreaking algorithms (ones which actually break encryption we care about) will require error-corrected
fault-tolerant QPUs (Quantum Processing Units), just as serious computing applications require reliable RAM. I may be wrong in this; Craig Gidney and Martin Ekerå published a paper in May this year entitled
How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. FT machines don't exist yet (they will), and 20M-qubit machines don't exist yet either. The state of the art today is 53-70 noisy qubits. Although the code samples in our book do run on present-day QPUs, the book is written primarily with upcoming FT machines in mind.
Factoring vs. Logic Search: A lot of emphasis is placed on Shor's Factoring Algorithm (chapter 12 in the book, code sample
here), however (just my personal view) I think people tend to overlook generalized logic reversal. As Stephan mentioned, most crypto is built on digital math (such as multiplication) which is easy to do forward and difficult to do in reverse. All QPUs (including both gate-based systems like the IBM Q, and annealers like D-Wave's machine), can take classical forward logic functions and with some efficiency determine the inputs, given the outputs (there are really fun examples of this in chapter 10 in the book, code sample
here). The strength of this is that it's more general than factoring, and still demonstrates a quantum advantage.
Quantum Encryption: Of course as Mainak mentions, the new forms of encryption introduced by QPUs (QKD, uncopyable data, etc) are very interesting as well, primarily because they're based on physical properties of information itself, not on math problems (code sample: "Spy Hunter" in chapter 2,
here).
Bitcoin: In an effort to form my own opinions on this, I recently picked up
Programming Bitcoin by Jimmy Song. It's the Bitcoin hands-on programmer's equivalent of our book, with a good explanation of elliptical encryption, proof-of-work, etc. I used Jimmy's book side-by-side with ours; I was doubtless re-treading existing research, but for me that was the right way to explore the problem.
None of this answers your question directly, but hopefully it gives you some starting material for thinking about the issue.
