Well, you can run multiple simultaneous particle chains and sum their results. There's some wasted work since each will need to burn in, but modern algorithms can make that go quite quickly.
MCMC is also used for finding MAP solutions, an operation which is strictly less difficult than computing the partition function.