On sampling determinantal and Pfaffian point processes on a quantum computer

DPPs were introduced by Macchi as a model in quantum optics the 1970s. Since then, they have been widely used as models and subsampling tools in statistics and computer science. Most applications require sampling from a DPP, and given their quantum origin, it is natural to wonder whether sampling a DPP on a quantum computer is easier than on a classical one. We focus here on DPPs over a finite state space, which are distributions over the subsets of {1, horizontal ellipsis ,N} parametrized by an N x N Hermitian kernel matrix. Vanilla sampling consists in two steps, of respective costs O(N3) and O(Nr2) operations on a classical computer, where r is the rank of the kernel matrix. A large first part of the current paper consists in explaining why the state-of-the-art in quantum simulation of fermionic systems already yields quantum DPP sampling algorithms. We then modify existing quantum circuits, and discuss their insertion in a full DPP sampling pipeline that starts from practical kernel specifications. The bottom line is that, with P (classical) parallel processors, we can divide the preprocessing cost by P and build a quantum circuit with O(Nr) gates that sample a given DPP, with depth varying from O(N) to O(rlogN) depending on qubit-communication constraints on the target machine. We also connect existing work on the simulation of superconductors to Pfaffian point processes (PfPP), which generalize DPPs and would be a natural addition to the machine learner's toolbox. In particular, we describe 'projective' PfPPs, the cardinality of which has constant parity, almost surely. Finally, the circuits are empirically validated on a classical simulator and on 5-qubit IBM machines.