1 Introduction↩︎

Fully classically describing a quantum state \(\rho\) has long been known to require exponential overhead, making characterizing the outputs of quantum devices a challenging task. Indeed, for a state \(\rho\) on \(n\) qubits, i.e., of dimension \(D=2^n\), a sample complexity of \(\Theta(D^2)\) copies of \(\rho\) are known to be necessary and sufficient for full quantum state tomography [1], [2]. In general, however, one is not necessarily interested in learning everything about \(\rho\), but only a specific set \(P\) of properties. Formally, we may model these as a set of \(M\) measurement operators \(P=\set{P_i}_{i=1}^M\), where one is interested in computing \(\operatorname{Tr}(\rho P_i)\). The natural question is now: Can one avoid full state tomography in this case?

In 2018, Aaronson showed [3] the answer is yes: for set \(P\) of \(2\)-outcome measurements, given \(k\) copies of \(\rho\), one can produce estimates \(b_1,\ldots, b_M\in[0,1]\) such that with probability at least \(1-\delta\), one has \(\abs{\operatorname{Tr}(P_i\rho)-b_i}\leq \epsilon\) for all \(i\). The magic here is that the sample complexity, \(k\), can be chosen polylogarithmic in the dimension \(D\) and number of measurements \(M\), i.e., \[k\in O\left( \log \frac{1}{\delta} \cdot \epsilon^{-5} \cdot \log^4 M \cdot \log D \right).\] While this original protocol was not yet time efficient, it did not take long for the latter to be rectified, e.g., Brand\(\tilde{\mathrm{a}}\)o, Kalev, Li, Lin, Svore, Wu [4]. Indeed, soon after Huang, Kueng and Preskill (HKP) discovered [5] a remarkably simple and efficient classical shadow tomography procedure, which for a given \(P\), randomly samples unitary \(U\) from an “appropriate” ensemble \(\cal U\) of unitaries, and measures \(U\rho U^\dagger\) in the standard basis. Roughly, the resulting string can be thought of as a “snapshot” of \(\rho\), and the set of all snapshots constitutes the classical shadow, \(S\). A recovery procedure via median-of-means is then specified, so that given \(S\), one can recover estimates for \(\operatorname{Tr}(\rho M_i)\). For general \(P\) and \(\mathcal{U}\), the procedure has sample complexity \[\label{eqn:shadowbound} O \left( \frac{\log(M)}{\epsilon^2} \max_{1 \leq i \leq M} \left\| P_i - \frac{\operatorname{Tr}(P_i)}{2^n} I \right\|_{\text{shadow}}^2 \right),\tag{1}\] where the shadow norm depends on \(P\) and \(\mathcal{U}\) (see 2 for details on the HKP protocol.) For \(\mathcal{U}\) the set of global Cliffords and the set of \(k\)-local Cliffords, the shadow norm in 1 is at most \(3\operatorname{Tr}(P_i^2)\) and \(4^k \|P_i\|_{\infty}^2\), respectively. Thus, for example, to predict measurement results for \(P\) the set of \(k\)-local Pauli strings¹, one obtains a sample and time efficient² protocol, which requires only \(\log(M)\) copies, and as a bonus needs only measure a single copy at a time.

1.0.0.1 Verifying classical shadows.

This work initiates the study of the natural question:

Given as input a “classical shadow” \(S\), what is the complexity of verifying that \(S\) actually “predicts” the measurement statistics of some \(\rho\) against \(P\)?

As stated, this question is ill-posed, in the sense that we are not aware of a formal definition of a “classical shadow” in the literature. Thus, to remedy this, we first provide a general formal definition:

This definition says nothing about prediction accuracy; it simply formalizes the idea that a “classical shadow” is a multi-set of strings \(S\), in principle obtained via some set of efficient measurements on copies of a physical state \(\rho\), coupled with a set of target observables \(O\) and an efficient recovery procedure \(A\) for “extracting predictions”. An alternate possible definition might be not to give shadow \(S\) as a fixed sequence of strings, but rather to generate \(S\) on-the-fly by sampling from some unknown distribution (thus capturing the idea of measurement bases \(\mathcal{U}\) as in HKP). To capture this, we also define a “sampled classical shadow” in 6, and show the complexity of verifying “classical shadows” ([def:classical-shadow]) versus “sampled classical shadows” (28) is equivalent under randomized reductions. For simplicity, we thus work with [def:classical-shadow], as its input model is the standard one used in (e.g.) BQP and QMA.

Moving on, the task of checking the validity of a shadow, i.e., that the outputs of \(A\) correctly predict measurement statistics, is formalized as:

The theme of this work is to characterize the complexity of this problem and its variants, including for the HKP protocol with local Clifford measurements, “dequantization” results for global Clifford measurements, and the case of exponentially many observables.

1.0.0.2 Comparison to and distinction from CONSISTENCY problem.

Before proceeding, the reader familiar with quantum complexity theory may notice that, at least in the setting of polynomially many observables \(O_i\), CSV is eerily similar to the QMA-complete CONSISTENCY problem of Liu [6]. In the latter, the input is a set of \(k\)-local reduced states \(\rho_i\) acting on a subset \(S_i\) of \(k\in O(1)\) out of \(n\) qubits each, and the question is whether there exists an \(n\)-qubit state \(\rho\) such that for all \(i\), \(\operatorname{Tr}_{[n]\setminus S_i}(\rho)\approx \rho_i\)? Indeed, as our definition of classical shadows is intentionally very general, it includes as a special case the CONSISTENCY problem. From this, one immediately obtains that CSV is at least QMA-hard (2). This is not the point of this paper!

The point is that classical shadow protocols used in practice typically do not produce local density operators as in CONSISTENCY, but rather highly non-local snapshots (e.g. \(n\)-local operators which are the tensor product of \(n\) non-trivial single qubit states)! Our goal is thus to characterize the complexity of CSV for precisely these experimentally relevant snapshots, to which the QMA-hardness of CONSISTENCY does not obviously apply. Indeed, as will be discussed shortly, a reduction from CONSISTENCY to CSV will have to overcome the well-known challenging problem of how to construct a global quantum snapshot from local overlapping reduced density operators (as in CONSISTENCY).

1.0.0.3 Motivation and application to near-term devices.

(1) As near-term experimental devices remain noisy, verifying that a device actually outputs the state intended remains a major challenge. Well-known examples include verification of quantum advantage experiments such as Random Circuit Sampling [7] or Boson Sampling [8], [9]. In the same vein, it is arguably important to verify the validity of snapshots output by classical shadow experiments; this is true even if the experimenter fully trusts that the device has not been tampered with. More generally, in the distributed cloud setting where the user does not trust the device, CSV becomes yet more crucial. (2) The study of \(\mathsf{CSV}\) is important to the study of classes \(\mathsf{QMA}\) versus \(\mathsf{QCMA}\) (i.e. \(\mathsf{QMA}\) with a classical proof [10]), as it underpins the central open question of whether quantum witnesses are fundamentally more powerful than classical ones. Specifically, if a QMA verifier’s measurement falls into a class of observables \(O\) whose output statistics could be efficiently predicted by poly-size classical shadows, and if CSV for said shadows could be solved by a (uniformly generated) poly-time quantum circuit, then \(\mathsf{QMA}=\mathsf{QCMA}\), which would be a breakthrough.

(3) We further motivate the study of \(\mathsf{CSV}\) by framing it as a natural quantum analogue of the classical Sparse Representation problem (\(\mathsf{SR}\)) (see 1) under the lens of classical shadow protocols. In \(\mathsf{SR}\), one has to decide if a sparse vector, consistent with a given measurement sketch, exists. While \(\mathsf{SR}\) is \(\mathsf{NP}\)-hard in the general case [11], it becomes efficiently solvable (via convex relaxation) when the measurement matrix satisfies the Restricted Isometry Property (RIP) [12]. In the quantum setting an analogous compressed sensing phenomenon is known: under a low-rank promise on the state and suitable measurements, convex programs can efficiently reconstruct the state [13]. Our work studies the quantum SR question arising in the classical shadow framework, [3], [5].

1.0.0.4 Our results.

We organize our discussion⁵ in terms of (1) polynomially many observables, (2) exponentially many observables, and (3) further variants of \(\mathsf{CSV}\) with connections to \(\mathsf{QMA(2)}\). For clarity, our main results involve (1) and (2). All hardness results are under poly-time many-one reductions.
1. Polynomially many observables: Hardness and dequantization. As previously stated, it is not difficult to see that \(\mathsf{CSV}\) in its most general form is QMA-complete (2). Here, we focus on the more challenging case of the HKP protocol [5] (instantiated with either local or global Clifford measurements), as well as a high-dimensional generalization thereof due to Mao, Yi and Zhu (MYZ) for odd-prime local dimension \(d\) [14].

