Tuesday, May 26, 2020

A #QuantumNative Engineer's Bookshelf


Quantum computing involves three major technical areas: mathematics, physics and computer science and engineering, and a fourth, important area: society. What does a new engineer, or student, aspiring to be a #QuantumNative need to know? Unlike some other researchers, I do not think it's necessary to learn physics first, or computer science first. I think you can dive straight in and learn quantum computing without insisting on quantum mechanics as a formal prerequisite. In fact, that's how you become #QuantumNative -- by learning quantum computing in parallel with classical. But, I do think there is  a structure to all of what you need to know, and an ordered walk through that will ease your way.
One of the duties of a university is to create a curriculum that provides structure to the body of knowledge. A book provides structure to a subset of that knowledge. Research papers move us forward, but assume a lot and ignore even more. Simply hopping around the web, looking for what you need at the moment, leaves gaps and causes you to miss things that an engineer with a more carefully curated set of knowledge will pick up on. Build your mental toolkit well, and you will be rewarded.
While books aren't the only way to learn, they are perhaps my favorite, so let me do this in terms of a bookshelf. These are not merely trophy books to look good, they should be used; by the time you're my age, they should be battered, coffee-stained and full of highlights and notes in the margins.

Many of these titles can be swapped out for similar, in some cases more modern, ones, but a few are truly unique, and several have their own Wikipedia pages. I think you'll see which are which.

Of course, if you're an undergrad, getting through all of these in four years will require focus and dedication, while at the same time, you must also keep up your social life, physical and mental health, and non-technical learning.  But hopefully these books will help guide you in good directions as your career develops.

Popular Science and on up to Beginners' Recommendations

  • Hillis, The Pattern on the Stone: my single favorite popular science book on what a computer is.
  • Conery, The Imposter's Handbook: hard to do better than this for a quick-and-dirty tour of CS, if you program a bit and are trying to get oriented to the more formal aspects, as well as the "secret handshake" lingo that gets tossed around by experienced hands.
  • Fortnow, The Golden Ticket: the best layman's introduction to computational complexity.
  • Williams and Clearwater, Ultimate Zero and One: when I was getting started in quantum computing, this popular science-level book cleared up a number of concepts for me. Now there are many popsci books on quantum, so it may have been surpassed, and certainly some will be far more up to date, so I don't mind if you swap this one out for a favorite of your own -- but it worked for me, and it will work for you.
  • Feynman Lectures on Computation: now quite old, and always quite idiosyncratic, but I was there; you'll find my name in the acknowledgments at the beginning. Feynman opened my eyes to the ideas of computation, perhaps even more than Carver Mead, from whom I took CS1 three years earlier. The book is deceptively simple; you can understand most of the content with minimal background, but that doesn't mean it's really a beginner's book. This will, inevitably, force you to rethink what you know about computers. What a broad-ranging way of thinking...
  • Sutor, Dancing with Qubits: this is intended to be, and is quite successful at being, more than a popsci book, but I've put it here because of its accessibility and how little it presumes you know; it begins with the very basics of binary numbers and complex numbers. The book is almost evenly split between background material (the first 200 pages) and quantum computing (the next 250). Yes, there's quite a bit of math in it, so it's more intense than a popsci book, but you won't regret it. Perfect for college freshmen. Aspiring #QuantumNative engineers could do far worse than making this the first real CS book they buy.

Mathematics (Both Pure and Engineering)

I have opinions on the topics, but fewer on the choice of books. Feel free to improvise here.
  • Margalit, Rabinoff, Interactive Linear Algebra: as it happens, this will not only teach you piles and piles of important math, it will also show you what a textbook can be in the modern era.
  • ...some calculus book or another: differentiation, integration, ordinary differential equations, introductory partial differential equations. I learned all this, and linear algebra, from Tommy volumes 1 and 2, which have a unique pedagogical approach. I recommend Tommy, but with no real experience with other books I can't much compare.
  • ...some probability book or another: both discrete and continuous.
  • ...some statistics.
  • Jungnickel, Graphs, Networks and Algorithms: Why isn't graph theory core to more engineering programs?!? It's usually relegated to graduate school. As computer engineers, we learn about spanning trees, shortest path and directed acyclic graphs (as in compiler optimization), but there is so much more...Diestel is the classic but is heavy going, definitely a graduate-level text. This book is a good compromise, but feel free to substitute Diestel or something else.
  • Oppenheim, Willsky, Hamid, Signals and Systems: you gotta know Fourier transforms and other transforms. Gotta. As in, must, required, not optional.  Fourier is fundamental, but quadrature modulation (used in the not-quite-extinct NTSC) was maybe the most interesting thing I learned, simply because I found it so counterintuitive that it worked at all. I learned from the first edition of this book. This book appears to be considered a classic, but again feel free to substitute.
  • Kleinrock, Queueing Systems: Volume 1, Theory: this will change the way you think about computer systems, networks, and even going to the bank. Depending on the university, often taught to graduate students in electrical engineering.
  • Cover and Thomas, Elements of Information Theory: information theory is its own distinct field -- not just math, not electrical engineering, certainly not pure computer science -- but I have reluctantly categorized it here. This is the classic text for classical information theory, though the basics are actually covered quite well in Wilde's quantum book, so perhaps you don't need both.

