Polynomial Approximations for Quantum Hamiltonian Complexity

Kan, Benjamin Ruoyu

Published Jan 1, 2023• 0 citations

Abstract

Quantum Hamiltonian Complexity (QHC) sits at the intersection of quantum complexity theory and quantum many-body physics. However, many results in QHC still remain disconnected across domains. The technique of polynomial approximations, derived from classical approximation theory methods, has recently seen remarkable success at proving results in QHC, and may change this detached paradigm. This thesis aims to better unify results in QHC by applying polynomial approximations to provide an alternative proof of the Lieb-Schultz-Mattis (LSM) theorem, a seminal result in condensed matter physics. The LSM theorem provides an upper bound on the spectral gap of quantum many-body systems under certain symmetry conditions, and is deeply related to topological quantum computing. We hope to provide a more elementary proof of LSM based in classical techniques, such as concentration bounds, and demonstrate new applications of the polynomial approximation technique. In this work, we outline the general approach for using polynomial approximations to prove the LSM theorem for a 1D periodic spin-1/2 chain, and characterize the valid ground states for this system. We also provide progress towards this end in the form of examples of unconcentrated LSM ground states, as well as discussing the uniform superposition ground state and alternate perspectives on a full proof or counterexample.

Related papers

An elementary proof of 1D LSM theorems

Abhishodh Prakash

The Lieb-Schultz-Mattis (LSM) theorem and its generalizations forbids the existence of a unique gapped ground state in the presence of certain lattice and internal symmetries and thus imposes powerful constraints on the low energy properties of quantum many-body systems. We provide an elementary proof of a class of generalized LSM theorems in 1D using matrix product state representations and the representation theory of groups.

arXiv:2002.11176Feb 25, 20203 citations

Approximate Degree in Classical and Quantum Computing

Mark Bun, Justin Thaler

The ability (or inability) to represent or approximate Boolean functions by polynomials is a central concept in complexity theory, underlying interactive and probabilistically checkable proof systems, circuit lower bounds, quantum complexity theory, and more. In this book, the authors survey what is known about a particularly natural notion of approximation by polynomials, capturing pointwise approximation over This book covers recent progress on proving approximate degree lower and upper bounds and describes some applications of the new bounds to oracle separations, quantum query and communication complexity, and circuit complexity. The authors explain how several of these advances have been unlocked by a particularly simple and elegant technique, called dual block composition, for constructing solutions to this dual linear program. They also provide concise coverage of even more recent lower bound techniques based on a new complexity measure called spectral sensitivity. Finally, they show how explicit constructions of approximating polynomials have been inspired by quantum query algorithms. This book provides a comprehensive review of the foundational and recent developments of an important topic in both classical and quantum computing. The reader has a considerable body of knowledge condensed in an accessible form to quickly understand the principles and further their own research.

Jan 1, 20220 citations

A polynomial-time algorithm for the ground state of 1D gapped local Hamiltonians

Zeph A. Landau, Umesh V. Vazirani, Thomas Vidick

Computing ground states of local Hamiltonians is a fundamental problem in condensed matter physics. We give the first randomized polynomial-time algorithm for finding ground states of gapped one-dimensional Hamiltonians: it outputs an (inverse-polynomial) approximation, expressed as a matrix product state (MPS) of polynomial bond dimension. The algorithm combines many ingredients, including recently discovered structural features of gapped 1D systems, convex programming, insights from classical algorithms for 1D satisfiability, and new techniques for manipulating and bounding the complexity of MPS. Our result provides one of the first major classes of Hamiltonians for which computing ground states is provably tractable despite the exponential nature of the objects involved.

arXiv:1307.5143Jul 19, 201325 citations

Polynomial-time degenerate ground state approximation of gapped 1D Hamiltonians.

Christopher T. Chubb, Steven T. Flammia

In spite of a plethora of no-go results that prevent classically efficient simulation of quantum systems in general, heuristic methods[1] have seen great success, proving typically efficient in practice. The downside of these heuristic methods is that we lack a rigorous understanding of how, and for which systems, they fail[2]. Provably efficient algorithms – even if practically surpassed by heuristic methods – are of key importance for understanding the true worst-case complexity of simulation. The cutting edge for provably efficient simulation is the ground state approximation of 1D spin systems. Under the assumption of a gap, there exists a provably efficient algorithm[3, 4] for approximation of a unique ground state of such systems; we present ongoing work to extend this algorithm to work for degenerate systems. This result comes in the wake of a recent degenerate extension of the area law[5], an important structural bound on the complexity of ground states. In practice this algorithm is no match for heuristic analogues such as the density matrix renormalisation group. However, it does add to the increasing understanding of the systems for which provably efficient simulation is attainable, and might hopefully lead to a future algorithm that is both provably and practically efficient.

Jan 1, 20140 citations

Gapped quantum systems: from higher-dimensional Lieb–Schultz–Mattis to the quantum Hall effect

Matthew B. Hastings

We consider many-body quantum systems on a finite lattice, where the Hilbert space is the tensor product of finite-dimensional Hilbert spaces associated with each site, and where the Hamiltonian of the system is a sum of local terms. We are interested in proving uniform bounds on various properties as the size of the lattice tends to infinity. An important case is when there is a spectral gap between the lowest state(s) and the rest of the spectrum which persists in this limit, corresponding to what physicists call a “phase of matter.” Here, the combination of elementary Fourier analysis with the technique of Lieb–Robinson bounds (bounds on the velocity of propagation) is surprisingly powerful. We use this to prove exponential decay of connected correlation functions, a higher-dimensional Lieb–Schultz–Mattis theorem, and a Hall conductance quantization theorem for interacting electrons with disorder.

arXiv:2111.01854EMS Press eBooksDec 15, 20233 citations

Quantum Hamiltonian complexity and the detectability lemma

Dorit Aharonov, Itai Arad, Zeph A. Landau +1 more

Quantum Hamiltonian complexity studies computational complexity aspects of local Hamiltonians and ground states; these questions can be viewed as generalizations of classical computational complexity problems related to local constraint satisfaction (such as SAT), with the additional ingredient of multi-particle entanglement. This additional ingredient of course makes generalizations of celebrated theorems such as the PCP theorem from classical to the quantum domain highly non-trivial; it also raises entirely new questions such as bounds on entanglement and correlations in ground states, and in particular area laws. We propose a simple combinatorial tool that helps to handle such questions: it is a simplified, yet more general version of the detectability lemma introduced by us in the more restricted context on quantum gap amplification a year ago. Here, we argue that this lemma is applicable in much more general contexts. We use it to provide a simplified and more combinatorial proof of Hastings' 1D area law, together with a less than 1 page proof of the decay of correlations in gapped local Hamiltonian systems in any constant dimension. We explain how the detectability lemma can replace the Lieb-Robinson bound in various other contexts, and argue that it constitutes a basic tool for the study of local Hamiltonians and their ground states in relation to various questions in quantum Hamiltonian complexity.

arXiv:1011.3445Nov 15, 20109 citations