The detectability lemma and quantum gap amplification

DOI10.1145/1536414.1536472zbMATH Open1304.68049arXiv0811.3412OpenAlexW2007370826WikidataQ130925570 ScholiaQ130925570MaRDI QIDQ5172736FDOQ5172736

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

Publication date: 4 February 2015

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

Abstract: The quantum analogue of a constraint satisfaction problem is a sum of local Hamiltonians - each local Hamiltonian specifies a local constraint whose violation contributes to the energy of the given quantum state. Formalizing the intuitive connection between the ground (minimal) energy of the Hamiltonian and the minimum number of violated constraints is problematic, since the number of constraints being violated is not well defined when the terms in the Hamiltonian do not commute. The detectability lemma proved in this paper provides precisely such a quantitative connection. We apply the lemma to derive a quantum analogue of a basic primitive in classical complexity: amplification of probabilities by random walks on expander graphs. It holds under the restriction that the interaction graph of the local Hamiltonian is an expander. Our proofs are based on a novel structure imposed on the Hilbert space that we call the $XY$ decomposition, which enables a reduction from the quantum non-commuting case to the commuting case (where many classical arguments go through). The results may have several interesting implications. First, proving a quantum analogue to the PCP theorem is one of the most important challenges in quantum complexity theory. Our quantum gap amplification lemma may be viewed as the quantum analogue of the first of the three main steps in Dinur's PCP proof. Quantum gap amplification may also be related to spectral gap amplification, and in particular, to fault tolerance of adiabatic computation. Finally, the detectability lemma, and the $XY$ decomposition provide a handle on the structure of local Hamiltonians and their ground states.

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

Recommendations

• The quantum detection problem: a survey
• Quantum detection and estimation theory
• On detection of quasiclassical states
• The detection loophole in Hardy's nonlocality theorem and minimum detection efficiency.
• Leggett-Garg inequality and quantumness under the influence of random telegraph noise
• Noncommuting observables in quantum detection and estimation theory
• Discriminating qubit amplitude damping channels
• Quantum nonlocality with arbitrary limited detection efficiency
• On the moment limit of quantum observables, with an application to the balanced homodyne detection

zbMATH Keywords

quantum computationPCPgap amplificationQMAlocal Hamiltoniansdetectability lemma

Mathematics Subject Classification ID

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

Cited In (20)

• Stability of frustration-free Hamiltonians
• Stronger methods of making quantum interactive proofs perfectly complete
• Product-state approximations to quantum states
• Spectral gaps for the two-species product vacua and boundary states models on the \(d\)-dimensional lattice
• Title not available (Why is that?)
• A note about a partial no-go theorem for quantum PCP
• The commuting local Hamiltonian problem on locally expanding graphs is approximable in \(\mathsf{NP}\)
• QMA with subset state witnesses
• Quantum Gibbs samplers: the commuting case
• Entanglement subvolume law for 2D frustration-free spin systems
• On the complexity of two dimensional commuting local Hamiltonians
• Entropy decay for Davies semigroups of a one dimensional quantum lattice
• Interactive oracle arguments in the QROM and applications to succinct verification of quantum computation
• Correlation length in random MPS and PEPS
• Quantum locally testable codes
• Commitments to quantum states
• NLTS Hamiltonians from good quantum codes
• Divide and conquer method for proving gaps of frustration free Hamiltonians
• Complete entropic inequalities for quantum Markov chains
• Mathematical open problems in projected entangled pair states

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

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