The detectability lemma and quantum gap amplification
From MaRDI portal
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 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 decomposition provide a handle on the structure of local Hamiltonians and their ground states.
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
Cited in
(25)- 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}\)
- Correlation length in random MPS and PEPS
- Entanglement subvolume law for 2D frustration-free spin systems
- Complete entropic inequalities for quantum Markov chains
- Mathematical open problems in projected entangled pair states
- Quantum Gibbs samplers: the commuting case
- QMA with subset state witnesses
- Stronger methods of making quantum interactive proofs perfectly complete
- A note about a partial no-go theorem for quantum PCP
- Quantum locally testable codes
- Stability of frustration-free Hamiltonians
- Divide and conquer method for proving gaps of frustration free Hamiltonians
- scientific article; zbMATH DE number 7650098 (Why is no real title available?)
- On the complexity of two dimensional commuting local Hamiltonians
- Product-state approximations to quantum states
- Entropy decay for Davies semigroups of a one dimensional quantum lattice
- NLTS Hamiltonians from good quantum codes
- Commitments to quantum states
- Interactive oracle arguments in the QROM and applications to succinct verification of quantum computation
- Guidable local Hamiltonian problems with implications to heuristic ansatz state preparation and the quantum PCP conjecture
- Circuit lower bounds for low-energy states of quantum code Hamiltonians
- Pseudorandomness properties of random reversible circuits
- Rapid thermalization of dissipative many-body dynamics of commuting Hamiltonians
- Quantum interactive oracle proofs
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)
