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

Verification Complexity and Extension of Classical Shadows

Georgios Karaiskos, Asad Raza, Dorian Rudolph, Dax Enshan Koh, Sevag Gharibian

On Aqora:Koh Enshan, DaxKoh Enshan, Dax
quant-phSubmitted Sep 30, 2026• Announced Oct 1, 2026• 0 citations
arXivHTMLPDF

Abstract

Classical shadows are an influential framework for compressing copies of a given quantum state $ρ$ into classical data $S$, enabling many properties of $ρ$ to be predicted from relatively few copies. In this work, we study two natural questions involving shadows: (1) Given $S$, when can one efficiently verify that $S$ came from a genuine $n$-qubit state? This is called the Classical Shadow Validity (CSV) problem, introduced by Karaiskos, Rudolph, Meyer, Eisert, and Gharibian [ICALP 2026]. (2) Given $S$ that allows one to capture 2-local properties of $ρ$, can one fake or spoof a shadow $S'$ which predicts 3-local properties of some state? For (1), we show CSV is efficiently solvable for permutation-invariant shadows, QMA-hard for real, fermionic, and bosonic shadows, and both coNP-hard and QMA-hard when the observable family consists of all $n$-qubit Pauli strings. A result of independent interest along the way is a new upper bound qc-$Σ_2$ $\subseteq$ $\mathrm{P}^{\mathrm{PP}}$, where qc-$Σ_2$ is a quantum analogue of the second level of the polynomial hierarchy in which the first proof is quantum. For (2), we show intractability: Given the 2-local marginals $S$ of a quantum state $ρ$, estimating the 3-local marginals of $ρ$ is intractable unless QCMA $\subseteq$ BPP, even if the state $ρ$ is the unique state consistent with $S$.

AI Summary

The paper studies whether classical-shadow predictions are jointly consistent with a quantum state, and whether classical postprocessing can extend two-body marginal data to three-body predictions. Validity means consistency of recovered expectations, not certification of the measurement record’s provenance. For polynomially many permutation-invariant observables, validity is in $\mathsf P$ when reduced Schur–Weyl blocks are explicitly supplied, and in $\mathsf{BQP}$ under efficient quantum measurement access. Symmetrization reduces consistency to a polynomial-size SDP; the quantum algorithm first estimates the blocks. Validity is $\mathsf{QMA}$-hard for local real shadows using only $X/Z$ measurements, matchgate fermionic shadows in an input-specified particle-number sector with observables on at most five modes, and heterodyne/homodyne bosonic shadows. These reductions use an $XZ$-only history-state construction, tagged fermionic constraints with synthesized snapshots, and two-level bosonic encodings with moment-controlled leakage, respectively. Bosonic hardness uses recovery cutoff $M=1$, moment order $\ell=O(\log n)$, and bound $B=2^\ell$, without truncating candidate states. Consistency for all Pauli strings with succinct targets is both $\mathsf{QMA}$-hard and $\mathsf{coNP}$-hard. A postselected-learning argument additionally establishes $\mathrm{qc}$-$\Sigma_2\subseteq\mathsf P^{\mathsf{PP}}$. Finally, polynomial-time randomized reconstruction of requested three-qubit marginals to a fixed constant trace-norm error from two-qubit marginals would imply $\mathsf{QCMA}\subseteq\mathsf{BPP}$, even with a unique global completion. The reduction uses witness isolation, encoded history states, and separate witness-recovery and verification stages. Open questions include completeness of all-Pauli consistency for $\mathrm{qc}$-$\Sigma_2$, higher-alternation upper bounds, bosonic hardness with fixed moment parameters, and concrete cryptographic applications of extension hardness.

Little sign of AI-generated textAI use disclosed
The authors used generative AI tools to explore proof ideas, assist in identifying and closing gaps in proofs, and improve the exposition.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
70 pages

Related papers

How Hard Is It to Verify a Classical Shadow?

Georgios Karaiskos, Dorian Rudolph, Johannes Jakob Meyer +2 more

