Physics – Quantum Physics
Scientific paper
2010-09-02
Physics
Quantum Physics
18 pages
Scientific paper
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.
Iwama Kazuo
Nishimura Harumichi
Raymond Rudy
Teruyama Junichi
No associations
LandOfFree
Quantum Counterfeit Coin Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Quantum Counterfeit Coin Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Counterfeit Coin Problems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-376091