# Quantum Compressive Sensing: Mathematical Machinery, Quantum Algorithms, and Quantum Circuitry
## 6 Demonstration
### Quantum Compressive Sensing
In the Rodeo and Decomposition protocols, the state of \(|\Psi\rangle\) is contingent upon measurements made prior to sampling. Indeed, the state of \(|\Psi\rangle\) is \"correct\" only when the correct syndrome is measured (\(|\mathbf{0}\rangle\) for Rodeo, and \(s\) from Equation (10) for Decomposition). If this syndrome is _not_ measured, the entire trial must be discarded. In Figure 13a, we find the number of failures out of the 1024 trials for each signal \(y\), and we plot the inter-quartile ranges of the distribution of failures counts over all 32 signals. We anticipate the chance of failure to increase with \(m\), since larger \(m\) have more complicated syndromes, which is also observed here. We also observe in Figure 13a that the chance of failure increases with the size of \(\sigma\) used in the Rodeo protocol. Smaller \(\sigma\) mean the random times \(\tau\) are relatively small, inducing relatively little phase shift on the Born machine \(|\Psi\rangle\). As such, phase kickback is more likely to collapse to the smallest value 0. This is beneficial for obtaining the correct syndrome, but it does not \"cast the net\" wide enough, reducing the likelihood to project onto the desired subspace. On the other hand, increasing \(\tau\) to arbitrarily large values may \"cast the net\" so wide that our limited number of trials (32) is insufficient to adequately sample the whole space. Thus, for any fixed number of trials, we can expect an optimal choice of \(\sigma\) which maximizes the increase in median RLL, as observed in Figure 13b. As our last demonstration, we compare the performance of each projection protocol (Decomposition, QITE with \(\sigma=0.5\), Rodeo with \(\sigma=\pi\)) under different classes of sensing  
Figure 13: A comparison of the Rodeo protocol with different choices of \(\sigma\). (**a**) shows the number of syndrome failures out of 1024 attempts, and (**b**) shows the median relative log likelihood for successful attempts. (**a**) also includes failures for the Decomposition protocol, for comparison. We clearly observe in (**a**) that the chance of failure increases with the size of \(\sigma\) used in the Rodeo protocol and can see in (**b**) that we can expect an optimal choice of \(\sigma\) which maximizes the increase in median RLL. matrix. Figure 14a considers the same binary sensing matrices we have used thus far, while Figure 14b considers sparse binary sensing matrices where the probability of each 1 is only 20%. We immediately observe that the Decomposition protocol _lowers_ the accuracy of reconstruction when measurements are introduced. This is anticipated as the considered class of sensing matrices does not satisfy the requirement that \(A\) is non-zero on only \(m\) columns. That said, the sparse matrices (Figure 14b) better approximate this condition, and we see that the Decomposition protocol actually performs reasonably well for larger \(m\). Meanwhile, the Rodeo algorithm underperforms for both classes of matrices-while the positive trend is evident, and it is more consistent than the Decomposition protocol for small \(m\), it has a significantly smaller slope of enhancement than its competitors. We see this trend continue in its extreme in Figure 14c, which considers the simple case where each row of \(A\) measures a single pixel. The Rodeo algorithm is a stochastic algorithm heavily reliant on sampling over a representative distribution of phases, and it may perform better when the \"one-shot\" sampling approach used in this paper is relaxed. Figure 14: Comparison of each Quantum Compressive Sensing protocol, for different classes of sensing matrix. (**a**), (**b**), (**c**) utilize a binary \(A\) with \(A_{ij}\) being 0 or 1 with equal probability, a binary \(A\) with \(A_{ij}\) being 1 with 20% probability, and a binary \(A\) with each row of \(A\) having only a single 1 respectively. (**d**) utilizes a uniform \(A\) where only \(m\) columns of \(A\) are nonzero. QITE uses \(\sigma=\frac{1}{2}\) and Rodeo uses \(\sigma=\pi\).