|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
25 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Quantum Counterfeit Coin Problems | | Kazuo Iwama
; Harumichi Nishimura
; Rudy Raymond
; Junichi Teruyama
; | | Date: |
2 Sep 2010 | | Abstract: | 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(klog(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. | | Source: | arXiv, 1009.0416 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER