Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Polynomial Approximations for Quantum Hamiltonian Complexity

Kan, Benjamin Ruoyu

Published Jan 1, 2023• 0 citations
OpenAlex

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.11176•Feb 25, 2020•8 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, 2022•0 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, 2014•0 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.01854•EMS Press eBooks•Dec 15, 2023•11 citations

Hardness of approximation for quantum problems

Sevag Gharibian, Julia Kempe

The polynomial hierarchy plays a central role in classical complexity theory. Here, we define a quantum generalization of the polynomial hierarchy, and initiate its study. We show that not only are there natural complete problems for the second level of this quantum hierarchy, but that these problems are in fact hard to approximate. Using the same techniques, we also obtain hardness of approximation for the class QCMA. Our approach is based on the use of dispersers, and is inspired by the classical results of Umans regarding hardness of approximation for the second level of the classical polynomial hierarchy [Umans, FOCS 1999]. The problems for which we prove hardness of approximation for include, among others, a quantum version of the Succinct Set Cover problem, and a variant of the local Hamiltonian problem with hybrid classical-quantum ground states.

Quantum Information and Computation•May 1, 2014•3 citations

Exact and rigorous methods in quantum many body physics

Zhiyuan Wang

Quantum many body physics is an exciting research area, involving novel phases of matter with fundamentally new properties, but is also notoriously hard due to complexity of interacting quantum systems. Some popular approaches involve approximation techniques and numerical simulations, which are known to fail in several important cases. In contrast, rigorous mathematical tools, such as exact solutions and operator inequalities, have a narrower range of applicability, but provide guaranteed results and insights into the underlying physical mechanisms. This research aims to develop new techniques in this direction and use them to explore novel phases of matter. My first direction is to construct toy models where exact solutions are possible. Such models are important as they prove that certain physical phenomena are theoretically possible in nature, and often lead to the discovery of new phases. Such insights are provided by three exactly solvable models I have discovered: (1) a family of 1D quantum spin models hosting free parastatistical quasiparticles (an exotic type of identical particles beyond fermions, bosons, and anyons), proving for the first time that parastatistics is theoretically possible as an emergent phenomenon; (2) a 3D classical Ising model whose phases are characterized by topological features of certain loop observables, suggesting existence of previously unknown classical phases and phase transitions with topological order parameters; and (3) a family of models with exact p-wave superconducting ground states demonstrating the existence of Majorana quasiparticles and non-Abelian statistics in particle number-conserving systems. My second direction is to derive rigorous bounds and exact constraints on physical observables, which are applicable to large families of quantum many-body systems. I present three directions of progress: (1) a method that dramatically improves the upper bounds on the speed of information propagation in locally-interacting systems, which significantly extends the scope of these bounds and enables new applications; (2) bounds on finite-size errors in numerical simulations of lattice systems, including quench dynamics and gapped ground states; and (3) a locality bound on gapped ground states of power-law interacting systems, which leads to a generalization of the aforementioned error bounds to such systems. These error bounds have important theoretical implications such as proving the existence of the thermodynamic limit and stability of phases, and are practically useful in determining the validity of finite-size numerical simulations.

•Aug 1, 2022•0 citations
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.
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.
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.
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.
The polynomial hierarchy plays a central role in classical complexity theory. Here, we define a quantum generalization of the polynomial hierarchy, and initiate its study. We show that not only are there natural complete problems for the second level of this quantum hierarchy, but that these problems are in fact hard to approximate. Using the same techniques, we also obtain hardness of approximation for the class QCMA. Our approach is based on the use of dispersers, and is inspired by the classical results of Umans regarding hardness of approximation for the second level of the classical polynomial hierarchy [Umans, FOCS 1999]. The problems for which we prove hardness of approximation for include, among others, a quantum version of the Succinct Set Cover problem, and a variant of the local Hamiltonian problem with hybrid classical-quantum ground states.
Quantum many body physics is an exciting research area, involving novel phases of matter with fundamentally new properties, but is also notoriously hard due to complexity of interacting quantum systems. Some popular approaches involve approximation techniques and numerical simulations, which are known to fail in several important cases. In contrast, rigorous mathematical tools, such as exact solutions and operator inequalities, have a narrower range of applicability, but provide guaranteed results and insights into the underlying physical mechanisms. This research aims to develop new techniques in this direction and use them to explore novel phases of matter. My first direction is to construct toy models where exact solutions are possible. Such models are important as they prove that certain physical phenomena are theoretically possible in nature, and often lead to the discovery of new phases. Such insights are provided by three exactly solvable models I have discovered: (1) a family of 1D quantum spin models hosting free parastatistical quasiparticles (an exotic type of identical particles beyond fermions, bosons, and anyons), proving for the first time that parastatistics is theoretically possible as an emergent phenomenon; (2) a 3D classical Ising model whose phases are characterized by topological features of certain loop observables, suggesting existence of previously unknown classical phases and phase transitions with topological order parameters; and (3) a family of models with exact p-wave superconducting ground states demonstrating the existence of Majorana quasiparticles and non-Abelian statistics in particle number-conserving systems. My second direction is to derive rigorous bounds and exact constraints on physical observables, which are applicable to large families of quantum many-body systems. I present three directions of progress: (1) a method that dramatically improves the upper bounds on the speed of information propagation in locally-interacting systems, which significantly extends the scope of these bounds and enables new applications; (2) bounds on finite-size errors in numerical simulations of lattice systems, including quench dynamics and gapped ground states; and (3) a locality bound on gapped ground states of power-law interacting systems, which leads to a generalization of the aforementioned error bounds to such systems. These error bounds have important theoretical implications such as proving the existence of the thermodynamic limit and stability of phases, and are practically useful in determining the validity of finite-size numerical simulations.