# Quantum Compressive Sensing: Mathematical Machinery, Quantum Algorithms, and Quantum Circuitry
## 5 Projection
### Decomposition  
We begin with the following decomposition for the sensing matrix \(A\):  
\[A=U\Delta L^{\dagger}\Pi R, \tag{9}\]  
where \(A=U\Delta V^{\dagger}\) is the singular-value decomposition (SVD) of \(A\), and \(V^{\dagger}=L^{\dagger}\Pi R\) is decomposed using a method originally developed for quantum simulation of fermionic systems [31]. Here, \(L\) is another \(m\times m\) unitary matrix, \(\Pi\) is the \(m\times n\) projection operator \(\Pi\equiv\begin{bmatrix}I_{m}&0\end{bmatrix}\) representing measurement of the first three qubits, and, most critically, \(R\) is an \(n\times n\) unitary matrix constructed as a series of Givens rotations, which are easily adapted into a quantum circuit that can be applied to \(n\) qubits. The factors \(U\), \(\Delta\) and \(L\) are classically invertible, permitting us to define a \"syndrome\" s as:  
\[s\equiv L\Delta^{-1}U^{\dagger}x=\Pi Ry. \tag{10}\]  
Figure 5: A quantum circuit to perform Quantum Compressive Sensing with the Decomposition protocol. The input state \(|\Psi\rangle\) is a trained quantum state such as the one prepared by the circuit in Figure 3. Each quantum gate \(\theta_{i}\) represents a Givens rotation, as implemented in the cirq Python package. Meters represent measurement, both within and at the end of the circuit.  
Figure 6: A quantum circuit to perform Quantum Compressive Sensing with the Rodeo algorithm. The input state \(|\Psi\rangle\) is a trained quantum state such as the one prepared by the circuit in Figure 3. The quantum gate \(H\) is the Hadamard gate. The quantum gate \(R_{z}(\theta)\) is defined as \(\exp\left(-i\frac{\theta}{2}\hat{Z}\right)\), where \(\hat{Z}\) is the Pauli \(Z\) operator. The quantum gate \(P(\theta)\) is the phase gate, identical to \(R_{z}\) except by a global phase such that the \(|0\rangle\) component is unchanged. Meters at the end of the circuit represent measurement.  
We cannot invert the singular matrix \(\Pi\)--this stems from the fact that there are many different \(y\) which generate the same syndrome. However, the information contained in our trained Born machine \(|\Psi\rangle\) is able to discriminate between them. We apply the operator \(R\) as a quantum circuit which effectively rotates the computational basis of \(|\Psi\rangle\) so that measuring the first three qubits yields a syndrome basis element \(|s\rangle\). We repeat this procedure until \(s\) and \(|s\rangle\) match, at which point we rotate _back_ into the original basis by applying \(R^{\dagger}\). Finally, we measure all \(n\) qubits to obtain a probabilistic estimate for \(y\). Figure 5 shows the circuit required to execute this protocol.  
Practically speaking, this protocol is suitable only for a restricted class of sensing matrices, in which \(R\) is a generalized permutation matrix. To see this heuristically, consider the case where the correct image can be reconstructed deterministically _without_ any classical measurements (i.e., \(\gamma\) contains only a single binary image such that \(|\Psi\rangle=|y\rangle\), a computational basis state). A well-formed projection protocol should retain this determinism, implying that the projected state \(R|\Psi\rangle\) should be a factorized state \(|s\rangle\otimes|\psi\rangle\), with a fixed syndrome \(|s\rangle\). This is true for any \(|\Psi\rangle=|y\rangle\) only when \(R\) is a generalized permutation matrix. As a consequence, the only suitable sensing matrices \(A\) are those which have non-zero entries in only \(m\) columns (i.e., \(A\) must have \(n-m\) empty columns). In contrast to the original work in [PERSON] et al. (2017), which implicitly considers only sensing matrices measuring individual pixels, this is still a meaningful generalization. However, applying this protocol to fully arbitrary sensing matrices, including those used in the random sensing protocol of [PERSON] et al. (2019), will produce useful results only to the extent that the rotation \(R\) can be approximated by a generalized permutation matrix.