The First Quantum Speedup

Deutsch's algorithm determines if a function is 'constant' or 'balanced' in a single query. A classical computer would need two queries. This proves that quantum computers can be faster.