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:2610.03582

Robustness of quantum spectrum estimation: weak Schur sampling under noisy inputs

Vladyslav Visnevskyi, Laura Mančinska

quant-phcs.ITmath.RTSubmitted Oct 2, 2026• Announced Oct 5, 2026• 0 citations
v1 · Oct 2, 2026v2 · Oct 5, 2026v3 · Oct 15, 2026
arXivHTMLPDF

Abstract

We initiate the study of weak Schur sampling (WSS) under noisy input. Many optimal quantum learning algorithms rely on this measurement, for instance in such fundamental tasks as quantum spectrum estimation (QSE) and quantum state tomography (QST). The standard analysis of WSS, QSE and QST assumes that the $n$ input copies of the target state $ρ$ are identical. We study what happens when they are not, a more realistic noisy scenario that breaks the very permutation symmetry on which WSS is built. In the simplest noise model, the copies are independent but not necessarily identical, i.e. they form a product state, and each is $ε$-close in trace distance to the $d$-dimensional target state $ρ$. A naive data-processing argument lets the per-copy errors accumulate to $nε$ on measurement output, growing with the input size. We prove that they do not accumulate: the expected output error in total variation is at most $ε+η(n,d)$, where $η(n,d)=O(d/\sqrt n)$ is the noiseless error, and the additive noise term $ε$ is optimal. Beyond noisy product states, for arbitrary inputs $ω$ we show that the outcome observables of WSS are $1/n$-Lipschitz with respect to the quantum Wasserstein distance $W_1$ of De Palma et al., so the error is at most $η(n,d)+\frac{1}{n}\|ω-ρ^{\otimes n}\|_{W_1}$. In particular, our results imply, for the first time, noise-robustness of Keyl and Werner's seminal algorithm for QSE, more than two decades after its introduction. Within our model of robustness, the promise cannot be weakened to closeness of single-copy marginals or to a global trace-distance budget alone, since in both cases some noisy inputs defeat every measurement and estimator. Our results are a necessary step towards optimal quantum learning in practice, and help make progress towards robustness of many other problems in quantum information theory.

Related papers

An Optimal Tradeoff between Entanglement and Copy Complexity for State Tomography

Sitan Chen, Jerry Zheng Li, Allen Liu

There has been significant interest in understanding how practical constraints on contemporary quantum devices impact the complexity of quantum learning. For the classic question of tomography, recent work tightly characterized the copy complexity for any protocol that can only measure one copy of the unknown state at a time, showing it is polynomially worse than if one can make fully-entangled measurements. While we now have a fairly complete picture of the rates for such tasks in the near-term and fault-tolerant regimes, it remains poorly understood what the landscape in between these extremes looks like, and in particular how to gracefully scale up our protocols as we transition away from NISQ. In this work, we study tomography in the natural setting where one can make measurements of t copies at a time. For sufficiently small є, we show that for any t ≤ d2, Θ(d3/√tє2) copies are necessary and sufficient to learn an unknown d-dimensional state ρ to trace distance є. This gives a smooth and optimal interpolation between the known rates for single-copy measurements and fully-entangled measurements. To our knowledge, this is the first smooth entanglement-copy tradeoff known for any quantum learning task, and for tomography, no intermediate point on this curve was known, even at t = 2. An important obstacle is that unlike the optimal single-copy protocol, the optimal fully-entangled protocol is inherently a biased estimator. This bias precludes naive batching approaches for interpolating between the two protocols. Instead, we devise a novel two-stage procedure that uses Keyl’s algorithm to refine a crude estimate for ρ based on single-copy measurements. A key insight is to use Schur-Weyl sampling not to estimate the spectrum of ρ, but to estimate the deviation of ρ from the maximally mixed state. When ρ is far from the maximally mixed state, we devise a novel quantum splitting procedure that reduces to the case where ρ is close to maximally mixed.

arXiv:2402.16353•ACM Symposium on Theory of Computing (STOC)•Jun 10, 2024•11 citations

A Unified Framework for Sample Complexity of Structured Quantum State Tomography under Noisy Observations

Zhen Qin

