Paper 2025/1837

Proofs of Quantum Memory

Abstract

With the rapid advances in quantum computer architectures and the emerging prospect of large-scale quantum memory, it is becoming essential to classically verify that remote devices genuinely allocate the promised quantum memory with a specified number of qubits. In this paper, we introduce a new concept, proofs of quantum memory (PoQM). 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 where the verifier can verify that the prover has possessed a quantum memory with a specified number of qubits for a specified period of time. PoQM generalize the well-studied notion of proofs of quantumness (PoQ) [Brakerski, Christiano, Mahadev, Vazirani, and Vidick, JACM 2021] where a classical verifier can verify that the prover is not classical. Our contributions are summarized as follows: We introduce a formal definition of PoQM. We also introduce a variant of PoQM, which we call inefficient-verifier PoQM (IV-PoQM), where the verifier's final computation to make the decision is not necessarily efficient. Clearly, PoQM imply IV-PoQM. We construct PoQM based on the hardness of LWE. Specifically, we give two constructions of PoQM. The first one is of two-round (i.e., four-message) and has negligible soundness error under the subexponential-hardness of LWE. The second one is of polynomial-round and has inverse-polynomial soundness error under the polynomial-hardness of LWE. As a lowerbound of IV-PoQM (and therefore PoQM), we show that IV-PoQM imply one-way puzzles. Moreover, we show that a certain restricted version of PoQM implies quantum computation classical communication (QCCC) key exchange, which suggests the difficulty of black-box constructing PoQM from one-way functions. We show that constant-round PoQ imply PoQM or single-round PoQ (with a quantum verifier). Single-round PoQ are ``trivial'' PoQ in the sense that the verifier asks the prover to solve a classical problem which is quantumly easy but classically hard. The result therefore demonstrates that PoQM capture ``genuinely-interactive'' PoQ. We show that if constant-round IV-PoQ that are black-box constructed from quantumly-secure falsifiable assumptions exist then IV-PoQM exist. This result implies that IV-PoQM can be constructed from quantumly-secure constant-round statistically-hiding commitments (and therefore from quantumly-secure collision-resistant hash functions).