Lower Bounds on Relative Error Quantum Compression and Classical Shadows

Kaushik Sankar

REVIEW 3 major objections 3 minor 12 references

Lower Bounds on Relative Error Quantum Compression and Classical Shadows

T0 review · 3 major / 3 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Relative-error quantum observable estimation forces Ω(√(2^n) ε^{-2}) bits of one-way communication, even for Pauli observables.

desk verdict The claimed relative-error lower bounds are not established: the reduction's error propagation is off by a factor of about √C, a load-bearing gap that invalidates all five main theorems. read the letter →

arxiv 2506.21345 v1 pith:2IXR7LWB submitted 2025-06-26 quant-ph cs.CC

Kaushik Sankar This is my paper · ORCID

classification quant-phcs.CC MSC 68Q1181P68 PACS 03.67.-a

keywords communicationcomplexityquantumstatecompressionrelativeerrorclassicalshadowsPauliobservablesGap-HammingDistanceone-wayrandomizedinnerproductestimation

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper attempts to determine how much classical communication is required when one party holds a classical description of a quantum state and another holds an observable, under a relative (multiplicative) error guarantee on the expectation value. It proves that ε-relative error costs Ω(√(2^n) $ε^{{-2}}$) one-way randomized bits, improving the earlier additive-error lower bound of Ω(√(2^n)) and showing the same bound holds even when the observable is restricted to a Pauli matrix. This implies an exponential separation between relative-error and additive-error compressibility for non-adaptive Pauli classical shadows, since additive error admits polynomial-size compressed descriptions. The same framework yields lower bounds for observable compression and for inner-product estimation. If these bounds are correct, requiring relative precision makes compressed quantum information exponentially harder to achieve.

What carries the argument

Central machinery is the reduction from Indexing to relative-error ⟨M⟩ through the Gap-Hamming Distance problem. The paper uses a modified version of Andoni et al.'s reduction (Theorem 2.3): from a random bitstring x and a random index i, shared random strings, one constructs binary strings a,b of length Cγ (γ=$ε^{{-2}}$) such that knowing Δ(a,b) to additive error d√(Cγ) recovers x_i with constant advantage. The link to expectation values is the polarization identity 2⟨a,b⟩ = ‖a+b‖² − ‖a‖² − ‖b‖², which converts a relative-error estimate of ‖a_j+b_i‖² into an additive estimate of the inner product and hence of Hamming distance. For the Pauli restriction, the additional object is the matrix Diag(P_n) whose rows are the diagonal entries of all tensor products of I and Z; it is an orthogonal basis scaled by 2^n, and Alice can pre-compute the vector of all ‖a_j+b_i‖² values, encode it (with extra 1s) into a state, and let Bob's Pauli observable P_l⊗X extract the desired entry. For the shadows connection, the reduction Theorem 4.1 converts a classical shadows learner into a communication protocol by simulating the measurement on a classical description of the state.

What would settle it

Compute the largest error in the Hamming distance Δ(a,b) induced by a (1±ε)-relative error in ‖a+b‖² for the constants C = 9/c² (0<c<√(2/π)) and d < 1/2 from Theorem 2.3; if it exceeds d√(Cγ) for γ=$ε^{{-2}}$, the reduction in Theorem 2.4 fails and the claimed lower bound lacks a proof.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is that the relative-error ⟨M⟩ problem—estimate ⟨ψ|M|ψ⟩ to within a factor (1±ε) with high probability—has one-way randomized communication complexity Ω(√(2^n) $ε^{{-2}}$) for ε ∈ ($2^{{-n/4}}$, 1), for general Hermitian observables with operator norm at most 1 (Theorem 2.4) and also when M is restricted to Pauli observables (Theorem 3.1). The argument reduces from the Indexing problem via a Gap-Hamming Distance reduction (Theorem 2.3, adapted from [ACK+15]): Alice encodes indexing instances into a quantum state whose expectation value under Bob's observable encodes a Hamming distance, and a relative-error estimate of that expectation value is claimed to yield an additive estimate of the Hamming distance accurate enough to recover the index. The same reduction scheme gives Ω(2^n $ε^{{-2}}$) for observable compression by general observables, Ω(√n $ε^{{-2}}$) for Pauli observables, and Ω(√(2^n) $ε^{{-2}}$) for inner product estimation. The paper further shows (Theorem 4.1) that any relative-error classical shadows protocol yields a one-way communication protocol with the same cost, so the communication lower bound transfers directly to a lower bound on the size of compressed classical shadows.

