Digital signatures with classical shadows on near-term quantum computers Pradeep Niroula, Minzhao Liu, Sivaprasad Omanakuttan, David Amaro, Shouvanik Chakrabarti, Soumik Ghosh, Zichang He, Yuwei Jin, Fatih Kaleoglu, Steven Kordonowy, Rohan Kumar, Michael A. Perlin, Akshay Seshadri, Matthew Steinberg, Joseph Sullivan, Jacob Watkins, Henry Yuen, Ruslan Shaydulin Abstract Quantum mechanics provides cryptographic primitives whose security is grounded in hardness assumptions independent of those underlying classical cryptography. However, existing proposals require low-noise quantum communication and long-lived quantum memory, capabilities which remain challenging to realize in practice. In this work, we introduce a quantum digital signature scheme that operates with only classical communication, using the classical shadows of states produced by random circuits as public keys. We provide theoretical and numerical evidence supporting the conjectured hardness of learning the private key (the circuit) from the public key (the shadow). A key technical ingredient enabling our scheme is an improved state-certification primitive that achieves higher noise tolerance and lower sample complexity than prior methods. We realize this certification by designing a high-rate error-detecting code tailored to our random-circuit ensemble and experimentally generating shadows for 32-qubit states using circuits with ≥ 80 \geq 80 logical ( ≥ 582 \geq 582 physical) two-qubit gates, attaining 0.90 ± 0.01 0.90\pm 0.01 fidelity. With increased number of measurement samples, our hardware‑demonstrated primitives realize a proof‑of‑principle quantum digital signature, demonstrating the near-term feasibility of our scheme. The study of quantum computing has traditionally focused on reducing computational resources such as time, memory, and energy, resulting in landmark quantum algorithms such as Shor’s algorithm for factorization Shor 1999 , Grover’s algorithm for unstructured search Grover 1996 , and methods for quantum Hamiltonian simulation Lloyd 1996 ; Childs 2010 ; Berry et al. 2015 ; Low and Chuang 2019 . Recently, a new dimension of quantum computational advantage has emerged, based on the development of cryptographic primitives whose security does not depend on the mathematical assumptions underpinning classical cryptography. Classical digital signatures and related primitives typically rely on one-way functions (OWFs), families of functions that are efficiently computable yet hard to invert on average. RSA instantiates such hardness through integer factorization, which fails against a fault-tolerant quantum computer. Learning-with-Errors forms the foundation of many post-quantum cryptographic (PQC) protocols and is intended to be secure against quantum adversaries, but is a subject of ongoing research. These pressures motivate security assumptions that do not depend on the existence of OWFs. Quantum mechanics offers independent routes to secure cryptographic schemes. While it has been long known that quantum communication can enable unconditionally-secure key distribution Bennett and Brassard 2014 , recently there have been significant advances in using quantum computation to propose cryptographic primitives that either rest on alternative assumptions than classical schemes or have no classical counterpart. Notably, some of these primitives are compatible with noisy devices Liu et al. 2025a ; Liu et al. 2025b , unlike many traditional algorithms that typically require fault tolerance, opening opportunities to strengthen communication, commerce, and national security by grounding security in more fundamental physical assumptions. Figure 1: Computational no-learning conjecture. a , Our shadow-based signature schemes uses assumptions independent of those traditionally used in classical cryptography. b , Our conjecture states that it is not feasible for an adversary to learn circuits from randomized measurements (shadows). One well-explored paradigm leverages the fact that quantum systems cannot be reliably observed without altering them Portmann and Renner 2022 . A more recent approach relies on the difficulty of learning quantum processes or states. In particular, it has been demonstrated that certain cryptographic primitives can be achieved through quantum communication, and could remain secure even in scenarios where OWFs do not exist Kretschmer 2021 ; Morimae and Yamakawa 2024 ; Fefferman et al. 2025 ; Morimae and Yamakawa 2022 ; Morimae and Yamakawa 2024 ; Khurana and Tomer 2024 . However, existing schemes rely on the ability to transmit quantum states between communicating parties, a task that remains challenging with current and near-term technologies. In this work, we present a digital signatures scheme that does not require OWFs or quantum communication. Digital signatures enable a recipient to verify the message’s true author using a signature generated by the sender. Our signature scheme modifies earlier proposals from Fefferman et al. 2025 to use classical shadows, instead of quantum states, as public keys, making the scheme friendly to near-term experiments. The security of our scheme is based on the conjectured computational hardness of learning quantum states from their classical shadows (“computational no-learning” conjecture). This conjecture is independent of the existence of one-way functions as illustrated in Fig. 1 . More precisely, this protocol implements the quantum cryptographic primitive known as “one-way puzzles”, distinct from OWFs. One-way puzzles have been used Khurana and Tomer 2024 to construct secure quantum multiparty computation Brakerski et al. 2023 and non-interactive quantum bit commitments Brakerski et al. 2023 ; Yan 2022 ; Hhan et al. 2023 , providing OWF-free building blocks for quantum cryptography. At present, no algorithm exists to efficiently learn a quantum circuit given its classical shadows. To provide evidence for the “computational no-learning” conjecture, we instead consider algorithms requiring a more powerful access model. First, we show that existing algorithms for learning shallow circuits fail in our setting Fefferman et al. 2025 ; Huang et al. 2024b ; Kim et al. 2024 ; Landau and Liu 2025 ; Fefferman et al. 2024 . Second, we derive a learning algorithm specialized to the class of all-to-all circuits considered in this work, extending the approach from Ref. Fefferman et al. 2024 , and show security against it. In addition to support for CNL, we also provide evidence that “spoofing” the protocol is exponentially harder than verifying the signature. Specifically, we prove the separation for two general classes of potential attacks: low-degree polynomial learning algorithms Chen et al. 2025 and variational circuit learning Anschuetz 2026 ; Anschuetz 2025 ; Anschuetz and Kiani 2022 . We demonstrate the near-term feasibility of the proposed scheme by generating shadows on a trapped-ion processor, successfully certifying the fidelity of the prepared quantum state. To enable the experiment, we introduce improved classical shadow schemes with better tolerance to experimental imperfections and a variant of Iceberg error-detecting code Steane 1996 ; Gottesman 1998a ; Self et al. 2024 tailored to our random circuits. Using multi‑block Iceberg encoding, we achieve beyond-break-even performance on circuits with 40 logical qubits and 680 logical gates (560 single‑qubit and 120 two‑qubit), where the encoded fidelity exceeds the fidelity without error detection, a result of independent interest. For hard-to-learn 32-qubit states, we achieve a fidelity of 0.90\pm 0.01 with 17,316 samples. We show that increasing the number of samples by 19.5 times is sufficient for a proof-of-principle demonstration of a signature scheme, demonstrating that our proposal can be realized in the near term. Digital signatures Figure 2: Digital signature schemes. a , The setup and the communication phases of classical digital signature. b , The setup and the communication phases of quantum digital signature. We show an example where the message communicated is a single bit \mathrm{msg}=0 . Blue arrows denote quantum communication, and black arrows represent classical communication. The left half of the panel shows a protocol requiring quantum communication and quantum memory. The right half of the panel shows our classical shadow protocol. Here, shadows of a quantum state correspond to classical descriptions of measurement outcomes on the state. Verification by the receiver only requires a classical computer but takes time exponential in the number of qubits. c,d,e,f, Classical shadow schemes. c , Single-qubit random Pauli basis protocol of Ref. Huang et al. 2024a , where a randomly chosen qubit is measured in a random Pauli basis and the rest are measured in the computational basis. d , An m -level shadow overlap protocol of Ref. Huang et al. 2024a , where m=3 qubits are randomly chosen and measured in random Pauli bases, and the rest are measured in the computational basis. We improve the multi-qubit protocol by modifying the post-processing step. e , An m -level protocol, where m=3 qubits are randomly chosen and an m -qubit random Clifford circuit is applied to them before all qubits are measured in the computational basis. This protocol is proposed by this work. f , A special case of the protocol in e where m is the same as the number of qubits. A global random Clifford circuit is applied to all qubits before measurement. This is the same as the classical shadow protocol based on random Clifford measurements for predicting quantum fidelities Huang et al. 2020 . In a classical digital signature scheme, a sender cryptographically “signs” a message such that a receiver may verify that the message truly originated from the sender and could not have been sent by an impersonator. To do this, the signer produces a key pair consisting of a public and a secret key. The public key \mathrm{pk} is broadcast while the secret key remains private to the sender. When the sender wishes to sign a message \mathrm{msg} , they use the secret key \mathrm{sk} to generate the signed message \mathrm{msg}_{\mathrm{s}} =S(\mathrm{sk},\mathrm{msg}) , where S denotes the signing function. The signed message \mathrm{msg}_{\mathrm{s}} is then sent to the receiver, who uses the sender’s public key and a verification function V(\mathrm{pk},\mathrm{msg}_{\mathrm{s}}) to check if the signed message \mathrm{msg}_{\mathrm{s}} is valid, i.e., corresponds to the sender. This protocol is illustrated in Fig. 2 a . The security of such a protocol is based on the fact that, without the knowledge of the secret key \mathrm{sk} , it is hard for an adversary to alter the contents of message \mathrm{msg}_{\mathrm{s}} and still pass the verification by the receiver. To enable this, it must be difficult to invert the signing function S and reconstruct the secret key \mathrm{sk} , even if an adversary were to intercept both \mathrm{msg} and \mathrm{msg}_{\mathrm{s}} . The non-invertibility of the signing function S and therefore the existence of OWFs are central to a secure classical signature scheme. Many quantum cryptographic protocols are based on quantum analogues of OWFs whose existence is, in a formal sense, independent of classical OWFs. As a notable example friendly to near-term implementation, Ref. Fefferman et al. 2025 constructs one-way state generators Morimae and Yamakawa 2022 using random quantum circuits, a class of circuits that have been extensively studied both theoretically and numerically. Specifically, it is easy to generate (on a quantum computer) a quantum state given the classical description of a randomly sampled quantum circuit as input, whereas it is hard in general to infer the circuit description given copies of the quantum state alone. This hinges on the so-called “computational no-learning” conjecture that forbids efficient learning of random quantum circuits from copies of the quantum state. Although proving the conjecture outright would require significant breakthroughs in computational complexity theory, there is extensive evidence in favor of the conjecture Fefferman et al. 2025 . Such a one-way state generator may also be leveraged to devise a quantum analog of a digital signature Fefferman et al. 2025 . In the quantum digital signature protocol proposed by Ref. Fefferman et al. 2025 , to sign a single bit, the sender begins with classical descriptions of two quantum circuits C_{0} and C_{1} , which serve as the secret key. For the public key, the sender distributes copies of the corresponding quantum states, \ket{C_0}=C_{0}\ket{0} and \ket{C_1}=C_{1}\ket{0} , for example via a trusted cloud repository. To transmit the bit b , the sender reveals the signed message (b,C_{b}) to the receiver. The receiver then downloads copies of the quantum state \ket{C_b} from the cloud and verifies that the state matches the circuit C_{b} —for instance, by checking that C_{b}^{\dagger}\ket{C_b} yields the all-zero state. This protocol is illustrated in the left half of Fig. 2 b . For an adversary to alter the signed message, i.e., flip the signed bit from b to its negation \neg b , it must output a message (\neg b,D) , without prior knowledge of C_{\neg b} (which is private to the sender), such that \ket{D}\approx\ket{C_{\neg b}} . The security of this protocol is based on the assumption that learning an equivalent circuit D\sim C_{\neg b} is hard, even if the adversary possesses copies of the public key \ket{C_{\neg b}} . However, while both the generation and verification steps are efficient with a quantum computer, the protocol relies on the coherent storage and distribution of quantum public keys—a requirement that far exceeds current technological capabilities. Establishing a cloud repository for quantum signatures also introduces new challenges. Although digital signatures protect against man-in-the-middle attacks on messages, they do not prevent an adversary from impersonating the cloud server itself. In classical digital signature schemes, this risk is mitigated through the use of digital certificates: users perform a one-time download of a trusted list that associates public keys with their legitimate owners. For quantum signatures, additional mechanisms must be developed to safeguard the integrity of public keys, or new trust assumptions must be introduced. Likewise, unclonability of quantum states limits the broadcasting and publishing of quantum public keys. It is therefore desirable for the public keys to be classical. We propose a protocol where the public keys are not quantum states but classical shadows. In particular, for secret keys (C_{0},C_{1}) , the sender publishes polynomial-length classical shadows \mathcal{S}(\ket{C_0}),\mathcal{S}(\ket{C_1}) as public keys. Here, \mathcal{S} denotes the quantum procedure that, across a polynomial number of samples, selects random local measurement bases on the qubits, measures the state accordingly, and for each sample records the chosen bases together with the corresponding measurement outcomes; the collection of these recorded basis choices and outcomes is the classical shadow. To communicate a bit b , the signer releases (b,C_{b}) as before. The receiver verifies the message by certifying that \mathcal{S}(C|0\rangle)\approx\mathcal{S}(C_{b}|0\rangle) using the shadow overlap protocol defined below, from which the receiver concludes that C|0\rangle\approx C_{b}|0\rangle Huang et al. 2024a ; Gupta et al. 2025 . Assuming the hardness of learning circuits from shadows, the verifier concludes that C indeed came from the sender’s private key. The protocol is illustrated in the right half of Fig. 2 b . To facilitate the analysis of our scheme, we introduce a general compiler that converts any shadow overlap protocol into a digital signature protocol (Supplementary Information (SI) Sec. I ). Evidence for Security For our shadow-based digital signatures protocol to be secure, it is crucial that learning the circuit C_{i} , given public classical shadows, is infeasible. In the protocol where the public keys are instead quantum states, the assumption of hardness is formalized by the computational no-learning (CNL) from states conjecture. This conjecture precludes the existence of efficient algorithms to learn certain ensembles of quantum circuits given copies of the output state Fefferman et al. 2025 . In a similar spirit, we introduce the “computational no-learning from shadows” conjecture, which asserts the hardness of learning quantum circuits given polynomial-length shadows. This new conjecture is a strictly weaker assumption (which is desirable) than the original CNL because, given polynomially many copies of an output state C\ket{0} , polynomial-length shadows can be obtained by simple measurements. As a result, the hardness of learning from shadows follows directly from the conjectured hardness of learning from states. Protocol security requires the existence of a family of random quantum circuits for which CNL holds. We provide evidence for this by showing in SI Sec. II that no existing algorithms Huang et al. 2024b ; Landau and Liu 2025 ; Fefferman et al. 2024 ; Kim et al. 2024 satisfy even two out of the three major requirements necessary to falsify CNL for the all-to-all circuits used in our experiment, namely (i) “proper learning” (i.e., recovering a circuit with the exact prescribed architecture), (ii) support for arbitrary circuit geometries, and (iii) reliance only on shadows and not on stronger forms of access to the circuit that are not reasonably available to an adversary. To provide further evidence for the security of our protocol, we design a learning algorithm that is proper yet effective for all-to-all shallow circuits (the type of circuits in our experiment), extending the protocol from Ref. Fefferman et al. 2024 (SI Sec. II.2 ). However, this algorithm cannot be directly extended to satisfy all three requirements since it relies on a stronger access model. Furthermore, we show that even under this stronger access model, we can design a family of circuits secure against our new attack. The central idea is that known approaches for learning circuits (including ours) proceed by inverting the gates one-by-one. Such local-inversion strategies are thwarted if the causal “lightcone” saturates the entire computational register, which we show can be achieved with shallow all-to-all circuits used in our experiment. Combined, this evidence indicates that major algorithmic breakthroughs are required to falsify CNL and compromise the security of our protocol. The arguments above provide theoretical and empirical evidence against the efficient learning of private circuits from public shadows. Since, for shadow-based signatures, the verification step – wherein a verifier validates a signature – is also expected to take exponential time, it would be desirable to choose circuit families such that verification can be done in a feasible wall-time while spoofing remains prohibitively expensive. We expect such a “gap” between verification time and learning or spoofing time to arise since circuit learning involves a search from the space of all possible circuits in the ensemble, which is as large as \exp(O(nd)) where d is the depth of the ensemble. In this work, we call a protocol secure if the time of verification T_{V} and the time of learning the circuits T_{L} satisfy T_{L}/T_{V}\geq\Omega(\exp(n)) , where n , the circuit size, serves as the security parameter. In other words, there is an exponential gap between the cost to cheat and the cost to verify. In SI Sec. III , we formalize this conjecture and provide evidence towards it. The first part of our evidence derives from the study of so-called “low-degree” learning algorithms Chen et al. 2025 , whose outputs can be expressed as low-degree polynomials over the input. In our case, the inputs to the adversary are the classical shadows that form the public key. Since the shadows are obtained by local measurements of quantum states, this setting is an instance of the low-degree algorithms for quantum state learning discussed in Ref. Chen et al. 2025 , where it was shown that this family encompasses all known state-of-the-art learning algorithms. In particular, it has been posited ( Hopkins 2018 , Hypothesis 2.1.5) that for most statistical learning problems, the class of algorithms of degree \leq d is no less powerful than the class of algorithms that take time O(\exp(d)) . Under this heuristic, if a learning algorithm requires a degree n^{1+\delta} for \delta>0 , it would be expected to take time T_{L}=O(\exp(n^{1+\delta})) , which would be enough for an exponential gap since verification takes time T_{V}=\Theta(2^{n}) . We show that we can indeed construct circuit ensembles that form “approximate designs” with respect to the Haar measure, such that the degree of a learning algorithm that takes as input non-adaptive local measurements on quantum states (such as the classical shadows that form the public key) has to be at least n^{1+\delta} for \delta>0 . Such a choice of circuit ensemble would give us the desired exponential gap between spoofing and learning. The runtime-degree correspondence discussed above, while applicable to a wide variety of algorithms, does not, however, capture all potential attacks. In particular, it may fail for settings where the best known algorithm is a greedy procedure such as gradient descent. Hence, the argument above cannot be applied to adaptive learning strategies that optimize a parameterized quantum circuit Anschuetz 2026 ; Anschuetz 2025 ; Anschuetz and Kiani 2022 . As the second part of our evidence, we show that our circuits exhibit exponentially-many poor local minima, making any variational training difficult (See SI Sec. III.2.2 ). In particular, such variational algorithms would have to compute the overlap with the target circuit exponentially many times, where each overlap computation incurs an exponential cost. Therefore, spoofing a circuit via variational training is also exponentially harder than verification. This exponential gap between learning and verification establishes the security of our protocol. Shadow overlap The digital signature scheme sketched out on the right side of Fig. 2 b requires certifying that a revealed circuit C prepares a state close to the honest state \ket{\psi_{\mathrm{hon}}}=C_{b}\ket{0} , that is, C\ket{0}\approx\ket{\psi_{\mathrm{hon}}} . Given classical shadows of a noisy laboratory state \sigma_{\mathrm{lab}} , we estimate the overlap with any target pure state \ket{\psi} specified by a circuit C_{\psi} . We build on classical shadow overlap certification while introducing modifications tailored to our setting. To fix notation, we briefly recall the Pauli–based baseline of Ref. Huang et al. 2024a (illustrated in Fig. 2 c,d ). That scheme performs T measurements. On each shot, it selects a subset \bm{k} of m qubits, measures those m qubits in random single–qubit Pauli bases \bm{P}\in\{X,Y,Z\}^{m} , measures the remaining n-m qubits in the Z basis, and records the bitstring \bm{z}\in\{0,1\}^{n} . This produces the shadow dataset \bigl\{\,\bm{k}^{(i)},\;\bm{P}^{(i)}\in\{X,Y,Z\}^{m},\;\bm{z}^{(i)}\,\bigr\}_{i\in[T]}. (1) Using these shadows together with a polynomial number of target amplitudes \psi(x)\equiv\langle x|C_{\psi}|0\rangle , one computes a score \omega_{i} for each i . The expectation \mathbb{E}[\omega] is the shadow overlap, which controls the fidelity between \ket{\psi} and \sigma_{\mathrm{lab}} Huang et al. 2024a . Before introducing our modifications, we summarize the verification complexity and the role of the “relaxation time”. In this framework, two standard implications connect shadow overlap and fidelity for a fixed hypothesis state \ket{\psi} : if \mathbb{E}[\omega]\geq 1-\varepsilon then \bra{\psi}\sigma_{\mathrm{lab}}\ket{\psi}\geq 1-\tau\varepsilon , and if \bra{\psi}\sigma_{\mathrm{lab}}\ket{\psi}\geq 1-\varepsilon then \mathbb{E}[\omega]\geq 1-\varepsilon . Here \tau\geq 1 is the relaxation time of a Markov chain induced by the chosen measurement rule and operator used in post–processing, and depends on the protocol and the circuit ensemble. Computing the overlap statistic requires a polynomial number of amplitudes of C_{\psi}\ket{0} , so exact verification scales as O(2^{n}) up to polynomial factors in T and n . Large \tau and large estimator variance increase the number of measurements, T , needed to avoid false accepts and false rejects; see Fig. 3 . Motivated by these considerations, our protocol adopts the same overall structure but modifies both the measurement rule and the estimator to reduce \tau and the variance. For shadow generation, on each shot we apply a random m -qubit Clifford circuit to a uniformly random subset of m qubits, then measure all qubits in the computational basis (Fig. 2 e ). This yields shadows \bigl\{\,\bm{k}^{(i)},\;U^{(i)}\in\mathrm{Clifford}[m],\;\bm{z}^{(i)}\,\bigr\}_{i\in[T]}. (2) In post–processing, we use a refined overlap estimator that achieves the minimal possible relaxation time \tau=1 in the limit m=n . Together, these choices define a tunable family of shadow–based state–certification protocols that interpolate between two well–studied extremes: global random Clifford measurements, which are most sample efficient but require global control (Fig. 2 f ; Ref. Huang et al. 2020 ), and single–qubit random Pauli measurements, which are less sample efficient but only require local control (Fig. 2 c,d ; Ref. Huang et al. 2024a ). Details appear in SI Sec. IV . We now state the honest and adversarial overlap bounds used in verification, focusing on the depolarizing model and deferring general noise to SI Sec. I.1 . Let \phi_{\mathrm{hon}}\equiv\langle\psi_{\mathrm{hon}}|\sigma_{\mathrm{lab}}|\psi_{\mathrm{hon}}\rangle=1-\varepsilon_{\mathrm{hon}} denote the honest signer’s fidelity. By the overlap–fidelity implication, this gives the honest lower bound E [ ω _hon] ≥1 - ε _hon. For an adversary, the computational no–learning assumption limits the state overlap with the honest target to |\langle\psi_{\mathrm{adv}}|\psi_{\mathrm{hon}}\rangle|^{2}\leq 1-\varepsilon_{\mathrm{CNL}} . Under depolarizing noise, Lemma 1 (SI Sec. I.1 ) implies an upper bound on the adversarial fidelity to the laboratory state, ϕ _adv ≡⟨ ψ _adv— σ _lab— ψ _adv⟩≤1 - ( ε _CNL - ε _hon ) + ε _hon 2^-n. Applying the contrapositive of the overlap–fidelity implication then yields an upper bound on the adversarial overlap, E [ ω _adv] ≤1 - ε CNL - ε hon τ + ε hon 2 n τ ≈1 - ε CNL - ε hon τ , where \tau is the relaxation time associated with the chosen hypothesis and protocol. The 2^{-n} term is negligible at the system sizes considered here. Together, these bounds imply a gap between the honest and adversarial overlap distributions whenever \varepsilon_{\mathrm{hon}} is small and \varepsilon_{\mathrm{CNL}} is bounded away from zero. Reducing \tau and the estimator variance, as achieved by our modified measurement rule and estimator, enlarges this gap at practical T , lowering the sample complexity and increasing robustness to experimental noise in signature verification. Figure 3: Discriminating between the honest signer and the adversary . To improve the discriminating power of the shadow overlap, we devise an improved protocol that reduces the relaxation time \tau to shift the adversary distribution to the left and reduces the variance of the score. Additionally, we use quantum error detection to increase the fidelity to shift the honest distribution to the right. Experimental Demonstration To demonstrate near-term feasibility, we implement shadow-based state certification on a trapped-ion processor using the random Clifford shadow protocol at level m=4 (Protocol IV.3 in SI Sec. IV ). Certification must operate in a regime where the honest and adversarial shadow overlaps are separated, i.e. \mathbb{E}[\omega_{\mathrm{adv}}]<\mathbb{E}[\omega_{\mathrm{hon}}] , which implies an upper bound on tolerable experimental infidelity in public-key generation \varepsilon_{\mathrm{hon}}<\varepsilon_{\mathrm{CNL}}/(\tau+1) . We construct a circuit family with low depth that yields causal light cones obstructing learning algorithms based on gate-by-gate local inversion described in SI Sec. II . For our circuits at n=32 and m=4 , the relaxation time is \tau\approx 8 (SI Sec. IV.1 ). Assuming that learning a circuit with overlap at least 1-\varepsilon_{\mathrm{CNL}}=0.01 is hard, one needs an experimental fidelity \phi_{\mathrm{hon}}=1-\varepsilon_{\mathrm{hon}}\geq 0.89 . Table 1 shows that this fidelity is out of reach without encoding. To overcome this hardware limitation, we introduce two constructions tailored to our random-circuit ensemble and hardware constraints. The first is a multi-block Iceberg encoding that partitions the k logical qubits into several independent Iceberg blocks, each with its own stabilizer checks. Blocks are coupled only through transversal CZ gates, which limits the spread of errors between blocks (Methods and Fig. 4 ). The introduction of multiple blocks increases the number and reduces the weight of syndrome measurements, thereby reducing idling overhead during high-weight checks. The second is a gauge-fixing scheme for the Iceberg code that produces additional ancilla qubits, allowing parallel execution of single-qubit logical layers and introducing additional low-weight checks that are less sensitive to errors (SI Sec. V ). As shown in Table 1 , the use of multiple code blocks and gauge fixing enables beyond-break-even performance with only a modest sampling overhead. We experimentally certify a four-block-encoded 32-qubit hard-to-learn random circuit with logical two-qubit gate depth 5 (Fig. 4 ). Using Protocol IV.3 at m=4 , we apply random four-qubit Clifford circuits after decoding and before measurement. The total physical two-qubit gate count per shot is 582. A total of 44,560 shots are executed. After discarding trials with detected errors, 17,316 classical shadows are retained, yielding an shadow overlap of 0.91 and \phi_{\mathrm{hon}}=0.90\pm 0.01 (see SI Sec. V.3 ). This fidelity is lower than the fidelities estimated in Table 1 due to the use of random Clifford circuits which require additional gates compared to the random Paulis in Table 1 . Under \varepsilon_{\mathrm{hon}}<0.11 and 1-\varepsilon_{\mathrm{CNL}}\leq 0.01 , the expected adversary shadow overlap is \mathbb{E}[\omega_{\mathrm{adv}}]\leq 0.89 . The protocol parameters are such that, in the malicious case, no adversarial circuit can pass our protocol with probability higher than \delta=0.15 (SI Theorem 13 ). On the other hand, our experimentally observed scores \{\omega_{\mathrm{exp},i}\}_{i\in[T]} give shadow overlap \mathbb{E}[\omega_{\mathrm{exp}}]=0.91 . The data passes the protocol and is consistent with the honest case. Type Logical qubits Blocks Shots p 2-Q depth Fidelity \phi_{\mathrm{hon}} Physical 32 N/A 500 1 5 0.82(7) Iceberg 32 2 2,000 0.37(1) 128 0.79(6) Iceberg 32 4 2,000 0.39(1) 75 0.98(5) Iceberg+ 32 2 2,000 0.38(1) 88 0.94(5) Physical 40 N/A 700 1 6 0.82(6) Iceberg 40 2 3,000 0.204(7) 177 0.63(7) Iceberg 40 4 3,000 0.226(8) 98 0.94(6) Iceberg+ 40 2 3,000 0.162(7) 108 0.75(7) Table 1: Estimated fidelity for random circuits. The number of logical qubits is 32 and 40, and the logical two-qubit gate depth is 5 and 6 respectively. All data is taken from Quantinuum H2 trapped-ion processor with 56 physical qubits Moses et al. 2023 . “Physical” refers to running the circuit without encoding into the Iceberg code. “Iceberg” means that the circuit is encoded into a specified number of Iceberg code blocks. “Iceberg+” indicates that the circuit is encoded into augmented Iceberg code blocks, in which l=2 logical qubits (per code block) are reserved for parallelizing logical operations. p is the probability of acceptance after post-selection based on error detection. 2-Q depth is the physical two-qubit gate depth required to implement the circuit. Fidelity \phi_{\mathrm{hon}} is estimated from shadow overlap as described in SI Sec. V.3 . The reduction in physical two-qubit depth for Iceberg+ over Iceberg (with two code blocks) improves the estimated fidelity, as memory and idling errors are significant in current hardware. Uncertainties show standard error. Figure 4: Quantum circuits used in the experiment. a , The circuit without encoding. The circuit has four blocks. Blue gates are Hadamard gates, and purple gates are parameterized single-qubit gates Z^{p}X^{1/2} for p\in\{-1,-\frac{3}{4},\dots,\frac{3}{4}\} . We interleave layers of random pairs of inner-block CZ gates and random pairs of transversal intra-block CZ gates. b , One layer of logical single-qubit gates. Each logical single-qubit R_{Z} gate is implemented using a physical parameterized R_{ZZ} gate (purple gates with circular ends), and each logical R_{X} gate is implemented using a physical R_{XX} gate (orange gates with square ends). c , The circuit with Iceberg code encoding. The encoder prepares the logical |{+}\rangle state with post selection. All logical two-qubit gates are implemented by physical two-qubit gates. The decoder transforms the encoded state into the physical state with post selection. Then, tomography on the decoded physical state is performed by collecting random Clifford classical shadows. The random Clifford circuit is applied to a random set of physical four qubits after decoding. Simply running the certification experiment for longer would allow our scheme to achieve nontrivial security for the digital signature. Corollary 3 (SI Sec. IV.3 ) shows that the sample complexity is proportional to \ln(1/\delta) . Therefore, decreasing \delta from {\color[rgb]{0,0,0}0.15} to 10^{-15} requires \ln(1/10^{-15})/\ln(1/\textcolor{black}{0.15})=19.5 times more samples, resulting in a total of 340 k samples. Consider a computationally bounded adversary that tries 10 billion adversary circuits and checks if each one passes the protocol. The probability that it spoofs the signature protocol is only 10^{-5} . To do this, it computes 10^{10}\times 340{,}000=3.4\times 10^{15} values of \omega . The computation of each \omega takes about 0.3 seconds on an AMD EPYC 7R13 processor using our implementation. Using the same implementation, an adversary that is one million times more powerful still requires 32 years. While future improvements to learning algorithms may make be possible to learn our 32-qubit circuit, a modest increase in circuit size would restore the security of the scheme. Outlook The protocol described above only signs a single bit. In the future, it would be interesting to demonstrate multi-bit quantum digital signatures. In SI Sec. I , we present a k -bit message protocol with a favorable verification cost. Instead of verifying every bit and paying a total verification cost of k\cdot O(2^{n}) , we can pay a cost independent of k by verifying a constant number of bits chosen randomly. If all verified bits pass, then it is guaranteed that most bits are not altered by the adversary. If the message is encoded in an error-correcting code, the message can be recovered even if some bits are altered. Using an error-correcting code for multi-bit message digital signatures gives a signer complexity of k\cdot\mathrm{poly}(n) , a receiver complexity of O(1)\cdot O(2^{n}) , and a spoofing complexity of O(k)\cdot\Omega(2^{n}) . Even for long messages with large k , signing remains feasible since each signature can be produced efficiently. In turn, verification is realistic via spot checks on a subset of signatures, while spoofing remains computationally prohibitive. The equivalence between our protocol, which realizes one-time signatures, and one-way puzzles allows one to construct many other quantum cryptographic primitives without assuming the existence of OWFs (see SI Sec. VI ). Our work is a step towards realizing this broad class of primitives, opening up new avenues of quantum advantage realizable with near-term quantum computers. Methods Figure 5: Multi-block random circuit and encoding in Iceberg code. a , Logical random circuit is composed of blocks of qubits, with each block encoded in a separate Iceberg code block. b , Single-qubit logical gates in Iceberg error-detection code: logical R_{X} and R_{Z} rotations are implemented with a physical two-qubit interaction involving the “top” qubit and the “bottom” qubit respectively. c , Promoting select logical operators to stabilizers (“gauge fixing”) enables multiple logical single-qubit rotations to be performed in parallel. The qubits gauge-fixed to eigenstates of logical x and logical z are denoted g_{x} and g_{z} respectively. .1 Multi-Block Iceberg Encoding of Random Circuits The success of quantum state certification and the overall digital signature protocol relies crucially on achieving high fidelity. To improve fidelity, we use a multi-block random circuit whose structure is chosen to improve the performance of the Iceberg error-detecting code. The Iceberg code Steane 1996b ; Gottesman 1998b ; Self et al. 2024 is a \llbracket k+2,k,2\rrbracket error-detecting code that encodes k logical qubits into k+2 physical qubits. It is a stabilizer code with two weight- (k+2) stabilizers ( Z and X ) and is capable of detecting any single-qubit error. Trapped-ion devices like the Quantinuum H2 race-track processor Moses et al. 2023 used in this work are particularly suitable for this code due to the ability to implement high-weight stabilizers using atom movement. The structure of random circuit used in this work is summarized in Fig. 5 a . The circuit consists of repeating sequence of four layers: (i) single-qubit Clifford gates sampled independently and uniformly for each qubit, (ii) two-qubit controlled-Z (CZ) gates on random pairs of qubits within block, (iii) another layer of single-qubit gates, and (iv) two-qubit inter-block CZ gates. We remark that similar structure has been used in Ref. Bluvstein et al. 2024 for IQP circuits encoded in the 3D color code. When encoding the random circuit in Iceberg code, each “block” of qubits is encoded within a separate Iceberg code block, with inter-block CZ gates applied transversally. We measure all stabilizers at the end of the circuit and post-select on the outcome. .2 Parallelization in Iceberg Code by Gauge Fixing The random circuit we use has more single-qubit than two-qubit gates. This creates a challenge for the Iceberg code since each logical single-qubit gate is implemented with a physical two-qubit gate involving either “top” (for R_{X} rotation) or “bottom” ( R_{Z} ) ancilla qubit (see Fig. 5 b ). Additionally, the high weight of the Iceberg code stabilizers leads to memory error accumulation during atom movement necessary to read out the stabilizer He et al. 202 . We overcome both of these challenges using a stabilizer extension procedure that we call gauge fixing , in which a selected subset of logical operators (such as \overline{Z}_{j} or \overline{X}_{j} ) is added to the stabilizer group. This projects the code space onto the joint +1 eigenspace of the chosen operators, thereby restricting the logical subspace and increasing the number of physical qubits to encode a fixed number of logical qubits. The resulting code has parameters \llbracket k+\ell+2,k,2\rrbracket , where k is the number of computational logical qubits and \ell is the number of logical operators promoted to stabilizers. See the SI Sec. V for a full mathematical treatment and further discussion. Promoting additional logical operators to stabilizers introduces “proxy” top or bottom qubits, allowing multiple logical rotations to be performed in parallel as shown in Fig. 5 c . Furthermore, the stabilizer checks corresponding to the introduced small stabilizers can be executed with much smaller atom movement overhead as compared to the stabilizers of the standard Iceberg code. For l=2 , we have four stabilizers per block and each of them are measured during each readout. Only runs in which all the stabilizer outcomes are +1 are retained for post processing. Author Contributions P.N., S.C., R.S. conceptualized the project. P.N., S.C. devised the single-bit digital signature protocol from shadow overlap protocols and conducted exploratory analysis. M.L. devised the improved shadow overlap protocol and the multi-bit signature protocol, proved the security of single-bit and multi-bit protocols, and provided low-degree polynomial hardness evidence. J.S., J.W. investigated classical error detection codes for multi-bit signatures. S.O., Y.J., J.S., M.A.P., M.S., Z.H., R.K. devised the quantum error detection protocol and compatible circuit ansatz. D.A. devised the parallelization technique shown in Figure 5 c . S.O., Y.J., P.N. conducted the experiment. P.N. and A.S. analyzed the data. P.N., S.C., S.K. analyzed the variational learning adversary. J.W. and S.K. developed and analyzed the gate-by-gate proper learning adversary. F.K. established the connection to one-way puzzles and other quantum cryptographic primitives. All authors contributed to the writing of the manuscript and shaping of the project. Competing Interests The authors declare no competing interests. Additional Information Supplementary Information is available for this paper. Disclaimer This paper was prepared for informational purposes with contributions from the Global Technology Applied Research center of JPMorgan Chase & Co. This paper is not a product of the Research Department of JPMorgan Chase & Co. or its affiliates. Neither JPMorgan Chase & Co. nor any of its affiliates makes any explicit or implied representation or warranty and none of them accept any liability in connection with this paper, including, without limitation, with respect to the completeness, accuracy, or reliability of the information contained herein and the potential legal, compliance, tax, or accounting effects thereof. This document is not intended as investment research or investment advice, or as a recommendation, offer, or solicitation for the purchase or sale of any security, financial instrument, financial product or service, or to be used in any way for evaluating the merits of participating in any transaction. Supplementary Material for: Digital signatures with classical shadows on near-term quantum computers I Digital signature from shadow overlap protocols A theoretical contribution of our work is a general compiler that converts any shadow overlap protocol into a digital signature protocol. A key ingredient of our digital signature protocol is the ability to verify if a given classical shadow corresponds to a quantum circuit. Shadow overlap protocols are used to certify that classical shadows of a “laboratory” quantum state (i.e., published shadows) is indeed close to a given hypothesis state (i.e., state generated by the quantum circuit), where closeness is defined with respect to state fidelity. To start, we define general shadow overlap protocols. Definition 1 (Shadow Overlap Protocol) . Let \ket{\psi} be a fixed hypothesis state. A non-adaptive, shadow overlap quantum state fidelity certification protocol (“shadow overlap protocol”) consists of a data collection phase and a certification phase. In the data collection phase, T copies of a laboratory state \rho are manipulated and measured to produce T independent shadows \{o_{i}\}_{i\in[T]} . In the certification phase, using the shadows \{o_{i}\}_{i\in[T]} and any known information about the hypothesis state, with probability at least 1-\delta , the protocol will correctly output Failed if the fidelity between the hypothesis state and the laboratory state is low, i.e. \langle\psi|\rho|\psi\rangle<1-\varepsilon , and will correctly output Certified if the fidelity is high, i.e. \langle\psi|\rho|\psi\rangle\geq 1-{\varepsilon}/{2\tau} , where \tau is a function that depends on |\psi\rangle . We call this a (T,\delta,\varepsilon,\tau(\cdot)) protocol, emphasizing that \tau(\cdot) is a function. The parameter \tau is the relaxation time for a certain Markov chain generated by the distribution of local measurements of the state \ket{\psi} . Its functional relationship with the hypothesis state \ket{\psi} is a key factor in the performance of the shadow-based certification, and hence we highlight this dependence in our parametrization. Protocol IV.1 and Protocol IV.2 in this work, as well as Protocol 2 in Huang et al. 2024a , are examples of shadow overlap protocols. In this work, each shadow o_{i} is a tuple of a) a uniformly random subset of l\subset[n] , b) a random Clifford operation acting on the qubits in l , and c) the computational basis measurement outcome of all n qubits. Now, we formally define the digital signature protocol. {protocol_framed} [Digital Signature of a single bit via Shadow Overlap] • \mathsf{SKGen} : Sample descriptions of quantum circuits C^{b} uniformly at random from some ensemble \mathcal{C} , for both b=0,1 . Set \mathsf{sk}=\left(C^{b}\right)_{b\in\{0,1\}} • \mathsf{PKGen} : Perform the data collection phase of some (T,\delta,\varepsilon,\tau(\cdot)) non-adaptive shadow overlap quantum state fidelity certification protocol on the state \rho obtained by applying C^{b} to the all zero state for b\in\{0,1\} . The public key is \mathsf{pk}=\{o_{i}^{b}\}_{i\in[T],b\in\{0,1\}} . • \mathsf{Sign} : To sign bit b , output the bit and the classical description of the circuit m_{\mathrm{s}}=(b,C^{b}) as the signed message. • \mathsf{Ver} : Use the certification phase of the non-adaptive shadow overlap-type quantum state fidelity certification protocol. Specifically, use \{o_{i}\}_{i\in[T]} that corresponds to the signed bit b in \mathsf{pk} and certify the state C^{b}|0\rangle . Output the same output as the fidelity certification protocol. The security of the protocol relies on the assumption that it is hard for an adversary to learn a circuit C^{\prime} in the circuit ensemble \mathcal{C} given classical shadows \{o^{b}_{i}\}_{i\in[T]} generated using a secret key C^{b} . The shadow overlap protocol certifies that the unknown quantum state producing the shadows \{o^{b}_{i}\}_{i\in[T]} is close to the state generated by the circuit revealed by the signer in the \mathsf{Sign} phase of the protocol. Therefore, for an adversary to pass the protocol, it must learn the circuit C^{b} (or more precisely, must learn a circuit \tilde{C} such that \tilde{C}\ket{0}\equiv C^{b}\ket{0} . If the circuit ensemble is such that learning C^{b} (or equivalent circuits) is difficult from the shadows, the protocol is hard to spoof if the adversary does not know C^{b} a priori. The above digital signature protocol certifies a single bit. Longer messages can be certified, in principle, by iterating the protocol over the entire message. This, however, is highly inefficient. Single-bit certification with shadows is already exponential time (as it involves calculation of quantum state amplitudes), and thus one would like to minimize the number of required calls to this protocol. Thankfully, we can substantially reduce the number of certifications using classical error detection. Take some block code with parameters [M,k,d] , where a logical message of k bits is encoded into an M -bit codespace, and the minimum Hamming distance between valid code words is at least d . Certification will now only take place on some subset of the bits. Below we give the updated protocol in Protocol I for a k -bit logical message. {protocol_framed} [Signature for a k -bit message] Input: • An [M,k,d] error detection code. • \mathsf{Enc}:\{0,1\}^{k}\rightarrow\{0,1\}^{M} : a function that encodes a k -bit message into M bits. • \mathsf{Chk}:\{0,1\}^{M}\rightarrow\{0,1\} : a boolean function that outputs 1 if the input is not in the code space (i.e. an indicator function). • \mathsf{Dec}:\{0,1\}^{M}\rightarrow\{0,1\}^{k} : a function that decodes the M -bit encoded message into the original k -bit message. • V : an integer parameter that determines how many circuits and classical shadows to check. Procedure: • \mathsf{SKGen} : Sample descriptions of quantum circuits C^{b,j} uniformly at random from some ensemble \mathcal{C} , for b=0,1 and j\in[M] . Set \mathsf{sk}=\left(C^{b,j}\right)_{{b\in\{0,1\}},j\in[M]} • \mathsf{PKGen} : Perform the data collection phase of some (T,\delta,\varepsilon,\tau(\cdot)) non-adaptive shadow overlap-type quantum state fidelity certification protocol on the state \rho obtained by applying C^{b,j} to the all zero state subject to device infidelity for b\in\{0,1\} and j\in[M] . The public key is \mathsf{pk}=\{o_{i}^{b,j}\}_{i\in[T],b\in\{0,1\},j\in[M]} . • \mathsf{Sign} : To sign the message m=(m^{1},\dots,m^{k})\in\{0,1\}^{k} , first encode it into encoded message m_{\mathrm{e}}=(m_{\mathrm{e}}^{1},\dots,m_{\mathrm{e}}^{M})=\mathsf{Enc}(m) . Then, output m_{\mathrm{s}}=\left(m_{\mathrm{e}},\{C^{m_{\mathrm{e}}^{j},j}\}_{j\in[M]}\right) as the signed message. • \mathsf{Ver} : – To verify m_{\mathrm{s}} , first check \mathsf{Chk}(m_{\mathrm{e}})=0 , otherwise abort. – Randomly select a subset \mathcal{V}\subset[M] satisfying |\mathcal{V}|=V . – For all j\in\mathcal{V} , use the certification phase of the shadow overlap protocol. Specifically, use \{o_{i}^{m_{\mathrm{e}}^{j},j}\}_{i\in[T]} as the classical shadows and the target state C^{m_{\mathrm{e}}^{j},j}|0\rangle . – Abort if shadow overlap protocol outputs Failed for any j\in\mathcal{V} . – Decode the message by outputting \mathsf{Dec}(m_{\mathrm{e}}) . To see why error detection helps, assume learning from classical shadows is intractable, and thus an adversary E is prevented from forging a signature by providing the circuit secret key. Then E must resort to changing a subset of bits and hoping they are not certified. To change the underlying message, the error correcting code forces E to modify at least d bits (the receiver will throw away any non-codeword). If d=d(M) scales sufficiently with code size, then these changes can be detected with high probability by, say, random sampling of bits on the codeword. The details of this argument are carried out in Section I.2 . I.1 Security of single-bit signatures We begin our security analysis with single bit messages. For our digital signatures protocol to be secure, it is necessary that a computationally-bounded adversary cannot obtain quantum circuits (within the circuit class of the protocol) that pass the shadow-based certification, in a time faster than certification itself. Thus, the critical assumption is the inability to efficiently learn circuits from classical shadows. Conjecture 1 (Computational no-learning from shadows) . Let \varepsilon,\eta\in[0,1] be fixed constants, and let \mathcal{C} be a family of unitary quantum circuits. The family \mathcal{C} is said to satisfy (\varepsilon,\eta) -Computational No-Learning from Shadows conjecture if the following holds with respect to any polynomial-time quantum adversary \mathcal{A} : given polynomial-sized classical shadows of some state \ket{C}=C\ket{0} for C\in\mathcal{C} , \mathcal{A} cannot output a classical description of some D\in\mathcal{C} such that \absolutevalue{\braket{C}{D}}=\absolutevalue{\bra{0}C^\dagger D\ket{0}}\geq 1-\varepsilon with probability at least 1-\eta . The task of learning quantum circuits from shadows has received relatively little attention compared to the related task of learning circuits from quantum states and from black-box queries to the circuit unitary Landau and Liu 2025 ; Huang et al. 2024b ; Fefferman et al. 2024 ; Kim et al. 2024 . Nonetheless, hardness results of the latter serve as evidence towards the former. For example, the no-learning from shadows assumption is implied (and inspired) by “no-learning from states” conjecture as introduced in Fefferman et al. 2025 . Conjecture 2 (Computational no-learning from states, Conjecture 1.1 of Fefferman et al. 2025 ) . Let \varepsilon,\eta\in[0,1] be fixed constants, and let \mathcal{C} be a family of unitary quantum circuits. The family \mathcal{C} is said to satisfy (\varepsilon,\eta) -Computational No-Learning from State conjecture if, given T=\poly(n) copies of an n -qubit quantum state \ket{C}=C\ket{0} , a polynomial-time quantum adversary \mathcal{A} cannot produce a \poly(n) -length classical representation of a circuit D such that \absolutevalue{\braket{C}{D}}=\absolutevalue{\bra{0}C^\dagger D \ket{0}}\geq 1-\varepsilon with probability at least 1-\eta . This conjecture is strictly stronger than Conjecture 1 . To see that, note that if one can learn circuits from shadows using an algorithm A , one can also learn the same circuit from copies of a state by first measuring the shadows, and then using A thereafter. Ref. Fefferman et al. 2025 provides several arguments in support of Conjecture 2 . Direct proof of the conjecture is obstructed: proving it for depth d=\log^{2}n brickwork Haar-random circuits would imply \mathrm{P}\neq\mathrm{PSPACE} , amounting to a mathematical breakthrough. However, examining the best current circuit learning algorithms suggest the hardness of learning sufficiently beyond \log -depth, such as with depth \log^{2}n . In fact, such hardness has been proven against the family of low-degree polynomial algorithms, which encompasses a large class of algorithms. Furthermore, the hardness of RingLWE used by post-quantum cryptography also implies the hardness of learning circuits, although assuming such hardness would defeat the purpose of avoiding assumptions used in classical cryptography. Finally, it is also shown that the no-learning conjecture is equivalent to assuming the existence of random circuit one-way state generators. Below, we formally instantiate the computational no-learning from states ( \mathrm{CNL} ) conjecture for a set of concrete circuit ensemble, adversary, and parameters. Definition 2 . We say the conjecture \mathrm{CNL}_{\mathcal{C},T,\mathcal{A},\varepsilon,\eta} holds if the following is true. Given T copies of the state |\psi\rangle such that |\psi\rangle=C|0\rangle for some C\in\mathcal{C} , with probability at least 1-\eta the adversary \mathcal{A} cannot learn a circuit C^{\prime}\in\mathcal{C} such that |\langle 0|C^{\prime\dagger}C|0\rangle|^{2}\geq 1-\varepsilon . Theorem 1 . If \mathrm{CNL}_{\mathcal{C},T,\mathcal{A},\varepsilon_{\mathrm{CNL}},\eta} holds and \tau(C|0\rangle)\leq\tau^{*} for all C\in\mathcal{C} , then, with probability at least 1-|\mathcal{C}|\delta-\eta , an adversary that does not have access to C^{b} fails Protocol I instantiated with a (T,\delta,\varepsilon_{\mathrm{CNL}},\tau(\cdot)) non-adaptive shadow overlap protocol. Additionally, an honest signer with fidelity at least 1-\varepsilon_{\mathrm{CNL}}/(2\tau^{*}) passes it with probability at least 1-\delta . Proof. If \mathrm{CNL}_{\mathcal{C},T,\mathcal{A},\varepsilon_{\mathrm{CNL}},\eta} holds, then with probability 1-\eta , any circuit C^{\prime} that \mathcal{A} returns must satisfy |\langle 0|C^{\prime\dagger}C|0\rangle|^{2}<1-\varepsilon_{\mathrm{CNL}} . To show this, we use proof by contradiction. The only information \mathcal{A} has access to are the shadows for the circuit C^{b} . If \mathcal{A} can learn C^{\prime} such that |\langle 0|C^{\prime\dagger}C|0\rangle|^{2}\geq 1-\varepsilon_{\mathrm{CNL}} just from the shadows, then it must also be able to learn C^{\prime} from copies of the state since it can measure the states and produce the shadows. Denote as \mathcal{W} the set of circuits C^{\prime} that satisfy |\langle 0|C^{\prime\dagger}C|0\rangle|^{2}<1-\varepsilon_{\mathrm{CNL}} , and we have |\mathcal{W}|<|\mathcal{C}| . Denote the output of \mathsf{Ver} when verifying on \mathsf{pk} , b , and C^{b} as \mathsf{Ver}(\mathsf{pk},b,C^{b}) . For any C^{\prime} such that |\langle 0|C^{\prime\dagger}C|0\rangle|^{2}<1-\varepsilon_{\mathrm{CNL}} , we have \displaystyle\Pr_{\mathsf{pk\sim\mathsf{Sign}}}[\mathsf{Ver}(\mathsf{pk},b,C^{\prime})=\textsc{Failed}]\geq 1-\delta, (3) which is guaranteed by the shadow overlap protocol since \tau(C^{\prime}|0\rangle)\;\leq\tau^{*} . Here, the hypothesis state is |\psi\rangle=C^{\prime}|0\rangle , and the state to certify is the lab state prepared by noisy C^{b} . The probability that no state the adversary can output leads to false certification is \displaystyle\Pr_{\mathsf{pk\sim\mathsf{Sign}}}[(\mathsf{Ver}(\mathsf{pk},b,C^{\prime})=\textsc{Failed})\text{ for all }C^{\prime}\in\mathcal{W}] (4) \displaystyle\geq \displaystyle 1-\sum_{C^{\prime}\in\mathcal{W}}\Pr_{\mathsf{pk\sim\mathsf{Sign}}}[(\mathsf{Ver}(\mathsf{pk},b,C^{\prime})=\textsc{Certified})]\geq 1-|\mathcal{C}|\delta. (5) Overall, this bounds the malicious-case false positive probability to |\mathcal{C}|\delta+\eta . The honest-case false negative probability (the probability of a honest signer signer failing the test) is simply \delta . ∎ Note that since |\mathcal{C}| is exponential in n , we need to make \delta exponentially small in n . However, since the sample complexity (size of classical shadows) scales with \ln(1/\delta) , this only increases sample complexity by a \poly(n) factor. The above derivation assumes that the classical shadows are collected for the ideal pure state C|0\rangle . In reality, a mixed laboratory state \sigma_{\mathrm{lab}} is prepared to generate classical shadows with fidelity \phi_{\mathrm{hon}}\equiv 1-\varepsilon_{\mathrm{hon}}\equiv\langle 0|C^{\dagger}\sigma_{\mathrm{lab}}C|0\rangle . In this case, we need to place a minimum assumed honest case fidelity \phi_{\mathrm{hon}} and find the corresponding upper bound on |\langle 0|C^{\prime\dagger}\sigma_{\mathrm{lab}}C^{\prime}|0\rangle|^{2} which is no longer bounded by simply |\langle 0|C^{\prime\dagger}C^{\prime}|0\rangle|^{2}\leq 1-\varepsilon_{\mathrm{CNL}} . Instead, the bound is given by the following two theorems. Lemma 1 . Under depolarizing noise, \displaystyle|\langle 0|C^{\prime\dagger}\sigma_{\mathrm{lab}}C^{\prime}|0\rangle|^{2}\leq 1-(\varepsilon_{\mathrm{CNL}}-\varepsilon_{\mathrm{hon}})+\varepsilon_{\mathrm{hon}}\frac{1}{2^{n}}. (6) Proof. Under the depolarizing noise, \displaystyle\sigma_{\mathrm{lab}}=(1-\varepsilon_{\mathrm{hon}})C|0\rangle\langle 0|C^{\dagger}+\varepsilon_{\mathrm{hon}}\frac{I}{2^{n}}. (7) Therefore, \displaystyle|\langle 0|C^{\prime\dagger}\sigma_{\mathrm{lab}}C^{\prime}|0\rangle|^{2} \displaystyle=(1-\varepsilon_{\mathrm{hon}})|\langle 0|C^{\prime\dagger}C^{\prime}|0\rangle|^{2}+\varepsilon_{\mathrm{hon}}\frac{1}{2^{n}} (8) \displaystyle\leq(1-\varepsilon_{\mathrm{hon}})(1-\varepsilon_{\mathrm{CNL}})+\varepsilon_{\mathrm{hon}}\frac{1}{2^{n}} (9) \displaystyle\leq 1-(\varepsilon_{\mathrm{CNL}}-\varepsilon_{\mathrm{hon}})+\varepsilon_{\mathrm{hon}}\frac{1}{2^{n}}. (10) ∎ Lemma 2 . Under general noise, \displaystyle|\langle 0|C^{\prime\dagger}\sigma_{\mathrm{lab}}C^{\prime}|0\rangle|^{2}=\sup_{0\leq\varepsilon^{\prime}_{\mathrm{CNL}}\leq\varepsilon_{\mathrm{CNL}}}\left(\sqrt{(1-\varepsilon_{\mathrm{hon}})(1-\varepsilon_{\mathrm{CNL}}^{\prime})}+\sqrt{\varepsilon_{\mathrm{hon}}\varepsilon_{\mathrm{CNL}}^{\prime}}\right)^{2}. (11) Proof. Denote |\psi_{\mathrm{hon}}\rangle=C|0\rangle and |\psi_{\mathrm{adv}}\rangle=C^{\prime}|0\rangle . For any mixed state \sigma_{\mathrm{lab}} such that \displaystyle 1-\varepsilon_{\mathrm{hon}}\equiv\langle\psi_{\mathrm{hon}}|\sigma_{\mathrm{lab}}|\psi_{\mathrm{hon}}\rangle, (12) we can write it as a sum of pure states \displaystyle\sigma_{\mathrm{lab}}=\sum_{i}w_{i}|\psi_{i}\rangle\langle\psi_{i}| (13) such that \displaystyle 1-\varepsilon_{i} \displaystyle\equiv|\langle\psi_{\mathrm{hon}}|\psi_{i}\rangle|^{2} (14) \displaystyle\sum_{i}w_{i}(1-\varepsilon_{i}) \displaystyle=1-\varepsilon_{\mathrm{hon}}, (15) can we can write the pure states as \displaystyle|\psi_{i}\rangle=\sqrt{1-\varepsilon_{i}}|\psi_{\mathrm{hon}}\rangle+\sqrt{\varepsilon_{i}}|\psi_{\mathrm{hon},i}^{\bot}\rangle (16) for some normalized |\psi_{\mathrm{hon},i}^{\bot}\rangle orthogonal to |\psi_{\mathrm{hon}}\rangle . Similarly, for any adversary state |\psi_{\mathrm{adv}}\rangle such that \displaystyle|\langle\psi_{\mathrm{adv}}|\psi_{\mathrm{hon}}\rangle|^{2}=1-\varepsilon^{\prime}_{\mathrm{CNL}}\leq 1-\varepsilon_{\mathrm{CNL}}, (17) we can write it as \displaystyle|\psi_{\mathrm{adv}}\rangle=\sqrt{1-\varepsilon^{\prime}_{\mathrm{CNL}}}|\psi_{\mathrm{hon}}\rangle+\sqrt{\varepsilon^{\prime}_{\mathrm{CNL}}}|\psi_{\mathrm{hon},\mathrm{adv}}^{\bot}\rangle (18) for some normalized |\psi_{\mathrm{hon},\mathrm{adv}}^{\bot}\rangle orthogonal to |\psi_{\mathrm{hon}}\rangle . Therefore, \displaystyle|\langle\psi_{\mathrm{adv}}|\psi_{i}\rangle|^{2} \displaystyle=\left(\sqrt{(1-\varepsilon_{i})(1-\varepsilon^{\prime}_{\mathrm{CNL}})}+\sqrt{\varepsilon_{i}\varepsilon^{\prime}_{\mathrm{CNL}}}\langle\psi_{\mathrm{hon},\mathrm{adv}}^{\bot}|\psi_{\mathrm{hon},i}^{\bot}\rangle\right)^{2} (19) \displaystyle\leq\left(\sqrt{(1-\varepsilon_{i})(1-\varepsilon^{\prime}_{\mathrm{CNL}})}+\sqrt{\varepsilon_{i}\varepsilon^{\prime}_{\mathrm{CNL}}}\right)^{2} (20) \displaystyle\equiv f(1-\varepsilon_{i}). (21) Further, one can easily check that for 0\leq\varepsilon_{i},\varepsilon_{\mathrm{CNL}}\leq 1 , we have f^{\prime\prime}(1-\varepsilon_{i})<0 and f is concave. With this, we can write \displaystyle\langle\psi_{\mathrm{adv}}|\sigma_{\mathrm{lab}}|\psi_{\mathrm{adv}}\rangle \displaystyle=\sum_{i}w_{i}|\langle\psi_{\mathrm{adv}}|\psi_{i}\rangle|^{2} (22) \displaystyle=\sum_{i}w_{i}f(1-\varepsilon_{i}) (23) \displaystyle\leq f\left(\sum_{i}w_{i}(1-\varepsilon_{i})\right) (24) \displaystyle=f(1-\varepsilon_{\mathrm{hon}}) (25) \displaystyle=\left(\sqrt{(1-\varepsilon_{\mathrm{hon}})(1-\varepsilon^{\prime}_{\mathrm{CNL}})}+\sqrt{\varepsilon_{\mathrm{hon}}\varepsilon^{\prime}_{\mathrm{CNL}}}\right)^{2}. (26) However, since we do not know the fidelity |\langle\psi_{\mathrm{adv}}|\psi_{\mathrm{hon}}\rangle|^{2}=1-\varepsilon^{\prime}_{\mathrm{CNL}} other than the fact that \varepsilon^{\prime}_{\mathrm{CNL}}\geq\varepsilon_{\mathrm{CNL}} and that f is not necessarily monotonic in \varepsilon^{\prime}_{\mathrm{CNL}} , we have to optimize \varepsilon^{\prime}_{\mathrm{CNL}} over the allowed interval to find the upper bound. ∎ With this, we can have an error aware version of the security guarantee. Corollary 1 . Set \varepsilon_{\mathrm{noisy}}=\varepsilon_{\mathrm{CNL}}-\varepsilon_{\mathrm{hon}} under depolarizing noise, or \displaystyle\varepsilon_{\mathrm{noisy}}=1-\sup_{0\leq\varepsilon^{\prime}_{\mathrm{CNL}}\leq\varepsilon_{\mathrm{CNL}}}\left(\sqrt{(1-\varepsilon_{\mathrm{hon}})(1-\varepsilon_{\mathrm{CNL}}^{\prime})}+\sqrt{\varepsilon_{\mathrm{hon}}\varepsilon_{\mathrm{CNL}}^{\prime}}\right)^{2} (27) under general noise. If \mathrm{CNL}_{\mathcal{C},T,\mathcal{A},\varepsilon_{\mathrm{CNL}},\eta} holds and \tau(C|0\rangle)\leq\tau^{*} for all C\in\mathcal{C} , then with probability at least 1-|\mathcal{C}|\delta-\eta , an adversary that does not have access to C^{b} fails Protocol I instantiated with a (T,\delta,\varepsilon_{\mathrm{noisy}},\tau(\cdot)) non-adaptive shadow overlap protocol. Additionally, an honest signer with fidelity at least 1-\frac{\varepsilon_{\mathrm{noisy}}}{2\tau^{*}} passes it with probability at least 1-\delta . Proof. The proof is similar to Theorem 1 . For all circuits C^{\prime} such that |\langle 0|C^{\prime\dagger}C|0\rangle|^{2}\leq 1-\varepsilon_{\mathrm{CNL}} , we have \displaystyle|\langle 0|C^{\prime\dagger}\sigma_{\mathrm{lab}}C^{\prime}|0\rangle|^{2}\leq 1-\varepsilon_{\mathrm{noisy}} (28) by Lemma 1 and Lemma 2 . Then, the shadow overlap protocol is going to output failed with probability at least 1-\delta for such circuits. A similar union bound for the probability is applied for all circuits in the ensemble. The honest case is similarly trivial. ∎ I.2 Security of multi-bit signatures In our proposal for a multi-bit signature, the sender encodes a k -bit message into a M -bit codeword using a classical error detection code [M,k,d] of distance d . Since the generation of signature is efficient, the sender signs all M bits of the encoded message. The receiver, on the other hand, only verifies the signature of a small fraction \alpha M of the message received. Specifically, the receiver accepts the signature if and only if a) the received message is a valid encoding per the error detection code and b) a random subset of \alpha M bits pass the signature verification. For any adversary to alter the signed message, it would have to “spoof” or alter at least d bits among the M -bit long message (otherwise, the received message is no longer a valid encoding). If d bits of the message were forged by an adversary, by uniformly spot-checking a small fraction V=\alpha M of the bits, the receiver would be able to detect any tampering of the original message. We begin by showing that the probability the verifier fails to detect at least one tampered bit decreases exponentially with V , the number of bits whose signature is verified. Lemma 3 . Consider an M -bit encoded message and suppose the verifier checks the signature of V bits uniformly at random. If an altered bit is checked, the verifier outputs Failed with probability at least 1-\delta_{1} . If an honest bit is checked, the verifier outputs Certified with probability at least 1-\delta_{2} . Denote as \Omega_{\mathrm{FP}} the false-positive event where an adversary alters at least \alpha M bits but none of the V signature certifications output Failed . Additionally, denote as \Omega_{\mathrm{FN}} the false-negative event where at least one of the V signature certification outputs Failed but there is no adversarial tampering (no bits were truly altered) (False Negative). Then \displaystyle\Pr[\Omega_{\mathrm{FP}}]\leq e^{-\alpha V}+\delta_{1},\qquad\text{and}\qquad\Pr[\Omega_{\mathrm{FN}}]\leq\delta_{2}V. (29) Proof. Let \Omega_{\mathrm{adv}} denote the event that an adversary alters at most \alpha M bits and let n_{\text{altered}} denote the number of altered bits in the randomly chosen validation set. The probability that the validation set will contain none of the “altered” bits is: \displaystyle\Pr[n_{\mathrm{altered}}=0|\Omega_{\mathrm{adv}}] \displaystyle\leq\frac{(1-\alpha)M}{M}\times\frac{(1-\alpha)M-1}{M-1}\times\cdots\times\frac{(1-\alpha)M-V+1}{M-V+1}\leq(1-\alpha)^{V}\leq e^{-\alpha V}. (30) On the other hand, if n_{\mathrm{altered}}\geq 1 , then the probability that at least one of the V signature certification outputs Failed is at least 1-\delta_{1} . Denote the number of Failed signatures as n_{\textsc{Failed}} . Overall, \displaystyle\Pr[\Omega_{\mathrm{FP}}]= \displaystyle\Pr[n_{\mathrm{altered}}=0|\Omega_{\mathrm{adv}}]+\Pr[n_{\textsc{Failed}}=0|n_{\mathrm{altered}}\geq 0\wedge\Omega_{\mathrm{adv}}]\cdot\Pr[n_{\mathrm{altered}}\geq 0|\Omega_{\mathrm{adv}}]\leq e^{-\alpha V}+\delta_{1}. (31) In the event \Omega_{\mathrm{honest}} where there is no adversary (no bits altered), the probability that at least one signature outputs Failed is \displaystyle\Pr[\Omega_{\mathrm{FN}}]=\Pr[n_{\textsc{Failed}}\geq 1|\Omega_{\mathrm{honest}}]=1-(1-\delta_{2})^{V}\leq\delta_{2}V. (32) ∎ Corollary 2 . For a message with M encoded bits, to achieve \Pr[\Omega_{\mathrm{FP}}]\leq\varepsilon and \Pr[\Omega_{\mathrm{FN}}]\leq\varepsilon under an adversary that alters at least \alpha M bits, having a single-bit digital signature protocol with \delta_{1}\leq\frac{\varepsilon}{2},\delta_{2}\leq\frac{\varepsilon}{V} and a verification fraction V\geq\frac{\ln(2/\varepsilon)}{\alpha} is sufficient. Proof. By Lemma 3 , we require \delta_{2}\leq\frac{\varepsilon}{V} by the false negative condition. Similarly, by the false positive condition, we require \varepsilon\leq e^{-\alpha V}+\delta_{1} . If \delta_{1}\leq\varepsilon/2 , then \varepsilon/2\leq e^{-\alpha V}\Rightarrow V\geq{\ln(2/\varepsilon)}/{\alpha} . ∎ Finally, we show Protocol I is secure with constant verification under reasonable assumptions. Theorem 2 . If there exists a linear [M,k,d] error detection code with relative distance d_{r}=d/M , the multi-bit signature Protocol 2 has false positive and false negative probabilities of at most \varepsilon . In particular, it requires 2M shadow-circuit pairs to use as public/secret keys, V=\max\{2,d_{r}^{-1}\ln(2/\varepsilon)\} of which are checked by the verifier. Each signature check must output Failed on an altered bit with probability 1-\delta_{1}\geq 1-\varepsilon/2 , and it must output Certified on an honest bit with probability 1-\delta_{2}\geq 1-\varepsilon/2 . Proof. If the adversary alters fewer than d bits, the tampering can be detected using the error detection code. If an adversary tampers at least d bits, by Corollary 2 , such an adversary may be detected with \delta_{1}\leq\frac{\varepsilon}{2},\delta_{2}\leq\frac{\varepsilon}{V} provided that V\geq\frac{\ln(2/\varepsilon)}{d_{r}M} . Taking V at least 2 ensures that the confidence bound holds even for \epsilon near 1. ∎ We saw how good error correcting codes could be used in the digital signatures protocol to avoid certifying a large fraction of the message. The key properties we would like in such a code are constant rate and relative distance as the block size increases. Furthermore, we would naturally like efficient encoding and decoding. Thankfully, there exists a restricted ensemble which retains good performance and has structure which allows for efficient decoding. Introduced by Robert Gallager in a 1963 PhD thesis Gallager 1962 , low density parity check (LDPC) codes are classical linear codes defined by a parity check matrix H which is sparse, in the sense that (a) few variables are assigned to each check and (b) each variable participates in a small number of checks. See Mezard and Montanari 2009 for a pedagogical introduction and ecz 2022 for specific code properties. As stated above, LDPC codes form a very large and imprecise class of sparse codes. For our purposes, it will suffice to consider a specific class known as Gallager’s ensemble , where the parity check matrix H is sampled uniformly at random among “regular” LDPC codes. Here regular means each check has fixed number of variables (degree) k , and similarly each variable has fixed degree \ell . Note that mk=n\ell , where m is the number of checks and n the number of variables. Let M be the block size and N\leq M the message size, with rate r=N/M , for a classical code H\sim\mathcal{G}(k,\ell) sampled from Gallager’s ensemble of degree k checks and degree \ell variables. It is conjectured Zyablov and Pinsker 1975 that the maximum efficiently decodable error weight w is given by \frac{w}{M}=(1+o_{k}(1))\mathrm{H}_{2}^{-1}\left(\frac{c^{*}(1-r)}{k}\right) (33) where o_{k} denotes asymptotics with respect to k , c^{*} is a universal constant, and \mathrm{H}_{2}^{-1}:[0,1]\rightarrow[0,1/2] is the inverse of the binary Shannon entropy. For fixed k and r , we thus see that, under this conjecture, the fraction of efficiently correctable errors in the message M remains fixed, even for constant rate. Moreover, it was shown in Gallager 1962 that the typical minimum distance of H\sim\mathcal{G}(k,\ell) scales linearly in the block size M . Thus, when LDPC codes are used in the digital signatures protocol, one only need check \gamma M=d_{r}^{-1}\ln(2/\epsilon)=O(\log(1/\epsilon)) bits per Theorem 2 . Thus, for such codes the number of verifications scales only with respect to the desired confidence, and logarithmically. II Evidence for computational no-learning Section I above formally introduces the proposed protocol for quantum digital signatures, and analyzes its security under the assumption of Computational No-Learning (CNL). This section discusses existing, and provides new, evidence for the CNL assumption within the setting of shallow quantum circuits. In order to falsify CNL for a given family of random quantum circuits and thereby compromise our proposed quantum digital signatures protocol, an adversary must have access to a circuit learning algorithm L which satisfies the following requirements. (a) The learning must be proper : L must return a circuit C within the circuit family \mathcal{F} agreed upon by all parties. (b) L must work for arbitrary circuit geometries, including circuits designed for devices with all-to-all connectivity. (c) L must learn given only access to the classical shadow measurement results published by the communicating parties. As we discuss in Sec. II.1 , there is no known circuit learning algorithm that satisfies even two of the three requirements. In Sec. II.2 , we introduce an algorithm satisfying the first two requirements. However, there is no clear path to extending it to satisfy all three requirements as it requires a much stronger access model. Finally, Sec. II.3 we show that the circuits used in our experiment are secure against this new algorithm even if adversary is allowed stronger access . In combination, this suggests that major algorithmic breakthroughs are required to compromise the security of the our protocol. II.1 Failure of known quantum algorithms for learning shallow quantum circuits At present, there is no known algorithm for learning shallow quantum circuits which satisfies property (c) above: learning from access to classical shadow measurements and a fixed input state. This rules out any immediate challenges to the protocol. However, there is also no obvious barrier to the development of such algorithms, and the study of learning shallow circuit has only been initiated relatively recently. To assess the potential for effective learning algorithms to break the quantum signatures protocol, here we consider algorithms for closely related circuit learning scenarios. Even allowing this flexibility, we will see that these algorithms fail our stringent learning requirements, and overcoming any of them would require major algorithmic developments or conceptual breakthroughs. Most existing algorithms for learning shallow circuits take advantage of the fact that each qubit at input has causal influence over a small subset of qubits Huang et al. 2024b ; Landau and Liu 2025 ; Fefferman et al. 2024 . Such causal structure, for circuits with interaction locality (each gate has bounded number of input qubits), tends to break down at logarithmic depth or greater. This causes this class of algorithms to fail on circuits of depth O(\log^{2}n) and higher. However, there are several reasons to consider circuit families which are as shallow as possible, yet hard to learn. Besides reducing computational footprint, using shallower circuits as the private key brings quantum digital signatures closer to the realm achievable by near-term quantum hardware. Additionally, it is desirable to delineate the precise transition into CNL with respect to depth, both for its own sake and for assessing how secure a family of circuits is for the protocol. The work of Huang et al. 2024b initiated the recent studies of learning shallow circuits, showing how circuits C of constant depth, with arbitrary geometry, can be learned in diamond distance in polynomial time, producing a circuit representation C^{\prime} that is also depth O(1) . However, the algorithm requires either unitary query access to C or to randomized measurements over randomized (tomographically complete) inputs. This fails requirement (c) in several ways, in particular, requiring access to variable initial states. Moreover, the algorithm is an improper learner and fails point (a): the representation circuit C^{\prime} has additional qubits and longer depth compared to C itself. Thus, this algorithm only satisfies point (b) above. A more suitable algorithm, which learns state preparation circuits is given by Landau and Liu 2025 ; Kim et al. 2024 . Here the task is more aligned with digital signatures, since one is required only to produce a circuit C^{\prime} such that C^{\prime}\ket{0}\approx C\ket{0} . However, these algorithms also fail to be proper (requirement (a)), requiring ancillary qubits and greater circuit depth than the original. Moreover, unlike the work of Huang et al. 2024b , the algorithm is limited to geometrically local circuits, and thus does not satisfy property (b). However, (c) is closer to being satisfied compared with the aforementioned algorithm, since the learner only requires a fixed input state. To summarize, all but one existing results on learning shallow circuits give improper algorithms, failing to learn circuit representations within the class \mathcal{C}_{n,d} of n -qubit d -depth circuits. While circuit compression schemes could conceivably reduce improperly-learned circuits to proper ones, such computations ought to be generally expensive (though there appears few concrete statements theoretically towards this). To our knowledge, the only competitive algorithm for proper learning of shallow unitary quantum circuits comes from Fefferman et al. 2024 Fefferman et al. 2024 . There, it was shown that brickwork random circuits with discretized Haar random gates can be efficiently and properly learned up to logarithmic depth. This impressive performance comes at the price of loss of generality: a gate set is specified and the architecture (brickwork) is known to the learner a priori. While the authors recognized that the method can be generalized to circuits with “good lightcone properties,” the full dimensions of this statement have not been explored. Moreover, the algorithm fails to satisfy point (c) above, requiring query access to C so that the learner can test cause-effect relationships with changes to the input. Taken with the condition of proper learning, the need for strong access to C seems to eliminate all existing candidates for learning shallow circuits in our protocol. While this already provides evidence in favor of CNL, we further strengthen our claims of security by assuming a hypothetical learner that has the appropriately strong access and devising an extension of the proper learning algorithm of Ref. Fefferman et al. 2024 . II.2 Proper learning algorithm for all-to-all shallow circuits In pursuit of better learning algorithms, and a better understanding of thee hardness of learning under relevant settings, we extend Fefferman et al. 2024 to accommodate more flexible situations and architectures, such as all-to-all circuits. We choose the algorithm of Fefferman et al. 2024 as a starting point because, despite the overly strong circuit access not available in our setting, this algorithm is closest to the type needed to properly learn shallow circuits. It is plausible that an adversary may have knowledge of the circuit architectures used in the signature protocol, without knowing specific gates. Additionally, we note that hardness results derived under stronger access conditions necessarily hold in the weaker case of practical relevance. These results on learning may be of interest beyond cryptographic applications, and additional details of the method will be the subject of a forthcoming paper. Because the core idea of the method is simple, we start with a description before moving into technical conditions for success. Most existing learning algorithms for shallow circuits attempt to exploit what is perhaps the key feature induced by shallowness: limited causal influence. Let Q be the collection of n qubits in a circuit. A unitary quantum circuit C naturally defines a directed, acyclic graph, with vertices representing gates and edges representing qubit wires, with specific qubit label. This graph defines causal relationships between qubits according to path connectivity. A forward causal set \vec{q}_{\ell}\subseteq Q for qubit q\in Q is the collection of qubits which are contained in some path originating at q at layer \ell\in[d] . Likewise, a backward causal set \reflectbox{$\vec{\reflectbox{$q$}}$}_{\ell} can be defined in the reverse sense. Forward and backward causal sets generally offer independent sources of information about causal connectivity in the circuit graph. In principle, any q^{\prime}\in\vec{q} can be influenced by changes in the state of q at input. The original causal, or “light cone,” approaches to learning shallow circuits are due to Huang et al. 2024b and Landau and Liu 2025 . These approaches utilize the low operator growth of local observables to learn their time evolution and, from a “stitching” procedure, produce a single circuit which implements each Heisenberg evolution. Although Fefferman et al. 2024 also uses a light cone argument, their method instead utilizes architecture knowledge to detect whether connections have been “broken” by local gate inversions at the front (or back) of the circuit. To illustrate, consider the setup of Fig. 6 . There is a gate G at the beginning of the circuit such that, when G is present, q and q^{\prime} are path connected, but when removed, q,q^{\prime} are disconnected. We call such a gate a pivot gate . While Fefferman et al. 2024 considered brickwork circuits in particular, this method can be generalized to various architectures, even geometrically nonlocal ones. In an analogous manner, pivot gates can be identified at the back of the circuit. Figure 6: Basic principle behind local inversion learning algorithm, using pivot gate G . a , Qubit q has a forward light cone, shown with yellow lines, determined by the gate layout of the circuit. Because qubit q^{\prime} is contained in this light cone, effects from q can be measured, in principle, at output. b , When gate G is removed, however, q at input does not connect to q^{\prime} at output, as shown by the new light cones. Measurements observe no changes when the initial state of q is modified. In some cases, this is a computationally efficient observable that can allow for effective learning at shallow depths. Given the circuit graph (“gate layout”) of C , the learner’s strategy is to identify the location of a pivot gate G , prepend (or append, for G in back) to C some “trial inverse” G^{\prime\dagger} , and test if q^{\prime} is no longer causally influenced by q . More precisely, one seeks to induce an approximate factorization G^{\prime\dagger}G\approx U_{1}\otimes U_{2} for single qubit U_{1},U_{2} . This event is detected through single-qubit tomography between an input qubit q and output q^{\prime} . More precisely, for distinct choices \rho,\rho^{\prime} of state q at input, one checks whether the corresponding output states \pi,\pi^{\prime} are either (a) identical and \dist(\pi,\pi^{\prime})=0 , or (b) distinct by some threshold g>0 so that \dist(\pi,\pi^{\prime})>g . Fig. 7 describes this procedure SingleInvert , which is a generalization of Algorithm 2 from Fefferman et al. 2024 . Figure 7: Single gate inversion heuristic. The meta-algorithm iterates over a set of trial local inversions until one of them breaks the connection between q and q^{\prime} induced by G . Detecting this breaking is done through the SingleQubitTomography protocol, which tests whether q^{\prime} is affected by changes in the state of q at input. SingleInvert Input : Black-box query access to U_{C} . Labels for input/output qubits \partial G=\{q,q_{2}\} of pivot gate G\in\mathbb{U}(4) , and corresponding pivot qubits (q,q^{\prime}) . Output : Description of gate G^{\prime} such that G^{\prime\dagger}G\approx U_{1}\otimes U_{2} . Parameters : Factorization precision \epsilon_{f} , tomography precision \epsilon_{t} . for G^{\prime} in trial gate set on \{q,q_{2}\} do if G is front gate then 1 U\leftarrow U_{C}G^{\prime\dagger} 2 else 3 U\leftarrow G^{\prime\dagger}U_{C} 4 end if 5 for (\sigma,\sigma_{2}) in \{X,Y,Z\}\times\{I,X,Y,Z\} do 6 7 initialize Q\leftarrow\ket{0}^{\otimes n} 8 set q\leftarrow(I+\sigma)/2 and q_{2}\leftarrow(I+\sigma_{2})/2 9 \pi\leftarrow SingleQubitTomography (q^{\prime},U,Q,\epsilon_{t}) initialize Q\leftarrow\ket{0}^{\otimes n} 10 set q\leftarrow(I-\sigma)/2 and q_{2}\leftarrow(I+\sigma_{2})/2 /* Same but with changed state of q */ 11 \pi^{\prime}\leftarrow SingleQubitTomography (q^{\prime},U,Q,\epsilon_{t}) 12 if \dist(\pi,\pi^{\prime})<\epsilon_{f} then 13 return G^{\prime} 14 end if 15 end for 16 end for 17 Protocol fails if this point reached 18 A full circuit learning protocol can be built from recursive calls to SingleInvert . For each successful inverse G^{\prime\dagger} of G , we add G^{\prime} to our circuit C^{\prime} under construction and prepend G^{\dagger} to our calls to U_{C} . Some technical obstacles must be dealt with, such as the possibility of consecutive gates with identical support. This thwarts a naive approach to learning because removing only one of these gates does not change the causal structure. The natural solution is to treat all such sequences as a single composite gate. After this compressed circuit has been learned, arbitrary gate insertions can be used to match the original architecture, if desired. Fig. 8 provides pseudocode for the full heuristic algorithm. Figure 8: Forward-only learning protocol for a unitary circuit C , given oracle access and the circuit graph but not the gates themselves. After computing the causal sets of each qubit, and pre-conditioning the circuit structure, one iterates the SingleInvert protocol with parameters \epsilon_{t},\epsilon_{f} depending on specific settings. With each successful inversion, G is removed from C ’s circuit graph, and the unitary G^{\prime} is added to the result C^{\prime} . Final decompression consist of choosing arbitrary sequence for G^{\prime} to match the layout of uncompressed C . We assume each SingleInvert is successful. ForwardLearn Input : Black-box query access to U_{C} . Circuit graph for C . Output : Description of circuit C^{\prime} (circuit graph with labelled gates) with same circuit graph as C . Parameters : Factorization precision \epsilon_{f} , tomography precision \epsilon_{t} . \texttt{Compress}(C) /* Group together consecutive gates, if exist */ Compute all forward causal sets for C . 1 partial_only \leftarrow false 2 for G in C (front:back) do 3 if G is not pivot in C then 4 partial_only \leftarrow true 5 break /* Continue to invert what is possible */ 6 end if 7 Find pivot pair (q,q^{\prime}) for G , and \{q,q_{2}\}=\partial G 8 G^{\prime}\leftarrow\textnormal{{SingleInvert}}(\partial G,C,q^{\prime}) 9 C .prepend( G^{\prime\dagger} ) and C^{\prime} .append( G^{\prime} ) 10 end for 11 Invert trivial parts of remaining circuit (if applicable, e.g. single-qubit rotations). 12 if partial_only then 13 print: Warning, only partial inversion possible. 14 end if 15 Decompress ( C^{\prime} ) /* Arbitrarily decompose any grouped gates from Compress */ 16 return C^{\prime} 17 II.2.1 Requirements Our description of the learning approach omits important details for implementation, such as the set of trial gates G^{\prime\dagger} or factorization precision \epsilon_{f} . These will depend on the class of circuits, and learning will not always be tractable. However, two characteristics are necessarily required for learning: 1. Good light cones: At each stage of the algorithm, there must exist a pivot gate. 2. Strong signal propagation: For pivot qubits (q,q^{\prime}) , it must be possible to determine if q^{\prime} belongs to q ’s light cone using local measurements. The first property more explicitly means that, after each successful local inversion, there must be some outer gate G and qubits q,q^{\prime}\in Q such that q connects to q^{\prime} , but only through G . This holds for many interaction-local unitary circuits, especially below depth d=O(\log n) , since below this depth the causal sets are proper subsets of Q and additional casual connections are possible. If at any point during the simplification process, no outer gates are pivot gates (at either end of the circuit), then the learning algorithm fails. Given any circuit graph, one can check this property by efficiently checking the light cone properties classically, prior to attempting a learning protocol. Strong signal propagation can be formulated in the following way: let \Phi_{C} be the single-qubit channel between pivot qubits q,q^{\prime} induced by U_{C} . For any input states \rho,\rho^{\prime} of q , we would like \dist(\Phi_{C}(\rho),\Phi_{C}(\rho^{\prime}))>G\dist(\rho,\rho^{\prime}) for some G depending on properties such as graph distance between q and q^{\prime} . This may be hard to show formally in many cases, but for the case of Haar-random circuits such a bound was shown by Fefferman et al. 2024 . Theorem 3 (Theorem 1.1 of Fefferman et al. 2024 ) . Let C be a random quantum circuit with a fixed architecture, where each gate is a k -qubit independent Haar random unitary. Let q,q^{\prime} be qubits that are d distance apart in the circuit. Arbitrarily fix the inputs to C except q , and let \Phi_{C} be the channel from q to q^{\prime} induced by C . Then for every \gamma>0 , with probability at least 1-\gamma over C the following holds: For every two single-qubit states \rho and \rho^{\prime} , \norm{\Phi_\cal{C}(\rho) - \Phi_\cal{C}(\rho')}_{\mathrm{F}}\geq\norm{\rho- \rho'}_{\mathrm{F}}\cdot(2^{-d}\gamma)^{c_{k}} where c_{k}>0 is a constant that depends only on k and \norm{\cdot}_{\mathrm{F}} is the Frobenius norm. We observe that this non-mixing result is agnostic to the choice of architecture as long as it is fixed in advance. Because G exponentially decreases in d for such Haar random circuits, polynomial-time learning is limited to logarithmic depths. It is plausible that Haar random circuits have very strong mixing properties, and that other gate families would allow for even stronger degrees of influence. Finally, besides the above two “essential” ingredients for learning, one must also properly consider the effects of small errors in the factorization U_{1}\otimes U_{2} . If G^{\prime\dagger}G is not exactly product structure, lingering causal influences will interfere with subsequent inversions. For continuous Haar random circuits, a simple error analysis conducted in Fefferman et al. 2024 shows that compensating for these errors leads to quasi-polynomial runtime. This is still sub-exponential and may plausibly be done faster than verification. Moreover, working with circuits that only have finite gate families can ameliorate this computational barrier to learning. Ultimately, we find this issue to be generally of less practical concern for effective learning than the previous two points. II.3 Security against extended learning algorithm Of the conditions mentioned previously for successful learning by local inversion, perhaps the one most naturally in control of the communicating parties is choice of circuit graph. By choosing a circuit with poor light cones, this type of learning attack can be successfully thwarted. A natural choice is to ensure that the forward and backward light cones for each qubit q\in Q contain every single qubit, even if several layers are removed. There are limitations imposed by interaction locality on how quickly such light cones can be generated. In particular, k -local circuits should require at least \log_{k}(n) depth. With proper circuit design this can be shown to be sufficient. Theorem 4 . Fix an integer k\geq 2 . For every d\in\mathbb{Z}_{+} , there exists a circuit C_{d} with n=k^{d} qubits, depth d , and k -local gates, such that for every qubit q\in Q , \vec{q}=\reflectbox{$\vec{\reflectbox{$q$}}$}=Q . Proof. We construct C_{d} as follows. Label each qubit with a unique integer in [n] represented in k -ary: q=q_{d-1}\ldots q_{1}q_{0} ( q_{j}\in[k] ). Let (L_{\ell})_{\ell\in[d]} be a sequence of k -regular partitions of [n] , where a block B\in L_{\ell} includes all k^{d-1} qubits which match in every digit except the \ell th. Define the circuit \mathcal{C}_{d} by assigning a k -qubit gate according to each block in the layer, and stacking the layers together in order, L_{1} applied first. Consider now a qubit q=q_{d-1}\ldots q_{1}q_{0} at input, and consider the succession of causal sets \vec{q}_{\ell} defined by paths from q at input of length at most \ell . For \ell=1 \vec{q}_{,1} contains all bitstrings which match all but the least significant digit q_{0} . After the second layer, \vec{q}_{,2} contains all qubits which match q except for the last two digits. Continuing inductively, after d layers, \vec{q}_{,d}\equiv\vec{q}_{0}=[n] . Because q was arbitrary, we see that \vec{q}=Q for every q . The backwards causal sets \reflectbox{$\vec{\reflectbox{$q$}}$}_{,\ell} out to depth \ell can be determined in the same manner, but traversing the strings in the opposite direction starting from the most significant bit. We conclude all forward light cones and backward light cones, from input and output respectively, contain every other qubit. ∎ The circuit constructed in the above proof is used to demonstrate the existence of \log_{k}(n) depth circuits that thwarts the light cone learning algorithm, and is not actually used in the experiment. It obeys the connectivity of a hypercube, and has intermediate connectivity between geometrically local (for fixed dimension) and all-to-all architectures. However, there is no faster way to expand the light cones compared with the above example: at each stage the causal set multiplies by a factor of k . Finally, by appending to C_{d} at least one layer, and maybe more for enhanced security, no causal boundary across layers is present. It is plausible that such a circuit is relatively secure against other conceivable learning attacks based on light cone arguments. II.3.1 Advanced considerations For circuits with simple geometric structures, such as brickwork, there is no need to differentiate between removing gates at the beginning or the end due to the symmetry. For more general circuits, however, this symmetry is not present, and a combination of front and back learning can be strictly more powerful than one direction alone. In particular, it is possible that the removal of a gate at the end may cause a new gate at the beginning to become a pivot gate. This is illustrated in Fig. 9 , demonstrating that alternating between forward and backward inversions is strictly more effective. However, such a protocol is obstructed from learning the circuit of Theorem 4 with appended layers, or any circuit with many layers of full light cone coverage. This is because no outer gates are pivots from the very beginning. Figure 9: Example of circuit learnable only through forward-backward alternation for learning. a, the only outer gates are A,B, and F . If removing gates is only allowed from the back, the algorithm will fail. This is because F is not a pivot gate and the backward causal influence of any qubit is all qubits. Similarly, if the learning algorithm is only allowed to remove gates from the front, the algorithm will fail. Although one can remove pivot gate A, (see a,b for changes in the forward causal influence of qubit 1 before and upon removing A ), B becomes the remaining outer gate and is not a pivot. However, after removing A , the gate F becomes a pivot gate, as is shown by the change in the backward causal influence of qubit 2 before and after removing F (compare b,c ). Therefore, F and can be removed from the back. After this, one can easily learn gate-by-gate. Even with full light cone coverage, more sophisticated and expensive learning attacks could be tried. For example, one could group together gates into a composite unitary on k>2 qubits that does have good light cone properties. Then one could search for local inversions over the larger unitary space, in a brute force manner. Such a procedure is always guaranteed to succeed, since in the hardest case it reduces to full search over entire circuit. The possibility of gate grouping could require somewhat deeper circuits in order to thwart an adversary. However, we stress that, for our present digital signatures experiment, the adversary already has much weaker circuit access than considered in this section, and therefore these advanced learning techniques are not of primary concern. III Gap between verification and learning The evidence presented in Section II suggests that existing quantum algorithms for learning sufficiently deep random circuits require exponentially many queries of either the target quantum state or the unitary. As a result, access to polynomial-length classical shadows (without the ability to manipulate the input states) appears to render the task of learning circuit from shadows computationally expensive, if not intractable, for such circuits. However, because signature verification itself requires exponential time, it is desirable that learning the circuit in question is not merely as difficult as verification, but rather exponentially harder. Formally, if T_{V} denotes the time for verification, and T_{L} the time for an adversary to learn the private circuit, one would like T_{L}/T_{V} to be very large, e.g., T_{L}/T_{V}=2^{\Omega(n)} . Below we provide two types of evidence for such a gap, first by considering the limitations of so-called “low-degree polynomial” learning algorithms in Sec. III.1 , and second by considering oracle-based learning algorithms like those based on training variational circuits in Sec. III.2 . III.1 Gap due to learning hardness with low-degree polynomials One approach to establishing evidence for hardness of learning is to prove hardness for a class of algorithms that use low-degree polynomials , where the output of the algorithm is a low-degree polynomial of the input. These algorithms are frequently analyzed in the context of high-dimensional statistical inference problems that seek conclusions about the distribution of high-dimensional data from some samples. In such problems, even when the data contains sufficient statistical information for inference, there may not exist an efficient algorithm to reach that decision. Such problems are said to exhibit an information-computation gap . Low-degree polynomials provide a powerful framework of obtaining heuristic or rigorous results on the computational complexity of problems, and they capture a wide range of algorithms including spectral methods, approximate message passing, and local algorithms on graphs Wein 2025 . In the quantum setting, we are frequently interested in learning properties of a quantum state by measuring copies. As before, even when polynomially many copies may provide enough information, there may not exist computationally efficient algorithms to learn such properties. A recent initial study of low-degree quantum learning algorithms is provided in Ref. Chen et al. 2025 , where the authors show hardness of various learning tasks using such algorithms. In particular, they apply their framework to the digital signature of Ref. Fefferman et al. 2025 and claim to prove that learning depth \tilde{\Theta}(k\log n) brickwork random circuits using degree k polynomials only succeeds with an inverse superpolynomially small probability, which encompasses the learning algorithms discussed above from Refs. Huang et al. 2024b ; Landau and Liu 2025 . This holds in the usual low-degree model where k=\omega(\log n) and the algorithm has polynomial time, hence polynomial time low-degree learning of \mathrm{depth}\geq\log^{2}(n) brickwork random circuits is impossible. In fact, their argument is valid up to k=\Theta(n) . III.1.1 Relations between learning and hypothesis testing We first briefly recap the result in Ref. Chen et al. 2025 showing that depth-( \log^{2}n ) circuits cannot be learned using a polynomial-time low-degree algorithm. Consider algorithm \mathcal{A} for learning quantum circuits C\sim\mathcal{E} (with high probability) sampled according to some distribution \mathcal{E} , given m copies of the state C|0\rangle . In particular, \mathcal{A} performs single-copy projection-valued measurements (PVMs) on C|0\rangle , and the set of all PVMs captures all measurements that can be performed on the state without using ancillae. These measurements on the m copies of C|0\rangle could be non-adaptive, meaning they are independent from each other, or adaptive, meaning earlier measurement results may affect the choice of PVMs for later measurements. For the algorithm to be low-degree, the output of the algorithm must be a low-degree polynomial of the binary variables b_{ij} corresponding to the i th bit of the j th measurement outcome. Fig. 1 and 2 in Section 6 and 7 of Ref. Chen et al. 2025 provides an intuitive illustration of what we mean by a low-degree algorithm using single-copy PVMs. To prove the hardness of learning, Section 8.2 of Ref. Chen et al. 2025 compiles \mathcal{A} into a hypothesis testing algorithm and shows that the related hypothesis testing problem cannot be solved using a low-degree polynomial algorithm. Specifically, they consider the following problem: given access to copies of an unknown n -qubit quantum state \rho and given an ensemble \mathcal{S} of structured states, distinguish between the following two cases: • Null case: \rho=I/2^{n} . • Alternative case: \rho\sim\mathcal{S} . To connect to quantum circuit learning, choose \mathcal{S}=\{C|0\rangle\}_{C\sim\mathcal{E}} . If \mathcal{A} learns a circuit C_{\mathrm{adv}} such that \Pr[|\langle 0|C_{\mathrm{adv}}^{\dagger}C|0\rangle|^{2}\geq\varepsilon]\geq\delta over choices of \rho\sim S and random outcomes C_{\mathrm{adv}} of the algorithm, then the following algorithm succeeds at the above hypothesis testing problem. First, use \mathcal{A} on some of the measurement samples to output C_{\mathrm{adv}} . Then, apply C_{\mathrm{adv}}^{\dagger} to a copy of the state and measure if the resulting state C_{\mathrm{adv}}^{\dagger}C\ket{0} is |0\rangle . If \ket{0^n} is measured, we output the “Alternative Case”. From our construction of \mathcal{A} , if \rho\sim\mathcal{S} , with probability at least \delta , we have |\langle 0|C_{\mathrm{adv}}^{\dagger}C|0\rangle|^{2}\geq\varepsilon and the probability of measuring |0\rangle is at least \varepsilon . On the other hand, if \rho=I/2^{n} (null case), the probability of measuring all zero is 1/2^{n} . Overall, the probability that the alternative case is guessed correctly is at least \delta\varepsilon . The probability that the null case is accidentally guessed as the alternative case is 1/2^{n} . Therefore, the algorithm is said to achieve \eta -detection, where \eta=\delta\varepsilon-1/2^{n} . Here, \eta is defined as the gap in the probability that the detection algorithm outputs 1 in the null and alternative cases, and the algorithm is said to achieve weak detection if \eta=\Omega(1) . For constant \varepsilon , for low degree algorithms to achieve weak detection of the hypothesis testing problem, the low-degree learning algorithm \mathcal{A} must satisfy \Pr[|\langle 0|C_{\mathrm{adv}}^{\dagger}C|0\rangle|^{2}\geq\varepsilon]\geq\Omega(1) . In our setting, the signer non-adaptively measures m copies of the laboratory state \sigma_{\mathrm{lab}} honestly prepared on a finite-fidelity quantum computer to generate the classical shadows, and this information is used by a spoofer to learn the circuit with a learning algorithm \mathcal{A} . Our learning-from-shadows setting restricts \mathcal{A} ’s access to m copies of the quantum state using non-adaptive PVMs. Further, for the case of single-qubit random Pauli shadows, the set of PVMs is restricted to single-qubit local PVMs. In the case of level- \ell random Clifford shadows where a random \ell -qubit Clifford unitary is applied before measurement of each copy, the learner \mathcal{A} ’s access is restricted to \ell -qubit local PVMs. III.1.2 Prior results on the hardness of hypothesis testing We first introduce the machinery used for analyzing hypothesis testing. In this section, although certain discussions follow Ref. Hopkins 2018 , we appropriately translate the notation of Ref. Hopkins 2018 into that of Ref. Chen et al. 2025 . In Ref. Hopkins 2018 , one aims to distinguish between the null and alternative hypotheses by sampling a random variable X\in\mathcal{X} from distribution D in the null case and D^{\prime} in the alternative case. A test function t:\mathcal{X}\rightarrow\{-1,1\} aims to output the incorrect binary label with at most o(1) probability. With unbounded computational power, the statistical limit of distinguishing the hypotheses is given by the optimal test function using the likelihood ratio test: \displaystyle t(x)=\begin{cases}1\quad&\text{if}\penalty\ \frac{D^{\prime}(x)}{D(x)}>1\\ -1\quad&\text{otherwise.}\end{cases} (34) The test function is said to achieve \eta -detection if \displaystyle\left|\underset{x\sim D}{\Pr}[t(x)=1]-\underset{x\sim D^{\prime}}{\Pr}[t(x)=1]\right|>\eta. (35) Moving to low-degree polynomials, binary output test functions can be constructed using the so-called simple statistic . We say p is a k -simple statistic if p(x)=\sum_{i}p_{i}(x) , each p_{i} depends on at most k input variables, and \mathbb{E}_{D^{\prime}}[p(x)^{2}]=1 . Ref. Chen et al. 2025 does not use the language “simple statistic” and does not center p , whereas Ref. Hopkins 2018 shifts p so that \mathbb{E}_{D}[p(x)]=0 . The simple statistic captures in spirit a scoring function that likely outputs a high value for the alternative case, meaning \mathbb{E}_{D^{\prime}}[p(x)] is large, and it is common to assume a bound on \mathbb{E}_{D^{\prime}}[p(x)^{2}] . It can then be used within a binary output test function t(x)=\mathbbm{1}[p(x)\geq c(n)] (where \mathbbm{1} outputs 1 if the condition is true and -1 otherwise) for some threshold c(n) that grows with the problem size. This only works when the variances of p(x) under both hypotheses are bounded and the gap in the expectation value of p(x) does not approach 0. Therefore, the asymptotic behavior of \mathbb{E}_{D^{\prime}}[p(x)] (which is the same as the gap for Ref. Hopkins 2018 ) is crucial in determining whether detection of the alternative hypothesis is possible. In particular, if \mathbb{E}_{D^{\prime}}[p(x)]=o(1) , we say that weak detection is not possible. On the other hand, having \Omega(1) gap in the simple statistic does not guarantee weak detection, since the resulting test function still might under-perform. Nevertheless, upper bounding the gap in p(x) is sufficient to rule out distinguishers. Since Ref. Chen et al. 2025 does not center p for the null hypothesis, the gap is more explicitly expressed as \displaystyle\mathrm{adv}=\underset{\|p\|_{D}=1}{\sup}\bigg|\mathbb{E}_{D}[p(x)]-\mathbb{E}_{D^{\prime}}[p(x)]\bigg| (36) and is called the distinguishing advantage. If p=p^{*} is the optimal polynomial, the advantage is: \displaystyle\mathrm{adv} \displaystyle=\bigg|\sum_{x}D(x)p^{*}(x)-\sum_{x}D^{\prime}(x)p^{*}(x)\bigg|=\Bigg|\sum_{x}D(x)p^{*}(x)\left[\frac{D^{\prime}(x)}{D(x)}-1\right]\Bigg|=|\langle p^{*},\bar{D}-1\rangle_{D}| (37) for \bar{D}=D^{\prime}/D , where \bar{D} is the likelihood ratio. By the Cauchy-Schwarz inequality, p^{*}=(\bar{D}-1)/\|\bar{D}-1\|_{D} maximizes this inner product, and \mathrm{adv}=\|\bar{D}-1\|_{D} . The rest of the analysis in Chen et al. 2025 follows assuming D is the uniform distribution, which simplifies the analysis. For low-degree polynomials, they constrain the optimization to p\in\mathcal{V}^{\leq k} (polynomials of degree k ). Redefining the advantage to maximize only over k -degree polynomial results in a smaller advantage \mathrm{adv}=\|\bar{D}^{\leq k}-1\|_{D} , where f^{\leq k} is the projection of f onto V^{\leq k} . Finally, to rule out low-degree polynomials, we need \|\bar{D}^{\leq k}-1\|_{D}=o(1) , which is hypothesized to rule out weak detection in Conjecture 1 of Ref. Chen et al. 2025 or Conjecture 2.2.4 of Ref. Hopkins 2018 . To achieve this for degree- k polynomials, it turns out that the so-called the k -local indistinguishability needs to be small \displaystyle kLI=d_{\mathrm{tr}}\left(\mathbb{E}_{\rho\sim\mathcal{E}}\mathrm{tr}_{[mn]/T}\rho^{\otimes m},\frac{I}{2^{|T|}}\right)\leq 2^{-\tilde{\Omega}(k\log{n})}, (38) where T is a set of at most k qubits. The condition above checks if a mn -sized subsystem ( m samples, each of size n ) of \rho^{\otimes m} is measurably different from the maximally mixed state. However, this cannot hold for k>n/\log{n} . Even if \rho is drawn from a random circuit distribution (or some ensemble that approaches Haar-random), this trace distance is expected to decay at most by 2^{-n} Ghosh et al. 2025 , which means that one can only satisfy the requirement for k\leq n/\log{n} . III.1.3 Our extension As evidence for the security of our protocol, we’d like to show that the time-complexity of circuit learning is 2^{\omega(n)} . Since verification takes time \Theta(2^{n}) , this would ensure an asymptotic gap between verifying and spoofing. The time-complexity of a learning algorithm is intimately related to the degree of the learning algorithm. But, how large does k need to be to ensure a gap? Naively, for polynomials with N variables, a k -degree algorithm can have at most \binom{N+k}{k} many terms and therefore the time complexity is O\left(\binom{N+k}{k}\right) . However, certain polynomials of high degree might be much more efficient to evaluate (for example when the polynomial consists of a single term). Nevertheless, a heuristic degree-runtime correspondence has been hypothesized in Hopkins 2018 that argues that, as discussed above Hypothesis 3.2 of Ref. Wein 2025 , for natural problems, a degree of n^{\delta} for a constant \delta>0 corresponds to runtime \exp(n^{\delta\pm o(1)}) . Following this heuristic argument, a degree of k=\omega(n) would provide an evidence of a gap. However, due to the fact that the k -local indistinguishability is expected to decay at most as 2^{-n} as discussed earlier, the argument of Chen et al. 2025 only applies to low-degree algorithms of degree k=O(n/\log(n)) and this alone is not sufficient to rule out a time complexity \omega(2^{n}) . To circumvent the aforementioned barrier on the k -local distinguishability, we choose the null case to correspond to measuring copies of a Haar random state (instead of the maximally mixed state). In this case, one can make the k -local indistinguishability arbitrarily small by making \mathcal{E} close to the Haar measure. For this new null hypothesis, one can similarly compile a hypothesis testing algorithm. If the circuit is from \mathcal{E} , then the circuit learning algorithm can learn the circuit and invert the next copy of the state to obtain the zero bitstring. On the other hand, if the circuit is Haar random, it should not be able to learn the circuit and invert the state to obtain the zero bitstring. However, computing \|\bar{D}-1\|_{D} is no longer easy due to the presence of a non-uniform measure. To simplify the analysis, we instead consider an alternative definition of distinguishing advantage, which we justify in Section III.1.4 : \displaystyle\mathrm{adv}^{\prime}=\underset{\|p\|_{U}=1}{\sup}\bigg|\mathbb{E}_{D}[p(x)]-\mathbb{E}_{D^{\prime}}[p(x)]\bigg|, (39) where U is the uniform distribution. Then, \displaystyle\mathrm{adv}^{\prime} \displaystyle=\left|\sum_{x}p^{*}(x)[D^{\prime}(x)-D(x)]\right|=\left|\langle p^{*},2^{mn}(D-D^{\prime})\rangle_{U}\right|. (40) The 2^{mn} factor arises from the fact that the measure U has value 1/2^{mn} for all x , since there are mn bits for m copies of states measured and n bits per measured state. Then, p^{*}=(D-D^{\prime})/\|D-D^{\prime}\|_{U} and \mathrm{adv}^{\prime}=2^{2mn}\|D-D^{\prime}\|_{U} . Similar to Chen et al. 2025 , we limit p\in\mathcal{V}^{\leq k} (polynomials of degree k ). Redefining the advantage to maximize only over k -degree polynomial gives \displaystyle p^{*}=\frac{D^{\leq k}-D^{\prime\leq k}}{\|D^{\leq k}-D^{\prime\leq k}\|_{U}}\qquad\mathrm{adv}^{\prime}=2^{2mn}\|D^{\leq k}-D^{\prime\leq k}\|_{U}. (41) Now, mirroring section 6.1 of Chen et al. 2025 , consider the Fourier expansion \displaystyle D^{\prime}(s)=\sum_{T\subseteq[mn]}\alpha_{T}\chi_{T}(s)\qquad D(s)=\sum_{T\subseteq[mn]}\beta_{T}\chi_{T}(s). (42) Then, using the fact that \chi_{T} forms an orthonormal basis, \displaystyle 2^{2mn}\|D^{\leq k}-D^{\prime\leq k}\|_{U} \displaystyle=2^{2mn}\sum_{x}\left(\sum_{\|T\|\leq k}\alpha_{T}\chi_{T}(s)-\sum_{\|T\|\leq k}\beta_{T}\chi_{T}(s)\right)^{2}=2^{2mn}\sum_{\|T\|\leq k}(\alpha_{T}-\beta_{T})^{2}. (43) Further, just as Eq. 5 of Ref. Chen et al. 2025 , \displaystyle\alpha_{T} \displaystyle=\mathbb{E}_{s}D^{\prime}(s)\chi_{T}(s)=2^{-mn}\mathbb{E}_{\rho,s[T]}2^{|T|}\mathrm{tr}\left(\underset{[mn]\setminus T}{\mathrm{tr}}\rho^{\otimes m}\bigotimes_{(i,r)\in T}|\phi_{s_{i,r}}\rangle\langle\phi_{s_{i,r}}|\right). (44) Similarly, \displaystyle\beta_{T}=2^{-mn}\mathbb{E}_{\rho\in\mathrm{Haar},s[T]}2^{|T|}\mathrm{tr}\left(\underset{[mn]\setminus T}{\mathrm{tr}}\rho^{\otimes m}\bigotimes_{(i,r)\in T}|\phi_{s_{i,r}}\rangle\langle\phi_{s_{i,r}}|\right). (45) Now, define the new k -local indistinguishability (NOT kLLR ) \displaystyle kLI^{\prime}=d_{\mathrm{tr}}\left(\underset{\rho\sim\mathcal{E}}{\mathbb{E}}\underset{[mn]\setminus T}{\mathrm{tr}}(\rho^{\otimes m}),\underset{\rho\sim\mathrm{Haar}}{\mathbb{E}}\underset{[mn]\setminus T}{\mathrm{tr}}(\rho^{\otimes m})\right)\leq\varepsilon, (46) we have (similar to the proof of Corollary 6.2 in B.1 of Chen et al. 2025 ) \displaystyle|\alpha_{T}-\beta_{T}|=2^{-mn}\big|\mathbb{E}_{s}2^{|T|}\zeta_{s}\big|\leq 2^{|T|-mn}\varepsilon (47) for some \zeta_{s}\in[-\varepsilon,\varepsilon] . Therefore, \displaystyle\mathrm{adv}^{\prime}=2^{2mn}\|D^{\leq k}-D^{\prime\leq k}\|_{U}\leq 2^{2|T|}\varepsilon^{2}k(mn)^{k} (48) similar to Proposition 6.3. While this looks very similar to the original Chen et al. 2025 , we have a new k -local distinguishability that can be reduced arbitrarily by making the circuit close to Haar random. Let \mathcal{E} form an \varepsilon_{D} approximate m -design. The reduced density operators are degree- m polynomials of \rho , i.e. f(\rho)=\underset{[mn]\setminus T}{\mathrm{tr}}(\rho^{\otimes m}) is a degree- m polynomial, so \displaystyle\left\|\underset{\rho\sim\mathcal{E}}{\mathbb{E}}\underset{[mn]\setminus T}{\mathrm{tr}}(\rho^{\otimes m})-\underset{\rho\sim\mathrm{Haar}}{\mathbb{E}}\underset{[mn]\setminus T}{\mathrm{tr}}(\rho^{\otimes m})\right\|_{\infty}=\left\|\underset{\rho\sim\mathcal{E}}{\mathbb{E}}f(\rho)-\underset{\rho\sim\mathrm{Haar}}{\mathbb{E}}(\rho)\right\|_{\infty}\leq\varepsilon_{D}. (49) Then, by the standard norm inequality between the trace norm and the operator norm that d_{\mathrm{tr}}(\cdot)\leq d\|\cdot\|_{\infty} where d is the dimensionality of the Hilbert space, we have kLI\leq\varepsilon_{D}2^{k} and \mathrm{adv}\leq\varepsilon_{D}^{2}2^{4k}k(mn)^{k} . Setting \varepsilon_{D}=2^{-\tilde{\Omega}(k\log(n))} gives \mathrm{adv}=o(1) and that weak detection is degree- k hard. As we discussed before, having \mathrm{adv}=o(1) is sufficient for the purpose of digital signatures, and we require that k=\omega(n) for the gap in the time complexity between verification and spoofing. Therefore, the circuit family has to form an 2^{-\tilde{\omega}(n\log(n))} -approximate \mathrm{poly}(n) -design. Since Chen et al. 2025 shows how to construct \varepsilon_{D} -approximate t -designs in depth O(nt\log^{7}(t)+\log(1/\varepsilon_D)) (Lemma 8.7), we can construct circuits of depth polynomial in n to satisfy the requirement. III.1.4 Justification of reformulated advantage We are concerned with the possibility that \mathrm{adv}^{\prime}\ll\mathrm{adv} . Fortunately, \displaystyle\mathrm{adv} \displaystyle=\|\bar{D}-1\|_{D}=\sum_{x}\frac{(D^{\prime}(x)-D(x))^{2}}{D(x)} (50) \displaystyle\mathrm{adv}^{\prime} \displaystyle=2^{2mn}\|D-D^{\prime}\|_{U}=2^{mn}\sum_{x}(D^{\prime}(x)-D(x))^{2}. (51) Each term’s contribution to the sum is changed by a factor of 2^{mn}D(x) . To bound the factor by which the distinguishing advantage is decreased, we simply need to lower bound D(x) . In our case, the distribution D is generated by non-adaptive shadow measurements over copies of a Haar random state. Consider a set of shadow measurement bases fixed ahead of time. The first output has the uniform distribution since the state is Haar random. The first measurement outcome tells us something about the actual state. Suppose all measurements are in the computational basis, this would double the probability of measuring this bitstring in the second round and uniformly decrease the probability of the rest bitstrings. For all subsequent rounds, the probability of measuring any bitstring is proportional to the number of occurrence of that bitstring in prior measurements. In the (i+1) st round, the probability of sampling a particular bitstring that never occurred before is 2^{-n}\times\left(1-\frac{i}{2^{n}}\right) . Overall, the lowest probability event is to sample a different bitstring each time with probability \displaystyle\prod_{i=0}^{m-1}2^{-n}\times\left(1-\frac{i}{2^{n}}\right), (52) which is negligibly close to 2^{-mn} for m=\poly(n) . For the actual shadow protocol, the above bound on the probability of any particular event is not applicable, but it is plausible that it should be similarly close to 2^{-mn} . If we were only interested in the distribution of classical variables which is the probabilities in the computational basis, measurement in the computational basis would be the optimal learning strategy. Further, the actual distribution we should examine is D^{\leq k}(x) , which should be even closer to the uniform distribution. III.2 Gap due to oracle-based learning hardness Another approach of making such an argument is by considering the family of learning algorithms that uses the same computational primitive as the verifier. The verifies uses the public shadows to perform a sort of fidelity estimation, or to perform an overlap against some projector. This primitive takes time T_{P} . We can now wonder how many calls to a similar primitive an adversarial learner has to make in order to learn the circuit. On one extreme, we can consider a brute force strategy where the adversary iterates through all possible circuits in the ensemble and performs fidelity estimation with respect to the public shadows. Here, the primitive is the same as verification, which means T_{P}=T_{V} . This strategy would correspond to T_{L}\sim|\mathcal{C}|T_{V} , where |\mathcal{C}| is the size of the ensemble and is typically exponential in the number of gates (nd) . However, an adversary can indeed use far more sophisticated algorithms than a brute-force search. An example of an algorithm that use oracle access to “fidelity-estimation”-like primitive for learning is variational learning where parameters are iteratively optimized against a loss-function, where each query of the loss-function involves fidelity estimation with respect to the target state. Two arguments – first from Statistical Query Learning and second from the difficulty of variational training – suggest that one needs exponentially many queries to such an oracle in order to learn a circuit “properly.” III.2.1 Statistical query learning argument In the statistical query (SQ) learning framework, one aims to learn some observable M on a distribution of states \mathcal{D} . One is provided with a correlational stastical query qCSQ(O,\tau) which takes in a bounded observable O with \|O\|\leq 1 and a tolerance \tau and returns a value in the range \mathbb{E}_{\rho\sim\mathcal{D}}[\mathrm{Tr}(O\rho)\mathrm{Tr}(M\rho)-\tau]\leq qCSQ(O,\tau)\leq\mathbb{E}_{\rho\sim\mathcal{D}}[\mathrm{Tr}(O\rho)\mathrm{Tr}(M\rho)+\tau] (53) The hardness of SQ learning is characterized by the query dimension of the hypothesis class \mathcal{H} which the target observable M belongs to. In particular, if the query dimension is d , SQ learning requires at least d(\tau^{2}-1)/2 queries to the oracle. In the case of learning random circuits M=\ket{C}\bra{C} , the hypothesis class \mathcal{H} spans the space of all quantum states, suggesting that d\sim 4^{n} . This can be seen by noting that a n -qubit quantum circuit of depth \log(n) can express all 4^{n} Pauli observables. Therefore, the number of oracle calls one needs is exponential in n . However, statistical query learning framework assumes adversarial noise on the query a consequence of which is that even simple circuits (i.e., consisting of single qubit gates) have exponential lower bounds. In the next section, we next explore a more realistic learning algorithm, that is not subject to the restriction of adversarial noise. III.2.2 Hardness of learning variational circuits In variational training, a parameterized circuit is optimized iteratively to optimize a loss function. Given target state \ket{C} , one can train a parameterized circuit \ket{D(\theta)} and tune the parameters, using some optimization method, to minimize the loss function, which in the case of state-learning is the infidelity with respect to the target state: \ell(\theta,C)=1-|\innerproduct{D(\theta)}{C}|^{2} (54) We consider an adversarial learner that is granted access to an oracle which computes such loss functions and their gradients (or higher derivatives). Such an oracle is at least as powerful as the “verification” oracle needed to verify signatures. Below, we argue that an adversary defined as such necessarily needs to make an exponential number of queries to such an oracle, suggesting that the ratio of “time for spoofing with a variational algorithm” to “time to verify signature” is an exponential function in n . Such an argument is made using a series of works that establish the trainability of variational circuits Anschuetz 2026 ; Anschuetz and Kiani 2022 ; Anschuetz 2025 . Omitting technical details, Anschuetz 2025 defines a variational circuit D(\theta) to be trainable when both the following properties are satisfied: 1. There is an absence of barren plateaus, and 2. There is an absence of poor local minima Expressive ansatzes, where the light-cone extends to \Omega(n) qubits, are known to exhibit barren plateaus, meaning that the gradients are exponentially small, requiring exponentially many measurements of the state \ket{D(\theta)} to even learn the direction of the gradient with respect to an ansatz parameter. However, in our conjecture, we allow for a powerful adversary that not only has oracle access to the loss function but also to its gradients. Therefore, we assume the adversary does not encounter barren plateau issues and the first part of the trainability definition is always satisfied. Instead, we focus only on the hardness that results from the non-convexity of the optimization landscape. Over the last decade, it has become apparent that variational quantum loss functions can be optimized efficiently only if they are heavily overparameterized . Since we can construct our verification protocol to reject circuits that have too many gates, we can ensure that the adversary has to perform an exponentially difficult computation to optimize an acceptable ansatz even if given oracle access to the gradients of the loss function. In other words, any circuits accepted by our verification protocol are not deep enough to avoid poor local minima in their training landscape and thus are not efficiently trainable. To be more precise, we restrict the adversary to only use ansatzes from our circuit ensemble, which is defined as follows. We divide n qubits to blocks, each of b qubits. The circuit is constructed by interleaving “intra-block” and “inter-block” layers of two-qubit gates. For each “intra-block”, we apply b/2 gates between arbitrary pairs within the same block. For each “inter-block” gates, we pair qubits between any two blocks and apply entangling gates in them. To make the learner circuit more powerful, we allow each of these gates to be SU(4) gates. In particular, we have d_{\mathrm{i}nner} intra-block layers for each of the d_{\mathrm{o}uter} inner-block layers. We denote this learner ensembles as \mathcal{D}(b,d_{\mathrm{i}nner},d_{\mathrm{o}uter}) . For convenience, we consider n to be a multiple of b . Let \ket{C} denote the target state. Let D_{d}(\theta) denote the learner circuit. The following lemma uses the definition of overparameterization given in Anschuetz 2025 applied to this circuit ansatz. Lemma 4 . The variational circuit D_{d}(\theta)\sim\mathcal{D}(b,d_{\mathrm{i}nner},d_{\mathrm{o}uter}) optimizing loss \ell(\theta,C) achieves overparameterization at depth d=d_{\mathrm{o}uter}\cdot d_{\mathrm{i}nner}=O(2^{n}/n) . Consequently, any circuit with d\ll 2^{n}/n exhibits exponentially-many poor local minima and therefore variational training starting from random angles succeeds with an exponentially low probability. This lemma is proven in three steps. (1) Show that the number of parameters p in D_{d}(\theta) is equal to 15(n/2)\cdot d_{\mathrm{i}nner}\cdot d_{\mathrm{o}uter} . (2) In order for a variational circuit to have good fidelity with \ket{C} , it should have at least p^{*}\geq 2^{n+1} parameters. (3) Therefore, a circuit from our ansatz needs depth d\geq\frac{2^{n+1}}{15n} in order for variational training with random starting angles to succeed with high probability. The crux of this proof comes from calculating the overparameterization ratio as defined in Anschuetz 2025 . In their work, the algebraic structure induced by the circuits is a Jordan algebra \mathcal{A} that admits decomposition \bigoplus_{i}\mathcal{A}_{i} . From here, \ell(\theta,C) is then understood on each subalgebra and hardness arises from the worst-case subalgebra. For our purposes, the Jordan algebra generated by the circuit ansatz \mathcal{C}_{n} is simply \mathcal{H}^{2^{n}}(\mathbb{C}) , the space of 2^{n}\times 2^{n} Hermitian matrices over \mathbb{C} with no additional decomposition structure. By Theorem 13 in Anschuetz 2025 , \ell(\theta,C) is well-approximated by a calculation over a random Wishart-distributed random matrix with 2r degrees of freedom, where r\coloneqq\frac{\|H_{1}\|_{*}^{2}}{\|H_{1}\|_{F}^{2}} (55) Here H_{1}=-\ket{C}\bra{C}-\lambda_{1}I=I-\ket{C}\bra{C} since \lambda_{1}=-1 is the minimum eigenvalue of H . Note that the loss function used in Anschuetz 2025 is simply \mathrm{Tr}[\rho U_{\theta}^{\dagger}HU_{\theta}] which matches ( 54 ) using \rho=\ket{0}\bra{0} , U_{\theta}=D_{d}(\theta) , and H_{1} . Proof. First we show that r=2^{n}-1 . Since H=\ket{C}\bra{C} is (minus-1) a rank-1 projector onto a normalized quantum state, we have spec(H)=(-1,0,\dots,0) and spec(H_{1})=(0,1,\cdots,1) . Simple calculations show that \displaystyle\|H_{1}\|_{*} \displaystyle=\mathrm{Tr}[H_{1}]=2^{n}-1\qquad\text{ and}\qquad\|H_{1}\|_{F}=\sqrt{\mathrm{Tr}[H_{1}]}=\sqrt{2^{n}-1}. (56) Therefore, r=2^{n}-1 . Let p be the number of parameters in D_{d}(\theta) . Then this circuit is overparameterized with respect to loss \ell(\theta,C) when p\geq 2r\gtrsim 2^{n+1} . Circuit D_{d}(\theta) has n/2 gates ( b/2 gates per each of the n/b blocks) per intra-block layers. Since there are d_{\mathrm{i}nner} intrablock layers, there are (n/2)\cdot d_{\mathrm{i}nner} random \text{SU}(4) gates per outer layer. There are d_{\mathrm{o}uter} outer layer and so we have (n/2)\cdot d_{\mathrm{i}nner}\cdot d_{\mathrm{o}uter} total parameterized gates. Each gate is a generic \text{SU}(4) which is parameterized by 4^{2}-1=15 angles. Thus, the total number of parameters p=15(n/2)\cdot d_{\mathrm{i}nner}\cdot d_{\mathrm{o}uter} . When d=d_{\mathrm{i}nner}\cdot d_{\mathrm{o}uter}\geq\frac{2^{n+2}}{15n} , we have p\geq 2r . ∎ Numerics We provide numerical evidence of the result established by the lemma above by showing that circuits only become trainable at an depth exponential in n . We consider two circuit ensembles: a) all-to-all ensemble with arbitrary \text{SU}(2) gates and b) circuits that make use of Iceberg code discussed in Section V (or described as “Circuit Ensemble” above). In the experiment we perform, we use a circuit ensemble that lends itself to the Iceberg code. The results can be seen in Fig. 10 . For both ensembles, we sample circuits that define the target state an adversary tries to learn. For each target circuit, we train ansatzes of varying depths (and therefore varying number of parameters) with the circuit structure being the same as the target. For the purposes of demonstration, we consider a circuit learned if the infidelity \epsilon falls below 0.1 . If the infidelity doesn’t fall below 0.1 in 500 training cycles, we consider training to have failed for that ansatz. For each depth, we train multiple ansatzes with different initializations. In Fig. 10 a , we plot the minimal depth required for average training infidelity to drop below \epsilon=0.1 within 500 epochs. We see that this “threshold” depth for training is exponential in n . Likewise, we also plot the number of oracle queries (training steps) necessary to train circuits from our ensemble to a target fidelity. As expected, the training is difficult at shallow depth, the regime the experiment was carried on. This suggests that, even in this stronger access model, variational training is only feasible in the vastly “improper” setting where the ansatz is much deeper than the circuit it is trying to mimic. Proper learning in variational training would thus require a large number of queries to the loss function. Figure 10: a , Depth required to train parameterized all-to-all circuits to fidelity >0.1 within 500 training steps and ten random initializations. At constant target fidelity, the required depth scales exponentially in n . b , Number of oracle queries required to train circuits from the ensemble used in the experiment to fidelity >0.1 and >0.05 for N=12 and N=16 respectively. For both sizes, ten random initializations were trained to 1000 training steps. The dashed vertical line represents the depth used in the experiment with N=32 . IV Shadow overlap protocols In Theorem 1 , we show that any shadow-overlap-type state certification protocol can be adapted into a digital signature scheme. While known schemes for shadows-based state certification all have sample complexity (size of shadows) that are nominally polynomial, for a practical application, it is desirable to make the exact, numeric size of shadows small, given the attributes of available quantum hardware. The goal of this section is to provide a shadow-based certification protocol which improves on known methods. We begin by briefly summarizing the relevant aspects of the protocol of Ref. Huang et al. 2024a , before introducing the improved protocol. Interested reader is encouraged to see Ref. Huang et al. 2024a for additional details. At a high level, the procedure for certifying that a “lab” state \rho is close to some target state \ket{\psi} of Protocol 2 of Huang et al. 2024a is as follows. To generate the shadows, we randomly select a subset of r qubits to measure the lab state in a random single-qubit Pauli basis and measure the rest in the computational basis. Using the shadows, compute the overlap with some operator dependent on the target quantum state to certify. Specifically, the procedure yields the so-called shadow overlap estimator \omega , which also satisfies \mathbb{E}[\omega]=\mathrm{tr}(L\rho) where L is some operator and \rho is the measured state. Given L , one can identify the certification procedure. The procedure for certifying quantum state fidelity in Huang et al. 2024a uses an L such that |\psi\rangle is an eigenvector with eigenvalue 1 and that the shadow overlap protocol over shadows generated from state \rho yields \mathrm{tr}(L\rho) in expectation (i.e., \mathrm{tr}(L\rho)=\mathbb{E}[\omega] , where \omega is the computed shadow overlap for a given trial). A step in establishing \text{tr}(L\rho)=\mathbb{E}[\omega] is that L can be written as the sum \displaystyle L=\frac{1}{N}\sum_{r\in[m]}\sum_{k=\{k_{1},\dots,k_{r}\}}\sum_{z_{k}\in\{0,1\}^{n-r}}|z_{k}\rangle\langle z_{k}|\otimes L_{z_{k}}, (57) where m is a positive integer that is at most n , k is a subset of r out of n qubits, z_{k} corresponds to a particular measurement outcome on the qubits measured in the fixed Z basis, L_{z_{k}} is efficiently computable, and N is the number of terms due to the summation over r and k which is given by \sum_{k=1}^{m}\binom{n}{k} . Specifically, Huang et al. 2020 uses the following definition of L_{z_{k}} : \displaystyle L_{z_{k}}=\sum_{\begin{subarray}{c}\ell_{1},\ell_{2}\in\{0,1\}^{r}\\ \mathrm{dist}(\ell_{1},\ell_{2})=r\end{subarray}}|\Psi_{z_{k}}^{\ell_{1},\ell_{2}}\rangle\langle\Psi_{z_{k}}^{\ell_{1},\ell_{2}}|\quad\text{with}\quad|\Psi_{z_{k}}^{\ell_{1},\ell_{2}}\rangle=\frac{\Psi(z_{k}^{(\ell_{1})})|\ell_{1}\rangle+\Psi(z_{k}^{(\ell_{2})})|\ell_{2}\rangle}{\sqrt{|\Psi(z_{k}^{(\ell_{1})})|^{2}+|\Psi(z_{k}^{(\ell_{2})})|^{2}}}, (58) where \Psi is a model providing query access to amplitudes of \ket{\psi} , z_{k}^{\ell} equals \ell on bits k_{1},\dots,k_{r} and equals z_{k} on the remaining n-r bits. To certify a state, T copies of the state \rho are measured according to the shadow overlap protocol and produce an estimator \hat{\omega} , which is given by the empirical average \frac{1}{T}\sum_{t=1}^{T}\omega_{t} . Ref. Huang et al. 2024a states that T=O(2^{2m}) samples are required such that |\hat{\omega}-\mathbb{E}[\omega]|\leq\varepsilon with high probability. The number of samples required (adjusting for an error in the use of Hoeffding’s inequality in Huang et al. 2020 ) is given by the following theorem: Theorem 5 (Theorem 5 of Huang et al. 2024a , corrected) . Using T\geq\frac{2^{4m-1}}{\varepsilon^{2}}\ln\frac{2}{\delta} samples of the state \rho , the empirical average \frac{1}{T}\sum_{t=1}^{T}\omega_{t} computed by Protocol 2 of Huang et al. 2024a is within \varepsilon additive distance from the shadow overlap \mathbb{E}[\omega] with probability at least 1-\delta . Proof. The proof is identical to Theorem 5 of Huang et al. 2020 except for the application of Hoeffding’s inequality. Instead of Eq. 30 of Huang et al. 2024a , the corrected quantity is \displaystyle\Pr\left[\left|\frac{1}{T}\sum_{t=1}^{T}\omega_{t}-\mathbb{E}[\omega]\right|>\varepsilon\right]\leq 2e^{-\frac{2T^{2}\varepsilon^{2}}{T(2^{2m-1}-(-2^{2m-1}))^{2}}}=2e^{-\frac{T\varepsilon^{2}}{2^{4m-1}}}\leq\delta. (59) Solving for T completes the proof. ∎ While this determines the sample complexity required to estimate the shadow overlap \omega precisely, it still remains to show the connection between \mathbb{E}[\omega] and the fidelity \langle\psi|\rho|\psi\rangle , which is necessary for certification. For any L , one can compute the so-called relaxation time \tau , which corresponds to the relaxation time of the Markov chain defined by L . Then, Theorem 4 of Huang et al. 2024a guarantees a equivalence between shadow overlap and fidelity. Namely, if \mathbb{E}[\omega]\geq 1-\varepsilon , then \langle\psi|\rho|\psi\rangle\geq 1-\tau\varepsilon (high shadow overlap implies high fidelity). Conversely, if \langle\psi|\rho|\psi\rangle\geq 1-\varepsilon , then \mathbb{E}[\omega]\geq 1-\varepsilon (high fidelity implies high shadow overlap). For a concrete experiment, it becomes important to determine \tau . The relaxation time \tau for m=1 is shown to be upper-bounded by n^{2} for Haar random states. For noisy quantum devices, however, even if \rho is prepared by executing the quantum circuit for |\psi\rangle , \langle\psi|\rho|\psi\rangle cannot be arbitrarily close to 1 due to the fidelity limitations of the device. Having \langle\psi|\rho|\psi\rangle\geq 1-\varepsilon , where \varepsilon is the infidelity, implies \mathbb{E}[\omega]\geq 1-\varepsilon , which certifies that \langle\psi|\rho|\psi\rangle\geq 1-\tau\varepsilon . This means the infidelity of certification grows by a factor of \tau . For \tau=O(n^{2}) , certification becomes impossible for low fidelity devices as the requirement \tau\epsilon\ll 1 implies \epsilon\ll\frac{1}{O(n^{2})} . Although empirical evidence in Fig. 11 a suggests \tau=O(n) for Haar-random states, this is still highly impractical for fidelities below 0.99 . Specifically, to see this issue, we can state the corrected shadow overlap protocol sample complexity for obtaining completeness and soundness of certification. Theorem 6 (Theorem 6 of Huang et al. 2024a , corrected) . Given any n -qubit hypothesis state |\psi\rangle with a relaxation time \tau\geq 1 , error \varepsilon>0 , failure probability \delta>0 , and \displaystyle T=2^{4m+3}\cdot\frac{\tau^{2}}{\varepsilon^{2}}\cdot\ln\frac{2}{\delta} (60) samples of an unknown n -qubit state \rho , with probability at least 1-\delta , Protocol IV.2 with shadow overlap threshold \omega_{\mathrm{threshold}}\equiv 1-\varepsilon^{\prime}=\frac{3\varepsilon}{4\tau} will correctly output Failed if the fidelity is low, i.e. \langle\psi|\rho|\psi\rangle<1-\varepsilon , and will correctly output Certified if the fidelity is high, i.e. \langle\psi|\rho|\psi\rangle\geq 1-\frac{\varepsilon}{2\tau} . Proof. The proof is identical to Theorem 6 of Huang et al. 2024a except we use Theorem 5 . Simply substituting \varepsilon\rightarrow\varepsilon/\tau-\varepsilon^{\prime}=\frac{\varepsilon}{4\tau} . ∎ IV.1 Improved random Pauli shadow overlap protocols One way of reducing the sample complexity (Eq. 60 ) is by reducing the relaxation time \tau . In order to do so, we make two observations. First, increasing the level m of the protocol increases the connectivity of the Markov chain. This is apparent since the supported edges are between bitstrings that differ in at most m bits. Second, as long as L_{z_{k}} is the outer product of normalized quantum states, any L of the form of Eq. 57 has a correspondence to a shadow overlap procedure, with L_{z_{k}} as the observable of interest. As a result, we define the following operator \displaystyle L=\binom{n}{m}^{-1}\times\sum_{k=\{k_{1},\dots,k_{m}\}}\sum_{z_{k}\in\{0,1\}^{n-m}}|z_{k}\rangle\langle z_{k}|\otimes L_{z_{k}},\qquad\text{with }\quad L_{z_{k}}=|\Psi_{z_{k}}\rangle\langle\Psi_{z_{k}}|\quad\text{and}\quad|\Psi_{z_{k}}\rangle=\frac{\sum_{\ell\in\{0,1\}^{m}}\Psi(z_{k}^{\ell})|\ell\rangle}{\sqrt{\sum_{\ell\in\{0,1\}^{m}}|\Psi(z_{k}^{\ell})|^{2}}}. (61) Now, we redefine the shadow overlap procedure with the new L_{z_{k}} . The same steps of Proposition 3 of Huang et al. 2024a yield \mathrm{tr}[L\rho]=\mathbb{E}[\omega] . We will prove later that L|\psi\rangle=|\psi\rangle . It is clear from definition that L is Hermitian. One also can define the Markov chain with transition matrix P=S^{-1/2}F^{\dagger}LFS^{1/2} , which is exactly the same as Proposition 3 of Huang et al. 2024a , which allows us to compute the relaxation time and bound the fidelity from the shadow overlap. Fig. 11 shows the relaxation of Haar random states and states prepared by the ansatz of our experimental quantum circuits using different definitions of the operator L . In particular, our experimental quantum circuit ansatz is as described in the main text, and we show the shadow overlap of those with two blocks and \lceil\log_{2}n\rceil layers. We observe in Fig. 11 a that for Protocol 2 of Huang et al. 2020 , increasing m does not reduce the relaxation time meaningfully beyond m=3 . Additionally, the slopes seem to be about the same for different values of m , indicating similar asymptotic scaling of \tau . On the other hand, Fig. 11 b shows that our protocol achieves a notably lower relaxation time. For m=4 , extrapolating to n=32 gives \tau\approx 8 . Note that the horizontal axis scaling is different from Fig. 11 a . The asymptotic scaling also improves with m . An overall trend is that increasing m or n decreases the variance in the relaxation time. We also show that the choice of the quantum circuits we make does not impact the average relaxation time very much, as is evidenced by Fig. 11 c , but it does increase the variance in the relaxation time. Figure 11: Relaxation time of the certification procedures. a , Relaxation time of Protocol 2 of Huang et al. 2024a for Haar random states. b , Relaxation time of our Protocol IV.1 for Haar random states. c , Relaxation time of our m=4 protocol for Haar random states and the state generated using the ansatz of our experimental quantum circuits with two blocks and \lceil\log_{2}n\rceil layers. Error bars show the standard deviation. Data points with n\leq 12 are averaged over 10 random instances, whereas each data point beyond that only consists of a single instance. To understand why this construction achieves a lower relaxation time, consider the extreme case of L=|\psi\rangle\langle\psi| . All eigenvectors other than |\psi\rangle have eigenvalue zero and the relaxation time is the smallest it can be, i.e. \tau=1 . The operator L defined in Huang et al. 2024a is not |\psi\rangle\langle\psi| even for m=n . This is due to the normalization factors of |\Psi_{z_{k}}^{\ell_{1},\ell_{2}}\rangle being the root of the sum of two probabilities always. On the other hand, for m=n , our L operator is exactly |\psi\rangle\langle\psi| . Additionally, this construction of L is more natural than the scheme in Huang et al. 2024a . Specifically, L_{z_{k}} is the collapsed state of the hypothesis state |\psi\rangle conditioned on the qubits not in k being measured to z_{k} . Although L is a sum of these collapsed states, it is not |\psi\rangle\langle\psi| even up to normalization. It may be tempting to interpret L as |\psi\rangle going through a random measurement channel up to some normalization, but even this is not correct since each term corresponding to z_{k} have equal weight instead of proportional to the measurement probability. In fact, if we use the density operator of |\psi\rangle going through a random measurement channel, it would not have |\psi\rangle as an eigenvector in general. We now formally describe the protocol in Protocol IV.1 and prove its correctness. {protocol_framed} [Improved level- m shadow overlap] Input: • T samples of an unknown state \rho . • A model \Psi that gives query access to the amplitudes of |\psi\rangle . • A level m\in[n] . • Error 0\leq\varepsilon^{\prime}<1 , or equivalently shadow overlap threshold \omega_{\mathrm{threshold}}\equiv 1-\varepsilon^{\prime} . Procedure: 1. Uniformly choose m random qubits denoted by k=\{k_{1},\dots,k_{m}\} . 2. Perform single-qubit Z -basis measurements on all but qubits k_{1},\dots,k_{m} of \rho . Denote the measurement outcomes collectively by z_{k}\in\{0,1\}^{n-m} . 3. For each qubit k_{1},\dots,k_{m} , choose an X,Y,Z -basis measurement uniformly at random and measure it. Denote the post-measurement state of these qubits by |s_{1}\rangle,\dots,|s_{m}\rangle . Compute the classical shadow \displaystyle\sigma=(3|s_{1}\rangle\langle s_{1}|-\mathbb{I})\otimes\cdots\otimes(3|s_{m}\rangle\langle s_{m}|-\mathbb{I}). (62) 4. Query the model \Psi for all choices of m -bit strings \ell to obtain the normalized state \displaystyle|\Psi_{z_{k}}\rangle=\frac{\sum_{\ell\in\{0,1\}^{m}}\Psi(z_{k}^{\ell})|\ell\rangle}{\sqrt{\sum_{\ell\in\{0,1\}^{m}}|\Psi(z_{k}^{\ell})|^{2}}}, (63) where z_{k}^{\ell} equals \ell on bits k_{1},\dots,k_{m} and equals z_{k} on the remaining n-m bits. 5. Compute the overlap \displaystyle\omega=\mathrm{tr}(L_{z_{k}}\sigma)\quad\text{with}\quad L_{z_{k}}=|\Psi_{z_{k}}\rangle\langle\Psi_{z_{k}}|. (64) 6. Repeat steps 1 to 5 for T times to obtain overlaps \omega_{1},\dots,\omega_{T} . Report the estimated shadow overlap \displaystyle\hat{\omega}=\frac{1}{T}\sum_{t=1}^{T}\omega_{t}. (65) 7. If the estimated shadow overlap \hat{\omega}\geq 1-\varepsilon^{\prime} , output Certified . Otherwise, output Failed . Lemma 5 . Consider a quantum state \psi \displaystyle|\psi\rangle=\Psi(z)|z\rangle. (66) Define an operator L \displaystyle L=\binom{n}{m}^{-1}\times\sum_{k=\{k_{1},\dots,k_{m}\}}\sum_{z_{k}\in\{0,1\}^{n-m}}|z_{k}\rangle\langle z_{k}|\otimes L_{z_{k}}, (67) where \displaystyle L_{z_{k}}=|\Psi_{z_{k}}\rangle\langle\Psi_{z_{k}}|\quad\text{with}\quad|\Psi_{z_{k}}\rangle=\frac{\sum_{\ell\in\{0,1\}^{m}}\Psi(z_{k}^{\ell})|\ell\rangle}{\sqrt{\sum_{\ell\in\{0,1\}^{m}}|\Psi(z_{k}^{\ell})|^{2}}}, (68) where z_{k}^{\ell} equals \ell on bits k_{1},\dots,k_{m} and equals z_{k} on the remaining n-m bits. We have \displaystyle L|\psi\rangle=|\psi\rangle. (69) Proof. We first observe that given m qubits specified by vector k , \displaystyle\langle z_{k}|\psi\rangle=\langle z_{k}|\sum_{z}\Psi(z)|z\rangle=\langle z_{k}|\sum_{z_{k}^{\prime}}\sum_{\ell\in\{0,1\}^{m}}\Psi(z_{k}^{\prime\ell})|z_{k}^{\prime}\rangle\otimes|\ell\rangle_{k}=\sum_{\ell\in\{0,1\}^{m}}\Psi(z_{k}^{\ell})|\ell\rangle_{k}, (70) which means that the post selected state is \displaystyle\frac{\langle z_{k}|\psi\rangle}{\sqrt{\langle\psi|z_{k}\rangle\langle z_{k}|\psi\rangle}}=|\Psi_{z_{k}}\rangle\quad (71) for |\Psi_{z_{k}}\rangle and L_{z_{k}} defined in the lemma. Additionally, \displaystyle|\psi\rangle=\mathbb{I}|\psi\rangle=\sum_{z_{k}}|z_{k}\rangle\langle z_{k}|\psi\rangle=\sum_{z_{k}}|z_{k}\rangle\otimes\sum_{\ell\in\{0,1\}^{m}}\Psi(z_{k}^{\ell})|\ell\rangle_{k}=\sum_{z_{k}}\sqrt{p(z_{k})}|z_{k}\rangle\otimes|\Psi_{z_{k}}\rangle, (72) where p(z_{k})=\sum_{\ell\in\{0,1\}^{m}}|\Psi(z_{k}^{\ell})|^{2} . \displaystyle\binom{n}{m}L|\psi\rangle= \displaystyle\sum_{k}\sum_{z_{k}}|z_{k}\rangle\langle z_{k}|\otimes L_{z_{k}}|\psi\rangle (73) \displaystyle= \displaystyle\sum_{k}\sum_{z_{k}}\left(|z_{k}\rangle\otimes|\Psi_{z_{k}}\rangle_{k}\right)\left(\langle z_{k}|\otimes\langle\Psi_{z_{k}}|_{k}\right)\sum_{z_{k}^{\prime}}\sqrt{p(z_{k}^{\prime})}|z_{k}^{\prime}\rangle\otimes|\Psi_{z_{k}^{\prime}}\rangle (74) \displaystyle= \displaystyle\sum_{k}\sum_{z_{k}}\sqrt{p(z_{k})}|z_{k}\rangle\otimes|\Psi_{z_{k}}\rangle_{k}=\sum_{k}|\psi\rangle=\binom{n}{m}|\psi\rangle. (75) ∎ Lemma 6 . For \omega of Protocol IV.1 , we have \displaystyle\mathrm{tr}(L\rho)=\mathbb{E}[\omega]. (76) Proof. We follow the same idea as Proposition 3 of Huang et al. 2024a . \displaystyle\mathrm{tr}[L\rho] \displaystyle=\binom{n}{m}^{-1}\times\sum_{k=\{k_{1},\dots,k_{m}\}}\sum_{z_{k}\in\{0,1\}^{n-m}}\mathrm{tr}\left(\langle z_{k}|\rho|z_{k}\rangle\right)\cdot\mathrm{tr}\left(L_{z_{k}}\cdot\frac{\langle z_{k}|\rho|z_{k}\rangle}{\mathrm{tr}(\langle z_{k}|\rho|z_{k}\rangle)}\right)=\underset{k,z_{k}}{\mathbb{E}}\mathrm{tr}\left(L_{z_{k}}\cdot\frac{\langle z_{k}|\rho|z_{k}\rangle}{\mathrm{tr}(\langle z_{k}|\rho|z_{k}\rangle)}\right). (77) We note that converting the sum into expectation is valid just like in Huang et al. 2020 , although the sampling process is different. In Huang et al. 2020 , the procedure samples r , followed by sampling k=\{k_{1},\dots,k_{r}\} , and finally measuring z_{k} . Here, we directly sample k=\{k_{1},\dots,k_{m}\} and then measure z_{k} . Following the rest of the steps identically as Huang et al. 2024a completes the proof. ∎ Theorem 7 . Let \lambda_{1}=1-\frac{1}{\tau} be the second largest eigenvalue of the transition matrix P defined as P=S^{-1/2}F^{\dagger}LFS^{1/2} for state |\psi\rangle , where L is as defined in Lemma 5 . The shadow overlap satisfies the following. If \mathbb{E}[\omega]\geq 1-\varepsilon , then \langle\psi|\rho|\psi\rangle\geq 1-\tau\varepsilon . If \langle\psi|\rho|\psi\rangle\geq 1-\varepsilon , then \mathbb{E}[\omega]\geq 1-\varepsilon for \omega as defined in Protocol IV.1 . Proof. The proof is identical to Theorem 4 of Huang et al. 2024a . ∎ Theorem 8 . Using T=2^{2m+1}\cdot\frac{1}{\varepsilon^{2}}\cdot\ln(\frac{2}{\delta}) samples of the state \rho , the empirical average \frac{1}{T}\sum_{t=1}^{T}\omega_{t} computed by Protocol IV.1 is within \varepsilon additive distance from the shadow overlap \mathbb{E}[\omega] with probability at least 1-\delta . Proof. Since L_{z_{k}} is the outer product of one normalized vector, \|L_{z_{k}}\|_{1}=1 . Following the rest of proof identically as Theorem 5 while noting the difference in \|L_{z_{k}}\|_{1}=1 instead of \|L_{z_{k}}\|_{1}\leq 2^{m-1} completes the proof. ∎ To reduce the relaxation time \tau , we want m to be as high as possible. However, the sample complexity required so that the estimator of the shadow overlap is close to the expectation value is O(2^{2m}) as stated in Theorem 8 . Nevertheless, compared the protocol in Huang et al. 2024a where the sample complexity is proportional to 2^{4m-1} , we need quadratically fewer samples in m . IV.2 Random Clifford shadow overlap protocols Nevertheless, for large m , even 2^{2m} samples can be an obstacle in practice. Fortunately, the shadow overlap variance bound can be notably improved if the shadows are obtained using random Clifford measurements. For any observable O and set \hat{o}=\mathrm{tr}(O\hat{\rho}) , where \hat{\rho} is a classical shadow, we have \displaystyle\mathrm{Var}[\hat{o}]\leq\left\|O-\frac{\mathrm{tr}(O)}{2^{n}}\mathbb{I}\right\|^{2}_{\mathrm{shadow}}=\|O_{0}\|^{2}_{\mathrm{shadow}} (78) from Lemma 1 of Huang et al. 2020 , where the second equality serves as a definition for O_{0} which is a traceless operator in \mathbb{H}_{2^{n}} . For classical shadows obtained by random Clifford measurements, we have \displaystyle\|O_{0}\|_{\mathrm{shadow}}^{2}\leq 3\mathrm{tr}(O^{2}) (79) by Proposition 1 of Huang et al. 2020 . Since our operator L_{z_{k}} is an outer product of a normalized vector, \displaystyle\mathrm{Var}[\omega_{z_{k}}]\leq\left\|L_{z_{k}}-\frac{\mathrm{tr}(L_{z_{k}})}{2^{n}}\mathbb{I}\right\|_{\mathrm{shadow}}\leq 3, (80) where \omega_{z_{k}} is the shadow overlap for the measurement outcome z_{k} on the n-m qubits other than those specified by set k . It should be noted that the above is the variance of \omega_{z_{k}} , not \omega . Each \omega_{z_{k}} could have variation in the expectation value between 0 and 1 . This is because \displaystyle\mathbb{E}[\omega_{z_{k}}]=\underset{\mathrm{shadows}\penalty\ \sigma}{\mathbb{E}}[\mathrm{tr}(L_{z_{k}}\sigma)]=\mathrm{tr}\left(L_{z_{k}}\cdot\frac{\langle z_{k}|\rho|z_{k}\rangle}{\mathrm{tr}(\langle z_{k}|\rho|z_{k}\rangle)}\right), (81) where \mathbb{E}_{\mathrm{shadow}s\penalty\ \sigma}[\sigma]=\frac{\langle z_{k}|\rho|z_{k}\rangle}{\mathrm{tr}(\langle z_{k}|\rho|z_{k}\rangle)} is a normalized state as discussed in Huang et al. 2020 and Appendix B of Huang et al. 2024a . This is because shadows of a state average to the unknown state by construction. The overall variance of \omega therefore is upper bounded by \mathrm{Var}[\omega]\leq 3.25 . To see this, consider the contribution to variance due to \omega_{z_{k}} where \mathbb{E}[\omega]-\mathbb{E}[\omega_{z_{k}}]=\delta_{z_{k}} . Then, \displaystyle\mathbb{E}\left[(\omega_{z_{k}}-\mathbb{E}\left[\omega\right])^{2}\right] \displaystyle=\mathbb{E}\left[(\omega_{z_{k}}-\mathbb{E}\left[\omega_{k_{z}}\right]+\delta_{z_{k}})^{2}\right] (82) \displaystyle=\mathbb{E}\left[(\omega_{z_{k}}-\mathbb{E}\left[\omega_{z_{k}}\right])^{2}+2(\omega_{z_{k}}-\mathbb{E}\left[\omega_{z_{k}}\right])+\delta_{z_{k}}^{2}\right] (83) \displaystyle=\mathrm{Var}\left[\omega_{z_{k}}\right]+\delta_{z_{k}}^{2}. (84) Note that we have the constraint that \sum_{z_{k}}p_{z_{k}}\cdot\delta_{z_{k}}=0 since \sum_{z_{k}}p_{z_{k}}\cdot\mathbb{E}[\omega_{z_{k}}]=\mathbb{E}[\omega] , where p_{z_{k}} is the probability of selecting m random qubits denoted by k and measuring the rest of the n-m qubits output bitstring z_{k} . Further, we have \delta_{z_{k}}\in[-\mathbb{E}[\omega],1-\mathbb{E}[\omega]] . It is easy to see that the maximum possible value of \sum_{z_{k}}p_{z_{k}}\cdot\delta_{z_{k}}^{2}\leq-\mathbb{E}[\omega]\cdot(1-\mathbb{E}[\omega])\leq 0.25 , where the equality is satisfied by a distribution where all the probability mass concentrates on the boundary. Therefore, \displaystyle\mathrm{Var}[\omega] \displaystyle=\sum_{z_{k}}p_{z_{k}}\cdot\mathbb{E}\left[(\omega_{z_{k}}-\mathbb{E}\left[\omega\right])^{2}\right]\leq\sum_{z_{k}}p_{z_{k}}\cdot(\mathrm{Var}\left[\omega_{z_{k}}\right]+\delta_{z_{k}}^{2})\leq 3+\sum_{z_{k}}p_{z_{k}}\cdot\delta_{z_{k}}^{2}\leq 3.25. (85) {protocol_framed} [Improved level- m shadow overlap with random Cliffords] Input: Same as Protocol IV.1 . Procedure: All steps are the same as Protocol IV.1 except step 3, which we describe here. For qubits k_{1},\dots,k_{m} , generate a circuit U from the m qubit Clifford group \mathrm{Cl}(2^{m}) uniformly at random and apply it to the m qubits. Then, perform computational basis measurement and record the resulting m -bit string b . Compute the classical shadow \displaystyle\sigma=(2^{m}+1)U^{\dagger}|b\rangle\langle b|U-\mathbb{I}. (86) Lemma 7 . For \omega of Protocol IV.2 , we have \displaystyle\mathrm{tr}(L\rho)=\mathbb{E}[\omega]. (87) Proof. The proof is identical to Lemma 6 . Specifically, the difference between the two proofs only occurs during the step of \displaystyle\frac{\langle z_{k}|\rho|z_{k}\rangle}{\mathrm{tr}(\langle z_{k}|\rho|z_{k}\rangle)}=\underset{\mathrm{shadow}s\penalty\ \sigma}{\mathbb{E}}[\sigma]. (88) In Protocol IV.1 , \sigma is a shadow computed from random Pauli measurements according to Eq. 62 , and the expectation is over random Pauli basis and measurement outcomes. In Protocol IV.2 , \sigma is a shadow computed from random Clifford measurements according to Eq. 86 , and the expectation is over random Clifford circuits and measurement outcomes. ∎ Theorem 9 . Theorem 7 also holds for \omega as defined in Protocol IV.2 . Proof. The proof is identical to Theorem 4 of Huang et al. 2024a . ∎ Theorem 10 . Using T=(\frac{6.5}{\varepsilon^{2}}+\frac{2}{3\varepsilon}\cdot 2^{m})\cdot\ln\frac{2}{\delta} samples of the state \rho , the empirical average \frac{1}{T}\sum_{t=1}^{T}\omega_{t} computed by Protocol IV.2 is within \varepsilon additive distance from the shadow overlap \mathbb{E}[\omega] with probability at least 1-\delta . Proof. We first bound the individual values in the sum. \displaystyle\mathrm{tr}(L_{z_{k}}\sigma) \displaystyle=\mathrm{tr}\left\{|\Psi_{z_{k}}\rangle\langle\Psi_{z_{k}}|\left[(2^{m}+1)U^{\dagger}|b\rangle\langle b|U-\mathbb{I}\right]\right\} (89) \displaystyle=(2^{m}+1)\cdot|\langle b|U|\Psi_{z_{k}}\rangle|^{2}-1. (90) Therefore, -1\leq\mathrm{tr}(L_{z_{k}}\sigma)\leq 2^{m} . Further, we know \mathrm{Var}[\omega]\leq 3.25 . By Bernstein’s inequality, \displaystyle\Pr\left[\left|\frac{1}{T}\sum_{t=1}^{T}\omega_{t}-\mathbb{E}[\omega]\right|>\varepsilon\right]\leq 2e^{-\frac{T\varepsilon^{2}}{2\times 3.25+\frac{2}{3}\times 2^{m}\varepsilon}}\leq\delta. (91) Solving for T completes the proof. ∎ Theorem 11 . Given any n -qubit hypothesis state |\psi\rangle with a relaxation time \tau\geq 1 , error \varepsilon>0 , failure probability \delta>0 , and \displaystyle T=\left(\frac{104\tau^{2}}{\varepsilon^{2}}+\frac{8\tau}{3\varepsilon}\cdot 2^{m}\right)\cdot\ln\frac{2}{\delta} (92) samples of an unknown n -qubit state \rho , with probability at least 1-\delta , Protocol IV.2 with shadow overlap threshold \omega_{\mathrm{threshold}}\equiv 1-\varepsilon^{\prime}=\frac{3\varepsilon}{4\tau} will correctly output Failed if the fidelity is low, i.e. \langle\psi|\rho|\psi\rangle<1-\varepsilon , and will correctly output Certified if the fidelity is high, i.e. \langle\psi|\rho|\psi\rangle\geq 1-\frac{\varepsilon}{2\tau} . Proof. The proof is identical to Theorem 6 of Huang et al. 2024a except we use Theorem 10 . Simply substituting \varepsilon\rightarrow\varepsilon/\tau-\varepsilon^{\prime}=\frac{\varepsilon}{4\tau} of Theorem 5 of Huang et al. 2020 or Theorem 10 of this work gives the sample complexity of Theorem 6 of Huang et al. 2024a or this theorem, respectively. ∎ We note that there is a substantial improvement in the sample complexity compared to Theorem 8 for the random Pauli shadow overlap protocol. First, there is an apparent quadratic improvement from 2^{2m} to 2^{m} . Moreover, the exponential factor in m is additionally improved to proportional to \frac{\tau}{\varepsilon} instead of (\frac{\tau}{\varepsilon})^{2} . The term proportional to (\frac{\tau}{\varepsilon})^{2} only has a constant factor independent of m . There is also a substantial improvement in sample complexity compared to Theorem 6 for the original shadow overlap protocol of Huang et al. 2024a , with a quartic improvement from 2^{4m} to 2^{m} . The exponential dependence on m can be further removed by using the median of means estimator, which requires \frac{64\mathrm{Var}\ln(1/\delta)}{\varepsilon^{2}} samples to estimate the mean of a random variance with error at most \varepsilon and failure probability at most \delta . This is exactly as discussed in Huang et al. 2020 , and the sample complexity only depends on the variance. The disadvantage of the approach is that is has a large constant factor. Specifically, substituting \varepsilon\rightarrow\frac{\varepsilon}{4\tau} and \mathrm{Var}=3.25 yields a sample complexity of 3{,}328\cdot\frac{\tau^{2}}{\varepsilon^{2}}\cdot\ln\frac{1}{\delta} . The advantage of the median of means estimator would only be apparent for large m . Under the median of means estimator scheme, the special case of m=n becomes exactly the random Clifford classical shadow approach in Huang et al. 2020 for estimating the fidelity. This makes apparent the fact that our protocol is a unification of the direct classical shadow approach of Huang et al. 2020 and the shadow overlap approach of Huang et al. 2024a for certifying the quantum state fidelity. On the one extreme, the direct classical shadow approach using random Clifford circuits is sample efficient in that the sample complexity does not increase with n , and states fidelities can be estimated in an unbiased manner since the relaxation time \tau is 1 . One can replace random Cliffords with random single-qubit Pauli measurements and the estimator is unbiased since the relaxation time is also 1, but the sample complexity is exponential in n . On the other extreme, the shadow overlap approach that measures one random qubit in a random Pauli basis achieves low sample complexity that is independent of n , but the relaxation time \tau is large and low fidelity states cannot be Certified . Our work bridges the gap by introducing a family of protocols that connect the two extremes. We can go from the extreme of large relaxation time to the minimum relaxation time by increasing the level m of the protocol. Additionally, the sample complexity is O(2^{2m}) for the random Pauli protocol that preserves the desirable property that the measurement is easy to implement. For the random Clifford protocol, the sample complexity is O(2^{m}) or independent of m for the mean estimator or the median of means estimator, respectively. The complexity of implementing the measurement, which is O(m^{2}) since implementing a random Clifford circuit requires quadratically many gates, can be controlled by keeping m moderate. Although Huang et al. 2020 also introduces a family of protocols parameterized by the level m , the choice of operator L does not lead to a correspondence with the direct random Clifford classical shadow approach of Huang et al. 2020 even when m=n , and the relaxation time remains large as m increases. Further, the sample complexity is O(2^{4m}) , which prohibits practical use for large m . IV.3 Certifying the state in our experiment The sample complexity used in Theorem 11 is for both completeness and soundness. However, once the experimental results on the shadow overlap protocol is collected, one can carry out a hypothesis test to see if the lab state has fidelity at least 1-\varepsilon and not worry about the completeness side. This motivates the following corollary. Corollary 3 . If \varepsilon\geq\tau\varepsilon^{\prime} and the number of shadows collected by Protocol IV.2 is T\geq(\frac{6.5}{(\varepsilon/\tau-\varepsilon^{\prime})^{2}}+\frac{2}{3\times(\varepsilon/\tau-\varepsilon^{\prime})}\cdot 2^{m})\cdot\ln\frac{1}{\delta} , then either the protocol outputs Failed with probability at least 1-\delta , or \langle\psi|\rho|\psi\rangle\geq 1-\varepsilon . Proof. If \langle\psi|\rho|\psi\rangle<1-\varepsilon , then \mathbb{E}[\omega]<1-\varepsilon/\tau . To pass the protocol, we need \hat{\omega}-\mathbb{E}[\omega]>\varepsilon/\tau-\varepsilon^{\prime} . From the proof of Theorem 10 , switching from two-sided to one-sided Bernstein’s inequality yields \displaystyle\Pr\left[\frac{1}{T}\sum_{t=1}^{T}\omega_{t}-\mathbb{E}[\omega]>\varepsilon\right]\leq e^{-\frac{T\varepsilon^{2}}{2\times 3.25+\frac{2}{3}\times 2^{m}\varepsilon}}. (93) Then, substituting \varepsilon in the Eq. 93 with \varepsilon/\tau-\varepsilon^{\prime} shows that the protocol must output Failed with probability at least 1-\delta . ∎ For our experiment, we are not in the ideal perfect honest fidelity case, so we need Lemma 1 to bound the infidelity of the adversary state relative to the laboratory state. Assume that the adversary can prepare a state \lvert\psi_{\mathrm{adv}}\rangle with fidelity |\langle\psi_{\mathrm{adv}}|\psi_{\mathrm{hon}}\rangle|^{2}\leq 1-\varepsilon_{\mathrm{CNL}}=0.01 . Further, we have empirically estimated that the honest lab state infidelity is at least \varepsilon_{\mathrm{hon}}\leq 0.11 , Lemma 1 implies that the adversary state fidelity to the lab state is \displaystyle|\langle 0|C^{\prime\dagger}\sigma_{\mathrm{lab}}C^{\prime}|0\rangle|^{2}\leq 1-(\varepsilon_{\mathrm{CNL}}-\varepsilon_{\mathrm{hon}})+\varepsilon_{\mathrm{hon}}\frac{1}{2^{n}}=0.12 (94) under depolarizing noise. Therefore, we set \varepsilon=1-0.12=0.88 . The shadow overlap test threshold is \omega_{\mathrm{threshold}}=1-\varepsilon^{\prime}=0.91 , which means \varepsilon^{\prime}=0.09 . Finally, the probability (risk) that a given adversary circuit exceeds the shadow overlap threshold is \delta . For this set of parameters, one can achieve \delta=0.36 at T=17{,}316 samples. The above corollary cannot guarantee that the state is certified with good security in our particular experiment since \delta is very large. As a result, we use the following result of Zhang et al. Zhang et al. 2026 to obtain a tighter bound, which allows us to go to as low as \delta=0.15 . Ref. Zhang et al. 2026 presents an efficient method to estimate bounds on the sum of conditional means of data random variables X_{1},X_{2},\dotsc during unseen trials by spot-checking a few trials. This can be mathematically phrased as having a sequence of binary (spot-checking) random variables Y_{1},Y_{2},\dotsc that determine whether (or not) we have access to the value of X_{i} at a given trial i with probability p (or 1-p ). Then, using the observed values of X_{i} , Zhang et al. Zhang et al. 2026 give a protocol to estimate bounds on the sum S of conditional means of the data random variables for the unseen trials, which satisfies the following theoretical guarantee. Theorem 12 . The procedure described in Ref. Zhang et al. 2026 takes as input the observed values of data random variables \bm{X}=\{X_{i}\}_{i} , spot-checking random variables \bm{Y}=\{Y_{i}\}_{i} , spot-checking probability p , optional calibration trials \bm{X}_{c} , lower and upper bounds x_{\min}\leq X_{i}\leq x_{\max} for all i , a confidence parameter \delta , and outputs a lower bound b(\delta,x_{\min},x_{\max},\bm{X}_{c},\bm{X},\bm{Y}) on the sum S of conditional means of unobserved trials such that \displaystyle\underset{\bm{X}_{c},\bm{X},\bm{Y}}{\Pr}\left[S0.89 . Feeding our experimental data into the function b with \delta=0.15 exceeds this threshold. V Quantum error detection The practical execution of quantum algorithms on current hardware is limited by noise. The conventional approach is quantum error correction (QEC), which encodes logical information in more physical qubits and performs syndrome extraction to detect and correct errors. However, QEC typically incurs substantial overhead in qubit count and circuit depth, making it difficult to implement on near-term devices. As an alternative, quantum error detection (QED) codes have emerged as a promising near-term strategy He et al. 202 ; Jin et al. 2025 ; Chung et al. 2025 ; Self et al. 2024 . Rather than correcting errors, QED codes identify and discard erroneous outcomes Steane 1996 . V.1 Iceberg code The Iceberg code is a stabilizer-based quantum error detection code that encodes k logical qubits into n=k+2 physical qubits. Its stabilizer group \mathcal{S} is generated by the X and Z stabilizers S_{X}=\bigotimes_{i=1}^{n}X_{i} and S_{Z}=\bigotimes_{i=1}^{n}Z_{i} . The code space is defined as the joint +1 eigenspace of these stabilizers: \mathcal{H}_{\mathcal{S}}=\left\{\ket{\psi}\in(\mathbb{C}^{2})^{\otimes n}:S_{X}\ket{\psi}=\ket{\psi},\ S_{Z}\ket{\psi}=\ket{\psi}\right\}. (99) Logical single and two qubit rotation for the Iceberg code are \displaystyle\overline{X}_{i}(\theta) \displaystyle=X_{t}X_{i}(\theta);\quad\overline{X}_{i}\overline{X}_{j}(\theta)=X_{i}X_{j}(\theta) \displaystyle\overline{Z}_{i}(\theta) \displaystyle=Z_{b}Z_{i}(\theta);\quad\overline{Z}_{i}\overline{Z}_{j}(\theta)=Z_{i}Z_{j}(\theta), (100) where for convenience we label 1 -st and k+2 -nd qubits to be top t and bottom b respectively (see Fig. 12 a ). The logical Hadamard operator on all k logical qubits is \prod_{i=1}^{k}\overline{H_{i}}=\text{SWAP}_{t,b}\prod_{i=1}^{n}H_{i}. (101) A generic encoding circuit for the Iceberg code encoding an arbitrary k -qubit state \ket{\psi} is given in Fig. 12 a . Fig. 12 b is the fault-tolerant encoding circuit for the logical state \ket{+}^{\otimes k} with a single additional ancilla qubit. Figure 12: Encoder circuits for Iceberg code. a , is the circuit that encodes an arbitrary k -qubit physical state \ket{\psi} to the logical state \ket{\overline{\psi}} which requires in total of 2k+1 physical CNOT gates. b , is the fault-tolerant encoding circuit for the state logical state \ket{+}^{\otimes k} using a single ancilla qubit. This circuit requires a total of k+3 CNOT gates and two-qubit depth of \lceil k/2\rceil+3 . V.2 Gauge fixing the Iceberg code For the n -qubit Pauli group \mathcal{P}_{n} , a stabilizer code is specified by an abelian subgroup \mathcal{S}\subset\mathcal{P}_{n} generated by independent, commuting Pauli operators with -I\notin\mathcal{S} . The code space is the joint +1 eigenspace \mathcal{H}_{\mathcal{S}}=\left\{\,\ket{\psi}\in(\mathbb{C}^{2})^{\otimes n}:S\ket{\psi}=\ket{\psi}\ \forall S\in\mathcal{S}\,\right\}. (102) Let \mathcal{C}(\mathcal{S})=\left\{P\in\mathcal{P}_{n}:[P,S]=0\ \forall S\in\mathcal{S}\right\} denote the centralizer of \mathcal{S} , i.e. the elements of \mathcal{P}_{n} that commute with all the stabilizers of the code. V.2.1 Gauge fixing Given a stabilizer code (\mathcal{S},\mathcal{H}_{\mathcal{S}}) and a set of commuting, independent Pauli operators \mathcal{G}=\langle g_{1},\dots,g_{r}\rangle with g_{i}\in\mathcal{C}(\mathcal{S})/\mathcal{S}\text{ and }\commutator{g_i}{g_j}=0, the gauge-fixed stabilizer group is \mathcal{S}^{\prime}=\langle\mathcal{S},\mathcal{G}\rangle, (103) where \langle\cdot\rangle denotes the group generated by all finite products of elements from the set. This defines a subcode with code space \mathcal{H}_{\mathcal{S}^{\prime}}\subseteq\mathcal{H}_{\mathcal{S}} and k-r logical qubits. Effectively, gauge-fixing projects the code space onto the joint +1 eigenspace of \mathcal{G} inside \mathcal{H}_{\mathcal{S}} : \Pi_{\mathcal{G}}=\prod_{i=1}^{r}\frac{I+g_{i}}{2},\qquad\mathcal{H}_{\mathcal{S}^{\prime}}=\Pi_{\mathcal{G}}\mathcal{H}_{\mathcal{S}}. (104) V.2.2 Logical gauge fixing Let \{\overline{X}_{j},\overline{Z}_{j}\}_{j=1}^{k} be a generating set of logical Pauli operators for (\mathcal{S},\mathcal{H}_{\mathcal{S}}) . Fixing a logical means promoting a subset of these logical operators to stabilizers. For example, fixing \overline{Z}_{a} yields \mathcal{S}^{\prime}=\langle\mathcal{S},\overline{Z}_{a}\rangle,\qquad\mathcal{H}_{\mathcal{S}^{\prime}}=\left\{\,\ket{\psi}\in\mathcal{H}_{\mathcal{S}}:\overline{Z}_{a}\ket{\psi}=\ket{\psi}\,\right\}, (105) which fixes the a -th logical qubit to |0_{L}\rangle and reduces the number of encoded qubits to k-1 . Alternatively, fixing \overline{X}_{a} prepares |+_{L}\rangle on the a -th logical. For the Iceberg code, we use logical gauge fixing and promote some of the logical operators to be stabilizers. Because the resulting gauge-fixed code \mathcal{S}^{\prime} results from keeping r of the logical qubits in the parent code \mathcal{S} in \ket{0_\mathrm{L}} or \ket{+_\mathrm{L}} , the fault tolerant encoding circuits for useful states such as \ket{+_\mathrm{L}}^{\otimes k-r} need to be modified relative to Fig. 12 (b). An example of this, shown in Fig. 13 , prepares \ket{+_\mathrm{L}}^{\otimes k-1} in the gauge-fixed code which fixes k -th logical qubit to \ket{0_\mathrm{L}} . Figure 13: Fault tolerant initialization circuit for the gauge-fixed Iceberg code. The initialization circuit for case when we fix the (k-1) -th logical qubit to |+_{\mathrm{L}}\rangle and k -th logical qubit in \ket{0_\mathrm{L}} of the Iceberg code which encode k logical qubits. This circuit requires a total of k+4 CNOT gates and two-qubit depth of \lceil k/2\rceil+4 . V.2.3 Parallelization of single qubit gates Many quantum algorithms contain layers of single-qubit rotations acting on each of the qubits. In the standard Iceberg code, these rotations get compiled down to X - and Z -rotations; from Eq. ( 100 ) a single-qubit X rotation by angle \theta on logical qubit i is physically implemented via e^{-i\frac{\theta}{2}X_{t}\otimes X_{i}} . Therefore, every logical X rotation involve the top qubit. If a layer contains many logical X rotations, they must be run sequentially because they share the top qubit . Likewise, all single-qubit Z rotations involve the bottom qubit b and must be run sequentially. Suppose that instead of using the standard \llbracket k+2,k,2\rrbracket Iceberg code, which encodes k logical qubits into k+2 physical qubits and has code distance 2, we gauge fix \ell qubits to fixed logical states while keeping the number of computational qubits k constant, which in turn gives us a \llbracket k+\ell+2,k,2\rrbracket code. Say we fix the logical qubit g_{z} to be in the +1 eigenstate of \overline{Z}_{g_{z}}=Z_{b}Z_{g_{z}} . This is equivalent to saying that logical qubit g_{z} is gauge-fixed to the |0\rangle_{L} state. Thus for any other unfixed logical qubit q , \displaystyle\overline{Z}_{q}=Z_{b}Z_{q}=Z_{b}Z_{q}\cdot Z_{b}Z_{g_{z}}=Z_{g_{z}}Z_{q}. (106) So we can use the new gauge-fixed qubit g_{z} as a proxy bottom qubit. Similarly, if we gauge-fix logical qubit g_{x} to |+\rangle_{L} by adding X_{t}X_{g_{x}} to the stabilizer group, for any other unfixed logical qubit q we can write \displaystyle\overline{X}_{q}=X_{t}X_{q}=X_{t}X_{q}\cdot X_{t}X_{g_{x}}=X_{g_{x}}X_{q}. (107) And so we can use gauge qubit g_{x} as a proxy top qubit. We can use these proxy qubits to parallelize our single qubit gate layers. For example, to perform \overline{X}_{q_{1}}(\theta_{1}) and \overline{X}_{q_{2}}(\theta_{2}) in the same layer. We can now run \overline{X}_{q_{1}}\cong X_{t}X_{q_{1}} and \overline{X}_{q_{2}}\cong X_{g_{x}}X_{q_{2}} in parallel, since they share no qubits. Given a layer of single-qubit X rotations of width w_{x} and n_{x} gauge qubits, the circuit depth of the single-qubit rotation layer is reduced from w_{x} to w_{x}/n_{x} . The same is true for the Z -type checks. V.3 Experimental Results Experiments were performed on the Quantinuum H2-1 and H2-2 quantum hardware devices, both with a total of 56 physical qubits. We experimentally demonstrate the effect of QED on the shadow overlap and the fidelity. For the shadow overlap, we use the improved protocol with single-qubit random Pauli bases measurements. For the estimated fidelity, we apply the transformation \hat{\phi}=2\hat{\omega}-1 , where \hat{\phi} is the estimated fidelity and \hat{\omega} is the empirical estimate of the average shadow overlap. This is approximately normalized shadow overlap in Ref. Huang et al. 2024a up to a 2^{-n} correction. For m -level shadow overlap protocols, the transformation is approximately \hat{\phi}=\frac{2^{m}}{2^{m}-1}(\hat{\omega}-\frac{1}{2^{m}}) . We refer to Ref. Huang et al. 2024a on why this is a reasonable estimate on experimental fidelity. Table 2 summarizes the shadow overlap and estimated fidelity for both unencoded (physical) and Iceberg-encoded circuits. For both devices, we observe that increasing the number of blocks leads to higher shadow overlap and fidelity. For example, on the H2-1 device, encoding 24 logical qubits into four blocks yields a shadow overlap of 1.02\pm 0.06 and an estimated fidelity of 1.04\pm 0.10 , compared to 0.90\pm 0.04 and 0.80\pm 0.09 for the physical circuit. For more details see Table 2 . Device Type Shots Logical qubits Blocks Logical 2-Q depth Physical qubits Physical 2-Q depth Physical 2-Q gates Acceptance rate (%) Shadow overlap Estimated Fidelity H2-1 Physical 500 24 N/A 5 24 5 60 100 0.90\pm 0.04 0.80\pm 0.09 H2-1 Encoded 2000 24 2 5 30 96 432 48 1.00\pm 0.03 0.99\pm 0.07 H2-1 Encoded 2000 24 4 5 34 61 444 17 1.02\pm 0.06 1.04\pm 0.10 H2-2 Physical 500 32 N/A 5 32 5 80 100 0.91\pm 0.03 0.82\pm 0.07 H2-2 Encoded 2000 32 2 5 38 128 572 37 0.90\pm 0.03 0.79\pm 0.06 H2-2 Encoded 2000 32 4 5 42 75 584 39 0.99\pm 0.02 0.98\pm 0.05 H2-2 Physical 700 40 N/A 6 40 6 120 100 0.91\pm 0.03 0.82\pm 0.06 H2-2 Encoded 3000 40 4 6 50 86 724 23 0.97\pm 0.03 0.94\pm 0.06 Table 2: Shadow overlap results. Shadow overlap values and acceptance rates for physical (unencoded) and Iceberg-encoded random quantum circuits on H2-1 and H2-2 Quantinuum hardware. Table 3 compares regular QED encoding and gauge-fixing strategies on the H2-2 device. For circuits with 32 logical qubits and two encoded blocks, gauge fixing improves the shadow overlap from 0.90\pm 0.03 to 0.97\pm 0.03 and the estimated fidelity from 0.79\pm 0.06 to 0.94\pm 0.05 , while maintaining a similar acceptance rate. Although for 40 logical qubits and 2 blocks, the gauge-fixed fidelity is lower than the physical fidelity, gauge fixing still provides significant improvements over regular encoded circuits. If experiments with 40 logical qubits and 4 gauge-fixed blocks were feasible, it is plausible that the fidelity would surpass that of regular encoded circuits, which already achieve 0.94 as shown in Table 2 . The gauge-fixed 40 logical qubit, 4 block experiment was not performed as it required more physical qubits than available on the device. Implementing this configuration would require 58 physical qubits— 4 blocks of 10 logical qubits each, with 2 gauge-fixed and 2 additional physical qubits per block, plus two ancilla qubits for syndrome checks—exceeding the available qubit count on the H2 devices. Device Type Shots Logical qubits Blocks Logical 2-Q depth Physical qubits Physical 2-Q depth Physical 2-Q gates Acceptance rate (%) Shadow overlap Estimated Fidelity H2-2 Physical 500 32 N/A 5 32 5 80 100 0.91\pm 0.03 0.82\pm 0.07 H2-2 Encoded 2000 32 2 5 38 128 572 37 0.90\pm 0.03 0.79\pm 0.06 H2-2 Gauge-fixed 2000 32 2 5 42 88 590 38 0.97\pm 0.03 0.94\pm 0.05 H2-2 Physical 700 40 N/A 6 40 6 120 100 0.91\pm 0.03 0.82\pm 0.07 H2-2 Encoded 3000 40 2 6 46 155 712 21 0.82\pm 0.03 0.63\pm 0.07 H2-2 Gauge-fixed 3000 40 2 6 50 108 730 16 0.88\pm 0.04 0.75\pm 0.07 Table 3: Gauge fixing. Comparison of shadow overlap and acceptance rates for regular QED and gauge-fixing strategies on H2-2 hardware. For circuits with 32 logical qubits and 5 layers, gauge fixing yields higher shadow overlap than regular QED encoding. VI One-time quantum digital signatures and one-way puzzles This section elaborates on the discussion at the end of the main text, and formally proves an equivalence between one-time quantum digital signatures and so-called one-way puzzles. This equivalence broadens the potential applications of quantum digital signatures to other kinds of cryptographic tasks. VI.1 Definitions Below, we give formal definitions for one-time quantum digital signatures and one-way puzzles in the inefficient verifier setting. Definition 3 (One-Time Signature Scheme) . A one-time (quantum) signature scheme is a tuple of algorithms (\mathsf{SKGen},\mathsf{PKGen},\mathsf{Sign},\mathsf{Ver}) with the following syntax: • \mathsf{SKGen}(1^{\lambda}) is a probabilistic polynomial-time (PPT) algorithm that takes as input a security parameter \lambda in unary and outputs a secret key \mathsf{sk} . • \mathsf{PKGen}(\mathsf{sk}) is a quantum polynomial-time (QPT) algorithm that takes as input a secret key \mathsf{sk} and outputs a classical public key \mathsf{pk} . • \mathsf{Sign}(\mathsf{sk},m) is a PPT algorithm that takes as input a secret key \mathsf{sk} and a message m ; it outputs a classical signature \sigma . • \mathsf{Ver}(\mathsf{pk},\sigma,m) is a (possibly inefficient) classical algorithm that takes as input a public key \mathsf{pk} , a signature \sigma , and a message m ; it outputs either FAILED or CERTIFIED . It satisfies the following properties: 1. Completeness: There exists a negligible function \mathsf{negl} such that for any message m we have \displaystyle\Pr\left[b=\textsc{CERTIFIED}:\begin{subarray}{c}\mathsf{sk}\leftarrow\mathsf{SKGen}(1^{\lambda})\\ \mathsf{pk}\leftarrow\mathsf{PKGen}(\mathsf{sk})\\ \sigma\leftarrow\mathsf{Sign}(\mathsf{sk},m)\\ b\leftarrow\mathsf{Ver}(\mathsf{pk},\sigma,m)\end{subarray}\right]\geq 1-\mathsf{negl}(\lambda). (108) 2. One-Time Security: There exists a negligible function \mathsf{negl} such that for any QPT algorithms \mathcal{A}_{1},\mathcal{A}_{2} we have \displaystyle\Pr\left[m^{\prime}\neq m\land b=\textsc{CERTIFIED}:\begin{subarray}{c}\mathsf{sk}\leftarrow\mathsf{SKGen}(1^{\lambda})\\ \mathsf{pk}\leftarrow\mathsf{PKGen}(\mathsf{sk})\\ m\leftarrow\mathcal{A}_{1}(\mathsf{pk})\\ \sigma\leftarrow\mathsf{Sign}(\mathsf{sk},m)\\ (\sigma^{\prime},m^{\prime})\leftarrow\mathcal{A}_{2}(\mathsf{pk},\sigma)\\ b\leftarrow\mathsf{Ver}(\mathsf{pk},\sigma^{\prime},m^{\prime})\end{subarray}\right]\leq\mathsf{negl}(\lambda). (109) Note that the only “quantum” parts are in the public key generation and the assumptions about the adversary. Definition 4 (One-Way Puzzle) . A one-way puzzle is a tuple of algorithms (\mathsf{PuzzleGen},\mathsf{PuzzleVer}) with the following syntax: • \mathsf{PuzzleGen}(1^{\lambda}) is a QPT algorithm that takes as input a security parameter \lambda in unary; outputs a secret key s and a puzzle p . • \mathsf{PuzzleVer}(s,p) is a possibly inefficient classical algorithm that takes as input a secret key s and a puzzle p ; it outputs CERTIFIED or FAILED . It satisfies the following properties: 1. Completeness: There exists a negligible function \mathsf{negl} such that we have \displaystyle\Pr\left[b=\textsc{CERTIFIED}:\begin{subarray}{c}(s,p)\leftarrow\mathsf{PuzzleGen}(1^{\lambda})\\ b\leftarrow\mathsf{PuzzleVer}(s,p)\end{subarray}\right]\geq 1-\mathsf{negl}(\lambda). (110) 2. Soundness: There exists a negligible function \mathsf{negl} such that for any QPT algorithm \mathcal{A} , we have \displaystyle\Pr\left[b=\textsc{CERTIFIED}:\begin{subarray}{c}(s,p)\leftarrow\mathsf{PuzzleGen}(1^{\lambda})\\ s^{\prime}\leftarrow\mathcal{A}(p)\\ b\leftarrow\mathsf{PuzzleVer}(s^{\prime},p)\end{subarray}\right]\leq\mathsf{negl}(\lambda). (111) VI.2 Equivalence Here, we adapt the arguments of Chung et al. 2024 , which show the equivalence between one-time signatures and one-way puzzles in the efficient verification, to our setting in which verification may be inefficient. Theorem 14 . One-time quantum digital signature schemes exist if and only if one-way puzzles exist. Proof. We start with the forward direction. Given a one-time signature scheme (\mathsf{SKGen},\mathsf{PKGen},\mathsf{Sign},\mathsf{Ver}) , we construct a one-way puzzle (\mathsf{PuzzleGen},\mathsf{PuzzleVer}) as follows: • \mathsf{PuzzleGen}(1^{\lambda}) computes \mathsf{sk}\leftarrow\mathsf{SKGen}(1^{\lambda}) and \mathsf{pk}\leftarrow\mathsf{PKGen}(\mathsf{sk}) . It outputs secret key s=\mathsf{sk} and puzzle p=\mathsf{pk} . • \mathsf{PuzzleVer}(s,p) parses \mathsf{sk}=s and \mathsf{pk}=p . It computes \sigma\leftarrow\mathsf{Sign}(\mathsf{sk},m_{0}) and b\leftarrow\mathsf{Ver}(\mathsf{pk},\sigma,m_{0}) for a fixed message m_{0} . It outputs b . Completeness follows by the completeness of the signature scheme. To show soundness, suppose there exists \mathcal{A} that breaks the soundness of the one-way puzzle. We construct (\mathcal{A}_{1},\mathcal{A}_{2}) which breaks the one-time security of the signature scheme: • \mathcal{A}_{1}(\mathsf{pk}) picks any m\neq m_{0} as its signing query. • \mathcal{A}_{2}(\mathsf{pk},\sigma) ignores \sigma . It computes s\leftarrow\mathcal{A}(\mathsf{pk}) and \sigma^{\prime}\leftarrow\mathsf{Sign}(s,m_{0}) . It outputs (\sigma^{\prime},m_{0}) . By assumption, (\mathcal{A}_{1},\mathcal{A}_{2}) breaks the soundness with the same advantage as \mathcal{A} . Next, we show the reverse direction. Given a one-way puzzle (\mathsf{PuzzleGen},\mathsf{PuzzleVer}) we construct a one-time signature scheme (\mathsf{SKGen},\mathsf{PKGen},\mathsf{Sign},\mathsf{Ver}) for one-bit messages below. The argument can be generalized to longer messages as done by Ref. Lamport 1979 . • \mathsf{SKGen}(1^{\lambda}) computes (s_{0},p_{0})\leftarrow\mathsf{PuzzleGen}(1^{\lambda}) and (s_{1},p_{1})\leftarrow\mathsf{PuzzleGen}(1^{\lambda}) by running \mathsf{PuzzleGen} in two independent instances. It outputs \mathsf{sk}=(s_{0},s_{1},p_{0},p_{1}) . • \mathsf{PKGen}(\mathsf{sk}) parses \mathsf{sk}=(s_{0},s_{1},p_{0},p_{1}) and outputs \mathsf{pk}=(p_{0},p_{1}) . • \mathsf{Sign}(\mathsf{sk},m) parses \mathsf{sk}=(s_{0},s_{1},p_{0},p_{1}) and outputs \sigma=s_{m} . • \mathsf{Ver}(\mathsf{pk},\sigma,m) parses \mathsf{pk}=(p_{0},p_{1}) and computes b\leftarrow\mathsf{PuzzleVer}(\sigma,p_{m}) . It outputs b . Correctness follows by the correctness of the one-way puzzle. To show one-time security, suppose there exists (\mathcal{A}_{1},\mathcal{A}_{2}) that breaks it. We construct \mathcal{A} which breaks the soundness of the one-way puzzle: • \mathcal{A} receives a puzzle p . It samples a new key-puzzle pair (s^{\prime},p^{\prime}) , then sets \mathsf{pk}=(p,p^{\prime}) or \mathsf{pk}=(p^{\prime},p) randomly. • Then, \mathcal{A} computes m\leftarrow\mathcal{A}_{1}(\mathsf{pk}) . If either \mathsf{pk}=(p,p^{\prime}) and m=1 , or \mathsf{pk}=(p^{\prime},p) and m=0 , \mathcal{A} continues; otherwise, it aborts. • If \mathcal{A} does not abort, then s^{\prime} is a valid signature of m . Thus, \mathcal{A} computes (\sigma^{\prime},m^{\prime})\leftarrow\mathcal{A}_{2}(\mathsf{pk},s^{\prime}) . Then, \mathcal{A} outputs \sigma^{\prime} . With non-negligible probability, m^{\prime}\neq m and \sigma^{\prime} is a valid signature on m^{\prime} . This means that \mathsf{PuzzleVer}(\sigma^{\prime},p) accepts with non-negligible probability. Since, the probability that \mathcal{A} does not abort is 1/2 , this suffices for the proof. Note that in the reductions above, the verification algorithms are all inefficient, and they are exclusively run by other verification algorithms, hence not affecting the efficiency of other algorithms. ∎