[Cryptography] Fuzzy Grover

[Mike Hamburg]

Hello Crypto list,

I’m curious about quantum solutions to a variant of search.

Suppose I have a distribution D on the interval [0,1], and a function F(seed) which samples from D using a random oracle.

An adversary wants to find seeds such that F(seed) is large, and in particular wants to write a quantum algorithm that maximizes the expectation of F(seed).

If the distribution is only supported on the endpoints {0,1}, then this is just search and Grover is known to be optimal.  With t quantum oracle evaluations, it produces expectation something like min(1, t^2 * pr(1)).

But what if it’s not just {0,1}?  Grover can still be applied, just by setting a cutoff x and searching for seeds where F(seed) > x.  But is this optimal, or is there some kind of “fuzzy Grover’s algorithm” that improves on it?

Thanks,
— Mike
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 3571 bytes
Desc: not available
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20170627/7d94f0e8/attachment.bin>