Is there any proof that quantum computers are more efficient than classical computers?
Yes, Grover's algorithm shows you can use a quantum algorithm to find an element in an unordered database of size $N$ with high probability by querying the database only $O(\sqrt{N})$ times. Any classical solution that succeeds with high probability requires $\Omega (N)$ queries to the database.