⚛️ quantum physics

Digital signatures with classical shadows on near-term quantum computers

This paper proposes and experimentally demonstrates a near-term feasible quantum digital signature scheme that relies solely on classical communication by using classical shadows of random circuit states as public keys, supported by an improved state-certification primitive and validated on a 32-qubit quantum processor.

Original authors: 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

Published 2026-02-05

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: 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

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: A New Kind of Digital ID Card

Imagine you want to send a secret message to a friend, and you need to prove it really came from you. In the digital world, we use digital signatures for this. Usually, these signatures rely on math problems that are hard for computers to solve (like factoring huge numbers). But, a powerful future quantum computer could solve these math problems easily, breaking our current security.

This paper proposes a new way to create digital signatures that doesn't rely on math puzzles. Instead, it relies on the weird laws of quantum physics. The authors show that even with today's noisy, imperfect quantum computers, they can create a signature that is secure because it is physically impossible to "fake" without knowing a secret key.

The Problem: The "Glass House" of Quantum Security

Previous ideas for quantum signatures had a major flaw: they required sending actual quantum particles (like photons) over the internet to prove a signature.

The Analogy: Imagine trying to mail a fragile glass sculpture. If you send it through the mail, it might break, or someone might swap it for a fake one. Keeping it safe requires special "quantum memory" (like a super-cooled vault) that doesn't really exist yet.

The authors asked: Can we make a quantum signature that only uses regular, classical data (like 0s and 1s) that we can send over the internet, without needing fragile quantum particles in transit?

The Solution: "Classical Shadows"

The answer is Classical Shadows.

The Metaphor: Imagine you have a complex, 3D sculpture (the quantum state). You cannot send the sculpture itself because it's too heavy and fragile. However, you can shine a light on it from many different angles and take shadows (2D silhouettes) of it.
The Magic: If you have enough shadows from random angles, you can mathematically reconstruct what the sculpture looks like. But here is the catch: if you only have the shadows, it is incredibly difficult to figure out exactly how the sculpture was built (the secret recipe or "circuit").
The Paper's Claim: The authors use these "shadows" (which are just lists of numbers) as the public key. The sender keeps the "recipe" (the quantum circuit) secret. To sign a message, they reveal the recipe. The receiver uses the public shadows to check if the recipe actually produces the correct sculpture.

The Challenge: Noisy Quantum Computers

Today's quantum computers are like a toddler trying to build a LEGO castle. They get tired, drop pieces, and make mistakes (noise). If the computer makes too many mistakes, the "sculpture" looks wrong, and the signature fails.

To fix this, the team invented a new way to check the quality of the sculpture, called State Certification.

The Analogy: Instead of just looking at the finished castle, they developed a special "error-detecting code" (like a spell-checker for quantum states). They built the castle using a special "Iceberg" structure. If a piece falls off, the structure changes in a way that is easy to spot, allowing them to throw away the bad attempts and keep only the good ones.

The Experiment: A Proof of Concept

The team tested this on a real quantum computer (a trapped-ion processor from Quantinuum).

What they did: They created a "shadow" of a quantum state involving 32 qubits (the basic units of quantum info).
The Result: They managed to create a signature with a 90% success rate (fidelity). This is high enough to prove the idea works.
The Security: They showed that while it takes a quantum computer a short time to verify the signature, it would take a hacker an impossibly long time to reverse-engineer the secret recipe from the shadows. It's like the difference between checking if a key fits a lock (fast) and trying to build a new key by looking at the lock's scratches (impossible).

Why This Matters (According to the Paper)

No "One-Way Functions" Needed: Current security relies on math problems we think are hard. This new method relies on the fundamental laws of physics, which are harder to break.
Works on Today's Hardware: You don't need a perfect, futuristic quantum computer. This works on the noisy, imperfect machines we have right now.
Classical Communication: You don't need to send quantum particles over the internet. You just send regular data (the shadows), which is much easier to do.

Summary in One Sentence

The authors created a new type of digital signature that uses "shadows" of quantum states to prove identity, proving that even with today's imperfect quantum computers, we can create secure codes that are impossible to fake without the secret key.

Technical Summary: Digital Signatures with Classical Shadows on Near-Term Quantum Computers

Problem Statement

