# Quantum Compressive Sensing: Mathematical Machinery, Quantum Algorithms, and Quantum Circuitry
## 5 Projection
### Rodeo Algorithm  
Define the measurement-vector operator \(\hat{N}_{i}\) for each row \(i\) of \(A\) as  
\[\hat{N}_{i}=\frac{1}{2}\sum_{q}A_{iq}(\hat{I}-\hat{Z}_{q}), \tag{11}\]  
where \(\hat{I}\) is the identity operator and \(\hat{Z}_{q}\) is the Pauli \(\sigma_{z}\) operator on qubit \(q\). When \(A\) is a binary matrix, \(\hat{N}\) is the standard qubit number operator acting on those pixels \"measured\" by \(A_{i}\). This operator is directly connected to the measurement outcome \(x_{i}\)--in fact, we would like to project our trained Born Machine \(|\Psi\rangle\) onto a quantum state \(|\Psi_{x_{i}}\rangle\) such that the expectation value \(\langle\Psi_{x_{i}}|(\hat{N}_{i}-x_{i})|\Psi_{x_{i}}\rangle\) is 0.  
We achieve this by implementing the Rodeo algorithm, a probabilistic method based on quantum phase estimation originally developed for spectrally identifying eigenvalues of a Hamiltonian operator ([PERSON] and [PERSON], 2002). The central idea is to apply the time-evolution operator \(\hat{U}=\exp\bigl{[}-i(\hat{N}_{i}-x_{i})\tau\bigr{]}\) to our trained Born machine \(|\Psi\rangle\) for a random time \(\tau\), controlled on a set of qubits in the Hadamard state. The phase accumulated by applying \(U\) is \"kicked back\" to the control register, and can be read off directly by measuring all qubits after a _Quantum Fourier Transform_. We are interested in the case where the accumulated phase is 0, corresponding to measuring all control qubits as 0. If we successfully do so, we have (with some probability) collapsed \(|\Psi\rangle\) onto \(|\Psi_{x_{i}}\rangle\) as desired. We now repeat this procedure for all \(\hat{N}_{i}\), and upon successfully measuring 0 on _all_ control qubits, we can measure the qubits on our Born machine for a probabilistic estimate of the original signal \(y\).  
Our collapsed state may include any contribution accumulating a phase multiple of \(2\pi\) after time \(\tau\). The latter is mitigated by randomly selecting every \(\tau\) from a normal distribution with variance \(\sigma^{2}\). The contribution of phases outside of \(\pm 1/\sigma\) falls off exponentially. Because \(U\) in our protocol decomposes into commuting single-qubit operators, implementing its controlled variant is relatively straightforward and independent of time \(\tau\) (as opposed to time-evolution of a general Hamiltonian, which may need to be decomposed into many small time steps). Therefore, \(\sigma\) may be freely tuned to balance accuracy and generalizability.  
Another factor affecting the success of the Rodeo algorithm is the resolution with which we can measure the phase, as determined by the number of qubits in the control register. This poses the primary limitation of the Rodeo protocol, since higher resolution requires more qubits, as well as higher qubit connectivity to accommodate controlled operations. Therefore, we adopt the highly speculative strategy of using a _single_ qubit for each \(\hat{N}_{i}\), requiring exactly \(m\) auxiliary qubits (see Figure 6). The quality of any single-shot experiment is relatively low, but repeating the experiment over many trials by randomly selecting new \(\tau\) for every trial has the potential to generate useful results.