To begin, we define \(\mathsf{CSV}_{\mathsf{HKP}}\) as CSV for the HKP protocol instantiated with local Clifford measurements (16); roughly, the elements of \(S\) are \(n\)-bit strings, conjugated by Pauli strings in \(\set{X,Y,Z}^n\), and the observables are \(k\)-local Pauli strings for \(k\in O(1)\). We show the following statement.

In words, deciding if a given HKP classical shadow based on local Clifford measurements is valid is intractable, even when the observables are \(6\)-local and essentially arranged on a line (formally on a spatially sparse hypergraph (in the sense of Ref.[15]; 2)). Specifically, the hardness construction may be viewed as 1D nearest-neighbor on qudits of dimension \(8\). Each qudit is then decomposed into \(3\) qubits, and neighboring pairs of qudits \((q_i,q_{i+1})\) have a \(6\)-local observable acting jointly on their constituent qubits.

Defining \(\mathsf{CSV}_{\mathsf{MYZ}}\) (19) analogously for MYZ on odd prime local dimensions \(d\), we next show:

Here, since we are allowed to work with larger \(d\), we cleanly obtain hardness with all observables acting on pairs of nearest neighbor qudits \((q_i,q_{i+1})\).

Finally, we study CSV for the HKP protocol instantiated with global Clifford measurements, denoted \(\mathsf{CSV}_{\mathsf{GC}}\) (20). We show a “dequantization” result as follows, for Frobenius norm \(\norm{A}_{\mathrm F}=\sqrt{\operatorname{Tr}(A^\dagger A)}\):

First, while the Frobenius norm bound above may a priori seem strong, this setting captures natural tasks such as (e.g.) fidelity estimation against pure and low rank states [5]. Moreover, the global Clifford HKP protocol itself is efficient precisely in this regime, i.e. when \(\|O_i\|_F\le \mathrm{poly}(n)\), coinciding with the regime in which 3 dequantizes \(\mathsf{CSV}_{\mathsf{GC}}\). By a similar argument, this “dequantization" result extends to the MYZ protocol with global Clifford measurements, under the same assumptions (18). Second, we dub this a”dequantization” result, in that conditions (a) and (b) are similar to those in previous dequantization works, e.g., Tang [16] and Chia, Gilyén, Li, Lin, Tang and Wang [17], allowing randomized linear algebra techniques to be employed. Specifically, our definition of sampling and query access is from [17].
2. Exponentially many observables. We next consider CSV with exponentially many observables. Although a priori this setting may seem unrealistic, King, Gosset, Kothari and Babbush gave [18] an explicit polynomial-sample complexity shadow protocol for the set of all \(4^n\) Pauli string observables, \(\set{I,X,Y,Z}^n\). (Note the time complexity is still exponential, but in our setting, we do not produce the shadow, but receive it as input; thus, this overhead is not relevant.) What is also relevant is that Ref. [18] gives a poly-time recovery algorithm for the observable expectations, assuming one only demands constant additive error. We show the following statement.

Let us discuss strengths and weaknesses: The strengths are that (1) the result holds even if one need only recover constant precision approximations of observable predictions, and (2) 4 yields the first natural complete problem for a quantum generalization of (a level of) the polynomial hierarchy (PH). Specifically, \(\mathsf{qc\text{-}\Sigma_2}\) (10) is a quantum generalization of \(\Sigma_2^p\), the second level of PH, in which the first proof is a mixed quantum state, the second a classical string, and the verifier is quantum. We remark this is the first work studying \(\mathsf{qc\text{-}\Sigma_2}\), though other variants of quantum PH have been studied in previous works [19]–[22]. The weakness is that, unlike 1, we do not prove the result for the specific observable set of Ref. [18], i.e., for \(\set{I,X,Y,Z}^n\).
3. Further variants of \(\mathsf{CSV}\) and connections to \(\mathsf{QMA(2)}\). For completeness, we also show the following for variants of \(\mathsf{CSV}\):

1. (5) CSV where the consistent state must be product, i.e., \(\rho=\rho_A\otimes\rho_B\), is \(\mathsf{QMA(2)}\)-complete⁶ for polynomially many observables, and \(\mathsf{qc\text{-}\Sigma_2(2)}\)-complete (11) for exponentially many observables. As an intermediate step, the proof shows that \(\mathsf{\mathsf{SuperQMA}(2)}_{\mathrm{poly}}=\mathsf{QMA(2)}\), where \(\mathsf{\mathsf{SuperQMA}(2)}_{\mathrm{poly}}\) is a product state generalization of \(\mathsf{QMA^+}\) from Ref. [24].

2. Verifying if a set of classical shadows, each possibly with different observables, all correspond to the same state \(\rho\) (30) is QMA-complete (13) and \(\mathsf{qc\text{-}\Sigma_2}\)-complete (15) for polynomially many and exponentially many observables, respectively.

1.0.0.5 Techniques.

We focus on QMA-completeness of \(\mathsf{CSV}_{\mathsf{HKP}}\) (1), “dequantization" of low-Frobenius norm \(\mathsf{CSV}_{\mathsf{GC}}\) (3), and \(\mathsf{qc\text{-}\Sigma_2}\)-completeness of CSV with exponentially many observables (4).
QMA-completeness of \(\mathsf{CSV}_{\mathsf{HKP}}\). Ideally, we wish to reduce the QMA-complete CONSISTENCY problem on \(k\)-local reduced density operators \(\rho_i\) to \(\mathsf{CSV}_{\mathsf{HKP}}\). The challenge? Each \(\rho_i\) acts on only \(k\)-qubits. HKP classical shadows with local Clifford measurements, on the other hand, have shadow elements \(s_i\) which are highly non-local — each \(s_i\) is an \(n\)-qubit tensor product of eigenvectors of single-qubit Pauli matrices. And”stitching” together local information, i.e., the \(\rho_i\), to obtain globally consistent information, i.e., the \(s_i\), is a difficult task, reminiscent of the quantum marginal problem.

To overcome this requires a series of steps. First, we start with the 1D CONSISTENCY problem on qudits, so that it suffices to stitch together nearest neighbor reduced states \((\rho_{i,i+1},\rho_{i+1,i+2})\) on the line. To this end, we first show⁷ QMA-completeness of 1D CONSISTENCY with local dimension \(d=8\) via many-one reduction by combining the locally simulatable technique of Broadbent and Grilo [26] with the QMA-complete result for the 1D Local Hamiltonian problem with \(d=8\) of Hallgren, Nagaj, and Narayanaswami [27]. Then, we take the local nearest-neighbor reduced states \(\rho_i\) on qu-\(8\)-its from 1D CONSISTENCY, decompose each qudit \(q_i\) into a triple of qubits \(T_i\), and consider all possible \(6\)-local HKP shadows on pairs \((T_i,T_{i+1})\). Crucially, we know under the HKP protocol that any valid local shadow’s expectation should exactly recover the corresponding state \(\rho_i\). Using this fact and our 1D setup, one can derive a linear program (LP) which captures “how much weight/probability” to put onto each local shadow, so that the “local probabilities” are consistent with some global HKP shadow if and only if the 1D CONSISTENCY instance we started with is a YES instance.

