Comparing Quantum Annealing and Spiking Neuromorphic Computing for Sampling Binary Sparse Coding QUBO Problems

Abstract

We consider the problem of computing a sparse binary representation of an image. To be precise, given an image and an overcomplete, non-orthonormal basis, we aim to find a sparse binary vector indicating the minimal set of basis vectors that when added together best reconstruct the given input. We formulate this problem with an $L_2$ loss on the reconstruction error, and an $L_0$ (or, equivalently, an $L_1$) loss on the binary vector enforcing sparsity. This yields a quadratic unconstrained binary optimization problem (QUBO), whose optimal solution(s) in general is NP-hard to find. The contribution of this work is twofold. First, we solve the sparse representation QUBOs by solving them both on a D-Wave quantum annealer with Pegasus chip connectivity via minor embedding, as well as on the Intel Loihi 2 spiking neuromorphic processor using a stochastic Non-equilibrium Boltzmann Machine (NEBM). Second, we deploy Quantum Evolution Monte Carlo with Reverse Annealing and iterated warm starting on Loihi 2 to evolve the solution quality from the respective machines. The solutions are benchmarked against simulated annealing, a classical heuristic, and the optimal solutions are computed using CPLEX. Iterated reverse quantum annealing performs similarly to simulated annealing, although simulated annealing is always able to sample the optimal solution whereas quantum annealing was not always able to. The Loihi 2 solutions that are sampled are on average more sparse than the solutions from any of the other methods. We demonstrate that both quantum annealing and neuromorphic computing are suitable for binary sparse coding QUBOs, and that Loihi 2 outperforms a D-Wave quantum annealer standard linear-schedule anneal, while iterated reverse quantum annealing performs much better than both unmodified linear-schedule quantum annealing and iterated warm starting on Loihi 2.

References in corpus (26)

• Ising formulations of many NP problems
• Quantum Annealing in the Transverse Ising Model
• Quantum annealing with more than one hundred qubits
• Quantum Annealing and Analog Quantum Computation
• Perspectives of quantum annealing: Methods and implementations
• Mathematical Foundation of Quantum Annealing
• Observation of topological phenomena in a programmable lattice of 1,800 qubits
• Experimental signature of programmable quantum annealing
• Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
• Coherent quantum annealing in a programmable 2000-qubit Ising chain
• Quantum Optimization of Fully-Connected Spin Glasses
• Entanglement in a quantum annealing processor
• Consistency Tests of Classical and Quantum Models for a Quantum Annealer
• Quantum Annealing Correction with Minor Embedding
• Dynamics of reverse annealing for the fully-connected $p$-spin model
• Exact non-equilibrium solutions of the Boltzmann equation under a time-dependent external force
• Simulating the Shastry-Sutherland Ising Model using Quantum Annealing
• Quantum annealing simulation of out-of-equilibrium magnetization in a spin-chain compound
• Mean field analysis of reverse annealing for code-division multiple-access multiuser detection
• Image classification using quantum inference on the D-Wave 2X
• Solving Larger Maximum Clique Problems Using Parallel Quantum Annealing
• Kagome qubit ice
• Breakdown of the weak coupling limit in quantum annealing
• Initial State Encoding via Reverse Quantum Annealing and h-gain Features
• Probing Environmental Spin Polarization with Superconducting Flux Qubits
• Sampling binary sparse coding QUBO models using a spiking neuromorphic processor