Document Open Access Logo

Parameterization of Tensor Network Contraction

Author Bryan O'Gorman

PDF
Thumbnail PDF

File

LIPIcs.TQC.2019.10.pdf
  • Filesize: 0.56 MB
  • 19 pages

Document Identifiers

Author Details

Bryan O'Gorman
  • Berkeley Quantum Information & Computation Center, University of California, Berkeley, CA, USA
  • Quantum Artificial Intelligence Laboratory, NASA Ames, Moffett Field, CA, USA

Funding

The author was supported by a NASA Space Technology Research Fellowship.

Acknowledgements

The author thanks Benjamin Villalonga for motivating this work, useful discussions, and feedback on the manuscript.

Cite AsGet BibTex

Bryan O'Gorman. Parameterization of Tensor Network Contraction. In 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 135, pp. 10:1-10:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.TQC.2019.10

Abstract

We present a conceptually clear and algorithmically useful framework for parameterizing the costs of tensor network contraction. Our framework is completely general, applying to tensor networks with arbitrary bond dimensions, open legs, and hyperedges. The fundamental objects of our framework are rooted and unrooted contraction trees, which represent classes of contraction orders. Properties of a contraction tree correspond directly and precisely to the time and space costs of tensor network contraction. The properties of rooted contraction trees give the costs of parallelized contraction algorithms. We show how contraction trees relate to existing tree-like objects in the graph theory literature, bringing to bear a wide range of graph algorithms and tools to tensor network contraction. Independent of tensor networks, we show that the edge congestion of a graph is almost equal to the branchwidth of its line graph.

Subject Classification

ACM Subject Classification
  • Theory of computation → Fixed parameter tractability
  • Theory of computation → Quantum information theory
  • Theory of computation → Graph algorithms analysis
Keywords
  • tensor networks
  • parameterized complexity
  • tree embedding
  • congestion

Metrics

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