Quantum state tomography (QST) has attracted considerable attention due to its fundamental role in quantum information processing. In this paper, we develop a unified theoretical framework for analyzing the sample complexity of structured QST under noisy observations arising from state preparation noise, measurement noise, and finite-shot statistical noise. The proposed framework applies to a broad family of structured quantum-state classes, including general mixed states, sparse states, low-rank states, matrix product states (MPSs), matrix product operators (MPOs), projected entangled-pair states (PEPSs), and projected entangled-pair operators (PEPOs), while further introducing physically consistent structured models---including low-rank and sparse states, low-rank MPOs (LR-MPOs), and low-rank PEPOs (LR-PEPOs)---that simultaneously exploit low-dimensional structures and preserve the physical constraint. Within this framework, we derive unified non-asymptotic sample complexity guarantees for two constrained least-squares estimators under noisy observations: a noise-aware estimator that incorporates the calibrated noise model and a noise-unaware estimator based on the ideal Born measurement model. For the noise-aware estimator, we derive unified trace-norm recovery guarantees that explicitly characterize the dependence of the sample complexity on three fundamental quantities: the complexity of the underlying structured state class, the complexity of the measurement ensemble, and the state preparation and measurement noise levels. For the noise-unaware estimator, we establish a unified non-asymptotic recovery guarantee consisting of a statistical error term and an additional deterministic bias term arising from the mismatch between the assumed reconstruction model and the noisy observation process.

quant-pharXiv:2608.05526•Aug 7, 2026•0 citations

Adversarially Robust Quantum State Learning and Testing

Maryam Aliakbarpour, Vladimir Braverman, Nai-Hui Chia +1 more

Quantum state learning is a fundamental problem in physics and computer science. As near-term quantum devices are error-prone, it is important to design error-resistant algorithms. Apart from device errors, other unexpected factors could also affect the algorithm, such as careless human read-out error, or even a malicious hacker deliberately altering the measurement results. Thus, we want our algorithm to work even in the worst case when things go against our favor.We consider the practical setting of single-copy measurements and propose the $\gamma$-adversarial corruption model where an imaginary adversary can arbitrarily change $\gamma$-fraction of the measurement outcomes. This is stronger than the $\gamma$-bounded SPAM noise model, where the post-measurement state changes by at most $\gamma$ in trace distance. Under our stronger model of corruption, we design an algorithm using non-adaptive measurements that can learn an unknown rank- r state up to $\tilde{O}(\gamma \sqrt{r})$ in trace distance, provided that the number of copies is sufficiently large. We further prove an information-theoretic lower bound of $\Omega(\gamma \sqrt{r})$ for non-adaptive measurements, demonstrating the optimality of our algorithm. Our upper and lower bounds also hold for quantum state testing, where the goal is to test whether an unknown state is equal to a given state or far from it. Our results are intriguingly optimistic and pessimistic at the same time. For general states, the error is dimension-dependent and $\gamma \sqrt{d}$ in the worst case, meaning that only corrupting a very small fraction $(1 / \sqrt{d})$ of the outcomes could totally destroy any non-adaptive learning algorithm. However, for constant-rank states that are useful in many quantum algorithms, it is possible to achieve dimension-independent error, even in the worst-case adversarial setting.

arXiv:2508.13959•Annual Symposium on Foundations of Computer Science•Dec 14, 2025•0 citations

The Keyl-Werner algorithm is not optimal for spectrum estimation

Angelos Pelecanos, Jack Spilecki, Ewin Tang +1 more

We give an algorithm which, given $n = O(d^2 \cdot (\log\log(d)/\log(d))^2)$ copies of $ρ$, estimates the eigenvalues of $ρ$ to constant error in total variation distance. Thus, we can learn the eigenvalues of a quantum state with fewer copies than the $Θ(d^2)$ needed to run full state tomography. This is the first improvement to spectrum estimation over the influential Keyl-Werner algorithm, which uses $n = Θ(d^2)$ copies, thereby resolving a question raised by Keyl and Werner in 2001 and refuting a 2016 conjecture of Wright. Our main technical tool is a new tomography guarantee, where the error of tomography in a particular direction $|w\rangle$ scales with $\langle w | ρ|w\rangle$ for all directions simultaneously. From this stronger "relative-error" bound, we recover better algorithms for principal component analysis in Bures distance and tomography in $χ^2$-divergence as corollaries.

quant-pharXiv:2607.27117•Jul 30, 2026•0 citations

Weak Schur sampling with logarithmic quantum memory

Enrique Cervero-Martí­n, Laura Mančinska

