# Quantum Compressive Sensing: Mathematical Machinery, Quantum Algorithms, and Quantum Circuitry
## 1 Introduction  
Recent advances in quantum computing technology have motivated new, \"quantum\" perspectives in machine learning. As a prime example, the classical idea of a \"Boltzmann machine\", which represents the probability distribution of a training set, can be adapted to that of a \"Born machine\", which gives complex-valued amplitudes whose square moduli are that same probability distribution [1]. The Born machine is easily understood as a quantum state that can be realized using qubits on a quantum computer, and correlations in the training set can be realized using entanglement between qubits [1, 2]. Robust and large-scale quantum computing is, however, still a distant technological reality. Tensor-network-based machine learning methods have ascended to a special niche, because they are classically-tractable mathematical structures which nevertheless approximate quantum states (e.g., Born machines) in a well-defined and practical way [3]. The Matrix Product State (MPS) tensor network is a particularly attractive model, as its linear structure accommodates an especially efficient implementation using the Density Matrix Renormalization Group algebra [4]. MPS has a long history in the numerical study of 1D quantum systems, and it is now being applied to the field of machine learning: [PERSON] and [PERSON] [5] proposed a supervised classification algorithm using MPS. [PERSON] et al. [6] extend upon theirmethods to implement an unsupervised generative modeling algorithm. More recently, [PERSON] et al. [7] proposed a communication protocol, christened Tensor Network Compressed Sensing (TNCS), in which [PERSON] sends [PERSON] only a partial message, and [PERSON] recovers the full message with the help of an MPS tensor network. All of these approaches use the language and formalism of quantum Born machines, while restricting implementation to an approximation of a fully quantum state describable with an MPS. The purpose of this work is to provide algorithms for implementing and extending the methodology of these past approaches on bona-fide quantum computers. The \"Compressed Sensing\" in TNCS is the name of a signal processing protocol, also known as _compressive sensing_ or _compressive sampling_. A sensing protocol is one in which an \(n\)-dimensional signal is sampled by \(m\) different measurements. In general, the measurement procedure can be described with an \(m\times n\) \"sensing matrix\" \(A\), such that the measurement vector \(x\in R^{m}\) and signal vector \(y\in R^{n}\) are related by the equation \(x=Ay\). The problem of reproducing the original signal from the set of measurements appears to be equivalent to finding the left inverse \(A^{-1}\), so that \(y=A^{-1}x\); this requires \(m\geq n\) at a _minimum_, and even more measurements may be required to ensure \(A\) is non-singular. However, in _compressive_ sensing, one takes \(m\ll n\). In the classical setting, this is possible only under the assumption that the signal \(y\) is _sparse_, so that it can be reconstructed via a minimization over the weight (i.e., the \(l_{0}\) norm) of all possible signals, constrained so as to be consistent with the measurements taken [8; 9; 10; 11]. Sparsity of a signal is basis-dependent: mathematically, one may always factor the sensing matrix \(A=\Phi\Psi\) such that the transformed signal \(y^{\prime}=\Psi y\) is sparse. Even without _knowing_ the appropriate transformation \(\Psi\), compressive sensing can still be completed successfully as long as \(\Phi\) possesses a certain mathematical property called \"restricted isometry.\" \"Restricted isometry\" essentially requires that the vector \(\Phi y\) has approximately the same norm as the original signal \(y\), for all sparse signals \(y\)[12; 13]. [PERSON] and [PERSON] [11] emphasize that randomly generated matrices do satisfy this requirement with overwhelming probability, both before and after factorization. In fact, one common way to approach the compressive sensing reconstruction problem is through convex optimization.