Recently a great deal of attention has been focused on quantum computa
tion Following a sequence of results [Bernstein and Vazirani, in Proc.
25th Annual ACM Symposium Theory Comput., 1993, pp. 11-20, SIAM J. Co
mput., 26 (1997), pp. 1411-1473], [Simon, in Proc. 35th Annual IEEE Sy
mposium Foundation Comput. Sci., 1994, pp. 116-123, SIAM J. Comput., 2
6 (1997), pp. 1474-1483], [Shor, in Proc. 35th Annual IEEE Symposium F
oundations Comput. Sci., 1994, pp. 124-134] suggesting that quantum co
mputers are more powerful than classical probabilistic computers. Foll
owing Shor's result that factoring and the extraction of discrete loga
rithms are both solvable in quantum polynomial time, it is natural to
ask whether all of NP can be efficiently solved in quantum polynomial
time. In this paper, we address this question by proving that relative
to an oracle chosen uniformly at random with probability 1 the class
NP cannot be solved on a quantum Turing machine (QTM) in time o(2(n/2)
). We also show that relative to a permutation oracle chosen uniformly
at random with probability 1 the class NP boolean AND co-NP cannot be
solved on a QTM in time o(2(n/3)). The former bound is tight since re
cent work of Grover [in Proc. 28th Annual ACM Symposium Theory Comput.
, 1996] shows how to accept the class NP relative to any oracle on a q
uantum computer in time O(2(n/2)).