2025/09/30 by Li, Guangyi, Gan, Yu, Wu, Zeguan +3
#FOS: Computer and information sciences #FOS: Physical sciences #Hardware Architecture (cs.AR) #Quantum Physics (quant-ph)
paper · doi:10.48550/arxiv.2509.26494
Quantum random access memories (QRAMs) are pivotal for data-intensive quantum algorithms, but existing general-purpose and domain-specific architectures are hampered by a critical bottleneck: a heavy reliance on non-Clifford gates (e.g., T-gates), which are prohibitively expensive to implement fault-tolerantly. To address this challenge, we introduce the Stabilizer-QRAM (Stab-QRAM), a domain-specific architecture tailored for data with an affine Boolean structure (f(x) = Ax + b over \mathbbF2), a class of functions vital for optimization, time-series analysis, and quantum linear systems algorithms. We demonstrate that the gate interactions required to implement the matrix A form a bipartite graph. By applying König's edge-coloring theorem to this graph, we prove that Stab-QRAM achieves an optimal logical circuit depth of O(log N) for N data items, matching its O(log N) space complexity. Critically, the Stab-QRAM is constructed exclusively from Clifford gates (CNOT and X), resulting in a zero T-count. This design completely circumvents the non-Clifford bottleneck, eliminating the need for costly magic state distillation and making it exceptionally suited for early fault-tolerant quantum computing platforms. We highlight Stab-QRAM's utility as a resource-efficient oracle for applications in discrete dynamical systems, and as a core component in Quantum Linear Systems Algorithms, providing a practical pathway for executing data-intensive tasks on emerging quantum hardware.