Introduction to Quantum Algorithms via Linear Algebra, second edition
Quantum computing explained in terms of elementary linear algebra, emphasizing computation and algorithms and 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.
1137329390
Introduction to Quantum Algorithms via Linear Algebra, second edition
Quantum computing explained in terms of elementary linear algebra, emphasizing computation and algorithms and 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.
45.0 Out Of Stock
Introduction to Quantum Algorithms via Linear Algebra, second edition

Introduction to Quantum Algorithms via Linear Algebra, second edition

Introduction to Quantum Algorithms via Linear Algebra, second edition

Introduction to Quantum Algorithms via Linear Algebra, second edition

Hardcover

$45.00 
  • SHIP THIS ITEM
    Temporarily Out of Stock Online
  • PICK UP IN STORE

    Your local store may have stock of this item.

Related collections and offers


Overview

Quantum computing explained in terms of elementary linear algebra, emphasizing computation and algorithms and 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.

Product Details

ISBN-13: 9780262045254
Publisher: MIT Press
Publication date: 04/06/2021
Pages: 280
Product dimensions: 6.10(w) x 9.10(h) x 0.90(d)

About the Author

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

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

Table of Contents

Preface to the First Edition xiii

Preface to the Second Edition xv

Acknowledgments xvii

I Essential Algorithms 1

1 Introduction 3

1.1 The Model 4

1.2 The Space and the States 5

1.3 The Operations 6

1.4 Where Is the Input? 8

1.5 What Exactly Is the Output? 8

1.6 Summary and Notes 9

2 Numbers and Strings 11

2.1 Asymptotic Notation 13

2.2 Problems 15

2.3 Selected Answers 16

2.4 Summary and Notes 16

3 Basic Linear Algebra 17

3.1 Hilbert Spaces 18

3.2 Products of Spaces and Tensor Products 19

3.3 Matrices 20

3.4 Complex Spaces and inner Products 22

3.5 Tensor Products of Matrices 22

3.6 Matrices, Graphs, and Sums over Paths 23

3.7 Problems 26

3.8 Selected Answers 29

3.9 Summary and Notes 30

4 Boolean Functions, Quantum Bits, and Feasibility 31

4.1 Feasible Boolean Functions 32

4.2 An Example 34

4.3 Quantum Representation of Boolean Arguments 37

4.4 Quantum Feasibility 39

4.5 Examples of Quantum Circuits 41

4.6 Problems 44

4.7 Selected Answers 46

4.8 Summary and Notes 46

5 Special Matrices 49

5.1 Hadamard Matrices 49

5.2 Fourier Matrices 50

5.3 Reversible Computation and Permutation Matrices 51

5.4 Feasible Diagonal Matrices 52

5.5 Reflections 52

5.6 Problems 54

5.7 Selected Answers 57

5.8 Summary and Notes 59

6 Tricks 61

6.1 Start Vectors 61

6.2 Controlling and Copying Base States 62

6.3 The Copy-Uncompute Trick 64

6.4 Superposition Tricks 65

6.5 Flipping a Switch 66

6.6 Measurement Tricks 68

6.7 Partial Transforms 69

6.8 Problems 69

6.9 Selected Answers 71

6.10 Summary and Notes 72

7 Phil's Algorithm 73

7.1 The Algorithm 73

7.2 The Analysis 73

7.3 An Example 74

7.4 A Two-Qubit Example 74

7.5 Phil Measures Up 76

7.6 Quantum Mazes Versus Circuits Versus Matrices 80

7.7 Problems 81

7.8 Selected Answers 84

7.9 Summary and Notes 85

8 Deutsch's Algorithm 87

8.1 The Algorithm 87

8.2 The Analysis 88

8.3 Superdense Coding and Teleportation 91

8.4 Problems 96

8.5 Summary and Notes 97

9 The Deutsch-Jozsa Algorithm 99

9.1 The Algorithm 99

9.2 The Analysis 100

9.3 Problems 101

9.4 Summary and Notes 102

10 Simon's Algorithm 103

10.1 The Algorithm 103

10.2 The Analysis 104

10.3 Problems 105

10.4 Summary and Notes 106

