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

Lower Bounds on Relative Error Quantum Compression and Classical Shadows

Sankar, Kaushik

Published Jun 26, 2025• 0 citations
arXivHTMLPDF

Abstract

We study the question of how much classical communication is needed when Alice is given a classical description of a quantum state $|ψ\rangle$ for Bob to recover any expectation value $\langle ψ| M |ψ\rangle$ given an observable $M$ with $M$ Hermitian and $||M||_{\text{op}} \leq 1$. This task, whose study was initiated by Raz (ACM 1999) and more recently investigated by Gosset and Smolin (TQC 2019), can be thought of as a fully classical version of the pure state case of the well-known classical shadows problem in quantum learning theory. We show how the hardness of these two seemingly distinct problems are connected. We first consider the relative error version of the communication question and prove a lower bound of $Ω(\sqrt{2^{n}}ε^{-2})$ on the one-way randomized classical communication, improving upon an additive error lower bound of $Ω(\sqrt{2^{n}})$ as shown by Gosset and Smolin. Notably, we show that this lower bound holds not only for the set of all observables but also when restricted to just the class of Pauli observables. This fact implies a $Ω(\sqrt{2^{n}})$ versus $O(\text{poly}(n))$ separation in the compression size between the relative and additive error settings for non-adaptive Pauli classical shadows with classical memory. Extending this framework, we prove randomized communication lower bounds for other relative error one-way classical communication tasks: an $Ω(2^{n}ε^{-2})$ lower bound when instead Alice is given an observable and Bob is given a quantum state and they are asked to estimate the expectation value, an $Ω(\sqrt{n}ε^{-2})$ lower bound when restricted to Paulis, and an $Ω(\sqrt{2^{n}}ε^{-2})$ lower bound when Alice and Bob are both given quantum states and asked to estimate the inner product.

DOI
10.48550/arxiv.2506.21345

Related papers

Sample-optimal classical shadows for pure states

Daniel Grier, Hakop Pashayan, Luke Schaeffer

We consider the classical shadows task for pure states in the setting of both joint and independent measurements. The task is to measure few copies of an unknown pure state ρ in order to learn a classical description which suffices to later estimate expectation values of observables. Specifically, the goal is to approximate Tr(Oρ) for any Hermitian observable O to within additive error ϵ provided Tr(O2)≤B and ‖O‖=1 . Our main result applies to the joint measurement setting, where we show Θ~(Bϵ−1+ϵ−2) samples of ρ are necessary and sufficient to succeed with high probability. The upper bound is a quadratic improvement on the previous best sample complexity known for this problem. For the lower bound, we see that the bottleneck is not how fast we can learn the state but rather how much any classical description of ρ can be compressed for observable estimation. In the independent measurement setting, we show that O(Bdϵ−1+ϵ−2) samples suffice. Notably, this implies that the random Clifford measurements algorithm of Huang, Kueng, and Preskill, which is sample-optimal for mixed states, is not optimal for pure states. Interestingly, our result also uses the same random Clifford measurements but employs a different estimator.

arXiv:2211.11810•Quantum•Jun 17, 2024•17 citations

Incompressibility of Classical Distributions

Anurag Anshu, Debbie Leung, Dave Touchette

Inblindcompression of quantum states, a sender Alice is given a specimen of a quantum state$\rho $drawn from a known ensemble (but without knowing what$\rho $is), and she transmits sufficient quantum data to a receiver Bob so that he can decode a near perfect specimen of$\rho $. For many such states drawn iid from the ensemble, the asymptotically achievable rate is the number of qubits required to be transmitted per state. The Holevo information is a lower bound for the achievable rate, and is attained for pure state ensembles, or in the related scenario of entanglement-assistedvisiblecompression of mixed states wherein Alice knows what state is drawn. In this paper, we prove a general and robust lower bound on the achievable rate for ensembles of classical states, which holds even in the least demanding setting when Alice and Bob share free entanglement and a constant per-copy error is allowed. We apply the bound to aspecificensemble of only two states and prove a near-maximal separation (saturating the dimension bound in leading order) between the best achievable rate and the Holevo information for constant error. This also implies that the ensemble is incompressible – compression does not reduce the communication cost by much. Since the states areclassical, the observed incompressibility is not fundamentally quantum mechanical. We lower bound the difference between the achievable rate and the Holevo information in terms of quantitative limitations to clone the specimen or to distinguish the two classical states.

