D.R. Simon:
On the Power of Quantum Computation
This paper pioneered the use of quantum computation to achieve an exponential speed up to a problem of finding a hidden period of a function.
P.W. Shor:
Algorithms for Quantum Computation: Discrete Logarithms and Factoring
This paper gave quantum polynomial-time algorithms for factoring and discrete log. It has had a tremendous impact on the entire field of quantum computing and beyond.
M. Sipser, D.A. Spielman:
Expander Codes
This paper gave linear error-correcting codes based on expander graphs with various excellent properties. This work has been hugely influential in both the TCS and Coding Theory communities.