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
- 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) - Taming Quantum Time Complexity [50.10645865330582]
We show how to achieve both exactness and thriftiness in the setting of time complexity.
We employ a novel approach to the design of quantum algorithms based on what we call transducers.
arXiv Detail & Related papers (2023-11-27T14:45:19Z) - 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) - A quantum Fourier transform (QFT) based note detection algorithm [0.0]
In quantum information processing, the quantum transform (QFT) has a plethora of applications.
We create a quantum music note detection algorithm both on a simulated and a real quantum computer.
arXiv Detail & Related papers (2022-04-25T16:45:56Z) - 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.