arXiv:1911.09126•IEEE Transactions on Information Theory•Nov 23, 2021•8 citations

Optimal Tradeoffs for Estimating Pauli Observables

Sitan Chen, Weiyuan Gong, Qi Ye

We revisit the problem of Pauli shadow tomography: given copies of an unknown n-qubit quantum state$\rho$, estimate Tr$(P\rho)$for some set of Pauli operators$F$to within additive error$\epsilon$. This has been a popular testbed for exploring the advantage of protocols with quantum memory over those without: with enough memory to measure two copies at a time, one can use Bell sampling to estimate$\vert \text{Tr}(P\rho)$for all$P$using$O(n/\epsilon^{4})$copies, but with$k\leq n$qubits of memory,$\Omega(2^{(n-k)/3})$copies are needed. These results leave open several natural questions. How does this picture change in the physically relevant setting where one only needs to estimate a certain subset of Paulis? What is the optimal dependence on$\epsilon ?$What is the optimal tradeoff between quantum memory and sample complexity? We answer all of these questions: •For any subset$A$of Paulis and any family of measurement strategies, we completely characterize the optimal sample complexity, up to$\log\vert A\vert$factors. •We show any protocol that makes poly$(n)$-copy measure-ments must make$\Omega(1/\epsilon^{4})$measurements. •For any protocol that makes poly$(n)$-copy measurements and only has$k < n$qubits of memory, we show that$\tilde{\Theta}(\min\{2^{n}/\epsilon^{2},2^{n-k}/\epsilon^{4}\})$copies are necessary and sufficient. The protocols we propose can also estimate the actual values$\text{Tr}(P\rho)$, rather than just their absolute values as in prior work. Additionally, as a byproduct of our techniques, we establish tight bounds for the task of purity testing and show that it exhibits an intriguing phase transition not present in the memory-sample tradeoff for Pauli shadow tomography.

arXiv:2404.19105•Annual Symposium on Foundations of Computer Science•Oct 27, 2024•16 citations

Learning Quantum States Without Entangled Measurements

Angus Lowe

How many samples of a quantum state are required to learn a complete description of it? As we will see in this thesis, the fine-grained answer depends on the measurements available to the learner, but in general it is at least Ω(d^2/ϵ^2) where d is the dimension of the state and ϵ the trace distance accuracy. Optimal algorithms for this task -- known as quantum state tomography -- make use of powerful, yet highly impractical entangled measurements, where some joint measurement is performed on all copies of the state. What can be accomplished without such measurements, where one must perform measurements on individual copies of the states? \n \nIn Chapter 2 we show a relationship between the recently proposed quantum online learning framework and quantum state tomography. Specifically, we show that tomography can be accomplished using online learning algorithms in a black-box manner and O(d^4/ϵ^4) two-outcome measurements on separate copies of the state. The interpretation of this approach is that the experimentalist uses informative measurements to teach the learner by helping it make "mistakes" on measurements as early as possible. \n \nWe move on to proving lower bounds on tomography in Chapter 3. First, we review a known lower bound for entangled measurements as well as a Ω(d^3/ϵ^2) lower bound in the setting where non-entangled measurements are made non-adaptively, both due to Ref.[18]. We then derive a novel bound of Ω(d^4/ϵ^2) samples when the learner is further restricted to observing a constant number of outcomes (e.g., two-outcome measurements). This implies that the folklore "Pauli tomography" algorithm is optimal in this setting. \n \nUnderstanding the power of adaptive measurements, where measurement choices can depend on previous outcomes, is currently an open problem. In Chapter 4 we present two scenarios in which adapting on previous outcomes makes no difference to the number of samples required. In the first, the learner is limited to adapting on at most o(d^2/ϵ^2) of the previous outcomes. In the second, measurements are drawn from some set of at most exp(O(d)) measurements. In particular, this second lower bound implies that adaptivity makes no difference in the regime of efficiently implementable measurements, in the context of quantum computing. \n \nFinally, we apply the above technique to the problems of classical shadows and shadow tomography to obtain similar lower bounds. Here, one is interested only in determining the expectations of some fixed set of observables. We once again find that, for the worst-case input of observables, adaptivity makes no difference to the sample complexity when considering efficient, non-entangled measurements. As a corollary, we find a straightforward algorithm for shadow tomography is optimal in this setting.

