A quantum lower bound for the query complexity of Simon's problem

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

Simon in his FOCS'94 paper was the first to show an exponential gap between classical and quantum computation. The problem he dealt with is now part of a well-studied class of problems, the hidden subgroup problems. We study Simon's problem from the point of view of quantum query complexity and give here a first nontrivial lower bound on the query complexity of a hidden subgroup problem, namely Simon's problem. Our bound is optimal up to a constant factor.
8 pages, 1 figure

Keywords

Quantum Physics, Computational Complexity

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/92642

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/quant-ph/0501060
 http://arxiv.org/abs/quant-ph/0501060

Collections

arXiv