Why Are Stronger Quantum State-Preparation Lower Bounds So Hard to Prove?

The barrier limits proof techniques, not circuits

The paper's target is not a particular quantum circuit class but a class of arguments. A common strategy for a state-preparation lower bound is to name a property of the target state and then show that no state preparable by the allowed circuits has that property. The authors call such a property natural when it satisfies two conditions: constructivity, meaning a classical algorithm can decide the property efficiently given the full list of the state's amplitudes up to sufficient precision, and largeness, meaning the property holds for a sufficiently large fraction of Haar-random states. A property is useful against a circuit model if no state approximately preparable by that model has the property, and a lower-bound proof is natural if it can be recast this way.

Constructivity here is deliberately permissive. The algorithm may inspect all 2^n amplitudes and run in time polynomial in the length of that amplitude list, so it can be exponential in the number of qubits. The amplitude list plays the role that the truth table of a Boolean function plays in the classical natural proofs framework. This is a classical mathematical test of a state property, not an efficient physical procedure for verifying it.

The main result is conditional. Assuming that classically subexponentially secure pseudorandom functions can be implemented by polynomial-size, depth-d threshold circuits, no natural property can prove that a state cannot be e^{-n}-approximately prepared by polynomial-size circuits in the (8d+20)th level of the magic hierarchy. The cryptographic assumption is entirely classical, and it is the same assumption used to obtain the classical natural proofs barrier against TC^0 circuits. The barrier therefore constrains which proof approaches can work, not which circuits exist.

The Magic Hierarchy fixes the circuit model

The magic hierarchy is a restricted circuit model whose circuits alternate between arbitrary Clifford circuits and constant-depth circuits of one- and two-qubit gates. Its levels bound the number of alternations. The authors work inside this hierarchy for convenience and to compare directly with earlier results connecting fixed levels of the hierarchy to classical lower bounds.

That comparison matters because state-preparation lower bounds at fixed levels of the magic hierarchy were already known to imply lower bounds for fixed-depth classical threshold circuits. What was missing was a link between a notion of a natural property of quantum states and a natural property of Boolean functions. The paper avoids needing such a correspondence by placing the obstruction directly on properties of quantum states.

The barrier is not specific to the magic hierarchy. Any preparation model that can simulate the circuits preparing the states in the paper's pseudorandom amplitude-list family inherits the corresponding barrier. The hierarchy is used to track the required circuit resources and to state a quantitative bound, and the authors note that the same obstruction reaches other constant-depth models at fixed depth.

Pseudorandom amplitude lists turn usefulness into a contradiction

The central technical object is a pseudorandom amplitude-list family: an ensemble of pure states that looks Haar random even to a classical algorithm given the entire finite-precision amplitude list and time polynomial in its length. The family supports any polynomially bounded amplitude precision. A state in the family is e-approximately C-preparable if it can be prepared to error e by a polynomial-size circuit in the model C; this requires a small preparation circuit for each state, not an efficient procedure for sampling the ensemble.

The logic of the barrier is then short. If such a family can be e-approximately prepared by polynomial-size circuits in C, then no natural property is e-useful against C for state preparation. A useful natural property would reject the pseudorandom states, while largeness would make it accept a sufficiently large fraction of Haar-random states. Its recognition algorithm, guaranteed by constructivity, would therefore distinguish the two ensembles and contradict pseudorandomness.

Standard pseudorandom-state constructions do not immediately suffice. The binary phase state built from a pseudorandom function is indistinguishable from Haar random to polynomial-time quantum adversaries given polynomially many copies, but an adversary who sees the entire amplitude list can easily tell it apart, because all of its amplitudes have the same magnitude 2^{-n/2} while Haar-random states have varying amplitude magnitudes. The paper therefore follows a Gaussian-based framework, generating approximate complex Gaussian entries and normalizing the resulting vector.

Gaussian sampling plus amplitude loading hides the states

The construction has three conceptual steps. First, a random function H from n-bit strings to R-bit strings supplies the random bits that determine each amplitude, and a sampler converts those bits into an approximate Gaussian sample. When H is random, its values are independent, so the amplitudes behave like independent Gaussian samples, and after normalization the truncated amplitude lists are statistically close to those of Haar-random states.

Second, the target states must actually be preparable. A coherent sampler computes a numerical description of the amplitude associated with an input index, and an amplitude loader turns those descriptions into the actual amplitudes of the normalized state. Both components are implemented within a fixed level of the magic hierarchy, so that when H can be evaluated in a fixed level, the full preparation also remains in a fixed level.

Third, the random function is replaced by a sufficiently secure pseudorandom function. A test distinguishing the resulting amplitude lists could be turned into a distinguisher for the pseudorandom function: compute the amplitude list from the function, then run the test. Constructing the entire amplitude list takes 2^{O(n)} time, so ordinary polynomial-time pseudorandom-function security is not enough. The authors choose the security parameter to be a sufficiently large polynomial in the state and precision parameters, so that subexponential security covers both this runtime and the required distinguishing advantage. Because the distinguisher receives a classical amplitude list, the reduction needs only a classically subexponentially secure pseudorandom function, not a stronger quantum assumption.

