Quantum Algorithms Via Linear Algebra

Announcing publication of our textbook with MIT Press

By permission of Nataly Meerson, artist : source

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 1948 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, December 5 as Dick and I write, is the US publication day of our textbook with MIT Press, titled Quantum Algorithms Via Linear Algebra: A Primer. It is also available from Amazon. Both places offer it for less than two adult IMAX tickets to see “Interstellar.” Publication abroad is on 1/1/15.

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 by Dick 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 1985 paper, led me to include an expanded treatment of quantum gates, framed in the exercises of five 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:

1. Introduction — 1

2. Numbers and Strings — 9

3. Basic Linear Algebra — 15
   • 3.5 Matrices, Graphs, and Sums Over Paths — 20
4. Boolean Functions, Quantum Bits, and Feasibility — 27

5. Special Matrices — 41

6. Tricks — 51

7. Phil’s Algorithm — 63
   • 7.6 Quantum Mazes versus Circuits versus Matrices — 69
8. Deutsch’s Algorithm — 77
   • 8.3 Superdense Coding and Teleportation — 82
9. The Deutsch-Jozsa Algorithm — 89

10. Simon’s Algorithm — 93

11. Shor’s Algorithm — 97

12. Factoring Integers — 109

13. Grover’s Algorithm — 115
    • 13.4 The General Case, with k Unknown — 118

    • 13.5 Grover Approximate Counting — 119
14. Quantum Walks — 129

15. Quantum Walk Search Algorithms — 143

16. Quantum Computation and BQP — 159
    • 16.4 Sum-Over-Paths and Polynomial Roots — 165
17. Beyond — 175

• Bibliography — 183

• Index — 189

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 later advanced topics.

The last main chapter 16 is notable for what we didn’t do in the earlier chapters: talk about complexity classes and the theory of quantum circuits. No complexity class names appear before that chapter. 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 prescribed dependence on computer theory, beyond Boolean logic networks as often included in a discrete mathematics course.

Nor is any physics required—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 we 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 chess guide I know, it 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.

Notation and Nature

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 heavier, less-serifed fonts. 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 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 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 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 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 in turn as some kind of object whose form may be ineffable to us. It may be necessarily ineffable if factoring and some other quantum-feasible tasks 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 accordingly our book promotes the view from combinatorics. That is why we blend numbers and strings early on, why graphs come in chapter 3 (where they also help for reading circuits in the next chapter), 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 into a “doubled-up” graph and then phrase the interference analysis in terms of counting heads/tails sub-sequences in the coin-flips. Finally, Chapter 16 includes my quasi-original extension of the proof of upper bounds for 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

Our final submitted typescript included everything in new LaTeX macros commissioned by MIT Press, even the exact front-matter, and came to 206 pages (192 numbered). Yet the published version, with no other content besides the cover, has 208 pages. The reason is a law of quantization that limits one’s ability to “save trees” by improving page-breaks and line-breaks. Can you explain this quantum principle?

[fixed 1984->1948]