Unfortunately, solving this LP is itself not enough, because we next need to simulate the probability of a local shadow \(s_j\) occurring when measuring local Cliffords in HKP by repeating \(s_j\) an appropriate integer number of times in our shadow set \(S\). We must, in fact, do this exactly to ensure consistency, and so we next “round” our LP into an integer program (IP) to give us integer weights on local shadows. This raises the potential roadblock that solving integer programs is NP-hard, but here we again crucially use the fact that we are working in 1D. Specifically, we exploit the 1D structure to design an efficient dynamic program to solve the IP, obtaining the desired integer weights on local shadows. Finally, we construct a list of global shadows by repeatedly carefully stitching together strings of local shadows under appropriate permutations given by a perfect matching.
Dequantization of low-Frobenius-norm \(\mathsf{CSV}_{\mathrm{GC}}\). For global Clifford shadows, we work with the abstract observable consistency problem, \(\mathsf{ObsCon}_{\mathrm{F,Samp}}\), whose input consists of pairs \((O_i,y_i)\) with \(\|O_i\|_F\le \mathrm{poly}(n)\), together with additional sampling and query access assumptions to the observables. The consistency conditions can then be viewed as an SDP feasibility problem with bounded-Frobenius-norm constraint matrices. We invoke the randomized classical SDP solver of [17], whose running time is polynomial in the Frobenius bound, the inverse promise gap, the number of constraints, and \(\log N\) for system dimension \(N=2^n\). This yields a randomized polynomial-time algorithm for \(\mathsf{CSV}_{\mathrm{GC}}\) under the stated sampling and query assumptions. The same proof applies to the global-Clifford MYZ protocol after replacing \(N=2^n\) by \(N=d^n\); for fixed local dimension \(d\), one has \(\log N=n\log d=O(n)\), so the runtime remains polynomial in the input size.
\(\mathsf{qc\text{-}\Sigma_2}\)-completeness of CSV with exponentially many observables. To connect \(\mathsf{CSV}\) with \(\mathsf{qc\text{-}\Sigma_2}\), we use the \(\mathsf{QMA^+}\) formalism of Aharonov and Regev [24], in which one is given polynomially many measurements \(\Pi_i\) and targets \(r_i\in \mathbb{R}\), and asks whether there is a state \(\rho\) such that \(\operatorname{Tr}(\Pi_i\rho)\approx r_i\) for all \(i\). While Ref. [24] showed \(\mathsf{QMA^+}=\mathsf{QMA}\), here we define the analogous class with exponentially many measurements \(\Pi_i\), denoted \(\mathsf{SuperQMA}_{\mathrm{exp}}\). We prove that \(\mathsf{CSV}\) with exponentially many observables is \(\mathsf{SuperQMA}_{\mathrm{exp}}\)-complete, and subsequently show that \(\mathsf{SuperQMA}_{\mathrm{exp}}=\mathsf{qc\text{-}\Sigma_2}\). One direction encodes a \(\mathsf{qc\text{-}\Sigma_2}\) verifier as an exponentially indexed family of consistency checks. Conversely, for \(\mathsf{SuperQMA}_{\mathrm{exp}}\subseteq\mathsf{qc\text{-}\Sigma_2}\), the existential quantum proof provides the candidate globally consistent state, while the universal classical proof specifies one of the exponentially many checks to test. The remaining technical ingredient is amplification for \(\mathsf{qc\text{-}\Sigma_2}\): in the NO case, Sion’s minimax theorem gives a single distribution over classical challenges that is bad against every quantum state; a matrix Hoeffding bound sparsifies this distribution to a polynomial-size list of challenges, after which standard weak-error amplification applies.

1.0.0.6 Open questions.

We have initiated the study of the complexity of verifying classical shadows. For hardness, an important open question is whether other specific classical shadow protocols and observable sets have QMA-hard CSV problems? In the case of exponentially many observables, for example, can one give a \(\mathsf{qc\text{-}\Sigma_2}\)-completeness proof of CSV for the protocol of King, Gosset, Kothari and Babbush [18]? The main bottleneck we faced here was that, unlike in our proof for HKP with polynomially many observables (1), it is not clear how to start from an “exponential size” analogue of the QMA-complete 1D CONSISTENCY problem. A natural idea might be to start with translationally invariant 1D systems [28]. Such systems, however, act on exponentially many qudits, whereas our setting requires polynomially many qubits — the exponentiality occurs only in the number of observables for CSV. Finally, are there instances of CSV aside from our HKP, MYZ global Clifford results which can also be dequantized, or even better, solved classically without sampling assumptions?

1.0.0.7 Organization.

2 begins with preliminaries, including reviews of the HKP and MYZ classical shadow protocols. 3 studies the general CSV problem (i.e., not restricted to any particular shadow protocol), including the case of exponentially many observables. 4 studies the HKP and MYZ protocols, showing QMA-hardness and our dequantization result. 5 studies product variants of CSV, and 6 the sampled and multiple shadow consistency variant of CSV.

2 Preliminaries↩︎

2.0.0.1 Definitions.

We use \(A\leq B\) and \(A\leq_r B\) to denote poly-time deterministic many-one and poly-time randomized reductions from \(A\) to \(B\), respectively.

Note our definition allows exponentially many checks, so long as each check can be efficiently generated on demand. We further remark that our definition \(\mathsf{SuperQMA}_{\mathrm{poly}}\), i.e., with \(m=\mathrm{poly}(|x|)\), coincide with \(\mathsf{QMA^+}\) from Ref. [24]. However, to the best of our knowledge, our \(\mathsf{SuperQMA}_{\mathrm{exp}}\) with \(m=\mathrm{exp}(|x|)\) has not been considered elsewhere before.

2.0.0.2 Observables.

In quantum mechanics, an observable is represented by a Hermitian operator \(O\). Its real eigenvalues correspond to the possible outcomes of a measurement. Throughout this work, we assume without loss of generality that all observables \(O_i\) are normalized such that their operator norm \(\|O_i\| \leq 1\). This implies that all eigenvalues \(\lambda\) of \(O_i\) lie in the interval \([-1, 1]\). This is a standard normalization, as any observable \(O\) can be efficiently rescaled by a factor \(C \geq \|O\|\) to satisfy this condition, which correspondingly rescales the expectation values and promise gap parameters in our problems.

2.0.0.3 Succinct access assumption.

When we say that we assume succinct access to a set \(\{A_i^{(n)}\}_{i=1}^m\), with \(n\) the natural size parameter of the instance (e.g., number of qubits for observables or precision parameter for a real value), we mean that given an index \(i\), a \(\mathrm{poly}(n)\)-bit description of \(A_i\) can be produced in \(\mathrm{poly}(n)\)-time.

2.0.0.4 Huang-Kueng-Preskill classical shadow framework.

Here we briefly describe a classical shadow protocol proposed by Huang, Kueng and Preskill in Ref. [5]. For an unknown \(n\)-qubit state \(\rho\) fix an ensemble \(\mathcal{U}\) of unitaries on \(n\) qubits. In each round do the following: sample \(U\sim\mathcal{U}\), measure \(U\rho U^\dagger\) in the computational basis to get a bitstring \(b_\ell\in\{0,1\}^n\), and store a succinct classical description of \(U_\ell^\dagger\ket{b_\ell}\bra{b_\ell}U_\ell\). The average channel \[\mathcal{M}(\rho)=\mathbb{E}_{U\sim\mathcal{U}}\sum_{b}\braket{b|U\rho U^\dagger|b}\,U^\dagger\ket{b}\bra{b}U\] is invertible for tomographically complete \(\mathcal{U}\), so a single-shot snapshot is \[\hat{\rho}_\ell=\mathcal{M}^{-1}\big(U_\ell^\dagger\ket{b_\ell}\bra{b_\ell}U_\ell\big),\qquad \mathbb{E}[\hat{\rho}_\ell]=\rho .\] For any observable \(O\) we use \(\hat{o}_\ell(O):=\operatorname{Tr}[O\,\hat{\rho}_\ell]\). Partition the \(L\) rounds into \(K\) blocks \(B_1,\ldots,B_K\) of (nearly) equal size, set \[\overline{o}_k=\frac{1}{|B_k|}\sum_{\ell\in B_k}\hat{o}_\ell(O), \quad A(S,O)=\operatorname{median}\{\overline{o}_1,\dots,\overline{o}_K\}\; \text{(rounded to \chi bits).}\] Since \(\mathbb{E}[U_\ell^\dagger\ket{b_\ell}\bra{b_\ell}U_\ell]=\mathcal{M}(\rho)\), linearity gives \(\mathbb{E}[\hat{\rho}_\ell]=\rho\) and thus \(\mathbb{E}[\hat{o}_\ell(O)]=\operatorname{Tr}(O\rho)\) (unbiased). The median of means provides robustness. We need \(L=O \left( \frac{\log(M)}{\epsilon^2} \max_{1 \leq i \leq M} \left\| O_i - \frac{\operatorname{Tr}(O_i)}{2^n} I \right\|_{\text{shadow}}^2 \right)\) samples to estimate \(M\) observables up to error \(\epsilon\).

2.0.0.5 Robust classical shadow version.

