Skip to content

Quantum Algorithms Via Linear Algebra

December 6, 2014


Announcing publication of our textbook with MIT Press

OLYMPUS DIGITAL CAMERA
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.


LRQmitbookcover

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 {2^{64} - 1} 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 {2^{64} \sim 10^{19}} 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 {10^{19}} 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 {10^{19}} 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 {G} into a “doubled-up” graph {G'} 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 {\mathsf{BQP}} 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]

36 Comments leave one →
  1. December 6, 2014 5:13 am

    This looks so interesting! I am fighting the urge to just buy it immediately now, poor grad-student or not. I loved the posts about this subject two years ago, and I’ve kept them in mind ever since. I believe a whole textbook about this subject seems like something that could plant the seeds of a revolution.

  2. December 6, 2014 8:22 am

    Open Problems  “Can you explain this quantum principle [of page-number quantization]?”

    A simple explanation of page-quantization is that offset-presses don’t print books as individual pages, but rather as signatures that are folded-and-cut into pages.

    Particularly when some signatures are printed (expensively) incolor, while other signatures are printed (cheaply) in black, the resulting quantization patters can be rich indeed!

    More richly, we can appreciate page-quantization as a metaphor for dynamical-quantization.

    Ideality  The creed of the Church of the Larger Hilbert Space regards basis-vectors as the independent “pages” of the Book of Nature. This independent-page description is adequate for most purposes, and is particularly congenial to students and to theorem-provers.

    Reality  For reasons of efficiency, Gaia’s Press prints the Book of Nature not on exponentially many separate pages, but upon polynomially many algebraic signatures. The associated signature-bundle description of the Book of Nature is particularly congenial to algebraic geometers and to simulationists.

    Synthesis  The independent basis-pages of the Church’s creed arise as a simplifying illusion that Gaia’s Press induces by the fold-and-cut process that is commonly called “experimental measurement”.

    Readings  The lecture “Accelerating Drug-Discovery: The Accurate Prediction of Potency” (available on YouTube), by Mark Murcko (who is the senior vice president of strategy at the quantum-simulation company Schrödinger), is a terrific introduction to burgeoning power of real-world quantum-signature dynamics.

    Summary  It is well for quantum-dynamics students to respect *both* the elegant creed of the Church and the burgeoning power of the Press.

    Dick and Ken’s Quantum Algorithms Via Linear Algebra is a terrific introduction to the beauty of the Church … we can hope that Dick and Ken will someday gift students with a comparably lucid introduction to the power of the Press!


    @inproceedings{Murcko:2014aa, Author =
    {Mark Murcko}, Booktitle = {Advances in
    Drug Discovery and Development},
    Date-Added = {2014-11-23 04:18:41 +0000},
    Date-Modified = {2014-11-23 04:18:41
    +0000}, Month = {24 September}, Year = {2014}}

    Accelerating Drug Discovery: The Accurate
    Prediction of Potency

  3. E.L. Wisty permalink
    December 6, 2014 8:48 am

    Reblogged this on Pink Iguana.

  4. aram permalink
    December 6, 2014 9:24 am

    congratulations!

  5. Jake permalink
    December 6, 2014 9:52 am

    You had me at:
    “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.”

    • December 9, 2014 10:02 pm

      but… the Dirac notation is just row and column vectors🙂 this is a . The idea is just to help keep track of when we have really taken an inner product , and also when we have an outer product like {|u\rangle\langle v|.} I find this much easier than using the superscript {{}^T} (or {{}^\dagger)} and trying to remember whether things are rows or columns!

      • December 9, 2014 10:04 pm

        oops, funny markup language. This is a \langle row |, and this is a | column \rangle. An inner product is \langle u | v \rangle, and an outer product is | u \rangle \langle v |.

      • December 10, 2014 8:56 am

        Use $-latex … $ without the hyphen. E.g. \langle u | v \rangle

  6. December 6, 2014 2:05 pm

    nice nice probably the best readable book on quantum algorithms available.

  7. Jim permalink
    December 6, 2014 3:35 pm

    Why don’t any quantum algorithms texts cover algorithms for simulating physics? That seems like the most practically useful application of QCs we know.

    • December 6, 2014 7:59 pm

      We pay “lip service” to that in chapter 7—since “Phillips” was Feynman’s middle name, ultimately we say “Phil’s Algorithm” refers to simulating nature. It did not seem thematic to go into further physics details now; that and something else might pick up on things mentioned briefly in chapter 17 for a later edition. (–Ken)

  8. arnab permalink
    December 6, 2014 3:56 pm

    Congratulations!

  9. Jim permalink
    December 6, 2014 5:30 pm

    The book is out of stock on Amazon. Do you know any other retailer that carries it other than MIT press?

  10. December 7, 2014 12:38 am

    Knowing nothing about QC but a lot of linear algebra, I’ve read the previous two posts. it seems like a very interesting approach, but there’s one very important aspect i don’t understand: what determines the set of “allowed” unitary computations?

    Obviously there’s always a unitary matrix that will take us directly from an initial state to the desired state – why can’t we just apply it? Why can we use the matrix diag(1_R) in Grover’s algorithm? Doesnt it assume knowing R, which is what we’re looking for in the first place?

    • December 7, 2014 11:25 pm

      We address the allowed unitaries in chapters 4 and 5, while the treatment of gates in the exercises of chapters 3–7 builds a concrete characterization, which is finally included in a theorem statement in chapter 16. The detail about the feasibility of the Grover matrix is the most particular “shortcut” referred to in the post’s intro (4th paragraph). We added sections to chapters 5 and 6, the latter with a reversible “How many … light bulb?” metaphor, in order to fully justify it. We introduce the term “functional superposition” for states of the form {\sum_x |x\rangle|f(x)\rangle} (this is one of our examples of Dirac notation), and in fact there seem to be some interesting not-yet-fully-treated theoretical questions about them.

  11. Adam permalink
    December 7, 2014 3:15 am

    Congrats ! Great News! I really like your style of exposition. I would be very happy to get your perspective on topics like algebraic and combinatorial methods in circuit complexity in the form of a book.

  12. December 7, 2014 7:33 am

    beyond Boolean logic networks as often included in a discrete mathematics course .. respect .. although I hate mathematical calculations and related stuff !

  13. December 7, 2014 3:34 pm

    Out of stock on Amazon. Hope the press is cranking more before Christmas!

  14. AdC(Alexandre de Castro) permalink
    December 8, 2014 12:10 pm

    interesting title, but what is the difference between linear algebra and quantum mechanics?

  15. Adc(Alexandre de Castro permalink
    December 8, 2014 12:22 pm

    interesting title, but what is the difference between linear algebra and quantum mechanics?

    • December 9, 2014 2:18 pm

      ADC, Since this blog post is partly an homage to Feynman, and since Richard Lipton loves a good quote, I can’t resist quoting Feynman’s answer to almost the same question:

      “Math (Linear Algebra) is to Physics (Quantum Mechanics) what masturbation is to sex.”

      • AdC permalink
        December 9, 2014 9:10 pm

        Hi rrtucci,

        Do you believe in fault-tolerant quantum computing? If so, QM = sex and LA = masturbation.

        I do not believe that quantum computing is feasible in a noisy (physical) system. For me, QM=LA

  16. asdf permalink
    December 12, 2014 5:07 am

    Which begs for the obvious question about your gut feeling. Do you believe QC is even remotely possible? And would answering this question affect book sales? :0)

  17. March 12, 2015 9:58 am

    Reblogged this on All about Nils.

  18. November 8, 2015 11:56 am

    On page 103, should it really be 0.4*r*r? 0.4/(r*r) makes more sense for me.

    I was unable to figure out how to create the functional superposition of a non-invertible function – as suggested in the description of Simon’s and Shor’s algorithm. See http://cs.stackexchange.com/questions/43805/how-is-quantum-function-fx-ax-mod-n-constructed-in-shors-algorithm/49198

    • November 20, 2015 3:54 am

      I found a solution for the functional superposition using ancillary qubits and edited my response on stackexchange accordingly.

      What about my problem with page 103? Am I missing something or is there a mistake?

Trackbacks

  1. A Quantum Two-Finger Exercise | Gödel's Lost Letter and P=NP
  2. A Polynomial Growth Puzzle | Gödel's Lost Letter and P=NP

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s