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

• URL: http://arxiv.org/abs/2405.20525v1
• Date: Thu, 30 May 2024 22:56:15 GMT
• Title: Comparing Quantum Annealing and Spiking Neuromorphic Computing for Sampling Binary Sparse Coding QUBO Problems
• Authors: Kyle Henke, Elijah Pelofske, Garrett Kenyon, Georg Hahn,
• Abstract summary: Given an image and an overcomplete, non-orthonormal basis, we aim to find a sparse binary vector indicating the minimal set of vectors that when added together best reconstruct the given input. This yields a quadratic binary optimization problem (QUBO), whose optimal solution(s) in general is NP-hard to find. Next, we solve the sparse representation QUBO by implementing it both on a D-Wave annealer with Pegasus chip connectivity via minor embedding, as well as on the Intel Loihi 2 spiking neuromorphic processor.
• Score: 2.249916681499244
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 binary optimization problem (QUBO), whose optimal solution(s) in general is NP-hard to find. The method of unsupervised and unnormalized dictionary feature learning for a desired sparsity level to best match the data is presented. Next, we solve the sparse representation QUBO by implementing it 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. On the quantum annealer, we sample from the sparse representation QUBO using parallel quantum annealing combined with quantum evolution Monte Carlo, also known as iterated reverse annealing. On Loihi 2, we use a stochastic winner take all network of neurons. 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. 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.

Related papers

• Slow Mixing of Quantum Gibbs Samplers [47.373245682678515]
  We present a quantum generalization of these tools through a generic bottleneck lemma. This lemma focuses on quantum measures of distance, analogous to the classical Hamming distance but rooted in uniquely quantum principles. Even with sublinear barriers, we use Feynman-Kac techniques to lift classical to quantum ones establishing tight lower bound $T_mathrmmix = 2Omega(nalpha)$.
  arXiv  Detail & Related papers  (2024-11-06T22:51:27Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• A Novel Normalized-Cut Solver with Nearest Neighbor Hierarchical Initialization [107.07093621337084]
  Normalized-Cut (N-Cut) is a famous model of spectral clustering. Traditional N-Cut solvers are two-stage: 1) calculating the continuous spectral embedding of normalized Laplacian matrix; 2) discretization via $K$-means or spectral rotation. We propose a novel N-Cut solver based on the famous coordinate descent method.
  arXiv  Detail & Related papers  (2023-11-26T07:11:58Z)
• Sampling binary sparse coding QUBO models using a spiking neuromorphic processor [3.0586855806896045]
  We consider the problem of computing a binary representation of an image. We aim to find a binary vector minimal set of basis that when added together best reconstruct the given input. This yields a so-called Quadratic Unconstrained Binary (QUBO) problem.
  arXiv  Detail & Related papers  (2023-06-02T22:47:18Z)
• A Quadratic Speedup in the Optimization of Noisy Quantum Optical Circuits [5.074606924176912]
  Linear optical quantum circuits with photon number resolving (PNR) detectors are used for both Gaussian Boson Sampling (GBS) and for the preparation of non-Gaussian states such as Gottesman-Kitaev-Preskill (GKP) We introduce a family of algorithms that calculate detection probabilities, conditional states and their gradients with respect to circuit parametrizations. These algorithms are implemented and ready to use in the open-source photonic optimization library MrMustard.
  arXiv  Detail & Related papers  (2023-03-15T18:51:36Z)
• Quantum Sparse Coding [5.130440339897477]
  We develop a quantum-inspired algorithm for sparse coding. The emergence of quantum computers and Ising machines can potentially lead to more accurate estimations. We conduct numerical experiments with simulated data on Lightr's quantum-inspired digital platform.
  arXiv  Detail & Related papers  (2022-09-08T13:00:30Z)
• An entanglement perspective on the quantum approximate optimization algorithm [0.0]
  We study the entanglement growth and spread resulting from randomized and optimized QAOA circuits. We also investigate the entanglement spectrum in connection with random matrix theory.
  arXiv  Detail & Related papers  (2022-06-14T17:37:44Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)
• Continuous black-box optimization with quantum annealing and random subspace coding [2.839269856680851]
  A black-box optimization algorithm such as Bayesian optimization finds extremum of an unknown function by alternating inference of the underlying function and optimization of an acquisition function. In a high-dimensional space, such algorithms perform poorly due to the difficulty of acquisition function optimization. We apply quantum annealing to overcome the difficulty in the continuous black-box optimization.
  arXiv  Detail & Related papers  (2021-04-30T06:19:07Z)
• Sampling electronic structure QUBOs with Ocean and Mukai solvers [44.62475518267084]
  The most advanced D-Wave Advantage quantum annealer has 5000+ qubits, however, every qubit is connected to a small number of neighbors. To compensate for the reduced number of qubits, one has to rely on special software such as qbsolv. We find that the Mukai QUBO solver outperforms the Ocean qbsolv for all calculations done in the present work.
  arXiv  Detail & Related papers  (2021-02-01T23:16:42Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.