How to make quantum cheese: efficient geometry oracles for exponentially many pseudorandom microstructures
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.
Related
- Efficient Quantum Algorithm for Mixed-State Quantum Geometry
- Efficient learning of Clifford disentanglers and typical t-doped unitaries with exponentially more T gates
- Derivatives of Quantum Randomness: Separating Pseudorandom Unitaries from Pseudorandom (Function-like) States
- Function-like pseudorandom unitaries generate pseudorandom quantum processes
- Quantum Pseudorandom Error-Correcting Codes
BibTeX
@misc{barthe2026make,
title = {{How to make quantum cheese: efficient geometry oracles for exponentially many pseudorandom microstructures}},
author = {Alice Barthe},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2606.00222},
eprint = {2606.00222},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.00222},
}
RIS
TY - UNPB
TI - How to make quantum cheese: efficient geometry oracles for exponentially many pseudorandom microstructures
AU - Alice Barthe
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2606.00222
UR - https://arxiv.org/abs/2606.00222
AB - 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.
ER -