Moore's law has accurately described the speedup of current computer technologies for half a century. However, due to transistor fabrication limitations, speedup is slowly coming to an end. A promising alternative is given by quantum computers that potentially allow for massive parallelism. Many practical challenges in building these devices remain, such as dealing with decoherence and showing that quantum algorithms are more efficient than current technologies in solving a broad range of problems. Using methods from computational statistical physics one can address these problems by understanding the stability of new quantum storage and processing schemes based on topological error codes to different error sources, testing the feasibility of annealing machine implementations via stringent benchmarks, and studying the efficiency of quantum optimization algorithms by classical proxies on large computer clusters.