As is well known Grover's algorithm can invert a function on a domain of 2^n possible values in other words it can find an x such that f(x)=1 if such an x exists for the oracle f(x). Suppose we are not interested to find the specific value of x but instead want to know if it is true or false if such an x exists and satisfies f(x)=1? What is there a polynomial time and polynomial space quantum algorithm that can decide if such an f exists? The obvious solution is just to use the exponential Grover's algorithm and that can be decided to know if such an x exists-but cam we do better than this?-in other words is there a polynomial time and polynomial space algorithm to decide if it is true or false if such an x exists in the domain? In this question there are not multiple solutions but only one solution if it exists.
-
$\begingroup$ Are you asking us to resolve the question $P=NP$? $\endgroup$– DaftWullieCommented Oct 13, 2023 at 16:02
-
$\begingroup$ Please consider and review "search versus decision" problems, e.g., here. In particular, if we had a way to decide whether one or zero solutions to our oracle exists using, say, $n$ queries, we can do a binary search to find the solution using $n\log n$ queries, by fixing particular qubits and recursing. Because Grover is optimal for search there's no further advantage for decision. $\endgroup$– Mark SpinelliCommented Oct 13, 2023 at 19:57
-
$\begingroup$ @MarkSpinelli I would say that deserves an answer: it answers the question and is quite interesting! At least, I've learned something reading this, so I'd like to upvote it! $\endgroup$– Tristan Nemoz ♦Commented Oct 14, 2023 at 8:05
2 Answers
The question appears to ask whether deciding if a problem has a solution could be easier than searching for the specific solution. But, at least for Grover's problem searching is only slightly harder than deciding, because we can do binary recursion at a small cost.
For example if we have a way to decide, in only $O(n^c)$ steps, if there's any $(x_1,\ldots,x_n)$ such that $f(x)=1$ promised that there's either zero or one solutions, we could find the solution in $O(n^c\log n)$ steps by recursively fixing each $x_i$ and deciding if there's a solution with $(0,\ldots,x_n)$; if not, is there a solution with $(1,\ldots,x_n)$; then recurse to fixing $x_2$, etc. Thus because Grover's algorithm is optimal for unstructured search, it must also be optimal for unstructured decision, and the answer to the OP's question is "no".
This is referred to as the "search to decision reduction" and it's an interesting project to deduce which problems admit such as reduction. Grover's problem does, as does graph isomorphism. As far as I know, however, it's not known whether knottedness admits a search-to-decision reduction. For example even if we have a fast way to deduce whether a knot is isotopic to the unknot we might not know how to untie the knot.
One other problem unique to quantum computing that might not have such a search-to-decision reduction is the "welded trees" problem of Childs et al. - as explained in this Quanta article. That is, in the welded trees problem we might easily know the vertex label of the EXIT node but we might not have a quick way to know how to traverse the maze to get there.
Although Quanta framed the question as "forgetting" the path from whence the particle came, it's morally equivalent to asking if there's a search-to-decision reduction for their oracle problem.
In fact, being able to figure out if 1 has a preimage or not is equivalent to distinguishing two oracles: $O_f$ with $O_f|x\rangle|y\rangle=|x\rangle|y\oplus f(x)\rangle$, and $O_0$, where $0$ is the constant function with the value $0$. (So, $O_0$ is in fact the identity operator $I$.)
Often, the optimality proof of the Grover search is formulated as hardness of distinguishing $O_f$ and $I$, and to be able to distinguish with constant advantage, you need to make $\Omega(\sqrt{2^n})$ queries. For example, this survey article contains a version of such a proof (Theorem 10).
