Tensor network states offer a memory-efficient compression of quantum many-body states with limited amounts of local entanglement, such as ground-states of local Hamiltonians. This representation forms the basis of common numerical techniques such as DMRG that enable one to efficiently simulate quantum many-body ground-states in 1d systems. Yet, many tasks: including simulating higher-dimensional systems, gapless or critical states, or non-equilibrium dynamics remain challenging. In this talk I will explore the frontier for tensor network calculations on two fronts: 1) I will exploit a mathematical mapping between 2d tensor network with random tensors and free-energies in a statistical mechanics model of generalized magnetism, in order to investigate the universal properties and phase transitions in the difficulty of carrying out 2d tensor network calculations on a quantum computer. 2) I will also describe theoretical and experimental progress in using quantum circuit generated tensor networks to simulate large many-body systems with small quantum computes, and discuss the prospects for achieving a practical quantum advantage for quantum materials questions of scientific and technological relevance using these methods.