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.
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.
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.
Buhrman, Patro, and Speelman presented a framework of conjectures that together form a quantum analogue of the strong exponential-time hypothesis and its variants. They called it the QSETH framework. In this paper, using a notion of quantum natural proofs (built from natural proofs introduced by Razborov and Rudich), we show how part of the QSETH conjecture that requires properties to be `compression oblivious' can in many cases be replaced by assuming the existence of quantum-secure pseudorandom functions, a standard hardness assumption. Combined with techniques from Fourier analysis of Boolean functions, we show that properties such as PARITY and MAJORITY are compression oblivious for certain circuit class Λ if subexponentially secure quantum pseudorandom functions exist in Λ, answering an open question in [Buhrman-Patro-Speelman 2021].
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.