Here's my attempt at a two sentence over-over-over simplification that at least gets people away from the "magic bit-sting that contains your answer." (It also harkens back to an old Einstein quote, so may be attractive to science writers.)

Quantum computing is a technique that lets you sample a problem's answer-space using "loaded dice," such that the problem's correct answers correspond with probability spikes in your dice throws. Right now, we only know how to usefully "load" those dice for certain problems, and it's pretty hard to do.