References

  1. Scott Aaronson and Lijie Chen. Complexity-theoretic foundations of quantum supremacy experiments. arXiv preprint, 2016. URL: http://arxiv.org/abs/1612.05903.
  2. The Parameterized Algorithms and Computational Experiments Challenge. Track A: Treewidth, December 2016. URL: https://pacechallenge.wordpress.com/pace-2017/track-a-treewidth/.
  3. Itai Arad and Zeph Landau. Quantum computation and the evaluation of tensor networks. SIAM Journal on Computing, 39(7):3089-3121, 2010. Google Scholar
  4. Stefan Arnborg and Andrzej Proskurowski. Linear time algorithms for NP-hard problems restricted to partial k-trees. Discrete applied mathematics, 23(1):11-24, 1989. Google Scholar
  5. Jacob Biamonte and Ville Bergholm. Tensor Networks in a Nutshell. arXiv e-prints, page arXiv:1708.00006, July 2017. URL: http://arxiv.org/abs/1708.00006.
  6. Jacob D. Biamonte, Jason Morton, and Jacob Turner. Tensor Network Contractions for #SAT. Journal of Statistical Physics, 160(5):1389-1404, September 2015. URL: http://dx.doi.org/10.1007/s10955-015-1276-z.
  7. Dan Bienstock. On embedding graphs in trees. Journal of Combinatorial Theory, Series B, 49(1):103-136, 1990. Google Scholar
  8. Hans L. Bodlaender. A Linear Time Algorithm for Finding Tree-decompositions of Small Treewidth. In Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing, STOC '93, pages 226-234, New York, NY, USA, 1993. ACM. URL: http://dx.doi.org/10.1145/167088.167161.
  9. Hans L Bodlaender, Michael R Fellows, and Dimitrios M Thilikos. Derivation of algorithms for cutwidth and related graph layout parameters. Journal of Computer and System Sciences, 75(4):231-244, 2009. Google Scholar
  10. Hans L. Bodlaender, John R. Gilbert, Hjálmtýr Hafsteinsson, and Ton Kloks. Approximating treewidth, pathwidth, and minimum elimination tree height. In Gunther Schmidt and Rudolf Berghammer, editors, Graph-Theoretic Concepts in Computer Science, pages 1-12, Berlin, Heidelberg, 1992. Springer Berlin Heidelberg. Google Scholar
  11. Hans L Bodlaender, John R Gilbert, Hjálmtyr Hafsteinsson, and Ton Kloks. Approximating treewidth, pathwidth, frontsize, and shortest elimination tree. J. Algorithms, 18(2):238-255, 1995. Google Scholar
  12. Hans L. Bodlaender and Dimitrios M. Thilikos. Constructive linear time algorithms for branchwidth. In Pierpaolo Degano, Roberto Gorrieri, and Alberto Marchetti-Spaccamela, editors, Automata, Languages and Programming, pages 627-637, Berlin, Heidelberg, 1997. Springer Berlin Heidelberg. Google Scholar
  13. Sergio Boixo, Sergei V Isakov, Vadim N Smelyanskiy, and Hartmut Neven. Simulation of low-depth quantum circuits as complex undirected graphical models. arXiv preprint, 2017. URL: http://arxiv.org/abs/1712.05384.
  14. Jianxin Chen, Fang Zhang, Mingcheng Chen, Cupjin Huang, Michael Newman, and Yaoyun Shi. Classical simulation of intermediate-size quantum circuits. arXiv preprint, 2018. URL: http://arxiv.org/abs/1805.01450.
  15. William Cook and Paul Seymour. Tour Merging via Branch-Decomposition. INFORMS Journal on Computing, 15(3):233-248, 2003. URL: http://dx.doi.org/10.1287/ijoc.15.3.233.16078.
  16. Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Lower Bounds Based on the Exponential-Time Hypothesis, pages 467-521. Springer International Publishing, Cham, 2015. URL: http://dx.doi.org/10.1007/978-3-319-21275-3_14.
  17. Reinhard Diestel. Graph theory. Springer Publishing Company, Incorporated, 2018. Google Scholar
  18. Eugene Dumitrescu. Tree tensor network approach to simulating Shor’s algorithm. Phys. Rev. A, 96:062322, December 2017. URL: http://dx.doi.org/10.1103/PhysRevA.96.062322.
  19. Eugene F. Dumitrescu, Allison L. Fisher, Timothy D. Goodrich, Travis S. Humble, Blair D. Sullivan, and Andrew L. Wright. Benchmarking treewidth as a practical component of tensor network simulations. PLOS ONE, 13(12):1-19, December 2018. URL: http://dx.doi.org/10.1371/journal.pone.0207827.
  20. E. Schuyler Fried, Nicolas P. D. Sawaya, Yudong Cao, Ian D. Kivlichan, Jhonathan Romero, and Alán Aspuru-Guzik. qTorch: The quantum tensor contraction handler. PLOS ONE, 13(12):1-20, December 2018. URL: http://dx.doi.org/10.1371/journal.pone.0208510.
  21. Daniel J. Harvey and David R. Wood. The treewidth of line graphs. Journal of Combinatorial Theory, Series B, 132:157-179, 2018. URL: http://dx.doi.org/10.1016/j.jctb.2018.03.007.
  22. I. Markov and Y. Shi. Simulating Quantum Computation by Contracting Tensor Networks. SIAM Journal on Computing, 38(3):963-981, 2008. URL: http://dx.doi.org/10.1137/050644756.
  23. M.I Ostrovskii. Minimal congestion trees. Discrete Mathematics, 285(1):219-226, 2004. URL: http://dx.doi.org/10.1016/j.disc.2004.02.009.
  24. Edwin Pednault, John A. Gunnels, Giacomo Nannicini, Lior Horesh, Thomas Magerlein, Edgar Solomonik, Erik W. Draeger, Eric T. Holland, and Robert Wisnieff. Breaking the 49-Qubit Barrier in the Simulation of Quantum Circuits. arXiv e-prints, page arXiv:1710.05867, October 2017. URL: http://arxiv.org/abs/1710.05867.
  25. Neil Robertson and P.D Seymour. Graph minors. X. Obstructions to tree-decomposition. Journal of Combinatorial Theory, Series B, 52(2):153-190, 1991. URL: http://dx.doi.org/10.1016/0095-8956(91)90061-N.
  26. P. D. Seymour and R. Thomas. Call routing and the ratcatcher. Combinatorica, 14(2):217-241, June 1994. URL: http://dx.doi.org/10.1007/BF01215352.
  27. Benjamin Villalonga, Sergio Boixo, Bron Nelson, Christopher Henze, Eleanor Rieffel, Rupak Biswas, and Salvatore Mandrà. A flexible high-performance simulator for the verification and benchmarking of quantum circuits implemented on real hardware. arXiv e-prints, page arXiv:1811.09599, November 2018. URL: http://arxiv.org/abs/1811.09599.
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 Imprint Privacy Contact