Classical shadows are succinct classical representations of quantum states which allow one to encode a set of properties P of a quantum state ρ, while only requiring measurements on logarithmically many copies of ρ in the size of P. In this work, we initiate the study of verification of classical shadows, denoted classical shadow validity (CSV), from the perspective of computational complexity, which asks: Given a classical shadow S, how hard is it to verify that S predicts the measurement statistics of a quantum state? We first show that even for the elegantly simple classical shadow protocol of [Huang, Kueng, Preskill, Nature Physics 2020] utilizing local Clifford measurements, CSV is QMA-complete. This hardness continues to hold for the high-dimensional extension of said protocol due to [Mao, Yi, and Zhu, PRL 2025]. In contrast, we show that for the HKP and MYZ protocols utilizing global Clifford measurements, CSV can be "dequantized" for low-Frobenius norm observables, i.e., solved in randomized poly-time with standard sampling assumptions. Finally, we show that CSV for exponentially many observables is complete for a quantum generalization of the second level of the polynomial hierarchy, yielding the first natural complete problem for such a class.

arXiv:2510.08515•Leibniz international proceedings in informatics•Oct 9, 2025•1 citation

Classical shadows with Pauli-invariant unitary ensembles

Kaifeng Bu, Dax Enshan Koh, Roy J. Garcia +1 more

Abstract Classical shadows provide a noise-resilient and sample-efficient method for learning quantum system properties, relying on a user-specified unitary ensemble. What is the weakest assumption on this ensemble that can still yield meaningful results? To address this, we focus on Pauli-invariant unitary ensembles—those invariant under multiplication by Pauli operators. For these ensembles, we present explicit formulas for the reconstruction map and sample complexity bounds and extend our results to the case when noise impacts the protocol implementation. Two applications are explored: one for locally scrambled unitary ensembles, where we present formulas for the reconstruction map and sample complexity bounds that circumvent the need to solve an exponential-sized linear system, and another for the classical shadows of quantum channels. Our results establish a unified framework for classical shadows with Pauli-invariant unitary ensembles, applicable to both noisy and noiseless scenarios for states and channels and primed for implementation on near-term quantum devices.

arXiv:2202.03272•npj Quantum Information•Jan 8, 2024•66 citations

Enhancing quantum state reconstruction with structured classical shadows

Zhen Qin, Joseph M. Lukens, Brian T. Kirby +1 more

While classical shadows can efficiently predict key quantum state properties, their suitability for certified quantum state tomography remains uncertain. In this paper, we address this challenge by introducing a projected classical shadow (PCS) that extends the standard classical shadow by incorporating a projection step onto the target subspace. For a general quantum state consisting of n qubits, our method requires a minimum of O (4 n ) total state copies to achieve a bounded recovery error in the Frobenius norm between the reconstructed and true density matrices, reducing to O (2 n r ) for states of rank r < 2 n —meeting information-theoretic optimal bounds in both cases. For matrix product operator states, we demonstrate that the PCS can recover the ground-truth state with O ( n 2 ) total state copies, improving upon the previously established Haar-random bound of O ( n 3 ). Numerical simulations validate our scaling results and demonstrate the practical accuracy of the proposed PCS method.

arXiv:2501.03144•npj Quantum Information•Sep 2, 2025•10 citations

Lower Bounds on Relative Error Quantum Compression and Classical Shadows

Sankar, Kaushik

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.

arXiv:2506.21345•Jun 26, 2025•1 citation

Shadow Engineering of Quantum Processes

Tian-Ci Tian, De-Tao Jiang, Wei-Ming Zhu +3 more

