Approaching Quantum Computing
Published on 6. October 2004
Book
Hardback
400 pages
978-0-13-145224-4 (ISBN)
Description
For one-semester first courses in Quantum Computing. An introduction to the subject for undergraduate and graduate students in computer and electrical engineering, computer science, mathematics, and chemistry.
With a clear writing style and matter-of-fact approach, this rigorous yet accessible introduction is designed for students with a solid mathematical background but limited knowledge of physics and quantum mechanics. It introduces the quantum circuit model comprehensively-including the mathematical formalism required for quantum computing-using a methodical approach and an abundance of worked examples.
With a clear writing style and matter-of-fact approach, this rigorous yet accessible introduction is designed for students with a solid mathematical background but limited knowledge of physics and quantum mechanics. It introduces the quantum circuit model comprehensively-including the mathematical formalism required for quantum computing-using a methodical approach and an abundance of worked examples.
Reviews / Votes
"This book arms to introduce the basics of quantum computing to advanced undergraduates anti beginning graduate students in electrical engineering arid computer science who have practically no background in quantum mechanics, but a fair level of mathematical sophistication. The basic ideas of quantum mechanics are developed in the context of two- and other finite state systems and illustrated by means of well-chosen physical examples. The heart of the book is devoted to a treatment of quantum gates and circuits, and following it, a discussion of quantum algorithms, including Shor's factoring algorithm and Grover's search algorithm. The purpose of the book is to make recent exciting developments in this emerging field accessible to the next generation of computer scientists as well as others without a traditional background in physics, End-of-chapter exercises, historical and biographical footnotes, a detailed glossary and a large number of references also make this a valuable text or reference work." - P.K. Aravind, Physics Department, Worcester Polytechnic Institute"Quantum computing is a new promising area of research that investigates how the laws of quantum mechanics allow new forms of computation exponentially more efficient than any classical counterpart. This book aims at giving a gentle introduction to the basic concepts and mathematical techniques of this interdisciplinary research area to a readership with no previous background in quantum mechanics." - G. Massimo Palma, University of Milano and INFM
"Since it draws on same deed aspects of physics and mathematics, quantum computing can be a challenging subject to present. The Marinescus have done an admirable job of writing a highly readable and self-contained textbook on this important and fascinating new area of computer science. This is a thorough and very readable introduction to quantum computing. It should be especially useful as the text far an upper-level undergraduate or beginning graduate course aimed at computer science and engineering majors. The Marinescus have managed the difficult task of writing a book an quantum computing that is both technically complete and a pleasure to read. " - John Hayes, University of Michigan
More details
Content
1 Preface
2 Introduction
2.1 Computing and the Laws of Physics
2.2 Quantum Information
2.3 Quantum Computers
2.4 The Wave and the Corpuscular Nature of Light
2.5 Deterministic versus Probabilistic Photon Behavior
2.6 State Description, Superposition, and Uncertainty
2.7 Measurements in Multiple Bases
2.8 Measurements of Superposition States
2.9 An Augmented Probabilistic Model. The Superposition Probability Rule.
2.10 A Photon Coincidence Experiment
2.11 A Three Beam Splitter Experiment
2.12 BB84, the Emergence of Quantum Cryptography
2.13 A Qubit of History
2.14 Summary and Further Readings
2.15Exercises and Problems
3 Quantum Mechanics, a Mathematical Model of the Physical World
3.1 Vector Spaces
3.2 n-Dimensional Real Euclidean Vector Space
3.3 Linear Operators and Matrices
3.4 Hermitian Operators in a Complex n -Dimensional Euclidean Vector Space
3.5 n -Dimensional Hilbert Spaces. Dirac Notations
3.6 The Inner Product in an n -Dimensional Hilbert Space
3.7 Tensor and Outer Products
3.8 Quantum States
3.9 Quantum Observables. Quantum Operators
3.10 Spectral Decomposition of a Quantum Operator
3.11 The Measurement of Observables
3.12 More about Measurements. The Density Operator
3.13 Double-Slit Experiments
3.14 Stern-Gerlach Type Experiments
3.15 The Spin as an Intrinsic Property
3.16 SchrodingerOs Wave Equation
3.17 HeisenbergOs Uncertainty Principle
3.18 A Brief History of Quantum Ideas
3.19 Summary and Further Readings
3.20 Exercises and Problems
4 Qubits and Their Physical Realization
4.1 One Qubit, a Very Small Bit
4.2 The Bloch Sphere Representation of One Qubit
4.3 Rotation Operations on the Bloch Sphere
4.4 The Measurement of a Single Qubit
4.5 Pure and Impure States of a Qubit
4.6 A Pair of Qubits. Entanglement
4.7 The Fragility of Quantum Information. SchrodingerOs Cat
4.8 Qubits: from Hilbert Spaces to Physical Implementation
4.9 Qubits as Spin One-Half Particles
4.10 The Measurement of the Spin
4.11 The Qubit as a Polarized Photon
4.12 Entanglement
4.13 The Exchange of Information Using Entangled Particles
4.14 Summary and Further Readings
4.15 Exercises and Problems
5 Quantum Gates and Quantum Circuits
5.1 Classical Logic Gates and Circuits
5.2 One-Qubit Gates
5.3 The Hadamard Gate, Beam Splitters and Interferometers
5.4 Two-Qubit Gates. The CNOT Gate
5.5 Can We Build Quantum Copy Machines?
5.6 Three-Qubit Gates. The Fredkin Gate
5.7 The Toffoli Gate
5.8 Quantum Circuits
5.9 The No Cloning Theorem
5.10 Qubit Swapping and Full Adder Circuits
5.11 More about Unitary Operations and Rotation Matrices
5.12 Single-Qubit Controlled Operations
5.13 Multiple Qubit Controlled Operations
5.14 Universal Quantum Gates
5.15 A Quantum Circuit for the Walsh-Hadamard Transform
5.16 The State Transformation Performed by Quantum Circuits
5.17 Mathematical Models of a Quantum Computer
5.18 Errors, Uniformity Conditions, and Time Complexity
5.19 Summary and Further Readings
5.20 Exercises and Problems
6 Quantum Algorithms
6.1 From Classical to Quantum Turing Machines
6.2 Computational Complexity and Entanglement
6.3 Classes of Quantum Algorithms
6.4 Quantum Parallelism
6.5 DeutschOs Problem
6.6 Quantum Fourier Transform
6.7 Tensor Product Factorization
6.8 A Circuit for Quantum Fourier Transform
6.9 A Case Study: A Three-Qubit QFT
6.10 ShorOs Factoring Algorithm and Order Finding
6.11 A Quantum Circuit for Computing f(x)Modulo 2
6.12 SimonOs Algorithm for Phase Estimation
6.13 The Fourier Transform on an Abelian Group
6.14 Periodicity and the Quantum Fourier Transform
6.15 The Discrete Logarithms Evaluation Problem
6.16 The Hidden Subgroup Problem
6.17 Quantum Search Algorithms
6.18 Historical Notes
6.19 Summary and Further Readings
6.20 Exercises and Problems
7 The "Entanglement" of Computing and Communication with Quantum Mechanics. Reversible Computations
7.1 Communication, Entropy, and Quantum Information
7.2 Information Encoding
7.3 Quantum Teleportation with Maximally Entangled Particles
7.4 Anti-Correlation and Teleportation
7.5 Dense Coding
7.6 Quantum Key Distribution
7.7 EPR Pairs and Bell States
7.8 Uncertainty and Locality
7.9 Possible Explanations of the EPR Experiment
7.10 The Bell Inequality. Local Realism
7.11 Reversibility and Entropy
7.12 Thermodynamics and Thermodynamic Entropy
7.13 The Maxwell Demon
7.14 Energy Consumption. Landauer Principle
7.15 Low Power Computing. Adiabatic Switching
7.16 Bennett Information Driven Engine
7.17 Logically Reversible Turing Machines and Physical Reversibility
7.18 Historical Notes
7.19 Summary and Further Readings 297
7.20 Exercises and Problems 299
8 Appendix I: Algebraic Structures
8.1 Rings, Commutative Rings, Integral Domains, Fields
8.2 Complex Numbers
8.3 Abstract Groups and Isomorphisms
8.4 Matrix Representation
8.5 Groups of Transformations
8.6 Symmetry in a Plane
8.7 Finite Fields
9 Appendix II: Modular Arithmetic
9.1 Elementary Number Theory Concepts
9.2 EuclidOs Algorithm for Integers
9.3 The Chinese Remainder Theorem and its Applications
9.4 Computer Arithmetic for Large Integers
10 Appendix III: Welsh-Hadamard Transform
10.1 Hadamard Matrices
10.2 The Fast Hadamard Transform
11 Appendix IV: Fourier Transform and Fourier Series
12 Glossary
2 Introduction
2.1 Computing and the Laws of Physics
2.2 Quantum Information
2.3 Quantum Computers
2.4 The Wave and the Corpuscular Nature of Light
2.5 Deterministic versus Probabilistic Photon Behavior
2.6 State Description, Superposition, and Uncertainty
2.7 Measurements in Multiple Bases
2.8 Measurements of Superposition States
2.9 An Augmented Probabilistic Model. The Superposition Probability Rule.
2.10 A Photon Coincidence Experiment
2.11 A Three Beam Splitter Experiment
2.12 BB84, the Emergence of Quantum Cryptography
2.13 A Qubit of History
2.14 Summary and Further Readings
2.15Exercises and Problems
3 Quantum Mechanics, a Mathematical Model of the Physical World
3.1 Vector Spaces
3.2 n-Dimensional Real Euclidean Vector Space
3.3 Linear Operators and Matrices
3.4 Hermitian Operators in a Complex n -Dimensional Euclidean Vector Space
3.5 n -Dimensional Hilbert Spaces. Dirac Notations
3.6 The Inner Product in an n -Dimensional Hilbert Space
3.7 Tensor and Outer Products
3.8 Quantum States
3.9 Quantum Observables. Quantum Operators
3.10 Spectral Decomposition of a Quantum Operator
3.11 The Measurement of Observables
3.12 More about Measurements. The Density Operator
3.13 Double-Slit Experiments
3.14 Stern-Gerlach Type Experiments
3.15 The Spin as an Intrinsic Property
3.16 SchrodingerOs Wave Equation
3.17 HeisenbergOs Uncertainty Principle
3.18 A Brief History of Quantum Ideas
3.19 Summary and Further Readings
3.20 Exercises and Problems
4 Qubits and Their Physical Realization
4.1 One Qubit, a Very Small Bit
4.2 The Bloch Sphere Representation of One Qubit
4.3 Rotation Operations on the Bloch Sphere
4.4 The Measurement of a Single Qubit
4.5 Pure and Impure States of a Qubit
4.6 A Pair of Qubits. Entanglement
4.7 The Fragility of Quantum Information. SchrodingerOs Cat
4.8 Qubits: from Hilbert Spaces to Physical Implementation
4.9 Qubits as Spin One-Half Particles
4.10 The Measurement of the Spin
4.11 The Qubit as a Polarized Photon
4.12 Entanglement
4.13 The Exchange of Information Using Entangled Particles
4.14 Summary and Further Readings
4.15 Exercises and Problems
5 Quantum Gates and Quantum Circuits
5.1 Classical Logic Gates and Circuits
5.2 One-Qubit Gates
5.3 The Hadamard Gate, Beam Splitters and Interferometers
5.4 Two-Qubit Gates. The CNOT Gate
5.5 Can We Build Quantum Copy Machines?
5.6 Three-Qubit Gates. The Fredkin Gate
5.7 The Toffoli Gate
5.8 Quantum Circuits
5.9 The No Cloning Theorem
5.10 Qubit Swapping and Full Adder Circuits
5.11 More about Unitary Operations and Rotation Matrices
5.12 Single-Qubit Controlled Operations
5.13 Multiple Qubit Controlled Operations
5.14 Universal Quantum Gates
5.15 A Quantum Circuit for the Walsh-Hadamard Transform
5.16 The State Transformation Performed by Quantum Circuits
5.17 Mathematical Models of a Quantum Computer
5.18 Errors, Uniformity Conditions, and Time Complexity
5.19 Summary and Further Readings
5.20 Exercises and Problems
6 Quantum Algorithms
6.1 From Classical to Quantum Turing Machines
6.2 Computational Complexity and Entanglement
6.3 Classes of Quantum Algorithms
6.4 Quantum Parallelism
6.5 DeutschOs Problem
6.6 Quantum Fourier Transform
6.7 Tensor Product Factorization
6.8 A Circuit for Quantum Fourier Transform
6.9 A Case Study: A Three-Qubit QFT
6.10 ShorOs Factoring Algorithm and Order Finding
6.11 A Quantum Circuit for Computing f(x)Modulo 2
6.12 SimonOs Algorithm for Phase Estimation
6.13 The Fourier Transform on an Abelian Group
6.14 Periodicity and the Quantum Fourier Transform
6.15 The Discrete Logarithms Evaluation Problem
6.16 The Hidden Subgroup Problem
6.17 Quantum Search Algorithms
6.18 Historical Notes
6.19 Summary and Further Readings
6.20 Exercises and Problems
7 The "Entanglement" of Computing and Communication with Quantum Mechanics. Reversible Computations
7.1 Communication, Entropy, and Quantum Information
7.2 Information Encoding
7.3 Quantum Teleportation with Maximally Entangled Particles
7.4 Anti-Correlation and Teleportation
7.5 Dense Coding
7.6 Quantum Key Distribution
7.7 EPR Pairs and Bell States
7.8 Uncertainty and Locality
7.9 Possible Explanations of the EPR Experiment
7.10 The Bell Inequality. Local Realism
7.11 Reversibility and Entropy
7.12 Thermodynamics and Thermodynamic Entropy
7.13 The Maxwell Demon
7.14 Energy Consumption. Landauer Principle
7.15 Low Power Computing. Adiabatic Switching
7.16 Bennett Information Driven Engine
7.17 Logically Reversible Turing Machines and Physical Reversibility
7.18 Historical Notes
7.19 Summary and Further Readings 297
7.20 Exercises and Problems 299
8 Appendix I: Algebraic Structures
8.1 Rings, Commutative Rings, Integral Domains, Fields
8.2 Complex Numbers
8.3 Abstract Groups and Isomorphisms
8.4 Matrix Representation
8.5 Groups of Transformations
8.6 Symmetry in a Plane
8.7 Finite Fields
9 Appendix II: Modular Arithmetic
9.1 Elementary Number Theory Concepts
9.2 EuclidOs Algorithm for Integers
9.3 The Chinese Remainder Theorem and its Applications
9.4 Computer Arithmetic for Large Integers
10 Appendix III: Welsh-Hadamard Transform
10.1 Hadamard Matrices
10.2 The Fast Hadamard Transform
11 Appendix IV: Fourier Transform and Fourier Series
12 Glossary