Computer Science

I'm including algorithms and machine learning here. Notice that there isn't really a pure theory book here focusing on complexity theory, but we have Fortnow above and Aaronson below.
  • Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms: this book will repay every moment you put into it.  It's more than just algorithms, it includes a lot on data structures and of course assesses the complexity of algorithms and structures, as well.
  • Guenin, Könemann, Tunçel, A Gentle Introduction to Optimization: a very mathematically-oriented introduction, I have used this book in my class.  I think it's a good intro to linear programming and the seminal simplex algorithm, for matrix-oriented optimization. I didn't find the math-oriented approach to be as enlightening for graph problems; I didn't even recognize Dijkstra's shortest path first algorithm for what it was in the unfamiliar notation. Overall, I think the book lives up to its name. If you want to substitute Papadimitriou and Steiglitz's Combinatorial Optimization: Algorithms and Complexity here though, I think you have made an excellent choice.
  • Russell and Norvig, Artificial Intelligence: A Modern Approach: a must-have for a complete bookshelf, this covers everything up to the machine learning revolution below, focusing on GOFAI and symbolic and algorithmic techniques. I learned the A* algorithm from this, for example.
  • Goodfellow, Bengio, Courville, Deep Learning: a just-right book, in the right place at the right time with the right depth, written just long enough after the revolution of 2012 to digest its importance, and soon enough to be timely. With the above, a great pair.
  • Petzold, The Annotated Turing: I have several books on Turing, and several other books on the history of computation, but I am by no means an expert on the topic. Out of my modest collection, though, I would tap this one. There is so much more in it than just Turing's seminal paper, but it stops to explore every nuance. It really changed the way I view Turing machines.
  • Knuth, TAOCP: do not buy these books until you have decided to dedicate your life to computation. But once you have made that decision, and once you think you understand algorithms, buy these unhesitatingly and spend as many hours with them as you can. In the problems sections alone you can find topics for an army of Ph.D.s. These books, perhaps more than any others on the list, will cause your hair to stand on end when you finally grasp a topic.
  • Numerical Recipes: I believe, if you're going to create quantum computers that surpass classical ones, you need to have something of an organized understanding of how classical computers do numerical computation. Of course you'll find some of this in Knuth v. 2, and in any good book on algorithms, but the focus there is generally on higher-level data structures and algorithmic approaches, rather than the details of the computation itself. It used to be that software engineers had to write a lot of math code themselves, but these days good libraries for linear algebra, statistics, transforms, and numerical methods for differential equations are available. This is good for programmer productivity, software portability, and even performance, given that not everyone wants to speed months tuning code.  But it's bad for learning about the underlying machine and methods, which I think are important for engineers to know. These days, also, a lot of purely numeric code can run well on GPUs, which is a whole other matter involving a lot of learning about data parallelism. So, the book Numerical Recipes is likely outdated, but I haven't yet found a substitute.
    Asking about this caused quite a conversation on Twitter, where the general recommendations were "function libraries" and "ask on Stack Exchange", both of which are great but don't build organized understanding. People also hastened to point out that the software libraries themselves that accompany the book are licensed commercial software, and the free libraries and language features have made them less valuable. Moreover, some people don't trust the material, and recommend Netlib or any of half a dozen other implementations instead, but what I'm after here is an understanding of how to implement numerics.  I'd say this is optional.
  • Foley, van Dam, Feiner, Hughes, Computer Graphics: all right, this is really optional, but you'll learn a lot about how math and computing go together in the real world, and how data reaches humans as information is an important topic.

Computer Engineering