Characterizing quantum processes is essential for hardware benchmarking, error diagnosis, and algorithm verification. While recent work [PRX QUANTUM \textbf{4}, 040337 (2023)] extended classical shadows from quantum state to quantum process, enabling efficient single-channel $\mathcal{E}$ property prediction, its applicability to composite processes $f(\mathcal{E}_1, \mathcal{E}_2,\cdots, \mathcal{E}_k)$ remains unexplored. We introduce shadow engineering, a framework encoding the classical shadows of processes into sparse transfer matrices to predict $f(\mathcal{E}_1, \mathcal{E}_2,\cdots, \mathcal{E}_k)$ properties with proven polynomial sample complexity, matching single-channel efficiency while exponentially lower than quantum process tomography. Crucially, this approach repurposes existing $\mathcal{E}_m$-shadow data without physical execution of $f(\mathcal{E}_1, \mathcal{E}_2,\cdots, \mathcal{E}_k)$, enabling flexible quantum process characterization with minimal hardware overhead. We demonstrate the framework's effectiveness and practicality on a superconducting quantum processor for typical applications such as error mitigation and Hamiltonian dynamical simulation. This framework unlocks new capabilities for predicting complex quantum behaviors without physical re-execution, with immediate applications in near-term device calibration and quantum simulation.

quant-pharXiv:2606.12035•Jun 11, 2026•0 citations

QMA-hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge

Anne Broadbent, Alex B. Grilo

We provide several advances to the understanding of the class of Quantum Merlin-Arthur proof systems (QMA), the quantum analogue of NP. Our central contribution is proving a longstanding conjecture that the Consistency of Local Density Matrices (CLDM) problem is QMA-hard under Karp reductions. The input of CLDM consists of local reduced density matrices on sets of at most k qubits, and the problem asks if there is an n-qubit global quantum state that is locally consistent with all of the k-qubit local density matrices. The containment of this problem in QMA and the QMA-hardness under Turing reductions were proved by Liu [APPROX-RANDOM 2006]. Liu also conjectured that CLDM is QMA-hard under Karp reductions, which is desirable for applications, and we finally prove this conjecture. We establish this result using the techniques of simulatable codes of Grilo, Slofstra, and Yuen [FOCS 2019], simplifying their proofs and tailoring them to the context of OMA. In order to develop applications of CLDM, we propose a framework that we call locally simulatable proofs for QMA: this provides QMA proofs that can be efficiently verified by probing only k qubits and, furthermore, the reduced density matrix of any k-qubit subsystem of a good witness can be computed in polynomial time, independently of the witness. Within this framework, we show several advances in zero-knowledge in the quantum setting. We show for the first time a commit-and-open computational zero-knowledge proof system for all of QMA, as a quantum analogue of a “sigma” protocol. We then define a Proof of Quantum Knowledge, which guarantees that a prover is effectively in possession of a quantum witness in an interactive proof, and show that our zero-knowledge proof system satisfies this definition. Finally, we show that our proof system can be used to establish that QMA has a quantum non-interactive zero-knowledge proof system in the secret parameter setting.11The full version of this work can be found in https://arxiv.org/abs/1911.07782.

