Sampling Matrices From Harish‐Chandra–Itzykson–Zuber Densities With Applications to Quantum Inference and Differential Privacy

ABSTRACT Given two Hermitian matrices and , the Harish‐Chandra–Itzykson–Zuber (HCIZ) distribution is given by the density with respect to the Haar measure on the unitary group. Random unitary matrices distributed according to the HCIZ distribution are important in various settings in physics and random matrix theory, but the problem of sampling efficiently from this distribution has remained open. We present two algorithms to sample matrices from distributions that are close to the HCIZ distribution. The first algorithm produces samples that are ‐close in total variation, and the number of arithmetic operations required depends on . The second algorithm comes with a stronger guarantee that the samples are ‐close in infinity divergence; however, its number of arithmetic operations depends polynomially on . Our results have the following applications: (1) an efficient algorithm to sample from complex versions of matrix Langevin distributions studied in statistics, (2) an efficient algorithm to sample from continuous maximum entropy distributions over unitary orbits, which in turn implies an efficient algorithm to sample a pure quantum state from the entropy‐maximizing ensemble representing a given density matrix, and (3) an efficient algorithm for differentially private rank‐ approximation that comes with improved utility bounds for .