11 Shor's Algorithm 107

11.1 Strategy 107

11.2 Good Numbers 108

11.3 The Quantum Part of the Algorithm 109

11.4 Analysis of the Quantum Part 110

11.5 Probability of a Good Number 112

11.6 Using a Good Number 114

11.7 Continued Fractions 115

11.8 Problems 116

11.9 Summary and Notes 117

12 Factoring Integers 119

12.1 Some Basic Number Theory 119

12.2 Periods Give the Order 120

12.3 Factoring 120

12.4 Problems 122

12.5 Summary and Notes 122

13 Grover's Algorithm 123

13.1 The Algorithm 125

13.2 The Analysis 125

13.3 The General Case, with k Unknown 126

13.4 Problems 127

13.5 Summary and Notes 128

II Advanced Algorithms 129

14 Physics of Quantum Computing 131

14.1 Coherence and Cards 131

14.2 Dirac Notation 133

14.3 What Are Qubits? 135

14.4 Transformations and the Bloch Sphere 141

14.5 Measurements of Pure States 145

14.6 Mixed States and Decoherence 148

14.6.1 Trace and POVM 150

14.6.2 Partial Traces 151

14.6.3 Depolarizing and Dephasing 153

14.7 The CHSH Game 155

14.7.1 Classical Case 156

14.7.2 Quantum Case 156

14.7.3 Quantum Case Redux 159

14.8 Quantum Supremacy 161

14.9 Problems 164

14.10 Summary and Notes 166

15 Phase Estimation and Approximate Counting 169

15.1 Grover Approximate Counting 170

15.2 The Algorithm 172

15.3 The Analysis 172

15.4 Problems 176

15.5 Summary and Notes 176

16 Quantum Walks 177

16.1 Classical Random Walks 177

16.2 Random Walks and Matrices 178

16.3 An Encoding Nicety 180

16.4 Defining Quantum Walks 181

16.5 Interference and Diffusion 182

16.6 The Big Factor 185

16.7 Problems 187

16.8 Summary and Notes 187

17 Quantum Walk Search Algorithms 189

17.1 Search in Big Graphs 189

17.2 General Quantum Walk for Graph Search 191

17.3 Specifying the Generic Walk 193

17.4 Adding the Data 194

17.5 Tool Kit Theorem for Quantum Walk Search 195

17.5.1 The Generic Algorithm 197

17.5.2 The Generic Analysis 197

17.6 Grover Search as Generic Walk 198

17.7 Element Distinctness 199

17.8 Subgraph Triangle Incidence 200

17.9 Finding a Triangle 200

17.10 Evaluating Formulas and Playing Chess 201

17.11 Problems 203

17.12 Summary and Notes 203

18 Quantum Matrix Algorithms 205

18.1 Hermitian Matrices and Nature's Algorithm 206

18.2 The HHL Algorithm 210

18.3 Error Analysis 214

18.4 Improvements 220

18.5 Problems 222

18.6 Summary and Notes 222

19 Quantum Computation and BQP 225

19.1 The Class BQP 225

19.2 Equations, Solutions, and Complexity 228

19.3 A Circuit-Labeling Algorithm 230

19.4 Sums over Paths and Polynomial Roots 232

19.5 The Additive Polynomial Simulation 234

19.6 Bounding BQP 235

19.7 Logical Description of Quantum Systems 236

19.8 Problems 239

19.9 Summary and Notes 241

20 Beyond 243

20.1 Reviewing the Algorithms 243

20.2 Some Further Topics 244

20.3 The "Quantum" in the Algorithms 246

References 249

Index 257

What People are Saying About This

From the Publisher

“This book covers the most important quantum algorithms from scratch, concisely but rigorously. It is well suited to those with some mathematics background but with scant knowledge of quantum computing.”
Stephen Fenner, Professor of Computer Science and Engineering, University of South Carolina.
 
“This lovely volume introduces quantum algorithms—from the early examples that launched the field of quantum computing to those underlying recent experiments—in an accessible and conversational style.”
Chris Umans, Professor of Computer Science in the Computing and Mathematical Sciences Department, California Institute of Technology

From the B&N Reads Blog

Customer Reviews