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

arXiv:2203.00811

The quantum low-rank approximation problem

Nic Ezzell, Zoë Holmes, Patrick J. Coles

Published Mar 2, 2022• 3 citations
arXivHTMLPDF

Abstract

We consider a quantum version of the famous low-rank approximation problem. Specifically, we consider the distance $D(ρ,σ)$ between two normalized quantum states, $ρ$ and $σ$, where the rank of $σ$ is constrained to be at most $R$. For both the trace distance and Hilbert-Schmidt distance, we analytically solve for the optimal state $σ$ that minimizes this distance. For the Hilbert-Schmidt distance, the unique optimal state is $σ= τ_R +N_R$, where $τ_R = Π_R ρΠ_R$ is given by projecting $ρ$ onto its $R$ principal components with projector $Π_R$, and $N_R$ is a normalization factor given by $N_R = \frac{1- \text{Tr}(τ_R)}{R}Π_R$. For the trace distance, this state is also optimal but not uniquely optimal, and we provide the full set of states that are optimal. We briefly discuss how our results have application for performing principal component analysis (PCA) via variational optimization on quantum computers.

DOI
10.48550/arxiv.2203.00811

Related papers

Strong bound between trace distance and Hilbert-Schmidt distance for low-rank states

Patrick J. Coles, Marco Cerezo, Łukasz Cincio

The trace distance between two quantum states, $\ensuremath{\rho}$ and $\ensuremath{\sigma}$, is an operationally meaningful quantity in quantum information theory. However, in general it is difficult to compute, involving the diagonalization of $\ensuremath{\rho}\ensuremath{-}\ensuremath{\sigma}$. In contrast, the Hilbert-Schmidt distance can be computed without diagonalization, although it is less operationally significant. Here, we relate the trace distance and the Hilbert-Schmidt distance with a bound that is particularly strong when either $\ensuremath{\rho}$ or $\ensuremath{\sigma}$ is low rank. Our bound is stronger than the bound one could obtain via the norm equivalence of the Frobenius and trace norms. We also consider bounds that are useful not only for low-rank states but also for low-entropy states. Our results have relevance to quantum information theory, quantum algorithm design, and quantum complexity theory.

arXiv:1903.11738•Physical Review A•Aug 6, 2019•53 citations

Approximating quantum states by states of low rank

Nathaniel Johnston, Chi-Kwong Li

Given a positive integer k , it is natural to ask for a formula for the distance between a given density matrix (i.e., mixed quantum state) and the set of density matrices of rank at most k . This problem has already been solved when “distance” is measured in the trace or Frobenius norm. We solve it for all other unitary similarity invariant norms. We also present some consequences of our formula. For example, in the trace and Frobenius norms, the density matrix that is farthest from the set of low-rank density matrices is the maximally-mixed state, but this is not true in many other unitary similarity invariant norms.

arXiv:2510.08463•Linear Algebra and its Applications•Jan 1, 2026•0 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•16 citations

Resource-efficient quantum principal component analysis

Youle Wang, Yu H. Luo

Abstract Principal component analysis (PCA) is an important dimensionality reduction method in machine learning and data analysis. Recently, the quantum version of PCA has been established to diagonalize quantum states. Although these quantum algorithms promise quantum advantages, they require substantial resources beyond the reach of state-of-the-art quantum technologies. This work aims to reduce resource requirements and improve the efficiency of quantum PCA. Assuming that the quantum state is accessed through a purified quantum query model and a sampling model, we propose quantum algorithms that use minimal resource requirements for ancillary qubits to reveal properties of eigenvectors and eigenvalues of a state. In particular, we show that estimating eigenvalue λ with error ε and success probability larger than λ ( 1 − η ) requests a query complexity O ~ ( ϵ − 1 ) and a sample complexity O ~ ( ϵ − 2 η − 1 ) , respectively. To our knowledge, our result is the first quantum speedup that achieves asymptotic linear scaling in 1 / ϵ for quantum PCA. As applications, we discuss estimating the minimum relative entropy of entanglement of bipartite pure-states and performing quantum state discrimination tasks. We show that quantum speedups are maintained when the pure state has a low Schmidt number and states of discrimination have a low rank. This study opens up a new quantum PCA method for high-dimensional quantum data analysis and discusses its application in quantum information processing tasks.

Quantum Science and Technology•May 2, 2024•11 citations

Optimal Estimation of Low Rank Density Matrices

Vladimir I. Koltchinskii, Dong Xia

