|
ИСТИНА |
Войти в систему Регистрация |
ФНКЦ РР |
||
Lower bounds of a quantum search for an extreme point, Proc.R.Soc.Lond. Aстатья
Информация о цитировании статьи получена из
Web of Science,
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 13 марта 2014 г.
- Автор: Ozhigov Y.I.
- Журнал: Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences
- Том: 455
- Год издания: 1999
- Издательство: Royal Society of London
- Местоположение издательства: United Kingdom
- Первая страница: 2165
- Последняя страница: 2172
- Аннотация: We show that Durr-Hoyer's quantum algorithm of searching for extreme point of integer function can not be sped up for functions chosen randomly. Any other algorithm acting in substantially shorter time $o(\sqrt{2^n})$ gives incorrect answer for the functions with the single point of maximum chosen randomly with probability converging to 1. The lower bound as $\Omega (\sqrt{2^n /b})$ was established for the quantum search for solution of equations $f(x)=1$ where $f$ is a Boolean function with $b$ such solutions chosen at random with probability converging to 1.
- Добавил в систему: Ожигов Юрий Игоревич