Principles Of Quantum Artificial Intelligence

Principles Of Quantum Artificial Intelligence

by Andreas Miroslaus Wichert

Hardcover

$98.00
View All Available Formats & Editions
Choose Expedited Shipping at checkout for guaranteed delivery by Monday, October 21

Overview

In this book, we introduce quantum computation and its application to AI. We highlight problem solving and knowledge representation framework. Based on information theory, we cover two main principles of quantum computation — Quantum Fourier transform and Grover search. Then, we indicate how these two principles can be applied to problem solving and finally present a general model of a quantum computer that is based on production systems.

Product Details

ISBN-13: 9789814566742
Publisher: World Scientific Publishing Company, Incorporated
Publication date: 10/25/2013
Pages: 276
Product dimensions: 6.00(w) x 9.00(h) x 0.80(d)

Table of Contents

Preface vii

1 Introduction 1

1.1 Artificial Intelligence 1

1.2 Motivation and Goals 2

1.3 Guide to the Reader 4

1.4 Content 4

1.4.1 Classical computation 4

1.4.2 Quantum computation 6

2 Computation 9

2.1 Entscheidungsproblem 9

2.1.1 Cantor's diagonal argument 11

2.1.2 Reductio ad absurdum 11

2.2 Complexity Theory 12

2.2.1 Decision problems 13

2.2.2 P and NP 13

2.3 Church-Turing Thesis 14

2.3.1 Church-Turing-Deutsch principle 15

2.4 Computers 15

2.4.1 Analog computers 15

2.4.2 Digital computers 16

2.4.3 Von Neumann architecture 16

3 Problem Solving 19

3.1 Knowledge Representation 19

3.1.1 Rules 19

3.1.2 Logic-based operators 20

3.1.3 Frames 23

3.1.4 Categorial representation 23

3.1.5 Binary vector representation 24

3.2 Production System 25

3.2.1 Deduction systems 26

3.2.2 Reaction systems 28

3.2.3 Conflict resolution 28

3.2.4 Human problem-solving 29

3.2.5 Example 29

3.3 Sub-Symbolic Models of Problem-Solving 30

3.3.1 Proto logic 31

3.3.2 Binding problem 32

3.3.3 Icons 32

3.3.4 Euclidian geometry of the world 35

4 Information 37

4.1 Information and Thermodynamics 37

4.1.1 Dice model 39

4.1.2 Entropy 40

4.1.3 Maxwell paradox and information 41

4.1.4 Information theory 42

4.2 Hierarchical Structures 47

4.2.1 Example of a taxonomy 49

4.3 Information and Measurement 50

4.3.1 Information measure I 52

4.3.2 Nature of information measure 55

4.3.3 Measurement of angle 55

4.3.4 Information and contour 56

4.4 Information and Memory 57

4.5 Sparse code for Sub-symbols 67

4.5.1 Sparsification based on unary sub-vectors 68

4.6 Deduction Systems and Associative Memory 68

4.6.1 Taxonomic knowledge organization 74

5 Reversible Algorithms 75

5.1 Reversible Computation 75

5.2 Reversible Circuits 76

5.2.1 Boolean gates 76

5.2.2 Reversible Boolean gates 76

5.2.3 Toffoli gate 77

5.2.4 Circuit 78

6 Probability 79

6.1 Kolmogorovs Probabilities 79

6.1.1 Conditional probability 80

6.1.2 Bayes's rule 81

6.1.3 Joint distribution 82

6.1.4 Naïve Bayes and counting 84

6.1.5 Counting and categorization 85

6.1.6 Bayesian networks 86

6.2 Mixed Distribution 90

6.3 Markov Chains 91

7 Introduction to Quantum Physics 95

7.1 Unitary Evolution 95

7.1.1 Schrödinger's cat paradox 96

7.1.2 Interpretations of quantum mechanics 96

7.2 Quantum Mechanics 97

7.2.1 Stochastic Markov evolution and unitary evolution 98

