How hard is it to verify a classical shadow?

• URL: http://arxiv.org/abs/2510.08515v2
• Date: Tue, 14 Oct 2025 16:35:12 GMT
• Title: How hard is it to verify a classical shadow?
• Authors: Georgios Karaiskos, Dorian Rudolph, Johannes Jakob Meyer, Jens Eisert, Sevag Gharibian,
• Abstract summary: We study the study of verification of classical shadows from the perspective of computational complexity.<n>We first show that even for the simple classical shadow protocol of [Huang, Kueng, Preskill, Nature Physics 2020] utilizing local Clifford measurements, CSV is QMA-complete.<n>We also show that CSV for exponentially many observables is complete for a quantum generalization of the second level of a quantum hierarchy.
• Score: 0.5219568203653523
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Classical shadows are succinct classical representations of quantum states which allow one to encode a set of properties P of a quantum state rho, while only requiring measurements on logarithmically many copies of rho 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-rank observables, i.e., solved in randomized poly-time with standard sampling assumptions. Among other results, we also 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.

Related papers

• On the Complexity of Decoded Quantum Interferometry [39.951444958798014]
  We study the complexity of Decoded Quantum Interferometry (DQI), a recently proposed quantum algorithm for approximate optimization.<n>We argue that DQI is hard to classically simulate, and that the hardness comes from locating an exponentially large hidden subset.
  arXiv  Detail & Related papers  (2025-09-17T21:31:58Z)
• Improved Classical Shadow Tomography Using Quantum Computation [9.576327614980395]
  Classical shadow tomography (CST) involves obtaining enough classical descriptions of an unknown state via quantum measurements to predict the outcome of a set of quantum observables.<n>This paper introduces a new CST procedure that exponentially reduces the space complexity and quadratically improves the running time of CST with single-copy measurements.
  arXiv  Detail & Related papers  (2025-05-20T22:28:46Z)
• Kochen-Specker for many qubits and the classical limit [55.2480439325792]
  It is shown that quantum and classical predictions converge as the number of qubits is increases to the macroscopic scale.<n>This way to explain the classical limit concurs with, and improves, a result previously reported for GHZ states.
  arXiv  Detail & Related papers  (2024-11-26T22:30:58Z)
• Real classical shadows [0.0]
  We study the case where U corresponds to either local or global Clifford gates, and W consists of real-valued vectors.<n>Our results show that for various situations of interest, this real'' classical shadow protocol improves the sample complexity.
  arXiv  Detail & Related papers  (2024-10-30T22:15:39Z)
• Learning to Classify Quantum Phases of Matter with a Few Measurements [41.94295877935867]
  We study the identification of quantum phases of matter, at zero temperature, when only part of the phase diagram is known in advance. We show how to use our previous knowledge to construct an observable capable of classifying the phase even in the unknown region. An important application of our findings is the classification of the phases of matter obtained in quantum simulators.
  arXiv  Detail & Related papers  (2024-09-08T18:52:34Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [62.46800898243033]
  Recent progress in quantum learning theory prompts a question: can linear properties of a large-qubit circuit be efficiently learned from measurement data generated by varying classical inputs?<n>We prove that the sample complexity scaling linearly in $d$ is required to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d.<n>We propose a kernel-based method leveraging classical shadows and truncated trigonometric expansions, enabling a controllable trade-off between prediction accuracy and computational overhead.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Improved classical shadows from local symmetries in the Schur basis [4.462208715451194]
  We study the sample complexity of the classical shadows task. We present the first joint measurement protocol for classical shadows whose sample complexity scales with the rank of the unknown state.
  arXiv  Detail & Related papers  (2024-05-15T17:33:10Z)
• Classical shadows meet quantum optimal mass transport [4.604003661048267]
  We show that the classical shadow obtained measuring O(log n) copies of the state to be learned constitutes an accurate estimate with respect to the proposed distance. We apply the results to quantum generative adversarial networks, showing that quantum access to the state to be learned can be useful only when some prior information on such state is available.
  arXiv  Detail & Related papers  (2023-09-15T14:29:57Z)
• ShadowNet for Data-Centric Quantum System Learning [188.683909185536]
  We propose a data-centric learning paradigm combining the strength of neural-network protocols and classical shadows. Capitalizing on the generalization power of neural networks, this paradigm can be trained offline and excel at predicting previously unseen systems. We present the instantiation of our paradigm in quantum state tomography and direct fidelity estimation tasks and conduct numerical analysis up to 60 qubits.
  arXiv  Detail & Related papers  (2023-08-22T09:11:53Z)
• Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
  A test of quantumness is a protocol that allows a classical verifier to certify (only) that a prover is not classical. We show that tests of quantumness that follow a certain template, which captures recent proposals such as (Kalai et al., 2022) can in fact do much more. Namely, the same protocols can be used for certifying a qubit, a building-block that stands at the heart of applications such as certifiable randomness and classical delegation of quantum computation.
  arXiv  Detail & Related papers  (2023-03-02T14:18:17Z)
• On Classical and Hybrid Shadows of Quantum States [0.0]
  Classical shadows are a computationally efficient approach to storing quantum states on a classical computer. We discuss the advantages and limitations of using classical shadows to simulate many-body dynamics. We introduce the notion of a hybrid shadow, constructed from measurements on a part of the system instead of the entirety.
  arXiv  Detail & Related papers  (2022-06-14T06:25:24Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover. In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
  arXiv  Detail & Related papers  (2021-07-05T17:45:41Z)
• Experimental quantum state measurement with classical shadows [5.455606108893398]
  A crucial subroutine for various quantum computing and communication algorithms is to efficiently extract different classical properties of quantum states. We show how to project the quantum state into classical shadows and simultaneously predict $M$ different functions of a state with only $mathcalO(log M)$ measurements. Our experiment verifies the efficacy of exploiting (derandomized) classical shadows and sheds light on efficient quantum computing with noisy intermediate-scale quantum hardware.
  arXiv  Detail & Related papers  (2021-06-18T15:42:03Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.