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.
AI Summary
The paper asks whether quantum state-preparation lower bounds face a Razborov–Rudich-type natural proofs barrier. A state property is called natural if it is classically decidable from all amplitudes at polynomially bounded precision, in time polynomial in the amplitude-list length, and holds for at least a $2^{-cn}$ fraction of Haar-random states. Thus recognition may take exponential time in the number of qubits.
Assuming classically subexponentially secure pseudorandom functions computable by polynomial-size, depth-$d$ threshold circuits, no such property can exclude every state approximately preparable by polynomial-size circuits at level $8d+20$ of the magic hierarchy, with trace-distance error $e^{-n}$. Assuming the corresponding security of the Naor–Reingold construction gives level $52$. This is a conditional limitation on proof techniques, not a state-preparation lower bound.
The proof constructs pseudorandom amplitude-list ensembles: their complete finite-precision descriptions fool classical algorithms polynomial-time in the list length, while their states have small preparation circuits. A finite Gaussian sampler and amplitude loader are implemented at fixed magic-hierarchy depth. Replacing random functions by PRFs establishes security using only classical cryptography. Several existing certificates are shown to be natural, including approximate Pauli degree, failure to be a unique local-Hamiltonian ground state, and mutual information; the mutual-information example requires clean-output preparation.
The barrier does not establish an analogous result for $\mathsf{QAC}^0$. For unitary implementation, only an abstract conditional barrier is obtained; reproducing the construction’s statistical random-function stage for full unitary matrices would imply a solution to Boolean-oracle unitary synthesis.
Little sign of AI-generated textAI use disclosedStrong assumptions
We also used AI for assistance with improving the exposition, and checking arguments.
Error found: The footnote claiming quantum security for the decisional Diffie–Hellman assumption is incorrect: Shor’s discrete-logarithm algorithm breaks that assumption, although the paper’s barrier requires only classical security.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
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.
The paper asks whether quantum state-preparation lower bounds face a Razborov–Rudich-type natural proofs barrier. A state property is called natural if it is classically decidable from all amplitudes at polynomially bounded precision, in time polynomial in the amplitude-list length, and holds for at least a 2−cn fraction of Haar-random states. Thus recognition may take exponential time in the number of qubits.
Assuming classically subexponentially secure pseudorandom functions computable by polynomial-size, depth-d threshold circuits, no such property can exclude every state approximately preparable by polynomial-size circuits at level 8d+20 of the magic hierarchy, with trace-distance error e−n. Assuming the corresponding security of the Naor–Reingold construction gives level 52. This is a conditional limitation on proof techniques, not a state-preparation lower bound.
The proof constructs pseudorandom amplitude-list ensembles: their complete finite-precision descriptions fool classical algorithms polynomial-time in the list length, while their states have small preparation circuits. A finite Gaussian sampler and amplitude loader are implemented at fixed magic-hierarchy depth. Replacing random functions by PRFs establishes security using only classical cryptography. Several existing certificates are shown to be natural, including approximate Pauli degree, failure to be a unique local-Hamiltonian ground state, and mutual information; the mutual-information example requires clean-output preparation.
The barrier does not establish an analogous result for QAC0. For unitary implementation, only an abstract conditional barrier is obtained; reproducing the construction’s statistical random-function stage for full unitary matrices would imply a solution to Boolean-oracle unitary synthesis.
Near-Optimal Bounds on the Density of Low-Energy States of k-Local Hamiltonians and Faster Quantum Algorithms
Low-energy estimation and state preparation for general k-local Hamiltonians are fundamental challenges in quantum complexity theory. Buhrman et al.~ [BGLGST, PRL 2025] recently broke the natural Grover bound O∗(2n/2) for both problems, with the improvement depending on the relative accuracy ε and the locality k. In this work, we present faster exponential quantum algorithms for these problems, where the binary entropy function governs the runtime exponent. For sufficiently small ε/k, our algorithms improve the exponent by a factor of log(k/ε) over [BGLGST, PRL 2025]. Our main technical result is an entropy-governed lower bound on the dimension of the Hamiltonian's low-energy subspace, obtained by depolarizing its ground state. For fixed k, this bound is optimal up to constant factors in the exponent. The same framework yields tighter bounds for Heisenberg, XY, and Ising models on arbitrary interaction graphs.
We introduce a technique for studying state preparation complexity in the quantum p-spin model on n qubits, a disordered quantum spin system with random interactions on every set of p qubits. We reduce the task of proving state preparation lower bounds to bounding the local profile complexity of the class, a quantity derived from the metric entropy of the set of vectors recording each state's expectation values against all weight-p Pauli strings. We show that, for sufficiently large fixed p, any class with local profile complexity O(n2) remains separated from the ground-state energy by Ω(n), a gap on the leading energy scale. When the profile complexity is o(n2), we prove the stronger conclusion that the class cannot outperform a benchmark class of simpler states at leading order. Product states always provide such a benchmark.
Our framework strengthens known bounds and covers classes beyond the reach of previous methods. These include examples where circuit lightcones extend across the entire system, preventing an application of standard arguments. We obtain an Ω(n2/logn) gate lower bound for preparing near-ground states and depth--width tradeoffs, allowing arbitrary one- and two-qubit gates and arbitrarily many discardable ancillas. We also derive lower bounds on entanglement depth and matrix product state bond dimension, and energy obstructions for forward and reverse magic at every fixed level of Parham's magic hierarchy (arXiv:2504.19966). For Clifford circuits doped with T-gates, we obtain sharper energy comparisons using product stabilizer states as a more restrictive benchmark. The proof combines an adaptation of a nonsymmetric quantum de Finetti theorem (arXiv:1810.12197) with metric-entropy bounds for the Gaussian process indexed by the local profiles of states in the class.
A central question in quantum information theory is the circuit complexity of states arising from standard many-body models. We study this question for quantum p-spin glasses, random Hamiltonians whose interactions act on p-tuples of qubits through Pauli strings. Anschuetz, Gamarnik, and Kiani (arXiv:2404.07231) showed that the optimum energy is separated from the best energy achievable by product states. This leaves open whether shallow circuits can close the gap, since even depth-one circuits can generate entanglement.
We show that the entanglement needed to close the product-state gap cannot be generated at shallow depth. When the average interaction degree grows with n, we prove that, for all sufficiently large fixed p, any circuit preparing an n-qubit state whose normalized energy is within a fixed positive constant of the optimum must have depth Ωp(logn). In the bounded-average-degree regime, we prove a fixed-depth obstruction: for every fixed D, a sufficiently large degree prefactor rules out depth-D preparation of near-ground states. Both results hold uniformly over circuits with an arbitrary number of ancilla qubits.
Our results give an obstruction in the spirit of the No Low-Energy Trivial States problem of Freedman and Hastings (arXiv:1301.1363), but for random quantum spin glasses rather than code-based Hamiltonians such as those of Anshu, Breuckmann, and Nirkhe (arXiv:2206.13228), whose ground states admit polynomial-size preparation circuits. This setting opens a probabilistic route to NLTS-like questions: we recast state-preparation lower bounds for random quantum Hamiltonians as uniform control of Gaussian processes indexed by shallow circuits.
Tight bounds on quantum sample complexity and quantum query complexity have been known for various computational problems in the literature, whereas tight bounds on quantum time complexity (i.e., the size of quantum circuits) remain unresolved. In this paper, we provide a framework to establish lower bounds on the quantum time complexity for testing permutation-invariant properties of quantum states, via a reduction from quantum sample complexity. As an application, we obtain a series of matching lower bounds when given sample access to the input quantum states, including:
1. The SWAP test due to Buhrman, Cleve, Watrous, and de Wolf (Phys. Rev. Lett. 2001) is time-optimal to estimate the purity tr(ρ2) and the inner product tr(ρσ).
2. The Shift test due to Ekert, Alves, Oi, Horodecki, Horodecki, and Kwek (Phys. Rev. Lett. 2002) is time-optimal to estimate the high-order functionals tr(ρk).
3. The productness tester for multipartite pure states due to Harrow and Montanaro (J. ACM 2013) is time-optimal.
4. The LMR protocol due to Lloyd, Mohseni, and Rebentrost (Nat. Phys. 2014) is time-optimal to implement the reflection operator about a pure state.
5. The samplizer due to Wang and Zhang (IEEE Trans. Inf. Theory 2025) is time-optimal for pure states.
6. The estimator for pure-state trace distance and fidelity due to Wang and Zhang (ICALP 2026) is time-optimal.
To the best of our knowledge, this is the first method that allows us to systematically establish tight lower bounds on quantum time complexity.
The last decade witnessed a great surge of fruitful studies in the new paradigm of quantum computing. Remarkable progress has been made in all the areas including quantum algorithms, quantum complexity theory, quantum error-correcting code, quantum information theory, quantum cryptography and physical implementations of quantum computers. However, quantum algorithm design, probably the most important task in quantum computing, did not make as much progress as people expected. This thesis aims at both designing new quantum algorithms and studying why efficient quantum algorithms are so hard to design by proving many lower bounds on quantum query complexity for various problems.
We first review (and generalize) known techniques for designing quantum algorithms and for proving quantum lower bounds. Using these techniques, we then study the quantum query complexity for many problems, including some specific problems such as Graph Matching and other natural graph properties, the general tuple search, and local search. We also study the lowest possible quantum query complexity for a class of functions as a whole, such as graph properties, circular functions, and functions invariant of a transitive permutation group, where tight results are given in all these cases.
Finally for the quantum lower bounds techniques themselves, we study the main two techniques and show that they are incomparable in power. For the most widely used one, which has a lot of parameters to choose, we show limitations for it in terms of certificate complexity. This implies that we cannot use the method to prove better lower bounds for almost all known open problems in this area.
A central question in quantum many-body physics is estimating the ground energy of a k-local Hamiltonian system. In this work, we present a spectral technique for certifying a lower bound on the ground energy of a random n-qubit Hamiltonian system defined as the sum of signed k-local Pauli operators. In particular, we prove that for any constant ℓ, there exists an efficiently computable length nO(ℓ) certificate that is always a lower bound on the ground energy with the promise that, with high probability over the random Hamiltonian distribution, the certificate value is an ε-good approximation of the true ground energy when the number of terms is sufficiently large. Second, we show by construction that this technique, while successful on average over random Hamiltonian systems, can fail to produce good certificates on worst-case instances. Our spectral technique for producing these certificates comes from extending classical results on k-XOR refutations to k-local Pauli Hamiltonians by crafting a quantum variant of the Kikuchi matrix for CSP refutations. To show the limitations of this technique, we prove non-commutative Sum-of-Squares lower bounds for worst-case signed k-local Pauli operators. More generally, we explore how the non-commutative Sum-of-Squares relaxation can be understood as augmenting the standard Sum-of-Squares relaxation with the commutation relations between the Pauli operators. We instantiate the resulting framework with a modification to prior quantum code-based NLTS Hamiltonians that yields stronger complexity guarantees for the low-energy space; our Hamiltonian family satisfies simultaneously (1) Ω(logn)-circuit depth lower bounds for all low-energy states, (2) constant-gap NP-hardness to approximate the ground energy, and (3) a constant-gap non-commutative Sum-of-Squares integrality gap up to Ω(n)-levels.