Abstract
Oracle-based quantum algorithms require coherent evaluation of classical functions on superposed inputs, and in fault-tolerant architectures this cost is dominated by non-Clifford gates: generic lookup constructions incur -counts that grow with the data size. Here we show that affine Boolean functions over -- the algebraic core of parity checks, linear feedback shift registers, and cipher linear layers -- are exactly the functions admitting computational-basis-preserving Clifford oracles, and we develop this correspondence into Stab-QRAM, a compiler mapping a specification to an ancilla-free circuit of CNOT and gates with zero -count. Via König's edge-coloring theorem, the compiled schedule provably attains the minimum depth for its gate set. Case studies spanning Simon-type oracles, block-encodings of -type coset operators, and syndrome extraction for CSS codes show one compiler serving the algorithm, primitive, and error-correction layers of the quantum stack.