Further advancement of quantum computing (QC) is contingent on enabling many-body models that avoid deep circuits and excessive use of CNOT gates. To this end, we develop a QC approach employing finite-order connected moment expansions (CMX) and affordable procedures for initial state preparation. We demonstrate the performance of our approach employing several quantum variants of CMX through the classical emulations on the H2 molecule potential energy surface and the Anderson model with a broad range of correlation strength. The results show that our approach is robust and flexible. Good agreement with exact solutions can be maintained even at the dissociation and strong correlation limits.