Leveraging near-term quantum computing for spin chemistry and combinatorial optimization