# Bypassing orthogonalization in the quantum DPP sampler

arXiv: https://arxiv.org/abs/2503.05906 · HTML: https://mlsanity.com/paper/2503.05906/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 48 references that are in the map.
- First posted on arXiv 7 Mar 2025.

## Builds on (most cited first, 18 of 18)

- [Determinantal Point Processes in Randomized Numerical Linear Algebra](https://mlsanity.com/paper/2005.03185/) (2020)
- [Large-scale Log-determinant Computation through Stochastic Chebyshev Expansions](https://mlsanity.com/paper/1503.06394/) (2015)
- [Learning Nonsymmetric Determinantal Point Processes](https://mlsanity.com/paper/1905.12962/) (2019)
- [Scalable Learning and MAP Inference for Nonsymmetric Determinantal Point Processes](https://mlsanity.com/paper/2006.09862/) (2020)
- [Determinantal point processes based on orthogonal polynomials for sampling minibatches in SGD](https://mlsanity.com/paper/2112.06007/) (2021)
- [A Randomized Algorithm for Approximating the Log Determinant of a Symmetric Positive Definite Matrix](https://mlsanity.com/paper/1503.00374/) (2015)
- [Uniform Sampling through the Lov'asz Local Lemma](https://mlsanity.com/paper/1611.01647/) (2016)
- [A determinantal point process for column subset selection](https://mlsanity.com/paper/1812.09771/) (2018)
- [Quantum Speedup for Graph Sparsification, Cut Approximation and Laplacian Solving](https://mlsanity.com/paper/1911.07306/) (2019)
- [Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence](https://mlsanity.com/paper/2204.02570/) (2022)
- [A Faster Sampler for Discrete Determinantal Point Processes](https://mlsanity.com/paper/2210.17358/) (2022)
- [A Matrix Chernoff Bound for Strongly Rayleigh Distributions and Spectral Sparsifiers from a few Random Spanning Trees](https://mlsanity.com/paper/1810.08345/) (2018)
- [Graph sampling with determinantal processes](https://mlsanity.com/paper/1703.01594/) (2017)
- [Fundamentals of Partial Rejection Sampling](https://mlsanity.com/paper/2106.07744/) (2021)
- [From point processes to quantum optics and back](https://mlsanity.com/paper/2210.05522/) (2022)
- [Smoothing complex-valued signals on Graphs with Monte-Carlo](https://mlsanity.com/paper/2210.08014/) (2022)
- [On sampling determinantal and Pfaffian point processes on a quantum computer](https://mlsanity.com/paper/2305.15851/) (2023)
- [Cycling in the forest with Wilson's algorithm](https://mlsanity.com/paper/2404.14803/) (2024)

## Abstract (arXiv)

Given an n× r matrix X of rank r, consider the problem of sampling r integers mathttCsubset 1, dots, n with probability proportional to the squared determinant of the rows of X indexed by mathttC. The distribution of mathttC is called a projection determinantal point process (DPP). The vanilla classical algorithm to sample a DPP works in two steps, an orthogonalization in O(nr2) 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 O(nr2) orthogonalization, followed by a O(nr) classical step to find the gates in a quantum circuit. The classical O(nr2) orthogonalization thus still dominates the cost. Our first contribution is to reduce preprocessing to normalizing the columns of X, obtaining mathsfX in 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 mathsfX^topmathsfX = 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 O(rlog n/√a) and 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 O(nr2) preprocessing bottleneck has been replaced by the O(nr) cost of normalizing the columns and the cost of our approximation of a.