•Oct 22, 2021•4 citations

Memory-Sample Lower Bounds for Learning with Classical-Quantum Hybrid Memory

Qipeng Liu, Ran Raz, Wei Zhan

In a work by Raz (J. ACM and FOCS 16), it was proved that any algorithm for parity learning on n bits requires either Ω(n2) bits of classical memory or an exponential number (in ‍n) of random samples. A line of recent works continued that research direction and showed that for a large collection of classical learning tasks, either super-linear classical memory size or super-polynomially many samples are needed. All these works consider learning algorithms as classical branching programs, which perform classical computation within bounded memory. However, these results do not capture all physical computational models, remarkably, quantum computers and the use of quantum memory. It leaves the possibility that a small piece of quantum memory could significantly reduce the need for classical memory or samples and thus completely change the nature of the classical learning task. Despite the recent research on the necessity of quantum memory for intrinsic quantum learning problems like shadow tomography and purity testing, the role of quantum memory in classical learning tasks remains obscure. In this work, we study classical learning tasks in the presence of quantum memory. We prove that any quantum algorithm with both, classical memory and quantum memory, for parity learning on n bits, requires either Ω(n2) bits of classical memory or Ω(n) bits of quantum memory or an exponential number of samples. In other words, the memory-sample lower bound for parity learning remains qualitatively the same, even if the learning algorithm can use, in addition to the classical memory, a quantum memory of size c n (for some constant c>0). Our result is more general and applies to many other classical learning tasks. Following previous works, we represent by the matrix M: A × X → {−1,1} the following learning task. An unknown x is sampled uniformly at random from a concept class X, and a learning algorithm tries to uncover x by seeing streaming of random samples (ai, bi = M(ai, x)) where for every i, ai∈ A is chosen uniformly at random. Assume that k,ℓ,r are integers such that any submatrix of M of at least 2−k·|A| rows and at least 2−ℓ·|X| columns, has a bias of at most 2−r. We prove that any algorithm with classical and quantum hybrid memory for the learning problem corresponding to M needs either (1) Ω(k · ℓ) bits of classical memory, or (2) Ω(r) qubits of quantum memory, or (3) 2Ω(r) random samples, to achieve a success probability at least 2−O(r). Our results refute the possibility that a small amount of quantum memory significantly reduces the size of classical memory needed for efficient learning on these problems. Our results also imply improved security of several existing cryptographical protocols in the bounded-storage model (protocols that are based on parity learning on n bits), proving that security holds even in the presence of a quantum adversary with at most c n2 bits of classical memory and c n bits of quantum memory (for some constant c>0).

arXiv:2303.00209•ACM Symposium on Theory of Computing (STOC)•May 16, 2023•6 citations

Tight Bounds on the Randomized Communication Complexity of Vector-in-Subspace

Chengu Wang

We prove that the randomized communication complexity of Vector-in-Subspace in $\mathbb R^n$ with error at most $1/3$ is $Θ(\sqrt n)$. Alice holds a unit vector $u$ and Bob holds an $n/2$-dimensional subspace $H$; they must distinguish $u\in H$ from $u\in H^\perp$. An exact one-way quantum protocol uses $O(\log n)$ qubits, making the problem a geometric example of an exponential quantum advantage over interactive classical communication. Our lower bound matches Raz's $O(\sqrt n)$ upper bound, improves the $Ω(n^{1/3})$ lower bound of Klartag and Regev, and removes the total-rank restriction in Grupel's $Ω(\sqrt n)$ result. The proof establishes a Gaussian moment bound over complete rectangle partitions. A complex Gaussian representation yields a vanishing even moment whose cancellation is preserved when averaging over the partition. We control the signed conditional moments around a real center by decomposing conditional Gaussian measures into fixed coordinates and sub-Gaussian components. Combining this estimate with spherical harmonic analysis gives the communication lower bound.

