Reference · 1997
Strengths and weaknesses of quantum computing
Bennett, C. H., Bernstein, E., Brassard, G., & Vazirani, U. (1997). Strengths and weaknesses of quantum computing. SIAM Journal on Computing, 26(5), 1510–1523.
- Authors
- Charles H. Bennett; Ethan Bernstein; Gilles Brassard; Umesh Vazirani
- Venue
- SIAM Journal on Computing 26(5), 1510–1523
Proves that, relative to a random oracle, NP cannot be solved on a quantum Turing machine in time o(2^(n/2)), and notes that Grover's O(2^(n/2)) algorithm makes the bound tight. This library cites that statement on Grover's algorithm and in the cryptography and optimization stubs, including the authors' caution that an oracle result does not by itself refute NP ⊆ BQP.
Cited by
- Cryptographytopic
- Grover's algorithmalgorithm
- Optimizationtopic
- Query complexityglossary
- What the source papers claimdigest
Updated 7 Oct 2026.