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• 1 citation
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•33 citations

A Compressed Classical Description of Quantum States

David Gosset, John A. Smolin

We show how to approximately represent a quantum state using the square root of the usual amount of classical memory. The classical representation of an $n$-qubit state $ψ$ consists of its inner products with $O(\sqrt{2^n})$ stabilizer states. A quantum state initially specified by its $2^n$ entries in the computational basis can be compressed to this form in time $O(2^n \mathrm{poly}(n))$, and, subsequently, the compressed description can be used to additively approximate the expectation value of an arbitrary observable. Our compression scheme directly gives a new protocol for the vector in subspace problem with randomized one-way communication complexity that matches (up to polylogarithmic factors) the optimal upper bound, due to Raz. We obtain an exponential improvement over Raz's protocol in terms of computational efficiency.

arXiv:1801.05721•Leibniz international proceedings in informatics•Jan 17, 2018•19 citations

Lower Bound on Expected Communication Cost of Quantum Huffman Coding

Anurag Anshu, Ankit Garg, Aram W. Harrow +1 more

Data compression is a fundamental problem in quantum and classical information theory. A typical version of the problem is that the sender Alice receives a (classical or quantum) state from some known ensemble and needs to transmit them to the receiver Bob with average error below some specified bound. We consider the case in which the message can have a variable length and the goal is to minimize its expected length. For classical messages this problem has a well-known solution given by Huffman coding. In this scheme, the expected length of the message is equal to the Shannon entropy of the source (with a constant additive factor) and the scheme succeeds with zero error. This is a single-shot result which implies the asymptotic result, viz. Shannon's source coding theorem, by encoding each state sequentially. For the quantum case, the asymptotic compression rate is given by the von-Neumann entropy. However, we show that there is no one-shot scheme which is able to match this rate, even if interactive communication is allowed. This is a relatively rare case in quantum information theory when the cost of a quantum task is significantly different than the classical analogue. Our result has implications for direct sum theorems in quantum communication complexity and one-shot formulations of Quantum Reverse Shannon theorem.

Leibniz international proceedings in informatics•Jan 1, 2016•1 citation

Lower bound on expected communication cost of quantum Huffman coding

Anurag Anshu, Ankit Garg, Aram W. Harrow +1 more

Data compression is a fundamental problem in quantum and classical information theory. A typical version of the problem is that the sender Alice receives a (classical or quantum) state from some known ensemble and needs to transmit them to the receiver Bob with average error below some specified bound. We consider the case in which the message can have a variable length and the goal is to minimize its expected length. For classical messages this problem has a well-known solution given by Huffman coding. In this scheme, the expected length of the message is equal to the Shannon entropy of the source (with a constant additive factor) and the scheme succeeds with zero error. This is a single-shot result which implies the asymptotic result, viz. Shannon's source coding theorem, by encoding each state sequentially. For the quantum case, the asymptotic compression rate is given by the von-Neumann entropy. However, we show that there is no one-shot scheme which is able to match this rate, even if interactive communication is allowed. This is a relatively rare case in quantum information theory when the cost of a quantum task is significantly different than the classical analogue. Our result has implications for direct sum theorems in quantum communication complexity and one-shot formulations of Quantum Reverse Shannon theorem.

arXiv:1605.04601•May 15, 2016•2 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•48 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.
We show how to approximately represent a quantum state using the square root of the usual amount of classical memory. The classical representation of an nnn-qubit state ψψψ consists of its inner products with O(2n)O(\sqrt{2^n})O(2n​) stabilizer states. A quantum state initially specified by its 2n2^n2n entries in the computational basis can be compressed to this form in time O(2npoly(n))O(2^n \mathrm{poly}(n))O(2npoly(n)), and, subsequently, the compressed description can be used to additively approximate the expectation value of an arbitrary observable. Our compression scheme directly gives a new protocol for the vector in subspace problem with randomized one-way communication complexity that matches (up to polylogarithmic factors) the optimal upper bound, due to Raz. We obtain an exponential improvement over Raz's protocol in terms of computational efficiency.
Data compression is a fundamental problem in quantum and classical information theory. A typical version of the problem is that the sender Alice receives a (classical or quantum) state from some known ensemble and needs to transmit them to the receiver Bob with average error below some specified bound. We consider the case in which the message can have a variable length and the goal is to minimize its expected length. For classical messages this problem has a well-known solution given by Huffman coding. In this scheme, the expected length of the message is equal to the Shannon entropy of the source (with a constant additive factor) and the scheme succeeds with zero error. This is a single-shot result which implies the asymptotic result, viz. Shannon's source coding theorem, by encoding each state sequentially. For the quantum case, the asymptotic compression rate is given by the von-Neumann entropy. However, we show that there is no one-shot scheme which is able to match this rate, even if interactive communication is allowed. This is a relatively rare case in quantum information theory when the cost of a quantum task is significantly different than the classical analogue. Our result has implications for direct sum theorems in quantum communication complexity and one-shot formulations of Quantum Reverse Shannon theorem.
Data compression is a fundamental problem in quantum and classical information theory. A typical version of the problem is that the sender Alice receives a (classical or quantum) state from some known ensemble and needs to transmit them to the receiver Bob with average error below some specified bound. We consider the case in which the message can have a variable length and the goal is to minimize its expected length. For classical messages this problem has a well-known solution given by Huffman coding. In this scheme, the expected length of the message is equal to the Shannon entropy of the source (with a constant additive factor) and the scheme succeeds with zero error. This is a single-shot result which implies the asymptotic result, viz. Shannon's source coding theorem, by encoding each state sequentially. For the quantum case, the asymptotic compression rate is given by the von-Neumann entropy. However, we show that there is no one-shot scheme which is able to match this rate, even if interactive communication is allowed. This is a relatively rare case in quantum information theory when the cost of a quantum task is significantly different than the classical analogue. Our result has implications for direct sum theorems in quantum communication complexity and one-shot formulations of Quantum Reverse Shannon theorem.
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.