I'm trying to build a deep understanding of where the power of quantum computing comes from when compared to probabilistic computing. A naive observation might be that probabilistic computing would be just as powerful since both give you a single result from a set of possible results with a certain probability. I've come to understand that quantum computing is more powerful, because unlike with probabilistic computing, quantum computers can make the probabilities interfere with each other to suppress undesired results, and enhance desired results.
Is there a simple quantum gate that shows this suppression and enhancements of results in action? I think that that would really help me tie the intuition behind quantum computers to the concrete mathematical description of quantum gates.
And how does all this relate to entanglement? Is entanglement required to get useful results out of interference?