Approximate degree, ground states, and mutual information are natural

The paper shows that several existing state-preparation lower-bound techniques are natural in its sense. These include arguments based on approximate degree, on a state not being a unique ground state of a local Hamiltonian, and on mutual information. Each of these can be recast as identifying a property that is efficiently testable from the amplitude list and holds for a large fraction of Haar-random states.

The mutual information example is worked out in the clean-output preparation model, which is required for the usefulness argument. The mutual information promise property is shown to be e_MI-useful against clean-output A1CQ state preparation, with e_MI(n) := 2^{-4n-10}. The proof applies an existing lower bound and shows that, for sufficiently large n, a state that is approximately cleanly preparable must fall into the NO-set. A corresponding natural-proofs barrier therefore uses a pseudorandom amplitude-list family that is also preparable in the clean-output model.

The paper also gives a simple example of a natural proof that does work against a restricted model. Consider states whose nonidentity Pauli expectations are all bounded away from one in magnitude, max_{P != I} |<psi|P|psi>| < 0.9. This condition can be tested from the amplitude list in polynomial time and holds for Haar-random states with high probability, while every state prepared by a Clifford circuit has many nonidentity Pauli expectations with absolute value one. This certifies hardness for Clifford circuits, a restricted state-preparation model.

QAC^0 and unitary implementation remain open

The barrier applies whenever the states in the pseudorandom amplitude-list family can be prepared within the circuit model of interest. Extending it to weaker models therefore amounts to asking whether comparable families can be prepared with fewer computational resources. A particularly interesting target is QAC^0, which is contained in the more powerful constant-depth models captured by the magic hierarchy but is conjectured to be strictly weaker.

Recent work suggests existing techniques are approaching a threshold. With polynomially many unrestricted ancillas, the strongest known lower bounds only reach very small constant depths; for arbitrary constant depth, known results require additional restrictions on the number of ancillas or circuit size. One result shows that a depth-d QAC^0 circuit computing PARITY needs at least n^{1+3^{-d}} ancillas, and the authors of that work observe that strengthening this to n^{1+exp(-o(d))} would already imply PARITY is not in QAC^0.

Pseudorandom unitaries, and hence pseudorandom states in the usual copy-access sense, can be implemented with high accuracy by polynomial-size QAC^0 circuits. What is insufficient for the barrier is the security guarantee: the existing construction is secure only against quasipolynomial-time adversaries, whereas a distinguisher given the entire amplitude list may run in 2^{O(n)} time. Strengthening that security would give a promising route to a natural-proofs barrier for QAC^0.

For unitary implementation, the paper formulates a corresponding notion of a natural unitary property and identifies the pseudorandom matrix object that would imply a barrier, but does not construct that object from a cryptographic assumption. The unitary setting appears qualitatively harder: reproducing the statistical random-function stage for full unitary matrices with efficient Boolean-oracle implementations would already resolve the Aaronson-Kuperberg unitary synthesis problem. The authors show that statistical closeness of finite-precision matrix descriptions at precision T = n+10 would yield unitary synthesis with polynomial query complexity, polynomial Boolean-oracle input length, and diamond-norm error at most 1/10.

The decisive question is whether a technique is natural

For readers assessing a proposed state-preparation lower bound, the paper's most useful distinction is not which circuit class the bound targets but whether the proof is natural. If a technique can be recast as a property that is efficiently testable from the full amplitude list and holds for a large fraction of Haar-random states, then under the stated classical cryptographic assumption it cannot establish superpolynomial lower bounds even against a fixed level of the magic hierarchy. The concrete corollary makes the level explicit: if the Naor-Reingold pseudorandom function construction is classically subexponentially secure, no natural property is useful against polynomial-sized circuits in the 52nd level of the magic hierarchy for state preparation.

This reframes the practical priority. The interesting frontier is not simply pushing a known natural technique to a stronger circuit model, because the barrier travels with the technique. Progress requires either a proof approach that is not natural in this sense, or a pseudorandom amplitude-list family that cannot be prepared within the model being studied. The QAC^0 case illustrates the second route: the missing ingredient is a construction whose security holds against a distinguisher running in 2^{O(n)} time, not merely against a quasipolynomial-time one.

The paper's own boundary is equally specific. The barrier is conditional on a classically subexponentially secure pseudorandom function implementable by polynomial-size, depth-d threshold circuits, and it is stated for e^{-n}-approximate preparation. It does not show that strong state-preparation lower bounds are impossible, and it does not construct the pseudorandom matrix object needed for the unitary analogue. What it does show is that a broad class of existing arguments, including approximate degree, unique-ground-state obstructions, and mutual information, cannot by themselves deliver the stronger bounds, so the next step has to come from outside that class.

Sources used in this answer