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