Training a Large Scale Classifier with the Quantum Adiabatic Algorithm

Abstract

In a previous publication we proposed discrete global optimization as a method to train a strong binary classifier constructed as a thresholded sum over weak classifiers. Our motivation was to cast the training of a classifier into a format amenable to solution by the quantum adiabatic algorithm. Applying adiabatic quantum computing (AQC) promises to yield solutions that are superior to those which can be achieved with classical heuristic solvers. Interestingly we found that by using heuristic solvers to obtain approximate solutions we could already gain an advantage over the standard method AdaBoost. In this communication we generalize the baseline method to large scale classifier training. By large scale we mean that either the cardinality of the dictionary of candidate weak classifiers or the number of weak learners used in the strong classifier exceed the number of variables that can be handled effectively in a single global optimization. For such situations we propose an iterative and piecewise approach in which a subset of weak classifiers is selected in each iteration via global optimization. The strong classifier is then constructed by concatenating the subsets of weak classifiers. We show in numerical studies that the generalized method again successfully competes with AdaBoost. We also provide theoretical arguments as to why the proposed optimization method, which does not only minimize the empirical loss but also adds L0-norm regularization, is superior to versions of boosting that only minimize the empirical loss. By conducting a Quantum Monte Carlo simulation we gather evidence that the quantum adiabatic algorithm is able to handle a generic training problem efficiently.

14 pages, 5 figures

References in corpus (5)

• First order phase transition in the Quantum Adiabatic Algorithm
• Size dependence of the minimum excitation gap in the Quantum Adiabatic Algorithm
• First Order Quantum Phase Transition in Adiabatic Quantum Computation
• A more robust boosting algorithm
• Training a Binary Classifier with the Quantum Adiabatic Algorithm

Cited by in corpus (19)

• Adiabatic Quantum Computing
• Simulating chemistry using quantum computers
• Strawberry Fields: A Software Platform for Photonic Quantum Computing
• Adiabatic Quantum Simulation of Quantum Chemistry
• Nonnegative/binary matrix factorization with a D-Wave quantum annealer
• Recent advances for quantum classifiers
• A Near-Term Quantum Computing Approach for Hard Computational Problems in Space Exploration
• Quantum Machine-Learning for Eigenstate Filtration in Two-Dimensional Materials
• Machine learning \& artificial intelligence in the quantum domain
• Model Predictive Control for Finite Input Systems using the D-Wave Quantum Annealer
• Advances in quantum machine learning
• Quantum learning of coherent states
• Robust Classification with Adiabatic Quantum Optimization
• Physical Realization of Measurement Based Quantum Computation
• A Quantum Implementation Model for Artificial Neural Networks
• Quantum annealing with pairs of ${}^2\Sigma$ molecules as qubits
• Recommender systems inspired by the structure of quantum theory
• Quantum computing for pattern classification
• Dealing with ignorance: universal discrimination, learning and quantum correlations