Annual Symposium on Foundations of Computer Science•Nov 1, 2020•22 citations
Classical shadows are an influential framework for compressing copies of a given quantum state ρρρ into classical data SSS, enabling many properties of ρρρ to be predicted from relatively few copies. In this work, we study two natural questions involving shadows: (1) Given SSS, when can one efficiently verify that SSS came from a genuine nnn-qubit state? This is called the Classical Shadow Validity (CSV) problem, introduced by Karaiskos, Rudolph, Meyer, Eisert, and Gharibian [ICALP 2026]. (2) Given SSS that allows one to capture 2-local properties of ρρρ, can one fake or spoof a shadow S′S'S′ which predicts 3-local properties of some state? For (1), we show CSV is efficiently solvable for permutation-invariant shadows, QMA-hard for real, fermionic, and bosonic shadows, and both coNP-hard and QMA-hard when the observable family consists of all nnn-qubit Pauli strings. A result of independent interest along the way is a new upper bound qc-Σ2Σ_2Σ2​ ⊆\subseteq⊆ PPP\mathrm{P}^{\mathrm{PP}}PPP, where qc-Σ2Σ_2Σ2​ is a quantum analogue of the second level of the polynomial hierarchy in which the first proof is quantum. For (2), we show intractability: Given the 2-local marginals SSS of a quantum state ρρρ, estimating the 3-local marginals of ρρρ is intractable unless QCMA ⊆\subseteq⊆ BPP, even if the state ρρρ is the unique state consistent with SSS.
The paper studies whether classical-shadow predictions are jointly consistent with a quantum state, and whether classical postprocessing can extend two-body marginal data to three-body predictions. Validity means consistency of recovered expectations, not certification of the measurement record’s provenance.
For polynomially many permutation-invariant observables, validity is in P\mathsf PP when reduced Schur–Weyl blocks are explicitly supplied, and in BQP\mathsf{BQP}BQP under efficient quantum measurement access. Symmetrization reduces consistency to a polynomial-size SDP; the quantum algorithm first estimates the blocks. Validity is QMA\mathsf{QMA}QMA-hard for local real shadows using only X/ZX/ZX/Z measurements, matchgate fermionic shadows in an input-specified particle-number sector with observables on at most five modes, and heterodyne/homodyne bosonic shadows. These reductions use an XZXZXZ-only history-state construction, tagged fermionic constraints with synthesized snapshots, and two-level bosonic encodings with moment-controlled leakage, respectively. Bosonic hardness uses recovery cutoff M=1M=1M=1, moment order ℓ=O(log⁡n)\ell=O(\log n)ℓ=O(logn), and bound B=2ℓB=2^\ellB=2ℓ, without truncating candidate states.
Consistency for all Pauli strings with succinct targets is both QMA\mathsf{QMA}QMA-hard and coNP\mathsf{coNP}coNP-hard. A postselected-learning argument additionally establishes qc\mathrm{qc}qc-Σ2⊆PPP\Sigma_2\subseteq\mathsf P^{\mathsf{PP}}Σ2​⊆PPP. Finally, polynomial-time randomized reconstruction of requested three-qubit marginals to a fixed constant trace-norm error from two-qubit marginals would imply QCMA⊆BPP\mathsf{QCMA}\subseteq\mathsf{BPP}QCMA⊆BPP, even with a unique global completion. The reduction uses witness isolation, encoded history states, and separate witness-recovery and verification stages.
Open questions include completeness of all-Pauli consistency for qc\mathrm{qc}qc-Σ2\Sigma_2Σ2​, higher-alternation upper bounds, bosonic hardness with fixed moment parameters, and concrete cryptographic applications of extension hardness.
Classical shadows are succinct classical representations of quantum states which allow one to encode a set of properties P of a quantum state ρ, while only requiring measurements on logarithmically many copies of ρ in the size of P. In this work, we initiate the study of verification of classical shadows, denoted classical shadow validity (CSV), from the perspective of computational complexity, which asks: Given a classical shadow S, how hard is it to verify that S predicts the measurement statistics of a quantum state? We first show that even for the elegantly simple classical shadow protocol of [Huang, Kueng, Preskill, Nature Physics 2020] utilizing local Clifford measurements, CSV is QMA-complete. This hardness continues to hold for the high-dimensional extension of said protocol due to [Mao, Yi, and Zhu, PRL 2025]. In contrast, we show that for the HKP and MYZ protocols utilizing global Clifford measurements, CSV can be "dequantized" for low-Frobenius norm observables, i.e., solved in randomized poly-time with standard sampling assumptions. Finally, we show that CSV for exponentially many observables is complete for a quantum generalization of the second level of the polynomial hierarchy, yielding the first natural complete problem for such a class.
Abstract Classical shadows provide a noise-resilient and sample-efficient method for learning quantum system properties, relying on a user-specified unitary ensemble. What is the weakest assumption on this ensemble that can still yield meaningful results? To address this, we focus on Pauli-invariant unitary ensembles—those invariant under multiplication by Pauli operators. For these ensembles, we present explicit formulas for the reconstruction map and sample complexity bounds and extend our results to the case when noise impacts the protocol implementation. Two applications are explored: one for locally scrambled unitary ensembles, where we present formulas for the reconstruction map and sample complexity bounds that circumvent the need to solve an exponential-sized linear system, and another for the classical shadows of quantum channels. Our results establish a unified framework for classical shadows with Pauli-invariant unitary ensembles, applicable to both noisy and noiseless scenarios for states and channels and primed for implementation on near-term quantum devices.
While classical shadows can efficiently predict key quantum state properties, their suitability for certified quantum state tomography remains uncertain. In this paper, we address this challenge by introducing a projected classical shadow (PCS) that extends the standard classical shadow by incorporating a projection step onto the target subspace. For a general quantum state consisting of n qubits, our method requires a minimum of O (4 n ) total state copies to achieve a bounded recovery error in the Frobenius norm between the reconstructed and true density matrices, reducing to O (2 n r ) for states of rank r < 2 n —meeting information-theoretic optimal bounds in both cases. For matrix product operator states, we demonstrate that the PCS can recover the ground-truth state with O ( n 2 ) total state copies, improving upon the previously established Haar-random bound of O ( n 3 ). Numerical simulations validate our scaling results and demonstrate the practical accuracy of the proposed PCS method.
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.
Characterizing quantum processes is essential for hardware benchmarking, error diagnosis, and algorithm verification. While recent work [PRX QUANTUM \textbf{4}, 040337 (2023)] extended classical shadows from quantum state to quantum process, enabling efficient single-channel E\mathcal{E}E property prediction, its applicability to composite processes f(E1,E2,⋯ ,Ek)f(\mathcal{E}_1, \mathcal{E}_2,\cdots, \mathcal{E}_k)f(E1​,E2​,⋯,Ek​) remains unexplored. We introduce shadow engineering, a framework encoding the classical shadows of processes into sparse transfer matrices to predict f(E1,E2,⋯ ,Ek)f(\mathcal{E}_1, \mathcal{E}_2,\cdots, \mathcal{E}_k)f(E1​,E2​,⋯,Ek​) properties with proven polynomial sample complexity, matching single-channel efficiency while exponentially lower than quantum process tomography. Crucially, this approach repurposes existing Em\mathcal{E}_mEm​-shadow data without physical execution of f(E1,E2,⋯ ,Ek)f(\mathcal{E}_1, \mathcal{E}_2,\cdots, \mathcal{E}_k)f(E1​,E2​,⋯,Ek​), enabling flexible quantum process characterization with minimal hardware overhead. We demonstrate the framework's effectiveness and practicality on a superconducting quantum processor for typical applications such as error mitigation and Hamiltonian dynamical simulation. This framework unlocks new capabilities for predicting complex quantum behaviors without physical re-execution, with immediate applications in near-term device calibration and quantum simulation.
We provide several advances to the understanding of the class of Quantum Merlin-Arthur proof systems (QMA), the quantum analogue of NP. Our central contribution is proving a longstanding conjecture that the Consistency of Local Density Matrices (CLDM) problem is QMA-hard under Karp reductions. The input of CLDM consists of local reduced density matrices on sets of at most k qubits, and the problem asks if there is an n-qubit global quantum state that is locally consistent with all of the k-qubit local density matrices. The containment of this problem in QMA and the QMA-hardness under Turing reductions were proved by Liu [APPROX-RANDOM 2006]. Liu also conjectured that CLDM is QMA-hard under Karp reductions, which is desirable for applications, and we finally prove this conjecture. We establish this result using the techniques of simulatable codes of Grilo, Slofstra, and Yuen [FOCS 2019], simplifying their proofs and tailoring them to the context of OMA. In order to develop applications of CLDM, we propose a framework that we call locally simulatable proofs for QMA: this provides QMA proofs that can be efficiently verified by probing only k qubits and, furthermore, the reduced density matrix of any k-qubit subsystem of a good witness can be computed in polynomial time, independently of the witness. Within this framework, we show several advances in zero-knowledge in the quantum setting. We show for the first time a commit-and-open computational zero-knowledge proof system for all of QMA, as a quantum analogue of a “sigma” protocol. We then define a Proof of Quantum Knowledge, which guarantees that a prover is effectively in possession of a quantum witness in an interactive proof, and show that our zero-knowledge proof system satisfies this definition. Finally, we show that our proof system can be used to establish that QMA has a quantum non-interactive zero-knowledge proof system in the secret parameter setting.11The full version of this work can be found in https://arxiv.org/abs/1911.07782.