2025/07/24 by Ghosh, Soumik, Subramanian, Sathyawageeswar, Zhan, Wei
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph)
paper · doi:10.48550/arxiv.2507.18796
Quantum computational pseudorandomness has emerged as a fundamental notion that spans connections to complexity theory, cryptography and fundamental physics. However, all known constructions of efficient quantum-secure pseudorandom objects rely on complexity theoretic assumptions. In this work, we establish the first unconditionally secure efficient pseudorandom constructions against shallow-depth quantum circuit classes. We prove that: \bullet Any quantum state 2-design yields unconditional pseudorandomness against both QNC0 circuits with arbitrarily many ancillae and AC0\circQNC0 circuits with nearly linear ancillae. \bullet Random phased subspace states, where the phases are picked using a 4-wise independent function, are unconditionally pseudoentangled against the above circuit classes. \bullet Any unitary 2-design yields unconditionally secure parallel-query pseudorandom unitaries against geometrically local QNC0 adversaries, even with limited AC0 postprocessing. Our indistinguishability results for 2-designs stand in stark contrast to the standard setting of quantum pseudorandomness against BQP circuits, wherein they can be distinguishable from Haar random ensembles using more than two copies or queries. Our work demonstrates that quantum computational pseudorandomness can be achieved unconditionally for natural classes of restricted adversaries, opening new directions in quantum complexity theory.