The Complexity of the Local Hamiltonian Problem
From MaRDI portal
Publication:5470726
DOI10.1137/S0097539704445226zbMath1102.81032OpenAlexW2895657145WikidataQ30054696 ScholiaQ30054696MaRDI QIDQ5470726
Oded Regev, Alexei Yu. Kitaev, Julia Kempe
Publication date: 1 June 2006
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539704445226
Quantum computation (81P68) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (58)
Two-dimensional local Hamiltonian problem with area laws is \textsf{QMA}-complete ⋮ QUANTUM WALKS ON NECKLACES AND MIXING ⋮ The power of quantum systems on a line ⋮ Testing Quantum Circuits and Detecting Insecure Encryption ⋮ On Quantum Algorithm for Binary Search and Its Computational Complexity ⋮ Improved gap estimates for simulating quantum circuits by adiabatic evolution ⋮ Dynamical structure factors of dynamical quantum simulators ⋮ Constant-round blind classical verification of quantum sampling ⋮ Quantum simulation of quantum field theories as quantum chemistry ⋮ A fast algorithm for approximating the ground state energy on a quantum computer ⋮ Undecidability of the Spectral Gap ⋮ Universal qudit Hamiltonians ⋮ Efficient quantum algorithms for simulating sparse Hamiltonians ⋮ Tensor network contractions for \#SAT ⋮ The complexity of translationally invariant spin chains with low local dimension ⋮ Entanglement in pure and thermal cluster states ⋮ A variational principle for ground spaces ⋮ Total functions in QMA ⋮ Quantum algorithm for preparing the ground state of a physical system through multi-step quantum resonant transitions ⋮ The complexity of translationally invariant low-dimensional spin lattices in 3D ⋮ Unnamed Item ⋮ A study of heuristic guesses for adiabatic quantum computation ⋮ Unnamed Item ⋮ Schrieffer-Wolff transformation for quantum many-body systems ⋮ New construction for a QMA complete three-local Hamiltonian ⋮ Toric codes and quantum doubles from two-body Hamiltonians ⋮ On the coalescence time of reversible random walks ⋮ Error-transparent evolution: the ability of multi-body interactions to bypass decoherence ⋮ Self-correcting quantum computers ⋮ Connecting the probability distributions of different operators and generalization of the Chernoff–Hoeffding inequality ⋮ Asymptotic behavior of macroscopic observables in generic spin systems ⋮ Epsilon-net method for optimizations over separable states ⋮ An introduction to quantum annealing ⋮ Realizable Hamiltonians for universal adiabatic quantum computers ⋮ On complexity of the quantum Ising model ⋮ HYPERGRAPH RAMSEY NUMBERS AND ADIABATIC QUANTUM ALGORITHM ⋮ Estimating the ground state energy of the Schrödinger equation for convex potentials ⋮ Adiabatic approximation with exponential accuracy for many-body systems and quantum computation ⋮ PERFECT, EFFICIENT, STATE TRANSFER AND ITS APPLICATION AS A CONSTRUCTIVE TOOL ⋮ The commuting local Hamiltonian problem on locally expanding graphs is approximable in \(\mathsf{NP}\) ⋮ Unnamed Item ⋮ Complexity Classification of Local Hamiltonian Problems ⋮ Product-state approximations to quantum states ⋮ Perturbation gadgets: arbitrary energy scales from a single strong interaction ⋮ Polynomial-time algorithm for simulation of weakly interacting quantum Spin systems ⋮ Minor-embedding in adiabatic quantum computation. I: The parameter setting problem ⋮ Quantum 3-SAT Is QMA$_1$-Complete ⋮ The Kitaev–Feynman clock for open quantum systems ⋮ Perturbative 2-body parent Hamiltonians for projected entangled pair states ⋮ Verification of quantum computation: an overview of existing approaches ⋮ Unifying Variational Methods for Simulating Quantum Many-Body Systems ⋮ Ground state entanglement in one-dimensional translationally invariant quantum systems ⋮ Fast universal quantum computation with railroad-switch local Hamiltonians ⋮ The theory of variational hybrid quantum-classical algorithms ⋮ Unnamed Item ⋮ Approximating ground and excited state energies on a quantum computer ⋮ QMA-Hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge ⋮ Ground-state spaces of frustration-free Hamiltonians
This page was built for publication: The Complexity of the Local Hamiltonian Problem
