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• 9 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•64 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

On the Hardness of Approximate Quantum Circuit Membership and Optimization

Adam Husted Kjelstrøm, Jaco van de Pol, Andreas Pavlogiannis

Quantum circuit optimization is an indispensable component of the quantum software stack, used to reduce noise, maximize performance, alleviate costs of quantum error correction, or target specific hardware. A related problem is approximate membership: for a fixed set of unitaries $S$, decide whether a given circuit $C$ is within distance $\varepsilon$ of a unitary in $S$ under some metric $m$. Membership is a special case of optimization, where $S$ is a set of unitaries implementable at no cost (e.g., with noise-minimal circuits, or without magic states). Janzing, Wocjan, and Beth (Int. J. Quantum Inf., 2005) showed that, for the operator metric, the case $S=\{I\}$ (approximate identity) is QMA-complete when $C$ is promised to be either close to the identity or far from it. We generalize this setting in three directions: (i) promise-free inputs, (ii) besides $S=\{I\}$, sets $S$ containing only Clifford unitaries, or only generalized permutation matrices (i.e., no superposition), and (iii) the trace-based, spectral, and operator metrics. We show that, in all cases, approximate membership is PP-hard for wide ranges of $\varepsilon$, provided $C$'s gate-set can implement Clifford+T, as the gate-sets of standard hardware do. If $S=\{I\}$, or if $S$ contains only generalized permutation matrices, $I\in S$, and $m$ is a trace-based distance, PP-hardness holds for all non-trivial $\varepsilon$. If $S=\{I\}$ and $m$ is a trace-based distance, PP-hardness holds even for circuits over classical-reversible gate-sets. Our results indicate that approximate membership is harder over promise-free inputs than the QMA-complete promise version, and that this hardness persists across quantum resources (any gates, non-Clifford, superposition) and distance metrics. They directly imply PP-hardness of circuit optimization when minimizing total, non-Clifford, or superposition gate depth or count.

quant-pharXiv:2611.04381•Nov 4, 2026•0 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•13 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

QAOA-PCA: Enhancing Efficiency in the Quantum Approximate Optimization Algorithm via Principal Component Analysis

Owain Parry, Phil McMinn

The Quantum Approximate Optimization Algorithm (QAOA) is a promising variational algorithm for solving combinatorial optimization problems on near-term devices. However, as the number of layers in a QAOA circuit increases, which is correlated with the quality of the solution, the number of parameters to optimize grows linearly. This results in more iterations required by the classical optimizer, which results in an increasing computational burden as more circuit executions are needed. To mitigate this issue, we introduce QAOA-PCA, a novel reparameterization technique that employs Principal Component Analysis (PCA) to reduce the dimensionality of the QAOA parameter space. By extracting principal components from optimized parameters of smaller problem instances, QAOA-PCA facilitates efficient optimization with fewer parameters on larger instances. Our empirical evaluation on the prominent MaxCut problem demonstrates that QAOA-PCA consistently requires fewer iterations than standard QAOA, achieving substantial efficiency gains. While this comes at the cost of a slight reduction in approximation ratio compared to QAOA with the same number of layers, QAOA-PCA almost always outperforms standard QAOA when matched by parameter count. QAOA-PCA strikes a favorable balance between efficiency and performance, reducing optimization overhead without significantly compromising solution quality.

arXiv:2504.16755•International Conference on Evaluation and Assessment in Software Engineering (EASE)•Jun 17, 2025•2 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.
Quantum circuit optimization is an indispensable component of the quantum software stack, used to reduce noise, maximize performance, alleviate costs of quantum error correction, or target specific hardware. A related problem is approximate membership: for a fixed set of unitaries SSS, decide whether a given circuit CCC is within distance ε\varepsilonε of a unitary in SSS under some metric mmm. Membership is a special case of optimization, where SSS is a set of unitaries implementable at no cost (e.g., with noise-minimal circuits, or without magic states). Janzing, Wocjan, and Beth (Int. J. Quantum Inf., 2005) showed that, for the operator metric, the case S={I}S=\{I\}S={I} (approximate identity) is QMA-complete when CCC is promised to be either close to the identity or far from it. We generalize this setting in three directions: (i) promise-free inputs, (ii) besides S={I}S=\{I\}S={I}, sets SSS containing only Clifford unitaries, or only generalized permutation matrices (i.e., no superposition), and (iii) the trace-based, spectral, and operator metrics. We show that, in all cases, approximate membership is PP-hard for wide ranges of ε\varepsilonε, provided CCC's gate-set can implement Clifford+T, as the gate-sets of standard hardware do. If S={I}S=\{I\}S={I}, or if SSS contains only generalized permutation matrices, I∈SI\in SI∈S, and mmm is a trace-based distance, PP-hardness holds for all non-trivial ε\varepsilonε. If S={I}S=\{I\}S={I} and mmm is a trace-based distance, PP-hardness holds even for circuits over classical-reversible gate-sets. Our results indicate that approximate membership is harder over promise-free inputs than the QMA-complete promise version, and that this hardness persists across quantum resources (any gates, non-Clifford, superposition) and distance metrics. They directly imply PP-hardness of circuit optimization when minimizing total, non-Clifford, or superposition gate depth or count.
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.
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.
The Quantum Approximate Optimization Algorithm (QAOA) is a promising variational algorithm for solving combinatorial optimization problems on near-term devices. However, as the number of layers in a QAOA circuit increases, which is correlated with the quality of the solution, the number of parameters to optimize grows linearly. This results in more iterations required by the classical optimizer, which results in an increasing computational burden as more circuit executions are needed. To mitigate this issue, we introduce QAOA-PCA, a novel reparameterization technique that employs Principal Component Analysis (PCA) to reduce the dimensionality of the QAOA parameter space. By extracting principal components from optimized parameters of smaller problem instances, QAOA-PCA facilitates efficient optimization with fewer parameters on larger instances. Our empirical evaluation on the prominent MaxCut problem demonstrates that QAOA-PCA consistently requires fewer iterations than standard QAOA, achieving substantial efficiency gains. While this comes at the cost of a slight reduction in approximation ratio compared to QAOA with the same number of layers, QAOA-PCA almost always outperforms standard QAOA when matched by parameter count. QAOA-PCA strikes a favorable balance between efficiency and performance, reducing optimization overhead without significantly compromising solution quality.