Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

ACM Symposium on Theory of Computing (STOC)

Sampling matrices from Harish-Chandra–Itzykson–Zuber densities with applications to Quantum inference and differential privacy

Jonathan Leake, Colin McSwiggen, Nisheeth K. Vishnoi

Published Jun 15, 2021• 10 citations
Publisher

Abstract

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.

DOI
10.1145/3406325.3451094

Related papers

Marginal spectral distributions on regular bipartite unitary orbits

Lin Zhang

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 $x_i + y_j$. 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.

quant-pharXiv:2608.30370•Sep 1, 2026•1 citation

Randomized truncation of quantum states

Aram W. Harrow, Angus Lowe, Freek Witteveen

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.

arXiv:2510.08518•Oct 9, 2025•6 citations

Estimation of low rank density matrices: Bounds in Schatten norms and other distances

Dong Xia, Vladimir I. Koltchinskii

Let $\mathcal{S}_{m}$ be the set of all $m\times m$ density matrices (Hermitian positively semi-definite matrices of unit trace). Consider a problem of estimation of an unknown density matrix $\rho\in\mathcal{S}_{m}$ based on outcomes of $n$ measurements of observables $X_{1},\dots,X_{n}\in\mathbb{H}_{m}$ ($\mathbb{H}_{m}$ being the space of $m\times m$ Hermitian matrices) for a quantum system identically prepared $n$ times in state $\rho.$ Outcomes $Y_{1},\dots,Y_{n}$ of such measurements could be described by a trace regression model in which $\mathbb{E}_{\rho}(Y_{j}|X_{j})={\rm tr}(\rho X_{j}),j=1,\dots,n.$ The design variables $X_{1},\dots,X_{n}$ are often sampled at random from the uniform distribution in an orthonormal basis $\{E_{1},\dots,E_{m^{2}}\}$ of $\mathbb{H}_{m}$ (such as Pauli basis). The goal is to estimate the unknown density matrix $\rho$ based on the data $(X_{1},Y_{1}),\dots,(X_{n},Y_{n}).$ Let \[\hat{Z}:=\frac{m^{2}}{n}\sum_{j=1}^{n}Y_{j}X_{j}\] and let $\check{\rho}$ be the projection of $\hat{Z}$ onto the convex set $\mathcal{S}_{m}$ of density matrices. It is shown that for estimator $\check{\rho}$ 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\in[1,\infty]$ and for Bures version of quantum Hellinger distance. Moreover, for a slightly modified version of estimator $\check{\rho}$ the same property holds also for quantum relative entropy (Kullback-Leibler) distance between density matrices.

arXiv:1604.04600•Electronic Journal of Statistics•Jan 1, 2016•19 citations

A Quasi-Random Approach to Matrix Spectral Analysis

Michael Ben-Or, Lior Eldar

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(\log^2 n)$ parallel time with a total cost of $O(n^{ω+1})$ Boolean operations. This Boolean complexity matches the best known rigorous $O(\log^2 n)$ 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(\log^2 n)$ 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.

arXiv:1505.08126•Leibniz international proceedings in informatics•May 29, 2015•4 citations

Efficient unitary paths and quantum computational supremacy: A proof of average-case hardness of Random Circuit Sampling

Ramis Movassagh

One-parameter interpolations between any two unitary matrices (e.g., quantum gates) $U_1$ and $U_2$ along efficient paths contained in the unitary group are constructed. Motivated by applications, we propose the continuous unitary path $U(θ)$ obtained from the QR-factorization \[ U(θ)R(θ)=(1-θ)A+θB, \] where $U_1 R_1=A$ and $U_2 R_2=B$ are the QR-factorizations of $A$ and $B$, and $U(θ)$ is a unitary for all $θ$ with $U(0)=U_1$ and $U(1)=U_2$. The QR-algorithm is modified to, instead of $U(θ)$, output a matrix whose columns are proportional to the corresponding columns of $U(θ)$ and whose entries are polynomial or rational functions of $θ$. By an extension of the Berlekamp-Welch algorithm we show that rational functions can be efficiently and exactly interpolated with respect to $θ$. We then construct probability distributions over unitaries that are arbitrarily close to the Haar measure. Demonstration of computational advantages of NISQ over classical computers is an imperative near-term goal, especially with the exuberant experimental frontier in academia and industry (e.g., IBM and Google). A candidate for quantum computational supremacy is Random Circuit Sampling (RCS), which is the task of sampling from the output distribution of a random circuit. The aforementioned mathematical results provide a new way of scrambling quantum circuits and are applied to prove that exact RCS is $\#P$-Hard on average, which is a simpler alternative to Bouland et al's. (Dis)Proving the quantum supremacy conjecture requires "approximate" average case hardness; this remains an open problem for all quantum supremacy proposals.

arXiv:1810.04681•Oct 10, 2018•35 citations

Direct dialling of Haar random unitary matrices

Nicholas J Russell, Levon Chakhmakhchyan, Jeremy L. O’Brien +1 more

Random unitary matrices find a number of applications in quantum information science, and are central to the recently defined boson sampling algorithm for photons in linear optics. We describe an operationally simple method to directly implement Haar random unitary matrices in optical circuits, with no requirement for prior or explicit matrix calculations. Our physically motivated and compact representation directly maps independent probability density functions for parameters in Haar random unitary matrices, to optical circuit components. We go on to extend the results to the case of random unitaries for qubits.

