5
$\begingroup$

I'm interested in deciding if an oracle is constant or not, but cannot guarantee that the non-constant oracles are balanced. The Deutsch-Jozsa seems like the obvious starting place, but handling the non-constant case deterministic(ie with probability 1) is evading me.

Just a clarification: I'm only interested in knowing if it is constant, not for what values it diverges. If there was some way of deciding whether the resulting superposition was in an eigenstate or not, that would suffice.

Any help would be appreciated.

Edit: Per my comments below, I don't see the reduce from general search to constancy checking. This is why I do not believe the optimality of Grover's search precludes a faster solution to my original problem. Perhaps such a floor would hold if the problem statement allowed oracles to refuse inputs, but I'm not interested in such a case.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

This is not so straightforward, I suspect. The issue is being able to distinguish between the constant case (e.g. every input gives output 0) and the case where only one input returns 1, and all others return 0. To distinguish these cases is essentially a Grover Search (the return of 1 being essentially a marked item that you want to search for the existence of), which takes a lot longer.

So, my guess for how things would work is:

  • run a standard Deutsch-Jozsa a few times. If the answer is not 'constant' every time, you know your function was not constant. If the answer is 'constant' every time, you can estimate how much imbalance the function has (since it will be almost constant)
  • run a Grover search for unknown numbers of marked items.

To be a bit more precise: You have an oracle the evaluates a function $f:\{0,1\}^n\mapsto\{0,1\}$. I'll denote the set of all possible functions of this form by $\Lambda$. You want to always determine if $f$ is constant or not. Hence, to be able to resolve this question, it is necessary to be also be able to resolve the question on any subset of possible functions $\lambda\subset\Lambda$. Clearly, if you know the set is $\lambda$ not $\Lambda$, you know more so it must be easier (or, at least, no more difficult).

So, I'm going to make a particular choice for $\lambda$: the constant function and any of the $2^n$ functions which have exactly 1 output of 1. Now we can consider the action of evaluating the oracle as 'marking' an item, and our question for deciding if $f\in\lambda$ is constant is the same as resolving whether the oracle marks 0 or 1 items (where the one marked item could be any). This is exactly the sort of decision problem that Grover's search is built to answer. I know it happens to tell you, as well, which item is marked, but that doesn't change things.

Indeed, perhaps a stronger way to think about this is, instead, to let $f(x)$ be the verifier for an NP-complete problem such as 3-SAT. There is then a decision problem to resolve if there exists an $x$ such that $f(x)=1$. Since this is NP-complete and we believe NP$\neq$ BQP, we believe, at the very least, that it will take super-polynomial time to resolve the question of whether $f$ is constant or not.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Since the oracles can have arbitrarily large input sizes Grover's will not be fast enough at O(sqrt(2^n)) queries. Similarly, if only one of the 2^n possible inputs is divergent, the resulting superposition will be heavily skewed and the number of ds calls required to achieve confidence will be quite large. Moreover, I'm looking for a deterministic result. I currently see two possible avenues: 1. A way to indirectly detect if the phase is +/- 1 without measurement. 2. A way to adjust the start state that ensures even a single nonconstant value causes the phase kickback to "fall apart." $\endgroup$
    – haskellcurrying
    Aug 12, 2019 at 21:41
  • 1
    $\begingroup$ @haskellcurrying Since Grover's is optimal for distinguishing the existence of 0 and 1 marked items, I don't think you'll be able to do better. $\endgroup$
    – DaftWullie
    Aug 13, 2019 at 14:33
  • $\begingroup$ Thanks for circling back. I was worried about that might be the case. I'm going to do some more digging before I mark your answer as accepted. Any idea where I might look to get some confidence on this result? Not the optimality of Grover, but why this might not be possible. $\endgroup$
    – haskellcurrying
    Aug 13, 2019 at 19:57
  • 1
    $\begingroup$ What is the difference between "Grover's algorithm is optimal" and "it is not possible to do better than Grover in distinguishing constant functions from non-constant functions"? In any case, the following lecture notes by Ryan O'Donell [ cs.cmu.edu/~odonnell/quantum15/lecture11.pdf ] ought to cover it, and provide some context. $\endgroup$
    – Niel de Beaudrap
    Aug 15, 2019 at 10:40
  • $\begingroup$ I posed my original question because the reduction isn't apparent to me. Using the decision version of simple search (IE is x in S), a reduction to a "constancy checking" oracle would only directly map the constant "yes" case to the "no" case for the search problem. An answer of "no" to constancy doesn't get you much for search. It is, at best, a "maybe." Even the mapping from an unstructured set in the case of search to countable ordered sequence in the case of constancy checking seems non-obvious. Hope that clarifies my question! Apologies for not doing a proper job upfront. $\endgroup$
    – haskellcurrying
    Aug 15, 2019 at 21:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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