⚛️ quantum physics

Proofs of Quantum Memory

This paper introduces the concept of proofs of quantum memory (PoQM), a protocol enabling a classical verifier to confirm a prover's sustained possession of qubits over time, and provides constructions based on the hardness of LWE while exploring their theoretical implications for one-way puzzles and key exchange.

Original authors: Minki Hhan, Tomoyuki Morimae, Yasuaki Okinaka, Takashi Yamakawa

Published 2026-10-27

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Minki Hhan, Tomoyuki Morimae, Yasuaki Okinaka, Takashi Yamakawa

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

In the rapidly evolving landscape of computing, a new frontier is opening where machines do not just calculate faster, but calculate in a fundamentally different way. These quantum computers use the strange rules of physics to process information, holding data in states that can exist in multiple possibilities at once. As engineers race to build larger machines with more of these quantum units, a critical question arises for anyone relying on them: how can you be sure the machine actually has the memory it claims to have? Imagine a startup announcing they have built a processor with one hundred million of these quantum units. A traditional investor, using only a standard computer, cannot simply look inside the machine to count them, because the act of looking would destroy the delicate information. Furthermore, existing methods to prove a machine is "quantum" only confirm that it is doing something a normal computer cannot do; they do not verify that the machine is holding onto a specific, massive amount of memory for a set period of time. This gap leaves a dangerous blind spot where a company could claim a capability they do not possess.

A team of researchers has now addressed this gap by introducing a new concept called proofs of quantum memory. This is a protocol, or a structured conversation, between a classical computer acting as a verifier and a quantum computer acting as a prover. The goal is not just to prove the prover is quantum, but to prove it is holding a specific number of quantum units in its memory for a specific duration. The researchers designed a system where the classical verifier sends a challenge, the quantum prover must store a quantum state, wait for a time delay, and then respond correctly to a second challenge. If the prover attempts to deviate from the protocol by not storing the memory, or by storing less than promised, the laws of physics ensure they will fail the test with high probability. The researchers successfully constructed two versions of this protocol. The first version is very fast, requiring only two rounds of communication, but it relies on a strong mathematical assumption that is believed to be very hard to break. The second version is slightly slower, requiring many rounds of communication, but it works under a weaker, more standard mathematical assumption. Both methods provide a way for a classical observer to be confident that a remote quantum device is genuinely maintaining a large quantum memory.

The work also explores the boundaries of what is possible, revealing that creating these memory proofs is not as simple as just using basic encryption tools. The researchers showed that if such a protocol exists, it implies the existence of other complex cryptographic tools, suggesting that building these proofs from the most basic building blocks of cryptography is likely impossible. This finding helps map the landscape of quantum security, showing that these memory proofs occupy a unique and difficult-to-reach space. Additionally, the team demonstrated that these protocols capture a specific type of interaction that is genuinely interactive, distinguishing them from simpler, one-off tests. By proving that constant-round quantum tests lead to either these memory proofs or a specific type of single-round test, the researchers clarified that their new concept is essential for verifying the deep, interactive nature of quantum memory.

Ultimately, this research provides a practical toolkit for the future of quantum verification. As quantum technology moves from theory to large-scale hardware, the ability to verify memory capacity without destroying the data is becoming essential. The researchers have shown that this verification is possible, provided certain mathematical problems remain hard to solve. They have also shown that while the task is difficult, it is achievable under specific conditions, and that the difficulty of the task is linked to the fundamental security of the quantum world itself. This work does not just offer a new test; it offers a way to trust the scale of the quantum machines that will soon power our most complex calculations.

Technical Summary: Proofs of Quantum Memory

1. Problem Statement

With the rapid advancement of quantum computing architectures and the prospect of large-scale quantum memory, a critical verification challenge has emerged: How can a classical verifier confirm that a remote quantum device genuinely possesses and retains a specified number of qubits for a specific duration?

Existing Proofs of Quantumness (PoQ) [BCM+21] allow a classical verifier to confirm that a prover is performing non-classical computations. However, PoQ are insufficient for verifying the capacity or retention of quantum memory. A prover could theoretically pass a PoQ using a small number of qubits and classical post-processing, failing to demonstrate the possession of a large-scale quantum memory (e.g., 100 million qubits) over time. This paper addresses the need for a protocol where a classical verifier can certify that a prover has maintained a specific quantum memory size ( $m_1$ ) during a time interval $\Delta$ between an initialization phase and an execution phase.

2. Methodology and Definitions

2.1 Proofs of Quantum Memory (PoQM)

The authors introduce Proofs of Quantum Memory (PoQM) as a new cryptographic primitive. A PoQM is an interactive protocol between a classical Probabilistic Polynomial-Time (PPT) verifier and a Quantum Polynomial-Time (QPT) prover over a classical channel. The protocol consists of two phases:

Initialization Phase: The verifier ( $V_1$ ) and prover ( $P_1$ ) interact. $P_1$ outputs a classical string state and an $m_1$ -qubit quantum state $\sigma_{state}$ .
Execution Phase: After a time delay $\Delta$ , the verifier ( $V_2$ ) and prover ( $P_2$ ) interact. $P_2$ takes state and $\sigma_{state}$ as input.

