Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE International Conference on Rebooting Computing (ICRC)

Generating Sparse Representations Using Quantum Annealing: Comparison to Classical Algorithms

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

Published Nov 1, 2017• 6 citations
Publisher

Abstract

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.

DOI
10.1109/icrc.2017.8123653

Related papers

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.13215•IEEE International Conference on Rebooting Computing (ICRC)•Nov 1, 2018•30 citations

Comparing deep learning with quantum inference on the D-Wave 2X

Nguyen, Nga Thi Thuy [Los Alamos National Laboratory]; Kenyon, Garrett [Los Alamos National Laboratory]

We used a quantum annealing D-Wave 2X computer to obtain solutions to NP-hard sparse coding problems for inferring representation of reduced dimensional MNIST images.For comparison, we implemented two deep neural network architectures.The first (AlexNet-like) approximately matched the architecture of the sparse coding model.The second was state-of-the-art (RESNET).Classification based on the D-Wave 2X was superior to matching pursuit and AlexNet and nearly equivalent to RESNET.

•Feb 15, 2024•0 citations

Radiographic Inference Based on a Model of V1 Simple Cells Implemented on the D-Wave 2X Quantum Annealing Computer

Nga T. T. Nguyen, Garrett T. Kenyon

Just as the brain must infer 3D structure from 2D retinal images, radiologists are tasked with inferring 3D densities from 2D X-rays. Computer simulations suggest that V1 simple cells use lateral inhibition to generate sparse representations that are selective for 3D depth when presented with 2D stereo images and video. Analogously, we cast radiographic inference as a sparse coding problem employing lateral inhibition between binary neurons, resulting in a quadratic unconstrained binary optimization (QUBO)problem suitable for implementation on a quantum annealing D-Wave 2X (1152-qubit)computer. We generated synthetic radiographs by performing discrete Abel transforms on mathematically-defined objects possessing axial (cylindrical)symmetry and whose radially density profile was given by the sum of a randomly-chosen, sparse set of (nearly binary)Fourier components. We used embedding tools to map the above QUBO problem, which involved dense connections between up to 47 Fourier coefficients, onto the very sparsely connected D-Wave chimera. Using quantum inference, we were able to reconstruct reasonably accurate radial density profiles even after adding sufficiently noise to our synthetic radiographs to make inverse Abel transforms untenable. Compared to state-of-the-art classical QUBO solvers, GUROBI and the Hamze-Freitas-Selby algorithm, the quantum D-Wave 2X was orders of magnitude faster for the same final accuracy. Our results indicate a potential strategy for integrating neuromorphic and quantum computing techniques.

IEEE International Conference on Rebooting Computing (ICRC)•Nov 1, 2018•2 citations

Efficient Combinatorial Optimization Using Quantum Annealing

Hristo N. Djidjev, Guillaume Chapuis, Georg Hahn +1 more

The recent availability of the first commercial quantum computers has provided a promising tool to tackle NP hard problems which can only be solved heuristically with present techniques. However, it is unclear if the current state of quantum computing already provides a quantum advantage over the current state of the art in classical computing. This article assesses the performance of the D-Wave 2X quantum annealer on two NP hard graph problems, in particular clique finding and graph partitioning. For this, we provide formulations as Qubo and Ising Hamiltonians suitable for the quantum annealer and compare a variety of quantum solvers (Sapi, QBSolv, QSage provided by D-Wave Sys, Inc.) to current classical algorithms (METIS, Simulated Annealing, third-party clique finding and graph splitting heuristics) on certain test sets of graphs. We demonstrate that for small graph instances, classical methods still outperform the quantum annealer in terms of computing time, even though the quality of the best solutions obtained is comparable. Nevertheless, due to the limited problem size which can be embedded on the D-Wave 2X chip, the aforementioned finding applies to most of problems of general nature solvable on the quantum annealer. For instances specifically designed to fit the D-Wave 2X architecture, we observe substantial speed-ups in computing time over classical approaches.

arXiv:1801.08653•Jan 26, 2018•27 citations

Solving the sparse QUBO on multiple GPUs for Simulating a Quantum Annealer

Tomohiro Imanaga, Koji Nakano, Ryota Yasudo +6 more

Quadratic Unconstraint Binary Optimization (QUBO) is a combinatorial optimization problem such that an$n\times n$upper triangle matrix$W$is given and the objective is to find an n-bit vector$X$that minimizes the energy value$E(X)=X^{T}WX$. A QUBO instance$W$is sparse if instance$W$has few non-zero elements. The D-Wave 2000$Q$is a quantum annealer that can solve 2048-bit sparse QUBO instances represented as a Chimera graph topology. We present a sparse QUBO solver running on GPUs for 2048-bit sparse QUBO with a Chimera graph topology. We have evaluated the performance of our sparse QUBO solver and the D-Wave 2000Q for solving 2048-bit QUBO instances with various resolutions. The experimental results show that our sparse QUBO solver running on a GPU cloud server with 8 NVIDIA A100 GPUs can find optimal solutions in less than 3ms for all instances while the D-Wave 2000$Q$cannot find them in 996.7ms. Hence, our QUBO solver can find better solutions than the D-Wave 2000Q in less than 1/300 running time. We can think that our QUBO solver is a quantum annealer simulator with better performance in terms of the accuracy of solutions and the running time. Our result implies that quantum annealer D-Wave 2000$Q$does not achieve quantum supremacy yet.

International Symposium on Computing and Networking•Nov 1, 2021•9 citations

Convex Non-negative Matrix Factorization Through Quantum Annealing

Ahmed Zaiou, Basarab Mateï, Younès Bennani +1 more

In this paper we provide the quantum version of the Convex Non-negative Matrix Factorization algorithm (Convex-NMF) by using the D-wave quantum annealer. More precisely, we use D-wave 2000Q to find the low rank approximation of a fixed real-valued matrix$X$by the product of two non-negative matrices factors$W$and$G$such that the Frobenius norm of the difference$X$- XWG is minimized. In order to solve this optimization problem we proceed in two steps. In the first step we transform the global real optimization problem depending on$W, G$into two quadratic unconstrained binary optimization problems (QUBO) depending on$W$and$G$respectively. In the second step we use an alternative strategy between the two QUBO problems corresponding to$W$and$G$to find the global solution. The running of these two QUBO problems on D-wave 2000Q need to use an embedding to the chimera graph of D-wave 2000Q, this embedding is limited by the number of qubits of D-wave 2000Q. We perform a study on the maximum number of real data to be used by our approach on$\mathbf{D}$-wave 2000Q. The proposed study is based on the number of qubits used to represent each real variable. We also tested our approach on D-Wave 2000Q with several randomly generated data sets to prove that our approach is faster than the classical approach and also to prove that it gets the best results.

