Quantum chemical methods for the description of molecular polaritonic states in the strong coupling regime based on the Pauli-Fierz Hamiltonian are introduced. Based on a quantum electrodynamic Hartree-Fock (QED-HF) reference, a QED Møller-Plesset perturbation theory of second order for the electronic ground state and a second order quantum electrodynamic algebraic diagrammatic construction scheme for the polarization propagator [QED-ADC(2)] for excited electronic states have been derived, implemented, and tested for polaritons in hydrogen fluoride. Analogous approaches based on a standard non-polaritonic HF reference are also presented and thoroughly compared, both algebraically and numerically, to those based on the QED-HF reference. Furthermore, a promising route to approximate QED-ADC methods based on a unitary transformation of the algebraic expression into a restricted state space is outlined showing excellent agreement in second order with QED-ADC(2). All presented novel methods are compared to and tested against other existing ab initio approaches, mostly QED coupled cluster theory, including single and double excitations, and show qualitative agreement at a reduced computational effort.