Introduction to Quantum Algorithms via Linear Algebra

by Lipton, Regan

ISBN: 9780262363167 | Copyright 2021

Click here to preview

Instructor Requests

Digital Exam/Desk Copy Print Desk Copy Ancillaries
Tabs

The second edition of a textbook that explains quantum computing in terms of elementary linear algebra, requiring no background in physics.

This introduction to quantum algorithms is concise but comprehensive, covering many key algorithms. It is mathematically rigorous but requires minimal background and assumes no knowledge of quantum theory or quantum mechanics. The book explains quantum computation in terms of elementary linear algebra; it assumes the reader will have some familiarity with vectors, matrices, and their basic properties, but offers a review of the relevant material from linear algebra. By emphasizing computation and algorithms rather than physics, it makes quantum algorithms accessible to students and researchers in computer science who have not taken courses in quantum physics or delved into fine details of quantum effects, apparatus, circuits, or theory.

In this second edition, part I, on essential algorithms, provides additional exercises and solved problems. Part II, on advanced algorithms, offers two new chapters: one provides students with a deeper understanding of quantum physics, and includes a discussion of recent experiments claiming “quantum supremacy”; the other new chapter focuses on the Harrow-Hassidim-Lloyd (HHL) algorithm for linear algebra. Additional material touches on some of the philosophical issues involved in quantum mechanics, addressing the divide between quantum and classical. This edition is more versatile than the first edition (published as Quantum Algorithms via Linear Algebra: A Primer), with part I suitable for advanced undergraduates and part II, now including notation and tools used by practitioners, suitable for graduate students.

