Contracting projected entangled pair states is average-case hard
Jonas Haferkamp, Dominik Hangleiter, Jens Eisert, Marek Gluza
Abstract
This work shows that contraction of tensor networks is average-case hard, which means that the computation of expectation values is on average as hard as for specific configurations of highest computational hardness. This result is a stepping stone to the development of numerical algorithms to simulate strongly correlated quantum matter and at the same time contributes to the body of results on average-case hardness of physically relevant computational problems.
Topics & Concepts
ComputationWork (physics)Computational complexity theoryContraction (grammar)MathematicsQuantumStatistical physicsTensor (intrinsic definition)AlgorithmComputer scienceComputational modelQuantum computerTheoretical computer scienceMathematical optimizationPhysicsQuantum many-body systemsMachine Learning in Materials ScienceQuantum Computing Algorithms and Architecture