论文标题
用子空间状态进行量子机学习
Quantum machine learning with subspace states
论文作者
论文摘要
我们引入了一种基于量子子空间状态的量子线性代数的新方法，并介绍了三种新的量子机学习算法。第一个是一种量子决定量采样算法，该算法是从分布$ \ pr [s] = det（x_ {x_ {s} x_ {s} x}^{t}）$ for $ | s | = d $使用$ o（nd）$ gates和带电路depth $ o（d \ log n）$的$ | s | = d $。该任务的最先进算法需要$ o（d^{3}）$ operations \ cite {derezinski2019minimax}。第二个是复合矩阵$ \ MATHCAL {a}^{k} $的量子奇异值估计算法，该算法的加速可能是指数的。它将$ \ binom {n} {k} $订单 - $ k $相关的维矢量分解为对应于$ k $ a $ a $的单数向量的子空间状态的线性组合。第三个算法将量子拓扑数据分析中使用的电路深度从$ o（n）$降低到$ o（\ log n）$。 我们的基本工具是量子子空间状态，定义为$ | col（x）\ rangle = \ sum_ {s \ subset [n]，| s | = d} det（x_ {s}）| s \ rangle $用于矩阵的$ x \ in \ mathbb {r} $ \ mathbb {r}^{n} $的编码$ D $ -Dimensional子空间。我们开发了两种有效的状态制备技术，第一种使用givens电路使用子空间的表示为吉文族旋转的顺序，而第二个则使用了一个有效的unitaries $γ（x）= \ sum_ {i} x__ {i} x_ {i} z^{i} z^{\ imimes（i-1）} nimimes x^$ timime x^iimimeime x^iimimeimeime x^iimimeimeime x^iimime iimimeime x^ $ o（\ log n）$ DEPTH电路我们称为Clifford加载程序。
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 $\Pr[S]= det(X_{S}X_{S}^{T})$ for $|S|=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 $\binom{n}{k}$ 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$ for matrices $X \in \mathbb{R}^{n \times d}$ such that $X^{T} X = I_{d}$, that encode $d$-dimensional subspaces of $\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 $Γ(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.
