The six- and eight-vertex models originate in statistical mechanics for crystal lattices with hydrogen bonds. The first such model was introduced by Linus Pauling in 1935 to account for the residual entropy of water ice. The family of models not only are among the most extensively studied topics in physics, but also have fascinated chemists, mathematicians, theoretical computer scientists, and others, with thousands of papers studying their properties and connections to other fields. In this dissertation, we study the computational complexity of approximately counting and sampling in the six- and eight-vertex models on various classes of underlying graphs. First, we study the approximability of the partition function on general 4-regular graphs, classified according to the parameters of the models. Our complexity results conform to the phase transition phenomenon from physics due to the change in temperature. We introduce a quantum decomposition of the six- and eight-vertex models and prove a set of closure properties in various regions of the parameter space. These regions of the parameter space are concordant with the phase transition threshold. Using these closure properties, we derive polynomial time approximation algorithms via Markov chain Monte Carlo in some parameter space in the high temperature regime. In some other parameter space in the high temperature regime, we prove that the problem is (at least) as hard as approximately counting perfect matchings, a central open problem in this field. We also show that the six- and eight-vertex models are NP-hard to approximate in the whole low temperature regime on general 4-regular graphs. We then study the six- and eight-vertex models on more restricted classes of 4-regular graphs, including planar graphs and bipartite graphs. We give the first polynomial time approximation algorithm for the partition function in the low temperature regime on planar and on bipartite graphs. Our results show that the six- and eight-vertex models are the first problems with the provable property that while NP-hard to approximate on general graphs (even #P-hard for planar graphs in exact complexity), they possess efficient approximation schemes on both bipartite graphs and planar graphs in substantial regions of the parameter space. Finally, we study the square lattice six- and eight-vertex models. We prove that natural Markov chains for these models are mixing torpidly in the low temperature regime. Moreover, we give the first efficient approximate counting and sampling algorithms for the six- and the eight-vertex models on the square lattice at sufficiently low temperatures.