The quantum Schur transform maps the computational basis of a system of $n$ qudits onto a \textit{Schur basis}, which spans the minimal invariant subspaces of the representations of the unitary and the symmetric groups acting on the state space of $n$ $d$-level systems. We introduce a new algorithm for the task of weak Schur sampling. Our algorithm efficiently determines both the Young label which indexes the irreducible representations and the multiplicity label of the symmetric group. There are two major advantages of our algorithm for weak Schur sampling when compared to existing approaches which proceed via quantum Schur transform algorithm or Generalized Phase Estimation algorithm. First, our algorihtm is suitable for streaming applications and second it is exponentially more efficient in its memory usage. We show that an instance of our weak Schur sampling algorithm on $n$ qubits to accuracy $ε$ requires only $O(\log_2n)$ qubits of memory and $O(n^3\log_2(\frac{n}ε))$ gates from the Clifford+T set. Further, we show that our weak Schur sampling algorithm on $n$ qudits decomposes into $O\big(dn^{2d}\log_2^p\big(\frac{n^{2d}}ε\big)\big)$ gates from an arbitrary fault-tolerant qudit universal set, for $p\approx 4$, and requires a memory of $O(\log_dn)$ qudits to implement.

arXiv:2309.11947•Sep 21, 2023•0 citations

Robust quantum minimum finding with an application to hypothesis selection

Yihui Quek, Clément L. Canonne, Patrick Rebentrost

We consider the problem of finding the minimum element in a list of length $N$ using a noisy comparator. The noise is modelled as follows: given two elements to compare, if the values of the elements differ by at least $α$ by some metric defined on the elements, then the comparison will be made correctly; if the values of the elements are closer than $α$, the outcome of the comparison is not subject to any guarantees. We demonstrate a quantum algorithm for noisy quantum minimum-finding that preserves the quadratic speedup of the noiseless case: our algorithm runs in time $\tilde O(\sqrt{N (1+Δ)})$, where $Δ$ is an upper-bound on the number of elements within the interval $α$, and outputs a good approximation of the true minimum with high probability. Our noisy comparator model is motivated by the problem of hypothesis selection, where given a set of $N$ known candidate probability distributions and samples from an unknown target distribution, one seeks to output some candidate distribution $O(\varepsilon)$-close to the unknown target. Much work on the classical front has been devoted to speeding up the run time of classical hypothesis selection from $O(N^2)$ to $O(N)$, in part by using statistical primitives such as the Scheffé test. Assuming a quantum oracle generalization of the classical data access and applying our noisy quantum minimum-finding algorithm, we take this run time into the sublinear regime. The final expected run time is $\tilde O( \sqrt{N(1+Δ)})$, with the same $O(\log N)$ sample complexity from the unknown distribution as the classical algorithm. We expect robust quantum minimum-finding to be a useful building block for algorithms in situations where the comparator (which may be another quantum or classical algorithm) is resolution-limited or subject to some uncertainty.

