One of the most exciting potential applications of a quantum computer is the ability to efficiently simulate quantum systems, a task that is out of the reach of even the largest classical supercomputers. Such simulations require a quantum algorithm capable of efficiently representing and manipulating a quantum system, as well as a device with sufficient coherence to execute it. In this work, we describe experiments advancing both of these goals. First, we discuss dephasing---currently a leading cause of decoherence in superconducting qubits---and present measurements accurately quantifying both low- and high-frequency phase noise sources. We then discuss two quantum algorithms for the simulation of chemical Hamiltonians, and experimentally contrast their performance. These results show that with continuing improvement in quantum devices we may soon be able to apply quantum computers to practical chemistry problems.