In this theoretical paper, we consider spin systems in three spatial dimensions and consider the computational complexity of estimating the ground state energy, known as the local Hamiltonian problem, for translationally invariant Hamiltonians. We prove that the local Hamiltonian problem for 3D lattices with face-centered cubic unit cells and 4-local translationally invariant interactions between spin-3/2 particles and open boundary conditions is QMAEXP-complete, where QMAEXP is the class of problems which can be verified in exponential time on a quantum computer. We go beyond a mere embedding of past hard 1D history state constructions, for which the local spin dimension is enormous: even state-of-the-art constructions have local dimension 42. We avoid such a large local dimension by combining some different techniques in a novel way. For the verifier circuit which we embed into the ground space of the local Hamiltonian, we utilize a recently developed computational model, called a quantum ring machine, which is especially well suited for translationally invariant history state constructions. This is encoded with a new and particularly simple universal gate set, which consists of a single 2-qubit gate applied only to nearest-neighbour qubits. The Hamiltonian construction involves a classical Wang tiling problem as a binary counter which translates one cube side length into a binary description for the encoded verifier input and a carefully engineered history state construction that implements the ring machine on the cubic lattice faces. These novel techniques allow us to significantly lower the local spin dimension, surpassing the best translationally invariant result to date by two orders of magnitude (in the number of degrees of freedom per coupling). This brings our models on par with the best non-translationally invariant construction.
In this theoretical paper, we consider spin systems in three spatial dimensions and consider the computational complexity of estimating the ground state energy, known as the local Hamiltonian problem, for translationally invariant Hamiltonians. We prove that the local Hamiltonian problem for 3D lattices with face-centered cubic unit cells and 4-local translationally invariant interactions between spin-3/2 particles and open boundary conditions is QMAEXP-complete, where QMAEXP is the class of problems which can be verified in exponential time on a quantum computer. We go beyond a mere embedding of past hard 1D history state constructions, for which the local spin dimension is enormous: even state-of-the-art constructions have local dimension 42. We avoid such a large local dimension by combining some different techniques in a novel way. For the verifier circuit which we embed into the ground space of the local Hamiltonian, we utilize a recently developed computational model, called a quantum ring machine, which is especially well suited for translationally invariant history state constructions. This is encoded with a new and particularly simple universal gate set, which consists of a single 2-qubit gate applied only to nearest-neighbour qubits. The Hamiltonian construction involves a classical Wang tiling problem as a binary counter which translates one cube side length into a binary description for the encoded verifier input and a carefully engineered history state construction that implements the ring machine on the cubic lattice faces. These novel techniques allow us to significantly lower the local spin dimension, surpassing the best translationally invariant result to date by two orders of magnitude (in the number of degrees of freedom per coupling). This brings our models on par with the best non-translationally invariant construction.
We prove that estimating the ground state energy of a translationally invariant, nearest-neighbour Hamiltonian on a 1D spin chain is QMAEXP -complete, even for systems of low local dimension ( ≈40 ). This is an improvement over the best previously known result by several orders of magnitude, and it shows that spin-glass-like frustration can occur in translationally invariant quantum systems with a local dimension comparable to the smallest-known non-translationally invariant systems with similar behaviour. While previous constructions of such systems rely on standard models of quantum computation, we construct a new model that is particularly well-suited for encoding quantum computation into the ground state of a translationally invariant system. This allows us to shift the proof burden from optimizing the Hamiltonian encoding a standard computational model, to proving universality of a simple model. Previous techniques for encoding quantum computation into the ground state of a local Hamiltonian allow only a linear sequence of gates, hence only a linear (or nearly linear) path in the graph of all computational states. We extend these techniques by allowing significantly more general paths, including branching and cycles, thus enabling a highly efficient encoding of our computational model. However, this requires more sophisticated techniques for analysing the spectrum of the resulting Hamiltonian. To address this, we introduce a framework of graphs with unitary edge labels. After relating our Hamiltonian to the Laplacian of such a unitary labelled graph, we analyse its spectrum by combining matrix analysis and spectral graph theory techniques.
Abstract Recent work has characterized rigorously what it means for one quantum system to simulate another and demonstrated the existence of universal Hamiltonians—simple spin lattice Hamiltonians that can replicate the entire physics of any other quantum many-body system. Previous universality results have required proofs involving complicated ‘chains’ of perturbative ‘gadgets.’ In this paper, we derive a significantly simpler and more powerful method of proving universality of Hamiltonians, directly leveraging the ability to encode quantum computation into ground states. This provides new insight into the origins of universal models and suggests a deep connection between universality and complexity. We apply this new approach to show that there are universal models even in translationally invariant spin chains in 1D. This gives as a corollary a new Hamiltonian complexity result that the local Hamiltonian problem for translationally invariant spin chains in one dimension with an exponentially small promise gap is PSPACE-complete. Finally, we use these new universal models to construct the first known toy model of 2D–1D holographic duality between local Hamiltonians.
We study the complexity of a class of problems involving satisfying constraints which remain the same under translations in one or more spatial directions. In this paper, we show hardness of a classical tiling problem on an (N x N) 2-dimensional grid and a quantum problem involving finding the ground state energy of a 1-dimensional quantum system of N particles. In both cases, the only input is N, provided in binary. We show that the classical problem is NEXP-complete and the quantum problem is QMAEXP-complete. Thus, an algorithm for these problems that runs in time polynomial in N (exponential in the input size) would imply EXP = NEXP or BQEXP = QMAEXP, respectively. Although tiling in general is already known to be NEXP-complete, to our knowledge, all previous reductions require that either the set of tiles and their constraints or some varying boundary conditions be given as part of the input. In the problem considered here, these are fixed, constant-sized parameters of the problem. Instead, the problem instance is encoded solely in the size of the system.
In this work we extend the notion of universal quantum Hamiltonians to the setting of translationally-invariant systems. We present a construction that allows a two-dimensional spin lattice with nearest-neighbour interactions, open boundaries, and translational symmetry to simulate any local target Hamiltonian---i.e. to reproduce the whole of the target system within its low-energy subspace to arbitrarily-high precision. Since this implies the capability to simulate non-translationally-invariant many-body systems with translationally-invariant couplings, any effect such as characteristics commonly associated to systems with external disorder, e.g. many-body localization, can also occur within the low-energy Hilbert space sector of translationally-invariant systems. Then we sketch a variant of the universal lattice construction optimized for simulating translationally-invariant target Hamiltonians. Finally we prove that qubit Hamiltonians consisting of Heisenberg or XY interactions of varying interaction strengths restricted to the edges of a connected translationally-invariant graph embedded in RD are universal, and can efficiently simulate any geometrically local Hamiltonian in RD.
Spin models are widely studied in the natural sciences, from investigating magnetic materials in condensed matter physics to studying neural networks. Previous work has demonstrated that there exist simple classical spin models that are universal: they can replicate—in a precise and rigorous sense—the complete physics of any other classical spin model, to any desired accuracy. However, all previously known universal models break translational invariance. In this paper we show that there exist translationally invariant universal models. Our main result is an explicit construction of a translationally invariant, 2D, nearest-neighbour, universal classical Hamiltonian with a single free parameter. The proof draws on techniques from theoretical computer science, in particular recent complexity theoretic results on tiling problems. Our results imply that there exists a single Hamiltonian which encompasses all classical spin physics, just by tuning a single parameter and varying the size of the lattice. We also prove that our construction is optimal in terms of the number of parameters in the Hamiltonian; there cannot exist a translationally invariant universal Hamiltonian with only the lattice size as a parameter.
The local Hamiltonian (LH) problem is the canonical QMA-complete problem introduced by Kitaev. In this paper, we show its hardness in a very strong sense: we show that the 3-local Hamiltonian problem on n qubits cannot be solved classically in time O(2(1−ε)n) for any ε>0 under the Strong Exponential-Time Hypothesis (SETH), and cannot be solved quantumly in time O(2(1−ε)n/2) for any ε>0 under the Quantum Strong Exponential-Time Hypothesis (QSETH). These lower bounds give evidence that the currently known classical and quantum algorithms for LH cannot be significantly improved.
Furthermore, we are able to demonstrate fine-grained complexity lower bounds for approximating the quantum partition function (QPF) with an arbitrary constant relative error. Approximating QPF with relative error is known to be equivalent to approximately counting the dimension of the solution subspace of QMA problems. We show the SETH and QSETH hardness to estimate QPF with constant relative error. We then provide a quantum algorithm that runs in O(2n) time for an arbitrary 1/poly(n) relative error, matching our lower bounds and improving the state-of-the-art algorithm by Bravyi, Chowdhury, Gosset, and Wocjan (Nature Physics 2022) in the low-temperature regime.
To prove our fine-grained lower bounds, we introduce the first size-preserving circuit-to-Hamiltonian construction that encodes the computation of a T-time quantum circuit acting on N qubits into a (d+1)-local Hamiltonian acting on N+O(T1/d) qubits. This improves the standard construction based on the unary clock, which uses N+O(T) qubits.