⚛️ quantum physics

Natural proofs for quantum state preparation lower bounds

This paper establishes a quantum analogue of the Razborov-Rudich natural proofs barrier, demonstrating that under standard cryptographic assumptions, no "natural" property—defined as one holding for most Haar-random states and efficiently testable—can be used to prove superpolynomial lower bounds for quantum state preparation.

Original authors: Christine Li, Natalie Parham

Published 2026-10-06

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Christine Li, Natalie Parham

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the quest to build powerful quantum computers, scientists face a fundamental puzzle: which tasks are truly impossible for these machines to perform efficiently, and which are merely difficult because we haven't found the right algorithm yet? To answer this, researchers study the "complexity" of quantum states—the specific configurations of particles that a computer must create to solve a problem. If a state is too complex, no amount of clever engineering can prepare it quickly; it requires a circuit so deep and intricate that it would take longer than the age of the universe to build. Proving that a state is this hard to make is the holy grail of quantum theory, because it tells us where the true limits of nature lie. However, for decades, these proofs have been frustratingly elusive. The tools mathematicians use to prove such limits often hit a wall, not because the limits don't exist, but because the methods themselves are too broad to distinguish between the truly hard problems and the merely difficult ones.

A new study by Christine Li and Natalie Parham at Columbia University identifies exactly why this wall exists and shows that it is likely unbreakable using current techniques. The researchers have established a barrier for quantum state preparation that mirrors a famous obstacle discovered in classical computing decades ago. They call this the "natural proofs" barrier. In simple terms, a "natural" proof is a method that tries to show a state is hard to make by finding a specific property that the state has, which simpler circuits cannot produce. For a proof to be considered "natural," the property must be easy to check if you have the full mathematical description of the state, and it must be a property that most random states possess. The authors show that if certain standard assumptions about cryptography hold true, then no such natural property can ever prove that a state is super-polynomially hard to prepare. In other words, the very tools we use to try to prove quantum states are difficult are mathematically incapable of doing the job for the most powerful quantum circuits we can imagine.

To demonstrate this, the team constructed a specific family of quantum states that act as a perfect test case. These states are designed to look completely random to any classical observer who examines their full mathematical description, even one with unlimited time to crunch the numbers. Yet, paradoxically, these same states can be prepared by quantum circuits that are surprisingly simple and shallow, operating within a fixed level of complexity known as the "magic hierarchy." The magic hierarchy is a way of organizing quantum circuits by how many times they switch between simple, reversible operations and the more complex, non-reversible operations needed to create true quantum magic. The researchers proved that if you assume the existence of secure cryptographic functions—a standard belief in computer science—then these "fake random" states are indistinguishable from truly random ones to any classical test. Because a natural proof relies on finding a difference between the easy-to-make states and the hard ones, and because these fake random states are both easy to make and look random, any natural proof would fail. It would either reject the easy states (which it shouldn't) or accept the hard states (which it shouldn't), leaving the proof useless.

The paper goes further by examining several existing techniques that scientists have used to argue that certain states are hard to prepare. The authors show that arguments based on the "Pauli degree" (a measure of how many particles are entangled in a specific way), the uniqueness of ground states in local energy systems, and mutual information between particles all fall into the category of natural proofs. This means that these popular methods, while useful for simpler circuits, are fundamentally blocked from proving strong lower bounds against more powerful quantum models. The researchers found that these techniques are too "natural" to work; they are so good at identifying random-looking states that they cannot tell the difference between a state that is genuinely hard to create and one that is just a cleverly disguised, easy-to-make state.

This discovery does not mean that strong quantum states don't exist or that they aren't hard to make. It simply means that the current playbook for proving it is incomplete. The barrier suggests that to make progress, scientists will need to develop entirely new kinds of arguments that are not "natural"—methods that might be incredibly difficult to construct or that rely on properties that are hard to check. The study also touches on the challenge of proving limits for quantum operations, or unitaries, which are the instructions that tell a computer how to manipulate data. While the authors could not construct the same type of barrier for these operations using standard assumptions, they showed that doing so would solve another major open problem in the field, suggesting that the difficulty is even deeper there.

Ultimately, this work provides a clear map of the terrain. It tells us that the difficulty in proving quantum lower bounds is not just a lack of effort or cleverness, but a structural limitation in the logic we use. By identifying this barrier, the authors have saved the community from chasing dead ends and pointed toward the need for a new kind of mathematical insight. The path forward requires stepping outside the comfort zone of natural properties and finding a way to see the quantum world through a lens that is not so easily fooled by randomness. Until then, the strongest limits of quantum computation will remain hidden behind a wall that is, for now, mathematically impenetrable.

Technical Summary: Natural Proofs for Quantum State Preparation Lower Bounds

Problem Statement
Proving lower bounds for quantum state preparation—demonstrating that specific quantum states cannot be generated by circuits of limited resources (time, depth, or gate sets)—is a fundamental challenge in quantum complexity theory. While simple arguments like lightcone constraints work for shallow circuits, general techniques for certifying hardness in deeper or more powerful models are scarce. This difficulty mirrors the classical circuit complexity landscape, where the Razborov–Rudich "natural proofs" barrier demonstrates that, under standard cryptographic assumptions, a broad class of proof techniques (those that are "constructive" and "large") cannot establish superpolynomial lower bounds against powerful classical circuits.

