A candidate application for quantum computers is to simulate the low-temperature properties of quantum systems. For this task, there is a well-studied quantum algorithm that performs quantum phase estimation on an initial trial state that has a non-negligible overlap with a low-energy state. However, it is notoriously hard to give theoretical guarantees that such a trial state can be prepared efficiently. Moreover, the heuristic proposals that are currently available, such as with adiabatic state preparation, appear insufficient in practical cases. This paper shows that, for most random sparse Hamiltonians, the maximally mixed state is a sufficiently good trial state, and phase estimation efficiently prepares states with energy arbitrarily close to the ground energy. Furthermore, any low-energy state must have non-negligible quantum circuit complexity, suggesting that low-energy states are classically nontrivial and phase estimation is the optimal method for preparing such states (up to polynomial factors). These statements hold for two models of random Hamiltonians: (i) a sum of random signed Pauli strings and (ii) a random signed d -sparse Hamiltonian. The main technical argument is based on some new results in nonasymptotic random matrix theory. In particular, a refined concentration bound for the spectral density is required to obtain complexity guarantees for these random Hamiltonians. Published by the American Physical Society 2024
Providing evidence that quantum computers can efficiently prepare low-energy or thermal states of physically relevant interacting quantum systems is a major challenge in quantum information science. A newly developed quantum Gibbs sampling algorithm [Chen et al., 2023] provides an efficient simulation of the detailed-balanced dissipative dynamics of non-commutative quantum systems. The running time of this algorithm depends on the mixing time of the corresponding quantum Markov chain, which has not been rigorously bounded except in the high-temperature regime. In this work, we establish a polylog(n) upper bound on its mixing time for various families of random n × n sparse Hamiltonians at any constant temperature. We further analyze how the choice of the jump operators for the algorithm and the spectral properties of these sparse Hamiltonians influence the mixing time. Our result places this method for Gibbs sampling on par with other efficient algorithms for preparing low-energy states of quantumly easy Hamiltonians.
We present several refinements and extensions of the statistical quantum phase estimation (SQPE) framework to address some of its key practical limitations, improving its applicability to realistic cases. Recently, a family of statistical approaches for QPE have been proposed where each run uses only a few ancillae and shorter circuits than standard QPE and thus is better suited for early fault-tolerant quantum computers that are qubit-and depth-limited. SQPE method within that family estimates the cumulative distribution function (CDF) associated with spectral density of the Hamiltonian for a given trial state by using its Fourier approximation and then identifies the first jump discontinuity of the CDF to determine the ground state energy (GSE) of the Hamiltonian. It relies on random compilation procedure based on linear combination of unitaries (LCU) decomposition of the Hamiltonian assuming positive Pauli weights and requires a good estimate of lower bound on the overlap between the trial and true ground state, both of which may be difficult to achieve in practice. We address these limitations by generalizing the random compilation procedure for negative Pauli weights and employing a changepoint detection method for determining GSE which does not rely on an estimate of this overlap. We also show that by exploiting symmetry of the Fourier series one can reduce number of circuit runs/samples by a factor of 2x while keeping the GSE estimation accuracy the same. We illustrate these new developments numerically via a quantum simulator in Qiskit.
Providing evidence that quantum computers can efficiently prepare low-energy or thermal states of physically relevant interacting quantum systems is a major challenge in quantum information science. A newly developed quantum Gibbs sampling algorithm [Chen et al., 2023] provides an efficient simulation of the detailed-balanced dissipative dynamics of non-commutative quantum systems. The running time of this algorithm depends on the mixing time of the corresponding quantum Markov chain, which has not been rigorously bounded except in the high-temperature regime. In this work, we establish a polylog(n) upper bound on its mixing time for various families of random n × n sparse Hamiltonians at any constant temperature. We further analyze how the choice of the jump operators for the algorithm and the spectral properties of these sparse Hamiltonians influence the mixing time. Our result places this method for Gibbs sampling on par with other efficient algorithms for preparing low-energy states of quantumly easy Hamiltonians.
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.
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.
Quantum algorithms for ground-state energy estimation of chemical systems require a high-quality initial state. However, initial state preparation is commonly either neglected entirely, or assumed to be solved by a simple product state like Hartree-Fock. Even if a nontrivial state is prepared, strong correlations render ground-state overlap inadequate for quality assessment. In this work, we address the initial state preparation problem with an end-to-end algorithm that and the quality of initial states, accomplishing the latter with a new metric—the energy distribution. To be able to prepare more complicated initial states, we introduce an implementation technique for states in the form of a sum of Slater determinants that exhibits significantly better scaling than all prior approaches. We also propose low-precision quantum phase estimation (QPE) for further state quality refinement. The complete algorithm is capable of generating high-quality states for energy estimation, and is shown in select cases to lower the overall estimation cost by several orders of magnitude when compared with the best single product state ansatz. More broadly, the energy distribution picture suggests that the goal of QPE should be reinterpreted as generating improvements compared to the energy of the initial state and other classical estimates: such an improvement can still be achieved even if QPE does not project directly onto the ground state. Finally, we show how the energy distribution can help in identifying potential quantum advantage. Published by the American Physical Society 2024