Quantum machine learning with subspace states

We introduce a new approach for quantum linear algebra based on quantum subspace states and present three new quantum machine learning algorithms. The first is a quantum determinant sampling algorithm that samples from the distribution $\mathrm{Pr}[S]=det(X_S{X}_S^T)$ for $\mathrm{\mid }S\mathrm{\mid }=d$ using $O(nd)$ gates and with circuit depth $O(d\log n)$. The state of art classical algorithm for the task requires $O(d^3)$ operations \cite{derezinski2019minimax}. The second is a quantum singular value estimation algorithm for compound matrices ${\mathcal{A}}^k$, the speedup for this algorithm is potentially exponential. It decomposes a $\left(\genfrac{}{}{0px}{}{n}{k}\right)$ dimensional vector of order-$k$ correlations into a linear combination of subspace states corresponding to $k$-tuples of singular vectors of $A$. The third algorithm reduces exponentially the depth of circuits used in quantum topological data analysis from $O(n)$ to $O(\log n)$. Our basic tool are quantum subspace states, defined as $|Col(X)\rangle = \sum_{S\subset [n], |S|=d} det(X_{S}) |S\rangle$formatrices$X \in $\mathbb{R}$^{n \times d}$suchthat$X^{T} X = I_{d}$,thatencode$d$-dimensionalsubspacesof$$\mathbb{R}$^{n}$. We develop two efficient state preparation techniques, the first using Givens circuits uses the representation of a subspace as a sequence of Givens rotations, while the second uses efficient implementations of unitaries $\Gamma(x) = \sum_{i} x_{i} Z^{\otimes (i-1)} \otimes X \otimes I^{n-i}$with$O(\log n)$ depth circuits that we term Clifford loaders.