%0 Generic %1 citeulike:1196706 %A Hoyer, Peter %A Spalek, Robert %D 2005 %K complexity quantum query %T Lower Bounds on Quantum Query Complexity %U http://arxiv.org/abs/quant-ph/0509153 %X 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.

@misc{citeulike:1196706, 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-at = {2007-08-18T13:22:24.000+0200}, author = {Hoyer, Peter and Spalek, Robert}, biburl = {https://www.bibsonomy.org/bibtex/2639ec6ceed395c1bda7fdeb8f3fadbcc/a_olympia}, citeulike-article-id = {1196706}, description = {citeulike}, eprint = {quant-ph/0509153}, interhash = {c9ad4a7d9cc5c8f8d56c49e421ba9195}, intrahash = {639ec6ceed395c1bda7fdeb8f3fadbcc}, keywords = {complexity quantum query}, month = Sep, priority = {2}, timestamp = {2007-08-18T13:22:28.000+0200}, title = {Lower Bounds on Quantum Query Complexity}, url = {http://arxiv.org/abs/quant-ph/0509153}, year = 2005 }