FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science

DOI10.1007/B104325MaRDI QIDQ5465869zbMATH OpenOpenAlexFDO

Authors Julia Kempe, Alexei Yu. Kitaev, Oded Regev

Publication date 12 August 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b104325

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum computation (81P68)

Recommendations

• The Complexity of the Local Hamiltonian Problem
• THE 2-LOCAL HAMILTONIAN PROBLEM ENCOMPASSES NP
• Complexity classification of local Hamiltonian problems
• The complexity of quantum spin systems on a two-dimensional square lattice
• New construction for a QMA complete three-local Hamiltonian

Cited in

(29)

• 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
• Complexity classification of local Hamiltonian problems
• Hardness of approximation for quantum problems
• Complexity of commuting Hamiltonians on a square lattice of qubits
• Approximation algorithms for QMA-complete problems
• scientific article; zbMATH DE number 6351479 (Why is no real title available?)
• Hardness and Ease of Curing the Sign Problem for Two-Local Qubit Hamiltonians
• Quantum SAT for a Qutrit-Cinquit Pair Is QMA 1-Complete
• Two QCMA-complete problems
• Commutative version of the local Hamiltonian problem and common eigenspace problem
• The complexity of stoquastic local Hamiltonian problems
• New construction for a QMA complete three-local Hamiltonian
• On the Hamiltonian operators for adiabatic quantum reduction of SAT
• Complexity of stoquastic frustration-free Hamiltonians
• Consistency of Local Density Matrices Is QMA-Complete
• The complexity of quantum spin systems on a two-dimensional square lattice
• The complexity of translationally invariant low-dimensional spin lattices in 3D
• THE 2-LOCAL HAMILTONIAN PROBLEM ENCOMPASSES NP
• scientific article; zbMATH DE number 7453153 (Why is no real title available?)
• On complexity of the quantum Ising model
• The Bose-Hubbard model is QMA-complete
• The Complexity of the Local Hamiltonian Problem
• On the complexity of two dimensional commuting local Hamiltonians
• Exploiting subspace constraints and \textit{ab initio} variational methods for quantum chemistry
• Quantum interactive proofs using quantum energy teleportation
• Mixing time of quantum Gibbs sampling for random sparse Hamiltonians
• Quantum sat problems with finite sets of projectors are complete for a plethora of classes
• The power of quantum systems on a line

This page was built for publication: FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5465869)