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