cs.CCCross-listedarXiv:2610.30052•Oct 22, 2026•0 citations
We study the question of how much classical communication is needed when Alice is given a classical description of a quantum state ∣ψ⟩|ψ\rangle∣ψ⟩ for Bob to recover any expectation value ⟨ψ∣M∣ψ⟩\langle ψ| M |ψ\rangle⟨ψ∣M∣ψ⟩ given an observable MMM with MMM Hermitian and ∣∣M∣∣op≤1||M||_{\text{op}} \leq 1∣∣M∣∣op​≤1. This task, whose study was initiated by Raz (ACM 1999) and more recently investigated by Gosset and Smolin (TQC 2019), can be thought of as a fully classical version of the pure state case of the well-known classical shadows problem in quantum learning theory. We show how the hardness of these two seemingly distinct problems are connected. We first consider the relative error version of the communication question and prove a lower bound of Ω(2nε−2)Ω(\sqrt{2^{n}}ε^{-2})Ω(2n​ε−2) on the one-way randomized classical communication, improving upon an additive error lower bound of Ω(2n)Ω(\sqrt{2^{n}})Ω(2n​) as shown by Gosset and Smolin. Notably, we show that this lower bound holds not only for the set of all observables but also when restricted to just the class of Pauli observables. This fact implies a Ω(2n)Ω(\sqrt{2^{n}})Ω(2n​) versus O(poly(n))O(\text{poly}(n))O(poly(n)) separation in the compression size between the relative and additive error settings for non-adaptive Pauli classical shadows with classical memory. Extending this framework, we prove randomized communication lower bounds for other relative error one-way classical communication tasks: an Ω(2nε−2)Ω(2^{n}ε^{-2})Ω(2nε−2) lower bound when instead Alice is given an observable and Bob is given a quantum state and they are asked to estimate the expectation value, an Ω(nε−2)Ω(\sqrt{n}ε^{-2})Ω(n​ε−2) lower bound when restricted to Paulis, and an Ω(2nε−2)Ω(\sqrt{2^{n}}ε^{-2})Ω(2n​ε−2) lower bound when Alice and Bob are both given quantum states and asked to estimate the inner product.
We consider the classical shadows task for pure states in the setting of both joint and independent measurements. The task is to measure few copies of an unknown pure state ρ in order to learn a classical description which suffices to later estimate expectation values of observables. Specifically, the goal is to approximate Tr(Oρ) for any Hermitian observable O to within additive error ϵ provided Tr(O2)≤B and ‖O‖=1 . Our main result applies to the joint measurement setting, where we show Θ~(Bϵ−1+ϵ−2) samples of ρ are necessary and sufficient to succeed with high probability. The upper bound is a quadratic improvement on the previous best sample complexity known for this problem. For the lower bound, we see that the bottleneck is not how fast we can learn the state but rather how much any classical description of ρ can be compressed for observable estimation. In the independent measurement setting, we show that O(Bdϵ−1+ϵ−2) samples suffice. Notably, this implies that the random Clifford measurements algorithm of Huang, Kueng, and Preskill, which is sample-optimal for mixed states, is not optimal for pure states. Interestingly, our result also uses the same random Clifford measurements but employs a different estimator.
Inblindcompression of quantum states, a sender Alice is given a specimen of a quantum state$\rho drawnfromaknownensemble(butwithoutknowingwhatdrawn from a known ensemble (but without knowing whatdrawnfromaknownensemble(butwithoutknowingwhat\rho is),andshetransmitssufficientquantumdatatoareceiverBobsothathecandecodeanearperfectspecimenofis), and she transmits sufficient quantum data to a receiver Bob so that he can decode a near perfect specimen ofis),andshetransmitssufficientquantumdatatoareceiverBobsothathecandecodeanearperfectspecimenof\rho $. For many such states drawn iid from the ensemble, the asymptotically achievable rate is the number of qubits required to be transmitted per state. The Holevo information is a lower bound for the achievable rate, and is attained for pure state ensembles, or in the related scenario of entanglement-assistedvisiblecompression of mixed states wherein Alice knows what state is drawn. In this paper, we prove a general and robust lower bound on the achievable rate for ensembles of classical states, which holds even in the least demanding setting when Alice and Bob share free entanglement and a constant per-copy error is allowed. We apply the bound to aspecificensemble of only two states and prove a near-maximal separation (saturating the dimension bound in leading order) between the best achievable rate and the Holevo information for constant error. This also implies that the ensemble is incompressible – compression does not reduce the communication cost by much. Since the states areclassical, the observed incompressibility is not fundamentally quantum mechanical. We lower bound the difference between the achievable rate and the Holevo information in terms of quantitative limitations to clone the specimen or to distinguish the two classical states.
We revisit the problem of Pauli shadow tomography: given copies of an unknown n-qubit quantum stateρ\rhoρ, estimate Tr(Pρ)(P\rho)(Pρ)for some set of Pauli operatorsFFFto within additive errorϵ\epsilonϵ. This has been a popular testbed for exploring the advantage of protocols with quantum memory over those without: with enough memory to measure two copies at a time, one can use Bell sampling to estimate∣Tr(Pρ)\vert \text{Tr}(P\rho)∣Tr(Pρ)for allPPPusingO(n/ϵ4)O(n/\epsilon^{4})O(n/ϵ4)copies, but withk≤nk\leq nk≤nqubits of memory,Ω(2(n−k)/3)\Omega(2^{(n-k)/3})Ω(2(n−k)/3)copies are needed. These results leave open several natural questions. How does this picture change in the physically relevant setting where one only needs to estimate a certain subset of Paulis? What is the optimal dependence onϵ?\epsilon ?ϵ?What is the optimal tradeoff between quantum memory and sample complexity? We answer all of these questions: •For any subsetAAAof Paulis and any family of measurement strategies, we completely characterize the optimal sample complexity, up tolog⁡∣A∣\log\vert A\vertlog∣A∣factors. •We show any protocol that makes poly(n)(n)(n)-copy measure-ments must makeΩ(1/ϵ4)\Omega(1/\epsilon^{4})Ω(1/ϵ4)measurements. •For any protocol that makes poly(n)(n)(n)-copy measurements and only hask<nk < nk<nqubits of memory, we show thatΘ~(min⁡{2n/ϵ2,2n−k/ϵ4})\tilde{\Theta}(\min\{2^{n}/\epsilon^{2},2^{n-k}/\epsilon^{4}\})Θ~(min{2n/ϵ2,2n−k/ϵ4})copies are necessary and sufficient. The protocols we propose can also estimate the actual valuesTr(Pρ)\text{Tr}(P\rho)Tr(Pρ), rather than just their absolute values as in prior work. Additionally, as a byproduct of our techniques, we establish tight bounds for the task of purity testing and show that it exhibits an intriguing phase transition not present in the memory-sample tradeoff for Pauli shadow tomography.
How many samples of a quantum state are required to learn a complete description of it? As we will see in this thesis, the fine-grained answer depends on the measurements available to the learner, but in general it is at least Ω(d^2/ϵ^2) where d is the dimension of the state and ϵ the trace distance accuracy. Optimal algorithms for this task -- known as quantum state tomography -- make use of powerful, yet highly impractical entangled measurements, where some joint measurement is performed on all copies of the state. What can be accomplished without such measurements, where one must perform measurements on individual copies of the states? \n \nIn Chapter 2 we show a relationship between the recently proposed quantum online learning framework and quantum state tomography. Specifically, we show that tomography can be accomplished using online learning algorithms in a black-box manner and O(d^4/ϵ^4) two-outcome measurements on separate copies of the state. The interpretation of this approach is that the experimentalist uses informative measurements to teach the learner by helping it make "mistakes" on measurements as early as possible. \n \nWe move on to proving lower bounds on tomography in Chapter 3. First, we review a known lower bound for entangled measurements as well as a Ω(d^3/ϵ^2) lower bound in the setting where non-entangled measurements are made non-adaptively, both due to Ref.[18]. We then derive a novel bound of Ω(d^4/ϵ^2) samples when the learner is further restricted to observing a constant number of outcomes (e.g., two-outcome measurements). This implies that the folklore "Pauli tomography" algorithm is optimal in this setting. \n \nUnderstanding the power of adaptive measurements, where measurement choices can depend on previous outcomes, is currently an open problem. In Chapter 4 we present two scenarios in which adapting on previous outcomes makes no difference to the number of samples required. In the first, the learner is limited to adapting on at most o(d^2/ϵ^2) of the previous outcomes. In the second, measurements are drawn from some set of at most exp(O(d)) measurements. In particular, this second lower bound implies that adaptivity makes no difference in the regime of efficiently implementable measurements, in the context of quantum computing. \n \nFinally, we apply the above technique to the problems of classical shadows and shadow tomography to obtain similar lower bounds. Here, one is interested only in determining the expectations of some fixed set of observables. We once again find that, for the worst-case input of observables, adaptivity makes no difference to the sample complexity when considering efficient, non-entangled measurements. As a corollary, we find a straightforward algorithm for shadow tomography is optimal in this setting.
In a work by Raz (J. ACM and FOCS 16), it was proved that any algorithm for parity learning on n bits requires either Ω(n2) bits of classical memory or an exponential number (in ‍n) of random samples. A line of recent works continued that research direction and showed that for a large collection of classical learning tasks, either super-linear classical memory size or super-polynomially many samples are needed. All these works consider learning algorithms as classical branching programs, which perform classical computation within bounded memory. However, these results do not capture all physical computational models, remarkably, quantum computers and the use of quantum memory. It leaves the possibility that a small piece of quantum memory could significantly reduce the need for classical memory or samples and thus completely change the nature of the classical learning task. Despite the recent research on the necessity of quantum memory for intrinsic quantum learning problems like shadow tomography and purity testing, the role of quantum memory in classical learning tasks remains obscure. In this work, we study classical learning tasks in the presence of quantum memory. We prove that any quantum algorithm with both, classical memory and quantum memory, for parity learning on n bits, requires either Ω(n2) bits of classical memory or Ω(n) bits of quantum memory or an exponential number of samples. In other words, the memory-sample lower bound for parity learning remains qualitatively the same, even if the learning algorithm can use, in addition to the classical memory, a quantum memory of size c n (for some constant c>0). Our result is more general and applies to many other classical learning tasks. Following previous works, we represent by the matrix M: A × X → {−1,1} the following learning task. An unknown x is sampled uniformly at random from a concept class X, and a learning algorithm tries to uncover x by seeing streaming of random samples (ai, bi = M(ai, x)) where for every i, ai∈ A is chosen uniformly at random. Assume that k,ℓ,r are integers such that any submatrix of M of at least 2−k·|A| rows and at least 2−ℓ·|X| columns, has a bias of at most 2−r. We prove that any algorithm with classical and quantum hybrid memory for the learning problem corresponding to M needs either (1) Ω(k · ℓ) bits of classical memory, or (2) Ω(r) qubits of quantum memory, or (3) 2Ω(r) random samples, to achieve a success probability at least 2−O(r). Our results refute the possibility that a small amount of quantum memory significantly reduces the size of classical memory needed for efficient learning on these problems. Our results also imply improved security of several existing cryptographical protocols in the bounded-storage model (protocols that are based on parity learning on n bits), proving that security holds even in the presence of a quantum adversary with at most c n2 bits of classical memory and c n bits of quantum memory (for some constant c>0).
We prove that the randomized communication complexity of Vector-in-Subspace in Rn\mathbb R^nRn with error at most 1/31/31/3 is Θ(n)Θ(\sqrt n)Θ(n​). Alice holds a unit vector uuu and Bob holds an n/2n/2n/2-dimensional subspace HHH; they must distinguish u∈Hu\in Hu∈H from u∈H⊥u\in H^\perpu∈H⊥. An exact one-way quantum protocol uses O(log⁡n)O(\log n)O(logn) qubits, making the problem a geometric example of an exponential quantum advantage over interactive classical communication. Our lower bound matches Raz's O(n)O(\sqrt n)O(n​) upper bound, improves the Ω(n1/3)Ω(n^{1/3})Ω(n1/3) lower bound of Klartag and Regev, and removes the total-rank restriction in Grupel's Ω(n)Ω(\sqrt n)Ω(n​) result. The proof establishes a Gaussian moment bound over complete rectangle partitions. A complex Gaussian representation yields a vanishing even moment whose cancellation is preserved when averaging over the partition. We control the signed conditional moments around a real center by decomposing conditional Gaussian measures into fixed coordinates and sub-Gaussian components. Combining this estimate with spherical harmonic analysis gives the communication lower bound.