scientific article

zbMath1218.81032arXivquant-ph/0602108MaRDI QIDQ3001461

Sergey Bravyi

Publication date: 31 May 2011

Full work available at URL: https://arxiv.org/abs/quant-ph/0602108

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

satisfiability problemlocal Hamiltonianquantum complexity classes

Mathematics Subject Classification ID

Quantum computation (81P68) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items (14)

Entanglement subvolume law for 2D frustration-free spin systems ⋮ Quantum logic is undecidable ⋮ The complexity of translationally invariant spin chains with low local dimension ⋮ Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete ⋮ Total functions in QMA ⋮ The complexity of translationally invariant low-dimensional spin lattices in 3D ⋮ The quantum detection of projectors in finite-dimensional algebras and holography ⋮ On efficiently solvable cases of quantum \(k\)-SAT ⋮ Linear-Time Algorithm for Quantum 2SAT ⋮ The commuting local Hamiltonian problem on locally expanding graphs is approximable in \(\mathsf{NP}\) ⋮ Complexity Classification of Local Hamiltonian Problems ⋮ Perturbation gadgets: arbitrary energy scales from a single strong interaction ⋮ Quantum 3-SAT Is QMA$_1$-Complete ⋮ Gapped and gapless phases of frustration-free spin-12 chains

This page was built for publication: