The detectability lemma and quantum gap amplification

DOI10.1145/1536414.1536472zbMath1304.68049arXiv0811.3412OpenAlexW2007370826MaRDI QIDQ5172736

Itai Arad, Dorit Aharonov, Umesh V. Vazirani, Zeph A. Landau

Publication date: 4 February 2015

Published in: Proceedings of the forty-first annual ACM symposium on Theory of computing (Search for Journal in Brave)

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

zbMATH Keywords

quantum computationPCPgap amplificationQMAlocal Hamiltoniansdetectability lemma

Mathematics Subject Classification ID

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

Related Items (16)

Quantum Locally Testable Codes ⋮ Quantum Gibbs samplers: the commuting case ⋮ Entanglement subvolume law for 2D frustration-free spin systems ⋮ Complete entropic inequalities for quantum Markov chains ⋮ Stability of frustration-free Hamiltonians ⋮ QMA with Subset State Witnesses ⋮ Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete ⋮ Unnamed Item ⋮ Entropy decay for Davies semigroups of a one dimensional quantum lattice ⋮ Unnamed Item ⋮ Spectral gaps for the two-species product vacua and boundary states models on the \(d\)-dimensional lattice ⋮ The commuting local Hamiltonian problem on locally expanding graphs is approximable in \(\mathsf{NP}\) ⋮ Product-state approximations to quantum states ⋮ Divide and conquer method for proving gaps of frustration free Hamiltonians ⋮ Correlation length in random MPS and PEPS ⋮ Mathematical open problems in projected entangled pair states

This page was built for publication: The detectability lemma and quantum gap amplification