★grads.net/bibliography

WIKINDX Resources

Report/Documentation:

BibTeX citation key: Hoyer2005a

P. Høyer and R. Špalek, “Lower Bounds on Quantum Query Complexity,” 2005.
Added by: D. L. Yonge-Mallo 2008-10-03 16:04:25

Categories: Quantum computing
Keywords: lower bounds, Quantum query complexity
Creators: Špalek, Høyer

Number of views: 31
Popularity index: 58.49%

Abstract

Shor's and Grover's famous quantum algorithms for factoring and searching show that quantum computers can solve certain computational problems significantly faster than any classical computer. We discuss here what quantum computers_cannot_ do, and specifically how to prove limits on their computational power. We cover the main known techniques for proving lower bounds, and exemplify and compare the methods.
Added by: D. L. Yonge-Mallo

Further information may be found at:

http://arxiv.org/abs/quant-ph/0509153

Wikindx

Bookmarks

Resources

Metadata

Help

Statistics

WIKINDX Resources