Introduction to Classical and Quantum Computing

Classical Information and Computation
Bits
Coins
Dice
Encoding Information
Physical Bits
Binary
ASCII
Logic Gates
Single-Bit Gates
Two-Bit Gates
Logic Gates as Physical Circuits
Multiple Gates
Universal Gates
Adders and Verilog
Adding Binary Numbers by Hand
Half Adder
Full Adder
Ripple-Carry Adder
Ripple-Carry with Full Adders
Circuit Complexity
Circuit Simplification and Boolean Algebra
Order of Operations
Association, Commutivity, and Distribution
Identities Involving Zero and One
Single-Variable Identities
Two-Variable Identities and De Morgan's Laws
Circuit Simplification
Reversible Logic Gates
Reversible Gates
Irreversible Gates
Toffoli Gate: A Reversible AND Gate
Making Irreversible Gates Reversible
Error Correction
Errors in Physical Devices
Error Detection
Error Correction
Computational Complexity
Asymptotic Notation
Complexity Classes
Turing Machines
Components
Incrementing Binary Numbers
Church-Turing Thesis
Summary
One Quantum Bit
Qubit Touchdown: A Quantum Computing Board Game
Superposition
Zero or One
Superposition
Review of Complex Numbers
Measurement
Measurement in the Z-Basis
Normalization
Measurement in Other Bases
Consecutive Measurements
Bloch Sphere Mapping
Global and Relative Phases
Spherical Coordinates
Cartesian Coordinates
Physical Qubits
Quantum Gates
Linear Maps
Classical Reversible Gates
Common One-Qubit Quantum Gates
General One-Qubit Gates
Quantum Circuits
Circuit Diagrams
Quirk
Summary
Linear Algebra
Quantum States
Column Vectors
Row Vectors
Inner Products
Inner Products Are Scalars
Orthonormality
Projection, Measurement, and Change of Basis
Quantum Gates
Gates as Matrices
Common One-Qubit Gates as Matrices
Sequential Quantum Gates
Circuit Identities
Unitarity
Reversibility
Outer Products
Outer Products Are Matrices
Completeness Relation
Summary
Multiple Quantum Bits
Entanglion: A Quantum Computing Board Game
Mechanics
Connection to Quantum Computing
States and Measurement
Tensor Product
Kronecker Product
Measuring Individual Qubits
Sequential Single-Qubit Measurements
Entanglement
Product States
Entangled States
Quantum Gates
One-Qubit Quantum Gates
Two-Qubit Quantum Gates
Toffoli Gate
No-Cloning Theorem
Quantum Adders
Classical Adder
Making the Classical Adder a Quantum Gate
Quantum Setup
Quantum Sum
Quantum Carry
Quantum Ripple-Carry Adder
Circuit Complexity
Adding in Superposition
Universal Quantum Gates
Definition
Components of a Universal Gate Set
Examples of Universal Gate Sets
Solovay-Kitaev Theorem
Quantum Computing without Complex Numbers
Quantum Error Correction
Decoherence
Bit-Flip Code
Phase-Flip Code
Shor Code
Summary
Quantum Programming
IBM Quantum Experience
Services
Circuit Composer
Quantum Processor
Simulator
Quantum Assembly Language
OpenQASM
Quantum Experience Standard Header
OpenQASM in IBM Quantum Experience
Quantum Adder
Qiskit
Circuit Composer
Quantum Lab
Simulator
Quantum Processor
Other Quantum Programming Languages
Summary
Entanglement and Quantum Protocols
Measurements
Product States
Maximally Entangled States
Partially Entangled States
Bell Inequalities
EPR Paradox and Local Hidden Variables
Bell Inequalities and the CHSH Inequality
Quantum Processor Experiment
Other Experiments
No-Signaling Principle
Other Theories
Monogamy of Entanglement
Classical Correlations
Quantum Entanglement
Superdense Coding
The Problem
Classical Solution
Quantum Solution
Quantum Teleportation
The Problem
Classical Solution
Quantum Solution
Quantum Key Distribution
Encryption
Classical Solution: Public Key Cryptography
Quantum Solution: BB84
Summary
Quantum Algorithms
Circuit vs Query Complexity
Circuit Complexity
Query Complexity
Quantum Oracles
Phase Oracle
Parity
The Problem
Classical Solution
Quantum Solution: Deutsch's Algorithm
Generalization to Additional Bits
Constant vs Balanced Functions
The Problem
Classical Solution
Quantum Solution: Deutsch-Jozsa Algorithm
Secret Dot Product String
The Problem
Classical Solution
Quantum Solution: Bernstein-Vazirani Algorithm
Recursive Problem
Secret XOR Mask
The Problem
Classical Solution
Quantum Solution: Simon's Algorithm
Summary
Brute-Force Searching
The Problem
Classical Solution
Quantum Solution: Grover's Algorithm
Reflection About Uniform State
Optimality
Discrete Fourier Transform
Application: Analyzing Music
Classical Solution: Fast Fourier Transform
Quantum Solution: Quantum Fourier Transform
Inverse Quantum Fourier Transform
Phase / Eigenvalue Estimation
The Problem
Classical Solution
Quantum Solution
Multiple Eigenstates
Period of Modular Exponentiation
The Problem
Classical Solution
Quantum Solution
Factoring
The Problem
Classical Solution
Quantum Solution: Shor's Algorithm
Summary
Next Steps
Careers in Quantum Computing
Technical Next Steps
Questions
Parting Words
Answers to Exercises
Index