What's missing here is a good book on the modern state of VLSI, including its limitations. There is some material on semiconductor physics in Gershenfeld, below, though. I have, reluctantly, left databases and web/information systems off this list; we have to draw the line somewhere. A complete understanding will extend to parallel programming and to distributed systems, as well.
  • Hennessy & Patterson, Computer Architecture: A Quantitative Approach: I have had multiple copies of the classic as it has evolved over the last thirty years (one signed!). This is nominally a graduate-level text, and it's very tempting to put in the more basic Hardware-Software Interface as a nice introduction to how computers actually perform their calculations, but the important ideas are presented so much more powerfully here.
  • Arpaci-Dusseau and Arpaci-Dusseau, Operating Systems: Three Easy Pieces: a very nice overview of key principles in an operating system, organized around virtualization (of CPU, memory, devices, even whole machines), concurrency, and persistence. I used to use Tanenbaum's Modern Operating Systems, but I'm afraid it's now too old, out of step with current practice. Sometimes the structure and humor in OSTEP both feel a little forced, and I would do things a little bit differently if I were writing, but overall I think this is the best introductory book on operating systems out there.
  • McKusick, Neville-Neil, and Watson, The Design and Implementation of the FreeBSD Operating System: building on decades of its predecessors (I'm especially fond of the shorter and admirably lucid but now outdated, book on 4.3BSD), this is the single best explanation of the structure of a OS known to humankind. Read this book!
  • Aho, Sethi, Lam and Ullman's Dragon Book (well okay, that's not the formal name): Most people would place a compilers book under CS, even under theory, but I view programming languages and compilers as one of the three pillars of computer systems, alongside OS and architecture -- a legacy, I suppose, of having first been introduced to leading-edge computer systems research by reading an ASPLOS proceedings. You simply must learn about lexical analyzers and parsers and their relationship to finite automata and pushdown automata, as well as code generation and optimization. Yes, yes, there's a strong connection to theory here -- that's the point.
  • Kurose, Ross, Computer Networking: a Top-Down Approach: obviously -- obviously -- you need a book on networking, ideally one that focuses on the Internet and its protocol suite, but that understands telephone networks, both fixed and mobile. Kurose seems to be the introductory textbook of choice these days, but I'm okay if you have a different choice.
  • Stevens (and Fall, on the recent edition), The Illustrated TCP/IP (vol. 1 and 2): you also need to understand the joys and pains of creating implementations of the Internet protocols. This might feel secondary if you're working in quantum computing, rather than networking, but it's ultimately part of understanding computer systems. This book influenced many people. After Stevens died, I was at a conference where his wife picked up a lifetime achievement award in his honor, and there was a standing ovation and people were crying.
  • Jain, The Art of Computer Systems Performance Analysis: another broad-ranging must-have.

Software Engineering

Michał Stęchły pointed out that I didn't have SE on this list. What an oversight! More coming soon.

Physics