The variant of the HKP scheme presented in Ref. [29] – which has attractive features concerning the quantum ensemble \(\mathcal{U}\) of unitaries implemented – shares most of the above properties from the perspective of the present work. There, the ensemble of unitaries \(\mathcal{U}\) is taken to be as the set of unitaries of the form \[U = U_C U_S U_H,\] where \(U_C\) is an \(n\)-qubit unitary that consists of i.i.d.random controlled-\(Z\) gates, \(U_S\) is a single layer of gates drawn i.i.d.from \(\{I_2,S\}\), where \(S:= (I_2+iZ)/\sqrt{2}\) is a single qubit Clifford \(S\) gate, and \(U_H\) is a fixed single layer of single qubit Hadamard gates. This set of unitaries is a not quite tomographically complete subset of Clifford circuits. But one can still use single-shot snapshots \[\hat{\rho}_\ell=\mathcal{M}^{-1}\big(U_\ell^\dagger\ket{b_\ell}\bra{b_\ell}U_\ell\big),\qquad \mathbb{E}[\hat{\rho}_\ell]=\rho\] such that for any observable \(O\) that is not supported on the main diagonal in the computational basis one can use \(\hat{o}_\ell(O)=\operatorname{Tr}[O\,\hat{\rho}_\ell]\) in an unbiased recovery. This is usually satisfactory, as there are other ways of estimating the main diagonal elements of \(\rho\). Hence, the framework also applies here.

Local-Clifford (random Pauli). Here \(\mathcal{U}=\mathrm{Cl}(2)^{\otimes n}\). Per round, sample independent single-qubit Cliffords \(U_{j,\ell}\) (equivalently, pick Pauli bases \(P_{j,\ell}\in\{X,Y,Z\}\)) and measure to get bits \(x_{j,\ell}\). Store the measurement record \[s_\ell=\big((P_{1,\ell},b_{1,\ell}),\ldots,(P_{n,\ell},b_{n,\ell})\big),\quad b_{j,\ell}=(-1)^{x_{j,\ell}}\in\{\pm1\}.\] The average channel factorizes as \(\mathcal{M}=D_{1/3}^{\otimes n}\) with inverse \(D_{1/3}^{-1}(A)=3A-\operatorname{Tr}(A)\,I_2\), hence the snapshot factorizes sitewise as \[\hat{\rho}_\ell=\bigotimes_{j=1}^n\hat{\eta}_{j,\ell},\quad \hat{\eta}_{j,\ell}=3\,\ket{\psi_{j,\ell}}\bra{\psi_{j,\ell}}-I_2,\] where \(\ket{\psi_{j,\ell}}:=U_{j,\ell}^\dagger\ket{x_{j,\ell}}\) an eigenvector of \(X\) or \(Y\) or \(Z\). To estimate \(M\) \(k\)-local observables up to error \(\epsilon\), it suffices to take \(L=\mathcal{O}\big(\frac{\log M}{\epsilon^2}\max_i 4^{k}\|O_i\|_{\infty}^2\big)\) rounds.

Global Clifford. Here \(\mathcal{U}=\mathrm{Cl}(2^n)\). Per round, sample \(U_\ell\in\mathrm{Cl}(2^n)\) uniformly at random and measure to get \(b_\ell\). Store the measurement record as \[s_\ell=(\mathsf{Stab}_{\ell},b_{\ell})\] where \(\mathsf{Stab}\) is the efficient classical representation of the global Clifford via the stabilizer formalism and \(b\in \{0,1\}^n\) the measurement outcome of that round.
The average channel is the global depolarizing map \[\mathcal{M}(\rho)=D_{1/(2^n+1)}(\rho),\qquad \mathcal{M}^{-1}(A)=(2^n+1)A-\operatorname{Tr}(A)I_{2^n},\] so the snapshot is \[\hat{\rho}_\ell=(2^n+1)\ket{\psi_\ell}\bra{\psi_\ell}-I_{2^n}.\] To estimate \(M\) linear observables, one needs \(L=\mathcal{O}\big(\frac{\log M}{\epsilon^2}\max_i\operatorname{Tr}(O_i^2)\big)\) rounds.

2.0.0.6 Mao–Yi–Zhu classical shadow framework.

Mao, Yi and Zhu [14] extend the HKP classical-shadow protocol to \(n\) qudits of odd prime local dimension \(d\). Let \(\mathbb{F}_d\) be the finite field with \(d\) elements and \(\omega=e^{2\pi i/d}\) a primitive \(d\)-th root of unity. Fix an ensemble \(\mathcal{E}\) of unitaries on \(n\) qudits. In each round: sample \(U\sim\mathcal{E}\), measure \(U\rho U^\dagger\) in the computational basis to get an outcome \(b_\ell\in\mathbb{F}_d^{\,n}\), and store a succinct classical description of \(U_\ell^\dagger\ket{b_\ell}\bra{b_\ell}U_\ell\). The average channel \[\mathcal{M}(\rho)=\mathbb{E}_{U\sim\mathcal{E}}\sum_{b}\braket{b|U\rho U^\dagger|b}\,U^\dagger\ket{b}\bra{b}U\] is invertible for tomographically complete \(\mathcal{E}\), so a single-shot snapshot is \[\hat{\rho}_\ell=\mathcal{M}^{-1}\big(U_\ell^\dagger\ket{b_\ell}\bra{b_\ell}U_\ell\big),\qquad \mathbb{E}[\hat{\rho}_\ell]=\rho.\] For any observable \(O\) we use \(\hat{o}_\ell(O):=\operatorname{Tr}[O\,\hat{\rho}_\ell]\). Partition the \(L\) rounds into \(K\) blocks and take the median of block-means (rounded to \(\chi\) bits) as before. Since \(\mathbb{E}[U_\ell^\dagger\ket{b_\ell}\bra{b_\ell}U_\ell]=\mathcal{M}(\rho)\), linearity gives \(\mathbb{E}[\hat{o}_\ell(O)]=\operatorname{Tr}(O\rho)\) (unbiased). Again \(L=O \left( \frac{\log(M)}{\epsilon^2} \max_{1 \leq i \leq M} \left\| O_i - \frac{\operatorname{Tr}(O_i)}{d^n} I \right\|_{\text{shadow}}^2 \right)\) samples, suffice to estimate \(M\) observables up to error \(\epsilon\).

Local-Clifford. Here \(\mathcal{E}=\mathrm{Cl}(d)^{\otimes n}\). Per round, sample independent single-qudit Cliffords \(U_{j,\ell}\) (equivalently, pick on each site one of the \(d+1\) stabilizer bases and measure there). Store the measurement record \(s_\ell=\big((\mu_{1,\ell},b_{1,\ell}),\ldots,(\mu_{n,\ell},b_{n,\ell})\big)\), where \(\mu_{j,\ell}\in\mathbb{F}_d\cup\{\infty\}\) labels the basis (\(\mu=\infty\): \(Z\)-eigenbasis; \(\mu=t\in\mathbb{F}_d\): eigenbasis of \(Z^tX\)) and \(b_{j,\ell}\in\mathbb{F}_d\) is the outcome label. The average channel factorizes as \(\mathcal{M}=D_{1/(d+1)}^{\otimes n}\) with inverse \(D_{1/(d+1)}^{-1}(A)=(d+1)A-\operatorname{Tr}(A)\,I_d\), hence the snapshot factorizes sitewise: \[\hat{\rho}_\ell=\bigotimes_{j=1}^n\hat{\eta}_{j,\ell},\qquad \hat{\eta}_{j,\ell}=(d+1)\,\ket{\phi_{\mu_{j,\ell},b_{j,\ell}}}\bra{\phi_{\mu_{j,\ell},b_{j,\ell}}}-I_d,\] where \(\ket{\phi_{\mu,a}}\) is the eigenvector in the chosen stabilizer basis. To estimate \(M\) \(k\)-local observables up to error \(\epsilon\), it suffices to take \(L=\mathcal{O}\Big(\frac{\log M}{\epsilon^2}\max_i d^{2k}\,\|O_i\|_{\infty}^2\Big)\).

Global Clifford. Here \(\mathcal{E}=\mathrm{Cl}(d^n)\). Per round, sample \(U_\ell\in\mathrm{Cl}(d^n)\) uniformly at random and measure to get \(b_\ell\in\mathbb{F}_d^{\,n}\). Store the measurement record: \(s_\ell=(\mathsf{Stab}_{\ell},b_{\ell})\), where \(\mathsf{Stab}\) is the efficient classical representation (via stabilizer formalism) of the global Clifford and \(b\) the \(d\)-ary outcome string. The average channel is the global depolarizing map \[\mathcal{M}(\rho)=D_{1/(d^n+1)}(\rho),\qquad \mathcal{M}^{-1}(A)=(d^n+1)A-\operatorname{Tr}(A)I_{d^n},\] so the snapshot is \(\hat{\rho}_\ell=(d^n+1)\ket{\psi_\ell}\bra{\psi_\ell}-I_{d^n}\). To estimate \(M\) linear observables, one needs \(L=\mathcal{O}\Big(\frac{\log M}{\epsilon^2}\max_i [(2d-3)\operatorname{Tr}(O_i^2)+2\|O_i\|_{\infty}^2]\Big)\) rounds.