arXiv:2203.15634•IEEE International Conference on High Performance Computing and Communications; IEEE International Conference on Smart City; IEEE International Conference on Data Science and Systems (HPCC/SmartCity/DSS)•Dec 1, 2021•2 citations
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.
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.
Just as the brain must infer 3D structure from 2D retinal images, radiologists are tasked with inferring 3D densities from 2D X-rays. Computer simulations suggest that V1 simple cells use lateral inhibition to generate sparse representations that are selective for 3D depth when presented with 2D stereo images and video. Analogously, we cast radiographic inference as a sparse coding problem employing lateral inhibition between binary neurons, resulting in a quadratic unconstrained binary optimization (QUBO)problem suitable for implementation on a quantum annealing D-Wave 2X (1152-qubit)computer. We generated synthetic radiographs by performing discrete Abel transforms on mathematically-defined objects possessing axial (cylindrical)symmetry and whose radially density profile was given by the sum of a randomly-chosen, sparse set of (nearly binary)Fourier components. We used embedding tools to map the above QUBO problem, which involved dense connections between up to 47 Fourier coefficients, onto the very sparsely connected D-Wave chimera. Using quantum inference, we were able to reconstruct reasonably accurate radial density profiles even after adding sufficiently noise to our synthetic radiographs to make inverse Abel transforms untenable. Compared to state-of-the-art classical QUBO solvers, GUROBI and the Hamze-Freitas-Selby algorithm, the quantum D-Wave 2X was orders of magnitude faster for the same final accuracy. Our results indicate a potential strategy for integrating neuromorphic and quantum computing techniques.
The recent availability of the first commercial quantum computers has provided a promising tool to tackle NP hard problems which can only be solved heuristically with present techniques. However, it is unclear if the current state of quantum computing already provides a quantum advantage over the current state of the art in classical computing. This article assesses the performance of the D-Wave 2X quantum annealer on two NP hard graph problems, in particular clique finding and graph partitioning. For this, we provide formulations as Qubo and Ising Hamiltonians suitable for the quantum annealer and compare a variety of quantum solvers (Sapi, QBSolv, QSage provided by D-Wave Sys, Inc.) to current classical algorithms (METIS, Simulated Annealing, third-party clique finding and graph splitting heuristics) on certain test sets of graphs. We demonstrate that for small graph instances, classical methods still outperform the quantum annealer in terms of computing time, even though the quality of the best solutions obtained is comparable. Nevertheless, due to the limited problem size which can be embedded on the D-Wave 2X chip, the aforementioned finding applies to most of problems of general nature solvable on the quantum annealer. For instances specifically designed to fit the D-Wave 2X architecture, we observe substantial speed-ups in computing time over classical approaches.
Quadratic Unconstraint Binary Optimization (QUBO) is a combinatorial optimization problem such that ann×nn\times nn×nupper triangle matrixWWWis given and the objective is to find an n-bit vectorXXXthat minimizes the energy valueE(X)=XTWXE(X)=X^{T}WXE(X)=XTWX. A QUBO instanceWWWis sparse if instanceWWWhas few non-zero elements. The D-Wave 2000QQQis a quantum annealer that can solve 2048-bit sparse QUBO instances represented as a Chimera graph topology. We present a sparse QUBO solver running on GPUs for 2048-bit sparse QUBO with a Chimera graph topology. We have evaluated the performance of our sparse QUBO solver and the D-Wave 2000Q for solving 2048-bit QUBO instances with various resolutions. The experimental results show that our sparse QUBO solver running on a GPU cloud server with 8 NVIDIA A100 GPUs can find optimal solutions in less than 3ms for all instances while the D-Wave 2000QQQcannot find them in 996.7ms. Hence, our QUBO solver can find better solutions than the D-Wave 2000Q in less than 1/300 running time. We can think that our QUBO solver is a quantum annealer simulator with better performance in terms of the accuracy of solutions and the running time. Our result implies that quantum annealer D-Wave 2000QQQdoes not achieve quantum supremacy yet.
In this paper we provide the quantum version of the Convex Non-negative Matrix Factorization algorithm (Convex-NMF) by using the D-wave quantum annealer. More precisely, we use D-wave 2000Q to find the low rank approximation of a fixed real-valued matrixXXXby the product of two non-negative matrices factorsWWWandGGGsuch that the Frobenius norm of the differenceXXX- XWG is minimized. In order to solve this optimization problem we proceed in two steps. In the first step we transform the global real optimization problem depending onW,GW, GW,Ginto two quadratic unconstrained binary optimization problems (QUBO) depending onWWWandGGGrespectively. In the second step we use an alternative strategy between the two QUBO problems corresponding toWWWandGGGto find the global solution. The running of these two QUBO problems on D-wave 2000Q need to use an embedding to the chimera graph of D-wave 2000Q, this embedding is limited by the number of qubits of D-wave 2000Q. We perform a study on the maximum number of real data to be used by our approach onD\mathbf{D}D-wave 2000Q. The proposed study is based on the number of qubits used to represent each real variable. We also tested our approach on D-Wave 2000Q with several randomly generated data sets to prove that our approach is faster than the classical approach and also to prove that it gets the best results.