Complexity Classification of Local Hamiltonian Problems

DOI10.1137/140998287zbMath1353.68095arXiv1311.3161OpenAlexW2034763770WikidataQ59451003 ScholiaQ59451003MaRDI QIDQ2799351

Ashley Montanaro, Toby S. Cubitt

Publication date: 11 April 2016

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1311.3161

zbMATH Keywords

quantum computationconstraint satisfaction problemsquantum complexitylocal Hamiltonian problem

Mathematics Subject Classification ID

Quantum computation (81P68) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items (17)

Ground State Connectivity of Local Hamiltonians ⋮ The Classification of Reversible Bit Operations ⋮ Universal qudit Hamiltonians ⋮ QMA with Subset State Witnesses ⋮ The complexity of translationally invariant spin chains with low local dimension ⋮ A variational principle for ground spaces ⋮ Quantum algorithm for preparing the ground state of a physical system through multi-step quantum resonant transitions ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Approximation algorithms for quantum many-body problems ⋮ Classifying data using near-term quantum devices ⋮ On complexity of the quantum Ising model ⋮ Verifying quantum computations at scale: A cryptographic leash on quantum devices ⋮ Perturbation gadgets: arbitrary energy scales from a single strong interaction ⋮ Hardness and Ease of Curing the Sign Problem for Two-Local Qubit Hamiltonians ⋮ Translationally invariant universal quantum Hamiltonians in 1D ⋮ QMA-Hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On complexity of the quantum Ising model
• A dichotomy theorem for maximum generalized satisfiability problems.
• Boolean constraint satisfaction: Complexity results for optimization problems with arbitrary weights
• Separability of mixed states: necessary and sufficient conditions.
• An explicit universal gate-set for exchange-only quantum computation
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• Quantum 3-SAT Is QMA$_1$-Complete
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Ordering Energy Levels of Interacting Spin Systems
• On the Structure of Polynomial Time Reducibility
• Normal Forms for Skew-Symmetric Matrices and Hamiltonian Systems with First Integrals Linear in Momenta
• Realizable Hamiltonians for universal adiabatic quantum computers
• The Bose-Hubbard Model is QMA-complete
• Modern Quantum Mechanics
• The complexity of satisfiability problems
• The Complexity of the Local Hamiltonian Problem
• On the Complexity of Commuting Local Hamiltonians, and Tight Conditions for Topological Order in Such Systems

This page was built for publication: Complexity Classification of Local Hamiltonian Problems