Skip to content
DraconiticResearch
Search Sources API
201,683 studies31 sourcesUpdated 15 min ago
PreprintCC BY 4.0arXiv

Natural proofs for quantum state preparation lower bounds

  • Christine Li
  • Natalie Parham
Open at sourcePDFDOICite

Abstract

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.

Related

  1. Elementary proofs of quantum lower bounds for element distinctness and k-sum
    Andris Ambainis, Martins Kokainis
    arXivPreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv
  2. Verification Meets Calibration: Bounds and Secret-Independent State Preparation with an NV-Center as a Case Study
    Ezra Acalapati, Elham Kashefi, Cica Gustiani
    arXivPreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
  3. Rigorous error bounds for dissipative thermal state preparation from weak system-bath coupling
    Christopher Ong, S. A. Parameswaran, Benedikt Placke +1
    arXivPreprintCC BY 4.0Full textQuantum physics & quantum informationStatistical & nonlinear physicsarXiv
  4. Imaginary-time-enhanced feedback-based quantum algorithms for ground-state preparation
    Thanh Nguyen Van Long, Lan Nguyen Tran, Le Bin Ho
    Physical Review ResearchPeer-reviewedPublisher termsFull textAtomic, molecular & optical physicsCrossrefDOAJAPS
  5. Quantum state preparation for weighted d-DNNF
    Steef Hegeman, Joon Hyung Lee, Alfons Laarman
    arXivPreprintarXiv licenceFull textQuantum physics & quantum informationarXiv

Cite

BibTeXRIS
BibTeX
@misc{li2026natural,
  title = {{Natural proofs for quantum state preparation lower bounds}},
  author = {Christine Li and Natalie Parham},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.06826},
  eprint = {2610.06826},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.06826},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Natural proofs for quantum state preparation lower bounds
AU  - Christine Li
AU  - Natalie Parham
PY  - 2026
DA  - 2026/10/05
PB  - arXiv
DO  - 10.48550/arxiv.2610.06826
UR  - https://arxiv.org/abs/2610.06826
AB  - 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.
ER  -