Load-bearing premise

The chain of lower bounds rests on the step that converts a relative error in measuring ‖a+b‖² into a precise enough absolute error in counting the differing bits between two binary strings; if the conversion is too lossy, the reduction to the hard indexing problem fails.

Editorial extensions

If this is right

Any ε-relative-error classical shadows protocol must produce a compressed classical description of size Ω(√(2^n) ε^{-2}) bits, no matter how many non-adaptive measurements are allowed.
Relative-error Pauli shadow tomography is exponentially harder to compress than additive-error Pauli shadow tomography: polynomial-size shadow descriptions exist for additive error, while relative error requires 2^{n/2}-scale communication.
The lower bound survives the restriction to Pauli observables, so the hardness comes from requiring multiplicative precision rather than from the size of the observable class.
The same reduction scheme shows that observable compression requires Ω(2^n ε^{-2}) bits for general observables and Ω(√n ε^{-2}) bits for Pauli observables, and that inner product estimation requires Ω(√(2^n) ε^{-2}) bits.
If the bounds are correct, relative error is strictly more informationally demanding than additive error in one-way settings, since the additive problem admits a nearly matching O~(√(2^n) ε^{-1}) upper bound.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A patched error analysis for the Hamming-distance conversion would likely make the same framework apply to other relative-error overlap estimators, such as state fidelity or purity estimation.
The Ω(√n ε^{-2}) Pauli-observable compression bound suggests the trivial O(n)-bit encoding of a Pauli is essentially optimal under relative error, up to the ε^{-2} factor.
An information-theoretic proof of the lower bound, avoiding the Gap-Hamming reduction constants, could extend the result to multi-round or interactive communication protocols.
If the claimed separation is correct, it implies that relative-error guarantees are the wrong target for near-term classical-shadows pipelines that aim for polynomial-size classical memory.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The paper's main message—that relative-error compression of quantum states is much harder than additive-error compression—is coherent, and the author correctly identifies an interesting open problem. Unfortunately, the proof of the central lower bound does not work, and the same error analysis gap appears in every main theorem.

The issue is in Theorem 2.4. Bob's relative-error estimate of ⟨ψ|M|ψ⟩ translates, after rescaling, into a (1±ε)-estimate of ||â_j + b_i||². The identity 2⟨â,b⟩ = ||a+b||² − ||a||² − ||b||² then gives an estimate of ⟨â,b⟩ with additive error ε·||a+b||². On the Gap-Hamming input distribution, ||a+b||² is Θ(Cγ) = Θ(C/ε²), so the additive error on the Hamming distance is Θ(C/ε). Theorem 2.3, however, requires error d√(Cγ) = Θ(√C/ε). With the explicit constants in Appendix A (C = 9/c² ≥ 14), the achieved error is larger by a factor Θ(√C) > 3.7. The reduction therefore does not solve Indexing. The same flaw propagates to the Pauli restriction (Thm 3.1), the observable-compression results (Thms 5.1, 6.1), and the inner-product bound (Thm 7.1). Theorem 7.1 has an additional hand-wave about the size of |⟨ψ|ϕ⟩|; the stated argument does not even attempt to control the scaling.

Now what is genuinely good. The paper is clearly written, the author is honest about constants, and the reduction framework in Theorem 4.1 (classical shadows to communication) is correct as far as it goes. The connection between relative error and the additive/relative separation is a good question. The citations are appropriate, and there is no self-citation inflation.

Proportionately: this is not a collection of minor fixable typos; the error analysis is load-bearing and the constants make the failure explicit. Still, the topic is important enough that I would not desk-reject it out of hand. A referee can give the author a precise diagnosis, and perhaps the reduction can be repaired by a different construction (though this one seems beyond repair). My recommendation: send it to review, but with low expectations; the results as stated are not established.

