- Physical Review Journals
All JournalsPhysics Magazine
Access Provided by Xinjiang University

Physical Review E

Export citation

Export citation

Choose format for download:

Download Citation
  • Access by Xinjiang University

Tensor network method for reversible classical computation

Zhi-Cheng Yang1, Stefanos Kourtis1, Claudio Chamon1, Eduardo R. Mucciolo2, and Andrei E. Ruckenstein1

  • 1Physics Department, Boston University, Boston, Massachusetts 02215, USA
  • 2Department of Physics, University of Central Florida, Orlando, Florida 32816, USA

PDF

Phys. Rev. E 97, 033303 – Published 8 March, 2018

DOI: https://doi.org/10.1103/PhysRevE.97.033303

Abstract

We develop a tensor network technique that can solve universal reversible classical computational problems, formulated as vertex models on a square lattice [Nat. Commun. 8, 15303 (2017)]. By encoding the truth table of each vertex constraint in a tensor, the total number of solutions compatible with partial inputs and outputs at the boundary can be represented as the full contraction of a tensor network. We introduce an iterative compression-decimation (ICD) scheme that performs this contraction efficiently. The ICD algorithm first propagates local constraints to longer ranges via repeated contraction-decomposition sweeps over all lattice bonds, thus achieving compression on a given length scale. It then decimates the lattice via coarse-graining tensor contractions. Repeated iterations of these two steps gradually collapse the tensor network and ultimately yield the exact tensor trace for large systems, without the need for manual control of tensor dimensions. Our protocol allows us to obtain the exact number of solutions for computations where a naive enumeration would take astronomically long times.

View figure in article

Physics Subject Headings (PhySH)

Article Text

