Quantum interference as a resource for quantum speedup

Understand

Quantum states can in a sense be thought of as generalizations of classical probability distributions, but are more powerful than probability distributions when used for computation or communication.

• Quantum speedup therefore requires some feature of quantum states that classical probability distributions lack.
• One such feature is interference.
• We quantify interference and show that there can be no quantum speedup due to a small number of operations incapable of generating large amounts of interference (although large numbers of such operations can in fact lead to quantum speedup).