Quantum matching pursuit: A quantum algorithm for sparse representations

• URL: http://arxiv.org/abs/2208.04145v1
• Date: Mon, 8 Aug 2022 13:50:57 GMT
• Title: Quantum matching pursuit: A quantum algorithm for sparse representations
• Authors: Armando Bellante and Stefano Zanero
• Abstract summary: Representing signals with sparse vectors has a wide range of applications that range from image and video coding to shape representation and health monitoring. Quantum computing has recently shown promising speed-ups in many representation learning tasks.
• Score: 3.4376560669160394
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Representing signals with sparse vectors has a wide range of applications that range from image and video coding to shape representation and health monitoring. In many applications with real-time requirements, or that deal with high-dimensional signals, the computational complexity of the encoder that finds the sparse representation plays an important role. Quantum computing has recently shown promising speed-ups in many representation learning tasks. In this work, we propose a quantum version of the well-known matching pursuit algorithm. Assuming the availability of a fault-tolerant quantum random access memory, our quantum matching pursuit lowers the complexity of its classical counterpart of a polynomial factor, at the cost of some error in the computation of the inner products, enabling the computation of sparse representation of high-dimensional signals. Besides proving the computational complexity of our new algorithm, we provide numerical experiments that show that its error is negligible in practice. This work opens the path to further research on quantum algorithms for finding sparse representations, showing suitable quantum computing applications in signal processing.

Related papers

• An Efficient Quantum Classifier Based on Hamiltonian Representations [50.467930253994155]
  Quantum machine learning (QML) is a discipline that seeks to transfer the advantages of quantum computing to data-driven tasks. We propose an efficient approach that circumvents the costs associated with data encoding by mapping inputs to a finite set of Pauli strings. We evaluate our approach on text and image classification tasks, against well-established classical and quantum models.
  arXiv  Detail & Related papers  (2025-04-13T11:49:53Z)
• Halving the Cost of Quantum Algorithms with Randomization [0.138120109831448]
  Quantum signal processing (QSP) provides a systematic framework for implementing a transformation of a linear operator. Recent works have developed randomized compiling, a technique that promotes a unitary gate to a quantum channel. Our algorithm implements a probabilistic mixture of randomizeds, strategically chosen so that the average evolution converges to that of a target function, with an error quadratically smaller than that of an equivalent individual.
  arXiv  Detail & Related papers  (2024-09-05T17:56:51Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Tensor Quantum Programming [0.0]
  We develop an algorithm that encodes Matrix Product Operators into quantum circuits with a depth that depends linearly on the number of qubits. It demonstrates effectiveness on up to 50 qubits for several frequently encountered in differential equations, optimization problems, and quantum chemistry.
  arXiv  Detail & Related papers  (2024-03-20T10:44:00Z)
• Quantum Computing and Tensor Networks for Laminate Design: A Novel Approach to Stacking Sequence Retrieval [1.6421520075844793]
  A prime example is the weight optimization of laminated composite materials, which to this day remains a formidable problem. The rapidly developing field of quantum computation may offer novel approaches for addressing these intricate problems.
  arXiv  Detail & Related papers  (2024-02-09T15:01:56Z)
• Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
  The anticipated applications of quantum computers span across science and industry. We present a survey of several potential application areas of quantum algorithms. We outline the challenges and opportunities in each area in an "end-to-end" fashion.
  arXiv  Detail & Related papers  (2023-10-04T17:53:55Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
  arXiv  Detail & Related papers  (2022-12-13T16:04:16Z)
• Quantum communication complexity of linear regression [0.05076419064097732]
  We show that quantum computers have provable and exponential speedups in terms of communication for some fundamental linear algebra problems. We propose an efficient quantum protocol for quantum singular value transformation.
  arXiv  Detail & Related papers  (2022-10-04T13:27:01Z)
• 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)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Optimizing Tensor Network Contraction Using Reinforcement Learning [86.05566365115729]
  We propose a Reinforcement Learning (RL) approach combined with Graph Neural Networks (GNN) to address the contraction ordering problem. The problem is extremely challenging due to the huge search space, the heavy-tailed reward distribution, and the challenging credit assignment. We show how a carefully implemented RL-agent that uses a GNN as the basic policy construct can address these challenges.
  arXiv  Detail & Related papers  (2022-04-18T21:45:13Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59:55Z)

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.