# Quantum Compressive Sensing: Mathematical Machinery, Quantum Algorithms, and Quantum Circuitry
## 4 Training  
We now consider quantum algorithms to prepare \(n\) qubits into a Born machine \(|\Psi\rangle\) describing the set \(Y\). Practically speaking, the Born machine is constructed in the machine learning sense--that is, on a representative _training set_\(T\subset Y\), while we assume that \(|\Psi\rangle\) generalizes usefully onto the entire population \(Y\). A typical approach is to prepare \(|\Psi\rangle\) variationally, applying a unitary _variational form_\(V(\mathbf{\theta})\) to the initial state \(|\mathbf{0}\rangle\) to prepare an _ansatz_\(|\Psi(\mathbf{\theta})\rangle=V(\mathbf{\theta})|\mathbf{0}\rangle\). One then makes measurements on the ansatz to determine the expectation values of some cost function \(C(\mathbf{\theta})\). The parameters \(\mathbf{\theta}\) are tuned through a classical algorithm such as gradient descent until the cost function \(C\) is minimized. The cost function is selected such that its minimum corresponds to a Born Machine which well represents the training set \(T\). For example, the Negative Log Likelihood (NLL) function used in previous works is given as [6; 7]:  
\[C(\mathbf{\theta})=-\frac{1}{|T|}\sum_{y\in T}\ln|\langle y|\Psi(\mathbf{\theta}) \rangle|^{2}. \tag{4}\]  
The variational form \(V(\mathbf{\theta})\) should in principle be capable of preparing any ansatz \(|\Psi\rangle\) in the Hilbert space of \(n\) qubits. In gate-model quantum computing, any unitary operation must be decomposed into single- and two-qubit operations, and a fully general variational form may require an exponential number of operations. Therefore, one may choose to use a randomized circuit which merely approximates the Hilbert space. Layered circuits alternating between single-qubit rotations and entanglement between adjacent qubits have been shown to sample uniformly from the Hilbert space provided sufficient layers, making them promising candidates. However, recent theoretical efforts show that quantum variational algorithms are extremely vulnerable to the phenomenon of _barren plateaus_, in which large tracts of the parameter space are essentially flat, resulting in optimizations which either fail to converge or which converge at entirely arbitrary points [28; 29]. These difficulties motivate us to explore an alternative training procedure, which does not require gradient descent or any such optimization process at all. Let us model the Born machine \(|\Psi\rangle\) to be a _superposition_ of each element in \(Y\), in some sense a \"quantum average\" ([PERSON] et al. [7] use this term in a similar way):  
\[|\Psi\rangle=\frac{1}{\sqrt{|Y|}}\sum_{z=0}^{|Y|-1}|y_{z}\rangle. \tag{5}\]  
Figure 2: A simple quantum circuit to map an \(n\)-dimensional vector \(y\) onto \(n\) qubits. The quantum gate \(R_{y}(\theta)\) is defined as \(\exp\left(-i\frac{\theta}{2}\hat{Y}\right)\), where \(\hat{Y}\) is the Pauli Y spin operator. If all \(y\in Y\) are orthogonal, the square amplitude \(|\langle y|\Psi\rangle|^{2}=1/|Y|\) is precisely the probability of retrieving \(y\) from \(Y\), as desired. It should be noted we assume all \(y\) are uniformly distributed. In the more general case, we consider \(Y\) a collection which may contain multiple copies of the same \(y\), so that it is summed over more than once. This will not hold for a set \(Y\) whose elements are not orthogonal, but this is advantageous: overlap between qualitatively similar images permits us to construct \(|\Psi\rangle\) only from the training set \(T\), and still achieve meaningful amplitudes for \(y\
ot\in T\). There is no simple quantum operation which can deterministically prepare the sum of two arbitrary non-orthogonal quantum states. To see this, note that adding the states \(|0\rangle\), \(-|0\rangle\) (the same but for opposite phases) must result in the unnormalizable state \(0\), which cannot be prepared by a unitary operation. There is, however, a procedure by which we may yet achieve our goal.