Expand/Collapse All
Contents (pg. vii)
Preface to the First Edition (pg. xiii)
Preface to the Second Edition (pg. xv)
Acknowledgments (pg. xvii)
I. ESSENTIAL ALGORITHMS (pg. 1)
1. Introduction (pg. 3)
1.1 The Model (pg. 4)
1.2 The Space and the States (pg. 5)
1.3 The Operations (pg. 6)
1.4 Where Is the Input? (pg. 8)
1.5 What Exactly Is the Output? (pg. 8)
1.6 Summary and Notes (pg. 9)
2. Numbers and Strings (pg. 11)
2.1 Asymptotic Notation (pg. 13)
2.2 Problems (pg. 15)
2.3 Selected Answers (pg. 16)
2.4 Summary and Notes (pg. 16)
3. Basic Linear Algebra (pg. 17)
3.1 Hilbert Spaces (pg. 18)
3.2 Products of Spaces and Tensor Products (pg. 19)
3.3 Matrices (pg. 20)
3.4 Complex Spaces and Inner Products (pg. 22)
3.5 Tensor Products of Matrices (pg. 22)
3.6 Matrices, Graphs, and Sums over Paths (pg. 23)
3.7 Problems (pg. 26)
3.8 Selected Answers (pg. 29)
3.9 Summary and Notes (pg. 30)
4. Boolean Functions, Quantum Bits, and Feasibility (pg. 31)
4.1 Feasible Boolean Functions (pg. 32)
4.2 An Example (pg. 34)
4.3 Quantum Representation of Boolean Arguments (pg. 37)
4.4 Quantum Feasibility (pg. 39)
4.5 Examples of Quantum Circuits (pg. 41)
4.6 Problems (pg. 44)
4.7 Selected Answers (pg. 46)
4.8 Summary and Notes (pg. 46)
5. Special Matrices (pg. 49)
5.1 Hadamard Matrices (pg. 49)
5.2 Fourier Matrices (pg. 50)
5.3 Reversible Computation and Permutation Matrices (pg. 51)
5.4 Feasible Diagonal Matrices (pg. 52)
5.5 Reflections (pg. 52)
5.6 Problems (pg. 54)
5.7 Selected Answers (pg. 57)
5.8 Summary and Notes (pg. 59)
6. Tricks (pg. 61)
6.1 Start Vectors (pg. 61)
6.2 Controlling and Copying Base States (pg. 62)
6.3 The Copy-Uncompute Trick (pg. 64)
6.4 Superposition Tricks (pg. 65)
6.5 Flipping a Switch (pg. 66)
6.6 Measurement Tricks (pg. 68)
6.7 Partial Transforms (pg. 69)
6.8 Problems (pg. 69)
6.9 Selected Answers (pg. 71)
6.10 Summary and Notes (pg. 72)
7. Phil’s Algorithm (pg. 73)
7.1 The Algorithm (pg. 73)
7.2 The Analysis (pg. 73)
7.3 An Example (pg. 74)
7.4 A Two-Qubit Example (pg. 74)
7.5 Phil Measures Up (pg. 76)
7.6 Quantum Mazes Versus Circuits Versus Matrices (pg. 80)
7.7 Problems (pg. 81)
7.8 Selected Answers (pg. 84)
7.9 Summary and Notes (pg. 85)
8. Deutsch’s Algorithm (pg. 87)
8.1 The Algorithm (pg. 87)
8.2 The Analysis (pg. 88)
8.3 Superdense Coding and Teleportation (pg. 91)
8.4 Problems (pg. 96)
8.5 Summary and Notes (pg. 97)
9. The Deutsch-Jozsa Algorithm (pg. 99)
9.1 The Algorithm (pg. 99)
9.2 The Analysis (pg. 100)
9.3 Problems (pg. 101)
9.4 Summary and Notes (pg. 102)
10. Simon’s Algorithm (pg. 103)
10.1 The Algorithm (pg. 103)
10.2 The Analysis (pg. 104)
10.3 Problems (pg. 105)
10.4 Summary and Notes (pg. 106)
11. Shor’s Algorithm (pg. 107)
11.1 Strategy (pg. 107)
11.2 Good Numbers (pg. 108)
11.3 The Quantum Part of the Algorithm (pg. 109)
11.4 Analysis of the Quantum Part (pg. 110)
11.5 Probability of a Good Number (pg. 112)
11.6 Using a Good Number (pg. 114)
11.7 Continued Fractions (pg. 115)
11.8 Problems (pg. 116)
11.9 Summary and Notes (pg. 117)
12. Factoring Integers (pg. 119)
12.1 Some Basic Number Theory (pg. 119)
12.2 Periods Give the Order (pg. 120)
12.3 Factoring (pg. 120)
12.4 Problems (pg. 122)
12.5 Summary and Notes (pg. 122)
13. Grover’s Algorithm (pg. 123)
13.1 The Algorithm (pg. 125)
13.2 The Analysis (pg. 125)
13.3 The General Case, with k Unknown (pg. 126)
13.4 Problems (pg. 127)
13.5 Summary and Notes (pg. 128)
II. ADVANCED ALGORITHMS (pg. 129)
14. Physics of Quantum Computing (pg. 131)
14.1 Coherence and Cards (pg. 131)
14.2 Dirac Notation (pg. 133)
14.3 What Are Qubits? (pg. 135)
14.4 Transformations and the Bloch Sphere (pg. 141)
14.5 Measurements of Pure States (pg. 145)
14.6 Mixed States and Decoherence (pg. 148)
14.7 The CHSH Game (pg. 155)
14.8 Quantum Supremacy (pg. 161)
14.9 Problems (pg. 164)
14.10 Summary and Notes (pg. 166)
15. Phase Estimation and Approximate Counting (pg. 169)
15.1 Grover Approximate Counting (pg. 170)
15.2 The Algorithm (pg. 172)
15.3 The Analysis (pg. 172)
15.4 Problems (pg. 176)
15.5 Summary and Notes (pg. 176)
16. Quantum Walks (pg. 177)
16.1 Classical Random Walks (pg. 177)
16.2 Random Walks and Matrices (pg. 178)
16.3 An Encoding Nicety (pg. 180)
16.4 Defining Quantum Walks (pg. 181)
16.5 Interference and Diffusion (pg. 182)
16.6 The Big Factor (pg. 185)
16.7 Problems (pg. 187)
16.8 Summary and Notes (pg. 187)
17. Quantum Walk Search Algorithms (pg. 189)
17.1 Search in Big Graphs (pg. 189)
17.2 General Quantum Walk for Graph Search (pg. 191)
17.3 Specifying the Generic Walk (pg. 193)
17.4 Adding the Data (pg. 194)
17.5 Tool Kit Theorem for Quantum Walk Search (pg. 195)
17.6 Grover Search as Generic Walk (pg. 198)
17.7 Element Distinctness (pg. 199)
17.8 Subgraph Triangle Incidence (pg. 200)
17.9 Finding a Triangle (pg. 200)
17.10 Evaluating Formulas and Playing Chess (pg. 201)
17.11 Problems (pg. 203)
17.12 Summary and Notes (pg. 203)
18. Quantum Matrix Algorithms (pg. 205)
18.1 Hermitian Matrices and Nature’s Algorithm (pg. 206)
18.2 The HHL Algorithm (pg. 210)
18.3 Error Analysis (pg. 214)
18.4 Improvements (pg. 220)
18.5 Problems (pg. 222)
18.6 Summary and Notes (pg. 222)
19. Quantum Computation and BQP (pg. 225)
19.1 The Class BQP (pg. 225)
19.2 Equations, Solutions, and Complexity (pg. 228)
19.3 A Circuit-Labeling Algorithm (pg. 230)
19.4 Sums over Paths and Polynomial Roots (pg. 232)
19.5 The Additive Polynomial Simulation (pg. 234)
19.6 Bounding BQP (pg. 235)
19.7 Logical Description of Quantum Systems (pg. 236)
19.8 Problems (pg. 239)
19.9 Summary and Notes (pg. 241)
20. Beyond (pg. 243)
20.1 Reviewing the Algorithms (pg. 243)
20.2 Some Further Topics (pg. 244)
20.3 The “Quantum” in the Algorithms (pg. 246)
References (pg. 249)
Index (pg. 257)

Richard J. Lipton

Richard J. Lipton is Frederick G. Story Professor of Computing (Emeritus) at Georgia Institute of Technology.

Kenneth W. Regan

Kenneth W. Regan is Associate Professor in the Department of Computer Science and Engineering at the University at Buffalo, State University of New York.

eTextbook
Go paperless today! Available online anytime, nothing to download or install.

Features

  • Bookmarking
  • Note taking
  • Highlighting