3 Complexity of \(\mathsf{ObsCon}\)↩︎

The [def:CSV] is overloaded for the general hardness results we are about to present. For that reason we will now recast it in a more abstract form. Notice that we will come back to the full-fledged definition when we consider specific classical shadow protocols.

We will analyze the complexity of this problem in two regimes, distinguished by the number of observables \(m\).

3.1 Polynomially many observables (\(\mathsf{ObsCon}_{\mathrm{poly}}\))↩︎

Note here that the \(\mathsf{QMA}\)-hardness result need not go through the super-verifier machinery. We can directly reduce from the \(\mathsf{CLDM}\) problem which is known to be \(\mathsf{QMA}\) complete under Karp reductions [26]. We give this reduction in 7. The reason we use this machinery is because it will become helpful in the \(\mathrm{exp}\) regime that we analyze next.

3.2 Exponentially many observables (\(\mathsf{ObsCon}_{\mathrm{exp}}\))↩︎

We now move to analyze the case where the observables can be exponentially many, albeit we have succinct access to them. Here the super-verifier machinery we developed for the \(\mathrm{poly}\) regime will help us extract completeness results for \(\mathsf{ObsCon}_{\mathrm{exp}}\) immediately.

We next show that \(\mathsf{SuperQMA}_{\mathrm{exp}}\) coincides with the second level of a quantum-classical variant of the quantum polynomial hierarchy (\(\mathsf{QPH}\)). By \(\mathsf{QPH}\) we refer to the hierarchy \(\mathsf{Q\Sigma_i}\) of Ref.[20] (see 7). We call our variant \(\mathsf{qc\text{-}\Sigma_2}\) (see 10).

We first prove an amplification lemma showing that the constant-gap and inverse-polynomial-gap definitions of \(\mathsf{qc\text{-}\Sigma_2}\) coincide.

An important variant of \(\mathsf{ObsCon}_{\mathrm{exp}}\), because of its connection with a triply efficient classical shadow protocol for all the \(n\)-bit Pauli observables  [18], is when we have a constant gap parameter:

It is easy to see that even for a constant gap we still have \(\mathsf{SuperQMA}_{\mathrm{exp}}\)-completeness:

We conclude this section by showing an easy lower and upper bound for this new class.

4 Complexity of specific protocol classical shadows↩︎

The QMA-completeness of \(\mathsf{ObsCon}_{\mathrm{poly}}\), and so of \(\mathsf{CSV}_{\mathrm{poly}}\) (the more involved definition of the problem that will come in handy on this section ([def:CSV])), demonstrates the problem’s fundamental difficulty. We now further explore the complexity of this problem by casting it on specific, structured measurement protocols. We show that the hardness persists for two such protocols, namely the HKP with a local Clifford ensemble protocol, given in Ref.[5] and the MYZ which is its qudit generalization, given in Ref.[14]. Additionally we give an efficient algorithm result for the HKP, MYZ protocols with global Clifford ensemble.

4.1 HKP classical shadows↩︎

First we focus on the Huang, Kueng and Preskill protocol using local Clifford measurements [5] (for details on the protocol check 2.0.0.4). We will call the \(\mathsf{CSV}\) problem that is based on this protocol \(\mathsf{CSV}_{\text{HKP}}\).

We sometimes speak of the snapshot operator, \(\hat{\eta}\), associated to a stored string \((P,b)\); it is not stored explicitly but computed in recovery. The map \(s\rightarrow \hat{\eta}\) is a bijection onto the set of achievable snapshots, so storing strings or storing snapshots are equivalent representations, hence we freely use “strings” and “snapshots” interchangeably when no confusion can arise.

4.2 MYZ classical shadow↩︎

Our hardness result is not limited to qubit translated systems. A recent protocol by Mao, Yi, and Zhu [14] generalizes the local Clifford measurement framework to qudits of odd prime dimension \(d\). Their protocol uses the ensemble \(\mathcal{E} = \mathrm{Cl}(d)^{\otimes n}\), where \(\mathrm{Cl}(d)\) is the single-qudit Clifford group, leading to snapshots that are tensor products of single-qudit operators. Each such operator is derived from one of the \(d(d+1)\) single-qudit stabilizer states (for details see 2.0.0.6).

This protocol works for odd prime \(d\). Notice that we can always pad the local dimensions of our chain and add projector terms in our Hamiltonian and so we can trivially get a \(\mathsf{QMA}\)-completeness under Karp reductions result for a \(d\ge8\)-level \(1D\mhyphen\mathsf{CLDM}\) problem.

4.3 “Dequantizing” HKP, MYZ for global Clifford measurements↩︎

Recall now that classical shadows constructed using global Clifford operations allow for an efficient recovery of the expectation values of observables whose Frobenius norm \(\lVert O \rVert_{F} = \sqrt{\operatorname{Tr}[ O^{\dagger} O]}\) is bounded. Interestingly, in this setting, we can solve the validity problem in polynomial time if we have sampling and query access to the target observables. Briefly, this is done by invoking the bounded Frobenius norm semidefinite programming (SDP) dequantization result of [17] (see also [35], which previously handled the low-rank case).

We begin by defining the Global Clifford version of CSV.

It will be easier to work in the abstract definition which we denote \(\mathsf{ObsCon}_{\mathsf{F}}\) and define as:

Let us now properly define what a sampling and query access to the target observables mean.

With our sampling and query access definitions in hand, we can define:

We now recall the definition of the (SDP \(\varepsilon\)-feasibility)-problem [17], [35].

We now state the qudit analogue for the global \(n\)-qudit Clifford ensemble protocol (see 2.0.0.6).

5 Product state variants and connections to \(\mathsf{QMA(2)}\)↩︎

In this section we explore the variants of our problems stemming from the restriction to the product-state space and show completeness results for the corresponding product-state classes, i.e., \(\mathsf{\mathsf{SuperQMA}(2)}\), \(\mathsf{\mathsf{qc\text{-}\Sigma_2}(2)}\) (See 6 11 respectively) in the \(\mathrm{poly}\) and the \(\mathrm{exp}\) regime.

Let us start by analyzing the \(\mathrm{poly}\) case. First let us show the equivalence between \(\mathsf{\mathsf{SuperQMA}(2)}_{\mathrm{poly}}\) and \(\mathsf{QMA(2)}\):

Now in order to see what happens in the case of exponentially many checks we follow the same pattern as before and make use of the classes \(\mathsf{\mathsf{SuperQMA}(2)}_{\mathrm{exp}}\) and \(\mathsf{\mathsf{qc\text{-}\Sigma_2}(2)}\).

We start by showing the equivalence of the two classes.

6 Variants of \(\mathsf{CSV}\): Robustness and multiple shadow consistency↩︎

In this section we introduce two natural variants of \(\mathsf{CSV}\): a randomized (sampled-shadow) formulation and a multiple-shadow formulation. We prove that the sampled and explicit versions are equivalent under efficient randomized reductions, and that the multiple-shadow variant is computationally equivalent to the single-shadow \(\mathsf{CSV}\).

6.0.0.1 Randomized definition.

6.0.0.2 Multiple shadow consistency.

The following problem differs from the previous definitions as the input is multiple shadows, and the question is if these shadows can all stem from the same state \(\rho\). This is motivated by considering the case where we have (e.g.) two shadows, one of which captures local observable measurements, and the other which targets non-local measurements.

Though the above definition makes the importance of the \(\mathsf{MCSV}\) problem and its difference from \(\mathsf{CSV}\) more apparent, it would again be useful for our analysis to define an abstract syntactic variant problem in the same spirit as \(\mathsf{ObsCon}\):

Let us now quickly see why these problems are equivalent.

Acknowledgements↩︎

The authors thank Asad Raza for helpful discussions.

SG was supported by the DFG under grant numbers 563388236 (Priority Programme “Quantum Software, Algorithms and Systems – Concepts, Methods and Tools for the Quantum Software Stack” (SPP 2514)), and 450041824, the BMFTR within the funding program “Quantum Technologies - from Basic Research to Market” via project PhoQuant (grant number 13N16103), and the project “PhoQC” from the programme “Profilbildung 2020”, an initiative of the Ministry of Culture and Science of the State of North Rhine-Westphalia.

JE was supported by the BMFTR (QSolid, Hybrid++, QuSol, MUNIQC-Atoms, PasQuops), the Munich Quantum Valley (K-4 and K-8), the Quantum Flagship (PasQuans2, Millenion), QuantERA (HQCC), the Clusters of Excellence MATH+ and ML4Q, the DFG (CRC 183, SPP 2514), Berlin Quantum, and the ERC (DebuQC).

