arXiv:1704.01605 · PLoS ONE

Nonnegative/Binary matrix factorization with a D-Wave quantum annealer

Daniel O’Malley, Velimir V. Vesselinov, Boian S. Alexandrov, Ludmil B. Alexandrov

Published Dec 10, 2018• 139 citations

Abstract

D-Wave quantum annealers represent a novel computational architecture and have attracted significant interest. Much of this interest has focused on the quantum behavior of D-Wave machines, and there have been few practical algorithms that use the D-Wave. Machine learning has been identified as an area where quantum annealing may be useful. Here, we show that the D-Wave 2X can be effectively used as part of an unsupervised machine learning method. This method takes a matrix as input and produces two low-rank matrices as output-one containing latent features in the data and another matrix describing how the features can be combined to approximately reproduce the input matrix. Despite the limited number of bits in the D-Wave hardware, this method is capable of handling a large input matrix. The D-Wave only limits the rank of the two output matrices. We apply this method to learn the features from a set of facial images and compare the performance of the D-Wave to two classical tools. This method is able to learn facial features and accurately reproduce the set of facial images. The performance of the D-Wave shows some promise, but has some limitations. It outperforms the two classical codes in a benchmark when only a short amount of computational time is allowed (200-20,000 microseconds), but these results suggest heuristics that would likely outperform the D-Wave in this benchmark.

DOI: 10.1371/journal.pone.0206653

Related papers

Nonnegative/Binary matrix factorization for image classification using quantum annealing

Hinako Asaoka, Kazue Kudo

Classical computing has borne witness to the development of machine learning. The integration of quantum technology into this mix will lead to unimaginable benefits and be regarded as a giant leap forward in mankind's ability to compute. Demonstrating the benefits of this integration now becomes essential. With the advance of quantum computing, several machine-learning techniques have been proposed that use quantum annealing. In this study, we implement a matrix factorization method using quantum annealing for image classification and compare the performance with traditional machine-learning methods. Nonnegative/binary matrix factorization (NBMF) was originally introduced as a generative model, and we propose a multiclass classification model as an application. We extract the features of handwritten digit images using NBMF and apply them to solve the classification problem. Our findings show that when the amount of data, features, and epochs is small, the accuracy of models trained by NBMF is superior to classical machine-learning methods, such as neural networks. Moreover, we found that training models using a quantum annealing solver significantly reduces computation time. Under certain conditions, there is a benefit to using quantum annealing technology with machine learning.

arXiv:2311.01028Scientific ReportsOct 2, 202312 citations

Relaxation-assisted reverse annealing on nonnegative/binary matrix factorization

Renichiro Haba, Masayuki Ohzeki, Kazuyuki Tanaka

Quantum annealing has garnered significant attention as meta-heuristics inspired by quantum physics for combinatorial optimization problems. Among its many applications, nonnegative/binary matrix factorization stands out for its complexity and relevance in unsupervised machine learning. The use of reverse annealing, a derivative procedure of quantum annealing to prioritize the search in a vicinity under a given initial state, helps improve its optimization performance in matrix factorization. This study proposes an improved strategy that integrates reverse annealing with a linear programming relaxation technique. Using relaxed solutions as the initial configuration for reverse annealing, we demonstrate improvements in optimization performance comparable to the exact optimization methods. Our experiments on facial image datasets show that our method provides better convergence than known reverse annealing methods. Furthermore, we investigate the effectiveness of relaxation-based initialization methods on randomized datasets, demonstrating a relationship between the relaxed solution and the optimal solution. This research underscores the potential of combining reverse annealing and classical optimization strategies to enhance optimization performance.

arXiv:2501.02114PLoS ONEJul 3, 20250 citations

A hybrid quantum enabled RBM advantage: convolutional autoencoders for quantum image compression and generative learning

Jennifer Sleeman, John E. Dorband, Milton Halem

Understanding how the D-Wave quantum computer could be used for machine learning problems is of growing interest. Our work explores the feasibility of using the D-Wave as a sampler for a machine learning task. We describe a hybrid method that combines a classical deep neural network autoencoder with a quantum annealing Restricted Boltzmann Machine (RBM) using the D-Wave for image generation. Our method overcomes two key limitations in the 2000-qubit D-Wave processor, namely the limited number of qubits available to accommodate typical problem sizes for fully connected quantum objective functions, and samples that are binary pixel representations. As a consequence of these limitations we are able to show how we achieved nearly a 22-fold compression factor of grayscale 28 x 28 sized images to binary 6 x 6 sized images with a lossy recovery of the original 28 x 28 grayscale images. We further show how generating samples from the D-Wave after training the RBM, resulted in 28 x 28 images that were variations of the original input data distribution, as opposed to recreating the training samples. We evaluated the quality of this method by using a downstream classification method. We formulated a MNIST classification problem using a deep convolutional neural network that used samples from the quantum RBM to train the MNIST classifier and compared the results with a MNIST classifier trained with the original MNIST training data set, as well as a MNIST classifier trained using classical RBM samples. We also explored using a secondary dataset, the MNIST Fashion dataset and demonstrate the first quantum-generated fashion. Our hybrid autoencoder approach indicates advantage for RBM results relative to the use of a current RBM classical computer implementation for image-based machine learning and even more promising results for the next generation D-Wave quantum system. Our method for compression and image mappings is not constrained to RBMs, the autoencoder part of this method could be coupled with other quantum-based algorithms.

arXiv:2001.11946Apr 24, 202026 citations

A Near-Term Quantum Computing Approach for Hard Computational Problems in Space Exploration

