Quantum algorithms for data analysis
1
Preface
1.1
Abstract
1.2
Changelog
1.3
Teaching using this book
I Bridging the gap
2
Quantum computing and quantum algorithms
2.1
Getting rid of physics in quantum computing
2.2
Axioms of quantum mechanics
2.2.1
Review of important statements in quantum computation
2.3
Measuring complexity of quantum algorithms
2.4
Review of famous quantum algorithms
2.4.1
Deutsch-Josza
2.4.2
Bernstein-Vazirani
2.4.3
Hadamard test
2.4.4
Modified Hadamard test
2.4.5
Swap test
3
Classical data on quantum computers
3.1
Representing data in quantum computers
3.1.1
Binary encoding
3.1.2
Amplitude encoding
3.1.3
Block encoding
3.1.4
Angle encoding
3.1.5
Graph encoding
3.1.6
One-hot encoding
3.2
Quantum memory
3.2.1
The quantum memory model of computation
3.2.2
The quantum processing unit and quantum memory device
3.3
Implementations
3.3.1
Binary encoding
3.3.2
Amplitude encoding
3.3.3
Block encoding
3.4
Use case: working with classical probability distributions
3.5
Retrieving Data
3.5.1
Density matrices
4
Classical machine learning
4.1
Supervised learning
4.2
Unsupervised learning
4.3
Generative and discriminative models
4.4
Dimensionality reduction
4.5
Generalized eigenvalue problems in machine learning
4.6
How to evaluate a classifier
5
A useful toolbox
5.1
Phase estimation
5.2
Grover’s algorithm, amplitude games
5.2.1
Amplitude estimation
5.2.2
Amplitude amplification
5.2.3
Example: estimating average and variance of a function
5.3
Finding the minimum
5.4
Quantum linear algebra
5.4.1
Singular value estimation
5.4.2
Linear combination of unitaries
5.4.3
Singular value transformation
5.4.4
Matrix inversion after HHL
5.5
Distances, inner products, norms, and quadratic forms
5.5.1
Inner products and quadratic forms with KP-trees
5.5.2
Inner product and l1-norm estimation with query access
5.6
Hamiltonian simulation
5.6.1
Introduction to Hamiltonians
II Quantum Machine Learning
6
Quantum perceptron
6.1
Classical perceptron
6.1.1
Training the perceptron
6.2
Online quantum perceptron
6.3
Version space quantum perceptron
7
SVE-based quantum algorithms
7.1
Spectral norm and the condition number estimation
7.2
Explained variance: estimating quality of representations
7.3
Extracting the SVD representations
7.4
Singular value estimation of a product of two matrices
7.5
A last example: Slow algorithms for log-determinant
8
Quantum algorithms for Monte Carlo
8.1
Monte Carlo with quantum computing
8.2
Bounded output
8.3
Bounded
\(\ell_2\)
norm
8.4
Bounded variance
8.5
Applications
8.5.1
Pricing of financial derivatives
9
Dimensionality reduction
9.1
Unsupervised algorithms
9.1.1
Quantum PCA
9.1.2
Quantum Correspondence Analysis
9.1.3
Quantum Latent Semantic Analysis
9.2
Supervised algorithms
9.2.1
Quantum Slow Feature Analysis
10
q-means
10.1
The k-means algorithm
10.1.1
\(\delta-\)
k-means
10.2
The
\(q\)
-means algorithm
10.2.1
Step 1: Centroid distance estimation
10.2.2
Step 2: Cluster assignment
10.2.3
Step 3: Centroid state creation
10.2.4
Step 4: Centroid update
10.2.5
Initialization of
\(q\)
-means++
10.3
Analysis
10.3.1
Error analysis
10.3.2
Runtime analysis
11
Quantum Expectation-Maximization
11.1
Expectation-Maximization for GMM
11.2
Expectation-Maximization
11.2.1
Initialization strategies for EM
11.2.2
Dataset assumptions in GMM
11.3
Quantum Expectation-Maximization for GMM
11.3.1
Expectation
11.3.2
Maximization
12
QML on real datasets
12.1
Theoretical considerations
12.1.1
Modelling well-clusterable datasets
12.2
Experiments
12.2.1
Datasets
12.2.2
q-means
12.2.3
QSFA
12.2.4
QEM
12.2.5
QPCA
13
Quantum algorithms for graph problems
13.1
Connectivity
13.2
Summary of results
14
Lower bounds on query complexity of quantum algorithms
14.1
Polynomial method
14.2
Quantum adversary method
III Everything else
15
Selected works on quantum algorithms
16
Solutions to exercises
Appendix
A
Math and linear algebra
A.1
Norms, distances, trace, inequalities
A.2
Linear algebra
A.2.1
Eigenvalues, eigenvectors and eigendecomposition of a matrix
A.2.2
Singular value decomposition
A.2.3
Singular vectors for data representation
A.3
Useful theorems around linear algebra
A.4
Inequalities
A.5
Trigonometry
B
Series
C
Probability
C.1
Measure theory
C.1.1
Boosting probabilities with “median lemma” (or powering lemma )
C.2
Markov chains
C.3
Distributions
C.4
Concentration inequalities
C.4.1
Markov inequality
C.4.2
Chebyshev inequality
C.4.3
Weak Law of large numbers
C.4.4
Strong Law of Large Numbers
C.4.5
Chernoff bound
C.4.6
Hoeffding inequality
D
Error propagation and approximation
D.0.1
Propagation of error in functions of one variable
D.1
Useful quantum subroutines and folklore results
E
Approximation theory
E.1
Polynomial approximation of
\(\log(x)\)
E.2
Polynomial approximation of
\(1/x\)
E.3
Polynomial approximation of other functions
F
Contributions and acknowledgements
F.1
License and citation
F.2
Cookie Policy
G
References
By Alessandro 'Scinawa' Luongo
Quantum algorithms for data analysis
Chapter 16
Solutions to exercises