7 \(\mathsf{CLDM}\le \mathsf{ObsCon}_{\mathrm{poly}}\)↩︎

8 \(1D\mhyphen\mathsf{CLDM}\) on 8-level qudits is \(\mathsf{QMA}\)-complete↩︎

Here we specialize the [26] framework for simulatable history states and \(\mathsf{CLDM}\) hardness to the [27] 1D \(d=8\) nearest-neighbor architecture. Concretely, we instantiate BG’s simulatable verifier \(V_x^{(s)}\) and their snapshot and interval simulation lemmas inside HNN’s marker/work formalism and 2-local rule set, yielding a Karp reduction from any \(L\in\mathsf{QMA}\) to an \(1D\mhyphen\mathsf{CLDM}\) instance supported on single sites and edges of the HNN chain. Our proof follows BG’s Theorem 3.4 and Lemma 3.5 (simulation of history states) at the level of local work states, while swapping Kitaev’s unary-clock picture for HNN’s timetable on an 8-state line.

We begin by introducing some useful notation closely related to that of HNN: Each site \(j\in\{1,\dots,N\}\) from the 8-level qudit chain in Ref.[27] has a local Hilbert space: \[\mathcal{H}_j =\bigoplus_{k=1}^{4}\Big(\,\ket{M_k}\otimes \mathbb{C}\,\Big)\oplus\Big(\,\ket{Q}\otimes \mathbb{C}^{2}\,\Big)\oplus\Big(\,\ket{Q'}\otimes \mathbb{C}^{2}\,\Big).\] Here the marker symbols \(M_k\) carry no work qubit (work space \(\mathbb{C}\)), while \(Q\) and \(Q'\) each carry one work qubit (work space \(\mathbb{C}^{2}\)).

8.0.0.1 Time-\(t\) configuration and snapshot.

At step \(t\) the HNN timetable fixes a marker string \[m(t)=(m_1(t),\dots,m_N(t))\in\{M_1,M_2,M_3,M_4,Q,Q'\}^{N},\] and the computation has a work (data) state \(\ket{w(t)}\) on the tensor product of the single-qubit spaces at sites with \(m_j(t)\in\{Q,Q'\}\). The full snapshot (no history superposition) is \[\ket{\Psi_t} \;=\; \Big(\bigotimes_{j=1}^{N} \ket{m_j(t)}\Big)\;\otimes\;\ket{w(t)}.\] Notice that here the allowed marker strings are those specified in Ref.[27].

8.0.0.2 Local notation (sites and edges).

For a site \(i\) and an edge \(e=(i,i+1)\) define the marker kets and projectors \[\ket{c_t(i)} := \ket{m_i(t)}, \qquad \Pi^{\mathrm{mk}}_{t,i} := \ket{c_t(i)}\bra{c_t(i)},\] \[\ket{c_t(e)} := \ket{m_i(t)} \otimes \ket{m_{i+1}(t)}, \qquad \Pi^{\mathrm{mk}}_{t,e} := \ket{c_t(e)}\bra{c_t(e)}.\]

8.0.0.3 Local work space at time \(t\).

For \(S\subseteq\{1,\dots,N\}\) (we will use \(S=\{i\}\) or \(S=e=(i,i+1)\)), set \[\mathsf W_S(t)\;=\;\bigotimes_{j\in S} \begin{cases} \mathbb{C} & \text{if } m_j(t)\in\{M_1,M_2,M_3,M_4\},\\[2pt] \mathbb{C}^{2} & \text{if } m_j(t)\in\{Q,Q'\}, \end{cases} \qquad d_S(t)\;=\;\dim \mathsf W_S(t)\;=\;2^{\,n_S(t)},\] where \(n_S(t):=\big|\{\,j\in S:\;m_j(t)\in\{Q,Q'\}\,\}\big|\in\{0,1,2\}\).

8.0.0.4 Local snapshot reduced state.

The reduced snapshot on \(S\) is \[X(x,t,S):=\operatorname{Tr}_{\overline{S}}\big(\ket{\Psi_t}\bra{\Psi_t}\big) \;\in\; \big(\text{markers on }S\big)\;\otimes\;\mathsf L\big(\mathsf W_S(t)\big).\]

8.0.0.5 Edge cases (dimensions).

For an edge \(e=(i,i+1)\) at time \(t\): \[\dim \mathsf W_e(t)= \begin{cases} 1 & \text{if }(m_i(t),m_{i+1}(t))\in\{M_1,\dots,M_4\}\times\{M_1,\dots,M_4\}\quad(MM),\\[2pt] 2 & \text{if exactly one of }m_i(t),m_{i+1}(t)\in\{Q,Q'\}\quad(MQ\;\text{or}\;QM),\\[2pt] 4 & \text{if }m_i(t),m_{i+1}(t)\in\{Q,Q'\}\quad(QQ,QQ',Q'Q,Q'Q'). \end{cases}\]

8.0.0.6 Verification circuit.

Start with a QMA verifier \(V_x\), amplified so that completeness error and soundness error are negligible. Fix a constant BG22 simulator parameter \(s\ge 5\) large enough for all site/edge interval simulations below, and apply the BG22 simulatable compiler with parameter \(s\), obtaining the encoded verifier \(V_x^{(s)}\). Thus Lemma 4.8 of Ref. [26] gives a deterministic simulator for the reduced work state on any work-qubit set \(Y\) with \(|Y|\le 3s+2\).

Next we insert SWAP and identity gates as needed, in order to make the \(V_x^{(s)}\) circuit nearest-neighbor, and apply the HNN construction to obtain an equivalent computation \(\widetilde{V}_x^{(s)}\) on a line of \(N=\mathrm{poly}(|x|)\) eight-dimensional qudits. The legal HNN configurations carry the work qubits of the nearest-neighbor circuit \(V_x^{(s)}\) in the \(Q,Q'\)-type two-dimensional subspaces, and all marker patterns and work-qubit locations are computable from the HNN timetable. Therefore every site/edge HNN support, and every bounded HNN interval used below, refers to only constantly many underlying work qubits. Our choice of \(s\) ensures that this number is at most \(3s+2\), so the BG22 simulator applies.

We now prove that \(\widetilde{V}_x^{(s)}\) is simulatable and that the simulated marginals have zero combined energy with respect to the local terms of the HNN circuit-to-Hamiltonian construction.

We closely follow the exposition in Ref.[26], i.e., we first show simulatability and low energy for every snapshot of the computation on a good witness and for small intervals of the history state.

We next record the local energy contributions of the interval targets.

8.0.0.7 Initialization terms.

Write the initialization Hamiltonian as a sum of one-site marker-activated penalties, \[H_{\mathrm{in}}=\sum_j h^{\mathrm{in}}_j,\; \text{with}\;\; h^{\mathrm{in}}_1 = \big(\ket{Q}\bra{Q}\otimes\ket{1}\bra{1}\big)_1,\quad h^{\mathrm{in}}_j = \big(\ket{Q'}\bra{Q'}\otimes\ket{1}\bra{1}\big)_j .\] Let \(S_j=\{j\}\) be the support of \(h^{\mathrm{in}}_j\). We claim that \(\operatorname{Tr}\left(h^{\mathrm{in}}_j\,\widehat X(x,I,S_j)\right)=0\) for every \(j\) appearing in the above sum.

Indeed, the marker part of \(h^{\mathrm{in}}_j\) projects onto the corresponding initial marker sector. Hence, by marker orthogonality, all blocks of \(\widehat X(x,I,S_j)\) vanish against \(h^{\mathrm{in}}_j\) except possibly the block with the initial marker sector. On this surviving block, the initialization property of 22 gives that the simulated ancilla work qubit is \(\ket{0}\bra{0}\). Therefore the \(\ket{1}\bra{1}\) penalty has expectation zero. Thus \(\operatorname{Tr}\left(h^{\mathrm{in}}_j\,\widehat X(x,I,S_j)\right)=0\).

8.0.0.8 Output term.

Let \(S_{\mathrm{out}}=\{j_{\mathrm{out}}\}\) be the one-site support of the HNN output check, i.e. the final legal marker sector carrying the decoded output qubit. In our notation the output Hamiltonian has the form \[H_{\mathrm{out}}:= \big(\ket{Q}\bra{Q}\otimes\ket{0}\bra{0}\big)_{\,j_{\mathrm{out}}},\] where \(\ket{Q}\bra{Q}\) projects onto the final output-checking marker sector. This \(1\)-local, marker-activated projector penalizes output \(0\) only at the final layer on the designated active carrier; it is orthogonal (hence contributes \(0\)) on all other marker sectors. Let \(I\in\mathcal{I}(S_{\mathrm{out}})\). If \(I\) does not contain the final output-checking time, then the term is inactive by marker orthogonality. If \(I\) contains the final output-checking time, then by the output clause of 22 the simulated output block at \(j_{\mathrm{out}}\) is the accepting branch \(\ket{1}\bra{1}\). Hence the local penalty \(\ket{0}\bra{0}\) has expectation zero. Therefore \(\operatorname{Tr}\big(H_{\mathrm{out}}\widehat X(x,I,S_{\mathrm{out}})\big)=0\).

8.0.0.9 Penalty terms:

Let \(\Sigma=\{M_1,M_2,M_3,M_4,Q,Q'\}\). Partition the chain into blocks \(B_k=\{2n(k-1)+1,\dots,2nk\}\) and, for each edge \(e=(i,i+1)\), define its location type \(\mathrm{L}(e)\in\{A,B,C,D,E\}\) from the block index and the in block position (interior odd/even and the two block-end / between-block cases (see Table 5 in Ref.[27])). For each location \(L\in\{A,B,C,D,E\}\), let \(L_L\subseteq \Sigma^2\) be the set of legal adjacent marker pairs that occur at edges of type \(L\) in the timetable, and set \(F_L:=\Sigma^2\setminus L_L\), the set of illegal pairs. The penalty Hamiltonian is the edge-local projector \[H_{\mathrm{pen}} =\sum_eH_{\mathrm{pen},e}= \sum_{e=(i,i+1)}\;\;\sum_{(a,b)\in F_{\mathrm{L}(e)}} \bigl(\ket{a}\bra{a}\bigr)_i\;\otimes\;\bigl(\ket{b}\bra{b}\bigr)_{i+1}.\] (It acts only on marker registers; work qubits, if present, are ignored). Since every marker string \(m(r)\) in the HNN timetable is legal, every edge marker pair \(c_r(e)\) lies in the legal set \(L_{\mathrm L(e)}\). Thus, for every forbidden pair \((a,b)\in F_{\mathrm L(e)}\) and all \(r,r'\in I\), the projector \((\ket a\bra a)_i\otimes(\ket b\bra b)_{i+1}\) is orthogonal to the marker block \(\ket{c_r(e)}\bra{c_{r'}(e)}\). Hence \(\operatorname{Tr}\big(H_{\mathrm{pen},e}\widehat X(x,I,e)\big)=0\).

The HNN penalty Hamiltonian also contains the boundary marker penalties \(H_{\mathrm{left}}\) and \(H_{\mathrm{right}}\). These are one-site marker projectors which exclude symbols that cannot appear at the left and right boundaries of a legal HNN configuration. They are handled identically. Thus \[\operatorname{Tr}(H_{\mathrm{left}}\widehat X(x,I,\{1\}))=0, \quad \operatorname{Tr}(H_{\mathrm{right}}\widehat X(x,I,\{N\}))=0.\]

8.0.0.10 Propagation terms.

Fix a legal HNN transition \(t\to t+1\), and let \(e=(i,i+1)\) be the active edge whose local marker/work pattern changes in this transition. The actual HNN propagation Hamiltonian is written as a sum over rules and locations, rather than as a separate term for every pair \((e,t)\). The notation below isolates the legal contribution associated with the transition \(t\to t+1\). Any other local propagation-rule component either corresponds to a marker transition different from the one realized by this legal time step, or involves a locally illegal marker pattern detected by the marker-penalty terms. These terms have zero expectation against the target intervals by marker orthogonality.

Define the marker partial isometry on \(e\) by \[A_{e,t}:=\ket{c_{t+1}(e)}\bra{c_t(e)}.\] Thus \[A_{e,t}^{\dagger}A_{e,t}=\Pi^{\mathrm{mk}}_{t,e}, \quad A_{e,t}A_{e,t}^{\dagger}=\Pi^{\mathrm{mk}}_{t+1,e}.\] Let \(V_{e,t}:\mathsf W_e(t)\longrightarrow \mathsf W_e(t+1)\) be the work-space map induced by this legal HNN transition, under the canonical identification of the legal marker sectors with the underlying work qubits. Depending on the transition, \(V_{e,t}\) is the identity, the prescribed nearest-neighbor gate, a SWAP, or the corresponding move of the carried work registers. We regard \(V_{e,t}\) as an isometry between the relevant legal work spaces, so \(V_{e,t}^{\dagger}V_{e,t}=I_{\mathsf W_e(t)}\). For bookkeeping, write the legal off-diagonal transition piece as \[T_{e,t}:= A_{e,t}\otimes V_{e,t} + A_{e,t}^{\dagger}\otimes V_{e,t}^{\dagger}.\]

We also write the two legal diagonal marker checks associated with this transition as \[G^{\mathrm{pre}}_{e,t} := \Pi^{\mathrm{mk}}_{t,S^{\mathrm{pre}}_{e,t}}, \quad G^{\mathrm{post}}_{e,t} := \Pi^{\mathrm{mk}}_{t+1,S^{\mathrm{post}}_{e,t}},\] where \(S^{\mathrm{pre}}_{e,t},S^{\mathrm{post}}_{e,t} \in\bigl\{(i-1,i),(i,i+1),(i+1,i+2)\bigr\}\) are the HNN local supports on which the corresponding pre- and post-transition marker patterns are checked. Thus the legal grouped contribution associated with the transition \(t\to t+1\) has the form \[G^{\mathrm{pre}}_{e,t} + G^{\mathrm{post}}_{e,t} - T_{e,t}.\] The cancellation of this grouped contribution is not claimed at the level of a single interval. It will be obtained in 25 after averaging the interval targets with weights \(|I|/(T+1)\).

Let \[I_{\mathrm{pre}}\in\mathcal{I}(S^{\mathrm{pre}}_{e,t}), \quad I_{\mathrm{post}}\in\mathcal{I}(S^{\mathrm{post}}_{e,t}), \quad I_e\in\mathcal{I}(e).\] For the pre-projector, we have \[\operatorname{Tr}\left( G^{\mathrm{pre}}_{e,t} \widehat X(x,I_{\mathrm{pre}},S^{\mathrm{pre}}_{e,t}) \right) = \frac{1}{|I_{\mathrm{pre}}|} \sum_{r,r'\in I_{\mathrm{pre}}} \bra{c_{r'}(S^{\mathrm{pre}}_{e,t})} \Pi^{\mathrm{mk}}_{t,S^{\mathrm{pre}}_{e,t}} \ket{c_r(S^{\mathrm{pre}}_{e,t})} \operatorname{Tr}\left( \rho_{r,r'}(x,I_{\mathrm{pre}},S^{\mathrm{pre}}_{e,t}) \right).\] If \(t\in I_{\mathrm{pre}}\), the only nonzero marker contribution is \(r=r'=t\), and the corresponding diagonal work block has trace \(1\). If \(t\notin I_{\mathrm{pre}}\), every marker block is orthogonal to the projector. Hence \[\operatorname{Tr}\left( G^{\mathrm{pre}}_{e,t} \widehat X(x,I_{\mathrm{pre}},S^{\mathrm{pre}}_{e,t}) \right) = \begin{cases} \dfrac{1}{|I_{\mathrm{pre}}|}, & t\in I_{\mathrm{pre}},\\[2mm] 0, & t\notin I_{\mathrm{pre}}. \end{cases}\]

Similarly for the post-projector, \[\operatorname{Tr}\left( G^{\mathrm{post}}_{e,t} \widehat X(x,I_{\mathrm{post}},S^{\mathrm{post}}_{e,t}) \right) = \frac{1}{|I_{\mathrm{post}}|} \sum_{r,r'\in I_{\mathrm{post}}} \bra{c_{r'}(S^{\mathrm{post}}_{e,t})} \Pi^{\mathrm{mk}}_{t+1,S^{\mathrm{post}}_{e,t}} \ket{c_r(S^{\mathrm{post}}_{e,t})} \operatorname{Tr}\left( \rho_{r,r'}(x,I_{\mathrm{post}},S^{\mathrm{post}}_{e,t}) \right),\] and therefore \[\operatorname{Tr}\left( G^{\mathrm{post}}_{e,t} \widehat X(x,I_{\mathrm{post}},S^{\mathrm{post}}_{e,t}) \right) = \begin{cases} \dfrac{1}{|I_{\mathrm{post}}|}, & t+1\in I_{\mathrm{post}},\\[2mm] 0, & t+1\notin I_{\mathrm{post}}. \end{cases}\]

It remains to record the contribution of the legal off-diagonal piece \(T_{e,t}\) on the active edge \(e\). If \(\{t,t+1\}\subseteq I_e\), then by marker orthogonality only the \((t,t+1)\) and \((t+1,t)\) blocks contribute, and \[\operatorname{Tr}\left( T_{e,t}\widehat X(x,I_e,e) \right) = \frac{1}{|I_e|} \left( \operatorname{Tr}\left(V_{e,t}\rho_{t,t+1}(x,I_e,e)\right) + \operatorname{Tr}\left(V_{e,t}^{\dagger}\rho_{t+1,t}(x,I_e,e)\right) \right).\] By construction of the interval blocks through the known one-step evolution on \(e\), \[\rho_{t+1,t}(x,I_e,e) = V_{e,t}\rho_{t,t}(x,I_e,e), \qquad \rho_{t,t+1}(x,I_e,e) = \rho_{t,t}(x,I_e,e)V_{e,t}^{\dagger}.\] Using cyclicity of trace and \(V_{e,t}^{\dagger}V_{e,t}=I\), we get \[\operatorname{Tr}\left(V_{e,t}\rho_{t,t+1}(x,I_e,e)\right) = \operatorname{Tr}\left( V_{e,t}\rho_{t,t}(x,I_e,e)V_{e,t}^{\dagger} \right) = \operatorname{Tr}\left(\rho_{t,t}(x,I_e,e)\right) = 1,\] and \[\operatorname{Tr}\left(V_{e,t}^{\dagger}\rho_{t+1,t}(x,I_e,e)\right) = \operatorname{Tr}\left( V_{e,t}^{\dagger}V_{e,t}\rho_{t,t}(x,I_e,e) \right) =\operatorname{Tr}\left(\rho_{t,t}(x,I_e,e)\right)=1.\] Therefore \[\operatorname{Tr}\left( T_{e,t}\widehat X(x,I_e,e) \right)=\frac{2}{|I_e|} \quad \text{if } \{t,t+1\}\subseteq I_e.\] If \(\{t,t+1\}\cap I_e=\varnothing\), then the expectation is \(0\) by marker orthogonality. For the active edge \(e\), the mixed case \(|I_e\cap\{t,t+1\}|=1\) cannot occur: the legal transition \(t\to t+1\) changes only the markers on \(e\), so \(t\) and \(t+1\) have the same outside-\(e\) marker pattern and hence lie in the same maximal interval of \(\mathcal{I}(e)\).

We are now ready to prove that \(\widetilde{V}_x^{(s)}\) is simulatable and that the simulations have low-energy with respect to the local terms of the circuit-to-Hamiltonian construction:

8.0.0.11 Proof of 13

Since the containment is straightforward we only show hardness explicitly. Let \(A=(A_{\mathsf{yes}},A_{\mathsf{no}})\in\mathsf{QMA}\). Amplify the original verifier so that the completeness error is negligible, and apply the BG22/HNN construction from 25. On input \(x\), the reduction computes the local targets \(\widehat X(x,S)\) for all HNN supports \(S\) which are sites or nearest-neighbor edges. The reduction outputs the site and edge marginals \[\left\{ (\{i\},\widehat X(x,\{i\})) : 1\le i\le N \right\} \cup \left\{ (\{i,i+1\},\widehat X(x,\{i,i+1\})) : 1\le i<N \right\}.\]

Let \(H_{\mathrm{HNN}}(x)=\sum_{\ell=1}^{L} h_\ell\) be the full weighted HNN Hamiltonian for \(\widetilde{V}_x^{(s)}\), expanded into its one-site and nearest-neighbor two-site local pieces. For propagation, we keep the grouping convention from 24: the pre-projector, post-projector, and transition pieces belonging to the same HNN transition check are evaluated together. Define \(W:=\sum_{\ell=1}^{L}\|h_\ell\|_\infty\). Since the HNN Hamiltonian has polynomially many local terms with polynomially bounded weights, \(W=\mathrm{poly}(|x|)\). Let \(\Delta_{\mathrm{HNN}}\ge \frac{1}{\mathrm{poly}(|x|)}\) denote the HNN NO-instance lower bound on the ground energy.

Let \(\eta=\mathsf{negl}(|x|)\) be the local simulation error from 25. By amplification and by choosing the simulation precision sufficiently high, assume \(\eta\le \frac{\Delta_{\mathrm{HNN}}}{16W}\). Set the \(1D\mhyphen\mathsf{CLDM}\) thresholds to be \(\alpha:=2\eta, \; \beta:=\frac{\Delta_{\mathrm{HNN}}}{4W}\). Then \(\beta-\alpha\ge 1/\mathrm{poly}(|x|)\).

If \(x\in A_{\mathsf{yes}}\), then by 25 there is an HNN history state \(\Phi^{\mathrm{HNN}}\) such that for every relevant support \(S\), \(\left\|\operatorname{Tr}_{\overline{S}}\left(\Phi^{\mathrm{HNN}}\right) -\widehat X(x,S)\right\|_{\operatorname{Tr}}\le \eta\le \alpha\). Thus the produced local-density-matrix instance is a YES instance.

Now suppose \(x\in A_{\mathsf{no}}\). Assume for contradiction that there exists a global state \(\tau\) whose relevant local marginals are all \(\beta\)-close to the targets: \(\left\| \operatorname{Tr}_{\overline{S}}(\tau)-\widehat X(x,S) \right\|_{\operatorname{Tr}} <\beta\). By 25, the target marginals have zero combined HNN energy: the initialization, output, penalty, and boundary terms vanish termwise, and each legal propagation contribution vanishes in the grouped sense we discussed. Therefore, \[\begin{align} \operatorname{Tr}\left(H_{\mathrm{HNN}}(x)\tau\right) &=\sum_{\ell=1}^{L} \operatorname{Tr}\left( h_\ell\,\operatorname{Tr}_{\overline{S_\ell}}(\tau) \right)=\sum_{\ell=1}^{L}\operatorname{Tr}\left( h_\ell\bigl(\operatorname{Tr}_{\overline{S_\ell}}(\tau)-\widehat X(x,S_\ell)\bigr) \right)\\ &\le\sum_{\ell=1}^{L}\|h_\ell\|_\infty\left\|\operatorname{Tr}_{\overline{S_\ell}}(\tau)-\widehat X(x,S_\ell) \right\|_{\operatorname{Tr}}\\ &< W\beta =\frac{\Delta_{\mathrm{HNN}}}{4}< \Delta_{\mathrm{HNN}}. \end{align}\] Here \(S_\ell\) denotes the site or edge support of \(h_\ell\).

This contradicts the HNN soundness lower bound \(\lambda_{\min}(H_{\mathrm{HNN}}(x))\ge \Delta_{\mathrm{HNN}}\). Therefore, for every global state \(\tau\), at least one relevant local marginal violates its target by trace distance at least \(\beta\). Hence the produced \(1D\mhyphen\mathsf{CLDM}\) instance is a NO instance. This concludes our proof.

References↩︎

---

1. A Pauli string \(Q\) is an element of \(\set{I,X,Y,Z}^n\). We say \(Q\) is \(k\)-local if it contains at most \(k\) non-identity terms.↩︎

2. Since \(k\)-local Clifford measurements \(\mathcal{U}\) are easy to implement.↩︎

3. This is the succinct access assumption.↩︎

4. Formally, we can efficiently measure in the eigenbasis of \(O_i\), and return the eigenvalue corresponding to the measurement result.↩︎

5. We remark that although we gave a fully general formal definition of classical shadows ([def:classical-shadow]), most of our results are actually independent of the specific recovery algorithm \(A\) employed therein; thus, behind the scenes we often work with a simpler restatement of CSV, denoted Observable Consistency (\(\mathsf{ObsCon}\), 12). Hence, while we informally state our results in terms of CSV here, our formal statements are often in terms of \(\mathsf{ObsCon}\).↩︎

6. \(\mathsf{QMA(2)}\) is QMA, but where the proof is promised to be in tensor product [23].↩︎

7. One could alternatively use the 1D CONSISTENCY QMA-hardness result of Liu [25], but this would only yield hardness under Turing reductions, not many-one reductions.↩︎

8. A “super-verifier" is given by a classical polynomial-time randomized algorithm that given an input \(x\) outputs a description of a quantum circuit \(V\) and two numbers \(r,s\in[0,1].\)↩︎