Traditional digital signature schemes rely on the existence of one-way functions (OWFs), such as integer factorization (RSA) or lattice-based problems (LWE). These assumptions are vulnerable to fault-tolerant quantum computers (e.g., Shor's algorithm) and are subjects of ongoing research regarding their security against quantum adversaries. While quantum mechanics offers alternative cryptographic primitives grounded in physical laws rather than mathematical hardness, existing proposals for quantum digital signatures (QDS) typically require the transmission and coherent storage of quantum states as public keys. This reliance on low-noise quantum communication and long-lived quantum memory renders current proposals impractical for near-term quantum devices.

The central challenge addressed in this work is the realization of a quantum digital signature scheme that:

Does not rely on OWFs or the existence of one-way functions.
Operates using only classical communication, eliminating the need for quantum memory or quantum transmission of public keys.
Is feasible on near-term, noisy intermediate-scale quantum (NISQ) hardware.

Methodology

Core Concept: Classical Shadows as Public Keys

The authors propose a signature scheme where the public keys are not quantum states but classical shadows of quantum states.

Secret Key: Two random quantum circuits, $C_0$ and $C_1$ .
Public Key: Classical shadows, $S(|C_0\rangle)$ and $S(|C_1\rangle)$ , generated by performing randomized measurements on the states $|C_b\rangle = C_b|0\rangle$ .
Signing: To sign a bit $b$ , the sender reveals the classical description of the circuit $C_b$ .
Verification: The receiver uses the public shadows and the revealed circuit to verify that the circuit $C_b$ produces a state consistent with the public shadows. This is achieved via a shadow overlap protocol.

Security Assumption: Computational No-Learning (CNL)

The security of the scheme rests on the Computational No-Learning (CNL) from shadows conjecture. This conjecture posits that it is computationally infeasible for an adversary to learn the description of a random quantum circuit given only its classical shadows (polynomial-length samples of randomized measurements).

This assumption is distinct from and weaker than the standard "no-learning from states" conjecture, as shadows are derived from state copies via simple measurements.
The paper provides theoretical evidence that existing learning algorithms (e.g., those based on local inversion or light-cone arguments) fail to learn these circuits under the constraints of the protocol (proper learning, arbitrary geometry, and shadow-only access).
The authors demonstrate a separation between the time required to verify a signature (exponential in $n$ but feasible for the verifier) and the time required to learn (spoof) the circuit (exponentially harder), creating a security gap.

Technical Innovations

To make the scheme viable on noisy hardware, the authors introduce two key technical improvements:

Improved Shadow Overlap Protocol: They modify existing shadow overlap protocols (based on Ref. [30]) by using random Clifford circuits on subsets of qubits rather than just random Pauli measurements. This reduces the "relaxation time" ( $\tau$ ) of the certification Markov chain and lowers the variance of the estimator, significantly improving noise tolerance and reducing the sample complexity required for certification.
Quantum Error Detection (QED): To overcome hardware infidelity, the authors employ a multi-block Iceberg error-detecting code.
- The Iceberg code encodes $k$ logical qubits into $k+2$ physical qubits.
- They utilize gauge fixing to promote certain logical operators to stabilizers, creating "proxy" qubits that allow for the parallelization of single-qubit logical gates, thereby reducing circuit depth and memory errors.
- This approach achieves "beyond-break-even" performance, where the encoded fidelity exceeds the unencoded fidelity despite the overhead.

Key Results

Theoretical Evidence

Learning Hardness: The authors show that known algorithms for learning shallow circuits fail to satisfy the necessary conditions (proper learning, arbitrary geometry, shadow-only access) to break the scheme.
Security Gap: They prove that for specific circuit ensembles (approximate designs), the time complexity for an adversary to learn the circuit via low-degree polynomials or variational training is exponentially larger than the time required for verification. Specifically, they show that variational training requires exponentially many queries to reach the target fidelity for the circuit depths used.

Experimental Demonstration

The authors implemented the protocol on the Quantinuum H2 trapped-ion processor (56 physical qubits).

Circuit Parameters: They generated shadows for 32-qubit states using random circuits with $\ge 80$ logical two-qubit gates (corresponding to $\ge 582$ physical two-qubit gates).
Fidelity: Using the multi-block Iceberg code with gauge fixing, they achieved a certified fidelity of $0.90 \pm 0.01$ with 17,316 samples.
Proof-of-Principle: The experiment successfully demonstrated the ability to distinguish between an honest signer and an adversary. The authors calculated that increasing the sample size by a factor of 19.5 (to ~340k samples) would be sufficient to achieve a security parameter where the probability of a computationally bounded adversary successfully spoofing the signature is negligible ( $< 10^{-5}$ ).

Significance and Claims

The paper claims to demonstrate the near-term feasibility of quantum digital signatures that do not rely on OWFs or quantum communication.

Independence from OWFs: The scheme grounds security in the physical difficulty of learning quantum processes, offering a route to cryptography that remains secure even if OWFs do not exist.
NISQ Compatibility: By utilizing classical shadows and error-detecting codes rather than full error correction, the protocol operates within the capabilities of current noisy quantum hardware.
Foundational Primitive: The work establishes a link between quantum digital signatures and one-way puzzles, a primitive that enables the construction of other quantum cryptographic protocols (like non-interactive bit commitments) without assuming OWFs.

The authors emphasize that while the current demonstration is a proof-of-principle for a single-bit signature, the underlying primitives (shadow overlap certification and error detection) are scalable. They note that extending this to multi-bit messages is possible using classical error-correcting codes to reduce verification costs, and that increasing the circuit size would further restore security against potential future learning algorithm breakthroughs.