Given two Hermitian matrices Y and Λ, the Harish-Chandra–Itzykson–Zuber (HCIZ) distribution is given by the density eTr(U Λ U*Y) 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 produces samples that are ξ-close in total variation distance, and the number of arithmetic operations required depends on poly(log1/ξ). The second produces samples that are ξ-close in infinity divergence, but with a poly(1/ξ) dependence. 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-k approximation that comes with improved utility bounds for k>1.
Given two Hermitian matrices Y and Λ, the Harish-Chandra–Itzykson–Zuber (HCIZ) distribution is given by the density eTr(U Λ U*Y) 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 produces samples that are ξ-close in total variation distance, and the number of arithmetic operations required depends on poly(log1/ξ). The second produces samples that are ξ-close in infinity divergence, but with a poly(1/ξ) dependence. 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-k approximation that comes with improved utility bounds for k>1.
Given two n×n Hermitian matrices Y and Λ, the Harish-Chandra-Itzykson-Zuber (HCIZ) distribution on the unitary group U(n) is etr(UΛU∗Y)dμ(U), where μ is the Haar measure on U(n). The density etr(UΛU∗Y) is known as the HCIZ density. Random unitary matrices distributed according to the HCIZ density are important in various settings in physics and random matrix theory. However, the basic question of efficient sampling from the HCIZ distribution has remained open. We present two efficient algorithms to sample matrices from distributions that are close to the HCIZ distribution. The first algorithm outputs samples that are ξ-close in total variation distance and requires polynomially many arithmetic operations in log1/ξ and the number of bits needed to encode Y and Λ. The second algorithm comes with a stronger guarantee that the samples are ξ-close in infinity divergence, but the number of arithmetic operations depends polynomially on 1/ξ, the number of bits needed to encode Y and Λ, and the differences of the largest and the smallest eigenvalues of Y and Λ. HCIZ densities can also be viewed as exponential densities on U(n)-orbits, and these densities have been studied in statistics, machine learning, and theoretical computer science. Thus 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 max-entropy distributions on unitary orbits, which 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-k approximation, with improved utility bounds for k>1.
Fix the spectrum of a bipartite density matrix and randomize its eigenbasis according to Haar measure. We study the probability distributions induced on the spectra of the two marginal states. For arbitrary subsystem dimensions m and n, the joint characteristic function of the reduced density matrices is expressed as a Harish-Chandra-Itzykson-Zuber integral whose external eigenvalues are the pairwise sums xi+yj. Repeated external eigenvalues are handled by confluent determinant limits. In the two-qubit case, we derive an explicit alternating-spline formula for the joint density of the two marginal Bloch radii. Its support is the Bravyi-Klyachko compatibility region. We also obtain a compact truncated-power formula for the Bloch-radius density of either individual qubit marginal. In the qubit-qutrit case, we derive a truncated-power formula for the qubit Bloch-radius density and a bivariate spline formula for the joint density of the largest and smallest eigenvalues of the qutrit marginal. The latter two variables determine the full qutrit spectrum because the trace is fixed. The derivations combine confluent HCIZ integrals, distributional Fourier inversion, orbital measures, and the SU(2) and SU(3) derivative principles. The resulting densities are piece-wise polynomial on chambers determined by subset sums of the fixed global eigenvalues, in agreement with the Duistermaat-Heckman description of projected coadjoint-orbit measures.
A fundamental task in quantum information is to approximate a pure quantum state in terms of sparse states or, for a bipartite system, states of bounded Schmidt rank. The optimal deterministic approximation in each case is straightforward, and maximizes the fidelity: keep the largest entries or singular values. On the other hand, random mixtures of sparse states can achieve quadratically improved trace distances, and yield nontrivial bounds on other distance measures like the robustness. In this work, we give efficient algorithms for finding mixtures of sparse states that optimally approximate a given pure state in either trace distance or robustness. These algorithms also yield descriptions of efficiently samplable ensembles of sparse, or less-entangled, states that correspond to these optimal mixed approximations. This can be used for the truncation step of algorithms for matrix product states, improving their accuracy while using no extra memory and no asymptotic increase in runtime, and we demonstrate this improvement numerically. Our proofs rely on tools from convex optimization and zero-sum games, as well as rigorous gurarantees for computing and sampling from maximum-entropy distributions. In particular, a key step in our construction is conditional Poisson sampling, which is the well-studied problem of drawing fixed-size subsets from a population with known inclusion probabilities. We give improved algorithms for carrying out this sampling, which may be of independent interest.
Let Sm be the set of all m×m density matrices (Hermitian positively semi-definite matrices of unit trace). Consider a problem of estimation of an unknown density matrix ρ∈Sm based on outcomes of n measurements of observables X1,…,Xn∈Hm (Hm being the space of m×m Hermitian matrices) for a quantum system identically prepared n times in state ρ. Outcomes Y1,…,Yn of such measurements could be described by a trace regression model in which Eρ(Yj∣Xj)=tr(ρXj),j=1,…,n. The design variables X1,…,Xn are often sampled at random from the uniform distribution in an orthonormal basis {E1,…,Em2} of Hm (such as Pauli basis). The goal is to estimate the unknown density matrix ρ based on the data (X1,Y1),…,(Xn,Yn). Let Z^:=nm2∑j=1nYjXj and let ρˇ be the projection of Z^ onto the convex set Sm of density matrices. It is shown that for estimator ρˇ the minimax lower bounds in classes of low rank density matrices (established earlier) are attained up logarithmic factors for all Schatten p-norm distances, p∈[1,∞] and for Bures version of quantum Hellinger distance. Moreover, for a slightly modified version of estimator ρˇ the same property holds also for quantum relative entropy (Kullback-Leibler) distance between density matrices.
We initiate a study of the following problem: Given a continuous domain Ω along with its convex hull K, a point A∈K and a prior measure μ on Ω, find the probability density over Ω whose marginal is A and that minimizes the KL-divergence to μ. This framework gives rise to several extremal distributions that arise in mathematics, quantum mechanics, statistics, and theoretical computer science. Our technical contributions include a polynomial bound on the norm of the optimizer of the dual problem that holds in a very general setting and relies on a "balance" property of the measure μ on Ω, and exact algorithms for evaluating the dual and its gradient for several interesting settings of Ω and μ. Together, along with the ellipsoid method, these results imply polynomial-time algorithms to compute such KL-divergence minimizing distributions in several cases. Applications of our results include: 1) an optimization characterization of the Goemans-Williamson measure that is used to round a positive semidefinite matrix to a vector, 2) the computability of the entropic barrier for polytopes studied by Bubeck and Eldan, and 3) a polynomial-time algorithm to compute the barycentric quantum entropy of a density matrix that was proposed as an alternative to von Neumann entropy in the 1970s: this corresponds to the case when Ω is the set of rank one projections matrices and μ corresponds to the Haar measure on the unit sphere. Our techniques generalize to the setting of Hermitian rank k projections using the Harish-Chandra-Itzykson-Zuber formula, and are applicable even beyond, to adjoint orbits of compact Lie groups.
Inspired by the quantum computing algorithms for Linear Algebra problems [HHL,TaShma] we study how the simulation on a classical computer of this type of "Phase Estimation algorithms" performs when we apply it to solve the Eigen-Problem of Hermitian matrices. The result is a completely new, efficient and stable, parallel algorithm to compute an approximate spectral decomposition of any Hermitian matrix. The algorithm can be implemented by Boolean circuits in O(log2n) parallel time with a total cost of O(nω+1) Boolean operations. This Boolean complexity matches the best known rigorous O(log2n) parallel time algorithms, but unlike those algorithms our algorithm is (logarithmically) stable, so further improvements may lead to practical implementations. All previous efficient and rigorous approaches to solve the Eigen-Problem use randomization to avoid bad condition as we do too. Our algorithm makes further use of randomization in a completely new way, taking random powers of a unitary matrix to randomize the phases of its eigenvalues. Proving that a tiny Gaussian perturbation and a random polynomial power are sufficient to ensure almost pairwise independence of the phases (mod(2π)) is the main technical contribution of this work. This randomization enables us, given a Hermitian matrix with well separated eigenvalues, to sample a random eigenvalue and produce an approximate eigenvector in O(log2n) parallel time and O(nω) Boolean complexity. We conjecture that further improvements of our method can provide a stable solution to the full approximate spectral decomposition problem with complexity similar to the complexity (up to a logarithmic factor) of sampling a single eigenvector.