Introduction to Quantum Algorithms via Linear Algebra, second edition
Published on 6. April 2021
280 pages
978-0-262-36215-3 (ISBN)
Description
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.
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.
More details
Other editions
Additional editions
Richard J. Lipton | Kenneth W. Regan
Introduction to Quantum Algorithms via Linear Algebra
Book
04/2021
2nd Edition
MIT Press
€53.50
Shipment within 10-20 days
Persons
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.
Kenneth W. Regan is Associate Professor in the Department of Computer Science and Engineering at University at Buffalo, the State University of New York.
Content
- Intro
- Title Page
- Copyright
- Dedication
- Table of Contents
- Preface to the First Edition
- Preface to the Second Edition
- Acknowledgments
- I. Essential Algorithms
- 1. Introduction
- 1.1. The Model
- 1.2. The Space and the States
- 1.3. The Operations
- 1.4. Where Is the Input?
- 1.5. What Exactly Is the Output?
- 1.6. Summary and Notes
- 2. Numbers and Strings
- 2.1. Asymptotic Notation
- 2.2. Problems
- 2.3. Selected Answers
- 2.4. Summary and Notes
- 3. Basic Linear Algebra
- 3.1. Hilbert Spaces
- 3.2. Products of Spaces and Tensor Products
- 3.3. Matrices
- 3.4. Complex Spaces and Inner Products
- 3.5. Tensor Products of Matrices
- 3.6. Matrices, Graphs, and Sums over Paths
- 3.7. Problems
- 3.8. Selected Answers
- 3.9. Summary and Notes
- 4. Boolean Functions, Quantum Bits, and Feasibility
- 4.1. Feasible Boolean Functions
- 4.2. An Example
- 4.3. Quantum Representation of Boolean Arguments
- 4.4. Quantum Feasibility
- 4.5. Examples of Quantum Circuits
- 4.6. Problems
- 4.7. Selected Answers
- 4.8. Summary and Notes
- 5. Special Matrices
- 5.1. Hadamard Matrices
- 5.2. Fourier Matrices
- 5.3. Reversible Computation and Permutation Matrices
- 5.4. Feasible Diagonal Matrices
- 5.5. Reflections
- 5.6. Problems
- 5.7. Selected Answers
- 5.8. Summary and Notes
- 6. Tricks
- 6.1. Start Vectors
- 6.2. Controlling and Copying Base States
- 6.3. The Copy-Uncompute Trick
- 6.4. Superposition Tricks
- 6.5. Flipping a Switch
- 6.6. Measurement Tricks
- 6.7. Partial Transforms
- 6.8. Problems
- 6.9. Selected Answers
- 6.10. Summary and Notes
- 7. Phil's Algorithm
- 7.1. The Algorithm
- 7.2. The Analysis
- 7.3. An Example
- 7.4. A Two-Qubit Example
- 7.5. Phil Measures Up
- 7.6. Quantum Mazes Versus Circuits Versus Matrices
- 7.7. Problems
- 7.8. Selected Answers
- 7.9. Summary and Notes
- 8. Deutsch's Algorithm
- 8.1. The Algorithm
- 8.2. The Analysis
- 8.3. Superdense Coding and Teleportation
- 8.4. Problems
- 8.5. Summary and Notes
- 9. The Deutsch-Jozsa Algorithm
- 9.1. The Algorithm
- 9.2. The Analysis
- 9.3. Problems
- 9.4. Summary and Notes
- 10. Simon's Algorithm
- 10.1. The Algorithm
- 10.2. The Analysis
- 10.3. Problems
- 10.4. Summary and Notes
- 11. Shor's Algorithm
- 11.1. Strategy
- 11.2. Good Numbers
- 11.3. The Quantum Part of the Algorithm
- 11.4. Analysis of the Quantum Part
- 11.5. Probability of a Good Number
- 11.6. Using a Good Number
- 11.7. Continued Fractions
- 11.8. Problems
- 11.9. Summary and Notes
- 12. Factoring Integers
- 12.1. Some Basic Number Theory
- 12.2. Periods Give the Order
- 12.3. Factoring
- 12.4. Problems
- 12.5. Summary and Notes
- 13. Grover's Algorithm
- 13.1. The Algorithm
- 13.2. The Analysis
- 13.3. The General Case, with k Unknown
- 13.4. Problems
- 13.5. Summary and Notes
- II. Advanced Algorithms
- 14. Physics of Quantum Computing
- 14.1. Coherence and Cards
- 14.2. Dirac Notation
- 14.3. What Are Qubits?
- 14.4. Transformations and the Bloch Sphere
- 14.5. Measurements of Pure States
- 14.6. Mixed States and Decoherence
- 14.6.1. Trace and POVM
- 14.6.2. Partial Traces
- 14.6.3. Depolarizing and Dephasing
- 14.7. The CHSH Game
- 14.7.1. Classical Case
- 14.7.2. Quantum Case
- 14.7.3. Quantum Case Redux
- 14.8. Quantum Supremacy
- 14.9. Problems
- 14.10. Summary and Notes
- 15. Phase Estimation and Approximate Counting
- 15.1. Grover Approximate Counting
- 15.2. The Algorithm
- 15.3. The Analysis
- 15.4. Problems
- 15.5. Summary and Notes
- 16. Quantum Walks
- 16.1. Classical Random Walks
- 16.2. Random Walks and Matrices
- 16.3. An Encoding Nicety
- 16.4. Defining Quantum Walks
- 16.5. Interference and Diffusion
- 16.6. The Big Factor
- 16.7. Problems
- 16.8. Summary and Notes
- 17. Quantum Walk Search Algorithms
- 17.1. Search in Big Graphs
- 17.2. General Quantum Walk for Graph Search
- 17.3. Specifying the Generic Walk
- 17.4. Adding the Data
- 17.5. Tool Kit Theorem for Quantum Walk Search
- 17.5.1. The Generic Algorithm
- 17.5.2. The Generic Analysis
- 17.6. Grover Search as Generic Walk
- 17.7. Element Distinctness
- 17.8. Subgraph Triangle Incidence
- 17.9. Finding a Triangle
- 17.10. Evaluating Formulas and Playing Chess
- 17.11. Problems
- 17.12. Summary and Notes
- 18. Quantum Matrix Algorithms
- 18.1. Hermitian Matrices and Nature's Algorithm
- 18.2. The HHL Algorithm
- 18.3. Error Analysis
- 18.4. Improvements
- 18.5. Problems
- 18.6. Summary and Notes
- 19. Quantum Computation and BQP
- 19.1. The Class BQP
- 19.2. Equations, Solutions, and Complexity
- 19.3. A Circuit-Labeling Algorithm
- 19.4. Sums over Paths and Polynomial Roots
- 19.5. The Additive Polynomial Simulation
- 19.6. Bounding BQP
- 19.7. Logical Description of Quantum Systems
- 19.8. Problems
- 19.9. Summary and Notes
- 20. Beyond
- 20.1. Reviewing the Algorithms
- 20.2. Some Further Topics
- 20.3. The "Quantum" in the Algorithms
- References
- Index
