How to make quantum cheese: efficient geometry oracles for exponentially many pseudorandom microstructures

arXiv:2606.00222v2 Announce Type: replace Abstract: Quantum algorithms for partial differential equations often assume oracle access to the geometry of the material being simulated. As explicitly specifying a geometry pixel by pixel on an exponentially large grid automatically yields an exponential cost, a central question is when such oracles can effectively be implemented by polynomially sized quantum circuits. We give explicit polynomial-size circuits for a family of geometries with exponentially many pseudorandom microscopic features. The geometry is generated by a pseudorandom procedure and a convolution with a local kernel to shape the texture. This proves to be a versatile framework, that includes materials with fixed-shape holes, spatially correlated textures, and activation--inhibition patterns. For a fixed kernel with bounded integer coefficients, the oracle cost is polynomial in the number of qubits, even when the number of microfeatures is exponential. We implement the circuit constructions in PsiQuantum Construct and verify their behaviour through numerical simulation. We also discuss why efficient access does not follow from an arbitrary description of the material, by proving worst-case query lower bounds for amplitude-encoded formation fields and databases of holes.