The development of quantum computers has promised to greatly improve our understanding of quantum many-body physics. However, many physical systems display complex and unpredictable behaviour which is not amenable to analytic or even computational solutions. This thesis aims to further our understanding of what properties of physical systems a quantum computer is capable of determining, and simultaneously explore the behaviour of exotic quantum many-body systems. First, we analyse the task of determining the phase diagram of a quantum material, and thereby charting its properties as a function of some externally controlled parameter. In the general case we find that determining the phase diagram to be uncomputable, and in special cases show it is P^{QMA_{EXP}}-complete. Beyond this, we examine how a common method for determining quantum phase transitions --- the Renormalisation Group (RG) --- fails when applied to a set of Hamiltonians with uncomputable properties. We show that for such Hamiltonians (a) there is a well-defined RG procedure, but this procedure must fail to predict the uncomputable properties (b) this failure of the RG procedure demonstrates previously unseen and novel behaviour. We also formalise in terms of a promise problem, the question of computing the ground state energy per particle of a model in the limit of an infinitely large system, and show that approximating this quantity is likely intractable. In doing this we develop a new kind of complexity question concerned with determining the precision to which a single number can be determined. Finally we consider the problem of measuring local observables in the low energy subspace of systems --- an important problem for experimentalists and theorists alike. We prove that if a certain kind of construction exists for a class of Hamiltonians, , the results about hardness of determining the ground state energy directly implies hardness results for measuring observables at low energies.