For me, this is a reading-group example of how error propagation can silently kill a reduction. I would not cite it for the claimed bounds.

Referee Report

3 major / 3 minor

Summary. The manuscript claims one-way randomized communication lower bounds for relative-error expectation value estimation from compressed classical descriptions of quantum states, covering arbitrary observables (Theorem 2.4), Pauli observables (Theorem 3.1), observable-side communication variants (Theorems 5.1 and 6.1), and inner product estimation (Theorem 7.1), together with a reduction to relative-error classical shadows (Theorem 4.1). The common proof template reduces from Indexing via the Gap-Hamming Distance problem: Alice encodes many binary strings into a quantum state, Bob chooses an observable whose expectation equals a scaled squared norm ||a_j + b_i||^2, and a relative-error estimate of that expectation is meant to yield an additive estimate of the Hamming distance Delta(a_j,b_i).

Significance. If the theorems were correct, they would improve the additive-error bound of Gosset and Smolin by an epsilon^{-2} factor and establish a sharp separation between relative and additive error settings for Pauli classical shadows. The paper has useful expository features: the reduction template is explicit, and Appendix A gives concrete constants for the Gap-Hamming-to-Indexing reduction. However, the central error-propagation step is invalid and is reused in every main theorem; consequently the claimed lower bounds are not established and the shadow-compression separation does not follow from the arguments given.

major comments (3)

[Section 2, proof of Theorem 2.4, after the display 2<â_j,b_i> = ||â_j+b_i||^2 - ||â_j||^2 - ||b_i||^2] The conversion from a (1±epsilon)-relative-error estimate of S = ||â_j+b_i||^2 into a d√(Cγ)-additive estimate of Delta(a_j,b_i) is invalid. A relative-error guarantee on S gives an absolute error of at most epsilon*S on S, and since the subsequent identities only subtract exactly known quantities ||â_j||^2 and ||b_i||^2, the same additive error epsilon*S propagates to 2<â_j,b_i> and to Delta(a_j,b_i). On the Gap-Hamming input distribution from Theorem 2.3, S = Θ(Cγ) = Θ(C epsilon^{-2}) with high probability, so the resulting additive error on Delta is Θ(C epsilon^{-1}). Theorem 2.3 permits only d√(Cγ) = d√C epsilon^{-1} with d < 1/2. With the paper's constant C = 9/c^2 ≥ 9π/2 ≈ 14.1, the achieved error exceeds the allowed error by a factor Θ(√C) > 3.7. Therefore the reduction does not solve Indexing, and Theorem 2.4 is not established.
[Sections 3, 5, and 6] The same flawed conversion is reused in the proofs of Theorems 3.1, 5.1, and 6.1. In Theorem 3.1 the proof says to proceed exactly as in the previous proof; in Theorem 5.1 the proof invokes the same argument as before; and in Theorem 6.1 the relative-error guarantee on the Pauli expectation -Delta(a_j,b_i)/(Cγ) yields, after rescaling, an absolute error of epsilon*Delta(a_j,b_i) = Θ(C/epsilon) on the Hamming distance, again exceeding the allowed d√(Cγ) = Θ(√C/epsilon). Since Theorem 4.1 derives its shadow lower bound from Theorems 2.4 and 3.1, its main conclusion is unsupported as well. Although the reduction in Theorem 4.1 is logically sound in isolation, it cannot compensate for the failure of the lower bounds on which it relies.
[Section 7, proof of Theorem 7.1] The claimed error bound c'*epsilon*|<ψ|φ>| ≤ c'*epsilon*γ ≤ c'/epsilon does not bridge to the required d√(Cγ)-additive estimate of Delta. Even if the inner-product estimate had absolute error O(epsilon*|<ψ|φ>|), rescaling by √(DD') to recover <â_j,b_i> multiplies that error by a factor of size Θ(2^{n/4}√(Cγ)), giving again Θ(C/epsilon) absolute error on Delta, rather than the required d√C/epsilon. The displayed inequality is also not a valid measure of the final Hamming error, since |<ψ|φ>| ≤ 1 makes c'*epsilon*γ = c'/epsilon bound a quantity much larger than the actual inner-product error. Thus Theorem 7.1 is not established by the given argument.

