REVIEW 1 cited by
The computational difficulty of finding MPS ground states
Not yet reviewed by Pith; the record is open.
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
read the original abstract
We determine the computational difficulty of finding ground states of one-dimensional (1D) Hamiltonians which are known to be Matrix Product States (MPS). To this end, we construct a class of 1D frustration free Hamiltonians with unique MPS ground states and a polynomial gap above, for which finding the ground state is at least as hard as factoring. By lifting the requirement of a unique ground state, we obtain a class for which finding the ground state solves an NP-complete problem. Therefore, for these Hamiltonians it is not even possible to certify that the ground state has been found. Our results thus imply that in order to prove convergence of variational methods over MPS, as the Density Matrix Renormalization Group, one has to put more requirements than just MPS ground states and a polynomial spectral gap.
Forward citations
Cited by 1 Pith paper
-
Optimizing Tensor Network Partitioning using Simulated Annealing
A simulated annealing refinement of tensor network partitionings for distributed contraction lowers estimated computational and memory cost by about 8x on average versus naive partitioning on MQT Bench circuits.
Discussion (0). Continue with ORCID to comment.