Barriers identified for proving strong quantum state preparation limits
Natural proofs for quantum state preparation lower bounds
Computational Complexity
Summary
It’s very hard to prove strict limits on how complex it is to create certain quantum states. The authors found a new reason why: some ways of proving these limits can't work if a certain cryptographic assumption is true. They showed that many existing proof methods fall into this category, meaning new ideas are needed to prove stronger limits.
What this means in practice
- •For quantum algorithm designers: Avoid relying on natural property techniques when proving limitations on quantum state preparation complexity.
- •For quantum hardware engineers: Recognize where existing proof techniques cannot establish superpolynomial complexity lower bounds for state generation.
A theory result. No direct application yet.
Authors
Christine Li, Natalie Parham
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.