Understanding chemical structure and reactivity at physical interfaces is fundamentally important for modern society. Interfacial structure and reactivity are involved in myriad everyday processes: catalysis, tribology, electrochemistry, industrial-scale chemical processing and the production of advanced materials. They are also of crucial interest in the context of nuclear fusion where a better understanding of plasma-wall interactions (PWI) requires accurate atomic-scale modeling. Unfortunately, despite leaps in modern computer technology, quantum chemical simulations remain incapable of probing interfacial structure and reactivity on experimentally relevant scales. Consequently, small-scale theoretical models of physical interfaces remain largely disconnected from their real-world counterparts. In order to bridge this gap, our group has recently developed an ultrafast linear-scaling quantum chemical method by the combination of an approximate density functional theory method (DFTB) [1] and the fragment molecular orbital (FMO) [2] approach we call “FMO-DFTB” [3] for molecular systems such as polymers and liquid/solid interfaces. In collaboration with the Nakai group we also developed a divide-and-conquer-based DFTB method (DC-DFTB) [4] more suitable for extended systems. Both methods can be employed on massively parallel computer architectures. In the presentation I will briefly introduce these methods and report recent DFTB-based simulations of PWI and graphene growth on transition metal surfaces as representative examples.