7.3 Hilbert Space 99

7.3.1 Spectral representation* 101

7.4 Quantum Time Evolution 103

7.5 Compound Systems 105

7.6 Von Neumann Entropy 108

7.7 Measurement 109

7.7.1 Observables 110

7.7.2 Measuring a compound system 111

7.7.3 Heisenberg's uncertainty principle* 112

7.8 Randomness 114

7.8.1 Deterministic chaos 114

7.8.2 Kolmogorov complexity 114

7.8.3 Humans and random numbers 116

7.8.4 Randomness in quantum physics 116

8 Computation with Qubits 119

8.1 Computation with one Qubit 119

8.2 Computation with m Qubit 121

8.3 Matrix Representation of Serial and Parallel Operations 123

8.4 Entanglement 125

8.5 Quantum Boolean Circuits 127

8.6 Deutsch Algorithm 130

8.7 Deutsch Jozsa Algorithm 132

8.8 Amplitude Distribution 135

8.8.1 Cloning 136

8.8.2 Teleportation 137

8.9 Geometric Operations 139

9 Periodicity 145

9.1 Fourier Transform 145

9.2 Discrete Fourier Transform 147

9.2.1 Example 149

9.3 Quantum Fourier Transform 150

9.4 FFT 153

9.5 QFT Decomposition 154

9.5.1 QFT quantum circuit* 155

9.6 QFT Properties 159

9.7 The QFT Period Algorithm 161

9.8 Factorization 164

9.8.1 Example 164

9.9 Kitaev's Phase Estimation Algorithm* 168

9.9.1 Order finding 170

9.10 Unitary Transforms 171

10 Search 173

10.1 Search and Quantum Oracle 173

10.2 Lower Bound Ω(n) for Uf-based Search* 175

10.2.1 Lower bound of at 176

10.2.2 Upper bound of at 178

10.2.3 Ω(n) 179

10.3 Grover's Amplification 180

10.3.1 Householder reflection 180

10.3.2 Householder reflection and the mean value 181

10.3.3 Amplification 182

10.3.4 Iterative amplification 184

10.3.5 Number of iterations 191

10.3.6 Quantum counting 192

10.4 Circuit Representation 194

10.5 Speeding up the Traveling Salesman Problem 195

10.6 The Generate-and-Test Method 196

11 Quantum Problem-Solving 199

11.1 Symbols and Quantum Reality 199

11.2 Uninformed Tree Search 200

11.3 Heuristic Search 203

11.3.1 Heuristic functions 205

11.3.2 Invention of heuristic functions 205

11.3.3 Quality of heuristic 207

11.4 Quantum Tree Search 208

11.4.1 Principles of quantum tree search 208

11.4.2 Iterative quantum tree search 210

11.4.3 No constant branching factor 211

11.5 Quantum Production System 212

11.6 Tarrataca's Quantum Production System 213

11.6.1 3-puzzle 213

11.6.2 Extending for any n-puzzle 217

11.6.3 Pure production system 218

11.6.4 Unitary control strategy 219

11.7 A General Model of a Quantum Computer 220

11.7.1 Cognitive architecture 220

11.7.2 Representation 221

12 Quantum Cognition 223

12.1 Quantum Probability 223

12.2 Decision Making 226

12.2.1 Interference 231

12.3 Unpacking Effects 232

12.4 Conclusion 233

13 Related Approaches 235

13.1 Quantum Walk 235

13.1.1 Random walk 235

13.1.2 Quantum insect 235

13.1.3 Quantum walk on a graph 237

13.1.4 Quantum walk on one dimensional lattice 238

13.1.5 Quantum walk and search 239

13.1.6 Quantum walk for formula evaluation 239

13.2 Adiabatic Computation 240

13.2.1 Quantum annealing 241

13.3 Quantum Neural Computation 243

13.4 Epilogue 245

Bibliography 247

Index 259

Customer Reviews

Most Helpful Customer Reviews

See All Customer Reviews