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
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,
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
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,
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,
D. Angluin, "Queries and concept learning," Machine Learning, vol. 2, iss. 4, pp.
D. Anguita, S. Ridella, F. Rivieccio, and R. Zunino, "Quantum
optimization for training support vector machines," Neural Networks, vol. 16, iss. 5, pp.
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.
A. Atici and R. A. Servedio, "Improved Bounds on Quantum Learning
Algorithms," Quantum Information
Processing, vol. 4, iss. 5, pp. 355-386, 2005.
J. E. Avron and A. Elgart, "Adiabatic Theorem without a Gap Condition,"
Communications in Mathematical
Physics, vol. 203, iss. 2, pp. 445-463, 1999.
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.
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.
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,
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,
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.
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.
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.
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.
G. Brassard, R. Cleve, and A. Tapp, "Cost of Exactly Simulating Quantum
Entanglement with Classical Communication," Physical Review Letters, vol. 83, pp.
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.
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.
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.
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,
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,
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
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.
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
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.
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,
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,
L. Duan and G. Guo, "Probabilistic Cloning and Identification of
Linearly Independent Quantum States," Physical Review Letters, vol. 80, pp.
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,"
B. Efron, "Bootstrap methods: another look at the jackknife," The Annals of Statistics, pp. 1-26,
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.
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,
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
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
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.
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
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,
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.
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.
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.
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.
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.
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,
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
S. Lloyd, "Universal Quantum Simulators," Science, vol. 273, iss. 5278, pp.
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,
D. J. C. MacKay, Information Theory,
Inference & Learning Algorithms, 4th ed., Cambridge University
A. Manju and M. J. Nigam, "Applications of quantum inspired
computational intelligence: A survey," Artificial Intelligence Review, pp.
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.
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,
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,
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.
J. Oppenheim and S. Wehner, "The uncertainty principle determines the
nonlocality of quantum mechanics," Science, vol. 330, iss. 6007, pp.
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.
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.
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.
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.
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,
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.
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.
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
J. B. Tenenbaum, V. Silva, and J. C. Langford, "A global geometric
framework for nonlinear dimensionality reduction," Science, vol. 290, iss. 5500, pp.
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.
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.
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.
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.
A. P. Young, S. Knysh, and V. N. Smelyanskiy, "First-Order Phase
Transition in the Quantum Adiabatic Algorithm," Physical Review Letters, vol. 104, p.
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.