arXiv:2003.11777•Mar 26, 2020•4 citations
We initiate the study of weak Schur sampling (WSS) under noisy input. Many optimal quantum learning algorithms rely on this measurement, for instance in such fundamental tasks as quantum spectrum estimation (QSE) and quantum state tomography (QST). The standard analysis of WSS, QSE and QST assumes that the nnn input copies of the target state ρρρ are identical. We study what happens when they are not, a more realistic noisy scenario that breaks the very permutation symmetry on which WSS is built. In the simplest noise model, the copies are independent but not necessarily identical, i.e. they form a product state, and each is εεε-close in trace distance to the ddd-dimensional target state ρρρ. A naive data-processing argument lets the per-copy errors accumulate to nεnεnε on measurement output, growing with the input size. We prove that they do not accumulate: the expected output error in total variation is at most ε+η(n,d)ε+η(n,d)ε+η(n,d), where η(n,d)=O(d/n)η(n,d)=O(d/\sqrt n)η(n,d)=O(d/n​) is the noiseless error, and the additive noise term εεε is optimal. Beyond noisy product states, for arbitrary inputs ωωω we show that the outcome observables of WSS are 1/n1/n1/n-Lipschitz with respect to the quantum Wasserstein distance W1W_1W1​ of De Palma et al., so the error is at most η(n,d)+1n∥ω−ρ⊗n∥W1η(n,d)+\frac{1}{n}\|ω-ρ^{\otimes n}\|_{W_1}η(n,d)+n1​∥ω−ρ⊗n∥W1​​. In particular, our results imply, for the first time, noise-robustness of Keyl and Werner's seminal algorithm for QSE, more than two decades after its introduction. Within our model of robustness, the promise cannot be weakened to closeness of single-copy marginals or to a global trace-distance budget alone, since in both cases some noisy inputs defeat every measurement and estimator. Our results are a necessary step towards optimal quantum learning in practice, and help make progress towards robustness of many other problems in quantum information theory.
There has been significant interest in understanding how practical constraints on contemporary quantum devices impact the complexity of quantum learning. For the classic question of tomography, recent work tightly characterized the copy complexity for any protocol that can only measure one copy of the unknown state at a time, showing it is polynomially worse than if one can make fully-entangled measurements. While we now have a fairly complete picture of the rates for such tasks in the near-term and fault-tolerant regimes, it remains poorly understood what the landscape in between these extremes looks like, and in particular how to gracefully scale up our protocols as we transition away from NISQ. In this work, we study tomography in the natural setting where one can make measurements of t copies at a time. For sufficiently small є, we show that for any t ≤ d2, Θ(d3/√tє2) copies are necessary and sufficient to learn an unknown d-dimensional state ρ to trace distance є. This gives a smooth and optimal interpolation between the known rates for single-copy measurements and fully-entangled measurements. To our knowledge, this is the first smooth entanglement-copy tradeoff known for any quantum learning task, and for tomography, no intermediate point on this curve was known, even at t = 2. An important obstacle is that unlike the optimal single-copy protocol, the optimal fully-entangled protocol is inherently a biased estimator. This bias precludes naive batching approaches for interpolating between the two protocols. Instead, we devise a novel two-stage procedure that uses Keyl’s algorithm to refine a crude estimate for ρ based on single-copy measurements. A key insight is to use Schur-Weyl sampling not to estimate the spectrum of ρ, but to estimate the deviation of ρ from the maximally mixed state. When ρ is far from the maximally mixed state, we devise a novel quantum splitting procedure that reduces to the case where ρ is close to maximally mixed.
Quantum state tomography (QST) has attracted considerable attention due to its fundamental role in quantum information processing. In this paper, we develop a unified theoretical framework for analyzing the sample complexity of structured QST under noisy observations arising from state preparation noise, measurement noise, and finite-shot statistical noise. The proposed framework applies to a broad family of structured quantum-state classes, including general mixed states, sparse states, low-rank states, matrix product states (MPSs), matrix product operators (MPOs), projected entangled-pair states (PEPSs), and projected entangled-pair operators (PEPOs), while further introducing physically consistent structured models---including low-rank and sparse states, low-rank MPOs (LR-MPOs), and low-rank PEPOs (LR-PEPOs)---that simultaneously exploit low-dimensional structures and preserve the physical constraint. Within this framework, we derive unified non-asymptotic sample complexity guarantees for two constrained least-squares estimators under noisy observations: a noise-aware estimator that incorporates the calibrated noise model and a noise-unaware estimator based on the ideal Born measurement model. For the noise-aware estimator, we derive unified trace-norm recovery guarantees that explicitly characterize the dependence of the sample complexity on three fundamental quantities: the complexity of the underlying structured state class, the complexity of the measurement ensemble, and the state preparation and measurement noise levels. For the noise-unaware estimator, we establish a unified non-asymptotic recovery guarantee consisting of a statistical error term and an additional deterministic bias term arising from the mismatch between the assumed reconstruction model and the noisy observation process.
Quantum state learning is a fundamental problem in physics and computer science. As near-term quantum devices are error-prone, it is important to design error-resistant algorithms. Apart from device errors, other unexpected factors could also affect the algorithm, such as careless human read-out error, or even a malicious hacker deliberately altering the measurement results. Thus, we want our algorithm to work even in the worst case when things go against our favor.We consider the practical setting of single-copy measurements and propose the γ\gammaγ-adversarial corruption model where an imaginary adversary can arbitrarily change γ\gammaγ-fraction of the measurement outcomes. This is stronger than the γ\gammaγ-bounded SPAM noise model, where the post-measurement state changes by at most γ\gammaγ in trace distance. Under our stronger model of corruption, we design an algorithm using non-adaptive measurements that can learn an unknown rank- r state up to O~(γr)\tilde{O}(\gamma \sqrt{r})O~(γr​) in trace distance, provided that the number of copies is sufficiently large. We further prove an information-theoretic lower bound of Ω(γr)\Omega(\gamma \sqrt{r})Ω(γr​) for non-adaptive measurements, demonstrating the optimality of our algorithm. Our upper and lower bounds also hold for quantum state testing, where the goal is to test whether an unknown state is equal to a given state or far from it. Our results are intriguingly optimistic and pessimistic at the same time. For general states, the error is dimension-dependent and γd\gamma \sqrt{d}γd​ in the worst case, meaning that only corrupting a very small fraction (1/d)(1 / \sqrt{d})(1/d​) of the outcomes could totally destroy any non-adaptive learning algorithm. However, for constant-rank states that are useful in many quantum algorithms, it is possible to achieve dimension-independent error, even in the worst-case adversarial setting.
We give an algorithm which, given n=O(d2⋅(log⁡log⁡(d)/log⁡(d))2)n = O(d^2 \cdot (\log\log(d)/\log(d))^2)n=O(d2⋅(loglog(d)/log(d))2) copies of ρρρ, estimates the eigenvalues of ρρρ to constant error in total variation distance. Thus, we can learn the eigenvalues of a quantum state with fewer copies than the Θ(d2)Θ(d^2)Θ(d2) needed to run full state tomography. This is the first improvement to spectrum estimation over the influential Keyl-Werner algorithm, which uses n=Θ(d2)n = Θ(d^2)n=Θ(d2) copies, thereby resolving a question raised by Keyl and Werner in 2001 and refuting a 2016 conjecture of Wright. Our main technical tool is a new tomography guarantee, where the error of tomography in a particular direction ∣w⟩|w\rangle∣w⟩ scales with ⟨w∣ρ∣w⟩\langle w | ρ|w\rangle⟨w∣ρ∣w⟩ for all directions simultaneously. From this stronger "relative-error" bound, we recover better algorithms for principal component analysis in Bures distance and tomography in χ2χ^2χ2-divergence as corollaries.
The quantum Schur transform maps the computational basis of a system of nnn qudits onto a \textit{Schur basis}, which spans the minimal invariant subspaces of the representations of the unitary and the symmetric groups acting on the state space of nnn ddd-level systems. We introduce a new algorithm for the task of weak Schur sampling. Our algorithm efficiently determines both the Young label which indexes the irreducible representations and the multiplicity label of the symmetric group. There are two major advantages of our algorithm for weak Schur sampling when compared to existing approaches which proceed via quantum Schur transform algorithm or Generalized Phase Estimation algorithm. First, our algorihtm is suitable for streaming applications and second it is exponentially more efficient in its memory usage. We show that an instance of our weak Schur sampling algorithm on nnn qubits to accuracy εεε requires only O(log⁡2n)O(\log_2n)O(log2​n) qubits of memory and O(n3log⁡2(nε))O(n^3\log_2(\frac{n}ε))O(n3log2​(εn​)) gates from the Clifford+T set. Further, we show that our weak Schur sampling algorithm on nnn qudits decomposes into O(dn2dlog⁡2p(n2dε))O\big(dn^{2d}\log_2^p\big(\frac{n^{2d}}ε\big)\big)O(dn2dlog2p​(εn2d​)) gates from an arbitrary fault-tolerant qudit universal set, for p≈4p\approx 4p≈4, and requires a memory of O(log⁡dn)O(\log_dn)O(logd​n) qudits to implement.
We consider the problem of finding the minimum element in a list of length NNN using a noisy comparator. The noise is modelled as follows: given two elements to compare, if the values of the elements differ by at least ααα by some metric defined on the elements, then the comparison will be made correctly; if the values of the elements are closer than ααα, the outcome of the comparison is not subject to any guarantees. We demonstrate a quantum algorithm for noisy quantum minimum-finding that preserves the quadratic speedup of the noiseless case: our algorithm runs in time O~(N(1+Δ))\tilde O(\sqrt{N (1+Δ)})O~(N(1+Δ)​), where ΔΔΔ is an upper-bound on the number of elements within the interval ααα, and outputs a good approximation of the true minimum with high probability. Our noisy comparator model is motivated by the problem of hypothesis selection, where given a set of NNN known candidate probability distributions and samples from an unknown target distribution, one seeks to output some candidate distribution O(ε)O(\varepsilon)O(ε)-close to the unknown target. Much work on the classical front has been devoted to speeding up the run time of classical hypothesis selection from O(N2)O(N^2)O(N2) to O(N)O(N)O(N), in part by using statistical primitives such as the Scheffé test. Assuming a quantum oracle generalization of the classical data access and applying our noisy quantum minimum-finding algorithm, we take this run time into the sublinear regime. The final expected run time is O~(N(1+Δ))\tilde O( \sqrt{N(1+Δ)})O~(N(1+Δ)​), with the same O(log⁡N)O(\log N)O(logN) sample complexity from the unknown distribution as the classical algorithm. We expect robust quantum minimum-finding to be a useful building block for algorithms in situations where the comparator (which may be another quantum or classical algorithm) is resolution-limited or subject to some uncertainty.