Promised and Distributed Quantum Search
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 5. 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 ·c(P)=O(n2 log 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.
Shengyu Zhang
Computer Science Department, Princeton University, NJ 08544, USA
国际会议
The 11th Annual International Computing and Combinatorics Conference COCOON 2005(第11届国际计算和组合会议)
昆明
英文
430-439
2005-08-01（万方平台首次上网日期，不代表论文的发表时间）