Boosting and Adiabatic Quantum Computing

Hartmut Neven, Vasil S. Denchev, Geordie Rose +1 more

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.

Ray LaPierre

Bernard Zygelman

Hartmut Neven, Vasil S. Denchev, Geordie Rose +1 more

This paper describes how to make the problem of binary classification amenable to quantum computing. A formulation is employed in which the binary classifier is constructed as a thresholded linear superposition of a set of weak classifiers. The weights in the superposition are optimized in a learning process that strives to minimize the training error as well as the number of weak classifiers used. No efficient solution to this problem is known. To bring it into a format that allows the application of adiabatic quantum computing (AQC), we first show that the bit-precision with which the weights need to be represented only grows logarithmically with the ratio of the number of training examples to the number of weak classifiers. This allows to effectively formulate the training process as a binary optimization problem. Solving it with heuristic solvers such as tabu search, we find that the resulting classifier outperforms a widely used state-of-the-art method, AdaBoost, on a variety of benchmark problems. Moreover, we discovered the interesting fact that bit-constrained learning machines often exhibit lower generalization error rates. Changing the loss function that measures the training error from 0-1 loss to least squares maps the training to quadratic unconstrained binary optimization. This corresponds to the format required by D-Wave's implementation of AQC. Simulations with heuristic solvers again yield results better than those obtained with boosting approaches. Since the resulting quadratic binary program is NP-hard, additional gains can be expected from applying the actual quantum processor.

Mikuláš Matoušek, Katarzyna Pernal, Fabijan Pavošević +1 more

High Resolution Image Download MS PowerPoint Slide In this work, we integrate the variational quantum eigensolver (VQE) with the adiabatic connection (AC) method for efficient simulations of chemical problems on near-term quantum computers. Orbital-optimized VQE methods are employed to capture the strong correlation within an active space, and classical AC corrections recover the dynamical correlation effects comprising electrons outside of the active space. On two challenging strongly correlated problems, namely, the dissociation of N 2 and the electronic structure of the tetramethyleneethane biradical, we show that the combined VQE-AC approach enhances the performance of VQE dramatically. Moreover, since the AC corrections do not bring any additional requirements on quantum resources or measurements, they can actually boost the VQE algorithms. Our work paves the way toward quantum simulations of real-life problems on near-term quantum computers.

Ray LaPierre