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.
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.