[Cryptography] Fuzzy Grover
Mike Hamburg
mike at shiftleft.org
Tue Jun 27 03:00:53 EDT 2017
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>
More information about the cryptography
mailing list