Security Properties:

Completeness: An honest prover with an $m_1$ -qubit memory is accepted with high probability.
Soundness: Any prover that can only store at most $m_2$ qubits (where $m_2 < m_1$ ) during the interval $\Delta$ is rejected with high probability. The verifier effectively certifies that the prover possessed at least $(m_2 + 1)$ qubits.

The paper also defines Inefficient-Verifier PoQM (IV-PoQM), where the verifier's final decision computation need not be efficient (unbounded), though the interaction remains classical.

2.2 Technical Tools

The constructions rely on several cryptographic primitives and lemmata:

LWE Hardness: Both the Learning With Errors (LWE) assumption and its subexponential hardness variant are central to the constructions.
1-of- $2^k$ Puzzles: Used to construct two-round PoQM with negligible soundness error.
Verifiable Remote State Preparation (RSP): Used to replace quantum channels with classical channels, enabling classical verification of quantum states.
LOCC Leakage Property for BB84 States: A lemma from [ÇG24] regarding the security of BB84 states against adversaries with limited quantum memory and classical leakage.
Measurement Lemma: A result from [BZ13] relating the probability of outputting a string by a quantum algorithm with and without intermediate measurements.

3. Key Contributions and Results

3.1 Constructions of PoQM

The paper provides two distinct constructions of PoQM based on the hardness of LWE:

Two-Round Construction (Subexponential LWE):
- Basis: Based on 1-of- $2^k$ puzzles [LLQ22].
- Assumption: Subexponential hardness of LWE.
- Properties: Two-round (four-message) protocol. Achieves negligible soundness error.
- Mechanism: The prover generates a state via an "Obligate" algorithm. The verifier challenges the prover with a random string. The soundness relies on the inability of an adversary with limited memory to solve the puzzle for both halves of a split state simultaneously.
Polynomial-Round Construction (Polynomial LWE):
- Basis: Based on Verifiable Remote State Preparation (RSP) [Zha25].
- Assumption: Polynomial hardness of LWE.
- Properties: Polynomial-round protocol. Achieves inverse-polynomial soundness error.
- Mechanism: The verifier uses RSP to generate BB84 states over a classical channel. The prover must store these states and measure them correctly upon challenge. The soundness is amplified using the LOCC leakage property to show that an adversary with $m_2$ qubits cannot guess the measurement outcomes of $\lceil 9.1 m_2 \rceil$ qubits with high probability.

3.2 Lower Bounds and Implications

The paper establishes lower bounds on the cryptographic primitives required to construct PoQM:

IV-PoQM $\implies$ One-Way Puzzles (OWPuzzs): The authors show that IV-PoQM imply the existence of OWPuzzs [KT24], a quantum analogue of One-Way Functions (OWFs). This suggests that constructing PoQM from OWFs alone (in a black-box manner) is likely difficult.
Predictable PoQM $\implies$ QCCC Key Exchange: For a restricted version called "predictable PoQM" (where the execution phase is single-round and the verifier's check is deterministic), the authors show it implies Quantum Computation Classical Communication (QCCC) Key Exchange. Since evidence suggests QCCC KE cannot be constructed from OWFs in a black-box way, this implies a similar difficulty for PoQM.

3.3 Relationship to Proofs of Quantumness (PoQ)

The paper investigates the relationship between PoQM and existing PoQ:

Generalization: PoQM generalize PoQ. If a PoQM exists, a PoQ exists.
Capturing "Genuinely-Interactive" PoQ: The authors prove that constant-round PoQ imply either:
1. Constant-round PoQM (with $m_2=0$ ), or
2. Single-round Quantum-Verifier PoQ (QV-PoQ).
  Single-round QV-PoQ are considered "trivial" (solving a classically hard but quantumly easy problem). Thus, PoQM are shown to capture the "genuinely-interactive" nature of non-trivial PoQ.
Black-Box Reductions: If constant-round IV-PoQ exist that are black-box constructed from quantumly-secure falsifiable assumptions, then constant-round IV-PoQM exist. This leads to the conclusion that IV-PoQM can be constructed from quantumly-secure constant-round statistically-hiding commitments (and thus from collision-resistant hash functions).

4. Significance and Claims

The paper claims to establish the theoretical foundation for classically verifying quantum memory retention, a capability distinct from and stronger than verifying quantumness.

Feasibility: The paper demonstrates that PoQM are constructible under standard cryptographic assumptions (LWE), providing a concrete path for verification in future quantum networks.
Theoretical Limits: By linking PoQM to OWPuzzs and QCCC KE, the paper delineates the boundaries of what can be achieved with weaker assumptions (like OWFs), suggesting that PoQM likely requires stronger assumptions.
Conceptual Clarity: The work clarifies the hierarchy of quantum verification protocols, distinguishing between "trivial" single-round proofs and "genuinely-interactive" proofs that require memory retention, with PoQM serving as the formalization of the latter.

The authors maintain a modest tone regarding applications, focusing strictly on the cryptographic definitions, constructions, and theoretical implications within the context of quantum cryptography and complexity theory. They do not propose specific experimental implementations or immediate commercial applications, but rather provide the necessary theoretical tools for future verification systems.