# Quantum Compressive Sensing: Mathematical Machinery, Quantum Algorithms, and Quantum Circuitry
## 1 Introduction
This particular approach allows for said problem to be solved by a _linear programming_ solver and can account for measurements corrupted by noise [14; 15; 16; 17; 18]. [PERSON] et al. [19] propose an engineering solution to implement random measurement for compressive sensing, using a single-pixel camera in conjunction with a micro-array of mirrors which can be randomly configured to redirect light into or away from the camera. Each measurement is the total intensity of light corresponding to a different configuration of the mirrors; it is thus equivalent to the integration over a random selection of pixels in a typical CCD image. This mode of compressive sensing has been realized in LIDAR geomaging [20], which will be further discussed in our work. In addition to LIDAR geomaging, compressive sensing has garnered an impressive reputation in the practical world with applications including underwater imaging [21] and microwave imaging [22], as well as communication networks such as wireless sensor networks [23; 24], handling of big data for IoT [25], information security [26; 27], and much more. The _quantum_ approach to compressive sensing adopts a somewhat different strategy. In TNCS [7], [PERSON] and [PERSON] share a tensor network representing a Born machine trained on the set of \(n\)-bit messages [PERSON] is inclined to send. [PERSON] identifies her message, which is analogous to the signal \(y\) in compressive sensing. She then selects a subset of \(m\) bits to send to [PERSON], either randomly or targeting those bits which yield the most information in the tensor network. This step is most analogous to the measurement step in compressive sensing. Finally, [PERSON] reconstructs the full message with the help of the tensor network. We will describe this part of the algorithm in more detail in Section 2. We find the relation of TNCS to compressive sensing very attractive, with the potential to be expanded upon. In particular, the TNCS measurement step has two major differences from traditional compressive sensing. First, [PERSON] performs the measurement with full knowledge of the original signal; this makes it more akin to a compression algorithm rather than a _sensing_ algorithm. Second, the measurement selects \(m\) bits of an \(n\)-bit message, restricting the sensing matrix to one that is constructed only from standard basis vectors. In this paper, we adapt TNCS from a quantum-inspired tensor network communication protocol to a fully-quantum sensing protocol, considering especially the context of LIDAR geomaging. Let [PERSON] herself take the role of [PERSON], transmitting to our detector whatever sculpture of life and earth she is inclined to create. We offer a novel, gradient-free training procedure which can train a Born machine on, for example, known patterns in geological structure, or on previously obtained LIDAR images. We also demonstrate how arbitrary sensing matrices, such as those consistent with a single-pixel camera, may be translated into the TNCS formalism. Moreover, while both [PERSON] et al. and [PERSON] et al. suggest the _possibility_ of a quantum implementation of their algorithms, we propose several specific quantum protocols to implement our algorithm on a set of entangled qubits, permitting a much more powerful representation of highly correlated data.