# Quantum Compressive Sensing: Mathematical Machinery, Quantum Algorithms, and Quantum Circuitry
## Appendix A Relative Log Likelihood  
In this section, we develop a bias-free measure for rating how well an image _estimate_\(|z\rangle\) matches the true signal \(y\), suitable for contrasting performance across multiple trials and implementations. With a \"one-shot\" sampling approach, the output \(|z\rangle\) of our projection protocol is always a computational basis state:  
\[|z\rangle=\bigotimes_{q=1}^{n}|z_{i}\rangle,|z_{i}\rangle\in\{|0\rangle,|1 \rangle\}. \tag{1}\]  
Meanwhile, our pixel-qubit mapping and training protocol allow for gray-scale signals \(y=\big{[}y_{0}...y_{n}\big{]}\), \(y_{i}\in[0,1]\). The best possible binary image is straightforward to derive from the gray-scale signal, given the mapping in Equation (2): select \(|z_{i}\rangle=|0\rangle\) if \(y_{i}<p\) and \(|z_{i}\rangle=|1\rangle\) otherwise. However, even when the correct signal \(y\) is successfully discriminated by the compressive sensing protocol, the probability that the final readout step produces the optimal image is determined by the precise values of \(y_{i}\), and will in general be very low as \(n\) increases. We should consider \(|z\rangle\) \"correct\" as long as it remains qualitatively similar to \(y\). Our goal in this section is to develop a _quantitative_ statistic for the similarity between \(|z\rangle\) and \(y\).  
As a first attempt, consider the fidelity \(F\):  
\[F(y,z)\equiv|\langle z|y\rangle|^{2}, \tag{2}\]  
where \(|y\rangle\) is the quantum state mapped by Equation (2). This is an intuitive choice and a common metric for determining distance between quantum states. However, it is not _fair_, in the sense that different \(y_{i}\) have drastically different distributions of \(F\). To quickly appreciate this, consider the two-dimensional signals \(y_{a}=\begin{bmatrix}1&0\end{bmatrix}\) and \(y_{b}=\begin{bmatrix}2&3\\ 3&3\end{bmatrix}\), and set the midpoint \(p=0.5\). For both signals, the best possible binary image is \(|z\rangle=|10\rangle\). Finding the fidelity of \(|z\rangle\) with respect to each state, we see \(F_{a}=1\) while \(F_{b}=\frac{9}{16}\). This shows that the best possible fidelity for \(y_{b}\) is barely half of that of \(y_{a}\). Evidently, fidelity alone is not suitable for contrasting performance across multiple signals.  
The measure we propose is the following:  
\[RLL(y,z)=\ln F(y,z)+S(y), \tag{10}\]  
christened RLL for \"Relative Log Likelihood\", after its closely related cousin the Negative Log Likelihood (see Equation (4)). The first term \(\ln F\) is simply the fidelity from the previous paragraph, scaled logarithmically. The second term \(S\) normalizes the log fidelity by subtracting off the _average_ log fidelity over all possible choices of \(|z\rangle\), weighted by the probability of obtaining \(|z\rangle\) upon measuring \(|y\rangle\). Naturally, this probability is precisely the fidelity \(F\), and \(S\) turns out to be the information entropy of the distribution over all \(F\), i.e.,  
\[S(y)=-\sum_{z}F(y,z)\ln F(y,z). \tag{11}\]  
Because entropy is an extrinsic property, we know that \(S(y)\) can be calculated efficiently pixel by pixel via \(S(y)=\sum_{i=1}^{n}S(y_{i})\), where the information entropy for a single pixel is a simple sum over \(z_{i}=\{0,1\}\).