Document Open Access Logo

Hamiltonian Sparsification and Gap-Simulation

Authors Dorit Aharonov, Leo Zhou

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2019.2.pdf
  • Filesize: 0.75 MB
  • 21 pages

Document Identifiers

Author Details

Dorit Aharonov
  • School of Computer Science and Engineering, The Hebrew University, Jerusalem 91904, Israel
Leo Zhou
  • Department of Physics, Harvard University, Cambridge, MA 02138, USA

Funding

  • Aharonov, Dorit: Supported by ERC grant 280157, ISF grant No. 039-9494.
  • Zhou, Leo: Supported by ERC grant 280157, MIT MISTI.

Cite As Get BibTex

Dorit Aharonov and Leo Zhou. Hamiltonian Sparsification and Gap-Simulation. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 2:1-2:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ITCS.2019.2

Abstract

Analog quantum simulation - simulation of one Hamiltonian by another - is one of the major goals in the noisy intermediate-scale quantum computation (NISQ) era, and has many applications in quantum complexity. We initiate the rigorous study of the physical resources required for such simulations, where we focus on the task of Hamiltonian sparsification. The goal is to find a simulating Hamiltonian H~ whose underlying interaction graph has bounded degree (this is called degree-reduction) or much fewer edges than that of the original Hamiltonian H (this is called dilution). We set this study in a relaxed framework for analog simulations that we call gap-simulation, where H~ is only required to simulate the groundstate(s) and spectral gap of H instead of its full spectrum, and we believe it is of independent interest.
Our main result is a proof that in stark contrast to the classical setting, general degree-reduction is impossible in the quantum world, even under our relaxed notion of gap-simulation. The impossibility proof relies on devising counterexample Hamiltonians and applying a strengthened variant of Hastings-Koma decay of correlations theorem. We also show a complementary result where degree-reduction is possible when the strength of interactions is allowed to grow polynomially. Furthermore, we prove the impossibility of the related sparsification task of generic Hamiltonian dilution, under a computational hardness assumption. We also clarify the (currently weak) implications of our results to the question of quantum PCP. Our work provides basic answers to many of the "first questions" one would ask about Hamiltonian sparsification and gap-simulation; we hope this serves as a good starting point for future research of these topics.

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum computation theory
Keywords
  • quantum simulation
  • quantum Hamiltonian complexity
  • sparsification
  • quantum PCP

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. See extended version at URL: http://arxiv.org/abs/1804.11084.
  2. D. Aharonov, I. Arad, and S. Irani. Efficient algorithm for approximating one-dimensional ground states. Phys. Rev. A, 82:012315, 2010. Google Scholar
  3. D. Aharonov, I. Arad, and T. Vidick. The Quantum PCP Conjecture. ACM SIGACT News, 44:47-79, 2013. Google Scholar
  4. D. Aharonov and M. Ben-Or. Fault-tolerant Quantum Computation with Constant Error. In Proceedings of the 29th ACM Symposium on Theory of Computing, STOC '97, pages 176-188, 1997. Google Scholar
  5. D. Aharonov and L. Eldar. On the Complexity of Commuting Local Hamiltonians, and Tight Conditions for Topological Order in Such Systems. In Proceedings of the 52nd Symposium on Foundations of Computer Science, FOCS '11, pages 334-343, 2011. Google Scholar
  6. D. Aharonov and L. Eldar. The Commuting Local Hamiltonian Problem on Locally Expanding Graphs is Approximable in NP. Quantum Information Processing, 14(1):83-101, 2015. Google Scholar
  7. D. Aharonov, A. W. Harrow, Z. Landau, D. Nagaj, M. Szegedy, and U. Vazirani. Local Tests of Global Entanglement and a Counterexample to the Generalized Area Law. In Proceedings of the 55th Symposium on Foundations of Computer Science, FOCS '14, pages 246-255, 2014. Google Scholar
  8. D. Aharonov and T. Naveh. Quantum NP - A Survey. CoRR, 2002. URL: http://arxiv.org/abs/quant-ph/0210077.
  9. D. Aharonov, W. van Dam, J. Kempe, Z. Landau, S. Lloyd, and O. Regev. Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation. SIAM J. Comput., 37(1):166-194, 2007. Google Scholar
  10. R. Ahlswede and A. Winter. Strong converse for identification via quantum channels. IEEE Transactions on Information Theory, 48(3):569-579, 2002. Google Scholar
  11. I. Arad. A Note About a Partial No-go Theorem for Quantum PCP. Quantum Info. Comput., 11(11-12):1019-1027, 2011. Google Scholar
  12. A. Aspuru-Guzik and P. Walther. Photonic quantum simulators. Nature Physics, 8(4):285-291, 2012. Google Scholar
  13. Y. Atia and D. Aharonov, 2018. in preparation. Google Scholar
  14. J. Batson, D. A. Spielman, and N. Srivastava. Twice-Ramanujan Sparsifiers. SIAM J. Comput., 41:1704-1721, 2012. Google Scholar
  15. J. Batson, D. A. Spielman, N. Srivastava, and S.-H. Teng. Spectral Sparsification of Graphs. Commun. ACM, 56:87-94, 2013. Google Scholar
  16. E. Ben-Sasson, O. Goldreich, P. Harsha, M. Sudan, and S. Vadhan. Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding. SIAM J. Comput., 36(4):889-974, 2006. Google Scholar
  17. H. Bernien et al. Probing many-body dynamics on a 51-atom quantum simulator. Nature, 551(7682):579-584, 2017. Google Scholar
  18. R. Blatt and C. F. Roos. Quantum simulations with trapped ions. Nature Physics, 8(4):277-284, 2012. Google Scholar
  19. I. Bloch, J. Dalibard, and S. Nascimbène. Quantum simulations with ultracold quantum gases. Nature Physics, 8(4):267-276, 2012. Google Scholar
  20. F.G.S.L. Brandão and A. W. Harrow. Product-state Approximations to Quantum Ground States. Comm. Math. Phys., 342:47-80, 2016. Google Scholar
  21. S. Bravyi, D. P. DiVincenzo, D. Loss, and B. M. Terhal. Quantum Simulation of Many-Body Hamiltonians Using Perturbation Theory with Bounded-Strength Interactions. Phys. Rev. Lett., 101:070503, 2008. Google Scholar
  22. S. Bravyi and M. Hastings. On complexity of the quantum Ising model. CoRR, 2014. URL: http://arxiv.org/abs/1410.0703.
  23. S. Bravyi and M. Vyalyi. Commutative Version of the Local Hamiltonian Problem and Common Eigenspace Problem. Quantum Info. Comput., 5(3):187-215, 2005. Google Scholar
  24. Y. Cao, R. Babbush, J. Biamonte, and S. Kais. Hamiltonian gadgets with reduced resource requirements. Phys. Rev. A, 91:012315, 2015. Google Scholar
  25. Y. Cao and D. Nagaj. Perturbative gadgets without strong interactions. Quantum Inf. Comput., 15:1197-1222, 2015. Google Scholar
  26. J. I. Cirac and P. Zoller. Goals and opportunities in quantum simulation. Nature Physics, 8(4):264-266, 2012. Google Scholar
  27. T. Cubitt, A. Montanaro, and S. Piddock. Universal Quantum Hamiltonians. CoRR, 2017. URL: http://arxiv.org/abs/1701.05182.
  28. T. S. Cubitt, D. Perez-Garcia, and M. M. Wolf. Undecidability of the spectral gap. Nature, 528(7581):207-211, 2015. Google Scholar
  29. H. Dell and D. van Melkebeek. Satisfiability Allows No Nontrivial Sparsification Unless the Polynomial-time Hierarchy Collapses. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC '10, pages 251-260. ACM, 2010. Google Scholar
  30. R. H. Dicke. Coherence in Spontaneous Radiation Processes. Phys. Rev., 93:99-110, 1954. Google Scholar
  31. N. G. Dickson and M. H. Amin. Algorithmic approach to adiabatic quantum optimization. Phys. Rev. A, 85:032303, 2012. Google Scholar
  32. I. Dinur. The PCP Theorem by Gap Amplification. J. ACM, 54(3), 2007. Google Scholar
  33. I. Dinur, O. Goldreich, and T. Gur. Every set in 𝒫 is strongly testable under a suitable encoding. Electronic Colloquium on Computational Complexity (ECCC), 25:50, 2018. Google Scholar
  34. E. Farhi, J. Goldstone, S. Gutman, and D. Nagaj. How to Make the Quantum Adiabatic Algorithm Fail. Int. J. Quantum Inf., 6:503-516, 2008. Google Scholar
  35. E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser. Quantum Computation by Adiabatic Evolution. CoRR, 2000. URL: http://arxiv.org/abs/quant-ph/0001106.
  36. E. Farhi and A. W Harrow. Quantum Supremacy through the Quantum Approximate Optimization Algorithm. CoRR, 2016. URL: http://arxiv.org/abs/1602.07674.
  37. R. P. Feynman. Simulating Physics with Computers. International Journal of Theoretical Physics, 21(6), 1982. Google Scholar
  38. I. M. Georgescu, S. Ashhab, and F. Nori. Quantum simulation. Rev. Mod. Phys., 86:153-185, 2014. Google Scholar
  39. M. Grifoni and P. Hänggi. Driven quantum tunneling. Physics Reports, 304(5-6):229-354, 1998. Google Scholar
  40. M. B. Hastings. Trivial Low Energy States for Commuting Hamiltonians, and the Quantum PCP Conjecture. Quantum Info. Comput., 13(5-6):393-429, 2013. Google Scholar
  41. M. B. Hastings and T. Koma. Spectral Gap and Exponential Decay of Correlations. Comm. Math. Phys., 265:781-804, 2006. Google Scholar
  42. A. A. Houck, H. E. Türeci, and J. Koch. On-chip quantum simulation with superconducting circuits. Nature Physics, 8(4):292-299, 2012. Google Scholar
  43. S. P. Jordan and E. Farhi. Perturbative gadgets at arbitrary orders. Phys. Rev. A, 77:062329, 2008. Google Scholar
  44. A. Keesling et al. Probing quantum critical dynamics on a programmable Rydberg simulator. CoRR, 2018. URL: http://arxiv.org/abs/1809.05540.
  45. J. Kempe, A. Kitaev, and O. Regev. The Complexity of the Local Hamiltonian Problem. SIAM J. Comput., 35:1070-1097, 2006. Google Scholar
  46. A. Y. Kitaev. Fault-tolerant quantum computation by anyons. Annals of Physics, 303(1):2-30, 2003. Google Scholar
  47. A. Y. Kitaev, A. Shen, and M. N. Vyalyi. Classical and Quantum Computation. American Mathematical Society, 2002. Google Scholar
  48. E. Knill, R. Laflamme, and W. H. Zurek. Resilient quantum computation: error models and thresholds. Proc. R. Soc. London, Ser. A, 454(1969):365-384, 1998. Google Scholar
  49. W. Lechner, P. Hauke, and P. Zoller. A quantum annealing architecture with all-to-all connectivity from local interactions. Science Advances, 1(9), 2015. Google Scholar
  50. M. Levin and X.-G. Wen. Detecting Topological Order in a Ground State Wave Function. Phys. Rev. Lett., 96:110405, 2006. Google Scholar
  51. E. H. Lieb and D. W. Robinson. The finite group velocity of quantum spin systems. Comm. Math. Phys., 28(3):251-257, 1972. Google Scholar
  52. S. Lloyd. Universal Quantum Simulators. Science, 273(5278):1073-8, 1996. Google Scholar
  53. M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 10th edition, 2011. Google Scholar
  54. R. Oliveira and B. M. Terhal. The complexity of quantum spin systems on a two-dimensional square lattice. Quantum Inf. Comput., 8:900-924, 2008. Google Scholar
  55. J. Preskill. Quantum Computing in the NISQ era and beyond. Quantum, 2:79, 2018. Google Scholar
  56. S. Sachdev. Quantum phase transitions. Cambridge University Press, 2011. Google Scholar
  57. M. Saffman, T. G. Walker, and K. Mølmer. Quantum information with Rydberg atoms. Rev. Mod. Phys., 82:2313-2363, 2010. Google Scholar
  58. M. K. de Carli Silva, N. J. A. Harvey, and C. M. Sato. Sparse Sums of Positive Semidefinite Matrices. ACM Trans. Algorithms, 12(1):9:1-9:17, 2015. Google Scholar
  59. J. Simon, W. S. Bakr, R. Ma, M. Eric Tai, P. M. Preiss, and M. Greiner. Quantum simulation of antiferromagnetic spin chains in an optical lattice. Nature, 472(7343):307-312, 2011. Google Scholar
  60. D. A. Spielman and N. Srivastava. Graph Sparsification by Effective Resistances. SIAM J. Comput., 40(6):1913-1926, 2011. Google Scholar
  61. D. A. Spielman and S.-H. Teng. Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems. CoRR, 2006. URL: http://arxiv.org/abs/0607105.
  62. D. A. Spielman and S.-H. Teng. Spectral Sparsification of Graphs. SIAM J. Comput., 40(4):981-1025, 2011. Google Scholar
  63. X. G. Wen. Topological order in rigid states. Int. J. Mod. Phys. B, 04(02):239-271, 1990. Google Scholar
  64. J. Zhang et al. Observation of a many-body dynamical phase transition with a 53-qubit quantum simulator. Nature, 551(7682):601-604, 2017. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact