Journal
INFORMATION PROCESSING LETTERS
Volume 97, Issue 5, Pages 208-211Publisher
ELSEVIER
DOI: 10.1016/j.ipl.2005.01.016
Keywords
computational complexity; quantum computing; cryptography
Categories
Ask authors/readers for more resources
At the heart of the Goldreich-Levin theorem is the problem of determining an n-bit string a by making queries to two oracles, referred to as IP (inner product) and EQ (equivalence). The IP oracle, on input x, returns a bit that is biased towards a (.) x (the modulo two inner product of a with x) in the following sense. For a random x, the probability that IP(x) = a (.) x is at least 1/2(1 + epsilon). The EQ oracle, on input x, returns a bit specifying whether or not x = a. It has been shown that a quantum algorithm can solve this problem with O(1/epsilon) IP and EQ queries, whereas any classical algorithm requires Omega(n/epsilon(2)) such queries. Also, the quantum algorithm requires only O(n/epsilon) auxiliary one- and two-qubit gates in addition to its queries. We show that the above quantum algorithm is optimal in terms of both EQ and IP queries. Specifically, Omega(1/epsilon) EQ queries are necessary, and Omega(1/epsilon) IP queries are necessary if the number of EQ queries is o(root 2(n)). (c) 2005 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available