Discoveries in quantum materials, which are characterized by the strongly quantum-mechanical nature of electrons and atoms, have revealed exotic properties that arise from correlations. It is the promise of quantum materials for quantum information science superimposed with the potential of new computational quantum algorithms to discover new quantum materials that inspires this Review. We anticipate that quantum materials to be discovered and developed in the next years will transform the areas of quantum information processing including communication, storage, and computing. Simultaneously, efforts toward developing new quantum algorithmic approaches for quantum simulation and advanced calculation methods for many-body quantum systems enable major advances toward functional quantum materials and their deployment. The advent of quantum computing brings new possibilities for eliminating the exponential complexity that has stymied simulation of correlated quantum systems on high-performance classical computers. Here, we review new algorithms and computational approaches to predict and understand the behavior of correlated quantum matter. The strongly interdisciplinary nature of the topics covered necessitates a common language to integrate ideas from these fields. We aim to provide this common language while weaving together fields across electronic structure theory, quantum electrodynamics, algorithm design, and open quantum systems. Our Review is timely in presenting the state-of-the-art in the field toward algorithms with nonexponential complexity for correlated quantum matter with applications in grand-challenge problems. Looking to the future, at the intersection of quantum information science and algorithms for correlated quantum matter, we envision seminal advances in predicting many-body quantum states and describing excitonic quantum matter and large-scale entangled states, a better understanding of high-temperature superconductivity, and quantifying open quantum system dynamics.