Query-limited ram programs enable controlled stateful quantum computations
Query-Limited RAM Programs and their Applications
Cryptography and Security
Summary
Traditional quantum one-time programs let you use a quantum token to run a computation just once, but they can't keep track of state or allow multiple interactions. The authors developed query-limited RAM programs, which extend these ideas to allow multiple controlled uses of a program while protecting its internal state from being copied or reverted by attackers. They build these programs using new tools called one-shot programs, combining cryptographic and quantum concepts to enable more powerful and flexible quantum tokens. This work opens the door to new applications where quantum computations need to be stateful and access-controlled.
What this means in practice
- •For cloud service providers: Design secure delegation protocols that limit client queries while preserving computation state with quantum tokens.
- •For digital rights managers: Create quantum tokens that allow controlled usage budgets and prevent unauthorized copying or replay of software functionalities.$Commercial implications: Enables sale of quantum-protected software licenses with programmable usage limits, resisting piracy.
A theory result. No direct application yet.
Authors
Jiahui Liu, Justin Raizes, Bhaskar Roberts, Omri Shmueli
Abstract
Quantum one-time programs (Broadbent, Gutoski and Stebila, CRYPTO 2013) or OTPs for short, enable a functionality to be encoded into a quantum token that can be evaluated on a single chosen input and then becomes unusable. While powerful, this primitive is inherently stateless and tied to a setting in which a quantum token needs to be issued and distributed for every single evaluation of a circuit. This raises a natural question: can the one-time computation paradigm be extended to richer, stateful forms of controlled access, and would such an extension offer inherent advantages beyond standard OTPs? We introduce $\textit{query-limited RAM programs}$ (QLPs), a RAM-generalization of QOTPs that supports structured, stateful computation under bounded or policy-driven access. QLPs allow controlled sequences of evaluations while preventing adversarial forking or rollback of computational state. This enables new applications beyond stateless one-time programs, including quantum tokens for Turing Machines whose size depends only on $\textit{code length}$ (and not runtime), transferable $k$-time or budget-limited programs, and low-communication mechanisms for delegating computation in settings such as Software-as-a-Service. To construct QLPs, we introduce $\textit{one-shot programs}$, unifying one-shot signatures (Amos, Georgiou, Kiayias and Zhandry, STOC 2020) with the single effective query paradigm (Gupte, Liu, Raizes, Roberts and Vaikuntanathan, STOC 2025). We prove that one-shot programs generically imply query-limited programs, demonstrating that the strengthened unclonability guarantees of one-shot signatures translate into enhanced functionality. Along the way, we clarify the relationship between signature-token primitives and quantum one-time programs via generic constructions, essentially showing that one-time signing programs imply one-time general computation.