The Detectability Lemma and Quantum Gap Amplification

Details The Detectability Lemma and Quantum Gap Amplification The Detectability Lemma and Quantum Gap Amplification

2008-11-20

arxiv.org/abs/0811.3412v1

Physics

Quantum Physics

30 pages, 2 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

The Detectability Lemma and Quantum Gap Amplification does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Detectability Lemma and Quantum Gap Amplification, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Detectability Lemma and Quantum Gap Amplification will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-162404