In their seminal paper, Bennett, Bernstein, Brassard and Vazirani
[SICOMP, 1997] showed that relative to an oracle, quantum
algorithms are unable to solve NP-complete problems in
sub-exponential time (i.e., that Grover's search is optimal in
this...
Read More
