The detectability lemma and quantum gap amplification

ABSTRACT

The quantum analogue of the constraint satisfaction problem is the fundamental physics question of finding the minimal energy state of a local Hamiltonian --- each term of the Hamiltonian specifies a local constraint whose violation contributes to the energy of the given quantum state. However, in general it is not meaningful to ask for the probability that a given quantum state violates at least one constraint; the difficulty being that the terms of the Hamiltonian do not commute. We show how to make sense of this notion under mild restrictions on the form of the Hamiltonian. We then provide two main results. We first prove the quantum detectability lemma, which states that the probability of detecting a violation of a constraint in a local Hamiltonian system is bounded from below by some constant times the minimal energy of the system. The proof reveals some intrinsic structure of the Hilbert space of local Hamiltonians, which is captured in the "exponential decay" lemma, and formalized using a novel decomposition of the Hilbert space called the XY decomposition. As an application of the detectability lemma, we prove our second main result: a quantum analogue of the classical gap amplification lemma using random walks over expander graphs, which was the seed for Dinur's celebrated new proof of the PCP theorem [6]. We hope that these results will pave the way to better understandings of the computational properties of local Hamiltonians systems, and to the evolving field of quantum Hamiltonian complexity.

REFERENCES

• 1: D. Aharonov, I. Arad, Z. Landau, and U. Vazirani. The Detectability Lemma and Quantum Gap Amplification. arXiv:0811.3412, 2008.
• 2: M. Ajtai , J. Komlos , E. Szemeredi, Deterministic simulation in LOGSPACE, Proceedings of the nineteenth annual ACM symposium on Theory of computing, p.132-140, January 1987, New York, New York, United States [doi>10.1145/28395.28410]
• 3: Sanjeev Arora , Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, New York, NY, 2009
• 4: S. Bravyi. Efficient algorithm for a quantum analogue of 2-SAT. quant-ph/0602108, 2006.
• 5: S. Bravyi, D. DiVincenzo, D. Loss, and B. Terhal. Quantum Simulation of Many-Body Hamiltonians Using Perturbation Theory with Bounded-Strength Interactions. Physical Review Letters, 101(7):70503, 2008.
• 6: Irit Dinur, The PCP theorem by gap amplification, Journal of the ACM (JACM), v.54 n.3, p.12-es, June 2007 [doi>10.1145/1236457.1236459]
• 7: E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser. Quantum Computation by Adiabatic Evolution. arXiv:quant-ph/0001106, 2000.
• 8: R. Impagliazzo , D. Zuckerman, How to recycle random bits, Proceedings of the 30th Annual Symposium on Foundations of Computer Science, p.248-253, October 30-November 01, 1989 [doi>10.1109/SFCS.1989.63486]
• 9: S. P. Jordan and E. Farhi. Perturbative gadgets at arbitrary orders. Physical Review A (Atomic, Molecular, and Optical Physics), 77(6):062329, 2008.
• 10: Julia Kempe , Alexei Kitaev , Oded Regev, The Complexity of the Local Hamiltonian Problem, SIAM Journal on Computing, v.35 n.5, p.1070-1097, 2006 [doi>10.1137/S0097539704445226]
• 11: A. Yu. Kitaev , A. H. Shen , M. N. Vyalyi, Classical and Quantum Computation, American Mathematical Society, Boston, MA, 2002
• 12: J. ’Lberg, D. Kult, and E. Sjöqvist. Robustness of the adiabatic quantum search. Physical Review A, 71(6):60312, 2005.
• 13: D. A. Lidar. Towards fault tolerant adiabatic quantum computation. Physical Review Letters, 100(16):160506, 2008.
• 14: Chris Marriott , John Watrous, Quantum Arthur---Merlin games, Computational Complexity, v.14 n.2, p.122-152, June 2005 [doi>10.1007/s00037-005-0194-x]
• 15: R. Oliveira and B. Terhal. The complexity of quantum spin systems on a two-dimensional square lattice. Quant. Inf. Comp., 8(10):0900--0924, 2008.
• 16: J. Roland and N. Cerf. Noise resistance of adiabatic quantum computation using random matrix theory. Physical Review A, 71(3):32330, 2005.
• 17: M. Sarandy and D. Lidar. Adiabatic Quantum Computation in Open Systems. Physical Review Letters, 95(25):250503, 2005.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.m Miscellaneous

Additional Classification:
  F. Theory of Computation
  F.m MISCELLANEOUS

General Terms:
Algorithms, Theory

Keywords:
PCP, QMA, detectability lemma, gap amplification, local hamiltonians, quantum computation