The density matrices are positively semi-definite Hermitian matrices of unit trace that describe the state of a quantum system. The goal of the paper is to develop minimax lower bounds on error rates of estimation of low rank density matrices in trace regression models used in quantum state tomography (in particular, in the case of Pauli measurements) with explicit dependence of the bounds on the rank and other complexity parameters. Such bounds are established for several statistically relevant distances, including quantum versions of Kullback-Leibler divergence (relative entropy distance) and of Hellinger distance (so called Bures distance), and Schatten $p$-norm distances. Sharp upper bounds and oracle inequalities for least squares estimator with von Neumann entropy penalization are obtained showing that minimax lower bounds are attained (up to logarithmic factors) for these distances.

arXiv:1507.05131•Jul 17, 2015•26 citations

Quantum SDP Solvers: Large Speed-Ups, Optimality, and Applications to Quantum Learning

Fernando G. S. L. Brandão, Amir Kalev, Tongyang Li +3 more

We give two new quantum algorithms for solving semidefinite programs (SDPs) providing quantum speed-ups. We consider SDP instances with m constraint matrices, each of dimension n, rank at most r, and sparsity s. The first algorithm assumes an input model where one is given access to an oracle to the entries of the matrices at unit cost. We show that it has run time O~(s^2 (sqrt{m} epsilon^{-10} + sqrt{n} epsilon^{-12})), with epsilon the error of the solution. This gives an optimal dependence in terms of m, n and quadratic improvement over previous quantum algorithms (when m ~~ n). The second algorithm assumes a fully quantum input model in which the input matrices are given as quantum states. We show that its run time is O~(sqrt{m}+poly(r))*poly(log m,log n,B,epsilon^{-1}), with B an upper bound on the trace-norm of all input matrices. In particular the complexity depends only polylogarithmically in n and polynomially in r. We apply the second SDP solver to learn a good description of a quantum state with respect to a set of measurements: Given m measurements and a supply of copies of an unknown state rho with rank at most r, we show we can find in time sqrt{m}*poly(log m,log n,r,epsilon^{-1}) a description of the state as a quantum circuit preparing a density matrix which has the same expectation values as rho on the m measurements, up to error epsilon. The density matrix obtained is an approximation to the maximum entropy state consistent with the measurement data considered in Jaynes' principle from statistical mechanics. As in previous work, we obtain our algorithm by "quantizing" classical SDP solvers based on the matrix multiplicative weight update method. One of our main technical contributions is a quantum Gibbs state sampler for low-rank Hamiltonians, given quantum states encoding these Hamiltonians, with a poly-logarithmic dependence on its dimension, which is based on ideas developed in quantum principal component analysis. We also develop a "fast" quantum OR lemma with a quadratic improvement in gate complexity over the construction of Harrow et al. [Harrow et al., 2017]. We believe both techniques might be of independent interest.