minor comments (3)

[Appendix A, proof of Theorem 2.3] In the displayed algebra, the term involving 6·√γ/c^2 is inconsistent: since C = 9/c^2 and N = Cγ, the computation should give N/2 - 6√γ/c = N/2 - 2√N. The current display appears to have a typo in the exponent of c.
[Theorem 2.3 statement and proof] The theorem states an additive approximation of d√(Cγ), but the proof later refers to a d√(Δ(a,b))-additive approximation; this should be d√(Cγ) (or d√N) to match the statement and the subsequent application.
[Section 4, Theorem 4.1] The reduction from classical shadows to the ⟨M⟩ problem is stated for success probability 1 - δ, but the communication lower bounds are quoted at constant failure probability 1/3; a sentence explaining how the parameters are matched would improve readability, although this is not a load-bearing issue.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the lower bounds are reductions from the standard Indexing problem via external Gap-Hamming and majority-bias results.

full rationale

The paper derives its lower bounds by reduction from the Indexing problem (Theorem 2.1, cited from [JKS08]), using a Gap-Hamming-to-Indexing reduction (Theorem 2.3, credited to [ACK+15] with a proof in Appendix A based on [JKS08], [Rou15], and [Woo07]). No parameter in these reductions is fitted to the claimed conclusion; the states and observables are explicitly constructed from the Indexing instance, and the relative-error oracle is used only as a subroutine. Theorems 3.1, 5.1, 6.1, and 7.1 follow the same reduction pattern rather than assuming what they prove. Theorem 4.1 is a reduction from the classical shadows task to the communication problem and is logically independent of the lower bounds. There is no load-bearing self-citation: the cited lower bounds and reductions are external standard results. The suspected relative-error-to-additive-error conversion issue is a quantitative error-bound gap, not a step that is equal to its input by construction, so it does not amount to circularity.

Assumptions & free parameters 1 free parameters · 5 assumptions · 0 invented entities

The paper relies on standard communication complexity and probability results. The only hand-chosen constant is C in the Gap-Hamming construction; its value is central to the failed error analysis.

free parameters (1)

C = C = 9/c^2, 0 < c < sqrt(2/pi)
Hand-chosen constant number of random bitstrings per coordinate in the Gap-Hamming construction. Its value determines the ratio between the relative-error-induced additive error and the required Gap-Hamming gap; the proof fails because this ratio exceeds 1 for the chosen C.

assumptions (5)

standard math Indexing problem requires Ω(n) one-way randomized communication (Theorem 2.1).
Used as the hardness base in all reductions; standard result cited to [JKS08].
standard math The Gap-Hamming to Indexing reduction (Theorem 2.3) from [ACK+15, Lemma 5.3] is valid.
Invoked in every lower bound proof to turn an additive Hamming distance estimate into an indexing answer.
standard math Majority bias lemma (Lemma A.1) from [Woo07] holds, providing the constant c.
Used to set C = 9/c^2 in the distributed construction.
domain assumption Relative error can be converted to additive error via the identity 2<a,b> = ||a+b||^2 - ||a||^2 - ||b||^2.
This is the step where the proof's error bound fails; it is assumed that the additive error d√(Cγ) is achieved, but the constants do not support it.
domain assumption Quantum state descriptions can be represented with O(n) bit precision.
The paper's Section 1.3 asserts this; needed for the constructions to be finite-precision.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Lower Bounds on Relative Error Quantum Compression and Classical Shadows." pith.science (2026). https://pith.science/paper/2IXR7LWB

@misc{pith2026250621345,
  author       = {Pith},
  title        = {Pith review of: Lower Bounds on Relative Error Quantum Compression and Classical Shadows},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2IXR7LWB}},
  note         = {Machine review of arXiv:2506.21345}
}

abstract

