Linked e-resources
Details
Table of Contents
Machine generated contents note: Introduction
QUANTUM BUILDING BLOCKS
Single-Qubit Quantum Systems
The Quantum Mechanics of Photon Polarization
A Simple Experiment
A Quantum Explanation
Single Quantum Bits
Single-Qubit Measurement
A Quantum Key Distribution Protocol
The State Space of a Single-Qubit System
Relative Phases versus Global Phases
Geometric Views of the State Space of a Single Qubit
Comments on General Quantum State Spaces
References
Exercises
Multiple-Qubit Systems
Quantum State Spaces
Direct Sums of Vector Spaces
Tensor Products of Vector Spaces
The State Space of an n-Qubit System
Entangled States
Basics of Multi-Qubit Measurement
Quantum Key Distribution Using Entangled States
References
Exercises
Measurement of Multiple-Qubit States
Dirac's Bra/Ket Notation for Linear Transformations
Projection Operators for Measurement
Hermitian Operator Formalism for Measurement
The Measurement Postulate
EPR Paradox and Bell's Theorem
Setup for Bell's Theorem
What Quantum Mechanics Predicts
Special Case of Bell's Theorem: What Any Local Hidden Variable Theory Predicts
Bell's Inequality
References
Exercises
Quantum State Transformations
Unitary Transformations
Impossible Transformations: The No-Cloning Principle
Some Simple Quantum Gates
The Pauli Transformations
The Hadamard Transformation
Multiple-Qubit Transformations from Single-Qubit Transformations
The Controlled-not and Other Singly Controlled Gates
Applications of Simple Gates
Dense Coding
Quantum Teleportation
Realizing Unitary Transformations as Quantum Circuits
Decomposition of Single-Qubit Transformations
Singly-Controlled Single-Qubit Transformations
Multiply-Controlled Single-Qubit Transformations
General Unitary Transformations
A Universally Approximating Set of Gates
The Standard Circuit Model
References
Exercises
Quantum Versions of Classical Computations
From Reversible Classical Computations to Quantum Computations
Reversible and Quantum Versions of Simple Classical Gates
Reversible Implementations of Classical Circuits
A Naive Reversible Implementation
A General Construction
A Language for Quantum Implementations
The Basics
Functions
Some Example Programs for Arithmetic Operations
Efficient Implementation of and
Efficient Implementation of Multiply-Controlled Single-Qubit Transformations
In-Place Addition
Modular Addition
Modular Multiplication
Modular Exponentiation
References
Exercises
QUANTUM ALGORITHMS
Introduction to Quantum Algorithms
Computing with Superpositions
The Walsh-Hadamard Transformation
Quantum Parallelism
Notions of Complexity
Query Complexity
Communication Complexity
A Simple Quantum Algorithm
Deutsch's Problem
Quantum Subroutines
The Importance of Unentangling Temporary Qubits in Quantum Subroutines
Phase Change for a Subset of Basis Vectors
State-Dependent Phase Shifts
State-Dependent Single-Qubit Amplitude Shifts
A Few Simple Quantum Algorithms
Deutsch-Jozsa Problem
Bernstein-Vazirani Problem
Simon's Problem
Distributed Computation
Comments on Quantum Parallelism
Machine Models and Complexity Classes
Complexity Classes
Complexity: Known Results
Quantum Fourier Transformations
The Classical Fourier Transform
The Quantum Fourier Transform
A Quantum Circuit for Fast Fourier Transform
References
Exercises
Shor's Algorithm
Classical Reduction to Period-Finding
Shor's Factoring Algorithm
The Quantum Core
Classical Extraction of the Period from the Measured Value
Example Illustrating Shor's Algorithm
The Efficiency of Shor's Algorithm
Omitting the Internal Measurement
Generalizations
The Discrete Logarithm Problem
Hidden Subgroup Problems
References
Exercises
Graver's Algorithm and Generalizations
Graver's Algorithm
Outline
Setup
The Iteration Step
How Many Iterations?
Amplitude Amplification
The Geometry of Amplitude Amplification
Optimality of Grover's Algorithm
Reduction to Three Inequalities
Proofs of the Three Inequalities
Derandomization of Grover's Algorithm and Amplitude Amplification
Approach 1: Modifying Each Step
Approach 2: Modifying Only the Last Step
Unknown Number of Solutions
Varying the Number of Iterations
Quantum Counting
Practical Implications of Grover's Algorithm and Amplitude Amplification
References
Exercises
ENTANGLED SUBSYSTEMS AND ROBUST QUANTUM COMPUTATION
Quantum Subsystems and Properties of Entangled States
Quantum Subsystems and Mixed States
Density Operators
Properties of Density Operators
The Geometry of Single-Qubit Mixed States
Von Neumann Entropy
Classifying Entangled States
Bipartite Quantum Systems
Classifying Bipartite Pure States up to LOCC Equivalence
Quantifying Entanglement in Bipartite Mixed States
Multipartite Entanglement
Density Operator Formalism for Measurement
Measurement of Density Operators
Transformations of Quantum Subsystems and Decoherence
Superoperators
Operator Sum Decomposition
A Relation Between Quantum State Transformations and Measurements
Decoherence
References
Exercises
Quantum Error Correction
Three Simple Examples of Quantum Error Correcting Codes
A Quantum Code That Corrects Single Bit-Flip Errors
A Code for Single-Qubit Phase-Flip Errors
A Code for All Single-Qubit Errors
Framework for Quantum Error Correcting Codes
Classical Error Correcting Codes
Quantum Error Correcting Codes
Correctable Sets of Errors for Classical Codes
Correctable Sets of Errors for Quantum Codes
Correcting Errors Using Classical Codes
Diagnosing and Correcting Errors Using Quantum Codes
Quantum Error Correction across Multiple Blocks
Computing on Encoded Quantum States
Superpositions and Mixtures of Correctable Errors Are Correctable
The Classical Independent Error Model
Quantum Independent Error Models
CSS Codes
Dual Classical Codes
Construction of CSS Codes from Classical Codes Satisfying a Duality Condition
The Steane Code
Stabilizer Codes
Alternatives to the Circuit Model of Quantum Computation
Measurement-Based Cluster State Quantum Computation
Adiabatic Quantum Computation
Holonomic Quantum Computation
Topological Quantum Computation
Quantum Protocols
Insight into Classical Computation
Building Quantum Computers
Simulating Quantum Systems
Where Does the Power of Quantum Computation Come From?
What if Quantum Mechanics Is Not Quite Correct?
APPENDIXES
Some Relations Between Quantum Mechanics and Probability Theory
Tensor Products in Probability Theory
Quantum Mechanics as a Generalization of Probability Theory
References
Exercises
Solving the Abelian Hidden Subgroup Problem
Note continued: Representations of Finite Abelian Groups
Schur's Lemma
Quantum Fourier Transforms for Finite Abelian Groups
The Fourier Basis of an Abelian Group
The Quantum Fourier Transform Over a Finite Abelian Group
General Solution to the Finite Abelian Hidden Subgroup Problem
Instances of the Abelian Hidden Subgroup Problem
Simon's Problem
Shor's Algorithm: Finding the Period of a Function
Comments on the Non-Abelian Hidden Subgroup Problem
References
Exercises.
QUANTUM BUILDING BLOCKS
Single-Qubit Quantum Systems
The Quantum Mechanics of Photon Polarization
A Simple Experiment
A Quantum Explanation
Single Quantum Bits
Single-Qubit Measurement
A Quantum Key Distribution Protocol
The State Space of a Single-Qubit System
Relative Phases versus Global Phases
Geometric Views of the State Space of a Single Qubit
Comments on General Quantum State Spaces
References
Exercises
Multiple-Qubit Systems
Quantum State Spaces
Direct Sums of Vector Spaces
Tensor Products of Vector Spaces
The State Space of an n-Qubit System
Entangled States
Basics of Multi-Qubit Measurement
Quantum Key Distribution Using Entangled States
References
Exercises
Measurement of Multiple-Qubit States
Dirac's Bra/Ket Notation for Linear Transformations
Projection Operators for Measurement
Hermitian Operator Formalism for Measurement
The Measurement Postulate
EPR Paradox and Bell's Theorem
Setup for Bell's Theorem
What Quantum Mechanics Predicts
Special Case of Bell's Theorem: What Any Local Hidden Variable Theory Predicts
Bell's Inequality
References
Exercises
Quantum State Transformations
Unitary Transformations
Impossible Transformations: The No-Cloning Principle
Some Simple Quantum Gates
The Pauli Transformations
The Hadamard Transformation
Multiple-Qubit Transformations from Single-Qubit Transformations
The Controlled-not and Other Singly Controlled Gates
Applications of Simple Gates
Dense Coding
Quantum Teleportation
Realizing Unitary Transformations as Quantum Circuits
Decomposition of Single-Qubit Transformations
Singly-Controlled Single-Qubit Transformations
Multiply-Controlled Single-Qubit Transformations
General Unitary Transformations
A Universally Approximating Set of Gates
The Standard Circuit Model
References
Exercises
Quantum Versions of Classical Computations
From Reversible Classical Computations to Quantum Computations
Reversible and Quantum Versions of Simple Classical Gates
Reversible Implementations of Classical Circuits
A Naive Reversible Implementation
A General Construction
A Language for Quantum Implementations
The Basics
Functions
Some Example Programs for Arithmetic Operations
Efficient Implementation of and
Efficient Implementation of Multiply-Controlled Single-Qubit Transformations
In-Place Addition
Modular Addition
Modular Multiplication
Modular Exponentiation
References
Exercises
QUANTUM ALGORITHMS
Introduction to Quantum Algorithms
Computing with Superpositions
The Walsh-Hadamard Transformation
Quantum Parallelism
Notions of Complexity
Query Complexity
Communication Complexity
A Simple Quantum Algorithm
Deutsch's Problem
Quantum Subroutines
The Importance of Unentangling Temporary Qubits in Quantum Subroutines
Phase Change for a Subset of Basis Vectors
State-Dependent Phase Shifts
State-Dependent Single-Qubit Amplitude Shifts
A Few Simple Quantum Algorithms
Deutsch-Jozsa Problem
Bernstein-Vazirani Problem
Simon's Problem
Distributed Computation
Comments on Quantum Parallelism
Machine Models and Complexity Classes
Complexity Classes
Complexity: Known Results
Quantum Fourier Transformations
The Classical Fourier Transform
The Quantum Fourier Transform
A Quantum Circuit for Fast Fourier Transform
References
Exercises
Shor's Algorithm
Classical Reduction to Period-Finding
Shor's Factoring Algorithm
The Quantum Core
Classical Extraction of the Period from the Measured Value
Example Illustrating Shor's Algorithm
The Efficiency of Shor's Algorithm
Omitting the Internal Measurement
Generalizations
The Discrete Logarithm Problem
Hidden Subgroup Problems
References
Exercises
Graver's Algorithm and Generalizations
Graver's Algorithm
Outline
Setup
The Iteration Step
How Many Iterations?
Amplitude Amplification
The Geometry of Amplitude Amplification
Optimality of Grover's Algorithm
Reduction to Three Inequalities
Proofs of the Three Inequalities
Derandomization of Grover's Algorithm and Amplitude Amplification
Approach 1: Modifying Each Step
Approach 2: Modifying Only the Last Step
Unknown Number of Solutions
Varying the Number of Iterations
Quantum Counting
Practical Implications of Grover's Algorithm and Amplitude Amplification
References
Exercises
ENTANGLED SUBSYSTEMS AND ROBUST QUANTUM COMPUTATION
Quantum Subsystems and Properties of Entangled States
Quantum Subsystems and Mixed States
Density Operators
Properties of Density Operators
The Geometry of Single-Qubit Mixed States
Von Neumann Entropy
Classifying Entangled States
Bipartite Quantum Systems
Classifying Bipartite Pure States up to LOCC Equivalence
Quantifying Entanglement in Bipartite Mixed States
Multipartite Entanglement
Density Operator Formalism for Measurement
Measurement of Density Operators
Transformations of Quantum Subsystems and Decoherence
Superoperators
Operator Sum Decomposition
A Relation Between Quantum State Transformations and Measurements
Decoherence
References
Exercises
Quantum Error Correction
Three Simple Examples of Quantum Error Correcting Codes
A Quantum Code That Corrects Single Bit-Flip Errors
A Code for Single-Qubit Phase-Flip Errors
A Code for All Single-Qubit Errors
Framework for Quantum Error Correcting Codes
Classical Error Correcting Codes
Quantum Error Correcting Codes
Correctable Sets of Errors for Classical Codes
Correctable Sets of Errors for Quantum Codes
Correcting Errors Using Classical Codes
Diagnosing and Correcting Errors Using Quantum Codes
Quantum Error Correction across Multiple Blocks
Computing on Encoded Quantum States
Superpositions and Mixtures of Correctable Errors Are Correctable
The Classical Independent Error Model
Quantum Independent Error Models
CSS Codes
Dual Classical Codes
Construction of CSS Codes from Classical Codes Satisfying a Duality Condition
The Steane Code
Stabilizer Codes
Alternatives to the Circuit Model of Quantum Computation
Measurement-Based Cluster State Quantum Computation
Adiabatic Quantum Computation
Holonomic Quantum Computation
Topological Quantum Computation
Quantum Protocols
Insight into Classical Computation
Building Quantum Computers
Simulating Quantum Systems
Where Does the Power of Quantum Computation Come From?
What if Quantum Mechanics Is Not Quite Correct?
APPENDIXES
Some Relations Between Quantum Mechanics and Probability Theory
Tensor Products in Probability Theory
Quantum Mechanics as a Generalization of Probability Theory
References
Exercises
Solving the Abelian Hidden Subgroup Problem
Note continued: Representations of Finite Abelian Groups
Schur's Lemma
Quantum Fourier Transforms for Finite Abelian Groups
The Fourier Basis of an Abelian Group
The Quantum Fourier Transform Over a Finite Abelian Group
General Solution to the Finite Abelian Hidden Subgroup Problem
Instances of the Abelian Hidden Subgroup Problem
Simon's Problem
Shor's Algorithm: Finding the Period of a Function
Comments on the Non-Abelian Hidden Subgroup Problem
References
Exercises.