•Jan 1, 2019•60 citations
We consider a quantum version of the famous low-rank approximation problem. Specifically, we consider the distance D(ρ,σ)D(ρ,σ)D(ρ,σ) between two normalized quantum states, ρρρ and σσσ, where the rank of σσσ is constrained to be at most RRR. For both the trace distance and Hilbert-Schmidt distance, we analytically solve for the optimal state σσσ that minimizes this distance. For the Hilbert-Schmidt distance, the unique optimal state is σ=τR+NRσ= τ_R +N_Rσ=τR​+NR​, where τR=ΠRρΠRτ_R = Π_R ρΠ_RτR​=ΠR​ρΠR​ is given by projecting ρρρ onto its RRR principal components with projector ΠRΠ_RΠR​, and NRN_RNR​ is a normalization factor given by NR=1−Tr(τR)RΠRN_R = \frac{1- \text{Tr}(τ_R)}{R}Π_RNR​=R1−Tr(τR​)​ΠR​. For the trace distance, this state is also optimal but not uniquely optimal, and we provide the full set of states that are optimal. We briefly discuss how our results have application for performing principal component analysis (PCA) via variational optimization on quantum computers.
The trace distance between two quantum states, $\ensuremath{\rho}$ and $\ensuremath{\sigma}$, is an operationally meaningful quantity in quantum information theory. However, in general it is difficult to compute, involving the diagonalization of $\ensuremath{\rho}\ensuremath{-}\ensuremath{\sigma}$. In contrast, the Hilbert-Schmidt distance can be computed without diagonalization, although it is less operationally significant. Here, we relate the trace distance and the Hilbert-Schmidt distance with a bound that is particularly strong when either $\ensuremath{\rho}$ or $\ensuremath{\sigma}$ is low rank. Our bound is stronger than the bound one could obtain via the norm equivalence of the Frobenius and trace norms. We also consider bounds that are useful not only for low-rank states but also for low-entropy states. Our results have relevance to quantum information theory, quantum algorithm design, and quantum complexity theory.
Given a positive integer k , it is natural to ask for a formula for the distance between a given density matrix (i.e., mixed quantum state) and the set of density matrices of rank at most k . This problem has already been solved when “distance” is measured in the trace or Frobenius norm. We solve it for all other unitary similarity invariant norms. We also present some consequences of our formula. For example, in the trace and Frobenius norms, the density matrix that is farthest from the set of low-rank density matrices is the maximally-mixed state, but this is not true in many other unitary similarity invariant norms.
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.
Abstract Principal component analysis (PCA) is an important dimensionality reduction method in machine learning and data analysis. Recently, the quantum version of PCA has been established to diagonalize quantum states. Although these quantum algorithms promise quantum advantages, they require substantial resources beyond the reach of state-of-the-art quantum technologies. This work aims to reduce resource requirements and improve the efficiency of quantum PCA. Assuming that the quantum state is accessed through a purified quantum query model and a sampling model, we propose quantum algorithms that use minimal resource requirements for ancillary qubits to reveal properties of eigenvectors and eigenvalues of a state. In particular, we show that estimating eigenvalue λ with error ε and success probability larger than λ ( 1 − η ) requests a query complexity O ~ ( ϵ − 1 ) and a sample complexity O ~ ( ϵ − 2 η − 1 ) , respectively. To our knowledge, our result is the first quantum speedup that achieves asymptotic linear scaling in 1 / ϵ for quantum PCA. As applications, we discuss estimating the minimum relative entropy of entanglement of bipartite pure-states and performing quantum state discrimination tasks. We show that quantum speedups are maintained when the pure state has a low Schmidt number and states of discrimination have a low rank. This study opens up a new quantum PCA method for high-dimensional quantum data analysis and discusses its application in quantum information processing tasks.
The density matrices are positively semi-definite Hermitian matrices of unit trace that describe the state of a quantum system. The goal of the paper is to develop minimax lower bounds on error rates of estimation of low rank density matrices in trace regression models used in quantum state tomography (in particular, in the case of Pauli measurements) with explicit dependence of the bounds on the rank and other complexity parameters. Such bounds are established for several statistically relevant distances, including quantum versions of Kullback-Leibler divergence (relative entropy distance) and of Hellinger distance (so called Bures distance), and Schatten ppp-norm distances. Sharp upper bounds and oracle inequalities for least squares estimator with von Neumann entropy penalization are obtained showing that minimax lower bounds are attained (up to logarithmic factors) for these distances.
We give two new quantum algorithms for solving semidefinite programs (SDPs) providing quantum speed-ups. We consider SDP instances with m constraint matrices, each of dimension n, rank at most r, and sparsity s. The first algorithm assumes an input model where one is given access to an oracle to the entries of the matrices at unit cost. We show that it has run time O~(s^2 (sqrt{m} epsilon^{-10} + sqrt{n} epsilon^{-12})), with epsilon the error of the solution. This gives an optimal dependence in terms of m, n and quadratic improvement over previous quantum algorithms (when m ~~ n). The second algorithm assumes a fully quantum input model in which the input matrices are given as quantum states. We show that its run time is O~(sqrt{m}+poly(r))*poly(log m,log n,B,epsilon^{-1}), with B an upper bound on the trace-norm of all input matrices. In particular the complexity depends only polylogarithmically in n and polynomially in r. We apply the second SDP solver to learn a good description of a quantum state with respect to a set of measurements: Given m measurements and a supply of copies of an unknown state rho with rank at most r, we show we can find in time sqrt{m}*poly(log m,log n,r,epsilon^{-1}) a description of the state as a quantum circuit preparing a density matrix which has the same expectation values as rho on the m measurements, up to error epsilon. The density matrix obtained is an approximation to the maximum entropy state consistent with the measurement data considered in Jaynes' principle from statistical mechanics. As in previous work, we obtain our algorithm by "quantizing" classical SDP solvers based on the matrix multiplicative weight update method. One of our main technical contributions is a quantum Gibbs state sampler for low-rank Hamiltonians, given quantum states encoding these Hamiltonians, with a poly-logarithmic dependence on its dimension, which is based on ideas developed in quantum principal component analysis. We also develop a "fast" quantum OR lemma with a quadratic improvement in gate complexity over the construction of Harrow et al. [Harrow et al., 2017]. We believe both techniques might be of independent interest.