Physics – Quantum Physics
Scientific paper
2000-07-07
Physics
Quantum Physics
19 pages, a preliminary version appeared in FOCS 2000. This is the journal version, which will appear in Algorithmica (Special
Scientific paper
We study the quantum complexity of the static set membership problem: given a subset S (|S| \leq n) of a universe of size m (m \gg n), store it as a table of bits so that queries of the form `Is x \in S?' can be answered. The goal is to use a small table and yet answer queries using few bitprobes. This problem was considered recently by Buhrman, Miltersen, Radhakrishnan and Venkatesh, where lower and upper bounds were shown for this problem in the classical deterministic and randomized models. In this paper, we formulate this problem in the "quantum bitprobe model" and show tradeoff results between space and time.In this model, the storage scheme is classical but the query scheme is quantum.We show, roughly speaking, that similar lower bounds hold in the quantum model as in the classical model, which imply that the classical upper bounds are more or less tight even in the quantum case. Our lower bounds are proved using linear algebraic techniques.
Radhakrishnan Jaikumar
Sen Pranab
Venkatesh Suresh
No associations
LandOfFree
The Quantum Complexity of Set Membership 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 The Quantum Complexity of Set Membership, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Quantum Complexity of Set Membership will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-575070