Track the frontier, from condensed matter to cosmology.
Search papers, labs, and topics across Lattice.
This paper establishes a quantum analogue of the Razborov-Rudich natural proofs barrier, demonstrating that natural properties of quantum states cannot be used to prove superpolynomial state-preparation lower bounds against the Magic Hierarchy, under a standard cryptographic assumption. This barrier explains the difficulty in obtaining stronger lower bounds for quantum state preparation, as many existing techniques, such as those based on approximate degree or local Hamiltonians, are shown to be natural. The work implies that new, non-natural proof techniques are likely required to achieve significant advances in state-preparation lower bounds.
Most existing quantum state-preparation lower-bound techniques are fundamentally limited by a natural proofs barrier, preventing superpolynomial bounds.
We identify a barrier that helps explain why proving stronger quantum state-preparation lower bounds has been so difficult. In particular, we establish a quantum analogue of the Razborov-Rudich natural proofs barrier for state-preparation lower bounds. We call a property of quantum states \emph{natural} if it holds for a sufficiently large fraction of Haar-random states and can be efficiently tested when given all of the state's amplitudes. Under a standard cryptographic assumption, we show that no natural property can prove superpolynomial state-preparation lower bounds even against a fixed level of the Magic Hierarchy. We show that several existing state-preparation lower-bound techniques are natural in our sense, including arguments based on approximate degree, not being a unique ground state of a local Hamiltonian, and mutual information.