文章基本信息

标题：Exact Quantum Query Complexity of EXACT and THRESHOLD
本地全文：下载
作者：Andris Ambainis ; Janis Iraids ; Juris Smotrovs 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2013
卷号：22
页码：263-269
DOI：10.4230/LIPIcs.TQC.2013.263
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：A quantum algorithm is exact if it always produces the correct answer, on any input. Coming up with exact quantum algorithms that substantially outperform the best classical algorithm has been a quite challenging task. In this paper, we present two new exact quantum algorithms for natural problems: - for the problem EXACT_k^n in which we have to determine whether the sequence of input bits x_1, ..., x_n contains exactly k values x_i=1; - for the problem THRESHOLD_k^n in which we have to determine if at least k of n input bits are equal to 1.
关键词：Quantum query algorithms; Complexity of Boolean functions