This paper asks whether an analogous barrier exists for quantum state preparation. Specifically, it investigates whether general proof strategies that identify a property of a target state (which is easy to verify given the state's amplitudes and holds for most random states) can be used to prove strong lower bounds against quantum circuit models.

Methodology
The authors establish a quantum natural proofs barrier by constructing a specific family of quantum states, termed Pseudorandom Amplitude-List (PRAL) families, that satisfy two conflicting conditions:

Efficient Preparability: The states in the family can be approximately prepared by polynomial-size circuits within a fixed level of the Magic Hierarchy (a model alternating between Clifford circuits and constant-depth non-Clifford gates).
Pseudorandomness: To any classical algorithm given the full finite-precision list of amplitudes (the "amplitude list"), the states are computationally indistinguishable from Haar-random states, assuming the existence of classically subexponentially secure pseudorandom functions (PRFs).

The construction proceeds in three main stages:

Statistical Randomness via Random Functions: The authors first define target states using a uniformly random function $H: \{0,1\}^n \to \{0,1\}^R$ . By interpreting $H(x)$ as a random tape for a finite complex Gaussian sampler, they generate amplitude vectors that are statistically close to Haar-random. They prove that the truncated amplitude lists of these states are statistically indistinguishable from those of Haar-random states.
Low-Depth Preparation in the Magic Hierarchy: The core technical contribution is showing that these target states can be prepared within a fixed level of the Magic Hierarchy ( $MH$ $M H$ ). This involves two subroutines implemented coherently:
- Gaussian Sampler: A coherent circuit that evaluates the random function and applies a finite Poisson sampler to generate complex Gaussian-like amplitudes. This is implemented using parallel winner-selection techniques to avoid deep sequential comparisons, keeping the circuit within $A_8CQ$ (a specific level of the Magic Hierarchy).
- Amplitude Loader: A procedure that loads these computed amplitudes into a quantum register. Using a linear-combination-of-unitaries approach with parallel repetition and coherent selection, the authors boost the success probability of the loading process while maintaining low depth.
Cryptographic Reduction: Finally, the random function $H$ is replaced by a classically subexponentially secure PRF. The authors show that if a "natural" property could distinguish the PRAL states from Haar-random states (a requirement for a useful lower-bound proof), it would imply a distinguisher for the PRF, contradicting the cryptographic assumption.

Key Contributions and Results

Quantum Natural Proofs Barrier: The paper defines "natural" properties for quantum states as those that are constructive (decidable in polynomial time given the amplitude list) and large (holding for a $2^{-cn}$ fraction of Haar-random states).
Main Theorem (Theorem 5.6): Assuming the existence of classically subexponentially secure PRFs computable by polynomial-size depth- $d$ $d$ threshold circuits ( $TC_0$ $T C_{0}$ ), no natural property can be used to prove superpolynomial lower bounds against state preparation by polynomial-size circuits in the $(8d + 20)$ $(8 d + 20)$ -th level of the Magic Hierarchy.
- Corollary: If the Naor-Reingold PRF construction is secure, no natural property is useful against state preparation in the 52nd level of the Magic Hierarchy.
Analysis of Existing Techniques: The authors demonstrate that several existing lower-bound techniques are "natural" and thus subject to this barrier. These include:
- Arguments based on approximate Pauli degree (e.g., distinguishing CAT states from low-depth states).
- Obstructions related to being the unique ground state of a local Hamiltonian.
- Lower bounds based on mutual information.
- Arguments based on Pauli expectation values (e.g., distinguishing stabilizer states).
Unitary Implementation: The paper extends the framework to unitary implementation, defining "natural unitary properties." However, it notes that constructing a pseudorandom matrix family with efficient implementations would resolve the Aaronson-Kuperberg unitary synthesis problem, a major open problem. Thus, the unitary barrier is stated conditionally on the existence of such pseudorandom objects, which are not currently known to exist under standard assumptions.

Significance
The paper provides a "meta-theorem" explaining the difficulty of proving stronger quantum state-preparation lower bounds. It identifies a specific class of proof strategies—those relying on properties that are efficiently testable from amplitude lists and common among random states—that are fundamentally limited by classical cryptographic assumptions.

The authors emphasize that this barrier does not imply that lower bounds are impossible, but rather that any successful proof against powerful quantum circuit models (like those in the Magic Hierarchy) must either:

Rely on properties that are not constructive (e.g., requiring exponential time to verify from amplitudes).
Rely on properties that are not large (holding for only a negligible fraction of random states).
Break standard cryptographic assumptions (e.g., the existence of subexponentially secure PRFs).

By formalizing this obstruction, the work clarifies the landscape of quantum complexity theory, suggesting that qualitative new ideas beyond current "natural" techniques are likely required to separate quantum state preparation complexity from classical hardness assumptions. The paper also highlights the gap between state preparation and unitary synthesis, noting that the latter remains a harder open problem due to the lack of a known cryptographic construction for pseudorandom unitaries with efficient implementations.

More like this