Ttdfjt

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.

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^nmapsto0,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 $lambdasubsetLambda$. 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 $finlambda$ 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.