Is there a simple quantum gate that shows off the power of Quantum interference?

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?

• Hadamard gate? Apply it once to the state $|0\rangle$ create the superposition... then apply it again to get back to the state $|0\rangle$ via destructive interference May 1 at 15:57
• Yes that shows off entanglement and interference, but doesn't show off the power of this kind of interference has to suppress unwanted results. I was wondering if there is some simple calculation where this interference can serve as a clear example of the power quantum computers have over classic computers. May 1 at 16:41
• Note that the Hadamard gate is a single qubit gate so it does not create entanglement. And in term of suppressing the unwanted results using the Hadamard gate, look at the Bernstein Vazarini algorithm. May 1 at 16:46
• This answer describes the details of an interference demonstration using the Hadamard gate that @KAJ226 mentioned. (Of course, this does not answer the question here about the computational capabilities offered by interference, but may still be of some interest.) May 1 at 19:53
• Thanks! Another question: We model all these operations as matrix calculations, but is there some sort of disconnect between these matrix calculations and the actual power of a quantum computer? Because a classic computer can easily do these matrix calculations? Or is the problem just that the size of these matrices grows exponentially with an increased amount of qubits? May 2 at 6:56