Thiago Bergamaschi

The quantum PCP conjecture asks whether it is QMA-hard to distinguish between high- and low- energy Hamiltonians even when the gap between "high" and "low" energy is large (constant). A natural proof strategy is gap amplification: start from the fact that high- and low-energy Hamiltonians are hard to distinguish if the gap is small (inverse polynomial) [KSV02] and amplify the Hamiltonians to increase the energy gap while preserving hardness. Such a gap amplification procedure is at the heart of Dinur’s proof of the classical PCP theorem [Din07]. In this work, following Dinur’s model, we introduce a new quantum gap amplification procedure for Hamiltonians which uses random walks on expander graphs to derandomise (subsample the terms of) the tensor product amplification of a Hamiltonian. Curiously, our analysis relies on a new technique inspired by quantum de Finetti theorems, which have previously been used to rule out certain approaches to the quantum PCP conjecture [BH13].

It is shown that every one-dimensional Hamiltonian with short-range interacting spins admits a quantum Gibbs sampler [CKG23] with a system-size independent spectral gap at all finite temperatures. Consequently, their Gibbs states can be prepared in polylogarithmic depth, and satisfy exponential clustering of correlations, generalizing [Ara69].

When designing quantum circuits for a given unitary, it can be much cheaper to achieve a good approximation on most inputs than on all inputs. In this work we formalize this idea, and propose that such "optimistic quantum circuits" are often sufficient in the context of larger quantum algorithms. For the rare algorithm in which a subroutine needs to be a good approximation on all inputs, we provide a reduction which transforms optimistic circuits into general ones. Applying these ideas, we build an optimistic circuit for the in-place quantum Fourier transform (QFT). Our circuit has depth O(log(n/ϵ)) for tunable error parameter ϵ, uses n total qubits, i.e. no ancillas, is local for input qubits arranged in 1D, and is measurement-free. The circuit's error is bounded by ϵ on all input states except an ϵ-sized fraction of the Hilbert space. The circuit is also rather simple and thus may be practically useful. Combined with recent QFT-based fast arithmetic constructions, the optimistic QFT yields factoring circuits of nearly linear depth using only 2n + O(n/log n) total qubits. Additionally, we apply our reduction technique to yield an approximate QFT with well-controlled error on all inputs; it is the first to achieve the asymptotically optimal depth of O(log (n/ϵ)) with a sublinear number of ancilla qubits. The reduction uses long-range gates but no measurements.

Statistical mechanics assumes that a quantum many-body system at low temperature can be described by its Gibbs state. However, many complex quantum systems only exist as metastable states of dissipative open system dynamics, which substantially deviate from true thermal equilibrium. Why, then, should the predictions of thermal equilibrium--such as the area law--be so unreasonably effective in explaining low-temperature phenomena? In this work, we model metastable states as approximate stationary states of a quasi-local, (KMS)-detailed-balanced master equation representing Markovian system-bath interaction. We show that all metastable states exhibit universal structures that parallel true quantum Gibbs states: an area law of mutual information and a local Markov property. The more metastable the states are, the larger the regions to which these structural results apply. Behind our structural results lies a systematic framework encompassing sharp equivalences between local minima of free energy, a non-commutative Fisher information, as well as approximate detailed-balance and Kubo-Martin-Schwinger conditions, ultimately building towards a quantitative theory of thermal metastability.

We prove by construction that the Bravyi-Poulin-Terhal bound on the spatial density of stabilizer codes does not generalize to stabilizer circuits. To do so, we construct a fault tolerant quantum computer with a coding rate above 5$\%$ and quasi-polylog time overhead, out of a line of qubits with nearest-neighbor connectivity, and prove it has a threshold. The construction is based on modifications to the tower of Hamming codes of Yamasaki and Koashi (Nature Physics, 2024), with operators measured using a variant of Shor’s measurement gadget.

The ground state energy and the free energy of Quantum Local Hamiltonians are fundamental quantities in quantum many-body physics, however, it is QMA-Hard to estimate them in general. In this paper, we develop new techniques to find classical, additive error product-state approximations for these quantities on certain families of Quantum k-Local Hamiltonians. Namely, those which are either dense, have low threshold rank, or are defined on a sparse graph that excludes a fixed minor, building on the methods and the systems studied by Brandão and Harrow, Gharibian and Kempe, and Bansal, Bravyi and Terhal. We present two main technical contributions. First, we discuss a connection between product-state approximations of local Hamiltonians and combinatorial graph property testing. We develop a series of textitweak Szemer'edi regularity lemmas for k-local Hamiltonians, built on those of Frieze and Kannan and others. We use them to develop textitconstant time sampling algorithms, and to characterize the `vertex sample complexity' of the Local Hamiltonian problem, in an analog to a classical result by Alon, de la Vega, Kannan and Karpinski. Second, we build on the information-theoretic product-state approximation techniques by Brandão and Harrow, extending their results to the free energy and to an asymmetric graph setting. We leverage this structure to define families of algorithms for the free energy at low temperatures, and new algorithms for certain sparse graph families.