Pith. sign in

REVIEW 2 cited by

NP-Hardness of Tensor Network Contraction Ordering

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2310.06140 v1 pith:FTNE3NXD submitted 2023-10-09 cs.CC math.CO

Jianyu Xu , Hanwen Zhang , Ling Liang , Lei Deng , Yuan Xie , Guoqi Li This is my paper · ORCID
classification cs.CCmath.CO
keywords networktensorcontractiondifferentminimizenp-hardoptimalprove
verification ladder T0 review T1 audit T2 compute T3 formal

Signed reviews

No signed human review yet.

0 comments
read the original abstract

We study the optimal order (or sequence) of contracting a tensor network with a minimal computational cost. We conclude 2 different versions of this optimal sequence: that minimize the operation number (OMS) and that minimize the time complexity (CMS). Existing results only shows that OMS is NP-hard, but no conclusion on CMS problem. In this work, we firstly reduce CMS to CMS-0, which is a sub-problem of CMS with no free indices. Then we prove that CMS is easier than OMS, both in general and in tree cases. Last but not least, we prove that CMS is still NP-hard. Based on our results, we have built up relationships of hardness of different tensor network contraction problems.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. TensorKit.jl: A Julia package for large-scale tensor computations, with a hint of category theory

    cs.MS 2025-08 conditional novelty 7.0 of 10

    TensorKit.jl is an open-source Julia package that handles tensor operations with abelian, non-abelian, and anyonic symmetries in one framework, with order-of-magnitude speedups from symmetry exploitation.

  2. Integrating Neural Networks and Tensor Networks for Computing Free Energy

    cond-mat.stat-mech 2025-04 conditional novelty 5.0 of 10

    Tensor-network-based variational autoregressive networks (TNVAN) fix a small 'width set' of spins, contract the rest of the network exactly, and fit a neural variational distribution on the reduced system to estimate ...

Pith tools