Quantum Algorithms for Highly Structured Search Problems

作     者：Hunziker, Markus Meyer, David A. 

作者机构：Univ Calif San Diego Dept Math La Jolla CA 92093 USA 

出 版 物：《QUANTUM INFORMATION PROCESSING》 (量子信息处理)

年 卷 期：2002年第1卷第3期

页      面：145-154页

核心收录：

学科分类：07[理学] 070201[理学-理论物理] 0702[理学-物理学] 

基　　金：National Security Agency (NSA) Advanced Research and Development Activity (ARDA) under Army Research Office (ARO) [DAAD19-01-1-0520] Defense Advanced Research Projects Agency (DARPA) under DARPA/SSC [N66001-00-C-8040] Orincon Corporation National Science Foundation (NSF) [ECS-0202087] 

主　　题：quantum search query complexity 

摘      要：We consider the problem of identifying a base k string given an oracle which returns information about the number of correct components in a query, specifically, the Hamming distance between the query and the solution, modulo r = max{2, 6 - k}. Classically this problem requires Omega(n log(r) k) queries. For k is an element of {2, 3, 4}, we construct quantum algorithms requiring only a single quantum query. For k 4, we show that O(root k) quantum queries suffice. In both cases the quantum algorithms are optimal.