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

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.