Beyond NISQ Assumptions: One-time Memory in the Classically Accessible Random-Oracle Model
Abstract
Quantum information enables many cryptographic primitives that are impossible in the classical world. A line of works has developed cryptographic protocol under the assumption that quantum adversaries are restricted to noisy intermediate-scale quantum (NISQ) computing power, enabling strong one-time functionalities. But the advent of early fault-tolerant quantum computers eras will allow deeper logical quantum circuits, calling into questions the applicability of these NISQ-based assumptions. In this work, we adapt the classically accessible random oracle model (CAROM) as in [BDF+11] and [AK22], in which adversaries are only allowed to classically query the random oracle. The restriction is well motivated for NISQ quantum adversaries and may remain plausible in the presence of early fault-tolerant quantum computers. Then, we show that an efficient simulation-secure one-time memory (OTM) is possible under CAROM. Our protocol uses only BB84 states and has quadratic communication: for a λ-bit message and integer-valued parameters n=n(λ) and ℓ=ℓ(λ), the construction uses nℓ qubits and (n+2)λ classical bits, and for any quantum adversary with at most 2ℓ/2−1−1 classical queries to the random oracle, its simulation advantage is at most (n+3)(3/4)n. Hence exponentially small simulation advantage in n.
Related
- Can the system dynamics remain structurally non-Markovian while its experimentally accessible memory signatures disappear?
- Demonstration of Logical Error Suppression in a Surface Code Memory on a Cloud-Accessible IBM Superconducting Processor
- Beyond Orbital Rotations: Correlation-Rank Limits and Clifford-Accessible Measurement, from Algebra and Global Optimization
- Resource-efficient quantum-walker quantum random access memory
- Beyond Hippocampal Avoidance: Early Experience With Memory-Network Avoidance Prophylactic Cranial Irradiation in Small Cell Lung Cancer.
BibTeX
@misc{chen2026beyond,
title = {{Beyond NISQ Assumptions: One-time Memory in the Classically Accessible Random-Oracle Model}},
author = {Boyang Chen and Tianren Liu and Luojian Wei},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.32603},
eprint = {2609.32603},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.32603},
}
RIS
TY - UNPB
TI - Beyond NISQ Assumptions: One-time Memory in the Classically Accessible Random-Oracle Model
AU - Boyang Chen
AU - Tianren Liu
AU - Luojian Wei
PY - 2026
DA - 2026/09/26
PB - arXiv
DO - 10.48550/arxiv.2609.32603
UR - https://arxiv.org/abs/2609.32603
AB - Quantum information enables many cryptographic primitives that are impossible in the classical world. A line of works has developed cryptographic protocol under the assumption that quantum adversaries are restricted to noisy intermediate-scale quantum (NISQ) computing power, enabling strong one-time functionalities. But the advent of early fault-tolerant quantum computers eras will allow deeper logical quantum circuits, calling into questions the applicability of these NISQ-based assumptions. In this work, we adapt the classically accessible random oracle model (CAROM) as in [BDF+11] and [AK22], in which adversaries are only allowed to classically query the random oracle. The restriction is well motivated for NISQ quantum adversaries and may remain plausible in the presence of early fault-tolerant quantum computers. Then, we show that an efficient simulation-secure one-time memory (OTM) is possible under CAROM. Our protocol uses only BB84 states and has quadratic communication: for a λ-bit message and integer-valued parameters n=n(λ) and ℓ=ℓ(λ), the construction uses nℓ qubits and (n+2)λ classical bits, and for any quantum adversary with at most 2^ℓ/2−1−1 classical queries to the random oracle, its simulation advantage is at most (n+3)(3/4)^n. Hence exponentially small simulation advantage in n.
ER -