arXiv:1506.06220•New Journal of Physics•Feb 16, 2017•89 citations
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.
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 mmm and nnn, 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+yjx_i + y_jxi​+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\mathcal{S}_{m}Sm​ be the set of all m×mm\times mm×m density matrices (Hermitian positively semi-definite matrices of unit trace). Consider a problem of estimation of an unknown density matrix ρ∈Sm\rho\in\mathcal{S}_{m}ρ∈Sm​ based on outcomes of nnn measurements of observables X1,…,Xn∈HmX_{1},\dots,X_{n}\in\mathbb{H}_{m}X1​,…,Xn​∈Hm​ (Hm\mathbb{H}_{m}Hm​ being the space of m×mm\times mm×m Hermitian matrices) for a quantum system identically prepared nnn times in state ρ.\rho.ρ. Outcomes Y1,…,YnY_{1},\dots,Y_{n}Y1​,…,Yn​ of such measurements could be described by a trace regression model in which Eρ(Yj∣Xj)=tr(ρXj),j=1,…,n.\mathbb{E}_{\rho}(Y_{j}|X_{j})={\rm tr}(\rho X_{j}),j=1,\dots,n.Eρ​(Yj​∣Xj​)=tr(ρXj​),j=1,…,n. The design variables X1,…,XnX_{1},\dots,X_{n}X1​,…,Xn​ are often sampled at random from the uniform distribution in an orthonormal basis {E1,…,Em2}\{E_{1},\dots,E_{m^{2}}\}{E1​,…,Em2​} of Hm\mathbb{H}_{m}Hm​ (such as Pauli basis). The goal is to estimate the unknown density matrix ρ\rhoρ based on the data (X1,Y1),…,(Xn,Yn).(X_{1},Y_{1}),\dots,(X_{n},Y_{n}).(X1​,Y1​),…,(Xn​,Yn​). Let Z^:=m2n∑j=1nYjXj\hat{Z}:=\frac{m^{2}}{n}\sum_{j=1}^{n}Y_{j}X_{j}Z^:=nm2​∑j=1n​Yj​Xj​ and let ρˇ\check{\rho}ρˇ​ be the projection of Z^\hat{Z}Z^ onto the convex set Sm\mathcal{S}_{m}Sm​ of density matrices. It is shown that for estimator ρˇ\check{\rho}ρˇ​ the minimax lower bounds in classes of low rank density matrices (established earlier) are attained up logarithmic factors for all Schatten ppp-norm distances, p∈[1,∞]p\in[1,\infty]p∈[1,∞] and for Bures version of quantum Hellinger distance. Moreover, for a slightly modified version of estimator ρˇ\check{\rho}ρˇ​ the same property holds also for quantum relative entropy (Kullback-Leibler) distance between density matrices.
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(log⁡2n)O(\log^2 n)O(log2n) parallel time with a total cost of O(nω+1)O(n^{ω+1})O(nω+1) Boolean operations. This Boolean complexity matches the best known rigorous O(log⁡2n)O(\log^2 n)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π))(\mod (2π))(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(log⁡2n)O(\log^2 n)O(log2n) parallel time and O(nω)O(n^ω)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.
One-parameter interpolations between any two unitary matrices (e.g., quantum gates) U1U_1U1​ and U2U_2U2​ along efficient paths contained in the unitary group are constructed. Motivated by applications, we propose the continuous unitary path U(θ)U(θ)U(θ) obtained from the QR-factorization U(θ)R(θ)=(1−θ)A+θB, U(θ)R(θ)=(1-θ)A+θB, U(θ)R(θ)=(1−θ)A+θB, where U1R1=AU_1 R_1=AU1​R1​=A and U2R2=BU_2 R_2=BU2​R2​=B are the QR-factorizations of AAA and BBB, and U(θ)U(θ)U(θ) is a unitary for all θθθ with U(0)=U1U(0)=U_1U(0)=U1​ and U(1)=U2U(1)=U_2U(1)=U2​. The QR-algorithm is modified to, instead of U(θ)U(θ)U(θ), output a matrix whose columns are proportional to the corresponding columns of U(θ)U(θ)U(θ) and whose entries are polynomial or rational functions of θθθ. By an extension of the Berlekamp-Welch algorithm we show that rational functions can be efficiently and exactly interpolated with respect to θθθ. We then construct probability distributions over unitaries that are arbitrarily close to the Haar measure. Demonstration of computational advantages of NISQ over classical computers is an imperative near-term goal, especially with the exuberant experimental frontier in academia and industry (e.g., IBM and Google). A candidate for quantum computational supremacy is Random Circuit Sampling (RCS), which is the task of sampling from the output distribution of a random circuit. The aforementioned mathematical results provide a new way of scrambling quantum circuits and are applied to prove that exact RCS is #P\#P#P-Hard on average, which is a simpler alternative to Bouland et al's. (Dis)Proving the quantum supremacy conjecture requires "approximate" average case hardness; this remains an open problem for all quantum supremacy proposals.
Random unitary matrices find a number of applications in quantum information science, and are central to the recently defined boson sampling algorithm for photons in linear optics. We describe an operationally simple method to directly implement Haar random unitary matrices in optical circuits, with no requirement for prior or explicit matrix calculations. Our physically motivated and compact representation directly maps independent probability density functions for parameters in Haar random unitary matrices, to optical circuit components. We go on to extend the results to the case of random unitaries for qubits.