{\huge Quantum Algorithms Via Linear Algebra}
Announcing our textbook with MIT Press \vspace{.5in}
Richard Feynman had a knack for new ways of seeing. His Feynman diagrams not only enabled visualizing subatomic processes, they also rigorously encapsulated an alternative formalism that cross-validated the equations and procedures of quantum field theory. His 1984 path-integral formulation sprang out of work by Paul Dirac that re-interpreted a continuous Lagrangian operator as a matrix multiplication. Fast forward to his 1985 article ``Quantum Mechanical Computers'' (a followup to his 1981/82 keynote speech ``Simulating Physics With Computers'') and there are only matrices and circuit diagrams to be seen.
Today is the publication day of our textbook with MIT Press, Quantum Algorithms Via Linear Algebra: A Primer. It is also available from Amazon, both for less than two adult IMAX tickets to see Interstellar.
Quantum computing has captured the imagination of scientists and entrepreneurs from all walks of research and business. Whether any computers that operate in the quantum regime exist in the world today, however, remains a puzzle. Hence what has really been driving the surge are quantum algorithms, which by our expectant understanding of Nature promise to accomplish tasks beyond the feasibility of our abundant classical computers. The algorithms have stunning beauty yet can be taught with minimal prior involvement of either 'quantum' or 'computing' as they are made of matrices. Our text builds on elementary linear algebra and discrete mathematics to tell their story at an undergraduate level.
We first intended to make it a short story, growing out of a pair of posts four years ago. With a few shortcuts on arguing the feasibility of certain quantum states we could have dispensed with quantum circuits and held to a ``Brief'' format under 100 pages. Desire for completeness and the visual appeal of circuits led us to enlarge the fundamentals. Then we realized we could support some advanced topics, including what we believe is the first coverage in any general text of quantum walks and quantum walk search algorithms. Interaction with the quantum group at IBM Thomas Watson Labs, including Charles Bennett whose inspiration shows on the first page of Feynman's paper, led me to include an expanded treatment of quantum gates, framed in the exercises of four chapters to minimize interference with the main flow. We still kept it under 200 pages.
An Invitation to Quantum
Here is the table of contents, including page numbers and a few section titles:
Our idea of a 10-to-12-week undergraduate course runs up through section 13.4, possibly including chapter 14. A longer or advanced course or graduate seminar may include some of the advanced topics.
The last main chapter 16 is notable for what we haven't done before: talk about complexity classes and the analysis of quantum circuits. We limit ``machine'' models to an informal presence in chapter 4, and we describe ``polynomial time'' as meaning that whenever the problem size doubles, the time can increase by a constant factor c that might be greater than 2. Hence there is no dependence on an automata and formal languages course. Nor is there on physics courses---even the sum-over-paths idea is introduced by showing how matrix multiplication counts paths in graphs. Then it is visualized via ``maze diagrams'' introduced in chapter 7, whose title plays on how the subsequent algorithms are named after people and also plays on Feynman's middle name. (There are no Feynman diagrams.)
We are both chess fans and close chapter 15 with the result that quantum computers can speed up evaluating formulas and playing chess. My favorite childhood chess book was An Invitation to Chess: A Picture Guide to the Royal Game by Irving Chernev and Kenneth Harkness. It assumes nothing and begins with how the pieces move, but unlike any other book I know, progresses smoothly and with pictures up through some fairly advanced strategy. It ends with a chess endgame composition by Leonid Kubbel as an ode to beauty, which inspired me to compose endgames of my own. We hope that our book will provide the same smoothness and encouragement.
Nature and Notation
One thing important to us is that the book should look and feel like a linear algebra text. This entailed keeping to an ordinary column-vector (or transposed row vector) representation of quantum pure states, and avoiding the customary physics notation of Paul Dirac. We followed recent ISO/IEC standards of bold lowercase italic for vectors and bold uppercase italic for matrices, in a heavier, less-serifed font. We did include some examples of Dirac notation that especially show its advantages, so as not to obstruct its usage when desired.
We skirted famous philosophical issues of quantum mechanics, but instead tried to promote the issue of scale between natural processes and the notation. I knew Oxford physicist James Binney as a Fellow of Merton College in the 1980s, and I'm delighted to find a similar emphasis in his recent textbook with David Skinner used for undergraduate physics at Oxford. They begin their section 6.2 on ``Quantum computing'' with the famous old story of the creation of the game of chess, whose agreed royal reward was one grain of rice for the first square, two grains for the second square, four grains for the third square, and (unwittingly to the king) doubling to a mammoth total of $latex {2^{64} - 1}&fg=000000$ grains after the last square. They continue (their emphasis):
What is the relevance of this old story for quantum mechanics? ... By the time we have built a system from 64 two-state systems, our composite system will have $latex {2^{64} \sim 10^{19}}&fg=000000$ basis states. ...[It is] physically miniscule, [but] to calculate the dynamics of this miniscule system we would have to integrate the equations of motion of $latex {10^{19}}&fg=000000$ amplitudes! This is seriously bad news for physics.
The idea behind quantum computing is to turn this disappointment for physics into a boon for mathematics. We may not be able to solve $latex {10^{19}}&fg=000000$ equations of motion, but Nature can evolve the physical system, and appropriate measurements made on the system should enable us to discover what the results of our computations would have been if we had the time to carry them out. If this approach to computation can be made to work in practice, calculations will become possible that could never be completed on a conventional computer.
Our saving grace is that although the linear algebraic objects---that is, the vectors and matrices---are so huge as to make ``our computations'' with them unscalable, the linear algebraic formulas do scale when put in succinct functional form. The question is how and whether Nature has a way to treat those functions as some kind of object whose form may be ineffable to us---perhaps necessarily if factoring and some other quantum-feasible tasks do require exponential time in the classical regime. But how could Nature do it? Feynman famously advised:
Do not keep saying to yourself, if you can possibly avoid it, ``But how can it be like that?'' because you will get ``down the drain,'' into a blind alley from which nobody has yet escaped. Nobody knows how it can be like that.
We certainly have no idea. However, we have an idea of what might jar new ideas loose, and finally that is why our book promotes the view from combinatorics. That is why graphs come in chapter 3 (notwithstanding that they help with the classical and quantum circuits in the next chapter which are graphs), why we have a whole chapter on handy ``tricks,'' and why we include a chapter on the number theory used to make period-finding solve factoring though it has no quantum content. It is why we incorporate the ``coin space'' of a quantum walk on a graph $latex {G}&fg=000000$ into a ``doubled-up'' graph $latex {G'}&fg=000000$ and then phrase the interference analysis in terms of counting heads-tails subsequences in the coin-flips. Finally, Chapter 16 includes my quasi-original extension of the proof of upper bounds for $latex {\mathsf{BQP}}&fg=000000$ in this paper, whose authors expressly reference Feynman's sum-over-paths formulation, with lighter theorem statements and proofs than in my post and ``cookbook'' draft paper on this subject two years ago.
Open Problems
However it can be like that, how can we make the most of this beautiful area?