We propose a non-convex training objective for robust binary classification of data sets in which label noise is present. The design is guided by the intention of solving the resulting problem by adiabatic quantum optimization. Two requirements are imposed by the engineering constraints of existing quantum hardware: training problems are formulated as quadratic unconstrained binary optimization; and model parameters are represented as binary expansions of low bit-depth. In the present work we validate this approach by using a heuristic classical solver as a stand-in for quantum hardware. Testing on several popular data sets and comparing with a number of existing losses we find substantial advantages in robustness as measured by test error under increasing label noise. Robustness is enabled by the non-convexity of our hardware-compatible loss function, which we name q-loss.
We propose a non-convex training objective for robust binary classification of data sets in which label noise is present. The design is guided by the intention of solving the resulting problem by adiabatic quantum optimization. Two requirements are imposed by the engineering constraints of existing quantum hardware: training problems are formulated as quadratic unconstrained binary optimization; and model parameters are represented as binary expansions of low bit-depth. In the present work we validate this approach by using a heuristic classical solver as a stand-in for quantum hardware. Testing on several popular data sets and comparing with a number of existing losses we find substantial advantages in robustness as measured by test error under increasing label noise. Robustness is enabled by the non-convexity of our hardware-compatible loss function, which we name q-loss.
We study the problem of supervised binary classification from the perspective of deploying adiabatic quantum optimization in training. A vast body of prior academic work consisting of both theoretical and numerical studies has indicated that quantum technology promises to provide computational power that may be fundamentally superior to any classical computing methods. Given the abundance of NP-hard optimization problems that naturally arise in learning, it is clear that machine learning can immensely benefit from such an optimization tool. We describe a series of increasingly complex designs that result in computationally hard training problems of combinatorial nature. In return for accepting classical computational hardness, we retain theoretical properties such as maximal sparsity and robustness to label noise, which are otherwise sacrificed by convex methods for the sake of computational efficiency and sound theoretical footing. In order to be compatible with emerging quantum hardware technology, we formalize the training problem as quadratic unconstrained binary optimization. Our initial investigations focus on a simple training formulation with non-convex regularization that conforms to the architecture of existing quantum hardware and makes frugal use of a limited number of available physical qubits. Next, we extend this baseline formulation to a scalable algorithm, QBoost, which is able to train incrementally large-scale classifiers on data sets of practical interest. Further, we derive another algorithm, TotalQBoost, as a theoretically motivated totally corrective boosting algorithm with cardinality penalization that also makes use of quantum optimization. Both QBoost and TotalQBoost perform explicit cardinality regularization, which is the only known way of achieving maximal sparsity in the trained classifiers. We apply QBoost and TotalQBoost to three different real-world computer vision problems and make use of a quantum processor for solving the sequence of discrete optimization problems generated by one of them. Finally, we study a learning formulation with convex regularization and a non-convex loss function, q-loss, specifically designed for robust supervised learning in the presence of label noise as it occurs in practice. For compatibility with quantum hardware we derive the corresponding quadratic binary problem via variational approximation. For all proposed algorithms we compare results on a variety of popular synthetic and natural data sets against a rich selection of existing rival learning formulations.
Quantum annealing is a heuristic quantum algorithm which exploits quantum resources to minimize an objective function embedded as the energy levels of a programmable physical system. To take advantage of a potential quantum advantage, one needs to be able to map the problem of interest to the native hardware with reasonably low overhead. Because experimental considerations constrain our objective function to take the form of a low degree PUBO (polynomial unconstrained binary optimization), we employ non-convex loss functions which are polynomial functions of the margin. We show that these loss functions are robust to label noise and provide a clear advantage over convex methods. These loss functions may also be useful for classical approaches as they compile to regularized risk expressions which can be evaluated in constant time with respect to the number of training examples.
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.
A major challenge in machine learning is the computational expense of training these models. Model training can be viewed as a form of optimization used to fit a machine learning model to a set of data, which can take up significant amount of time on classical computers. Adiabatic quantum computers have been shown to excel at solving optimization problems, and therefore, we believe, present a promising alternative to improve machine learning training times. In this paper, we present an adiabatic quantum computing approach for training a linear regression model. In order to do this, we formulate the regression problem as a quadratic unconstrained binary optimization (QUBO) problem. We analyze our quantum approach theoretically, test it on the D-Wave adiabatic quantum computer and compare its performance to a classical approach that uses the Scikit-learn library in Python. Our analysis shows that the quantum approach attains up to [Formula: see text] speedup over the classical approach on larger datasets, and performs at par with the classical approach on the regression error metric. The quantum approach used the D-Wave 2000Q adiabatic quantum computer, whereas the classical approach used a desktop workstation with an 8-core Intel i9 processor. As such, the results obtained in this work must be interpreted within the context of the specific hardware and software implementations of these machines.
To witness quantum advantages in practical settings, substantial efforts are required not only at the hardware level but also on theoretical research to reduce the computational cost of a given protocol. Quantum computation has the potential to significantly enhance existing classical machine learning methods, and several quantum algorithms for binary classification based on the kernel method have been proposed. These algorithms rely on estimating an expectation value, which in turn requires an expensive quantum data encoding procedure to be repeated many times. In this work, we calculate explicitly the number of repetition necessary for acquiring a fixed success probability and show that the Hadamard-test and the swap-test circuits achieve the optimal variance in terms of the quantum circuit parameters. The variance, and hence the number of repetition, can be further reduced only via optimization over data-related parameters. We also show that the kernel-based binary classification can be performed with a single-qubit measurement regardless of the number and the dimension of the data. Finally, we show that for a number of relevant noise models the classification can be performed reliably without quantum error correction. Our findings are useful for designing quantum classification experiments under limited resources, which is the common challenge in the noisy intermediate-scale quantum era.
Variational quantum circuits for image classification suffer from barren plateaus, while quantum kernel methods scale quadratically with dataset size. We propose an iterative framework based on Quadratic Unconstrained Binary Optimization (QUBO) for training the classifier head of convolutional neural networks (CNNs) via quantum annealing, entirely avoiding gradient-based circuit optimization. Following the Extreme Learning Machine paradigm, convolutional filters are randomly initialized and frozen, and only the fully connected layer is optimized. At each iteration, a convex quadratic surrogate derived from the feature Gram matrix replaces the non-quadratic cross-entropy loss, yielding an iteration-stable curvature proxy. A per-output decomposition splits the C-class problem into C independent QUBOs, each with (d+1)K binary variables, where d is the feature dimension and K is the bit precision, so that problem size depends on the image resolution and bit precision, not on the number of training samples. We evaluate the method on six image-classification benchmarks (sklearn digits, MNIST, Fashion-MNIST, CIFAR-10, EMNIST, KMNIST). A precision study shows that accuracy improves monotonically with bit resolution, with 10 bits representing a practical minimum for effective optimization; the 15-bit formulation remains within the qubit and coupler limits of current D-Wave Advantage hardware. The 20-bit formulation matches or exceeds classical stochastic gradient descent on MNIST, Fashion-MNIST, and EMNIST, while remaining competitive on CIFAR-10 and KMNIST. All experiments use simulated annealing, establishing a baseline for direct deployment on quantum annealing hardware.