[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

The commuting local Hamiltonian problem on locally expanding graphs is approximable in \(\mathsf{{NP}}\)

  • Published:
Quantum Information Processing Aims and scope Submit manuscript

Abstract

The local Hamiltonian problem is famously complete for the class \(\mathsf{{QMA}}\), the quantum analogue of \(\mathsf{{NP}}\). The complexity of its semiclassical version, in which the terms of the Hamiltonian are required to commute (the \(\mathsf{{CLH}}\) problem), has attracted considerable attention recently due to its intriguing nature, as well as in relation to growing interest in the \(\mathsf{{qPCP}}\) conjecture. We show here that if the underlying bipartite interaction graph of the \(\mathsf{{CLH}}\) instance is a good locally expanding graph, namely the expansion of any constant-size set is \(\varepsilon \)-close to optimal, then approximating its ground energy to within additive factor \(O(\varepsilon )\) lies in \(\mathsf{{NP}}\). The proof holds for \(k\)-local Hamiltonians for any constant \(k\) and any constant dimensionality of particles \(d\). We also show that the approximation problem of \(\mathsf{{CLH}}\) on such good local expanders is \(\mathsf{{NP}}\)-hard. This implies that too good local expansion of the interaction graph constitutes an obstacle against quantum hardness of the approximation problem, though it retains its classical hardness. The result highlights new difficulties in trying to mimic classical proofs (in particular, Dinur’s \(\mathsf{{PCP}}\) proof) in an attempt to prove the quantum \(\mathsf{{PCP}}\) conjecture. A related result was discovered recently independently by Brandão and Harrow, for \(2\)-local general Hamiltonians, bounding the quantum hardness of the approximation problem on good expanders, though no \(\mathsf{{NP}}\) hardness is known in that case.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. To be more precise, \(\mathsf{{QMA}}_1\)—which is defined like \(\mathsf{{QMA}}\) except in case of YES, there exists a state which is accepted with probability exactly \(1\). Here, we will not distinguish between \(\mathsf{{QMA}}\) and \(\mathsf{{QMA}}_1\) since we are not using those terms technically, but see [1] and [14].

  2. Of course, our results regarding \(\mathsf{{CLH}}\)s are stronger if they hold for graphs which satisfy weaker requirements.

  3. Assuming standard computational complexity assumptions, specifically, \(\mathsf{{NP}}\subsetneq \mathsf{{QMA}}_1\).

  4. We note that when we reduce the local dimension of a \(d\)-level qudit by \(1\), the dimension of the total Hilbert space is reduced by a factor of \((d-1)/d\); here, we are interested, however, not in the standard dimension of the entire Hilbert space but in the sum of local dimensions over all particles.

References

  1. Aaronson, S.: The quantum \({\sf PCP}\) manifesto (2006). http://www.scottaaronson.com/blog/?p=139

  2. Aharonov, D., Arad, I., Landau, Z., Vazirani, U.: The Detectability Lemma and Quantum Gap Amplification. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing. ACM, New York, NY, USA, pp. 417426 (2009)

  3. Aharonov, D., Arad, I., Vidick, T.: The Quantum \({\sf PCP}\) Conjecture Guest column: the quantum PCP conjecture. SIGACT News 44(2), 47–79 (2013)

    Article  MathSciNet  Google Scholar 

  4. Aharonov, D., Eldar, L.: On the complexity of commuting local Hamiltonians, and tight conditions for topological order in such systems. In: IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 334–343 (2011)

  5. Aharonov, D., van Dam, W., Kempe, J., Landau, Z., Lloyd, S., Regev, O.: Adiabatic quantum computation is equivalent to standard quantum computation. SIAM J. Comput. 37(1), 166–194 (2007). Conference version in Proc. 45th FOCS, pp. 42–51 (2004)

  6. Aharonov, D., Gottesman, D., Irani, S., Kempe, J.: The power of quantum systems on a line Comm. Math. Phys. 287(1), 41–65 (2009)

    Article  ADS  MATH  MathSciNet  Google Scholar 

  7. Aharonov, D., Naveh, T.: Quantum NP—A Survey arXiv:quant-ph/0210077

  8. Arad, I.: A note about a partial no-go theorem for quantum \({\sf PCP}\). Quantum Inf. Comput. 11, 1019 (2011)

    MATH  MathSciNet  Google Scholar 

  9. Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and intractability of Approximation problems. J. ACM 45(3), 501–555 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  10. Arora, S., Safra, S.: Probabilistic checking of proofs: a new characterization of \({\sf NP}\). J. ACM 45(1), 70–122 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  11. Arora, S., Barak, B., Steurer, D.: Subexponential algorithms for unique games and related problems. In: FOCS, pp. 563–572 (2010)

  12. Arora, S., Khot, S., Kolla, A., Steurer, D., Tulsiani, M., Vishnoi, N.K.: Unique games on expanding constraint graphs are easy. In: STOC, pp. 21–28 (2008)

  13. Brandão, F., Harrow, A.: Approximation Guarantees for the Quantum Local Hamiltonian Problem and Limitations for Quantum \({\sf PCP}\)s Pre-Print

  14. Bravyi, S.: Efficient algorithm for a quantum analogue of 2-SAT (2006). arXiv:quant-ph/0602108v1

  15. Bravyi, S., Vyalyi, M.: Commutative version of the k-local Hamiltonian problem and common eigenspace problem. Quantum Inf. Comput. 5(3), 187–215 (2005)

    MATH  MathSciNet  Google Scholar 

  16. Bravyi, S., DiVincenzo, D.P., Loss, D., Terhal, B.M.: Simulation of many-body Hamiltonians using perturbation theory with bounded-strength interactions. Phys. Rev. Lett. 101, 070503 (2008)

    Article  ADS  Google Scholar 

  17. Capalbo, M.R., Reingold, O., Vadhan, S., Wigderson, A.: Randomness conductors and constant-degree lossless expanders. In: Proceedings of the ACM Symposium on Theory of Computing (STOC), pp. 659–668 (2002)

  18. Dinur, I.: The \({\sf PCP}\) theorem by gap amplification. In: STOC, pp. 241–250 (2006)

  19. Dinur, I., Kaufman, T.: Locally Testable Codes and Expanders Pre-Print

  20. Freedman, M.H., Hastings, M.B.: Quantum systems on non-k-hyperfinite complexes: a generalization of classical statistical mechanics on expander graphs. arXiv: 1301.1363

  21. Gharibian, S., Kempe, J.: Approximation algorithms for QMA complete problems. SIAM J. Comput. 41(4), 1028–1050 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  22. Gharibian, S., Kempe, J.: Hardness of approximation for quantum problems. In: ICALP (1), pp. 387–398 (2012)

  23. Gottesman, D., Irani, S.: The quantum and classical complexity of translationally invariant tiling and Hamiltonian problems. In: 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’09, pp. 95–104 (2009)

  24. Håstad, J.: Some optimal inapproximability results. J. ACM 48, 798–859 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  25. Hastings, M.B.: Trivial low energy states for commuting Hamiltonians, and the quantum \({\sf PCP}\) conjecture. Quantum Inf. Comput. 13(5–6), 393–429 (2013)

    MathSciNet  Google Scholar 

  26. Khot, S.: On the power of unique 2-prover 1-round games. In: Proceedings of the 17th Annual IEEE Conference on Computational Complexity, pp. 25 (2002)

  27. Kitaev, A.Yu., Shen, A.H., Vyalyi, M.N.: Classical and Quantum Computation, vol. 47, Graduate Studies in Mathematics. AMS (2002)

  28. Kitaev, AYu.: Fault-tolerant quantum computation by anyons. Ann. Phys. 303(1), 2–30 (2003)

    Article  ADS  MATH  MathSciNet  Google Scholar 

  29. Kempe, J., Kitaev, A., Regev, O.: The complexity of the local Hamiltonian problem. SIAM J. Comput. 35(5), 1070–1097 (2006). Conference version in Proc. 24th FSTTCS, p. 372–383 (2004)

  30. Levin, Michael A., Wen, Xiao-Gang: String-net condensation: a physical mechanism for topological phases. Phys. Rev. B71, 045110 (2005)

    Article  ADS  Google Scholar 

  31. Oliveira, R., Terhal, B.M.: The complexity of quantum spin systems on a two-dimensional square lattice. Quant. Inf. Comput. 8(10), 900–924 (2008)

    MATH  MathSciNet  Google Scholar 

  32. Osborne, T.: Hamiltonian complexity. Rep. Prog. Phys. 75, 022001 (2012)

    Article  ADS  MathSciNet  Google Scholar 

  33. Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading (1994)

    MATH  Google Scholar 

  34. Raghavendra, P., Steurer, D.: Graph expansion and the unique games conjecture. In: Proceedings of the 42nd ACM symposium on Theory of computing, STOC, pp. 755–764 (2010)

  35. Raghavendra, P., Steurer, D., Tulsiani, M.: Reductions between expansion problems. In: IEEE Conference on Computational Complexity, pp. 64–73 (2012)

  36. Schuch, N.: Complexity of commuting Hamiltonians on a square lattice of qubits. Quantum Inf. Comput. 11, 901 (2011)

    MATH  MathSciNet  Google Scholar 

  37. Schuch, N., Verstraete, F.: Computational complexity of interacting electrons and fundamental limitations of density functional theory. Nat. Phys. 5, 732–735 (2009)

    Article  Google Scholar 

  38. Sipser, M., Spielman, D.: Expander codes. IEEE Trans. Inf. Theory 42(6), 1710–1722 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  39. Trevisan, L.: Approximation algorithms for unique games. In: 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 197–205 (2005)

Download references

Acknowledgments

The authors would like to thank Irit Dinur and Gil Kalai for insightful discussions and Prasad Raghavendra, Luca Trevisan and Umesh Vazirani for helpful comments. The research leading to these results has received funding from the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007-2013)/ERC Grant Agreement No. 280157, and from ISF Grant No. 1446/09.

Author information

Authors and Affiliations

  1. School of Computer Science and Engineering, The Hebrew University, Jerusalem, Israel

    Dorit Aharonov & Lior Eldar

Authors
  1. Dorit Aharonov
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Lior Eldar
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Lior Eldar.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Aharonov, D., Eldar, L. The commuting local Hamiltonian problem on locally expanding graphs is approximable in \(\mathsf{{NP}}\) . Quantum Inf Process 14, 83–101 (2015). https://doi.org/10.1007/s11128-014-0877-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11128-014-0877-9

Keywords

Search

Navigation