期刊
THEORETICAL COMPUTER SCIENCE
卷 456, 期 -, 页码 51-64出版社
ELSEVIER
DOI: 10.1016/j.tcs.2012.05.039
关键词
Counterfeit coin problems; Quantum computing; Query complexity
资金
- Grants-in-Aid for Scientific Research [21244007, 22240001, 22700014] Funding Source: KAKEN
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据