References (41)

  1. M. Mézard, G. Parisi, and R. Zecchina, Analytic and algorithmic solution of random satisfiability problems, Science 297, 812 (2002).
  2. M. Mezard and A. Montanari, Information, Physics, and Computation (Oxford University Press, Oxford, 2009).
  3. F. Ricci-Tersenghi, Being glassy without being hard to solve, Science 330, 1639 (2010).
  4. T. Jörg, F. Krzakala, G. Semerjian, and F. Zamponi, First-Order Transitions and the Performance of Quantum Algorithms in Random Optimization Problems, Phys. Rev. Lett. 104, 207206 (2010).
  5. A. P. Young, S. Knysh, and V. N. Smelyanskiy, First-Order Phase Transition in the Quantum Adiabatic Algorithm, Phys. Rev. Lett. 104, 020502 (2010).
  6. I. Hen and A.P. Young, Exponential complexity of the quantum adiabatic algorithm for certain satisfiability problems, Phys. Rev. E 84, 061152 (2011).
  7. E. Farhi, D. Gosset, I. Hen, A. W. Sandvik, P. Shor, A. P. Young, and F. Zamponi, Performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs, Phys. Rev. A 86, 052334 (2012).
  8. C. Chamon, E. R. Mucciolo, A. E. Ruckenstein, and Z.-C. Yang, Quantum vertex model for reversible classical computing, Nat. Commun. 8, 15303 (2017).
  9. A. Cichocki, Era of big data processing: A new approach via tensor networks and tensor decompositions, arXiv:1403.2048 (2014).
  10. N. Vervliet, O. Debals, L. Sorber, and L. De Lathauwer, Breaking the curse of dimensionality using decompositions of incomplete tensors: Tensor-based scientific computing in big data analysis, IEEE Signal Process. Mag. 31, 71 (2014).
  11. A. Cichocki, Tensor networks for big data analytics and large-scale optimization problems, arXiv:1407.3124 (2014).
  12. J. Biamonte, B. Ville, and Marco L., Tensor network methods for invariant theory, J. Phys. A: Math. Theor. 46, 475301 (2013).
  13. J. D. Biamonte, J. Morton, and J. Turner, Tensor network contractions for #sat, J. Stat. Phys. 160, 1389 (2015).
  14. J. Biamonte and V. Bergholm, Tensor networks in a nutshell, arXiv:1708.00006 (2017).
  15. C. Chamon and E. R. Mucciolo, Virtual Parallel Computing and a Search Algorithm Using Matrix Product States, Phys. Rev. Lett. 109, 030503 (2012).
  16. F. Verstraete and J. Ignacio Cirac, Renormalization algorithms for quantum-many body systems in two and higher dimensions, preprint arXiv:cond-mat/0407066 (2004).
  17. M. Levin and Cody P. Nave, Tensor Renormalization Group Approach to two-Dimensional Classical Lattice Models, Phys. Rev. Lett. 99, 120601 (2007).
  18. Z.-C. Gu, M. Levin, and X.-G. Wen, Tensor-entanglement renormalization group approach as a unified method for symmetry breaking and topological phase transitions, Phys. Rev. B 78, 205116 (2008).
  19. H. C. Jiang, Z. Y. Weng, and T. Xiang, Accurate Determination of Tensor Network State of Quantum Lattice Models in two Dimensions, Phys. Rev. Lett. 101, 090603 (2008).
  20. Z.-C. Gu and X.-G. Wen, Tensor-entanglement-filtering renormalization approach and symmetry-protected topological order, Phys. Rev. B 80, 155131 (2009).
  21. G. Evenbly and G. Vidal, Algorithms for entanglement renormalization, Phys. Rev. B 79, 144108 (2009).
  22. Z. Y. Xie, J. Chen, M. P. Qin, J. W. Zhu, L. P. Yang, and T. Xiang, Coarse-graining renormalization by higher-order singular value decomposition, Phys. Rev. B 86, 045139 (2012).
  23. G. Evenbly and G. Vidal, Tensor Network Renormalization, Phys. Rev. Lett. 115, 180405 (2015).
  24. H.-H. Zhao, Z.-Y. Xie, T. Xiang, and M. Imada, Tensor network algorithm by coarse-graining tensor renormalization on finite periodic lattices, Phys. Rev. B 93, 125115 (2016).
  25. S. Yang, Z.-C. Gu, and X.-G. Wen, Loop Optimization for Tensor Network Renormalization, Phys. Rev. Lett. 118, 110504 (2017).
  26. M. Bal, M. Mariën, J. Haegeman, and F. Verstraete, Renormalization Group Flows of Hamiltonians Using Tensor Networks, Phys. Rev. Lett. 118, 250602 (2017).
  27. H. J. Liao, Z. Y. Xie, J. Chen, Z. Y. Liu, H. D. Xie, R. Z. Huang, B. Normand, and T. Xiang, Gapless Spin-Liquid Ground State in the s=1/2 Kagome Antiferromagnet, Phys. Rev. Lett. 118, 137202 (2017).
  28. G. Evenbly, Algorithms for tensor network renormalization, Phys. Rev. B 95, 045117 (2017).
  29. A. M. Goldsborough and G. Evenbly, Entanglement renormalization for disordered systems, Phys. Rev. B 96, 155136 (2017).
  30. U. Feige, S. Goldwasser, L. Lovasz, S. Safra, and M. Szegedy, Approximating clique is almost np-complete, in Proceedings of the 32nd Annual Symposium of Foundations of Computer Science (1991), pp. 2–12.
  31. U. Schollwöck, The density-matrix renormalization group, Rev. Mod. Phys. 77, 259 (2005).
  32. S. A. Cook, The complexity of theorem-proving procedures, in Proceedings of the 3rd annual ACM symposium on Theory of computing (ACM, 1971), pp. 151–158.
  33. L. A. Levin, Universal sequential search problems, Problemy Peredachi Informatsii 9, 115 (1973).
  34. M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information (Cambridge University Press, 2004).
  35. J. Reyes, L. Zhang, S. Kourtis, C. Chamon, E. R. Mucciolo, and A. E. Ruckenstein (unpublished).
  36. V. Vedral, A. Barenco, and A. Ekert, Quantum networks for elementary arithmetic operations, Phys. Rev. A 54, 147 (1996).
  37. C. Chamon and E. R. Mucciolo, Rényi entropies as a measure of the complexity of counting problems, J. Stat. Mech.: Theor. Exp. (2013) P04008.
  38. Elizabeth Crosson, Edward Farhi, Cedric Yen-Yu Lin, Han-Hsuan Lin, and Peter Shor, Different strategies for optimization using the quantum adiabatic algorithm, arXiv:1401.7320 (2014).
  39. D. S. Steiger, T. F. Rønnow, and M. Troyer, Heavy Tails in the Distribution of time to Solution for Classical and Quantum Annealing, Phys. Rev. Lett. 115, 230501 (2015).
  40. D. Wecker, M. B. Hastings, and M. Troyer, Training a quantum optimizer, Phys. Rev. A 94, 022309 (2016).
  41. Z.-C. Yang, A. Rahmani, A. Shabani, H. Neven, and C. Chamon, Optimizing variational quantum algorithms using Pontryagin's minimum principle, Phys. Rev. X 7, 021027 (2017).

Outline

Information

Phys. Rev. E 97, 033303– Published 8 March, 2018
  • Received 6 September 2017
  • Revised 5 February 2018
Article part of CHORUS
Crossmark - Check for updates button

©2018 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation