Supervised Learning with Quantum Computers

Preface......Page 3
Contents......Page 5
Acronyms......Page 9
1 Introduction......Page 10
1.1.1 Merging Two Disciplines......Page 11
1.1.2 The Rise of Quantum Machine Learning......Page 13
1.1.3 Four Approaches......Page 14
1.1.4 Quantum Computing for Supervised Learning......Page 15
1.2 How Quantum Computers Can Classify Data......Page 16
1.2.1 The Squared-Distance Classifier......Page 17
1.2.2 Interference with the Hadamard Transformation......Page 18
1.2.3 Quantum Squared-Distance Classifier......Page 22
1.2.4 Insights from the Toy Example......Page 25
1.3 Organisation of the Book......Page 26
References......Page 27
2 Machine Learning......Page 29
2.1 Prediction......Page 30
2.1.1 Four Examples for Prediction Tasks......Page 31
2.1.2 Supervised Learning......Page 33
2.2 Models......Page 36
2.2.1 How Data Leads to a Predictive Model......Page 38
2.2.2 Estimating the Quality of a Model......Page 40
2.2.3 Bayesian Learning......Page 42
2.2.4 Kernels and Feature Maps......Page 43
2.3 Training......Page 47
2.3.1 Cost Functions......Page 48
2.3.2 Stochastic Gradient Descent......Page 50
2.4 Methods in Machine Learning......Page 52
2.4.1 Data Fitting......Page 53
2.4.2 Artificial Neural Networks......Page 56
2.4.3 Graphical Models......Page 68
2.4.4 Kernel Methods......Page 72
References......Page 79
3 Quantum Information......Page 82
3.1.1 What Is Quantum Theory?......Page 83
3.1.2 A First Taste......Page 85
3.1.3 The Postulates of Quantum Mechanics......Page 91
3.2.1 What Is Quantum Computing?......Page 98
3.2.2 Bits and Qubits......Page 100
3.2.3 Quantum Gates......Page 104
3.2.4 Quantum Parallelism and Function Evaluation......Page 108
3.3.1 The Deutsch Algorithm......Page 110
3.3.2 The Deutsch-Josza Algorithm......Page 111
3.3.3 Quantum Annealing and Other Computational Models......Page 113
3.4 Strategies of Information Encoding......Page 115
3.4.1 Basis Encoding......Page 116
3.4.2 Amplitude Encoding......Page 117
3.4.3 Qsample Encoding......Page 119
3.4.4 Dynamic Encoding......Page 120
3.5.1 Grover Search......Page 121
3.5.2 Quantum Phase Estimation......Page 124
3.5.3 Matrix Multiplication and Inversion......Page 126
References......Page 130
4.1 Computational Complexity of Learning......Page 133
4.2 Sample Complexity......Page 137
4.2.1 Exact Learning from Membership Queries......Page 139
4.2.2 PAC Learning from Examples......Page 140
4.3 Model Complexity......Page 141
References......Page 143
5 Information Encoding......Page 144
5.1 Basis Encoding......Page 146
5.1.1 Preparing Superpositions of Inputs......Page 147
5.1.2 Computing in Basis Encoding......Page 150
5.1.3 Sampling from a Qubit......Page 151
5.2 Amplitude Encoding......Page 153
5.2.1 State Preparation in Linear Time......Page 155
5.2.2 Qubit-Efficient State Preparation......Page 159
5.3 Qsample Encoding......Page 164
5.3.2 Marginalisation......Page 165
5.3.3 Rejection Sampling......Page 167
5.4 Hamiltonian Encoding......Page 168
5.4.1 Polynomial Time Hamiltonian Simulation......Page 169
5.4.2 Qubit-Efficient Simulation of Hamiltonians......Page 171
5.4.3 Density Matrix Exponentiation......Page 172
References......Page 174
6.1 Linear Models......Page 177
6.1.1 Inner Products with Interference Circuits......Page 178
6.1.2 A Quantum Circuit as a Linear Model......Page 183
6.1.3 Linear Models in Basis Encoding......Page 186
6.1.4 Nonlinear Activations......Page 187
6.2 Kernel Methods......Page 192
6.2.1 Kernels and Feature Maps......Page 193
6.2.2 The Representer Theorem......Page 195
6.2.3 Quantum Kernels......Page 197
6.2.4 Distance-Based Classifiers......Page 200
6.2.5 Density Gram Matrices......Page 205
6.3.1 Qsamples as Probabilistic Models......Page 208
6.3.2 Qsamples with Conditional Independence Relations......Page 209
6.3.3 Qsamples of Mean-Field Approximations......Page 211
References......Page 213
7 Quantum Computing for Training......Page 215
7.1.1 Basic Idea......Page 216
7.1.2 Matrix Inversion for Training......Page 217
7.1.3 Speedups and Further Applications......Page 222
7.2 Search and Amplitude Amplification......Page 223
7.2.1 Finding Closest Neighbours......Page 224
7.2.2 Adapting Grover's Search to Data Superpositions......Page 225
7.2.3 Amplitude Amplification for Perceptron Training......Page 227
7.3 Hybrid Training for Variational Algorithms......Page 228
7.3.1 Variational Algorithms......Page 230
7.3.2 Variational Quantum Machine Learning Algorithms......Page 234
7.3.3 Numerical Optimisation Methods......Page 237
7.3.4 Analytical Gradients of a Variational Classifier......Page 240
7.4 Quantum Adiabatic Machine Learning......Page 242
7.4.1 Quadratic Unconstrained Optimisation......Page 243
7.4.2 Annealing Devices as Samplers......Page 244
7.4.3 Beyond Annealing......Page 246
References......Page 247
8 Learning with Quantum Models......Page 250
8.1 Quantum Extensions of Ising-Type Models......Page 251
8.1.1 The Quantum Ising Model......Page 252
8.1.2 Training Quantum Boltzmann Machines......Page 254
8.1.3 Quantum Hopfield Models......Page 256
8.1.4 Other Probabilistic Models......Page 258
8.2 Variational Classifiers and Neural Networks......Page 259
8.2.1 Gates as Linear Layers......Page 260
8.2.2 Considering the Model Parameter Count......Page 262
8.2.3 Circuits with a Linear Number of Parameters......Page 264
8.3.1 Quantum Walk Models......Page 266
8.3.2 Superposition and Quantum Ensembles......Page 269
8.3.3 QBoost......Page 272
References......Page 274
9 Prospects for Near-Term Quantum ML......Page 276
9.1 Small Versus Big Data......Page 277
9.2 Hybrid Versus Fully Coherent Approaches......Page 279
9.3 Qualitative Versus Quantitative Advantages......Page 280
9.4 What Machine Learning Can Do for Quantum Computing......Page 281
Reference......Page 282
 Index......Page 283