5
$\begingroup$

It's well known that, given an oracle for a function $f$ from a very large set $S$ (of order $N \gg 1$) to $\{0, 1\}$, Grover's algorithm can find an element of $S$ that maps to 1 with $\sim \sqrt{N}$ oracle queries, whereas the best classical oracle search algorithm requires $\sim N$ queries.

From this, it's often claimed that a quantum computing running Grover's algorithm could give useful speedups for many practical computational problems (since many such problems, e.g. numerical optimization, can be framed in this form).

But Grover's algorithm is a "black-box" algorithm that treats the oracle as the only method of getting any information at all about the solution to your problem. It completely ignores any possible correlations between the oracle's responses for different inputs, or any other "structure" behind the computation to be solved. Grover's algorithm therefore gives a square-root speedup over completely naive, brute-force search of every possible solution.

But it seems to me that (loosely speaking), most "interesting" or "practical" computational problems have enough structure that complete brute-force guessing is rarely the best classical approach. As a simple example, for numerically optimizing some complicated but differentiable function, gradient descent (plus some means of escaping from local minima) is typically vastly more efficient than random sampling.

Now an exponential (classical) speedup over brute-force guessing is too much to hope for in general: if $\mathrm{P} \neq \mathrm{NP}$ (which is presumably the case), then there exist problems in NP that do not admit exponential (classical) improvements over brute-force guessing that work even in the worst case. But even NP-complete problems often admit heuristic algorithms that allow for efficient solutions "in practice", e.g. they work for most problem instances. Even when this is not the case, my intuition is that most "practical" problems admit classical algorithms that provide an algebraic speedup over brute-force guessing that is better than square-root, at least for many problem instances. So my intuition is that for most "practical" problems, there's usually a heuristic classical algorithm that's more efficient than using Grover's algorithm for a square-root speedup over brute-force search.1

Is my intuition correct? Are they many practical problems for which the best known classical algorithms deliver less than a square-root speedup over brute force guessing "in practice"? (I guess the somewhat sharper version of "in practice" means "in the average case", but I'm also interested in less formal interpretations of "in practice" as well.) More bluntly, would a quantum computing running Grover's algorithm actually be that useful for many practical computational problems?

(Strictly speaking, this is just a question about classical algorithms, but I think this is the right place to ask it, because people here are more likely to have thought about quantum speedups for these kind of problems.)


1 The only type of problem for which I wouldn't expect any classical algorithm to provide a significant improvement over brute-force search is one where the mathematical structure has been deliberately chosen to be as complicated and obfuscated as possible. For example, inverting cryptographic hash functions or cracking a symmetric-key encryption algorithm like AES. This means that, ironically, the only type of math problem for which I can intuitively see Grover's algorithm delivering a clear quantum speedup is breaking symmetric-key encryption and hashes. (This is ironic because the main application for the other most famous quantum algorithm, Shor's algorithm, is of course also for breaking cryptography, although public-key rather than symmetric-key.)

$\endgroup$
  • $\begingroup$ According to this thread from a sister site, the best classical upper bounds for $\mathsf{3SAT}$ are $O(1.3...^n)$. Wouldn't Grover give you $O(2^{n/2})$? $\endgroup$ – Mark S Aug 9 at 23:29
  • 1
    $\begingroup$ @MarkS Yeah, which equals $1.414...^n$ - not as good. $\endgroup$ – tparker Aug 9 at 23:31
  • $\begingroup$ But can't you do Grover on all of the grunt-work in that $O(1.3...^n)$ classical algorithm? $\endgroup$ – Mark S Aug 9 at 23:33
  • $\begingroup$ @MarkS I don't think so. Grover only works on completely unstructured search. If the "grunt work" in the classical algorithm exploits the problem structure in any way, then you can't use Grover. $\endgroup$ – tparker Aug 9 at 23:38
  • $\begingroup$ You might be interested in this paper: link.springer.com/chapter/10.1007/978-3-540-78773-0_67 $\endgroup$ – DaftWullie Aug 16 at 7:53
0
$\begingroup$

Grover Search Algorithm has complexity of O(√(N/n) oracle queries, where N is the total no. of elements in search space & n is the number of acceptable solutions. And is very useful for all problems where we do not know the structure or insight about the problem. Further, even if we know the structure / insight / domain information about the practical / real world problems, we still have to perform some search either random or deterministic, which may in turn benefit from Grover's Algorithm depending on the specific problem being solved. Therefore, even if an efficient algorithm (O(log(N))) exists in classical computation it can be made still more efficient by using Grover's Search.

Further, Quantum Oracles, in theory, can be implemented for any problem that can be solved using classical Digital Computation as all such logic can be implemented using reversible logic gates. Therefore, Oracle can be designed to incorporate the some structures like feasibility checks in constrained Numerical Optimization problem. Though Oracle will answer only in {0, 1}, but for which inputs it will give 1, can be designed in the Oracle by using the domain information. Thus, Grover search will find more applications in Real World Optimization Problems than in unsorted database search.

$\endgroup$
0
$\begingroup$

I found the answer in these notes:

For an ​NP​-complete problem like CircuitSAT, we can be pretty confident that the Grover speedup is real, because no one has found any classical algorithm that’s even slightly better than brute force. On the other hand, for more “structured” ​NP​-complete problems, we ​do​ know exponential-time algorithms that are faster than brute force: for example, 3SAT is solvable in about $O(1.3​^n​)$ time. So then the question becomes a subtle one, of whether Grover’s algorithm can be ​combined​ with the best classical tricks that we know, to achieve a polynomial speedup even compared to a classical computer that uses the same tricks. For many ​NP​-complete problems, the answer seems to be yes, but it need not be yes for all of them.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.