We study the question of how much classical communication is needed when Alice is given a classical description of a quantum state $|\psi\rangle$ for Bob to recover any expectation value $\langle \psi | M |\psi\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 $\Omega(\sqrt{2^{n}}\epsilon^{-2})$ on the one-way randomized classical communication, improving upon an additive error lower bound of $\Omega(\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 $\Omega(\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 $\Omega(2^{n}\epsilon^{-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 $\Omega(\sqrt{n}\epsilon^{-2})$ lower bound when restricted to Paulis, and an $\Omega(\sqrt{2^{n}}\epsilon^{-2})$ lower bound when Alice and Bob are both given quantum states and asked to estimate the inner product.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 5 canonical work pages

[7]

2 [GPS24] Daniel Grier, Hakop Pashayan, and Luke Schaeffer

URL:https://arxiv.org/abs/2412.19022, arXiv:2412.19022. 2 [GPS24] Daniel Grier, Hakop Pashayan, and Luke Schaeffer. Sample-optimal classical shadows for pure states.Quantum, 8:1373, June

arXiv
[8]

2, 4, 11 [GS19] David Gosset and John Smolin

URL: http://dx.doi.org/10.22331/q-2024-06-17-1373, doi:10.22331/q-2024-06-17-1373. 2, 4, 11 [GS19] David Gosset and John Smolin. A compressed classical description of quantum states. Leibniz Int. Proc. Inf., 135:8:1–8:9,

work page doi:10.22331/q-2024-06-17-1373 2024
[1999]

doi:10.1145/301250.301343

Association for Computing Machinery. doi:10.1145/301250.301343. 1 [Rou15] Tim Roughgarden. Cs369e: Communication complexity (for algorithm designers) lecture #2: Lower bounds for one-way communication: Disjointness, index, and gap-hamming, January

arXiv
[2004]

Limitations of Quantum Advice and One-Way Communication

IEEE Computer Society. URL: https://arxiv.org/pdf/quant-ph/0402095. 2 [Aar18] Scott Aaronson. Shadow tomography of quantum states,

work page Pith review arXiv
[2008]

5, 17 [KGKB25] Robbie King, David Gosset, Robin Kothari, and Ryan Babbush

URL: https://theoryofcomputing.org/articles/v004a006, doi:10.4086/toc.2008.v004a006. 5, 17 [KGKB25] Robbie King, David Gosset, Robin Kothari, and Ryan Babbush. Triply efficient shadow tomography.PRX Quantum, 6(1), feb

work page doi:10.4086/toc.2008.v004a006 2008
[2015]

3, 4, 5, 7, 14, 15, 17 [CCHL21] Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, and Jerry Li

URL: http://arxiv.org/abs/1511.06099, arXiv:1511.06099. 3, 4, 5, 7, 14, 15, 17 [CCHL21] Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, and Jerry Li. Exponential separations between learning with and without quantum memory,

work page arXiv
[2018]

2 [ABF23] Alexandr Andoni, Jaroslaw Blasiok, and Arnold Filtser

URL: https://arxiv.org/abs/1711.01053, arXiv:1711.01053. 2 [ABF23] Alexandr Andoni, Jaroslaw Blasiok, and Arnold Filtser. Communication complexity of inner product in symmetric normed spaces. In Yael Tauman Kalai, editor,14th Innovations in Theoretical Computer Science Conference (ITCS 2023), volume 251 of Leibniz International Proceedings in Informatics ...

arXiv 2023
[2019]

2, 4 [HKP20] Hsin-Yuan Huang, Richard Kueng, and John Preskill

URL: https://inspirehep.net/files/008cdc6d46be75c464574f793b329a1b, doi:10.4230/LIPIcs.TQC.2019.8. 2, 4 [HKP20] Hsin-Yuan Huang, Richard Kueng, and John Preskill. Predicting many properties of a quantum system from very few measurements.Nature Physics, 16(10):1050–1057, June

work page doi:10.4230/lipics.tqc.2019.8 2019

Show all 12 references

[2020]

2 [JKS08] T

URL: http://dx.doi.org/10.1038/s41567-020-0932-7, doi:10.1038/s41567-020-0932-7. 2 [JKS08] T. S. Jayram, Ravi Kumar, and D. Sivakumar. The one-way communication complexity of hamming distance.Theory of Computing, 4(6):129–135,

doi
[2021]

2 [CGY24] Sitan Chen, Weiyuan Gong, and Qi Ye

URL: https://arxiv.org/abs/2111.05881, arXiv:2111.05881. 2 [CGY24] Sitan Chen, Weiyuan Gong, and Qi Ye. Optimal tradeoffs for estimating pauli observables,

arXiv
[2024]

2 [CGZ24] Sitan Chen, Weiyuan Gong, and Zhihan Zhang

URL:https://arxiv.org/abs/2404.19105, arXiv:2404.19105. 2 [CGZ24] Sitan Chen, Weiyuan Gong, and Zhihan Zhang. Adaptivity can help exponentially for shadow tomography,

arXiv
[2025]

2, 12 [Raz99] Ran Raz

URL: http://dx.doi.org/10.1103/PRXQuantum.6.010336, doi:10.1103/prxquantum.6.010336. 2, 12 [Raz99] Ran Raz. Exponential separation of quantum and classical communication complexity. In Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, STOC ’99, page ...

doi

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.

[1] [7]

2 [GPS24] Daniel Grier, Hakop Pashayan, and Luke Schaeffer

URL:https://arxiv.org/abs/2412.19022, arXiv:2412.19022. 2 [GPS24] Daniel Grier, Hakop Pashayan, and Luke Schaeffer. Sample-optimal classical shadows for pure states.Quantum, 8:1373, June

arXiv

[2] [8]

2, 4, 11 [GS19] David Gosset and John Smolin

URL: http://dx.doi.org/10.22331/q-2024-06-17-1373, doi:10.22331/q-2024-06-17-1373. 2, 4, 11 [GS19] David Gosset and John Smolin. A compressed classical description of quantum states. Leibniz Int. Proc. Inf., 135:8:1–8:9,

work page doi:10.22331/q-2024-06-17-1373 2024

[3] [1999]

doi:10.1145/301250.301343

Association for Computing Machinery. doi:10.1145/301250.301343. 1 [Rou15] Tim Roughgarden. Cs369e: Communication complexity (for algorithm designers) lecture #2: Lower bounds for one-way communication: Disjointness, index, and gap-hamming, January

arXiv

[4] [2004]

Limitations of Quantum Advice and One-Way Communication

IEEE Computer Society. URL: https://arxiv.org/pdf/quant-ph/0402095. 2 [Aar18] Scott Aaronson. Shadow tomography of quantum states,

work page Pith review arXiv

[5] [2008]

5, 17 [KGKB25] Robbie King, David Gosset, Robin Kothari, and Ryan Babbush

URL: https://theoryofcomputing.org/articles/v004a006, doi:10.4086/toc.2008.v004a006. 5, 17 [KGKB25] Robbie King, David Gosset, Robin Kothari, and Ryan Babbush. Triply efficient shadow tomography.PRX Quantum, 6(1), feb

work page doi:10.4086/toc.2008.v004a006 2008

[6] [2015]

3, 4, 5, 7, 14, 15, 17 [CCHL21] Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, and Jerry Li

URL: http://arxiv.org/abs/1511.06099, arXiv:1511.06099. 3, 4, 5, 7, 14, 15, 17 [CCHL21] Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, and Jerry Li. Exponential separations between learning with and without quantum memory,

work page arXiv

[7] [2018]

2 [ABF23] Alexandr Andoni, Jaroslaw Blasiok, and Arnold Filtser

URL: https://arxiv.org/abs/1711.01053, arXiv:1711.01053. 2 [ABF23] Alexandr Andoni, Jaroslaw Blasiok, and Arnold Filtser. Communication complexity of inner product in symmetric normed spaces. In Yael Tauman Kalai, editor,14th Innovations in Theoretical Computer Science Conference (ITCS 2023), volume 251 of Leibniz International Proceedings in Informatics ...

arXiv 2023

[8] [2019]

2, 4 [HKP20] Hsin-Yuan Huang, Richard Kueng, and John Preskill

URL: https://inspirehep.net/files/008cdc6d46be75c464574f793b329a1b, doi:10.4230/LIPIcs.TQC.2019.8. 2, 4 [HKP20] Hsin-Yuan Huang, Richard Kueng, and John Preskill. Predicting many properties of a quantum system from very few measurements.Nature Physics, 16(10):1050–1057, June

work page doi:10.4230/lipics.tqc.2019.8 2019