
doi: 10.1007/11533719_44
This paper gives a quantum algorithm to search in an set S for a k-tuple satisfying some predefined relation, with the promise that some components of a desired k-tuple are in some subsets of S. In particular when k=2, we show a tight bound of the quantum query complexity for the Claw Finding problem, improving previous upper and lower bounds by Buhrman, Durr, Heiligman, Hoyer, Magniez, Santha and de Wolf [7]. We also consider the distributed scenario, where two parties each holds an n-element set, and they want to decide whether the two sets share a common element. We show a family of protocols s.t.q(P)3/2 . c(P)= O(n2log n), where q(P) and c(P) are the number of quantum queries and the number of communication qubits that the protocol P makes, respectively. This implies that we can pay more for quantum queries to save on quantum communication, and vice versa. To our knowledge, it is the first result about the tradeoff between the two resources.
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 18 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
