{"id":"arxiv/2610.06826","url":"https://arxiv.org/abs/2610.06826","tags":["quant-ph","cs.CC"],"score":0,"title":"Natural proofs for quantum state preparation lower bounds","domain":"quant-ph","source":"arxiv","authors":["Christine Li","Natalie Parham"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-10-05","reactions":{}}