Can quantum computers efficiently simulate materials with complex microstructures?

Quantum algorithms for materials often assume a black-box oracle that describes geometry, but building those oracles is rarely examined. This work shows that fully arbitrary microstructures with exponentially many features face Grover-search lower bounds, making efficient oracles impossible in general. However, for a broad class of pseudorandom but locally structured materials, explicit polynomial-size quantum circuits exist — a concrete step toward practical quantum simulation of real engineered materials.