Title: Bypassing orthogonalization in the quantum DPP sampler Show Chinese title

Title: 在量子DPP采样器中绕过正交化

Abstract: Given an $n\times r$ matrix $X$ of rank $r$, consider the problem of sampling $r$ integers $\mathtt{C}\subset \{1, \dots, n\}$ with probability proportional to the squared determinant of the rows of $X$ indexed by $\mathtt{C}$. The distribution of $\mathtt{C}$ is called a projection determinantal point process (DPP). The vanilla classical algorithm to sample a DPP works in two steps, an orthogonalization in $\mathcal{O}(nr^2)$ and a sampling step of the same cost. The bottleneck of recent quantum approaches to DPP sampling remains that preliminary orthogonalization step. For instance, (Kerenidis and Prakash, 2022) proposed an algorithm with the same $\mathcal{O}(nr^2)$ orthogonalization, followed by a $\mathcal{O}(nr)$ classical step to find the gates in a quantum circuit. The classical $\mathcal{O}(nr^2)$ orthogonalization thus still dominates the cost. Our first contribution is to reduce preprocessing to normalizing the columns of $X$, obtaining $\mathsf{X}$ in $\mathcal{O}(nr)$ classical operations. We show that a simple circuit inspired by the formalism of Kerenidis et al., 2022 samples a DPP of a type we had never encountered in applications, which is different from our target DPP. Plugging this circuit into a rejection sampling routine, we recover our target DPP after an expected $1/\det \mathsf{X}^\top\mathsf{X} = 1/a$ preparations of the quantum circuit. Using amplitude amplification, our second contribution is to boost the acceptance probability from $a$ to $1-a$ at the price of a circuit depth of $\mathcal{O}(r\log n/\sqrt{a})$ and $\mathcal{O}(\log n)$ extra qubits. Prepending a fast, sketching-based classical approximation of $a$, we obtain a pipeline to sample a projection DPP on a quantum computer, where the former $\mathcal{O}(nr^2)$ preprocessing bottleneck has been replaced by the $\mathcal{O}(nr)$ cost of normalizing the columns and the cost of our approximation of $a$. Show Chinese abstract

Abstract: 给定一个秩为$r$的$n\times r$矩阵$X$，考虑采样$r$个整数$\mathtt{C}\subset \{1, \dots, n\}$的问题，其概率与由$\mathtt{C}$索引的$X$行的平方行列式成比例。 $\mathtt{C}$的分布被称为投影行列式点过程（DPP）。 经典的采样DPP的算法分为两步，在$\mathcal{O}(nr^2)$中进行正交化，然后进行相同成本的采样步骤。 最近量子方法在DPP采样中的瓶颈仍然是最初的正交化步骤。 例如，(Kerenidis和Prakash, 2022) 提出了一种算法，具有相同的$\mathcal{O}(nr^2)$正交化，然后进行$\mathcal{O}(nr)$的经典步骤以在量子电路中找到门。 因此，经典的$\mathcal{O}(nr^2)$正交化仍然主导着成本。 我们第一个贡献是将预处理减少到归一化$X$的列，得到$\mathsf{X}$在$\mathcal{O}(nr)$经典操作中。 我们表明，一个受 Kerenidis 等人，2022 年形式主义启发的简单电路采样了一种我们在应用中从未遇到过的 DPP，这与我们的目标 DPP 不同。 将此电路插入拒绝采样过程后，我们在预期$1/\det \mathsf{X}^\top\mathsf{X} = 1/a$次量子电路准备后恢复了我们的目标 DPP。 使用幅度放大，我们的第二个贡献是在电路深度为$\mathcal{O}(r\log n/\sqrt{a})$且额外需要$\mathcal{O}(\log n)$个量子比特的代价下，将接受概率从$a$提高到$1-a$。 在对$a$进行快速的基于草图的经典近似之前，我们获得了一个在量子计算机上采样投影DPP的流程，其中之前的$\mathcal{O}(nr^2)$预处理瓶颈已被$\mathcal{O}(nr)$的列归一化成本以及我们对$a$的近似成本所取代。