Vadim Smelyanskiy, Eleanor Gilbert Rieffel, Sergey Knysh +5 more

In this article, we show how to map a sampling of the hardest artificial intelligence problems in space exploration onto equivalent Ising models that then can be attacked using quantum annealing implemented in D-Wave machine. We overview the existing results as well as propose new Ising model implementations for quantum annealing. We review supervised and unsupervised learning algorithms for classification and clustering with applications to feature identification and anomaly detection. We introduce algorithms for data fusion and image matching for remote sensing applications. We overview planning problems for space exploration mission applications and algorithms for diagnostics and recovery with applications to deep space missions. We describe combinatorial optimization algorithms for task assignment in the context of autonomous unmanned exploration. Finally, we discuss the ways to circumvent the limitation of the Ising mapping using a "blackbox" approach based on ideas from probabilistic computing. In this article we describe the architecture of the D-Wave One machine and report its benchmarks. Results on random ensemble of problems in the range of up to 96 qubits show improved scaling for median core quantum annealing time compared with classical algorithms; whether this scaling persists for larger problem sizes is an open question. We also review previous results of D-Wave One benchmarking studies for solving binary classification problems with a quantum boosting algorithm which is shown to outperform AdaBoost. We review quantum algorithms for structured learning for multi-label classification and introduce a hybrid classical/quantum approach for learning the weights. Results of D-Wave One benchmarking studies for learning structured labels on four different data sets show a better performance compared with an independent Support Vector Machine approach with linear kernel.

arXiv:1204.2821Apr 12, 201254 citations

Image Classification Using Quantum Inference on the D-Wave 2X

Nga T. T. Nguyen, Garrett T. Kenyon

We use a quantum annealing D-Wave 2X computer to obtain solutions to NP-hard sparse coding problems. To reduce the dimensionality of the sparse coding problem to fit on the quantum D-Wave 2X hardware, we passed downsampled MNIST images through a bottleneck autoencoder. To establish a benchmark for classification performance on this reduced dimensional data set, we built two deep convolutional neural networks (DCNNs). The first DCNN used an AlexNet-like architecture and the second a state-of-the-art residual network (RESNET)model, both implemented in TensorFlow. The two DCNNs yielded classification scores of 94.54 ± 0.7% and 98.8 ± 0.1%, respectively. As a control, we showed that both DCNN architectures produced near-state-of-the-art classification performance ( ~ 99%) on the original MNIST images. To obtain a set of optimized features for inferring sparse representations of the reduced dimensional MNIST dataset, we imprinted on a random set of 47 image patches followed by an off-line unsupervised learning algorithm using stochastic gradient descent to optimize for sparse coding. Our single-layer of sparse coding matched the stride and patch size of the first convolutional layer of the AlexNet-like DCNN and contained 47 fully-connected features, 47 being the maximum number of dictionary elements that could be embedded onto the D-Wave 2X hardware. When the sparse representations inferred by the D-Wave 2X were passed to a linear support vector machine, we obtained a classification score of 95.68%. We found that the classification performance supported by quantum inference was maximal at an optimal level of sparsity corresponding to a critical value of the sparsity/reconstruction error trade-off parameter that previous work has associated with a second order phase transition, an observation supported by a free energy analysis of D-Wave energy states. We mimicked a transfer learning protocol by feeding the D-Wave representations into a multilayer perceptron (MLP), yielding 98.48% classification performance. The classification performance supported by a single-layer of quantum inference was superior to that supported by a classical matching pursuit algorithm set to the same level of sparsity. Whereas the classification performance of both DCNNs declined as the number of training examples was reduced, the classification performance supported by quantum inference was insensitive to the number of training examples. We thus conclude that quantum inference supports classification of reduced dimensional MNIST images exceeding that of a size-matched AlexNet-like DCNN and nearly equivalent to a state-of-the-art RESNET DCNN.

arXiv:1905.13215IEEE International Conference on Rebooting Computing (ICRC)Nov 1, 201830 citations

Generating Sparse Representations Using Quantum Annealing: Comparison to Classical Algorithms

Nga T. T. Nguyen, Amy E. Larson, Garrett T. Kenyon

We use a quantum annealing D-Wave 2X (1,152-qubit) computer to generate sparse representations of Canny-filtered, center-cropped 30×30 CIFAR-10 images. Each binary neuron (qubit) represents a feature kernel obtained initially by imprinting on a randomly chosen 5×5 image patch and then adapted via an off-line Hebbian learning protocol using the sparse solutions generated by the D-Wave. When using binary neurons, the energy function is non-convex (multiple local-minima) and finding a global minimum is NP-hard. Quantum annealing provides a strategy for finding sparse representations that correspond to good local minima of a non-convex cost function. To overcome the severe coupling restrictions between physical qubits on the D-Wave Chimera graph, we use embedding tools to achieve approximately all-to-all connectivity across a reduced number of logical qubits. We assess the sparse representations generated by the D-Wave using both the total energy as well as classification accuracy on a subset of the CIFAR-10 database. The D-Wave 2X outperforms two classical state-of-the-art binary solvers, GUROBI and Chimera-inspired algorithm Hamze-Freitas-Selby (HFS). Specifically, the D-Wave 2X yields lower energy sparse solutions within seconds while the largest problems take over 10 hours for both GUROBI and HFS. We obtained cross-validation classification of 31.02% for the first 4K images using 47 features on the quantum D- Wave 2X.

IEEE International Conference on Rebooting Computing (ICRC)Nov 1, 20176 citations