Physicists, both experimental and theoretical, will be shocked at how few books I list here. Of course, the more physics you know, the better your understanding of the devices will be, but in fact to become a quantum software engineer, surprisingly little true physics is required. In today's NISQ environment, I'll venture, a higher requirement for physics is required than will be the case in a decade or so -- just as many great software engineers have a basic grasp of computer architecture but almost no grasp of the underlying semiconductor physics in computer chips.
Quantum physicists will recoil in horror at diving straight into quantum computing without learning about momentum and forces and energy, but I think you can actually defer much of that learning until later. I do think learning about damped harmonic oscillators is valuable, and that does require some of those other topics, though. Also, make a pit stop for Boltzmann and a little bit of thermodynamics and statistical mechanics when you start getting into decoherence, but don't get bogged down there -- those topics alone can be a career. Electricity and magnetism nearly killed my interest in physics; I really struggled with Maxwell's equations in large part because I didn't understand partial differential equations yet. So, if you find yourself losing momentum(!) here, shift to a different approach and come back for the physics later. You'll be surprised how much of it seems easy, or even obvious, after a little perspective.
  • Feynman Lectures on Physics: available in a nice, online form, at least in English. (The paper edition has been translated into numerous languages, including Japanese and Russian.) Somewhat dated -- who does physics in feet, even in the 1960s? -- and perhaps the closest to "trophy" books of anything on this list, but the explanations of concepts are still as crystal clear as the day Feynman gave them.  Most of the topics above can be studied straight out of this set.
  • Crawford, Waves: Volume 3 in the Berkeley series, this is the one I learned from. Waves in 1, 2, 3 dimensions, standing waves, diffraction, propagation, all this just sits in the back of your brain once you've learned it and influences how you understand other ideas -- especially optics and quantum mechanics.
  • Hecht, Optics: I learned from an earlier edition of this, and use the current edition in my own group. For our stated purpose of making #QuantumNatives, perhaps the single most important physics topic and book; understanding interference patterns and waves in general is critical. I think you can do this without the Waves book above, but put them together and you have a powerful understanding.
  • French, Taylor, An Introduction to Quantum Mechanics: eventually, yes, you'll want to learn this: how spectra work, energy levels, atomic structure, bonding, wells and tunneling, etc. There are lots and lots of books on the topic. I learned from this one, but you can easily substitute here.
  • Saleh, Teich, Fundamentals of Photonics: I hesitate to even put this on the list; I have a copy but refer to it only very rarely, compared to the other books here. Most of what beginning engineers need to know is covered more than adequately in Hecht, but coupled with Hecht for fundamentals and the more abstract Gerry & Knight, the three books feel like a good set. I'd call this a low-priority acquisition and read, unless you're doing experimental work.
  • Gerry, Knight, Introductory Quantum Optics: I'm probably betraying my current preoccupation with quantum networks here, but I think this is a good topic that will aid in an understanding of quantum hardware more broadly, and this topic is surprisingly not covered in any depth at all in Mike & Ike. Perhaps optional, but I've found this valuable. In fact, though, I acquired it fairly early in my quantum career, and I initially found it rather opaque. As my skills have grown, though, I have referred to it more and more often.
  • Gershenfeld, The Physics of Information Technology: one of my favorite books. Not flawless, but where else will you learn about optical fiber, magnetic disk read/write heads, and semiconductor physics in one place? (Man, I'm citing a lot of books from MIT in this list!)

Cryptography and Security

Note that the security book probably belongs up under Computer Engineering rather than here, but I put it here anyway. If cryptography weren't such a juicy, well-funded topic for quantum computing, I might not have a separate section here, but in the context of growing #QuantumNatives, it's essential.
  • Bishop's Computer Security: Art and Science: security is a topic that far too many of us learn in an ad hoc fashion. This 1,400-page tome should help you realize that it's an important and rigorous field, and not something to be trifled with. Most universities will have at least one course on the topic, take it! Oh, and this book dedicates only about 10% of its length to cryptography itself, another indication of how broad and rich the concept of security is.
  • Schneier, Applied Cryptography: is there a better book than this out there?  It's now quite, um, mature, but it's so lucid, it's a classic. It also goes into more cryptographic corners than Bishop, including things like zero-knowledge proofs, and so might be a better fit for quantum folks than Bishop...if only there were a 3rd edition. The second edition is new enough to have a few paragraphs speculating about quantum computing, but old enough to just predate AES.
  • Menezes, van Oorschot, Vanstone, Handbook of Applied Cryptography: this one is definitely optional, I hesitated to even include it here. But if you want to go further into the field, there's a lot here that's hard to find anywhere else in such a comprehensive, organized fashion. Again, though, 20 years old.
  • Singh, The Code Book: a readable history of secrets, and more up to date than Kahn.
  • Kahn, The Codebreakers: 1,200 pages of goodness, if a bit of homophobia thrown in, which certainly occurred in the statecraft of spying through the years. Originally published in 1967, before public-key cryptography and the disclosure of Ultra; updated but not very effectively some years later. (See my review.)

Ethics and Society

I believe this is critical to the development of responsible, mature engineers, but I don't have a book for the reading list. Recommendations?

Quantum Computing and Information

Finally, we come to the core topic itself, if you're aiming to be a #QuantumNative engineer. We've already seen Dancing with Qubits and Ultimate Zero and One above, so here we go deeper. There's actually quite a bit of overlap among these, but you'll find the varying perspectives useful. It would be nice to have a good one on hardware, and an up-to-date one on algorithms. Both topics are moving too fast, though.
  • rdv & satoh, Understanding Quantum Computers: not a book...yet. Broad-ranging and very introductory, this covers about twice the material of a popsci book, covering key ideas as well as some aspects of the business and some chats with important researchers. After working through this course, you'll be ready to tackle Mike & Ike.
  • Rieffel and Polak, Quantum Computing: A Gentle Introduction: until the advent of Dancing, this was the book I recommended for a first serious book on QC. It's still good. More on algorithms, less on background math and nothing on implementations and decoherence.
  • Nielsen & Chuang (or, Mike & Ike), Quantum Computation and Quantum Information: this is the book you must have on your bookshelf. Yes, it's now 20 years old, but it still hasn't been surpassed in comprehensiveness. (Perhaps it's impossible to have one single book on the topic now, like having one book titled "Computer Science".)
  • Kitaev, Shen and Vyalyi, Classical and Quantum Computation: A short and rigorous but remarkably clear book, I found this an excellent complement to Mike & Ike. It cleared up a lot of things I found opaque in Mike & Ike.
  • Preskill's Lecture Notes for Ph/CS 219: Preskill has a solid claim on being the best explainer in the quantum business. His chapters date back as far as 1996, and as recently as 2018. The explanation of entanglement is straightforward, provided you understand the notation. These chapters are free, as well as incredible content, and so are a great place to start before you begin stocking your shelves with expensive books.
  • Wilde, Quantum Information Theory: covers the theory of information -- given a certain amount of noise, how much information can a channel carry? The book covers classical channels (Shannon theory) well, before moving into quantum.
  • Asfaw et al., The Qiskit Book: A rapidly-evolving introduction to quantum computing using IBM's quantum computers and the Qiskit Python toolkit. Couple this with the other books here, and your gut-level feel for how quantum computers work, and how to design algorithms for them, will grow rapidly.
  • Aaronson, Quantum Computing Since Democritus: about a third of this is non-quantum computational complexity, so it will serve as our pure theory book. Very few equations, and some of Scott's quirky humor, but make no mistake, this is a serious, rigorous book.
  • rdv, Quantum Networking: hey, you got a better suggestion?
  • Lidar & Brun, eds., Quantum Error Correction: this being a collection of chapters from different authors, (the only such book on this list), and now also mature, it would be nice to have a more cohesive and up-to-date book, but I don't know of one. Lidar & Brun's introduction on decoherence in quantum systems is probably the best summary of the topic I know of, which is what tips the balance here instead of just recommending a research paper, regardless of how good it is.

The Freshman Short List

Okay, okay, all that's way too much. Where should I start? With a sigh and a heavy heart (I hate shortening lists), here is one book each to start with from the largest of the above categories (plus one more).
Note that I only included one math book. You can get surprisingly far into quantum computing with nothing more than complex numbers, summations, matrix multiplication, tensor products, and the rudiments of probability. Sutor has not a single integral in the book. But to move more deeply into quantum mechanics, as well as into Gershenfeld and into the nonlinear optimization of deep learning, you will need not only differentiation and integration, but also the basics of partial differential equations. You shouldn't let math intimidate you out of working in this field, but at the same time, you should never stop trying to learn more math.
Of this list, Hennessy & Patterson, Gershenfeld, and Mike & Ike are probably most commonly used as graduate-level texts. Certainly, you should be prepared before tackling each of them, but ambition will be rewarded with an accelerated arrival at the ability to discuss these topics at the highest plane, with professional engineers and researchers.
So, the Freshman Short List:
  • Sutor (488 pages)
  • Margalit & Rabinoff (??? pages)
  • Cormen & co. (1,320 pages)
  • Hennessy & Patterson (936 pages)
  • Hecht (720 pages)
  • Gershenfeld (388 pages)
  • Bishop (1,440 pages)
  • Mike & Ike (702 pages)
That's 5,994 pages of paper, plus the equivalent of several hundred more in interactive web pages. If you're already a budding programmer, a dedicated 10 pages/day will get you through those by the time you're a junior (10 pages might be 20 minutes or several hours, depending on the content, how much background work you have to do to understand the topic, and whether you diligently do enough of the homework problems). That would make an excellent goal.  If you're not much of a programmer yet, you'll move slowly through Cormen; learning how to extend from a few lines of code to understanding the abstractions in algorithms takes time and patience. (I think that's one of the biggest intellectual hurdles I have ever had to guide students through, and needs much more attention in CS/CE/SE education, but that's another post entirely.) There's no harm in taking your time, keep up slow and steady progress. And don't hesitate to ask questions.

Good luck -- and come join my group!

Revision History

  • 2020/5/26: First published.
  • 5/27: Placeholder for SE added.

2 comments:

Anonymous said...

I found this book:
Understanding Cryptography
A Textbook for Students and Practitioners
http://www.crypto-textbook.com/
is good crypto book for undergrad student.

rdv said...

Thanks, I'll check it out -- not one I'm familiar with.