You can't get the exact answer, but you can approach it exponentially quickly by doing a binary search. So, if you want N digits of accuracy, you're going to need O(N) time. Someone mentioned this elsewhere but I can't find the comment now.

Your method above would work better, actually (assuming the function is valued from 0 to 1). Just randomly guess x, compute f(x)^n, then place a qubit in a superposition such that it is f(x)^n likely to be 0, and 1 - f(x)^n likely to be 1. Measure the qubit. If it is 0, quantum suicide. You can do the whole thing a few times, taking n = 10, n = 1000, and so on, until you're satisfied you've actually got the minimum. Of course, there's always the chance there's a slightly smaller minimum somewhere, so we're just getting an approximate answer like before, albeit an incredibly good approximate answer.