Quantum Machine Learning: What Quantum Computing Means to Data Mining
Machine learning has become indispensable in discovering patterns in large data sets, and the theory is at the core of a larger set of tools known as data mining. It is a mature field with an astonishing array of practical applications.
Quantum computing has the potential of taking machine learning to the next level. While hardware implementations of quantum computing systems are still in an initial phase, recent theoretical developments hint at the benefits of applying quantum methods to learning algorithms.
Computational complexity can be reduced exponentially in some cases, whereas we see quadratic reduction in others. Yet, improved learning time is just one part of the equation. Through nonconvex objective functions, quantum machine learning algorithms are more robust to noise and outliers, which makes their generalization performance better than many known classical algorithms. Examples include quantum support vector machines, learning a function by quantum process tomography, quantum neural networks, and adiabatic quantum optimization.
Quantum Machine Learning: What Quantum Computing Means to Data Mining explains the most relevant concepts of machine learning, quantum mechanics, and quantum information theory, and contrasts classical learning algorithms to their quantum counterparts.
The book is available at Elsevier Store, at Amazon, and also at Barnes and Noble. Elsevier Store gives a 25 % discount with the promotional code PRT2514.
Table of Contents
Part I: Fundamental Concepts
1.1 Learning Theory and Data Mining
1.2 Why Quantum Computers
1.3 A Heterogeneous Model
1.4 An Overview of Quantum Machine Learning
1.5 Quantum-Like Learning on Classical Computers
2 Machine Learning
2.1 Data-Driven Models
2.2 Feature Space
2.3 Supervised and Unsupervised Learning
2.4 Generalization Performance
2.5 Model Complexity
2.7 Data Dependencies and Computational Complexity
3 Quantum Mechanics
3.1 States and Superposition
3.2 Density Matrix Representation and Mixed States
3.3 Composite Systems and Entanglement
3.6 Uncertainty Relations
3.8 Adiabatic Theorem
3.9 No-Cloning Theorem
4 Quantum Computing
4.1 Qubits and the Bloch Sphere
4.2 Quantum Circuits
4.3 Adiabatic Quantum Computing
4.4 Quantum Parallelism
4.5 Grover's Algorithm
4.6 Complexity Classes
4.7 Quantum Information Theory
Part II: Classical Learning Algorithms
5 Unsupervised Learning
5.1 Principal Component Analysis
5.2 Manifold Embedding
5.3 K-Means and K-Medians Clustering
5.4 Hierarchical Clustering
5.5 Density-Based Clustering
6 Pattern Recognition and Neural Networks
6.1 The Perceptron
6.2 Hopfield Networks
6.3 Feedforward Networks
6.4 Deep Learning
6.5 Computational Complexity
7 Supervised Learning and Support Vector Machines
7.1 K-Nearest Neighbors
7.2 Optimal Margin Classifiers
7.3 Soft Margins
7.4 Nonlinearity and Kernel Functions
7.5 Least-Squares Formulation
7.6 Generalization Performance
7.7 Multiclass Problems
7.8 Loss Functions
7.9 Computational Complexity
8 Regression Analysis
8.1 Linear Least-Squares
8.2 Nonlinear Regression
8.3 Nonparametric Regression
8.4 Computational Complexity
9.1 Weak Classifiers
9.3 A Family of Convex Boosters
9.4 Nonconvex Loss Functions
Part III: Quantum Computing and Machine Learning
10 Clustering Structure and Quantum Computing
10.1 Quantum Random Access Memory
10.2 Calculating Dot Products
10.3 Quantum Principal Component Analysis
10.4 Towards Quantum Manifold Embedding
10.5 Quantum K-Means
10.6 Quantum K-Medians
10.7 Quantum Hierarchical Clustering
10.8 Computational Complexity
11 Quantum Pattern Recognition
11.1 Quantum Associative Memory
11.2 The Quantum Perceptron
11.3 Quantum Neural Networks
11.4 Physical Realizations
11.5 Computational Complexity
12 Quantum Classification
12.1 Nearest Neighbors
12.2 Support Vector Machines with Grover's Search
12.3 Support Vector Machines with Exponential Speedup
12.4 Computational Complexity
13 Quantum Process Tomography
13.1 Channel-State Duality
13.2 Quantum Process Tomography
13.3 Groups, Compact Lie Groups, and the Unitary Group
13.4 Representation Theory
13.5 Parallel Application and Storage of Unitary
13.6 Optimal State for Learning
13.7 Applying the Unitary
14 Boosting and Adiabatic Quantum Computing
14.1 Quantum Annealing
14.2 Quadratic Unconstrained Binary Optimization
14.3 Ising Model
14.6 Sparsity and Generalization Performance
14.7 Mapping to Hardware
14.8 Computational Complexity
Y. Abu-Mostafa and J. St.Jacques, "Information capacity of the Hopfield model," IEEE Transactions on Information Theory, vol. 31, iss. 4, pp. 461-464, 1985.
A. Acín, E. Jané, and G. Vidal, "Optimal estimation of quantum dynamics," Physical Review A, vol. 64, p. 50302, 2001.
D. Aerts and M. Czachor, "Quantum aspects of semantic analysis and symbolic artificial intelligence," Journal of Physics A: Mathematical and General, vol. 37, p. L123--L132, 2004.
D. Aharonov, W. Van Dam, J. Kempe, Z. Landau, S. Lloyd, and O. Regev, "Adiabatic quantum computation is equivalent to standard quantum computation," in Proceedings of FOCS-04, 45th Annual IEEE Symposium on Foundations of Computer Science, 2004.
M. V. Altaisky, "Quantum neural network," arXiv:quant-ph/0107012, 2001.
J. B. Altepeter, D. Branning, E. Jeffrey, T. Wei, P. G. Kwiat, R. T. Thew, J. L. O'Brien, M. A. Nielsen, and A. G. White, "Ancilla-assisted quantum process tomography," Physical Review Letters, vol. 90, iss. 19, p. 193601, 2003.
M. H. S. Amin and V. Choi, "First-order quantum phase transition in adiabatic quantum computation," Physical Review A, vol. 80, p. 62326, 2009.
M. H. S. Amin, C. J. S. Truncik, and D. V. Averin, "Role of single-qubit decoherence time in adiabatic quantum computation," Physical Review A, vol. 80, p. 22303, 2009.
D. Angluin, "Queries and concept learning," Machine Learning, vol. 2, iss. 4, pp. 319-342, 1988.
D. Anguita, S. Ridella, F. Rivieccio, and R. Zunino, "Quantum optimization for training support vector machines," Neural Networks, vol. 16, iss. 5, pp. 763-770, 2003.
M. Ankerst, M. M. Breunig, H. P. Kriegel, and J. Sander, "OPTICS: Ordering Points To Identify the Clustering Structure," in Proceedings of SIGMOD-99, International Conference on Management of Data, 1999, pp. 49-60.
K. Asanovic, R. Bodik, B. C. Catanzaro, J. J. Gebis, P. Husbands, K. Keutzer, D. A. Patterson, W. L. Plishker, J. Shalf, and S. W. Williams, "The landscape of parallel computing research: A view from Berkeley," University of California at Berkeley 2006.
A. Aspect, J. Dalibard, and G. Roger, "Experimental Test of Bell's Inequalities Using Time- Varying Analyzers," Physical Review Letters, vol. 49, pp. 1804-1807, 1982.
A. Atici and R. A. Servedio, "Improved Bounds on Quantum Learning Algorithms," Quantum Information Processing, vol. 4, iss. 5, pp. 355-386, 2005.
E. Aïmeur, G. Brassard, and S. Gambs, "Quantum speed-up for unsupervised learning," Machine Learning, vol. 90, iss. 2, pp. 261-287, 2013.
D. Bacon and W. van Dam, "Recent Progress in Quantum Algorithms," Communinactions of the ACM, vol. 53, iss. 2, pp. 84-93, 2010.
N. Beckmann, H. P. Kriegel, R. Schneider, and B. Seeger, "The R*-tree: an efficient and robust access method for points and rectangles," SIGMOD Record, vol. 19, iss. 2, pp. 322-331, 1990.
E. C. Behrman, J. Niemel, J. E. Steck, and S. R. Skinner, "A quantum dot neural network," in Proceedings of PhysComp-96, 4th Workshop on Physics of Computation, 1996, pp. 22-28.
E. C. Behrman, L. Nash, J. E. Steck, V. Chandrashekar, and S. R. Skinner, "Simulations of quantum neural networks," Information Sciences, vol. 128, iss. 3, pp. 257-269, 2000.
J. S. Bell, "On the Einstein Podolsky Rosen Paradox," Physics, vol. 195--200, iss. 3, p. 1, 1964.
Y. Bengio and Y. LeCun, "Scaling learning algorithms towards AI," in Large-Scale Kernel Machines, L. Bottou, O. Chapelle, D. DeCoste, and J. Weston, Eds., MIT Press, 2007, pp. 321-360.
C. Bennett, E. Bernstein, G. Brassard, and U. Vazirani, "Strengths and Weaknesses of Quantum Computing," SIAM Journal on Computing, vol. 26, iss. 5, pp. 1510-1523, 1997.
S. Berchtold, D. A. Keim, and H. Kriegel, "The X-tree : An Index Structure for High-Dimensional Data," in Proceedings of VLDB-96, 22th International Conference on Very Large Data Bases, 1996, pp. 28-39.
D. W. Berry, G. Ahokas, R. Cleve, and B. C. Sanders, "Efficient quantum algorithms for simulating sparse Hamiltonians," Communications in Mathematical Physics, vol. 270, iss. 2, pp. 359-371, 2007.
A. Bisio, G. M. D'Ariano, P. Perinotti, and M. Sedlák, "Quantum learning algorithms for quantum measurements," Physics Letters A, vol. 375, pp. 3425-3434, 2011.
A. Bisio, G. Chiribella, G. M. D'Ariano, S. Facchini, and P. Perinotti, "Optimal quantum learning of a unitary transformation," Physical Review A, vol. 81, iss. 3, p. 32324, 2010.
K. Blekas and I. E. Lagaris, "Newtonian clustering: An approach based on molecular dynamics and global optimization," Pattern Recognition, vol. 40, iss. 6, pp. 1734-1744, 2007.
A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth, "Learnability and the Vapnik-Chervonenkis dimension," Journal of the ACM, vol. 36, iss. 4, pp. 929-965, 1989.
S. Boixo, T. F. Rønnow, S. V. Isakov, Z. Wang, D. Wecker, D. A. Lidar, J. M. Martinis, and M. Troyer, "Evidence for quantum annealing with more than one hundred qubits," Nature Physics, vol. 10, iss. 3, pp. 218-224, 2014.
S. Boixo, T. Albash, F. M. Spedalieri, N. Chancellor, and D. A. Lidar, "Experimental signature of programmable quantum annealing," Nature Communications, vol. 4, iss. 2067, 2013.
R. Bonner and R. Freivalds, "A Survey of Quantum Learning," in Proceedings of QCL-02, 3rd International Workshop on Quantum Computation and Learning, 2002.
M. Born and V. Fock, "Beweis des Adiabatensatzes," Zeitschrift für Physik, vol. 51, iss. 3-4, pp. 165-180, 1928.
P. S. Bradley and U. M. Fayyad, "Refining Initial Points for K-Means Clustering," in Procedings of ICML-98, 15th International Conference on Machine Learning, 1998, pp. 91-99.
G. Brassard, R. Cleve, and A. Tapp, "Cost of Exactly Simulating Quantum Entanglement with Classical Communication," Physical Review Letters, vol. 83, pp. 1874-1877, 1999.
L. Breiman, "Random Forests," Machine Learning, vol. 45, iss. 1, pp. 5-32, 2001.
L. Breiman, "Bagging Predictors," Machine Learning, vol. 24, iss. 2, pp. 123-140, 1996.
S. Brin and L. Page, "The anatomy of a large-scale hypertextual Web search engine," Computer Networks and ISDN Systems, vol. 30, iss. 1-7, pp. 107-117, 1998.
P. D. Bruza and R. J. Cole, "Quantum logic of semantic space: An exploratory investigation of context effects in practical reasoning," in We Will Show Them: Essays in Honour of Dov Gabbay, S. Artemov, H. Barringer, A. S. d'Avila Garcez, L. C. Lamb, and J. Woods, Eds., College Publications, 2005.
N. H. Bshouty and J. C. Jackson, "Learning DNF over the Uniform Distribution Using a Quantum Example Oracle," in Proceedings of COLT-95, 8th Annual Conference on Computational Learning Theory, 1995, pp. 118-127.
H. Buhrman, R. Cleve, J. Watrous, and R. De Wolf, "Quantum fingerprinting," Physical Review Letters, vol. 87, iss. 16, p. 167902, 2001.
C. J. C. Burges, "A Tutorial on Support Vector Machines for Pattern Recognition," Data Mining and Knowledge Discovery, vol. 2, iss. 2, pp. 121-167, 1998.
A. Chatterjee, S. Bhowmick, and P. Raghavan, "FAST: Force-directed Approximate Subspace Transformation to Improve Unsupervised Document Classification," in Proceedings of 6th Text Mining Workshop held in conjunction with SIAM International Conference on Data Mining, 2008.
A. M. Childs, E. Farhi, and J. Preskill, "Robustness of adiabatic quantum computation," Physical Review A, vol. 65, p. 12322, 2001.
G. Chiribella, "Group theoretic structures in the estimation of an unknown unitary transformation," Journal of Physics: Conference Series, vol. 284, iss. 1, p. 12001, 2011.
G. Chiribella, G. M. D’ariano, and M. F. Sacchi, "Optimal estimation of group transformations using entanglement," Physical Review A, vol. 72, iss. 4, p. 42338, 2005.
M. Choi, "Completely positive linear maps on complex matrices," Linear Algebra and its Applications, vol. 10, iss. 3, pp. 285-290, 1975.
I. L. Chuang and M. A. Nielsen, "Prescription for experimental determination of the dynamics of a quantum black box," Journal of Modern Optics, vol. 44, iss. 11--12, pp. 2455-2467, 1997.
P. Ciaccia, M. Patella, and P. Zezula, "M-tree: An efficient access method for similarity search in metric spaces," in Proceedings of VLDB-97, 23rd International Conference on Very Large Data Bases, 1997, pp. 426-435.
J. F. Clauser, M. A. Horne, A. Shimony, and R. A. Holt, "Proposed Experiment to Test Local Hidden-Variable Theories," Physical Review Letters, vol. 23, pp. 880-884, 1969.
W. W. Cohen and Y. Singer, "Context-Sensitive Learning Methods for Text Categorization," in Proceedings of SIGIR-96, 19th International Conference on Research and Development in Information Retrieval, 1996, pp. 307-315.
C. Cohen-Tannoudji, B. Diu, and F. Laloë, Quantum Mechanics, John Wiley & Sons, 1996.
R. Collobert, F. Sinz, J. Weston, and L. Bottou, "Trading convexity for scalability," in Proceedings of ICML-06, 23rd International Conference on Machine learning, 2006, pp. 201-208.
J. B. Copas, "Regression, prediction and shrinkage," Journal of the Royal Statistical Society. Series B (Methodological), pp. 311-354, 1983.
D. R. Cox, Principles of Statistical Inference, Cambridge University Press, 2006.
T. F. Cox and M. A. A. Cox, Multidimensional Scaling, Chapman and Hall, 1994.
N. Cristianini and J. Shawe-Taylor, An Introduction to Support Vector Machines and Other Kernel-based Learning Methods, Cambridge University Press, 2000.
X. Cui, J. Gao, and T. E. Potok, "A flocking based algorithm for document clustering analysis," Journal of Systems Architecture, vol. 52, iss. 8, pp. 505-515, 2006.
G. M. D'Ariano and P. Lo Presti, "Imprinting Complete Information about a Quantum Channel on its Output State," Physical Review Letters, vol. 91, p. 47902, 2003.
V. De Silva and J. B. Tenenbaum, "Global versus local methods in nonlinear dimensionality reduction," Advances in Neural Information Processing Systems, vol. 15, pp. 721-728, 2003.
S. Deerwester, S. T. Dumais, G. W. Furnas, T. K. Landauer, and R. Harshman, "Indexing by latent semantic analysis," Journal of the American Society for Information Science, vol. 41, iss. 6, pp. 391-407, 1990.
A. Demiriz, K. P. Bennett, and J. Shawe-Taylor, "Linear programming boosting via column generation," Machine Learning, vol. 46, iss. 1-3, pp. 225-254, 2002.
V. S. Denchev, N. Ding, S. V. N. Vishwanathan, and H. Neven, "Robust Classification with Adiabatic Quantum Optimization," in Proceedings of ICML-2012, 29th International Conference on Machine Learning, 2012.
D. Deutsch, "Quantum theory, the Church--Turing principle and the universal quantum computer," Proceedings of the Royal Society A, vol. 400, iss. 1818, pp. 97-117, 1985.
T. G. Dietterich, "An Experimental Comparison of Three Methods for Constructing Ensembles of Decision Trees: Bagging, Boosting, and Randomization," Machine Learning, vol. 40, iss. 2, pp. 139-157, 2000.
C. Ding and X. He, "K-means Clustering via Principal Component Analysis," in Proceedings of ICML-04, 21st International Conference on Machine Learning, 2004, pp. 29-37.
D. Dong, C. Chen, H. Li, and T. Tarn, "Quantum reinforcement learning," IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, vol. 38, iss. 5, pp. 1207-1220, 2008.
H. Drucker, C. J. Burges, L. Kaufman, A. Smola, and V. Vapnik, "Support vector regression machines," Advances in Neural Information Processing Systems, vol. 10, pp. 155-161, 1997.
L. Duan and G. Guo, "Probabilistic Cloning and Identification of Linearly Independent Quantum States," Physical Review Letters, vol. 80, pp. 4999-5002, 1998.
N. Duffy and D. Helmbold, "Potential Boosters?," Advances in Neural Information Processing Systems, vol. 13, pp. 258-264, 2000.
C. Durr and P. Hoyer, "A Quantum Algorithm for Finding the Minimum," arXiv:quant-ph/9607014, 1996.
B. Efron, "Bootstrap methods: another look at the jackknife," The Annals of Statistics, pp. 1-26, 1979.
R. El-Yaniv and D. Pechyony, "Transductive Rademacher Complexity and Its Applications," in Proceedings of COLT-07, 20th Annual Conference on Learning Theory, 2007, pp. 157-171.
D. Erhan, Y. Bengio, A. Courville, P. Manzagol, P. Vincent, and S. Bengio, "Why does unsupervised pre-training help deep learning?," Journal of Machine Learning Research, vol. 11, pp. 625-660, 2010.
S. Ertekin, L. Bottou, and L. C. Giles, "Nonconvex online support vector machines," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 33, iss. 2, pp. 368-381, 2011.
M. Ester, H. P. Kriegel, J. Sander, and X. Xu, "A density-based algorithm for discovering clusters in large spatial databases with noise," in Proceedings of SIGKDD-96, 2nd International Conference on Knowledge Discovery and Data Mining, 1996, pp. 226-231.
A. A. Ezhov and D. Ventura, "Quantum Neural Networks," in Future Directions for Intelligent Systems and Information Sciences, N. Kasabov, Ed., Physica-Verlag HD, 2000, vol. 45, pp. 213-235.
E. Farhi, J. Goldston, D. Gosset, S. Gutmann, H. B. Meyer, and P. Shor, "Quantum Adiabatic Algorithms, Small Gaps, and Different Paths," Quantum Information & Computation, vol. 11, iss. 3, pp. 181-214, 2011.
E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, "Quantum computation by adiabatic evolution," arXiv:quant-ph/0001106, 2000.
M. Fayngold and V. Fayngold, Quantum Mechanics and Quantum Information, Wiley-VCH, 2013.
V. Feldman, V. Guruswami, P. Raghavendra, and Y. Wu, "Agnostic Learning of Monomials by Halfspaces Is Hard," SIAM Journal on Computing, vol. 41, iss. 6, pp. 1558-1590, 2012.
R. P. Feynman, "Simulating physics with computers," International Journal of Theoretical Physics, vol. 21, iss. 6, pp. 467-488, 1982.
A. B. Finnila, M. A. Gomez, C. Sebenik, C. Stenson, and J. D. Doll, "Quantum annealing: A new method for minimizing multidimensional functions," Chemical Physics Letters, vol. 219, iss. 5--6, pp. 343-348, 1994.
Y. Freund and R. E. Schapire, "A decision-theoretic generalization of on-line learning and an application to boosting," Journal of Computer and System Sciences, vol. 55, iss. 1, pp. 119-139, 1997.
J. H. Friedman, "Greedy Function Approximation: Gradient Boosting Machine," Annals of Statistics, vol. 29, iss. 5, pp. 1189-1232, 2001.
J. Friedman, T. Hastie, and R. Tibshirani, "Additive logistic regression: A statistical view of boosting," Annals of Statistics, vol. 28, iss. 2, pp. 337-407, 2000.
C. A. Fuchs, "Quantum mechanics as quantum information (and only a little more)," arXiv:quant-ph/0205039, 2002.
S. Gambs, "Quantum classification," arXiv:0809.0444, 2008.
A. Gammerman, V. Vovk, and V. Vapnik, "Learning by transduction," in Proceedings of UAI-98, 14th Conference on Uncertainty in Artificial Intelligence, 1998, pp. 148-155.
E. Gardner, "The space of interactions in neural network models," Journal of Physics A: Mathematical and General, vol. 21, iss. 1, p. 257, 1988.
S. Garnerone, P. Zanardi, and D. A. Lidar, "Adiabatic quantum algorithm for search engine ranking," Physical Review Letters, vol. 108, iss. 23, p. 230506, 2012.
D. Gavinsky, "Quantum Predictive Learning and Communication Complexity with Single Input," Quantum Information & Computation, vol. 12, iss. 7--8, pp. 575-588, 2012.
V. Giovannetti, S. Lloyd, and L. Maccone, "Quantum random access memory," Physical Review Letters, vol. 100, iss. 16, p. 160501, 2008.
F. Glover, "Tabu search---part I," ORSA Journal on Computing, vol. 1, iss. 3, pp. 190-206, 1989.
D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley Professional, 1989.
L. K. Grover, "A Fast Quantum Mechanical Algorithm for Database Search," in Proceedings of STOC0-96, 28th Annual ACM Symposium on Theory of Computing, 1996, pp. 212-219.
S. Gupta and R. K. P. Zia, "Quantum Neural Networks," Journal of Computer and System Sciences, vol. 63, iss. 3, pp. 355-383, 2001.
M. Guta and W. Kotłowski, "Quantum learning: asymptotically optimal classification of qubit states," New Journal of Physics, vol. 12, iss. 12, p. 123032, 2010.
I. Guyon, A. Elisseefi, and L. P. Kaelbling, "An Introduction to Variable and Feature Selection," Journal of Machine Learning Research, vol. 3, iss. 7-8, pp. 1157-1182, 2003.
J. Han, M. Kamber, and J. Pei, Data Mining: Concepts and Techniques, 3rd ed., Morgan Kaufmann, 2012.
A. W. Harrow, A. Hassidim, and S. Lloyd, "Quantum algorithm for linear systems of equations," Physical Review Letters, vol. 103, iss. 15, p. 150502, 2009.
T. Hastie, R. Tibshirani, and J. Friedman, The Elements of Statistical Learning: Data Mining, Inference, and Prediction, 2nd ed., Springer, 2008.
D. Haussler, "Decision theoretic generalizations of the PAC model for neural net and other learning applications," Information and Computation, vol. 100, iss. 1, pp. 78-150, 1992.
C. Hegde, M. B. Wakin, and R. G. Baraniuk, "Random projections for manifold learning," Advances in Neural Information Processing Systems, vol. 20, pp. 641-648, 2007.
G. Hinton, L. Deng, D. Yu, G. E. Dahl, A. Mohamed, N. Jaitly, A. Senior, V. Vanhoucke, P. Nguyen, T. N. Sainath, and others, "Deep neural networks for acoustic modeling in speech recognition: The shared views of four research groups," IEEE Signal Processing Magazine, vol. 29, iss. 6, pp. 82-97, 2012.
A. Holevo, Probabilistic and Statistical Aspects of Quantum Theory, North-Holland Publishing Company, 1982.
R. C. Holte, "Very Simple Classification Rules Perform Well on Most Commonly Used Datasets," Machine Learning, vol. 11, iss. 1, pp. 63-90, 1993.
J. J. Hopfield, "Neural networks and physical systems with emergent collective computational abilities," Proceedings of the National Academy of Sciences, vol. 79, iss. 8, pp. 2554-2558, 1982.
K. Hornik, M. Stinchcombe, and H. White, "Multilayer Feedforward Networks Are Universal Approximators," Neural Networks, vol. 2, iss. 5, pp. 359-366, 1989.
M. Horodecki, P. Horodecki, and R. Horodecki, "Separability of mixed states: necessary and sufficient conditions," Physics Letters A, vol. 223, iss. 1, pp. 1-8, 1996.
C. W. Hsu and C. J. Lin, "A comparison of methods for multiclass support vector machines," IEEE Transactions on Neural Networks, vol. 13, iss. 2, pp. 415-425, 2002.
G. Huang, Q. Zhu, and C. Siew, "Extreme learning machine: Theory and applications," Neurocomputing, vol. 70, iss. 1--3, pp. 489-501, 2006.
G. Huang, "Learning capability and storage capacity of two-hidden-layer feedforward networks," IEEE Transactions on Neural Networks, vol. 14, iss. 2, pp. 274-281, 2003.
G. Huang and H. A. Babri, "Upper bounds on the number of hidden neurons in feedforward networks with arbitrary bounded nonlinear activation functions," IEEE Transactions on Neural Networks, vol. 9, iss. 1, pp. 224-229, 1998.
W. K. Härdle, Applied Nonparametric Regression, Cambridge University Press, 1990.
W. Iba and P. Langley, "Induction of one-level decision trees," in Proceedings of ML-92, 9th International Workshop on Machine Learning, 1992, pp. 233-240.
M. Ito, T. Miyoshi, and H. Masuyama, "The characteristics of the torus Self Organizing Map," Faji Shisutemu Shinpojiumu Koen Ronbunshu, vol. 16, pp. 373-374, 2000.
A. Jamiołkowski, "Linear transformations which preserve trace and positive semidefiniteness of operators," Reports on Mathematical Physics, vol. 3, iss. 4, pp. 275-278, 1972.
T. Joachims, "Training linear SVMs in linear time," in Proceedings of SIGKDD-06, 12th International Conference on Knowledge Discovery and Data Mining, 2006, pp. 217-226.
T. Joachims, "Text categorization with Support Vector Machines: Learning with many relevant features," in Proceedings of ECML-98, 10th European Conference on Machine Learning, 1998, pp. 137-142.
M. Johnson, M. Amin, S. Gildert, T. Lanting, F. Hamze, N. Dickson, R. Harris, A. Berkley, J. Johansson, P. Bunyk, and others, "Quantum annealing with manufactured spins," Nature, vol. 473, iss. 7346, pp. 194-198, 2011.
I. T. Jolliffe, Principal Component Analysis, Springer, 1989.
K. Katayama and H. Narihisa, "Performance of simulated annealing-based heuristic for the unconstrained binary quadratic programming problem," European Journal of Operational Research, vol. 134, iss. 1, pp. 103-119, 2001.
V. M. Kendon, K. Nemoto, and W. J. Munro, "Quantum analogue computing," Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, vol. 368, iss. 1924, pp. 3609-3620, 2010.
J. Kennedy and R. Eberhart, "Particle Swarm Optimization," in Proceedings of ICNN-95, International Conference on Neural Networks, 1995, pp. 1942-1948.
A. Y. Khrennikov, Ubiquitous Quantum Structure: From Psychology to Finance, Springer Verlag, 2010.
K. Kitto, "Why quantum theory?," in Proceedings of QI-08, 2nd International Symposium on Quantum Interaction, 2008, pp. 11-18.
R. Kohavi and G. H. John, "Wrappers for feature subset selection," Artificial Intelligence, vol. 97, iss. 1-2, pp. 273-324, 1997.
R. I. Kondor and J. Lafferty, "Diffusion kernels on graphs and other discrete input spaces," in Proceedings of ICML-02, 19th International Conference on Machine Learning, 2002, pp. 315-322.
B. Kraus, "Topics in Quantum Information," in Lecture Notes of the 44th IFF Spring School ``Quantum Information Processing", 2013.
H. Kriegel, P. Kröger, J. Sander, and A. Zimek, "Density-based clustering," Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, vol. 1, iss. 3, pp. 231-240, 2011.
W. Kruskal, "Miracles and statistics: the casual assumption of independence," Journal of the American Statistical Association, vol. 83, iss. 404, pp. 929-940, 1988.
L. I. Kuncheva and C. J. Whitaker, "Measures of Diversity in Classifier Ensembles and Their Relationship with the Ensemble Accuracy," Machine Learning, vol. 51, iss. 2, pp. 181-207, 2003.
P. J. M. Laarhoven and E. H. L. Aarts, Simulated Annealing: Theory and Applications, Reidel Publishing Company, 1987.
M. Lan, C. L. Tan, J. Su, and Y. Lu, "Supervised and traditional term weighting methods for automatic text categorization," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 31, iss. 4, pp. 721-735, 2009.
P. Langley and S. Sage, "Oblivious decision trees and abstract cases," in Working Notes of the AAAI-94 Workshop on Case-Based Reasoning, 1994, pp. 113-117.
P. Langley and S. Sage, "Induction of selective Bayesian classifiers," in Proceedings of UAI-94, 10th Conference on Uncertainty in Artificial Intelligence, 1994, pp. 399-406.
A. N. Langville and C. D. Meyer, Google's PageRank and Beyond: The Science of Search Engine Rankings, Princeton University Press, 2006.
T. Lanting, A. J. Przybysz, Y. A. Smirnov, F. M. Spedalieri, M. H. Amin, A. J. Berkley, R. Harris, F. Altomare, S. Boixo, P. Bunyk, N. Dickson, C. Enderud, J. P. Hilton, E. Hoskinson, M. W. Johnson, E. Ladizinsky, N. Ladizinsky, R. Neufeld, T. Oh, I. Perminov, C. Rich, M. C. Thom, E. Tolkacheva, S. Uchaikin, A. B. Wilson, and G. Rose, "Entanglement in a quantum annealing processor," arXiv:1401.3500, 2014.
L. S. Larkey and W. B. Croft, "Combining classifiers in text categorization," in Proceedings of SIGIR-96, 19th International Conference on Research and Development in Information Retrieval, 1996, pp. 289-297.
M. H. C. Law, N. Zhang, and A. K. Jain, "Nonlinear Manifold Learning for Data Stream," in Proceedings of ICDM-04, 4th IEEE International Conference on Data Mining, 2004, pp. 33-44.
M. H. C. Law and A. K. Jain, "Incremental nonlinear dimensionality reduction by manifold learning," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 28, iss. 3, pp. 377-391, 2006.
D. W. Leung, "Choi's proof as a recipe for quantum process tomography," Journal of Mathematical Physics, vol. 44, p. 528, 2003.
M. Lewenstein, "Quantum perceptrons," Journal of Modern Optics, vol. 41, iss. 12, pp. 2491-2501, 1994.
D. D. Lewis and M. Ringuette, "A comparison of two learning algorithms for text categorization," in Proceedings of SDAIR-94, 3rd Annual Symposium on Document Analysis and Information Retrieval, 1994, pp. 81-93.
D. A. Lidar, A. T. Rezakhani, and A. Hamma, "Adiabatic approximation with exponential accuracy for many-body systems and quantum computation," Journal of Mathematical Physics, vol. 50, p. 102106, 2009.
H. T. Lin and C. J. Lin, "A Study on Sigmoid Kernels for SVM and the Training of non-PSD Kernels by SMO-type Methods," Department of Computer Science, National Taiwan University 2003.
T. Lin and H. Zha, "Riemannian manifold learning," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 30, iss. 5, p. 796, 2008.
S. Lloyd, M. Mohseni, and P. Rebentrost, "Quantum principal component analysis," arXiv:1307.0401, 2013.
S. Lloyd, "Universal Quantum Simulators," Science, vol. 273, iss. 5278, pp. 1073-1078, 1996.
S. Lloyd, M. Mohseni, and P. Rebentrost, "Quantum algorithms for supervised and unsupervised machine learning," arXiv:1307.0411, 2013.
H. Lodhi, C. Saunders, J. Shawe-Taylor, N. Cristianini, C. Watkins, and B. Scholkopf, "Text Classification using String Kernels," Journal of Machine Learning Research, vol. 2, iss. 3, pp. 419-444, 2002.
P. M. Long and R. A. Servedio, "Random classification noise defeats all convex potential boosters," Machine Learning, vol. 78, iss. 3, pp. 287-304, 2010.
C. K. Loo, M. Peruš, and H. Bischof, "Associative memory based image and object recognition by quantum holography," Open Systems & Information Dynamics, vol. 11, iss. 03, pp. 277-289, 2004.
H. Lu, R. Setiono, and H. Liu, "Effective data mining using neural networks," IEEE Transactions on Knowledge and Data Engineering, vol. 8, iss. 6, pp. 957-961, 1996.
D. J. C. MacKay, Information Theory, Inference & Learning Algorithms, 4th ed., Cambridge University Press, 2005.
A. Manju and M. J. Nigam, "Applications of quantum inspired computational intelligence: A survey," Artificial Intelligence Review, pp. 1-78, 2012.
N. Manwani and P. S. Sastry, "Noise tolerance under risk minimization," IEEE Transactions on Cybernetics, vol. 43, iss. 3, pp. 1146-1151, 2013.
H. Masnadi-Shirazi, V. Mahadevan, and N. Vasconcelos, "On the design of robust classifiers for computer vision," in Proceedings of CVPR-10, IEEE Conference on Computer Vision and Pattern Recognition, 2010, pp. 779-786.
H. Masnadi-Shirazi and N. Vasconcelos, "On the design of loss functions for classification: theory, robustness to outliers, and SavageBoost," Advances in Neural Information Processing Systems, vol. 21, pp. 1049-1056, 2008.
L. Mason, J. Baxter, P. Bartlett, and M. Frean, "Boosting algorithms as gradient descent in function space," Advances in Neural Information Processing Systems, vol. 11, 1999.
C. C. McGeoch and C. Wang, "Experimental Evaluation of an Adiabiatic Quantum System for Combinatorial Optimization," in Proceedings of CF-13, ACM International Conference on Computing Frontiers, 2013, p. 23:1--23:11.
M. Minsky and S. Papert, Perceptrons: An Introduction to Computational Geometry, MIT Press, 1969.
L. Mirsky, "Symmetric gage functions and unitarily invariant norms," The Quarterly Journal of Mathematics, vol. 11, pp. 50-59, 1960.
N. Mishra, D. Oblinger, and L. Pitt, "Sublinear Time Approximate Clustering," in Proceedings of SODA-01, 12th Annual ACM-SIAM Symposium on Discrete Algorithms, 2001, pp. 439-447.
T. M. Mitchell, Machine Learning, McGraw-Hill, 1997.
M. Mohseni, A. T. Rezakhani, and D. A. Lidar, "Quantum-process tomography: Resource analysis of different strategies," Physical Review A, vol. 77, p. 32322, 2008.
A. Narayanan and T. Menneer, "Quantum artificial neural network architectures and components," Information Sciences, vol. 128, iss. 3–4, pp. 231-255, 2000.
R. Neigovzen, J. L. Neves, R. Sollacher, and S. J. Glaser, "Quantum pattern recognition with liquid-state nuclear magnetic resonance," Physical Review A, vol. 79, p. 42321, 2009.
H. Neven, V. S. Denchev, G. Rose, and W. G. Macready, "QBoost: Large Scale Classifier Training with Adiabatic Quantum Optimization," in Proceedings of ACML-12, 4th Asian Conference on Machine Learning, 2012, pp. 333-348.
H. Neven, V. S. Denchev, M. Drew-Brook, J. Zhang, W. G. Macready, and G. Rose, "Binary classification using hardware implementation of quantum annealing," in Demonstrations at NIPS-09, 24th Annual Conference on Neural Information Processing Systems, 2009, pp. 1-17.
H. Neven, V. S. Denchev, G. Rose, and W. G. Macready, "Training a binary classifier with the quantum adiabatic algorithm," arXiv:0811.0416, 2008.
V. Onclinx, V. Wertz, and M. Verleysen, "Nonlinear data projection on non-Euclidean manifolds with controlled trade-off between trustworthiness and continuity," Neurocomputing, vol. 72, iss. 7-9, pp. 1444-1454, 2009.
J. Oppenheim and S. Wehner, "The uncertainty principle determines the nonlocality of quantum mechanics," Science, vol. 330, iss. 6007, pp. 1072-1074, 2010.
P. Orlik and H. Terao, Arrangements of Hyperplanes, Springer, 1992.
P. Orponen, "Computational Complexity of Neural Networks: A Survey," Nordic Journal of Computing, vol. 1, iss. 1, pp. 94-110, 1994.
G. Palubeckis, "Multistart Tabu Search Strategies for the Unconstrained Binary Quadratic Optimization Problem," Annals of Operations Research, vol. 131, iss. 1-4, pp. 259-282, 2004.
H. Park and C. Jun, "A Simple and Fast Algorithm for K-medoids Clustering," Expert Systems with Applications, vol. 36, iss. 2, pp. 3336-3341, 2009.
J. C. Platt, "Fast training of support vector machines using sequential minimal optimization," in Advances in Kernel Methods: Support Vector Learning, B. Schölkopf, C. J. C. Burges, and A. J. Smola, Eds., MIT Press, 1999, pp. 185-208.
R. Polikar, "Ensemble based systems in decision making," IEEE Circuits and Systems Magazine, vol. 6, iss. 3, pp. 21-45, 2006.
E. M. Pothos and J. R. Busemeyer, "Can quantum probability provide a new direction for cognitive modeling?," Behavioral and Brain Sciences, vol. 36, pp. 255-274, 2013.
G. Purushothaman and N. B. Karayiannis, "Quantum neural networks (QNNs): Inherently fuzzy feedforward neural networks," IEEE Transactions on Neural Networks, vol. 8, iss. 3, pp. 679-693, 1997.
R. Raina, A. Madhavan, and A. Y. Ng, "Large-scale deep unsupervised learning using graphics processors," in Proceedings of ICML-09, 26th Annual International Conference on Machine Learning, 2009.
P. Rebentrost, M. Mohseni, and S. Lloyd, "Quantum support vector machine for big feature and big data classification," arXiv:1307.0471, 2013.
J. Roland and N. J. Cerf, "Quantum search by local adiabatic evolution," Physical Review A, vol. 65, p. 42308, 2002.
F. Rosenblatt, "The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain," Psychological Review, vol. 65, iss. 6, pp. 386-408, 1958.
D. E. Rumelhart, G. E. Hinton, and R. J. Williams, Learning Internal Representations by Error Propagation, MIT Press, 1986.
D. E. Rumelhart, B. Widrow, and M. A. Lehr, "The basic ideas in neural networks," Communications of the ACM, vol. 37, iss. 3, pp. 87-92, 1994.
G. Rätsch, T. Onoda, and K. -R. Müller, "Soft Margins for AdaBoost," Machine Learning, vol. 42, iss. 3, pp. 287-320, 2001.
T. F. Rønnow, Z. Wang, J. Job, S. Boixo, S. V. Isakov, D. Wecker, J. M. Martinis, D. A. Lidar, and M. Troyer, "Defining and detecting quantum speedup," arXiv:1401.2910, 2014.
M. Sasaki and A. Carlini, "Quantum learning and universal quantum matching machine," Phyisical Review A, vol. 66, p. 22303, 2002.
M. Sasaki, A. Carlini, and R. Jozsa, "Quantum template matching," Physical Review A, vol. 64, iss. 2, p. 22317, 2001.
I. Sato, K. Kurihara, S. Tanaka, H. Nakagawa, and S. Miyashita, "Quantum Annealing for Variational Bayes Inference," in Proceedings of UAI-09, 25th Conference on Uncertainty in Artificial Intelligence, 2009, pp. 479-486.
V. Scarani, "Feats, features and failures of the PR-box," AIP Conference Proceedings, vol. 884, pp. 309-320, 2006.
G. Schaller, S. Mostame, and R. Schützhold, "General error estimate for adiabatic quantum computing," Physical Review A, vol. 73, p. 62307, 2006.
R. E. Schapire, "The strength of weak learnability," Machine Learning, vol. 5, iss. 2, pp. 197-227, 1990.
B. Schölkopf and A. J. Smola, Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond, MIT Press, 2001.
F. Sebastiani, "Machine learning in automated text categorization," ACM Computing Surveys, vol. 34, iss. 1, pp. 1-47, 2002.
G. Sentís, J. Calsamiglia, R. Muñoz-Tapia, and E. Bagan, "Quantum learning without quantum memory," Scientific Reports, vol. 2, 2012.
R. A. Servedio and S. J. Gortler, "Quantum versus classical learnability," in Proceedings of CCC-01, 16th Annual IEEE Conference on Computational Complexity, 2001, pp. 138-148.
R. A. Servedio and S. J. Gortler, "Equivalences and separations between quantum and classical learnability," SIAM Journal on Computing, vol. 33, iss. 5, pp. 1067-1092, 2004.
B. Settles, "Active Learning Literature Survey," University of Wisconsin--Madison, 1648, 2009.
S. Shalev-Shwartz, O. Shamir, and K. Sridharan, "Learning Kernel-Based Halfspaces with the Zero-One Loss," in Proceedings of COLT-10, 23rd Annual Conference on Learning Theory, 2010, pp. 441-450.
J. Shawe-Taylor and N. Cristianini, Kernel Methods for Pattern Analysis, Cambridge University Press, 2004.
S. W. Shin, G. Smith, J. A. Smolin, and U. Vazirani, "How ``Quantum" is the D-Wave Machine?," arXiv:1401.7087, 2014.
P. W. Shor, "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer," SIAM Journal on Computing, vol. 26, p. 1484, 1997.
J. Silva, J. Marques, and J. Lemos, "Selecting landmark points for sparse manifold learning," Advances in Neural Information Processing Systems, vol. 18, pp. 1241-1247, 2006.
A. J. Smola, B. Schölkopf, and K. R. Müller, "The connection between regularization operators and support vector kernels," Neural Networks, vol. 11, iss. 4, pp. 637-649, 1998.
M. Steinbach, G. Karypis, and V. Kumar, "A comparison of document clustering techniques," in KDD Workshop on Text Mining, 2000.
I. Steinwart, "Sparseness of support vector machines," Journal of Machine Learning Research, vol. 4, pp. 1071-1105, 2003.
G. Stempfel and L. Ralaivola, "Learning SVMs from Sloppily Labeled Data," in Proceedings of ICANN-09, 19th International Conference on Artificial Neural Networks, 2009, pp. 884-893.
J. Sun, B. Feng, and W. Xu, "Particle swarm optimization with particles having quantum behavior," in Proceedings of CEC-04, Congress on Evolutionary Computation, 2004, pp. 325-331.
J. A. Suykens and J. Vandewalle, "Least squares support vector machine classifiers," Neural Processing Letters, vol. 9, iss. 3, pp. 293-300, 1999.
K. Sörensen, "Metaheuristics -- the metaphor exposed," International Transactions in Operational Research, 2013.
J. B. Tenenbaum, V. Silva, and J. C. Langford, "A global geometric framework for nonlinear dimensionality reduction," Science, vol. 290, iss. 5500, pp. 2319-2323, 2000.
C. A. Trugenberger, "Phase Transitions in Quantum Pattern Recognition," Physical Review Letter, vol. 89, p. 277903, 2002.
C. A. Trugenberger, "Probabilistic Quantum Memories," Physical Review Letters, vol. 87, p. 67901, 2001.
L. G. Valiant, "A Theory of the Learnable," Communnications of the ACM, vol. 27, iss. 11, pp. 1134-1142, 1984.
W. Van Dam, M. Mosca, and U. Vazirani, "How powerful is adiabatic quantum computation?," in Proceedings of FOCS-01, 42nd IEEE Symposium on Foundations of Computer Science, 2001, pp. 279-287.
V. Vapnik, The Nature of Statistical Learning Theory, Springer, 1995.
V. N. Vapnik and Y. A. Chervonenkis, "On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities," Theory of Probability and Its Applications, vol. 16, iss. 2, pp. 264-280, 1971.
V. Vapnik, S. Golowich, and A. Smola, "Support vector method for function approximation, regression estimation, and signal processing," Advances in Neural Information Processing Systems, vol. 9, p. 281, 1997.
D. Ventura and T. Martinez, "Quantum associative memory," Information Sciences, vol. 124, iss. 1, pp. 273-296, 2000.
T. Vidick and S. Wehner, "More nonlocality with less entanglement," Physical Review A, vol. 83, iss. 5, p. 52310, 2011.
K. Q. Weinberger, F. Sha, and L. K. Saul, "Learning a kernel matrix for nonlinear dimensionality reduction," in Proceedings of ICML-04, 21st International Conference on Machine learning, 2004, pp. 106-113.
M. Weinstein and D. Horn, "Dynamic quantum clustering: A method for visual exploration of structures in data," Physical Review E, vol. 80, iss. 6, p. 66117, 2009.
J. Weston, S. Mukherjee, O. Chapelle, M. Pontil, T. Poggio, and V. Vapnik, "Feature selection for SVMs," Advances in Neural Information Processing Systems, vol. 13, pp. 668-674, 2000.
N. Wiebe, A. Kapoor, and K. M. Svore, "Quantum Nearest Neighbor Algorithms for Machine Learning," arXiv:1401.2142, 2014.
N. Wiebe, D. Berry, P. Høyer, and B. C. Sanders, "Higher order decompositions of ordered operator exponentials," Journal of Physics A: Mathematical and Theoretical, vol. 43, iss. 6, p. 65203, 2010.
P. Wittek and C. L. Tan, "Compactly Supported Basis Functions as Support Vector Kernels for Classification," Transactions on Pattern Analysis and Machine Intelligence, vol. 33, iss. 10, pp. 2039-2050, 2011.
P. Wittek, "High-Performance Dynamic Quantum Clustering on Graphics Processors," Journal of Computational Physics, vol. 233, pp. 262-271, 2013.
D. H. Wolpert and W. G. Macready, "No free lunch theorems for optimization," IEEE Transactions on Evolutionary Computation, vol. 1, iss. 1, pp. 67-82, 1997.
D. H. Wolpert, "Stacked generalization," Neural Networks, vol. 5, iss. 2, pp. 241-259, 1992.
Y. Yang and X. Liu, "A re-examination of text categorization methods," in Proceedings of SIGIR-99, 22nd International Conference on Research and Development in Information Retrieval, 1999, pp. 42-49.
Y. Yang and C. G. Chute, "An example-based mapping method for text categorization and retrieval," ACM Transactions on Information Systems, vol. 12, iss. 3, pp. 252-277, 1994.
A. P. Young, S. Knysh, and V. N. Smelyanskiy, "First-Order Phase Transition in the Quantum Adiabatic Algorithm," Physical Review Letters, vol. 104, p. 20502, 2010.
H. Yu, J. Yang, and J. Han, "Classifying large data sets using SVMs with hierarchical clusters," in Proceedings of SIGKDD-03, 9th International Conference on Knowledge Discovery and Data Mining, 2003, pp. 306-315.
Y. Yu, F. Qian, and H. Liu, "Quantum clustering-based weighted linear programming support vector regression for multivariable nonlinear problem," Soft Computing, vol. 14, iss. 9, pp. 921-929, 2010.
M. Zak and C. P. Williams, "Quantum Neural Nets," International Journal of Theoretical Physics, vol. 37, iss. 2, pp. 651-684, 1998.
M. J. Zaki and W. Meira Jr., Data Mining and Analysis: Fundamental Concepts and Algorithms, Cambridge University Press, 2013.
L. Zhang, W. Zhou, and L. Jiao, "Wavelet support vector machine," IEEE Transactions on Systems, Man, and Cybernetics, vol. 34, iss. 1, pp. 34-39, 2004.
T. Zhang and B. Yu, "Boosting with early stopping: Convergence and consistency," Annals of Statistics, vol. 33, iss. 4, pp. 1538-1579, 2005.
R. Zhou and Q. Ding, "Quantum Pattern Recognition with Probability of 100%," International Journal of Theoretical Physics, vol. 47, pp. 1278-1285, 2008.