Quantum counterfeit coin problems

作     者：Iwama, Kazuo Nishimura, Harumichi Raymond, Rudy Teruyama, Junichi 

作者机构：Nagoya Univ Grad Sch Informat Sci Chikusa Ku Nagoya Aichi 4648601 Japan Kyoto Univ Sch Informat Kyoto 6068501 Japan IBM Res Tokyo Yamato 2428502 Japan 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2012年第456卷

页      面：51-64页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Grants-in-Aid for Scientific Research [22700014  21244007  22240001] Funding Source: KAKEN 

主　　题：Counterfeit coin problems Quantum computing Query complexity 

摘      要：The counterfeit coin problem requires us to find all false coins from a given bunch of coins using a balance scale. We assume that the balance scale gives us only balanced or tilted information and that we know the number k of false coins in advance. The balance scale can be modeled by a certain type of oracle and its query complexity is a measure for the cost of weighing algorithms (the number of weighings). In this paper, we study the quantum query complexity for this problem. Let Q(k, N) be the quantum query complexity of finding all k false coins from the N given coins. We show that for any k and N such that k N/2, Q(k, N) = O(k(1/4)), contrasting with the classical query complexity, Omega (k log(N/k)), that depends on N. So our quantum algorithm achieves a quartic speed-up for this problem. We do not have a matching lower bound, but we show some evidence that the upper bound is tight: any algorithm, including our algorithm, that satisfies certain properties needs Omega(k(1/4)) queries. (C) 2012 Elsevier B.V. All rights reserved.